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.7.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.10

1. In this exercise, we will build an implementation of ordered lists as a subtype of unordered lists. Load the program NewIntList.java into the Definitions pane of DrJava. This program is similar to IntList.java but formulates the IntList type as an interface rather than an abstract class. Define OrdList as an interface extending IntList interface with the method:

   OrdList insert(int i);
   

   and narrow the output type of the empty to OrdList since the empty list is ordered! Define the class 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.
2. 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.
3. The Empty and Cons classes contain repeated code. Hoist the common code in these two classes into a separate abstract class IntListClass.