import java.util.*; // Needed for iterator interface

// For ease of reading these classes have been put in a file
// That is why none of them are declared to be public

// A run-time exception for invalid positions
class InvalidPositionException extends RuntimeException {  
       public InvalidPositionException(String err) {
         super(err);
       }
}

// A run-time exception for Empty list
class EmptyContainerException extends RuntimeException {
   public EmptyContainerException (String err) {
      super(err);
   }
}

// A run-time exception for traversing beyond end of the list
class BoundaryViolationException extends RuntimeException {
   public BoundaryViolationException (String err) {
      super(err);
   }
}

// A run-time exception for traversing beyond end of the list.
// This does not always have to be runtime, though. 
class UnImplementedException extends RuntimeException {
   public UnImplementedException (String err) {
      super(err);
   }
}

// Abstract ADT position
interface Position {
   public Object element();
}

// The node of a doubly linked list
class DNode implements Position {
       private DNode prev, next;     // References to the nodes before and after
       private Object element;       // Element stored in this position
       // Constructor
       public DNode(DNode newPrev, DNode newNext, Object elem) {
         prev = newPrev;
         next = newNext;
         element = elem;
       }
       // Method from interface Position
       public Object element() throws InvalidPositionException {
         if ((prev == null) && (next == null))
           throw new InvalidPositionException("Position is not in a list!");
         return element;
       }
       // Accessor methods
       public DNode getNext() { return next; }
       public DNode getPrev() { return prev; }
       // Update methods
       public void setNext(DNode newNext) { next = newNext; }
       public void setPrev(DNode newPrev) { prev = newPrev; }
       public void setElement(Object newElement) { element = newElement; }
     }


// ADT List. Implementation could be using linked lists, arrays, etc.
interface List {
       public int size();
       public boolean isEmpty();
       public boolean isFirst(Position p) throws InvalidPositionException;
       public boolean isLast(Position p) throws InvalidPositionException;
       public Position first() throws EmptyContainerException;
       public Position last() throws EmptyContainerException;
       public Position before (Position p)  
         throws InvalidPositionException, BoundaryViolationException;
       public Position after (Position p) 
         throws InvalidPositionException, BoundaryViolationException;
       public Position insertBefore (Position p, Object element) 
         throws InvalidPositionException;
       public Position insertAfter (Position p, Object element) 
         throws InvalidPositionException;
       public Position insertFirst(Object element);
       public Position insertLast(Object element);
       public Object remove(Position p) throws InvalidPositionException;
       public Object replaceElement (Position p, Object element)  
         throws InvalidPositionException;
       public void swapElements (Position a, Position b)
         throws InvalidPositionException;
       public Iterator iterator();

}


// A realization of List using linked list
class NodeList implements List {
       protected int numElts;                // Number of items in the list
       protected DNode header, trailer;      // Special sentinels

       // Constructor; O(1) time
       public NodeList() {
         numElts = 0;
         header = new DNode(null, null, null);       // create header
         trailer = new DNode(header, null, null);    // create trailer
         header.setNext(trailer);    // make header and trailer point to each other
       }

       // Convenience function; O(1) time
       protected DNode checkPosition(Position p) 
             throws InvalidPositionException {
         if (p == null)
           throw new InvalidPositionException
             ("Null Position passed to NodeList.");
         if (p == header)
             throw new InvalidPositionException
               ("The header node is not a valid position");
         if (p == trailer)
             throw new InvalidPositionException
               ("The trailer node is not a valid position");
         try {
           DNode temp = (DNode)p;
           if ((temp.getPrev() == null) || (temp.getNext() == null))
             throw new InvalidPositionException
               ("Position does not belong to a valid NodeList");
           return temp;
         } catch (ClassCastException e) {
           throw new InvalidPositionException
             ("Position is of wrong type for this container.");
         }
       }

       // Simple accessor methods:
       public int size() {  return numElts; }                // O(1) time
 
       public boolean isEmpty() { return (numElts < 1); }    // O(1) time

       public boolean isFirst(Position p)                    // O(1) time
           throws InvalidPositionException {  
         DNode v = checkPosition(p);
         return v.getPrev() == header;
       }

       public boolean isLast(Position p)                    // O(1) time
           throws InvalidPositionException {  
         DNode v = checkPosition(p);
         return v.getNext() == trailer;
       }

       public Position first()                               // O(1) time
           throws EmptyContainerException {
         if (isEmpty())
           throw new EmptyContainerException("List is empty");
         return header.getNext();
       }

       public Position last()                                // O(1) time
           throws EmptyContainerException {
         if (isEmpty())
           throw new EmptyContainerException("List is empty");
         return trailer.getPrev();
       }

