...
The Homework Support files IntList.java,
IntListVisitor.java
, LengthVisitor
, ScalarProductVisitor
, and IntListTest.java
provide a starting point for your code. Feel free to edit these files and omit files that are not needed in this homework assignment.
Problems
Apply the interpreter visitor design pattern to to define visitor classes implementing the IntListVistor
interface IntList
and its subclasses given above to write formulate all of the following methods as augmentations (added code) of the IntList
class. Also write a JUnit as visitorsJUnit test class, IntListTest
to test all of your new methods in the IntList
class. We strongly recommend that you write Template Instantiations for all of these new methods as an intermediate step in developing your code BUT DO NOT submit these Template Instantiations (or corresponding Templates) as part of your code documentation. The structure of your program implicitly provides this information Use the LengthVisitor example as a guide for defining your new visitor classes. Augment the test clas IntListTest.java
to include test methods for each of your visitor classes. Confine your documentation to writing contracts (purpose statements in HTDP terminology) for each visitor using javadoc
notation (opening the purpose statement (a comment preceding the corresponding definition) beginning with /**
and closing it closing with */
for each visitor class. Use the documentation of LengthVisitor
in the Homework Support files as an example.
- (10 pts.)
boolean contains(int key)
: returnstrue
ifkey
is in the list,false
otherwise. Name you visitor classContainsVisitor
.) - (10 pts.)
int lengthreverse()
constructs a list that is the reversal of this. Name your visitor classReverseVisitor
. : computes the length of the list Hint: this computation is faster and simpler if you introduce a help "method" that takes an argument (also a visitor). - (10 pts.)
int sum()
: computes the sum of the elements in the list. Name your visitor class SumVisitor. - (10 pts.)
double average()
: computes computes the average of the elements in the list; returns0
if the list is empty.
Name your visitor classAverageVisitor
. Hint: you can cast anint
todouble
by using the prefix casting operator(double)
. - (10 pts.)
IntList notGreaterThan(int bound)
: returns returns a list of elements in this list that are less than or equal tobound
. Name your visitor classNotGreaterThanVisitor
. - (10 pts.)
IntList remove(int key)
: returns returns a list of all elements in this list that are not equal tokey
. .Name your visitor class RemoveVisitor - (10 pts.)
IntList subst(int oldN, int newN)
: returns a list of all elements in this list witholdN
replaced bynewN
. .Name your visitor class SubstVisitor - (30 15 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.
Name your visitor classMergeVisitor
. Hint: add a method "method"mergeHelp(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.
The above implementation is an example of what is called the Composite Design Pattern. The composite design pattern is a special case of the union pattern where one or more of the variants for the union type T contains fields of root type T. In this pattern, the union is called a composite. Here the union type is IntList
and the variant ConsIntList
is said to be a composite because it includes a field of type IntList
.
The composite pattern also prescribes a coding pattern for the its methods: when a variant is called to perform an operation, it traverses its fields of root type and calls on them to perform the same operation. It allows a client to treat an instance of type T and it embedded instances uniformly using polymorphism.
This coding pattern is called the interpreter design pattern: it interprets the abstract behavior of a class in each of its concrete subclasses. The composite pattern refers to the the structure of the composite type hierarchy, while the interpreter pattern refers to how the behavior of the variants of the type are defined uniformly via polymorphism.
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 Racket 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 Racket 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);
}
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 given above to write all of the following methods as augmentations (added code) of the IntList
class. Also write a JUnit test class, IntListTest
to test all of your new methods in the IntList
class. We strongly recommend that you write Template Instantiations for all of these new methods as an intermediate step in developing your code BUT DO NOT submit these Template Instantiations (or corresponding Templates) as part of your code documentation. The structure of your program implicitly provides this information. Confine your documentation to writing contracts (purpose statements in HTDP terminology) using javadoc notation (opening the purpose statement (preceding the corresponding definition)with /** and closing it with */.
...
- You can formulate help methods as visitors.
- (15 pts.)
IntList mergeSort()
. Leveraging themerge
"method" you just wrote (as a visitor), writemergeSort()
that sorts anIntList.
Recall that you need to write a help function that splits a list approximately in two.
Testing Tricks
In Racket, the equal?
function performs structural equality. Java does not include such a built-in operation. For the IntList
composite type, we overrode the inherited equals
method (trivially defined in class Object
) by an equals method that implements structural equality but it is slightly more complex than you might expect. Recall that the argument passed to equal
has type Object
. Hence, we have to worry about the class of the argument; the simple (and IMO best) definition of structural equality is to mandate that objects cannot be equal unless they are instances of the same class. Study the definition of the equals
method in class ConsIntList
. Unfortunately, we can write the body of this method the return
of a boolean-valued expression, because Java does not support a notion of local
or let
at the level of expressions. So the body is an if
statement where explicit return
statements in the consequent statement and alternative statement. Notice that we still programmed in a functional style without any mutation.
To test the computations that yield results of composite type, we can either define structural equality over the composite type (as we did for IntList
) or write an intelligible toString method for the composite type (which I strongly recommend for debugging purposes) and compare the toString()
representations of the composite type. But beware that toString()
equality may not imply structural equality and vice versa. You should always endeavor to make them agree.
...