Structure
The list structure is one of the most fundamental data structures in programming. The following is a common definition of a list.
- A list is either empty or non-empty. If it is empty it contains no elements. If is not empty, it contains an element called first and an element called rest, which is itself a list.
We rephrase the above as follows.
- There is an abstract notion of a list. A list knows how to return the
element called first and the element called rest, which is itself
another list.
The empty list is a list. It has no first and no rest element.
A non-empty list is a list. It has an element called first and an element called rest, which is itself another list.
We model this abstract notion of a list by an abstract class called AList, the empty list and the non-empty lists as a concrete subclasses of AList called EmptyList and NEList respectively. The following UML diagram illustrates this structural design.
In the above diagram, the methods getFirst() and getRest() in AList are pure abstract, that is they contain no code body. They are overriden in the concrete subclasses NEList and EmptyList with concrete code body to carry out the appropriate tasks. The client should program only to the abstract class AList. Polymorphism will properly dispatch the method call to the appropriate concrete subclass at run-time.
The EmptyList class is implemented with the singleton pattern to model the fact that there is a unique empty list.
An NEList object "has a" an element, called rest, whose structure is isomorphic to the enclosing NEList object itself.. NEList is said to be a composite. Its structure is recursively constructed and terminates with the "base case", the EmptyList. The above taxonomy is an example of what is called the composite design pattern. The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structure is isomorphic to that of the container itself. In this pattern, the container is called a composite. The composite pattern also prescribes a coding pattern for the container's methods: when a container is called to perform an operation, it iterates through its list of composed objects and call on them to perform the same operation. It allows the client to treat the container and what it contains uniformly by making use of polymorphism. The following UML diagram illustrates the general composite pattern.
In many situations, an operation may call on "helper" operations on the sub-components to carry out the task. The coding pattern for an operation that requires a helper is as follows.
class Composite extends AComponent
{
// fields and sub-components.
public Object doTask (Object input)
{
// Process the input parameter and the data fields to obtain a temporary
result needed by the sub-components to help complete the task:
Object temp = process (data fields, input);
// Pass the temporary result to each of the sub-components asking each of
them to "help" complete the task:
Object pr1 = _part1.helpDoTask (temp); //
partial result 1.
Object pr2 = _part2.helpDoTask
(temp);
// etc...
Object prN = _partN.helpDoTask
(temp);
//
Reassemble the partial results computed by the sub-components to obtain the
final result:
return putTogether (pr1, pr2, ..., prN);
}
protected Object helpDoTask (Object input)
{
// Process the input parameter and the data fields to obtain a temporary
result needed by the sub-components to help complete the task:
Object temp = processPartial (data fields, input);
// Pass the temporary result to each of the sub-components asking each of
them to "help" complete the task:
Object pr1 = _part1.helpDoTask (temp); //
partial result 1.
Object pr2 = _part2.helpDoTask
(temp);
// etc...
Object prN = _partN.helpDoTask
(temp);
//
Reassemble the partial results computed by the sub-components to obtain the
final result:
return putTogetherPartial (pr1, pr2, ..., prN);
}
}
class Basic extends AComponent
{
// fields
public Object doTask (Object input)
{
// Process the input parameter and the data fields to obtain the result:
return simpleProcess (data fields, input);
}
protected Object helpDoTask (Object input)
{
// Process the input parameter and the data fields to obtain the result:
return simpleProcessPartial (data fields, input);
}
}
The exercises listed in the last section illustrate the composite coding pattern.
Behavior
AList and its subclasses in the above design are not very "smart". An AList cannot do much besides providing the first and rest to its client. A crude way of adding more capability (or "intelligence") the above system is to add methods to AList and its subclasses, as shown in the UML diagram below. In this diagram, we do not show the concrete inherited methods for brevity. We also add a singleton class called ListFactory to manufacture concrete AList objects. ListFactory is an example of what is called the factory pattern. In our case, ListFactory allows us to hide all details of the concrete subclasses from the client, forces the client to program only to the abstract class AList, and thus exercising the general principle of "information hiding".
Exercises
Implement all the methods in AList as specified. (Solutions).