import java.util.Collection;
import java.util.Iterator;

/*
 * CSE 214 - Spring 2009
 * HW 1 Solutions - SinglyLinkedList
 * Richard McKenna
 *  
 * YOU MUST FILL IN THE CODE FOR THE FOLLOWING TEN
 * METHODS IN THE SinglyLinkedList class:
 * public void addFirst(Object dataToAdd)
 * public void addLast(Object dataToAdd)
 * public void addAll(Collection c)
 * public void addAll(int index, Collection c)
 * public boolean contains(Object o)
 * public Object get(int index)
 * public void removeFirstOccurrence(Object o)
 * public void removeLastOccurrence(Object o)
 * public void set(int index, Object o)
 * public Object[] toArray()
 * 
 * AND YOU MUST ALSO DEFINE THE FOLLOWING TWO
 * METHODS INSIDE THE ListIterator INNER CLASS
 * - public boolean hasNext()
 * - public Object next()
 * 
 * NOTE: YOU MAY ADD INSTANCE VARIABLES AS NEEDED
 */
public class SinglyLinkedList 
{
	// FIRST NODE IN THE LIST
	private Node head = null;

	// LAST NODE IN THE LIST
	private Node tail = null;
	
	// NUMBER OF NODES IN THE LIST
	private int size = 0;
	
	/*
	 * Default Constructor
	 * 
	 * DO NOT CHANGE THIS METHOD
	 */
	public SinglyLinkedList() {}

	/*
	 * getSize - Accessor method that returns the
	 * number of nodes in the list.
	 * 
	 * DO NOT CHANGE THIS METHOD
	 */
	public int getSize() { return size; }

	/*
	 * clear - This method removes all nodes from
	 * the linked list.
	 * 
	 * DO NOT CHANGE THIS METHOD
	 */
	public void clear()

	{
		head = null;
		tail = null;
		size = 0;
	}
	
