package galapagos4.container;

/**
 * List implementation
 * 
 * Implemented as a double chained list using distinct head and tail elements.
 * 
 * @author Karl Koder
 *
 */

public class ListImplementation< Element > implements List< Element > {
	
	private class Node {
		Element element;
		Node next;
		Node previous;
		
		public Node( Element element )
		{
			this.element = element;
			this.next = null;
			this.previous = null;
		}
	}
	
	public ListImplementation()
	{
		size = 0;
		header = new Node( null );
		tail = new Node( null );
		
		header.next = tail;
		header.previous = tail;
		tail.next = header;
		tail.previous = header;
	}
	
	/**
	 * Command Add an element to the end of the list
	 * @param element the element to add
	 */
	public void add( Element element )
	{
		Node newNode = new Node( element );
		newNode.previous = tail.previous;
		tail.previous.next = newNode;
		newNode.next = tail;
		tail.previous = newNode;
		++size;
	}
	
	/**
	 * Command: Remove the first occurence of the element given
	 * @param element The element to remove
	 */
	public void remove( Element element )
	{
		Node n = header.next;

		if( n.next == tail && element == n.element )
		{
			// only one element left. Special case.
			n.previous = n.next;
			tail.previous = n.previous;
		}
		while( n != tail )
		{
			if( element.equals( n.element ) )
			{
				n.previous.next = n.next;
				n.next.previous = n.previous;
				--size;
				break;
			}
			else
			{
				n = n.next;
			}
		}
	}
	
	private Node tail;
	
	/**
	 * Remove the element at the given position
	 * @param index the index of the element to remove
	 * @require index >= 0 ^^ index < length()
	 * @ensure new.length = old.length - 1
	 */
	public void remove( int index )
	{
		Node n = header.next;
		while( index > 0 )
		{
			n = n.next;
			index--;
		}
		n.previous.next = n.next;
		n.next.previous = n.previous;
		size--;
	}
	
	private int size;
	
	/**
	 * Query: what is the length of the list
	 * @return the length of the list.
	 */
	public int length()
	{
		return size;
	}
	
	/**
	 * Query: Get element at specified position
	 * @param index The position of the element to get
	 * @return the element at given position
	 * @require index >= 0 && index < length()
	 */
	public Element get( int index )
	{
		Node n = header.next;
		while( index > 0 )
		{
			n = n.next;
			index--;
		}
		
		return n.element;
	}
	
	/**
	 * Query: Is the list empty
	 * @return return true if the list is empty
	 */
	public boolean isEmpty()
	{
		return header.next == tail;
	}
	
	private Node header;
	
	/**
	 * Query: Does the list contain the given element
	 * @param element The element to find
	 * @return True if the list contains the element.
	 */
	public boolean contains( Element element )
	{
		boolean result = false;
		
		Node n = header.next;
		while( n != tail )
		{
			if( n.element.equals( element ) )
			{
				result = result || true;
			}
			n = n.next;
		}
		
		return result;
	}
	
	/**
	 * Query: What is the first index of the supplied element
	 * @param element The element to look for
	 * @return The index of the element if found else -1.
	 */
	public int indexOf( Element element )
	{
		int r = -1;
		int count = 0;
		
		Node n = header.next;
		while( n != tail )
		{
			if( n.element.equals( element ) )
			{
				r = count;
				break;
			}
			n = n.next;
			++count;
		}

		return r;
	}
}