/* List.java */

/** The List class implements a linked list abstraction.  Lists
 * are mutable data structures, which can grow at either end.
 * @author Kathy Yelick                                       */

public class List {
  /** Construct an empty list */
  public List() {
    size = 0;
    head = null;
  }

  /** Returns true if this list is empty, 
   *   false otherwise.                                 
   *   @return true if the list is empty, false otherwise. */
  public boolean isEmpty() {
    return (size == 0);
  }
    
  /** Returns the length of this list. 
   *  @return the length of the list.                     */
  public int length() {
    return size;
  }

  /** Inserts obj into this list at the beginning.
   *  @param obj the object to be inserted.  */
  public void insertFront (Object obj) {
    ListNode newNode = new ListNode(obj, head);
    head = newNode;
    size += 1;
  }
        
  /** Inserts obj into this list at the end.
   *  @param obj the object to be inserted.  */
  public void insertEnd (Object obj) {
    if (head == null) {
      head = new ListNode(obj);
    } else {
      ListNode node = head.ptrTo(length());
      node.next = new ListNode(obj);
    }
    size += 1;
  }
    
  /** Inserts obj into this list at position n.
   *  @param n is the position as which obj should be inserted.
   *       If n is less than 1 or greater than length()+1, an 
   *       error message will be printed and the list left unchanged.
   *  @param obj the object to be inserted.
   */
  public void insertAt (Object obj, int n) {
     // unimplemented
  }
    
  /** Returns the element at the specified position.
   *    If position < 1 or position > length(), 
   *    then null is returned.  Otherwise, the item at       
   *    position is returned.  The list is unchanged in either
   *    case.                                                           
   *  @param position the desired position in the list (between
   *     1 and length()).  
   *  @return the Object at the given position in the List. */
  public Object nth(int position) {
    ListNode node = head.ptrTo(position);
    if (node == null) {
      return null;
    } else {
      return node.item;
    }
  } 

  /** Returns a String representation of the list. 
   *  @return a String representation of the list. */
  public String toString() {
    int i;
    Object obj;
    String result = "[  ";

    ListNode cur = head;

    while (cur != null) {
      obj = cur.item;
      result = result + obj.toString() + "  ";
      cur = cur.next;
    }
    result = result + "]";
    return result;
  }

  /** Runs test cases on the the List class. 
       Prints summary information on basic operations and halts 
       with an error (and a stack trace) if any of the tests fail. */
  public static void main (String [] argv) {
    // put code for Part I here.
    testEmpty();
    testAfterInsertFront();
    testAfterInsertEnd();
    // testAfterInsertAt();
  }
    
  private int size;
  ListNode head;

  /** Tests toString(), isEmpty(), length(), insertFront(), and
   *  insertEnd() on an empty list.   Prints summary information 
   *   of the tests and halts the program if errors are detected. */
  private static void testEmpty() {
    List lst1 = new List();
    List lst2 = new List();
    System.out.println("Here is a list after construction: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  ]"),
		      "toString on newly constructed list failed");

    System.out.println("isEmpty() should be true. It is: " +
		       lst1.isEmpty());
    TestHelper.verify(lst1.isEmpty() == true,
		      "isEmpty() on newly constructed list failed");    

