A mutable linear recursive structure (LRStruct) can be in the empty state or in a non-empty state. If it is empty, it contains no object. Otherwise, it contains
an object called first, and a LRStruct object called rest. When we insert a data object into an empty LRStruct, it changes it state to non-empty. When we remove the last element from an non-empty LRStruct, it changes its state to empty. We model
a LRStruct using the state pattern, and as in the case of the immutable list, we also apply the visitor pattern to obtain a framework. Below is the UML class diagram of the LRStruct framework. Because of the current limitation of our diagramming tool, we are using the
Object[]input notation to represent the variable argument list Object... input.
Download the code and the javadoc documentation here:
The public constructor:
- LRStruct()
and the methods:
- insertFront(...)
- removeFront(...)
- getFirst()
- setFirst(...)
- getRest()
- setRest(...)
of LRStruct expose the structure of an LRStruct to the client and constitute the intrinsic structural behavior of an LRStruct. They form a minimal and complete set of methods for manipulating an LRStruct. Using them, a client can create an empty LRStruct, store data in it, and remove/retrieve data from it at will.
The method,
- Object execute(IAlgo algo, Object inp)
is called the extensibility "hook". It allows the client to add an open-ended number of new application-dependent behaviors to the data structure LRStruct, such as computing its length or merging one LRStruct with another, without modifying any of the existing code. The application-dependent behaviors of LRStruct are extrinsic behaviors and are encapsulated in a union represented by a visitor interface called IAlgo.
When a client programs with LRStruct, he/she only sees the public methods of LRStruct and IAlgo. To add a new operation on an LRStruct, the client writes appropriate concrete classes that implements IAlgo. The framework dictates the overall design of an algorithm on LRStruct: since an algorithm on LRStruct must implement IAlgo , there must be some concrete code for emptyCase(...) and some concrete code for nonEmptyCase(...). For example,
public class DoSomethingWithLRS implements IAlgo { // fields and constructor code... public Object emptyCase(LRStruct host, Object... inp) { // some concrete code here... return some Object; // may be null. } public Object nonEmptyCase(LRStruct host, Object... inp) { // some concrete code here... return some Object; // may be null. } }
As illustrated in the above, an algorithm on LRStruct is "declarative" in nature. It does not involve any conditional to find out what state the LRStruct is in order to perform the appropriate task. It simply "declares" what needs to be done for each state of the host LRStruct, and leaves it to the polymorphism machinery to make the correct call. Polymorphism is exploited to minimize flow control and reduce code complexity.
To perform an algorithm on an LRStruct, the client must "ask" the LRStruct to "execute" the algorithm and passes to it all the inputs required by the algorithm.
LRStruct myList = new LRStruct(); // an empty list // code to call on the structural methods of myList, e.g. myList.insertFront(/*whatever*/) // Now call on myList to perform DoSomethingWithLRS: Object result = myList.execute(new DoSomethingWithLRS(/* constructor argument list */), -2.75, "abc");
Without knowing how LRStruct is implemented, let us look an example of an algorithm on an LRStruct.
- 1312 reads
