// 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.fiveElts.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 ""; }
}