// (Singly-Linked) Imperative Lists

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 IteratorI {

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

  /* Destructive operations */

  void insert(Object o);  
  // inserts before current item; when atEnd(), does insertRear(o)
  void remove(); 
}

// Notice that the ListI interface specifies a method called newIterator
// that creates a new iterator for a list. In the following implementation
// of the ListI interface, the iterator class is hidden inside the List
// class implementing the ListI interface.  Hence, the only way to construct
// new iterators is to use the newIterator method.  Such a method is
// called a ``factory'' method.

// We define a pair of exceptions, one for Lists and one for Iterators,
// which are subclasses of RuntimeException. (Recall that these
// exceptions are unchecked; this is a hint that they will be used
// to signal improper uses of the classes, or programming mistakes.

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

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

class List implements ListI {

  Node head = new Node();  // allocate header node object
  Node last = head;
  private int length = 0;

  // relying on default constructor

  public String toString() {
    IteratorI i = new Iterator();
    String result = "(";

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

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

  public int length() { return length; }

  public void insertFront(Object o) { 
    Node oldSucc = head.succ;
    Node newNode = new Node(o,oldSucc);  
    head.succ = newNode;
    if (last == head) last = newNode;
    length++;
  }
    
  public void insertRear(Object o)  { 
    Node newNode = new Node(o,null);  
    last.succ = newNode;              
    last = newNode;
    length++;
  }

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

  public boolean isEmpty() { return head == last; }

  public IteratorI newIterator() {
    return new Iterator();
  }

  private static class Node {
    Object item;
    Node succ;

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

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

  private class Iterator implements IteratorI {

    Node pred;  // current item is pred.succ

    Iterator() {
      pred = head;  
    }

    public void first() { 
      // reposition cursor to refer to first item (if one exists)
      pred = head; 
    }

    public void next() {

      if (atEnd()) 
	throw new 
          IteratorException("No next element in Iteration through List");
      pred = pred.succ;
    }

    public Object currentItem() { 
      if (atEnd()) 
        throw new IteratorException("No current element in " + List.this);
      return pred.succ.item; 
    }

    public boolean atEnd() { return pred == last; }


    public void insert(Object o) {

      // pre: current is either a list element or an imaginary
      //      element just beyond the last element
      // post: Node containing o is inserted before current item, 
      //       current is unchanged (pred is changed, last may be)

      Node oldSucc = pred.succ;
      Node newNode = new Node(o, oldSucc);   // allocate new node
      pred.succ = newNode;                   // insert it
      pred = newNode;                        // update current
      if (oldSucc == null) last = newNode;   // update last if inserted at end
      length++;
    }	

    public void remove() {

      // pre: pred != last (current is valid)
      // post: pred.succ becomes pred.succ.succ

      if (atEnd()) // no element available to remove!
        throw new IteratorException(
          "Iterator.remove() applied at end of List " + List.this);
      Node deadNode = pred.succ;
      pred.succ = deadNode.succ;
      if (last == deadNode) last = pred;
      length--;
    }	
  }
}


//
// Finally, we have a test class with a main method; we could
// have simply put a main method in the List class too.
//


class Test {

  static int max(List l) {
    if (l.isEmpty()) 
      throw new IllegalArgumentException("max applied to empty List");
    IteratorI i = l.newIterator();
    i.first();
    int max = ((Integer) i.currentItem()).intValue();
    for (i.next(); !i.atEnd(); i.next()) {
      int current = ((Integer) i.currentItem()).intValue();
      if (max < current) max = current;
    }
    return max;
  }

  public static void main(String[] args) {

    List l = new List();
    IteratorI it = l.newIterator();
    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());    
    System.out.println("The maximum of " + l + " is: " + max(l));
    it.first();
    System.out.println("Moved cursor to first item; current item is: " + it.currentItem());
    it.next();
    it.remove();
    System.out.println("Advanced cursor and removed item; current item is: " + it.currentItem());
    it.first();
    it.insert(new Integer(100));
    it.insert(new Integer(200));
    it.insert(new Integer(300));
    System.out.println("After moving cursor to the front and inserting " +
		       "100, 200, 300, the list is:" + l);
    System.out.println("The maximum of " + l + " is: " + max(l));
    for (it.first(); !it.atEnd(); ) it.remove();
    System.out.println("After removing all elements, the list is: " + l);
  }
}