    System.out.println("length() should be 0. It is: " +
		       lst1.length());
    TestHelper.verify(lst1.length() == 0, 
		      "length on newly constructed list failed");    
    lst1.insertFront(new Integer(3));
    System.out.println("Here is a list after insertFront(3) to an empty list: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  3  ]"),
		      "InsertFront on empty list failed");
    lst2.insertEnd(new Integer(5));
    System.out.println("Here is a list after insertEnd(5) on an empty list: "
		       + lst2.toString());
    TestHelper.verify(lst2.toString().equals("[  5  ]"),
		      "insertEnd on empty list failed");
  }

  /** Tests toString(), isEmpty(), length(), insertFront(), and
   *   insertEnd() after insertFront. Prints summary information 
   *   of the tests and halts the program if errors are detected. */
  private static void testAfterInsertFront() {
    List lst1 = new List();
    lst1.insertFront(new Integer(3));
    lst1.insertFront(new Integer(2));
    lst1.insertFront(new Integer(1));
    System.out.println("Here is a list after inserting 3, 2, 1: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  1  2  3  ]"),
		      "InsertFronts on non-empty list failed");
    System.out.println("isEmpty() should be false. It is: " +
		       lst1.isEmpty());
    TestHelper.verify(lst1.isEmpty() == false,
		      "isEmpty() after insertFront failed");    
    System.out.println("length() should be 3. It is: " +
		       lst1.length());
    TestHelper.verify(lst1.length() == 3, 
		      "length() after insertFront failed");
    lst1.insertEnd(new Integer(4));
    System.out.println("Here is the same list after insertEnd(4): "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  1  2  3  4  ]"),
		      "insertEnd on non-empty list failed");
  }
    
  /** Tests toString(), isEmpty(), length(), insertFront(), 
   *   insertEnd() and insertAt() after insertAt(). Prints summary 
   *   information of the tests and halts the program if errors are 
   *   detected. 
   */
  private static void testAfterInsertAt() {
    List lst1 = new List();
    lst1.insertAt(new Integer(2), 1);
    System.out.println("Here is a list after inserting 2 at 1: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  2  ]"),
		      "InsertAt on an empty list failed");

    lst1.insertAt(new Integer(1), 1);
    System.out.println("Here is the same list after inserting 1 at 1: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  1  2  ]"),
		      "InsertAt on an empty list failed");

    lst1.insertAt(new Integer(3), 3);
    System.out.println("Here is the same list after inserting 3 at 3: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  1  2  3  ]"),
		      "InsertAt on an empty list failed");
    TestHelper.verify(lst1.isEmpty() == false,
		      "isEmpty() after insertAt failed");    
    System.out.println("length() should be 3. It is: " +
		       lst1.length());
    TestHelper.verify(lst1.length() == 3, 
		      "length() after insertAt failed");

    lst1.insertEnd(new Integer(4));
    System.out.println("Here is the same list after insertEnd of 4: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  1  2  3  4  ]"),
		      "insertEnd after insertAt failed");

    lst1.insertFront(new Integer(-1));
    System.out.println("Here is the same list after insertFront of -1: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  -1  1  2  3  4  ]"),
		      "insertFront after insertAt failed");

    lst1.insertAt(new Integer(0), 2);
    System.out.println("Here is the same list after inserting 0 at 2: "
		       + lst1.toString());
    lst1.insertAt(new Integer(5), 7);
    System.out.println("Here is the same list after inserting 5 at 7: "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  -1  0  1  2  3  4  5  ]"),
		      "insertAt after insertFront/End failed");
  }
    
  /** Tests toString(), isEmpty(), length(), insertFront(), and
   * insertEnd() after insertEnd().  Prints summary information 
   * of the tests and halts the program if errors are detected. */
  private static void testAfterInsertEnd() {
    List lst1 = new List();
    lst1.insertEnd(new Integer(6));
    lst1.insertEnd(new Integer(7));
    System.out.println("Here is a list after insertEnd 6, 7: "
		       + lst1.toString());
    System.out.println("isEmpty() should be false. It is: " +
		       lst1.isEmpty());
    TestHelper.verify(lst1.isEmpty() == false,
		      "isEmpty() after insertEnd failed");    
    System.out.println("length() should be 2. It is: " +
		       lst1.length());
    TestHelper.verify(lst1.length() == 2, 
		      "length() after insertEndfailed");
    lst1.insertFront(new Integer(5));
    System.out.println("Here is the same list after insertFront(5): "
		       + lst1.toString());
    TestHelper.verify(lst1.toString().equals("[  5  6  7  ]"),
		      "insertFront after insertEnd failed");
  }
}