       public Position before(Position p)                    // O(1) time
           throws InvalidPositionException, BoundaryViolationException {
         DNode v = checkPosition(p);
         DNode prev = v.getPrev();
         if (prev == header)
           throw new BoundaryViolationException
             ("Cannot advance past the beginning of the list");
         return prev;
       }

       public Position after(Position p)                    // O(1) time
           throws InvalidPositionException, BoundaryViolationException {
         DNode v = checkPosition(p);
         DNode next = v.getNext();
         if (next == trailer)
           throw new BoundaryViolationException
             ("Cannot advance past the end of the list");
         return next;
       }

       public Position insertBefore(Position p, Object element) 
           throws InvalidPositionException {                 // O(1) time
         DNode v = checkPosition(p);
         numElts++;
         DNode newNode = new DNode(v.getPrev(), v, element);
         v.getPrev().setNext(newNode);
         v.setPrev(newNode);
         return newNode;
       }

       public Position insertAfter(Position p, Object element) 
           throws InvalidPositionException {                 // O(1) time
         DNode v = checkPosition(p);
         numElts++;
         DNode newNode = new DNode(v, v.getNext(), element);
         v.getNext().setPrev(newNode);
         v.setNext(newNode);
         return newNode;
       }

       public Position insertFirst(Object element) {         // O(1) time
         numElts++;
         DNode newNode = new DNode(header, header.getNext(), element);
         header.getNext().setPrev(newNode);
         header.setNext(newNode);
         return newNode;
       }

       public Position insertLast(Object element) {         // O(1) time
         numElts++;
         DNode newNode = new DNode(trailer.getPrev(), trailer, element);
         trailer.getPrev().setNext(newNode);
         trailer.setPrev(newNode);
         return newNode;
       }

       public Object remove(Position p)                      // O(1) time
           throws InvalidPositionException {
         DNode v = checkPosition(p);
         numElts--;
         DNode vPrev = v.getPrev();
         DNode vNext = v.getNext();
         vPrev.setNext(vNext);
         vNext.setPrev(vPrev);
         Object vElem = v.element();
         // unlink the position from the list and make it invalid
         v.setNext(null);
         v.setPrev(null);
         return vElem;
       }

       public Object replaceElement(Position p, Object element)
           throws InvalidPositionException {                 // O(1) time
         DNode v = checkPosition(p);
         Object oldElt = v.element();
         v.setElement(element);
         return oldElt;
       }
         
       public void swapElements(Position a, Position b)
           throws InvalidPositionException {                 // O(1) time
         DNode pA = checkPosition(a);
         DNode pB = checkPosition(b);
         Object temp = pA.element();
         pA.setElement(pB.element());
         pB.setElement(temp);
       }
       public Iterator iterator() {
          return new ListIterator(this);
       }
}

class ListIterator implements Iterator { // Iterator is defined in java.util
// Works with all implementations of list as it only uses interface methods
   private List list;
   private Position current;

   public ListIterator(List list) {
      this.list = list;
      current = null; 
   }
   public ListIterator(List list, Position p) {
      this.list = list;
      current = p;
   }   

   public boolean hasNext() {
      if(current == null)
        return !(list.isEmpty());
      else
         return !(list.isLast(current));
   }
   
   public Position nextPos() {
      if(current == null)
         current = list.first();
      else
         current = list.after(current);
      return current; // Return directly the position. Sometimes this may be needed.
   }

   public Object next() {
      return nextPos().element();
   }

   public void remove() throws UnImplementedException {
      throw new UnImplementedException("Iterator remove is unimplemented"); 
   }

   ListIterator copy() {
      return new ListIterator(list, current);
   }
   // And, maybe, some other useful methods
}

class testlist {

   public static void main(String argv[]) {
      List l = new NodeList();
      Position p;
      //  p = l.first(); /* This will raise an exception */

      // Only testlist knows what kinds of objects we are inserting in the list
      l.insertFirst(new Integer(10));
      p = l.first();
      l.insertFirst(new Integer(15));
      l.insertBefore(p, new Integer(20));
      // We now have a list with three Integers 15, 20, and 10

      // Print the elements in a loop
      p = l.first();
      while(! l.isLast(p)) {
         System.out.println("Position = "+((Integer)p.element()).intValue());
         p = l.after(p);
      }
      System.out.println("Position = "+((Integer)p.element()).intValue());

      // Or use the (forward) iterator. One could similarly write a backward iterator.
      Iterator itr = l.iterator();
      while(itr.hasNext()) {
         System.out.println("PositionITR = "+((Integer)(itr.next())).intValue());
      }
   }
}