1.7.3 Interface Types

An interface identifies a program type independent of any specific class. This mechanism enables Java to express computations in more abstract and flexible terms. Consider the following example. Java includes a built-in interface named Comparable with the following definition:

interface Comparable {
  int compareTo(Object o);
}

All of the methods in an interface are automatically abstract and public. Let us define a class CompList similar to IntList where list elements have the type Comparable. An object has type Comparable iff it is an instance of a class that implements the Comparable interface. Interface implementation is inherited: if a class C implements an interface I then all subclasses of C implement I also.

In this context, we can define the class CompList as follows:

abstract class CompList {
  abstract Comparable getFirst();
  abstract CompList getRest();
  abstract String toStringHelp();

  public static void main(String[] args) {
    Empty empty = new Empty();
    System.out.println("twoElts is: " + Cons.twoElts);
    System.out.println("fourElts is: " + Cons.fourElts);
  }
}

class Empty extends CompList {
  Comparable getFirst() { throw 
     new IllegalArgumentException("getFirst() requires a non-Empty CompList");
  }
  
  CompList getRest() { throw 
    new IllegalArgumentException("getRest() requires a non-Empty CompList");
  }

  public String toString() { return "()"; }

  String toStringHelp() { return ""; }

  public static void main(String[] args) {
    CompList e = new Empty();
    System.out.println("() = " + e);
  }
}

class Cons extends CompList {
  Comparable first;
  CompList rest;
  
  Cons(Comparable f, CompList r) { first = f; rest = r; }
  Comparable getFirst() { return first; }
  CompList getRest() { return rest; }
   
  public String toString() {
    return "(" + first + rest.toStringHelp() + ")";
  }
 
  String toStringHelp() {
    return " " + first + rest.toStringHelp();
  }

  static Cons twoElts = 
    new Cons(new Integer(1), new Cons(new Integer(2), Empty.ONLY));
  static Cons fourElts = 
    new Cons(new Integer(-1), new Cons(new Integer(-2), l1));

}

Now assume that we want to modify the CompList class so that it implements the Comparable interface. The compareTo method in the Comparable interface has the following contract. Any class C that implements the Comparable interface must have an associated binary relation that is totally ordered: for every pair of objects a and b in C, either (i) a is less than b, (ii) a equals b, or (iii) a is greater than b. For any instance o of the same class as this, compareTo(o) returns (i) a negative number if this is less than o, (ii) zero if this equals o, and (iii) a positive number if this is greater than o. If o belongs to a different class than this, compareTo(o) throws a ClassCastException indicating an erroneous use of the compareTo method.

In the CompList class, we can impose a lexicographic total ordering on lists. This ordering is a generalization of the familiar alphabetic ordering on strings. In such an ordering, a precedes b iff either

• a is empty and b is not,
• the first element of a precedes the first element of $b$, or
• the first element of a equals the first element of $b$ and the rest of a precedes the rest of $b$.

Finger Exercise Load your saved file objectList.java int the DrJava Definitions pane. Convert it to a definition of the class CompList given above. Modify this CompList class to implement the Comparable interface as described above. Include test examples in your code and run them to confirm that your program works in these cases.