1.7.4 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:

import java.util.*;
interface CompList {
  abstract Comparable getFirst();
  abstract CompList getRest();
  abstract String toStringHelp();
}

class Empty implements CompList {
  static Empty only = new Empty();
  
  public Comparable getFirst() { throw 
    new NoSuchElementException("getFirst() requires a non-Empty CompList");
  }
  
  public CompList getRest() { throw 
    new NoSuchElementException("getRest() requires a non-Empty CompList");
  }

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

  public String toStringHelp() { return ""; }

  public static void test() {
    CompList e = new Empty();
    System.out.println("() = " + e);
  }
}

class Cons implements CompList {
  Comparable first;
  CompList rest;
  
  Cons(Comparable f, CompList r) { first = f; rest = r; }

  public Comparable getFirst() { return first; }
  public CompList getRest() { return rest; }
   
  public String toString() {
    return "(" + first + rest.toStringHelp() + ")";
  }
 
  public 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), twoElts));
}

class Test {
  public static void test() {
    Empty empty = new Empty();
    System.out.println("twoElts is: " + Cons.twoElts);
    System.out.println("fourElts is: " + Cons.fourElts);
  }
}

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 NoSuchElementException indicating an erroneous use of the compareTo method.

In the CompList class, we can impose a lexicographic total ordering on lists of Comparable elements. This ordering is a generalization of the familiar alphabetic ordering on strings. In such an ordering, aprecedes 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.

For example, the Empty list is less than any non-empty (Cons) list. Similarly, the list ``("Jane", "Kyle")'' is less than ``("Sudaret", "Kyle")''.

Finger Exercise Enter the code for CompList class given above in the DrJava Definitions window. 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.