/** 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 "" for Empty
   *          " e1 e2 ... en" for IntList with elts e1,...,en
   */
  abstract String toStringHelp();  

}

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");
  }

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

  String toStringHelp() { return ""; }
}

class Cons extends IntList {

  /* 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;  }

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

class TestIntList {

  /* sample IntList values */
  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);

  /* IntList test method */
  static void test() {
    System.out.println("Sample list is: " + fiveElts);
    System.out.println("first = " + fiveElts.getFirst());
    System.out.println("rest = " + fiveElts.getRest());
    System.out.println("first of rest = " + fiveElts.getRest().getFirst());
  }
}