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 bi-directional traversal
  // Standard implementation uses double linking
  
  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

  public String toString() {
    BiIteratorI i = new BiIterator(this);
    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;
    length++;
  }

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

  public void remRear() { 
    if (isEmpty())    
      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(this);
  }

  public BiIteratorI newBiIterator() {
    return new BiIterator(this);
  }
}

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;
  }
} 

class BiIterator implements BiIteratorI {

  BiList listThis;
  Node current;

  BiIterator(BiList l) {
    listThis = l;                  // associated List instance
    current = listThis.head.succ;  // current is first item (if one exists)
  }

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

  public void last() { 
    current = listThis.head.pred;  // current is last item (if one exists)
  }

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

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

  }

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

  public boolean atEnd() { return current == listThis.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;
    listThis.length++;
      
  }	

  public void remove() {

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

    if (current == listThis.head) throw 
      new IteratorException(
        "BiIterator.remove() applied at end of BiList " + listThis);
    Node cPred = current.pred;
    Node cSucc = current.succ;
    cPred.succ = cSucc;
    cSucc.pred = cPred;
    current = cSucc;  
    listThis.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 iterator to front; current item is: " + it.currentItem());
    it.remove();
    System.out.println("Removed current element. current item is: " + it.currentItem());
    it.next();
    it.remove();
    System.out.println("Advanced current pointer and removed element; current item is: " + it.currentItem());
    it.remove();
    System.out.println("Removed current element from: " + l + "; current item is: " + it.currentItem());
    l.remRear();
    System.out.println("Removed element from rear. l is " + l);    
    it.last();
    it.remove();
    System.out.println("Moved to last element of " + l + " removed it");
  }
}