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 increasing order (non-decreasing if duplicates are allowed). In many cases, a class can ensure that such an invariant always holds by enforcing a well-chosen interface.
Consider the example that we already cited: a sorted list. Can we define a class OrdList similar to IntList class that guarantees that all instances are sorted? The answer is yes, but we have to change the visible interface (members) supported by the IntList class. In particular, we cannot allow clients of the OrdList class to perform new operations on OrdList. 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 Ordlist class includes a binary constructor just like IntList except for the fact that it is private, implying that no code outside of class Cons can use it. This visibility restriction raises a minor problem: how can we write the insert method for the Empty subclass? The binary Cons constructor is not accessible! The answer is to define a second constructor for the Cons class that takes a single int argument and initializes the rest field to Empty.ONLY.
Finger Exercise
Write a definition for the OrdList
composite class hierarchy as described above. Test your code.
Exercise
Load the sample program IntList into the Definitions
pane. Define a subclass OrdCons extending Cons
that guarantees that first precedes rest.first (assuming
it exists). The rest field of a OrdCons node must be
either Empty or OrdCons.
Define a sort method for the class IntList
that sorts a list converting all Cons nodes to OrdCons
nodes. Test your code.