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

abstract class IntList {

  /* Cons accessors */
  abstract int getFirst();    
  // throws an IllegalArgumentException on Empty
  // returns first element of non-empty list

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

  /* other methods */
  abstract IntList insert(int e);
  // given the elements of this appear in non-descendin order
  // returns this with e inserted in nonde

  abstract IntList sort();
  // returns the elements of this in nondescending order

  abstract String toStringHelp();  
  // returns "" for Empty
  //         " e1 e2 ... en" for IntList with elts e1,...,en
  
  static void test() {
    System.out.println(Cons.threeElts.sort());
  }
}

class Empty extends IntList {

  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 sort() { return Empty.only; }
  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 IntList oneElt = new Cons(-17, Empty.only);
  static IntList twoElts = new Cons(7, oneElt);
  static IntList threeElts = new Cons(25, twoElts);

  int first;
  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));
  }

  IntList sort() { return rest.sort().insert(first); }

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