// ****************************************************
// 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 myOnlyNode) {
    numItems = 1;
    head = new Node(myOnlyNode);
  }

  public ListReferenceBased(ListReferenceBased copyMe) {
    numItems = copyMe.numItems;
    head = copyMe.head;
  }

  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 
  // 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);
        // delete the node after the node that prev
        // references, save reference to node
        Node prev = curr.getPrev(); 
        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 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 findMe) {
    Node p = head;
    for (int i = 1; i <= numItems; i++, p=p.getNext()) {
      if (p.getItem().equals(findMe)) return i;
      //p = p.getNext();
    }
    return -1;
  }

  public void append(Object appendMePlease) {
    add(numItems+1, appendMePlease);
  }

  public void display() {
    Node p = head;
    for (int i = 1; i <= numItems; i++, p=p.getNext()) {
      System.out.println(p.getItem().toString());
    }
  }

  public void delete(Object deleteMe) {
    Node p = head;
    for (int i = 1; i <= numItems; i++, p=p.getNext()) {
      if (p.getItem().equals(deleteMe)) remove(i);
    }
  }
} // end ListReferenceBased