The LRStructure Package

The Linear Recursive Structure package is a State design pattern implementation of a full OO-style recursive, mutable linked list.   The LRStruct class is provides the 6 complete (and possibly minimal -- unproven as yet) methods upon which all algorithms on the list can be built.   A seventh, extensibility hook is provided to add external algorithms that implement the IAlgo interface.   This interface implements a (slightly modified) Visitor design pattern.   More information can be obtained from the original papers by Dung Nguyen and Stephen Wong presented at SIGCSE'98 and SIGCSE '99.   A lazy evaluation extension to LRStruct that demonstrates its power and flexibility was presented at SIGCSE'00 .    

LRStruct adheres to the notion that a list can be described as either:

1. Empty (null), or
2. Non-empty (non-null) where upon it contains:
   1. A data object ("first") and
   2. A reference to the rest of the list ("rest").

This implies that a list can be modeled as a two-state system and thus makes the State design pattern a natural implementation candidate.    The dynamic reclassification capabilities of the State pattern enables the elimination of control structures that would otherwise be used to determine whether the list is empty or not.   Instead, polymorphism is used to let the list behave naturally whether it is empty or non-empty -- no checks are needed to obtain the correct behavior. 

The only public methods supplied by LRStruct are the minimum needed to construct any arbitrary operation on the list:

1. Methods for growing and shrinking the list.
2. Accessor methods for "first".
3. Accessor methods for "rest".

In addition, there are package accessible two accessor methods for the internal state, which are used by the concrete states to effect state changes.

To enable the list to execute any arbitrary algorithm, an extensibility hook was added.   All recursive list algorithms have been abstracted into the IAlgo interface.   This interface has two methods, one for the base (null) case and one for the inductive case (non null case).   The Visitor pattern uses polymorphism to select the appropriate method to execute depending on which state the list is in.   An algorithm is executed by handing the algorithm object to the LRStruct, which in turn, hands it to its state.   Since a concrete state knows intrinisically whether it is null or non-null, it can immediately call the matching method in the algorithm.    A reference to the calling list is handed to the algorithm for it to work on.   This is basically the classic "double dispatch" method of dynamic behavior determination.   Another way to view the system is to recognize that LRStruct provides a framework that executes the component algorithms.

LRStruct thus encapsulates purely invariant list behavior and can be used unmodified for any purpose.    All algorithms on the list implement the IAlgo interface and are very similar to the recursive algorithms expressed in declarative languages.   As in those languages, the programmer only needs to separately write the base and inductive cases without worrying about overarching control structures (which don't exist at all here!).

Note:  At the moment, the LRStructure package is not designed to be thread-safe.

Note:  The package, class, variable and method names in the documentation may differ slightly from the those used in the distribution packages used at Rice University.