/** Data Definition: IntList :=  new Empty() + new Cons(int, IntList) */

interface IntList {
  /** Returns the empty list. */
  OrdList empty();
  /** Adds i to the front of this. */
  IntList cons(int i);
  /** Sort the IntList to produce an OrdList */
  OrdList sort();
  String toStringHelp();
}

interface OrdList extends IntList {
  OrdList insert(int i);
}

class Empty implements OrdList {

  static Empty ONLY = new Empty(); // singleton pattern

  /* constructor */
  private Empty() {} 

  /* OrdList methods */

  public OrdList empty() { return Empty.ONLY; }
  public OrdList insert(int i) { return new OrdCons(i); }

  /** returns String representation of Empty */
  public String toString() { return "()"; }

  /* IntList methods */
  public IntList cons(int i) { return new Cons(i, Empty.ONLY); }
  public OrdList sort() { return this; }
  /** returns String representation of Empty without enclosing parens */
  public String toStringHelp() { return ""; }
}

class Cons implements IntList {

  private int first;
  private IntList rest;

  /* constructor */
  Cons(int f, IntList r) {
    first = f;
    rest = r;
  }

  /* accessors */
 
  /** returns first element of non-empty list */
   int getFirst() { return first; };    

  /** returns all but the first element of non-empty list */
  IntList getRest() { return rest; }
 
  public String toString() {
    // no leading space before first
    return "(" + first + rest.toStringHelp() + ")";
  }
  public OrdList sort() { return rest.sort().insert(first); }
  public IntList cons(int i) { return new Cons(i, this); }
  public String toStringHelp() {
    // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}

class OrdCons extends Cons implements OrdList {

  /* Constructors */
  OrdCons(int i, OrdList ol) { super(i, ol); }
  OrdCons(int i) { super(i, Empty.ONLY); }

  /* OrdList methods */
  public OrdList empty() { return Empty.ONLY; }
  public OrdList insert(int i) { 
    if (i <= getFirst()) return new OrdCons(i, this);
    else return new OrdCons(getFirst(), ((OrdList) getRest()).insert(i));
  }
  
}