interface ListI {

  // Basic primitive operations on mutable lists
  // Standard implementation uses single linking

  ListI newList();
  int length();
  void insertFront(Object o);
  void insertRear(Object o);
  void remFront();
  boolean isEmpty();

  IteratorI newIterator();
}

interface BiListI extends ListI {

  // Extra operation required for bidirectional traversal
  // Standard implementation uses double linking
  
  BiListI newBiList();
  void remRear();
  BiIteratorI newBiIterator(); 
  // typically identical to newIterator() but with more precise type
}

interface IteratorI {

  void first();
  void next();
  boolean atEnd();
  Object currentItem();

  /* Destructive operations */

  void insert(Object o);  
  // inserts before current item; never faults, even atEnd()
  void remove(); 
}

interface BiIteratorI extends IteratorI {

  // extended iterator for BiListI

  void last();
  void prev();
}

class ListException extends RuntimeException {
  ListException(String s) { super(s); }
}

class IteratorException extends RuntimeException {
  IteratorException(String s) { super(s); }
}

class BiList implements BiListI {

  Node head = new Node();  // allocate circularly linked header node
  int length = 0;

  // relying on default constructor to create empty lists 

  public String toString() {
    BiIteratorI i = new BiIterator();
    String result = "(";

    for (i.first() ; ! i.atEnd(); i.next())  
      result = result + " " + i.currentItem();
    return result + " )";
  }

  public ListI newList() { return new BiList(); }

  public BiListI newBiList() { return new BiList(); }

  public int length() { return length; }

  public void insertFront(Object o) { 
    Node oldSucc = head.succ;
    Node newNode = new Node(o,head,oldSucc);  // allocate new Node
    // insert new Node
    head.succ = newNode;
    oldSucc.pred = newNode;
    length++;
  }
    
  public void insertRear(Object o)  { 
    Node oldPred = head.pred;
    Node newNode = new Node(o,oldPred,head);  // allocate new Node
    // insert new Node
    head.pred = newNode;
    oldPred.succ = newNode;
  }

  public void remFront() { 
    if (head == head.succ)    
      throw new ListException("remFront() applied to EmptyList");
    else {
      Node newSucc = head.succ.succ;
      head.succ = newSucc;
      newSucc.pred = head;
      length--;    
    }
  }

  public void remRear() { 
    if (head == head.succ)    
      throw new ListException("remRear() applied to EmptyList");
    else {
      Node newPred = head.pred.pred;
      head.pred = newPred;
      newPred.succ = head;
      length--;    
    }
  }

  public boolean isEmpty() { return head == head.succ; }

  public IteratorI newIterator() {
    // weaker typing for BiIterator when viewed as Iterator
    return new BiIterator();
  }

  public BiIteratorI newBiIterator() {
    return new BiIterator();
  }
  
  static class Node {
    Object item;
    Node pred,succ;

    Node(Object i, Node p, Node s) {
      item = i;
      pred = p;
      succ = s;
    }

    Node() {  // allocate header
      item = null;
      pred = this;
      succ = this;
    }
  } 

  private class BiIterator implements BiIteratorI {

    Node current;

    BiIterator() {
      current = head.succ;  // current is first item (if one exists)
    }

    public void first() { 
      current = head.succ;  // current is first item (if one exists)
      // if (current == head) 
      // throw new IteratorException("No first element in BiList");
    }

    public void last() { 
      current = head.pred;  // current is last item (if one exists)
      // if (current == head) 
      // throw new IteratorException("No last item in BiList");
    }

    public void next() {
      // wraps around end
      current = current.succ;
    }

    public void prev() {
      // wraps around end
      current = current.pred;
    }

    public Object currentItem() { 
      if (current == head) throw
        new IteratorException("No current item in " + BiList.this);
      return current.item; 
    }

    public boolean atEnd() { return current == head; }


    public void insert(Object o) {

      // pre: true
      // post: Node containing o is inserted before current item, 
      //       current is unchanged

      Node oldPred = current.pred;
      Node newNode = new Node(o, oldPred, current);  // allocate new node
      current.pred = newNode;                        // insert it
      oldPred.succ = newNode;
      length++;
    }	

    public void remove() {

      // pre:  current is valid
      // post: current becomes current.succ

      if (current == head) throw 
        new IteratorException(
          "BiIterator.remove() applied at end of BiList " + 
	    BiList.this);
      Node cPred = current.pred;
      Node cSucc = current.succ;
      cPred.succ = cSucc;
      cSucc.pred = cPred;
      current = cSucc;  
      length--;
    }	
  }
}

class Test {

  static int max(BiList l) {
    if (l.isEmpty()) 
      throw new IllegalArgumentException("max applied to empty List");
    BiIteratorI i = l.newBiIterator();
    i.last();
    int max = ((Integer) i.currentItem()).intValue();
    for (i.prev(); !i.atEnd(); i.prev()) {
      int current = ((Integer) i.currentItem()).intValue();
      if (max < current) max = current;
    }
    return max;
  }

  public static void main(String[] args) {

    BiList l = new BiList();
    BiIteratorI it = l.newBiIterator();
    for (int i=0; i < 10 ; i++) 
      it.insert(new Integer(i));
    System.out.println("The maximum of " + l + " is: " + max(l));
    l.remFront();
    System.out.println("Removed item from front. l is " + l);    
    it.insert(new Integer(10));
    System.out.println("Inserted 10 at end. The list " + l + " has length " 
+ l.length());
    it.first();
    System.out.println("Moved cursor to first item; current item is: " + it.currentItem());
    it.remove();
    System.out.println("Removed current item; current item is: " + it.currentItem());
    it.next();
    it.remove();
    System.out.println("Advanced cursor and removed item; current item is: " + it.currentItem());
    it.remove();
    System.out.println("Removed current item from: " + l + "; current item is: " + it.currentItem());
    l.remRear();
    System.out.println("Removed item from rear. l is " + l);    
    it.last();
    it.remove();
    System.out.println("Moved cursor to last item of " + l + " removed it");
  }
}