import java.util.Iterator;

/*
 * CSE 214 - Fall 2009
 * HW 2 - GenericDoublyLinkedList
 * Student Name: 
 * 
 * Solutions provided by Richard McKenna
 * 
 * YOU MUST DEFINE EACH OF THE FOLLOWING 3 ITERATORS,
 * WHICH WILL BE USED FOR ITERATING THROUGH YOUR LIST
 * IN DIFFERENT WAYS:
 * 	GenericDoublyLinkedListIterator
 * 	CircularForwardIterator
 * 	CircularReverseIterator
 * 
 * YOU MUST ALSO FILL IN THE CODE FOR THE FOLLOWING TEN
 * METHODS IN THE GenericDoublyLinkedList class:
 *	public void append(E dataToAdd)
 *	public void buildNewListFromArray(E[] arrayOfDataToAdd)
 *	public int indexOf(E[] searchData)
 *	public void moveDownOne(int index)
 *	public void moveUpOne(int index)
 *	public void prepend(E dataToAdd)
 *	public void removeAtIndex(int index)
 *	public String reverseToString()
 *	public GenericDoublyLinkedList<E> subset(int startIndex, int endIndex)
 *	public String toString()
 *  
 * NOTE: 	YOU MAY ADD INSTANCE VARIABLES
 * 			AND HELPER METHODS AS NEEDED
 */

public class GenericDoublyLinkedList <E>
{
	// 	YOU'LL NEED TO CAREFULLY MAINTAIN 
	//	THE head, tail, & size
	public GenericNode<E> head = null;
	public GenericNode<E> tail = null;
	public int size = 0;

	// DEFAULT CONSTRUCTOR
	public GenericDoublyLinkedList() {}

	/*
	 * append - This method adds a new node at the end 
	 * of the list with the dataToAdd argument as its data.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void append(E dataToAdd)
	{
// ADD YOUR CODE HERE
		GenericNode<E> node = new GenericNode<E>(dataToAdd, tail, null);
		if (tail != null)
		{
			tail.next = node;
		}
		else
		{
			head = node;
		}
		tail = node;
		size++;
	}
	
	/*
	 * buildNewListFromArray - This method will take all 
	 * of the contents of the arrayOfDataToAdd array argument 
	 * and make a node for each piece of data in the array. 
	 * These nodes will represent all of the nodes in the list, 
	 * so if any nodes existed already, they will simply be 
	 * excluded from the updated list.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void buildNewListFromArray(E[] arrayOfDataToAdd)
	{
// ADD YOUR CODE HERE
		clear();
		if (arrayOfDataToAdd.length > 0)
		{
			head = new GenericNode<E>(arrayOfDataToAdd[0], null, null);
			tail = head;

			for (int i = 1; i < arrayOfDataToAdd.length; i++)
			{
				tail.next = new GenericNode<E>(arrayOfDataToAdd[i], tail, null);
				tail = tail.next;
			}
			size += arrayOfDataToAdd.length;
		}		
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * clear - This method works properly, it simply removes all
	 * nodes in the list, properly managing the head, tail,
	 * and length. Note that in Java we have automatic
	 * garbage collection. If this were C++, we'd have to
	 * clean up all the data we just cleared out of our linked
	 * list ourselves.
	 */
	public void clear()
	{
		head = null;
		tail = null;
		size= 0;
	}
	
