/* DList2.java */

/**
 *  A DList2 is a mutable doubly-linked list.  Its implementation is
 *  circularly-linked and employs a sentinel (dummy) node at the head
 *  of the list.
 */

public class DList2 {

  /**
   *  head references the sentinel node.
   *
   *  DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
   */

  private DListNode2 head;

  /* DList2 invariants:
   *  1)  head != null.
   *  2)  For any DListNode x in a DList, x.next != null and x.prev != null.
   *  3)  For any DListNode x in a DList, if x.next == y, then y.prev == x.
   *  4)  For any DListNode x in a DList, if x.prev == y, then y.next == x.
   */

  /**
   *  DList2() constructor for an empty DList2.
   */
  public DList2() {
    head = new DListNode2();
    head.next = head;
    head.prev = head;
  }

  /**
   *  DList2() constructor for a one-node DList2.
   */
  public DList2(int a) {
    head = new DListNode2();
    head.next = new DListNode2();
    head.next.item = a;
    head.prev = head.next;
    head.next.prev = head;
    head.prev.next = head;
  }

  /**
   *  DList2() constructor for a two-node DList2.
   */
  public DList2(int a, int b) {
    head = new DListNode2();
    head.next = new DListNode2();
    head.next.item = a;
    head.prev = new DListNode2();
    head.prev.item = b;
    head.next.prev = head;
    head.next.next = head.prev;
    head.prev.next = head;
    head.prev.prev = head.next;
  }

  /**
   *  removeFirst() removes the first node from DList2.  If the list is empty,
   *  do nothing.
   */
  public void removeFirst() {
    // Your solution here.
  }

  /**
   *  toString() returns a String representation of this DList.
   *
   *  DO NOT CHANGE THIS METHOD.
   *
   *  @return a String representation of this DList.
   */
  public String toString() {
    String result = "[  ";
    DListNode2 current = head.next;
    while (current != head) {
      result = result + current.item + "  ";
      current = current.next;
    }
    return result + "]";
  }

  public static void main(String[] args) {
    // DO NOT CHANGE THE FOLLOWING CODE.

    DList2 l = new DList2(1, 2);
    System.out.println("List with 1 and 2 is " + l);
    l.removeFirst();
    System.out.println("List with 2 is " + l);
    if (l.head.next.prev != l.head) {
      System.out.println("head.next.prev is wrong.");
    }
    l.removeFirst();
    System.out.println("List with nothing is " + l);
    if (l.head.prev != l.head) {
      System.out.println("head.prev reference is wrong.");
    }
    if (l.head.next != l.head) {
      System.out.println("head.next reference is wrong.");
    }
    l.removeFirst();
    System.out.println("List with nothing is " + l);
    if (l.head.prev != l.head) {
      System.out.println("head.prev reference is wrong again.");
    }
    if (l.head.next != l.head) {
      System.out.println("head.next reference is wrong again.");
    }
  }

}