| << Chapter < Page | Chapter >> Page > |
In the previous lecture, we define what a list is and implement it using the composite design pattern. This list structure is fully encapsulated and does not expose any of its internal components. In order to manipulate such a list without having to make public its internals, we need to add methods to the structure. This lecture discusses the structure of the algorithms on the list.
Suppose we are given a list L and asked to find out how many elements it has. What should we do? The temptation here is to start thinking about "traversing" the list and keep a count as we go along, and when we encounter the "end" of the list, the count should be the number of elements in the list. But how do we know that that's the right answer? In order to determine whether or not the result obtained by counting as one traverses the list from beginning to end is correct, we have to define what it means to be the number of elements in the list. The number of elements in a list is an abstract notion, isn't it? In order to define such a quantity, we need to go back to the definition of what a list is.
To define the notion of the number of elements in a list, we need to define what we mean by the number of elements in an empty list and what we mean by the number of elements in a non-empty list.
The definition of the number of elements in a list is thus recursive. The recursive characteristic of this definition arises naturally from the recursive characteristic of the list structure. What ever approach we use to compute the number of elements in a list, in order to prove correctness, we must show that the result satisfies the above definition.
Here is the code for the above computation.
package listFW;
/*** Represents the abstract list structure.
*/public interface IList {
/*** Abstract notion of the number of elements in this IList.
*/public int getLength();
} |
package listFW;
/*** Represents empty lists.
*/public class MTList implements IList {
/*** The number of elements in an
* empty list is zero.*/
public int getLength() {return 0;
}} |
package listFW;
/*** Represents non-empty lists.
*/public class NEList implements IList {
private Object _first;private IList _rest;
// Constructor ommitted./**
* The number of elements in a non-empty* list is the number of elements of its
* rest plus 1.*/
public int getLength() {return 1 + _rest.getLength();
}} |
The above coding pattern is an example of what is called the interpreter design pattern : we are interpreting the abstract behavior of a class (or interface) in each of the concrete subclasses (or implementations). The composite pattern is a pattern to express the structure of a system, while the interpreter pattern is used to express the behaviors (i.e. methods) of the system. The interpreter pattern is usually applied to coding methods in a composite structure. In a later lecture, we shall see another way of expressing the behavior of a composite structure without having to add new methods and interpret them.
Whenever we want the IList to perform a task, we add a method to IList and write appropriate concrete implementations in MTList and NEList. The following table illustrates the code template for writing the concrete code in MTList and NEList.
interface IList | |
public abstract returnType methodName(param list);
// returnType may be 'void' | |
MTList
// no data |
NEList
Object _first;IList _rest; |
public returnType methodName(param list) {
/*This is in general the base case of a
recursive call. Write the (non-recursive)code to solve the problem.
*/} |
public returnType methodName(param list) {
/*This is in general a recursive method.
The code here can refer to _first and_rest, and all the methods in NEList
When referencing _rest, one usually makesthe recursive call:
_rest.methodName(appropriate parameters).*/
} |
Notification Switch
Would you like to follow the 'Design patterns' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|