// Predicate is command pattern for int -> boolean
interface Predicate {
  public boolean execute(int i);
}

// 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 filter(Predicate p);
    // returns list of elements that satisfy p
  
  abstract IntList insert(int e);
    // given the elements of this appear in non-descendin order
    // returns this with e inserted in nonde

  abstract String toStringHelp();  
    // returns "" for Empty
    //         " e1 e2 ... en" for IntList with elts e1,...,en
  
    static void test() {
    IntList one = Cons.fiveElts.insert(-5).insert(13);
    System.out.println("List1 = " + one);
    System.out.println("Odd elements of List1 are: " + one.filter(new Predicate() { /* ANONYMOUS CLASS */
	public boolean execute(int i) { return i % 2 != 0; } }));          
    }
}

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 filter(Predicate p) { 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 ""; }
}

class Cons extends IntList {

  static IntList oneElt = new Cons(15, Empty.only);
  static IntList twoElts = new Cons(10, oneElt);
  static IntList threeElts = new Cons(5, twoElts);
  static IntList fourElts = new Cons(0, threeElts);
  static IntList fiveElts = new Cons(-5, fourElts);

  int first;
  IntList rest;

    /* constructor */
    Cons(int f, IntList r) {
    first = f;
    rest = r;
    }

    /* accessors */
    int getFirst() { return first; }
    IntList getRest() { return rest; }

    /* other methods */
    IntList filter(Predicate p) {
    if (p.execute(first)) return new Cons(first, rest.filter(p));
    else return rest.filter(p);
    }
  
    IntList insert(int e) { 
    if (e <= first) return new Cons(e,this);
    else return new Cons(first, rest.insert(e));
    }

    public String toString() {
	// no leading space before first
    re