	/*
	 * addFirst -  Inserts the specified 
	 * element at the beginning of this list.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public void addFirst(Object dataToAdd)
	{
		head = new Node(dataToAdd, head);
		if (tail == null)
			tail = head;
		size++;
	}

	/*
	 * addLast - Appends the specified element
	 * to the end of this list.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void addLast(Object dataToAdd)
	{
		Node nodeToAdd = new Node(dataToAdd, null);
		if (head == null)
			head = nodeToAdd;
		else
			tail.next = nodeToAdd;
		tail = nodeToAdd;
		size++;		
	}

	/*
	 * addAll - Appends all of the elements in the 
	 * specified collection to the end of this list,
	 * in the order that they are returned by the 
	 * specified collection's iterator
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public void addAll(Collection c)
	{
		Iterator it = c.iterator();
		while (it.hasNext())
			addLast(it.next());
	}
	
	/*
	 * addAll - Inserts all of the elements in the 
	 * specified collection into this list, 
	 * starting at the specified position.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void addAll(int index, Collection c)
	{
		// IF NOTHING TO ADD, DO NOTHING
		if (c.size() == 0)
			return;
		// IF THIS LIST IS EMPTY, JUST ADD THEM TO END
		else if (size == 0)
			addAll(c);
		// IF IT'S AN ILLEGAL REQUEST, THROW EXCEPTION
		else if ((index < 0) || (index > size))
		{
			throw new IllegalArgumentException("Illegal index for addAll");
		}
		// IF WE ARE ADDING TO FRONT
		else
		{
			Iterator it = c.iterator();
			Node startNode = new Node(it.next(), null);
			Node addedNode = startNode;
			size++;

			while (it.hasNext())
			{
				Object o = it.next();
				Node nodeToAdd = new Node(o, null);
				addedNode.next = nodeToAdd;
				addedNode = nodeToAdd;
				size++;
			}

			if (index == 0)
			{
				addedNode.next = head;
				head = startNode;
			}
			else if (index == size)
			{
				tail.next = startNode;
				tail = addedNode;
			}
			else
			{
				Node traveller = head;
				int count = 0;
				while (count < index - 1)
				{
					traveller = traveller.next;
					count++;
				}
				addedNode.next = traveller.next;
				traveller.next = startNode;
			}
		}
	}
	
	/*
	 * contains - Returns true if this list contains 
	 * the specified element.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public boolean contains(Object o)
	{
		Node traveller = head;
		while (traveller != null)
		{
			if (traveller.data.equals(o))
				return true;
			traveller = traveller.next;
		}
		return false;
	}
	
	/*
	 * get - Returns the element at the 
	 * specified position in this list.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public Object get(int index)
	{
		int count = 0;
		Node traveller = head;
		while (count < index)
		{
			traveller = traveller.next;
			count++;
		}
		return traveller.data;	
	}

	/*
	 * removeFirstOccurrence - Removes the first 
	 * occurrence of the specified element in this 
	 * list (when traversing the list from head to tail).
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void removeFirstOccurrence(Object o)
	{
		// NO NODES IN THE LIST
		if (head == null)
			return;
		
		// FIRST NODE IN THE LIST TO BE REMOVED
		if (head.data.equals(o))
		{
			head = head.next;
			if (size == 1)
				tail = null;
			size--;
			return;
		}
		
		// MORE THAN ONE NODE IN THE LIST
		else if (size > 1)
		{
			Node traveller = head;
			while (traveller.next != null)
			{
				if (traveller.next.data.equals(o))
				{
					if (traveller.next == tail)
						tail = traveller;
					traveller.next = traveller.next.next;
					size--;
					return;
				}
				traveller = traveller.next;
			}
		}
	}

	/*
	 * removeLastOccurrence - Removes the last 
	 * occurrence of the specified element in this list
	 * (when traversing the list from head to tail).
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public void removeLastOccurrence(Object o)
	{
		// NO NODES IN LIST
		if (head == null)
			return;
		
		// ONE NODE IN LIST
		if (size == 1)
		{
			if (head.data.equals(o))
			{
				head = null;
				tail = null;
				size--;
			}
			return;
		}
		
		// MANY NODES IN LIST
		Node traveller = head;
		Node foundOccurrence = null;

		// FIRST CHECK THE FIRST NODE
		if (head.data.equals(o))
			foundOccurrence = head;
		
		// NOW THE REST
		while (traveller.next != null)
		{
			if (traveller.next.data.equals(o))
				foundOccurrence = traveller;
			traveller = traveller.next;
		}
		
		// NONE FOUND
		if (foundOccurrence == null)
			return;
		// REMOVE HEAD
		else if (foundOccurrence == head)
		{
			head = head.next;
			size--;
			return;
		}
		// CORRECT TAIL
		else if (foundOccurrence.next == tail)
		{
			tail = foundOccurrence;
		}
		
		// AND REMOVE LAST FOUND NODE
		foundOccurrence.next = foundOccurrence.next.next;
		size--;
	}

	/*
	 * set - Replaces the element at the specified 
	 * position in this list with the specified element.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public void set(int index, Object o)
	{
		int count = 0;
		Node traveller = head;
		while (count < index)
		{
			traveller = traveller.next;
			count++;
		}
		traveller.data = o;
	}

	/*
	 * toArray - Returns an array containing all of 
	 * the elements in this list in proper sequence 
	 * (from first to last element).
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public Object[] toArray()
	{
		Object[] array = new Object[size];
		Node traveller = head;
		int count = 0;
		while (traveller != null)
		{
			array[count] = traveller.data;
			traveller = traveller.next;
			count++;
		}
		return array;
	}
	
	/*
	 * listIterator - This method returns a custom
	 * iterator for going through all of the elements
	 * in the linked list.
	 * 
	 * DO NOT CHANGE THIS METHOD
	 */
	public Iterator listIterator()
	{
		return new ListIterator();
	}

	/*
	 * ListIterator - This class is a custom Iterator for 
	 * going through all of the elements in the linked list.
	 * 
	 * YOU MUST DEFINE THE hasNext AND next METHODS
	 * INSIDE THIS CLASS. YOU CAN AND SHOULD ADD
	 * INSTANCE VARIABLES AS YOU LIKE.
	 */
	private class ListIterator implements Iterator
	{
		Node currentNode = head;

		/*
		 * hasNext - For this Iterator object, it
		 * returns a boolean representing whether
		 * there is more data for this iterator
		 * to produce.
		 * 
		 * YOU MUST DEFINE THIS METHOD
		 */
		public boolean hasNext()
		{
			return (currentNode != null);
		}
		
		/*
		 * next - For this Iterator object, it
		 * returns data from a node and advances
		 * the iterator to the next node such that
		 * the iterator may gradually produce all
		 * data from head to tail.
		 * 
		 * YOU MUST DEFINE THIS METHOD
		 */
		public Object next()
		{
			Object dataToReturn = null;
			if (hasNext())
			{
				dataToReturn = currentNode.data;
				currentNode = currentNode.next;
			}
			return dataToReturn;
		}
		
		// DO NOT DEFINE THIS METHOD, WE
		// WILL NOT USE IT, IT'S HERE TO MAKE
		// THE COMPILER HAPPY, SINCE IT'S AN
		// ABSTRACT METHOD IN THE Iterator
		// INTERFACE
		public void remove(){}
	}

	/*
	 * Node - Nodes are the building blocks of
	 * linked lists. The head and the tail are
	 * both nodes, as are everything in between.
	 * 
	 * DO NOT CHANGE THIS CLASS
	 */
	private class Node
	{
		protected Object data;
		protected Node next;
		
		public Node(Object initData, Node initNext)
		{
			data = initData;
			next = initNext;
		}
	}
}