// ****************************************************
// Reference-based implementation of ADT list.
// ****************************************************
public class ListReferenceBased implements ListInterface 
{
	// reference to linked list of items
	private Node head; 
	private int numItems; // number of items in list

	public ListReferenceBased() 
	{
		numItems = 0;
		head = null;
	}  // end default constructor

	public ListReferenceBased(Object newItem) 
	{
		Node newNode = new Node(newItem);
		head = newNode;
		numItems = 1;
	}  // end constructor

	public ListReferenceBased(ListReferenceBased L) 
	{
		head = L.head;
		numItems = L.numItems;
	}  // end copy constructor

	public boolean isEmpty() 
	{
		return numItems == 0;
	}  // end isEmpty

	public int size() 
	{
		return numItems;
	}  // end size

	private Node find(int index) 
	{
		// --------------------------------------------------
		// Locates a specified node in a linked list.
		// Precondition: index is the number of the desired
		// node. Assumes that 1 <= index <= numItems+1 
		// Postcondition: Returns a reference to the desired 
		// node.
		// --------------------------------------------------
		Node curr = head;
		for (int skip = 1; skip < index; skip++) 
		{
				curr = curr.getNext();
		} // end for
		return curr;
	} // end find

	public Object get(int index) throws ListIndexOutOfBoundsException 
	{
    		if (index >= 1 && index <= numItems) 
		{
      			// get reference to node, then data in node
      			Node curr = find(index);
      			Object dataItem = curr.getItem();
      			return dataItem;
    		} 
    		else 
		{
      			throw new ListIndexOutOfBoundsException(
                     	"List index out of bounds exception on get");
    		} // end if
  	} // end get


	public void add(int index, Object item) throws ListIndexOutOfBoundsException 
	{
    		if (index >= 1 && index <= numItems+1) 
		{
      			if (index == 1) 
			{
        			// insert the new node containing item at
        			// beginning of list
        			Node newNode = new Node(item, head, null);
        			head = newNode;
      			} 
      			else 
			{
        			Node prev = find(index-1);
        			// insert the new node containing item after 
        			// the node that prev references
        			Node newNode = new Node(item, prev.getNext(), prev);
        			prev.setNext(newNode);
				if(newNode.getNext() != null)
				{
					newNode.getNext().setPrev(newNode);
				}
      			} // end if
      			numItems++;
    		} 
    		else 
		{
      			throw new ListIndexOutOfBoundsException(
                    	"List index out of bounds exception on add");
    		} // end if
  	}  // end add

	public void remove(int index) throws ListIndexOutOfBoundsException 
	{
    		if (index >= 1 && index <= numItems) 
		{
      			if (index == 1) 
			{
        			// delete the first node from the list
        			head = head.getNext();
				head.setPrev(null);
      			} 
      			else 
			{
				Node curr = find(index);
        			Node prev = curr.getPrev();
        			// delete the node after the node that prev
        			// references, save reference to node
        			prev.setNext(curr.getNext());
				if(prev.getNext() != null)
				{
					prev.getNext().setPrev(prev);
				}
      			} // end if
      			numItems--;
    		} // end if
    		else 
		{
      			throw new ListIndexOutOfBoundsException(
                   	"List index out of bounds exception on remove");
    		} // end if
  	}   // end remove

  	public void delete(Object item)
	{
		Node findit = head;
		int i = 1;
		while(i <= numItems)
		{
			if(findit.getItem().equals(item))
			{
				remove(i);
			}
			findit = findit.getNext();
			i++;
		}
			
	}

  	public void append(Object item)
	{
		int index = numItems + 1;
		add(index, item);
	}

	public void removeAll() 
	{
		// setting head to null causes list to be
		// unreachable and thus marked for garbage 
		// collection
		head = null;
		numItems = 0;
	} // end removeAll

	public int contains(Object item)
	{
		int count = 1;
		int found = 0;
		Node curr = head;
		while(curr != null)
		{
			if(curr.getItem().equals(item))
			{
				found = count;
				return count;
			}
			curr = curr.getNext();
		}
		return found;
	}

	public void display()
	{
		Node curr = head;
		while(curr != null)
		{
			System.out.println("Item> " + curr.getItem());
			curr = curr.getNext();
		}
	}
} // end ListReferenceBased