/** ComparableList ::= EmptyComparableList | ConsComparableList(Comparable, ComparableList). */ abstract class ComparableList { /** Sorts this ComparableList into ascending (non-descending) order. */ abstract ComparableList sort(); /** Adds the Comparable o to the front of this ComparableList. */ ComparableList add(Comparable o) { return new ConsComparableList(o, this); } /** Inserts n in proper order in this, assuming this is sorted in ascending order. */ abstract ComparableList insert(Comparable n); } class EmptyComparableList extends ComparableList { /** Singleton instance of this class. */ static EmptyComparableList ONLY = new EmptyComparableList(); private EmptyComparableList() { } ComparableList sort() { return this; } ComparableList insert(Comparable n) { return add(n); } } class ConsComparableList extends ComparableList { /** The first element of this ComparableList. */ Comparable first; /** The remaining elements of this ComparableList. */ ComparableList rest; ComparableList sort() { return rest.sort().insert(first); } ComparableList insert(Comparable c) { if (c.compareTo(first) <= 0) return add(c); else return rest.insert(c).add(first); } }