Comp 212 Assignment #2
Recursive Immutable Structures
Due 10:00 AM, Monday, February 04,
2002 -
No Late Submission will be accepted
This homework exercise serves as a transition from functional programming to
object-oriented programming. It is based on the immutable list example
discussed in class and in lab 03.
I. Scheme List
You are given the following object model for a Scheme-like immutable list structure.
Your task is to add the public methods to these classes as specified in the following
problems. You are free to add any private and protected methods to your classes to
support your public operations. You are not allowed to check for the type of AList, such as using instanceof
or add a method to check for the type, to perform any task. The classes AList, EmptyList, NEList should be in a package named scheme as
shown in lab 03.
- Modify the toString() method that returns
a String representation of AList
with matching parentheses as in Scheme.
For example, toString() for the list
containing 1, 2 ,3, should return (1 2 3),
and toString() for the empty list should
return (). 5 points
-
Write a test class. 5 pts
Add the method public AList reverse()
to class AList
and appropriate methods to the supporting classes to
compute and return the receiver in reverse order. 5 pts
-
Write a test class. 5 pts.
Add the method public AList makeClone() to
class AList
and appropriate methods to the supporting classes to compute and
return a copy of the receiver. 5 pts
- Write a test class. 5 pts.
Add the method public Object getNth(int n) to
class AList
and appropriate methods to the supporting classes to compute and
return the n-th elements of the receiver. Here 0 <= n, and the case n equals
0 corresponds to the first element of the list.
5 pts
- Write a test class. 5 pts.
Add the method public Object lastElement()
to class AList
and appropriate methods to the supporting classes to
find and return the last element of the receiver. Do this without
computing the length
of the receiver. 5 pts
- Write a test class. 5 pts.
Add the method public AList firstNElements(int n)
to class AList and appropriate methods to the supporting classes to compute
and return an AList that contains the first n elements of the receiver. Here 0
<= n, and the case n equals 0 corresponds to the empty list. 5 pts
- Write a test class. 5 pts.
Add the method public AList concatWith(AList rhs)
to class AList and appropriate methods to the supporting classes to
concatenate the receiver with the parameter and return the resulting AList. For example, (a b
c).concatWith (1 2) returns (a b c 1 2).
5 pts
- Write a test class. 5 pts.
II. The Tangled Web
Design an object model for the
following recursive immutable data structure that represents web pages.
- A web page has a header, which is a String, and a
body, which is a web document.
- A web document may be empty or non-empty.
When it is empty, it contains nothing.
When it is not empty, it may contain a String and web document, or it
may contain a web page and a web document.
- Draw a UML class diagram for the web page structure. The diagram
should show all relevant classes in your design with appropriate comment
boxes. 10 points
- Provide three distinct concrete examples of web pages that illustrate the
three concrete variants of web documents. 5 points
- Add a method called countWords() to
the web page class and appropriate methods to the supporting classes to count all the
String objects in a web page. You are free to add your own private and
protected methods to help countWords().
10 points
III. General Instructions
All programs in this exercise should be written in a purely functional style:
no object fields should be modified once they have been initialized by a constructor.
As with all programs in this course, lack of good coding style (good style includes
reasonable variable names, a comment preceding each method, consistent indentation) will result in a substantial loss of points.
The code should be documented in javadoc style. The provided java files in the labs and lectures can serve as examples of coding style and documentation format that are acceptable
to us.
IV. Submission
The homework is due Monday, February 04, 2002 at 10:00 AM. It is to be submitted
electronically. No late submission will be accepted.
To turn in this assignment, at the command line type in
turnin -c comp212 -p Homework2 dirname
where dirname is a directory containing all the files in your submission.
The complete
homework set should contain the following:
- A plain text file called README
documenting what you have and/or have not done, describing specific details that you feel we need to know when grading your work.
This README file alone is worth 5 points.
- UML diagrams of all your class designs.
- All the Java source code necessary to compile and execute your test code.
dxnguyen@cs.rice.edu
Please let us know of any broken links
Revised Jan. 25, 2002