	/*
	 * indexOf - This method should examine the list 
	 * to find a sequence of nodes that contains 
	 * equivalent data, in the equivalent order as 
	 * the searchData argument. So, if the searchData 
	 * array has 5 elements, you must find five 
	 * consecutive nodes in the list with equivalent 
	 * data in the same order. Your method should 
	 * return the index of the first node in that 
	 * sequence (the head node is index 0). If no 
	 * sequence is found, return -1.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public int indexOf(E[] searchData)
	{
// ADD YOUR CODE HERE
		GenericNode<E> traveller = head;
		int index = 0;
		while (		(traveller != null)
				&&	((index + searchData.length) <= size))
		{
			GenericNode<E> traveller2 = traveller;
			int testIndex = 0;
			boolean allSame = true;
			while ((testIndex < searchData.length)
					&& allSame)
			{
				if (!traveller2.data.equals(searchData[testIndex]))
					allSame = false;
				traveller2 = traveller2.next;
				testIndex++;
			}
			if (allSame)
				return index;
			index++;
			traveller = traveller.next;
		}
		return -1;
	}

	/*
	 * moveDownOne - This method should move the 
	 * node at location index down one index in the 
	 * list (toward the tail). This would result in 
	 * it's immediate neighbor moving up one (toward 
	 * to head), of course. No data should be lost 
	 * by this change.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void moveDownOne(int index)
	{
// ADD YOUR CODE HERE
		if ((index < 0) || (index >= (size-1)))
			return;
		else if (size == 2)
		{
			E temp = head.data;
			head.data = tail.data;
			tail.data = temp;
		}
		else if (index == 0)
		{
			// WE MUST UPDATE THE HEAD
			GenericNode<E> node = head;
			head = head.next;
			head.prev = null;
			node.next = head.next;
			node.next.prev = node;
			head.next = node;
			node.prev = head;
		}
		else if (index == (size-2))
		{
			// WE MUST UPDATE THE TAIL
			GenericNode<E> node = tail;
			tail = tail.prev;
			tail.next = null;
			node.prev = tail.prev;
			node.prev.next = node;
			tail.prev = node;
			node.next = tail;
		}
		else
		{
			// WE WON'T NEED TO UPDATE 
			// HEAD OR TAIL
			GenericNode<E> traveller = head;
			int counter = 0;
			while (counter < index)
			{
				traveller = traveller.next;
				counter++;
			}
			GenericNode<E> node = traveller.next;
			node.prev = traveller.prev;
			traveller.prev.next = node;
			traveller.next = node.next;
			node.next.prev = traveller;
			node.next = traveller;
			traveller.prev = node;
		}		
	}

	/*
	 * moveUpOne - This method should do the opposite 
	 * of moveDownOne. It should move the node at 
	 * location index up one index in the list 
	 * (toward the head). Again, this would result 
	 * in that node's neighbor moving down one 
	 * (toward the tail).
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void moveUpOne(int index)
	{
// ADD YOUR CODE HERE	
		if ((index <= 0) || (index >= size))
			return;
		else if (size == 2)
		{
			E temp = head.data;
			head.data = tail.data;
			tail.data = temp;
		}
		else if (index == 1)
		{
			// WE MUST UPDATE THE HEAD
			GenericNode<E> node = head;
			head = head.next;
			head.prev = null;
			node.next = head.next;
			node.next.prev = node;
			head.next = node;
			node.prev = head;
		}
		else if (index == (size-1))
		{
			// WE MUST UPDATE THE TAIL
			GenericNode<E> node = tail;
			tail = tail.prev;
			tail.next = null;
			node.prev = tail.prev;
			node.prev.next = node;
			tail.prev = node;
			node.next = tail;
		}
		else
		{
			// WE WON'T NEED TO UPDATE 
			// HEAD OR TAIL
			GenericNode<E> traveller = head;
			int counter = 0;
			while (counter < index)
			{
				traveller = traveller.next;
				counter++;
			}
			GenericNode<E> node = traveller.prev;
			node.next = traveller.next;
			traveller.next.prev = node;
			traveller.prev = node.prev;
			node.prev.next = traveller;
			node.prev = traveller;
			traveller.next = node;
		}
	}	

	/*
	 * prepend - This method adds a new node at the front 
	 * of the list with the dataToAdd argument as its data.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public void prepend(E dataToAdd)
	{
// ADD YOUR CODE HERE
		GenericNode<E> node = new GenericNode<E>(dataToAdd, null, head);
		if (head != null)
			head.prev = node;
		else
			tail = node;
		head = node;
		size++;
	}

	/*
	 * removeAtIndex - This method should remove 
	 * the node at the index location from the list.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public void removeAtIndex(int index)
	{
// ADD YOUR CODE HERE
		if (	(index < 0) 
			||	(index >= size)
			||	(size == 0))
			return;
		else if (head == tail)
		{
			head = null;
			tail = null;
		}
		else if (index == 0)
		{
			head = head.next;
			head.prev = null;
		}
		else if (index == (size-1))
		{
			tail = tail.prev;
			tail.next = null;
		}
		else
		{
			GenericNode<E> traveller = head;
			int counter = 0;
			while (counter < (index - 1))
			{
				traveller = traveller.next;
				counter++;
			}
			traveller.next.next.prev = traveller;
			traveller.next = traveller.next.next;
		}
		size--;
	}

	/*
	 * reverseToString - This method should return 
	 * a textual representation of the list from tail 
	 * to head. This can be done by combining the 
	 * toString results of all the node data in all 
	 * the nodes from tail to head.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public String reverseToString()
	{
// ADD YOUR CODE HERE
		String s = "";
		GenericNode<E> trav = tail;
		while (trav != null)
		{
			s += trav.data.toString();
			trav = trav.prev;
		}
		return s;
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * size - Accessor method for getting the size 
	 * of the list.
	 */
	public int size() { return size; }

