Date: Thu, 28 Mar 2024 09:48:19 -0500 (CDT) Message-ID: <1964192146.962.1711637299570@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_961_2110952122.1711637299569" ------=_Part_961_2110952122.1711637299569 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Submit via Owl-Space
This homework should be done using the Functional language level of DrJa= va.
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 <=
code>int and rest
is an IntList
, is an The above can be implemented in Java as follows.
/** Abs= tract list structure. IntList :=3D EmptyIntList + ConsIntList(int, IntList= ) */ abstract class IntList { } /** Concrete empty list structure containing nothing. */ class EmptyIntList extends IntList { } /** Concrete non-empty list structure containing an int, called first, and = an IntList called rest. */ class ConsIntList extends IntList { int first; IntList rest; }
The above implementation is an example of what is called the Com=
posite Design Pattern. The composite design pattern is a special c=
ase of the union pattern where one or more of the variants for the union ty=
pe 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 IntList
.
The composite pattern also prescribes a coding pattern for the its metho= ds: when a variant is called to perform an operation, it traverses its fiel= ds 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 interpr= ets the abstract behavior of a class in each of its concrete subclasses. Th= e composite pattern refers to the the structure of the composite type hiera= rchy, while the interpreter pattern refers to how the behavior of the varia= nts of the type are defined uniformly via polymorphism.
The interpreter design pattern applied to the above composite list struc=
ture prescribes a coding pattern for list operations that is analogous to S=
cheme function template. It entails declaring an abstract method for each l=
ist operation in the abstract list class, IntList
, and definin=
g corresponding concrete methods in the concrete list subclasses: the empty=
list class, EmptyIntList
, and the non-empty class, Cons=
IntList
. The concrete method for EmptyIntList
correspon=
ds to the base case in the Scheme function template while the concrete meth=
od in ConstIntList
corresponds to the recursive case by callin=
g the same method on its rest.
The following is the coding template for the interpreter design pattern =
for IntList
and its subclasses.
abstrac= t 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) ... } }
Apply the interpreter design pattern to IntList
and its sub=
classes to write the following methods. Also write a JUnit test class to te=
st all methods in EmptyIntList
and a different JUnit test clas=
s to test all methods in ConsIntList
. We strongly recommend t=
hat 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 y=
our documentation to writing contracts (purpose statements in HTDP terminol=
ogy) using javadoc notation. The javadoc documentation style will be discus=
sed 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.<=
/li>
int sum()
: computes the sum of the elements in =
the list.double average()
: computes the average of the e=
lements in the list; returns 0 if the list is empty.int
to double
by usi=
ng the prefix operator (double)
.IntList notGreaterThan(int bound)
: returns a li=
st of elements in this list that are less or equal to bound
.<=
/li>
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 li=
st of all elements in this list with oldN
replaced by ne=
wN
.IntList merge(IntList other)
merges this list wi=
th the input list other, assuming that this list and other are sorted in as=
cending order. Note that the lists need not have the same length.mergeHelp(ConsIntList other)
tha=
t does all of the work if one list is non-empty (a ConsIntList
=
). Only mergeHelp
is recursive. Use dynamic dispatch on the li=
st that may be empty. Recall that a.merge(b)
is equivalent to =
b.merge(a)
. This approach is the Java analog of the extra cre=
dit option in HTDP Problem 17.6.1 in HW 3.