// Name : Matthew Reeves 
// This class creates and alters a linked list 

package ListPkg;

import ExceptionPkg.EmptyListException;

//this class is part of the created package ListPkg and it manipulates 
//individual nodes

class ListNode
{
	//initializes instance variables for this class

	Object data;
	ListNode nextNode;
	
	//constructor with just one Object parameter	

	public ListNode(Object object)
	{
		this(object, null);
	}

	//constructor with both Object and listnode parameters 
	
	public ListNode(Object object, ListNode node)
	{
		data=object;
		nextNode=node;
	}

	//retrieves the reference to the data that a node references

	public Object getObject()
	{
		return data;
	}

	//retrieve the reference to the next node	

	public ListNode getNext()
	{
		return nextNode;
	}
}

//class that manipulates the list, such as adding/removing data from the list

public class LinkedList
{
	//initializes instance variables for this class

	ListNode firstNode;
	ListNode lastNode;
	int numElements;
	String name;

	//default constructor

	public LinkedList()
	{
		this ("List");
	}

	//constructor that accepts the name for the list, and initializes list

	public LinkedList(String listName)
	{
		name=listName;
		firstNode=lastNode=null;
		numElements=0;
	}

	//inserts values to list from front of list

	protected void insertAtFront(Object insertItem)
	{
		if (isEmpty())
		{
			firstNode=lastNode=new ListNode(insertItem);
		}
		else
		{
			firstNode=new ListNode(insertItem, firstNode);
		}
	
		numElements++;
	}
	
	//inserts values to list from back of list

	protected void insertAtBack(Object insertItem)
	{
		if (isEmpty())
		{
			firstNode=lastNode=new ListNode(insertItem);
		}
		else
		{
			lastNode=lastNode.nextNode=new ListNode(insertItem);
		}
	
		numElements++;
	}

	//removes values from front of list

	protected Object removeFromFront() throws EmptyListException
	{
		if (isEmpty())
		{
			throw new EmptyListException(name);
		}
	
		Object removedItem=firstNode.data;
		
		if (firstNode==lastNode)
		{
			firstNode=lastNode= null;
		}	
		else
		{
			firstNode=firstNode.nextNode;
		}	
	
		numElements--;
	
		return removedItem;
	}

	//removes values from back of list
	
	protected Object removeFromBack () throws EmptyListException 
	{
		if (isEmpty())
		{
			throw new EmptyListException(name);
		}

		Object removedItem=lastNode.data;
		
		if (firstNode==lastNode)
		{
			firstNode=lastNode=null;
		}
		else 
		{
			ListNode current=firstNode;

			while (current.nextNode!=lastNode)
			{
				current=current.nextNode;
			}

			lastNode=current;
			lastNode.nextNode=null;
		}

		numElements--;

		return removedItem;
	}

	//searches list for a specific value, and removes it if found

	protected boolean findAndRemove (Object item) throws EmptyListException 
	{
		boolean found=false;

		if (isEmpty())
		{
			throw new EmptyListException(name);
		}
		else 
		{
			if ((firstNode.data).equals(item)) 
			{
				removeFromFront();
				found=true;
			}
			else 
			{
				ListNode current=firstNode;

				while (current.nextNode!=null&&!found) 
				{
					if ((current.nextNode.getObject()).equals(item))
					{
						found=true;
					}
					else
					{
						current=current.nextNode;
					}
				}				
	
				if (found)
				{
					if (current.nextNode==lastNode)
					{
						lastNode=current;
					}

					current.nextNode=current.nextNode.nextNode;
			
					numElements--;
				}
			}		
		}
	
		return found;
	}	

	//searches list to determine if an item is present

	protected boolean findItem (Object item) 
	{
		boolean found=false;

		if (!isEmpty())
		{
			ListNode current=firstNode;

			while (current!=null&&!found) 
			{
				if ((current.getObject()).equals(item))
				{			
					found=true;
				}
				else
				{
					current=current.nextNode;
				}
			}		
		}
	
		return found;
	}

	//returns the number of items stored in list

	public int lengthIs()
	{
		return numElements;
	}

	//checks to determine if list is empty

	public boolean isEmpty()
	{
		if (numElements<=0 || firstNode==null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	//prints the name of the list, and the values stored in list

	public void Print() 
	{
		if (isEmpty())
		{
			System.out.printf("The current list, %s, is: ***Empty list***\n\n",name);
		}
		else 
		{
			System.out.printf("The current list, %s, is: ",name);

			ListNode current=firstNode;

			while (current!=null) 
			{
				System.out.printf("%s ", current.data);
				current=current.nextNode;
			}
	
			System.out.println("\n");
		}
	}	

	//clears all values from list, and sets numElements to 0

	public void Clear()
	{
		numElements=0;
		firstNode=lastNode=null;
	}

	//creates a string showing the list from front to back

	public String toString()
	{
		if (numElements<=0)
		{
			return String.format("***Stack is Empty***\n\n");
		}
		else
		{
			String tempString="";

			ListNode current=firstNode;	
	
			for(int count=0;count<numElements;count++)
			{
				tempString=tempString + String.format("%s\n",current.data);
				current=current.nextNode;
			}
			
			return tempString;
		}
	}
}