Below is the UML class diagram showing the design of LRStruct, our framework for mutable linear recursive structure.
The code for LRStruct follows the state design pattern and is almost trivial. LRStruct is the invariant part of the system. It remains the same for all applications using LRStruct. On the other hand, the different kinds of operations you want to perform on an LRStruct vary from application to application. They form the variant part of the system. Their behaviors are abstractly encapsulated in an interface called IAlgo. This is an example of what we call "behaviorial abstraction", which is what an OO design should be striving for. Within this union of all possible algorithms on LRStruct, IAlgo is invariant! In any system, an abstract class (or interface) should never change.
package lrs; /** * Mutable linear recursive structure. * Visitor Pattern: Serves as a host capable of executing algorithms which are * visitors. */ public class LRStruct { /** * The state of of thisLRStruct
. */ private ANode _head; /** * Initializes thisLRStruct
to the empty state. */ public LRStruct() { _head = EmptyNode.Singleton; } /** * Returns "()" if empty, otherwise returns the contents of this *LRStruct
enclosed in parentheses. */ public String toString() { return _head.toString(this); } /** * Inserts dat to the front of this LRStruct. * post condition:getFirst()
now returns dat. * @param dat data to be inserted. * @return thisLRStruct
*/ public final LRStruct insertFront(Object dat) { return _head.insertFront(this, dat); } /** * Removes and returns thisLRStruct
's first. */ public final Object removeFront() { return _head.removeFront(this); } /** * Gets the first data element from thisLRStruct
*/ public final Object getFirst() { return _head.getFirst (this); } /** * Sets first data element to a new value. * @param dat replaces the existing first for thisLRStruct
. * @throws NoSuchElementException if thisLRStruct
is empty. * @return thisLRStruct
*/ public final LRStruct setFirst(Object dat) { return _head.setFirst (this, dat); } /** * Gets the rest of thisLRStruct
. * @throws NoSuchElementException if thisLRStruct
is empty. */ public final LRStruct getRest() { return _head.getRest(this); } /** * Sets a new tail for thisLRStruct
. * post condition:getRest()
now returns tail. * @throws NoSuchElementException if thisLRStruct
is empty. * @return thisLRStruct
*/ public final LRStruct setRest(LRStruct tail) { return _head.setRest(this, tail); } /** * Hook method to execute an algorithm with a given input and return * an appropriate output object. * @param algo an algorithm (!= null) that operates on this LRStruct. * @param inp input object needed by visitor algo. * @return output object resulting from the execution of algo. */ public final Object execute(IAlgo algo, Object... inp) { return _head.execute(this, algo, inp); } /* Package access only: */ /** * Initializes thisLRStruct
with a given head node. * @param node != null. */ LRStruct(ANode node) { _head = node; } /** * Changes the head node (i.e. state) of thisLRStruct
. * @param head replaces the existing state of thisLRStruct
. * @return thisLRStruct
*/ final LRStruct setHead (ANode head) { _head = head; return this; } /** * Gets the head node (i.e. state) of thisLRStruct
. * @return the head node. */ final ANode getHead () { return _head; } }
Code |
Illustration |
class EmptyNode extends ANode { /** * The owner becomes non-empty and * has dat as its first element. */ LRStruct insertFront(LRStruct owner, Object dat) { return owner.setHead(new NENode(dat, new LRStruct(this))); } |
|
class NENode extends ANode { private Object _dat; private LRStruct _tail; /** * Initializes this NENode to contain dat and a given tail list. * @param dat the data object to be stored in this NENode. * @param tail the LRStruct tail of this NENode. */ NENode(Object dat, LRStruct tail) { _dat = dat; _tail = tail; } /** * Inserts a data object at the front of the LRStruct owner. * @param dat the object to be inserted at the front. * @param owner the LRS referencing this NENode. */ LRStruct insertFront(LRStruct owner, Object dat, ) { return owner.setHead(new NENode(dat, new LRStruct(this))); /* Details: LRStruct coOwner = new LRStruct (this); NENode newNode = new NENode (dat, coOwner); return owner.setHead (newNode); "old" style: owner._head = newNode - cannot be done here. */ } } |
|
Comment 1: Proper initialization of an object is crucial
in program correctness. The call However, it is a good programming practice to have an object
completely initialized when it is defined, and have all initialization
code done in one place.
|
|
Comment 2: We intentionally make the code for insertFront(...)
for both EmptyNode and NENode look identical. Doing so would make the abstract class ANode "aware" of a specific concrete variant, NENode, and prevent us from hiding (and perhaps changing) the details of implementation from external client code, and thus violating the principle of information hiding. As a general OO programming principle, never make a super class aware
of any of its subclasses.
|
|
class NENode extends ANode { Object removeFront(LRStruct owner) { owner.setHead(_tail.getHead()); // owner._head = _tail._head return _dat; } // other methods elided... } |
|
The above illustrations are combined into a series of object diagrams shown below. In UML, an object diagram is used to show a snapshot of an instance of a class.
Algorithms on LRStruct are written as IAlgo visitors. LRStruct overrides the toString() method by delegating its state, an ANode, to perform the task. The abstract class ANode has a concrete method toString(LRStruct owner) that makes use of an anonymous IAlgo inner class which in turns calls on another anonymous IAlgo inner class!
The use of anonymous inner classes here allows us to program a concrete method for ANode without referring to any concrete named implementation of IAlgo. This is crucial in keeping ANode independent of any concrete implementations.
abstract class ANode { /** * Uses anonymous visitor class to compute a String representation. */ String toString(LRStruct owner) { return (String)owner.execute (new IAlgo() { public Object emptyCase(LRStruct host, Object... nu) { return "()"; } public Object nonEmptyCase(LRStruct host, Object... nu) { return "(" + host.getFirst() + host.getRest().execute(new IAlgo() { public Object emptyCase(LRStruct h, Object... nu) { return ")"; } public Object nonEmptyCase(LRStruct h, Object... nu) { return " " + h.getFirst() + h.getRest().execute (this); } }); } }); } // Other methods elided... }
Exercise: Write an algorithm to remove the last element from an LRStruct. Throw an exception if the LRStruct is empty.