	/*
	 * subset - This method should make and return a 
	 * brand new GenericDoublyLinkedList that contains 
	 * all the data stored in the referenced list from 
	 * startIndex to and including endIndex. Note that 
	 * the original referenced list should not be 
	 * changed in any way. Think of this as an 
	 * operation similar to the String class' 
	 * substring method, except that the second 
	 * integer argument refers to an index included 
	 * in the newly constructed subset.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */	
	public GenericDoublyLinkedList<E> subset(int startIndex, int endIndex)
	{
// ADD YOUR CODE HERE
		GenericDoublyLinkedList<E> subList;
		subList = new GenericDoublyLinkedList<E>();
		if (	(startIndex >= 0) 
			&&	(endIndex < size)
			&&	(startIndex <= endIndex))
		{
			GenericNode<E> traveller = head;
			int counter = 0;
			while(counter < startIndex)
			{
				traveller = traveller.next;
				counter++;
			}
			while (counter <= endIndex)
			{
				subList.append(traveller.data);
				traveller = traveller.next;
				counter++;
			}
		}
		return subList;
	}
	
	/*
	 * toString - This method should produce a textual 
	 * representation of the list by concatenating the 
	 * textual representation of each node, head to tail, 
	 * and then returning this full String.
	 * 
	 * YOU MUST DEFINE THIS METHOD
	 */
	public String toString()
	{
// ADD YOUR CODE HERE
		String s = "";
		GenericNode<E> trav = head;
		while (trav != null)
		{
			s += trav.data.toString();
			trav = trav.next;
		}
		return s;
	}

	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * listIterator - This method provides an Iterator for
	 * iterating once through the list head to tail. 
	 * You should not change this method, but you must 
	 * define the GenericDoublyLinkedListIterator class.
	 */
	public Iterator<E> listIterator()
	{
		return new GenericDoublyLinkedListIterator();
	}
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * circularForwardIterator - This method provides
	 * an Iterator for iterating through the list, head
	 * to tail, repeatedly. After reaching the tail, it
	 * should then go to the head, thus we call it
	 * circular. You should not change this method, 
	 * but you must define the CircularForwardIterator
	 * class.
	 */	
	public Iterator<E> circularForwardIterator()
	{
		return new CircularForwardIterator();
	}
	
	/*
	 * DO NOT CHANGE THIS METHOD
	 * 
	 * circularReverseIterator - This method provides
	 * an Iterator for iterating through the list, tail
	 * to head, repeatedly. After reaching the head, it
	 * should then go to the tail, thus we call it
	 * circular. You should not change this method, 
	 * but you must define the CircularReverseIterator
	 * class.
	 */	
	public Iterator<E> circularReverseIterator()
	{
		return new CircularReverseIterator();
	}

	/*
	 * YOU MUST DEFINE THIS CLASS
	 * 
	 * This works like a disposable, front to back
	 * list iterator.
	 */
	class GenericDoublyLinkedListIterator implements Iterator<E>
	{
		// YOU MAY ADD INSTANCE VARIABLES AS YOU SEE FIT

