interface Ordering {
  boolean inOrder(Object a, Object b);
}

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

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

  abstract List getRest();
  // throws an IllegalArgumentException on Empty
  // returns the ``rest'' a non-empty list (all elements but first)
  
  abstract List sort(Ordering ord);
  
  abstract List insert(Object o, Ordering ord);

  abstract String toStringHelp();  
  // returns "" for Empty
  //         " e1 e2 ... en" for List with elts e1,...,en
}

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

  /* Cons accessors */	
  Object getFirst() { throw new IllegalArgumentException(
   "first requires a non Empty List");
  }
  List getRest() { throw new IllegalArgumentException(
   "rest requires a non Empty List");
  }
  
  List sort(Ordering ord) { return Empty.only; }
  
  List insert(Object o, Ordering ord) { return new Cons(o, Empty.only); }

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

  String toStringHelp() { return ""; }
}

class Cons extends List {

  Object first;
  List rest;

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

  /* accessors */
  Object getFirst() { return first; }
  List getRest() { return rest;  }
  
  List sort(Ordering ord) { return rest.sort(ord).insert(first, ord); }
  
  List insert(Object o, Ordering ord) {
    if (ord.inOrder(o, first)) return new Cons(o,this);
    else return new Cons(first, rest.insert(o,ord));
  }
 
  public String toString() {
    // no leading space before first
    return "(" + first + rest.toStringHelp() + ")";
  }
  String toStringHelp() {
    // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}

class Ascending implements Ordering {
  public boolean inOrder(Object a, Object b) {
    return ((Integer) a).intValue() <= ((Integer) b).intValue();
  }
}
class Descending implements Ordering {
  public boolean inOrder(Object a, Object b) {
    return ((Integer) a).intValue() >= ((Integer) b).intValue();
  }
}
class AscendingMagnitude implements Ordering {
  public boolean inOrder(Object a, Object b) {
    int a1 = ((Integer) a).intValue();
    int b1 = ((Integer) b).intValue();
    return Math.abs(a1) <= Math.abs(b1);
  }
}

class Test {

  static List buildIntegerList(int start, int stride, int ct) {
    if (ct == 0) return Empty.only;
    else return new Cons(new Integer(start), buildIntegerList(start+stride, stride, ct-1));
  }

  static List l1 = buildIntegerList(0,2,10);
 
  static List l2 = buildIntegerList(25,-5,10);
  
  static Ordering up = new Ordering() { /* ANONYMOUS class */
                         public boolean inOrder(Object a, Object b) {
                           return ((Integer) a).intValue() <= ((Integer) b).intValue();
                         }
                       };
  static Ordering down = new Descending();
  static Ordering upMag = new AscendingMagnitude();
}