Homework 07 (Due 11:00am Friday, Feb 27, 2009)

Submit via Owl-Space

Preliminaries

This homework can be done using either the Elementary or Intermediate language level of DrJava^?. If you are comfortable with casting between primitive types, the Intermediate level is probably a better choice because it supports such casting operations. You can test these operations in the Interactions pane, which supports the full Java language regardless of what language level is selected.

Download and extract the attached file (shapes.zip or shapes1.zip) into the same subdirectory. The files are available in Elementary and Intermediate form. It contains the following files:

Shape.dj0/dj1
Rectangle.dj0/dj1
Circle.dj0/dj1
TestRectangle.dj0/dj1
TestCircle.dj0/dj1

Use DrJava to open all these files and perform a Compile All (by clicking the Compile button). Click the Test button to run the two JUnit test files. Everything should compile and pass all the JUnit tests. Use these files as examples for documentation, coding style and JUnit testing.

Composite Design Pattern for List

The following is an object-oriented formulation of lists of integers.

IntList is an abstract list of int.
EmptyIntList is an IntList
ConsIntList(first, rest), where first is an int and rest is an IntList, is an IntList.

The above can be implemented in Java as follows.

/** Abstract list structure. */
abstract class IntList {
}
 
/** Concrete empty list structure containing nothing. */
class EmptyIntList extends IntList {
}
 
/** Concrete non-empty list structure containing an int, called first,
  * and a rest, which is a list structure.
  */
class ConsIntList extends IntList {
    int first;
    IntList rest;
}

The above implementation is an example of what is called the Composite Design Pattern. The composite design 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. Here the container object is the list and ConsIntList is said to be a composite: it is a list and is composed of a substructure that is itself a list.

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.

This coding pattern is called the interpreter design pattern: we are interpreting the abstract behavior of a class in each of the concrete subclasses. 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.

Interpreter Design Pattern for List

The interpreter design pattern applied to the above composite list structure prescribes a coding pattern for list operations that is analogous to Scheme function template. It entails declaring an abstract method for each list operation in the abstract list class, IntList, and defining corresponding concrete methods in the concrete list subclasses: the empty list class, EmptyIntList, and the non-empty class, ConsIntList. The concrete method for EmptyIntList corresponds to the base case in the Scheme function template while the concrete method in ConstIntList corresponds to the recursive case by calling the same method on its rest. The following is the coding template for the interpreter design pattern for IntList and its subclasses.

abstract class IntList {
    abstract returnType methodName(parameter_list); // returnType may be void
}
 
class EmptyIntList extends IntList {
    returnType methodName(parameter_list) {
        // base case code
    }
}
 
class ConsIntList extends IntList {
    int first;
    IntList rest;
    returnType methodName(parameter_list) {
        // ... first ...
        // ... rest.methodName(parameter_list) ...
    }
 
}

Problems

Apply the interpreter design pattern to IntList and its subclasses to write the following methods. Also write a JUnit test class to test all methods in EmptyIntList and a different JUnit test class to test all methods in ConsIntList. We strongly recommend that you write Template Instantiations as an intermediate step in developing your code BUT DO NOT submit these Template Instantiations (or corresponding Templates) as part of your code documentation. Confine your documentation to writing contracts (purpose statements in HTDP terminology) using javadoc notation. The javadoc documentation style will be discussed in the upcoming lab.

boolean contains(int key): returns true if key is in the list, false otherwise.
int length(): computes the length of the list.
int sum(): computes the sum of the elements in the list.
double average(): computes the average of the elements in the list; returns 0 if the list is empty. Hint: at the Intermediate level you can cast an int to double by using the prefix operator (double). At the Elementary level, casts are illegal, but you can use the workaround of adding 0. to an int to convert it to double.
IntList notGreaterThan(int bound): returns a list of elements in this list that are less or equal to bound.
IntList remove(int key): returns a list of all elements in this list that are not equal to key.
IntList subst(int oldN, int newN): returns a list of all elements in this list with oldN replaced by newN.
IntList merge(IntList^? other) merges this list with the input list other, assuming that this list and other are sorted in ascending order. Note that the lists need not have the same length. Hint: add a method mergeHelp(ConsIntList^? other) that does all of the work if one lists is non-empty (a ConsIntList). Only mergeHelp is recursive. Use dynamic dispatch on the list that may be empty. Recall that a.merge(b) is equivalent to b.merge(a). This approach is the Java analog of the extra credit option in HTDP Problem 17.6.1 in HW 3.