		// THIS KEEPS TRACK OF WHERE OUR ITERATOR IS
		// SO WE CAN PRODUCE THE CORRECT PIECE OF DATA NEXT
		private GenericNode<E> traveller = (GenericNode<E>) head;

		/*
		 * YOU MUST DEFINE THIS METHOD
		 */
		public boolean hasNext()
		{
			if (traveller == null)
				return false;
			else
				return true;
		}
		
		/*
		 * YOU MUST DEFINE THIS METHOD
		 */
		public E next()
		{
			if (traveller == null)
				return null;

			E dataToReturn = traveller.data;
			traveller = traveller.next;
			return dataToReturn;
		}

		/*
		 * DO NOT CHANGE, WE WON'T USE IT
		 */
		public void remove() {}
	}

	/*
	 * YOU MUST DEFINE THIS CLASS
	 * 
	 * This works like a circular, front to back
	 * list iterator. It will keep iterating as long
	 * as someone keeps calling next. Note that it
	 * would not produce elements if the list were
	 * empty.
	 */
	class CircularForwardIterator implements Iterator<E>
	{
		// YOU MAY ADD INSTANCE VARIABLES AS YOU SEE FIT

		// THIS KEEPS TRACK OF WHERE OUR ITERATOR IS
		// SO WE CAN PRODUCE THE CORRECT PIECE OF DATA NEXT
		private GenericNode<E> traveller = (GenericNode<E>) head;

		/*
		 * YOU MUST DEFINE THIS METHOD
		 */
		public boolean hasNext()
		{
			if (size == 0)
				return false;
			else
				return true;
		}
		
		/*
		 * YOU MUST DEFINE THIS METHOD
		 */
		public E next()
		{
			if (size == 0)
				return null;

			E dataToReturn = traveller.data;
			if (traveller == tail)
				traveller = (GenericNode<E>) head;
			else
				traveller = traveller.next;
			return dataToReturn;
		}

		/*
		 * DO NOT CHANGE, WE WON'T USE IT
		 */
		public void remove() {}
	}

	/*
	 * YOU MUST DEFINE THIS CLASS
	 * 
	 * This works like a circular, back to front
	 * list iterator. It will keep iterating as long
	 * as someone keeps calling next. Note that it
	 * would not produce elements if the list were
	 * empty.
	 */
	class CircularReverseIterator implements Iterator<E>
	{
		// YOU MAY ADD INSTANCE VARIABLES AS YOU SEE FIT

		// THIS KEEPS TRACK OF WHERE OUR ITERATOR IS
		// SO WE CAN PRODUCE THE CORRECT PIECE OF DATA NEXT
		private GenericNode<E> traveller = (GenericNode<E>) tail;

		/*
		 * YOU MUST DEFINE THIS METHOD
		 */
		public boolean hasNext()
		{
			if (size == 0)
				return false;
			else
				return true;
		}
		
		/*
		 * YOU MUST DEFINE THIS METHOD
		 */
		public E next()
		{
			if (size == 0)
				return null;

			E dataToReturn = traveller.data;
			if (traveller == head)
				traveller = (GenericNode<E>) tail;
			else
				traveller = traveller.prev;
			return dataToReturn;
		}

		/*
		 * DO NOT CHANGE, WE WON'T USE IT
		 */
		public void remove() {}
	}
	
	/*
	 * DO NOT CHANGE THIS CLASS
	 * 
	 * Node for a generic doubly linked list. It can store any
	 * type of object. In addition, the <E> denotes that we
	 * can have the compiler constrain which types of objects
	 * get put into and taken out of instances of this class.
	 */
	class GenericNode<E>
	{
		E data;
		protected GenericNode<E> prev;
		protected GenericNode<E> next;
		
		public GenericNode(E dataToAdd, GenericNode<E> initPrev, GenericNode<E> initNext)
		{
			data = dataToAdd;
			prev = initPrev;
			next = initNext;
		}
	}	
}