Today's menu:
By now, you must have the specification of the immutable list framework committed to memory. Here is again the UML class diagram of the immutable list framework.
The above framework dictates the design of all algorithms operating on the list structure:
All algorithms must be some concrete implementation of IListAlgo.
Algorithms that require the construction of empty and/or non-empty lists, must do so via some abstract list factory, IListFactory.
In order to apply an algorithm to a list, one must ask a list to "execute" that algorithm, giving it the required input parameter.
We do not know anything about how the above list framework is implemented, yet we have been able to write quite a few algorithms and test them for correctness. Click here to see a list of algorithms done in the lectures and in the labs. In order to obtain concrete lists and test an algorithm, we call on a concrete IL:istFactory, called CompositeListFactory, to manufacture empty and non-empty lists. We do not know how this factory creates those list objects, but we trust that it does the right thing and produces the appropriate list objects for us to use. And so far, it seems like it's doing its job, giving us all the lists we need. We now study how CompositeListFactory makes IEmptyList and INEList objects.
IEmptyList only has one method:
Object execute(IListAlgo algo, Object inp),
whose purpose is to perform the algorithm represented by the IListAlgo parameter, algo, with a given input Object represented by the parameter inp, and return the result.
To implement IEmptyList, we need to define a concrete class, call EmptyList, that has concrete code for the execute method. IListAlgo has two methods:
Object emptyCase(IEmptyList host, Object inp) : to operate on IEmptyList only, and
Object nonEmptyCase(INEList algo, Object inp) : to operate on INEList objects only.
What is the only logical thing for EmptyList to do when executing an IListAlgo? Call on IListAlgo.emptyCase, passing itself as the host parameter. Below is the code for EmptyList. Since it suffices to have exactly one instance of the empty list, we apply the Singleton pattern to EmptyList.
import listFW.*;
/**
* Concrete implementation of the empty list interface, IEmptyList.
* Provides concrete code for the execute method: simply calls the emptyCase
* method of the IListAlgo parameter, passing to this method itself as the host
* and the given input Object as the input.
* @author Dung X. Nguyen
* @since Copyright 2002 by DXN - All rights reserved
*/
public class EmptyList implements IEmptyList {
/**
* Singleton Design Pattern.
*/
public static final EmptyList Singleton = new EmptyList();
private EmptyList() {
}
/**
* Calls the empty case of the algorithm algo, passing to it itself as
* the host parameter and the given input inp as the input parameter.
* This method is marked as final to prevent all subclasses from
* overriding it. Finalizing a method also allows the compiler to generate
* more efficient calling code.
*/
final public Object execute(IListAlgo algo, Object inp) {
return algo.emptyCase(this, inp);
}
}
To implement INEList, we need to define a concrete class, call NEList, that has concrete code for the following three methods:
Object getFirst()
IList getRest() , and
Object execute(IListAlgo algo, Object inp)
How can NEList return its first element? The obvious thing to do is to have NEList hold an Object as its first element and return that Object when getFirst is called.
How can NEList return its rest? The obvious thing to do is to have NEList hold an IList as its rest and return that IList when getRest is called. Designed as such, NEList now contains a subcomponent rest that is of the same type (isomorphic) as itself. We call NEList a composite.
When we create an NEList, we must provide a first element and a rest IList. This requires a constructor that takes in as input parameters an Object for the first element and an IList for the rest.
NEList (Object first, IList rest)
What is the only logical thing for INEList to do when executing an IListAlgo? Call on IListAlgo.nonEmptyCase, passing itself as the host parameter.
Below is the code for INEList.
import listFW.*; /** * Concrete implementation of the non-empty list interface, INEList. * Contains two pieces of data:
first: an Object representing the first data element
rest: an IList object representing the rest of this non-emptylist.
* When a class contains other objects that are isomorphic to itself, * this class is called a composite. * Provides concrete code for
a constructor to initialize this NEList to a given first and rest.
the getFirst method: simply returns the
the execute method: simply calls the nonEmptyCase method of the IListAlgo parameter, passing to this method itself as the host and the given input Object as the input.
* @author Dung X. Nguyen
* @since Copyright 2002 by DXN - All rights reserved
*/
public class NEList implements INEList {
/**
* The first data element of this NEList.
*/
private Object _first;
/**
* The rest or "tail" of this NEList.
* Data Invariant: _rest != null;
*/
private IList _rest;
/**
* Initializes this NEList to a given first and rest.
* @param first the first data element of this NEList.
* @param tail != null, the rest of this NEList.
*/
public NEList(Object first, IList tail) {
_first = first;
_rest = tail;
}
/**
* Returns the first data element of this NEList.
* This method is marked as final to prevent all subclasses from
* overriding it. Finalizing a method also allows the compiler to generate
* more efficient calling code.
*/
final public Object getFirst() {
return _first;
}
/**
* Returns the rest of this NEList.
* This method is marked as final to prevent all subclasses from
* overriding it. Finalizing a method also allows the compiler to generate
* more efficient calling code.
*/
final public IList getRest() {
return _rest;
}
/**
* Calls the nonEmptyCase method of the IListAlgo parameter, passing to this
* method itself as the host parameter and the given input as the input
* parameter.
* This method is marked as final to prevent all subclasses from
* overriding it. Finalizing a method also allows the compiler to generate
* more efficient calling code.
*/
final public Object execute(IListAlgo algo, Object inp) {
return algo.nonEmptyCase(this, inp);
}
}
Below is the UML class diagram for EmptyList and NEList.
EmptyList and NEList are concrete implementations of IEmptyList and INEList respectively. An NEList object "has a" an element, called rest, whose structure is isomorphic to the enclosing NEList object itself.. NEList is said to be a composite. Its structure is recursively constructed and terminates with the "base case", the EmptyList. This is an example of what is called the Composite Design Pattern.
The composite pattern is a structural pattern that prescribes how to build a container object that is composed of other objects whose structure is isomorphic to that of the container itself. In this pattern, the container is called a composite. The composite pattern also prescribes a coding pattern for the container's methods: when a container is called to perform an operation, it traverses through its list of composed objects and call on them to perform the same operation. It allows the client to treat the container and what it contains uniformly by making use of polymorphism. The following UML diagram illustrates the general composite pattern.
In the above, note how the parameters of the anonymous inner class are renamed in order to avoid masking the parameter names in the outer object.
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 implemented so far has failed to hide EmptyList and NEList, which are concrete implementations of IList, the abstract specification of the list structure. Any list algorithms that needs the constructions of empty lists and non-empty can call directly EmptyList.Singleton or the constructor of NEList to instantiate concrete IList objects. In doing so, the algorithm is tied to a very specific implementation of IList and loses its interoperability and interchangeability properties. How can we hide the specific implementation details from all external code? This is where the concept of abstract factory comes in.
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. In our list framework, the abstract factory is specified by the interface IListFactory. To hide EmptyList and NEList from all external code, we define them as private and static classes nested inside of a concrete class, called CompositeListFactory, that implements IListFactory. By making EmptyList and NEList private, we complete shield them from all external code. By making them static, we are making them globally accessible to all instances of CompositeListFactory. The factory method makeEmptyList simply calls EmptyList.Singleton, while makeNEList makes sure that the parameter for rest is not null before calling the constructor for NEList.
Below is the code for CompositeListFacory.
package listFW.factory;
import listFW.*;
/**
* Manufactures concrete IEmptyList and INEList objects. Has only one
* instance referenced by CompositeListFactory.Singleton.
* @author Dung X. Nguyen
* @since Copyright 2002 by DXN - All rights reserved
*/
public class CompositeListFactory implements IListFactory {
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);
}
}
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);
}
}