As in the case of writing helper methods to "help" a "master" method complete a task, we write helper visitors to help a master visitor. For example, the toString() and toStringHelp() methods for a list can be translated directly into their corresponding ToString and ToStringHelp visitors. When we need to make use of an accumulator, we pass the accumulator as the input Object to the helper visitor, as illustrated by the GetMin and GetMinHelp visitors shown in lecture #08.
Sometimes, the helper can turn around and ask the "master" to help finish the job resulting in a mutually recursive algorithm as illustrated by the following exercise.
Exercise: Write a visitor called EvenIndexed for IList to extract the even indexed elements of the IList host. The first element of a non-empty list has index 0. For example, the even-indexed elements of the list (x y z) is (x z). What is the list consisting of the even-indexed elements for the empty list?
Solution: Click here for the solution.
As you can see from the above exercise, the code for the visitors of IList may invoke the concrete EmptyList and NEList classes. What this means is that with the current formulation of the list, we cannot always program to the interfaces I:List, IEmptyList, and INEList. In many cases the code is tied to a specific implementation of IList and as a result, is not applicable to any other legitimate IList implementation. The current formulation of IList violates a key software engineering principle called "information hiding".
Information hiding is a tried-and-true design principle that advocates hiding all implementation details of software components from the user in order to facilitate code maintenance. It was first formulated by David L. Parnas (in 1971-1972) as follows.
By adhering to the above, code written by both users and implementors will have a high degree of flexibility, extensibility, interoperability and interchangeability.
The list framework that we have developed so far has failed to hide EmptyList and NEList, which are concrete implementations of IList, the abstract specification of the list structure. In many of the list algorithms that we have developed so far, we need to call on EmptyList.Singleton or the constructor of NEList to instantiate concrete IList objects. The following is another such examples.
import OOscheme.*;
/**
* Inserts an Integer into an ordered host list, assuming the host list contains
* only Integer objects.
*/
public class InsertInOrder implements IListAlgo {
public static final InsertInOrder Singleton = new InsertInOrder();
private InsertInOrder() {
}
/**
* This is easy, don't you think?
* @param inp inp[0] is an Integer to be inserted in order into host.
*/
public Object emptyCase(IEmptyList host, Object... inp) {
return new NEList(inp[0], host);
}
/**
* Delegate (to recur)!
* @param inp inp[0] is an Integer to be inserted in order into host.
*/
public Object nonEmptyCase(INEList host, Object... inp) {
int n = (Integer)inp[0];
int f = (Integer)host.getFirst();
return n < f ?
new NEList(inp[0], host):
new NEList(host.getFirst(), (IList)host.getRest().execute(this, inp));
}
}
The above algorithm to insert in order an integer into an ordered list of integers can only be used for a very specific implementation of IList, namely the one that has EmptyList and NEList as concrete subclasses. How can we write list algorithms that can be used for ANY implementation of the abstract specification of the list structure represented by the abstract class IList? We can achieve our goal by applying the Abstract Factory Design Pattern to hide the concrete implementation from the user.
Before we describe in general what the Abstract Factory Pattern is, let's examine what we have to do in the case of IList.
package listFW;
/**
* Abstract factory to manufacture IEmptyList and INEList.
*/
public interface IListFactory {
/**
* Creates an empty list.
* @return an IEmptyList object.
*/
public abstract IEmptyList makeEmptyList();
/**
* Creates a non-empty list containing a given first and a given rest.
* @param first a data object.
* @param tail != null, the rest of the non-empty list to be manufactured.
* @return an INEList object containing first and tail
* @exception IllegalArgumentException if tail is null.
*/
public abstract INEList makeNEList(Object first, IList tail);
}
IList, IListAlgo, and IListFactory prescribe a minimal and complete abstract specification of what we call a list software component. We claim without proof that we can do anything with the list structure using this specification.
import listFW.*;
/**
* Inserts an Integer into an ordered host list, assuming the host list contains
* only Integer objects. Has no knowledge of how IList is implemented. Must
* make use of a list factory (IListFactory) to create IList objects instead of
* calling the constructors of concrete subclasses directly.
*/
public class InsertInOrderWithFactory implements IListAlgo {
private IListFactory _listFact;
public InsertInOrderWithFactory(IListFactory lf) {
_listFact = lf;
}
/**
* Simply makes a new non-empty list with the given inp parameter as first.
* @param host an empty IList.
* @param inp inp[0] is an Integer to be inserted in order into host.
*/
public Object emptyCase(IEmptyList host, Object... inp) {
return _listFact.makeNEList(inp[0], host);
}
/**
* Recur!
* @param host a non-empty IList.
* @param inp inp[0] is an Integer to be inserted in order into host.
*/
public Object nonEmptyCase(INEList host, Object... inp) {
int n = (Integer)inp[0];
int f = (Integer)host.getFirst();
return n < f ?
_listFact.makeNEList(inp[0], host):
_listFact.makeNEList(host.getFirst(),
(IList)host.getRest().execute(this, inp));
}
}
The above algorithm only "talks" to the list structure it operates on at the highest level of abstraction specified by IList and IListFactory. It does know and does not care how IList and IListFactory are implemented. Yet it can be proved to be correct. This algorithm can be plugged into any system that subscribes to the abstract specification prescribed by IList, IListAlgo, and IListFactory.
package listFW.factory;
import listFW.*;
/**
* Manufactures concrete IEmptyList and INEList objects. Has only one
* instance referenced by CompositeListFactory.Singleton<.
* EmptyList and NEList are static nested classes and hidden from all external
* client code. The implementations for EmptyList and NEList are the same as
* before but completely invisible to the outside of this factory.
*/
public class CompositeListFactory implements IListFactory {
/**
* Note the use of private static.
*/
private static class EmptyList implements IEmptyList {
public final static EmptyList Singleton = new EmptyList ();
private EmptyList() {
}
final public Object execute(IListAlgo algo, Object... inp) {
return algo.emptyCase(this, inp);
}
}
/**
* Note the use of private static.
*/
private static class NEList implements INEList {
private Object _first;
private IList _rest;
public NEList(Object dat, IList tail) {
_first = dat;
_rest = tail;
}
final public Object getFirst() {
return _first;
}
final public IList getRest() {
return _rest;
}
final public Object execute(IListAlgo algo, Object... inp) {
return algo.nonEmptyCase(this, inp);
}
}
/**
* The unique instance of this class.
*/
public static final CompositeListFactory Singleton
= new CompositeListFactory();
private CompositeListFactory() {
}
/**
* Creates an empty list.
* @return an IEmptyList object.
*/
public IEmptyList makeEmptyList() {
return EmptyList.Singleton;
}
/**
* Creates a non-empty list containing a given first and a given rest.
* @param first a data object.
* @param tail != null, the rest of the non-empty list to be manufactured.
* @return an INEList object containing first and tail
* @exception IllegalArgumentException if tail == null.
*/
public INEList makeNEList(Object first, IList tail) {
if (null == tail) {
throw new IllegalArgumentException("rest is null!");
}
return new NEList(first, tail);
}
}
Below is an example of a client that uses the InsertInOrderWithFactory algorithm.
import listFW.*;
import listFW.factory.*;
/**
* Client for testing IList, IEmptyList, INEList, IListAlgo, IListFactory,
* and InsertInOrderWithFactory.
*/
public class ListClient {
/**
* Creates an empty list and inserts a few integers in order.
*/
public void run(IListFactory listFac) {
IListAlgo algo = new InsertInOrderWithFactory(listFac);
IList e0 = listFac.makeEmptyList();
IList e1 = (IList)e0.execute(algo, 55);
IList e2 = (IList)e1.execute(algo, 30);
System.out.println(e2);
IList e3 = (IList)e1.execute(algo, 100);
System.out.println(e3);
IList e4 = (IList)e2.execute(algo, 45);
IList e5 = (IList)e4.execute(algo, 60);
System.out.println(e5);
}
/**
* Main entry point to test program.
* @param nu not used. May be used in future versions to pass in the name
* of a concrete IListFactory. We can then call on Java's dynamic class
* loading mechanism to instantiate the concrete factory and pass it to the
* run() method.
*/
public static void main(String[] nu) {
new ListClient().run(CompositeListFactory.Singleton);
}
}
The above design process is an example of what is called the Abstract Factory Design Pattern. The intent of this pattern is to provide an abstract specification for manufacturing a family of related objects (for examples, the empty and non-empty IList) without specifying their actual concrete classes thus hiding all details of implementation from the user.
Our example of the list structure framework successfully delineates specification from implementation and faithfully adheres to the principle of information hiding.
The files for the list framework are available in the data structures directory.
dxnguyen at rice edu Copyright 2005, Dung X. Nguyen - All rights reserved.