// Data Definition: List := new Empty() + new Cons(Object, List)
abstract class List {

    abstract String toStringHelp();
    abstract List concat(List other);

    abstract List reverse();
    abstract List reverseHelp(List stack);

    /**
     * Returns the last element Object in this List.
     * Throws a run-time exception if this List is empty.
     */
    abstract Object getLast();

    /**
     * "Helper" for getLast().
     * Helps determine the last element, given the element of the preceding list.
     * @param previous the element of the preceding list.
     * @return the object that is the last element of the enclosing list.
     */
    abstract Object getLastHelp(Object previous);

    /**
     * Assumes this List contains zero or more Comparable objects of the same
     * class type, sorted in ascending order.  "Inserts" a compatible data
     * object in order into this List.
     * @param compDat a Comparable object that is of the same class type with
     * the elements in this List.
     * @return a non-empty List containing that contains compDat and the elements
     * in this List sorted in ascending order.
     */
    abstract List insert(Object compDat);

     /**
     * Assumes this List contains zero or more Comparable objects of the same
     * class type; sorts the list in ascending order.
     * @return a List containing that contains all the elements in this List
     * sorted in ascending order.
     */
    abstract List sort();
}

class Empty extends List {
    static final Empty ONLY = new Empty();
    private Empty() {
    }

    List concat(List other) {
        return other;
    }

        public String toString() {
        return "[]";
    }
    String toStringHelp() {
        return "";
    }

    /**
     * The reverse of the empty list is the empty list itself!
     */
    List reverse() {
        return this;
    }

    /**
     * The parameter stack is the accumulated reverse of the list so far.
     * Since we are at the empty list, there is nothing else to reverse here.
     * stack is thus the reverse of the whole original list.
     */
    List reverseHelp(List stack) {
        return stack;
    }


    /**
     * Throws a special run-time exception called NoSuchElementException.
     * This class is in the java.util package.
     * Note the syntax for specifying the full package name of NoSuchElementException.
     * @return does not return normally
     * @throw java.util.NoSuchElementException
     */
    Object getLast() {
        throw new java.util.NoSuchElementException("Empty list has no data!");
    }

    /**
     * This List is empty, which means the element in the preceding list is the
     * last element of the enclosing list.
     * @param previous the element of the preceding list.
     * @return previous
     */
    Object getLastHelp(Object previous) {
        return previous;
    }

    /**
     * Since this List is empty, there is nothing to compare against: simply
     * insert the given data into the list by creating a new list with one
     * element: the given data element.
     * @param compDat a Comparable object that is of the same class type with
     * the elements in this List.
     * @return a non-empty List containing that contains compDat.
     */
    List insert(Object compDat) {
        return new Cons(compDat, Empty.ONLY);
    }

    /**
     * There is nothing to sort!
     * @return this List.
     */
    List sort() {
        return this;
    }

}

class Cons extends List {
    Object first;
    List rest;

    Cons(Object f, List r) {
        first = f;
        rest = r;
    }

    /**
     * Creates the reverse of the list so far, and sends it to rest asking
     * for help to reverse the rest.
     */
    List reverse() {
        return rest.reverseHelp(new Cons(fisrt, Empty.ONLY));
    }

    /**
     * There is still more elements to reverse.
     * Creates the reverse of the list so far, and sends it to rest asking
     * for help to reverse the rest.
     */
    List reverseHelp(List stack) {
        return rest.reverseHelp(new Cons(first, stack));
    }


     /**
     * no leading space before first
     */
    public String toString() {
        return "[" + first + rest.toStringHelp() + "]";
    }
    /**
     * leading space before each elt
     */
    String toStringHelp() {
        return " " + first + rest.toStringHelp();
    }
// List jeannie = Empty.ONLY looks like []
// List mary = new Cons("abc", Empty.ONLY) looks like ["abc"]
// List carolyn = new Cons(new Integer(5), mary) looks like [5 "abc"]

    Object getFirst() {
        return first;
    }

    List getRest() {
        return rest;
    }

    /**
     * Example: [1 2].concat(["a" "b" "c"]) returns [1 2 "a" "b" "c"]. In this
     * example, the List object that receives the method call is the list [1 2],
     * while other, the parameter of the method, is the list ["a" "b" "c"].
     */
    List concat(List other) {
        List rc = rest.concat(other); // rc is now [2 "a" "b" "c"].
        return new Cons(first, rc); // returning [1 2 "a" "b" "c"]
        // The above two lines of code can be combined into one line of code as
        // follows:
        // return new Cons(first, rest.concat(other));
    }

    /**
     * Cannot tell whether or not first, the current data object, is the last
     * element.
     * Passes first to rest and asks for help determining the last element.
     * @return the last element of this List.
     */
    Object getLast() {
        return rest.getLastHelp(first);
    }

    /**
     * This List is not empty, wich means the element in the preceding list
     * cannot be last element of the enclosing list.
     * The current first element may be the last element!
     * Passes first to rest and asks for help again.
     * @param previous the element of the preceding list.
     * @return the last element of this List.
     */
    Object getLastHelp(Object previous) {
        return rest.getLastHelp(first);
    }

    /**
     * Compares the given data with first:
     * if data < first: inserts data to the front of the list
     * else: inserts in order data into the rest, then inserts first to the
     * front of the result.
     * @param compDat a Comparable object that is of the same class type with
     * the elements in this List.
     * @return a non-empty List containing that contains compDat and the elements
     * in this List sorted in ascending order.
     */
    List insert(Object compDat) {
        Comparable dat = (Comparable)compDat;
        if (dat.compareTo(first) < -1) {
          return new Cons(dat, this);
        }
        else {
          List sortedRest = rest.insert(compDat);
          return new Cons(first, sortedRest);
        }
    }

    /**
     * Sorts the rest of this List, then inserts first into the sorted rest!
     * @return a List containing that contains all the elements in this List
     * sorted in ascending order.
     */
    List sort() {
        List restSort = rest.sort();
        return restSort.insert(first);
    }
}