/** Composite Data Definition: 
 *  IntList := new Empty() + new Cons(int, IntList)
 */
abstract class IntList {

  /** Returns first element of non-empty list.
   *  Throws an IllegalArgumentException on Empty.
   */ 
  abstract int getFirst();    

  /** Returns the ``rest'' a non-empty list (all elements but first).
   *  Throws an IllegalArgumentException on Empty.
   */
  abstract IntList getRest();

  /** Returns a new list consisting of this with e inserted in 
   *  ascendign order.
   *  Precondition: this is sorted in ascending order
   */
  abstract IntList insert(int e);

  /** Returns "" for Empty
   *          " e1 e2 ... en" for IntList with elts e1,...,en
   */
  abstract String toStringHelp();  

  static void test() {
    System.out.println(Cons.threeElts.insert(0).insert(20));
  }
}

class Empty extends IntList {

  /** The only instance of class Empty */
  static Empty only = new Empty(); // singleton pattern

  /* constructor */
  private Empty() {} 

  /* Cons accessors */  
  int getFirst() { throw new IllegalArgumentException(
   "first requires a non Empty IntList");
  }

  IntList getRest() { throw new IllegalArgumentException(
   "rest requires a non Empty IntList");
  }

  /* other methods */
  IntList insert(int e) { return new Cons(e,Empty.only); }

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

  String toStringHelp() { return ""; }
}

class Cons extends IntList {

  static final IntList oneElt = new Cons(15, Empty.only);
  static final IntList twoElts = new Cons(10, oneElt);
  static final IntList threeElts = new Cons(5, twoElts);
  static final IntList fourElts = new Cons(0, threeElts);
  static final IntList fiveElts = new Cons(-5, fourElts);

  /* private fields */
  private int first;
  private IntList rest;

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

  /* accessors */
  int getFirst() { return first; }
  IntList getRest() { return rest;  }

  /* other methods */
  IntList insert(int e) { 
    if (e <= first) return new Cons(e,this);
    else return new Cons(first, rest.insert(e));
  }

  public String toString() {
    // no leading space before first
    return "(" + first + rest.toStringHelp() + ")";
  }
  String toStringHelp() {
    // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}