// ****************************************************
// 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) 
	{
		//public void add(int index, Object item)
		Node curr = L.head;
		int count = numItems + 1;
		while(curr != null)
		{
			add(count, curr.getItem());
			curr = curr.getNext();
			count++;
		}
	}  // 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);
        			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.setNext(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();
      			} 
      			else 
			{
        			Node prev = find(index-1);
        			// delete the node after the node that prev
        			// references, save reference to node
        			Node curr = prev.getNext(); 
        			prev.setNext(curr.getNext());
      			} // 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)
	{
		int count = 1;
		Node curr = head;
		while(curr != null)
		{
			if(curr.getItem().equals(item))
			{
				System.out.println("Hello I am going to Delete> " + item);
				System.out.println(count +">= 1 && " + count +"<= " + numItems);
				if(count >= 1 && count <= numItems)
				{
					//System.out.println(count +">= 1 && " + count +"<= " + numItems);
					if(count == 1)
					{
						//System.out.println("count == 1");
						head = head.getNext();
					}
					else
					{
						//System.out.println("ELSE");
						Node prev = find(count - 1);
						curr = prev.getNext();
						//System.out.println("Prev> " + prev.getItem());
						//System.out.println("Curr> " + curr.getItem());
						prev.setNext(curr.getNext());
					}
				}
				numItems--;
			}
			curr = curr.getNext();
			count++;
		}
	}

  	public void append(Object item)
	{
		Node prev = find(numItems -1);
		Node newNode = new Node(item,prev.getNext());
		prev.setNext(newNode);
		numItems++;
	}

	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