4.1 Mutable linear recursive structure  (Page 2/2)

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

3. example

Consider the problem of inserting an Integer object in order into a sorted list of Integers.  Let us contrast the insert in order algorithms between IList , the immutable list, and LRStruct , the mutable list.