1.7.2 Using Classes and Interfaces to Enforce Invariants

Some data objects have an associated invariant (boolean condition) which must be maintained for the object to be well-formed. For example, the elements in a sorted list must appear in ascending order. In many cases, we can use an interface to ensure that such an invariant always holds.

Consider the example that we already cited: a sorted list. Can we define an OrdList class hierarchy with subclasses Empty and OrdCons similar to the IntList class hierarchy in Section 1.6.2 that guarantees that all instances are sorted? The answer is yes, but we have to change the visible interface (members) of the class. In particular, we cannot allow clients of the OrdList type to perform new operations on the OrdCons class. To add an element to an OrdList, clients must use a method

OrdList insert(int f)

that inserts f in proper position in this.

The OrdCons class includes a binary constructor just like IntList except for the fact that it is private, implying that no code outside of class OrdCons can use it. This visibility restriction raises a minor problem: how can we write the insert method for the Empty subclass? The binary OrdCons constructor is not accessible! The answer is to define a second constructor for the OrdCons class that takes a single int argument and initializes the rest field to Empty.only.

Finger Exercises

1.

Write a definition for the OrdList composite class hierarchy as described above. Test your code.

2.

Load your saved program IntList.java from the preceding finger exercise. into the Definitions window of DrJava. Convert the abstract class IntList to an interface and make the fields of Cons private. Define OrdList as an interface extending IntList interface with the methods:

OrdList insert(int i);
OrdList empty();

Define OrdCons as a subclass of Cons. The OrdCons and Empty classes implement the interface OrdList. The member fields of Cons can be private if you rely on a super call to initialize these fields in your OrdCons constructors.

3.

Define a sort method for the class IntList that sorts a list converting all Cons nodes to OrdCons nodes. Test your code. Save your program as OrdList.java.

4.

(Optional) The IntList interface includes the help functions for toString() and reverse() which do not belong in an interface because they are artifacts of a particular implementation. Remove these methods from the IntList interface and place them in a separate abstract class IntListClass.