Homework 07 (Due
...
10:00am Friday,
...
March 12,
...
2010)
Submit via Owl-Space
Preliminaries
...
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.
Code Block |
---|
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) ...
}
}
|
...
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.
- (10 pts.)
boolean contains(int key)
: returns true if key is in the list, false otherwise. - (10 pts.)
int length()
: computes the length of the list. - (10 pts.)
int sum()
: computes the sum of the elements in the list. - (10 pts.)
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 anint
todouble
by using the prefix operator(double)
. At the Elementary level, casts are illegal, but you can use the workaround of adding0.
to anint
to convert it todouble
. - (10 pts.)
IntList notGreaterThan(int bound)
: returns a list of elements in this list that are less or equal tobound
. - (10 pts.)
IntList remove(int key)
: returns a list of all elements in this list that are not equal tokey
. - (10 pts.)
IntList subst(int oldN, int newN)
: returns a list of all elements in this list witholdN
replaced bynewN
. - (30 pts.)
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 methodmergeHelp(ConsIntList other)
that does all of the work if one list is non-empty (aConsIntList
). OnlymergeHelp
is recursive. Use dynamic dispatch on the list that may be empty. Recall thata.merge(b)
is equivalent tob.merge(a)
. This approach is the Java analog of the extra credit option in HTDP Problem 17.6.1 in HW 3.