Comp 212 Assignment #3
Composite Immutable Structures and Visitors
See Course Web Page for due date -
No Late Submission will be accepted
All usual Honor code rules apply.
This homework exercise serves as a transition from functional programming to
object-oriented programming. It is based on the immutable list framework discussed in
lecture 08 and in lab 03.
I. Object-Oriented Scheme List
Your task is to write algorithms on IList as visitors
as specified in the following problems. The classes IList,
IEmptyList, INEList,
EmptyList, NEList should be in a package named OOscheme.
You are free to add any private
and protected methods to your visitor classes to support your public operations.
You are also free to write helper visitors to support your main visitors.
You are not allowed to check for the type of any object, such as using instanceof
or add a method to check for the type, to perform any task. The
visitors should be in a package named OOscheme.visitor,
unless specified otherwise.
- Write a visitor called ToString to
compute as String representation of
IList 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 (). 3 pts
- Write a JUnit test class. 2 pts
- Write a visitor called Reverse to compute and return the host in reverse order.
3 pts
- Write a JUnit test class. 2 pts
- Write a visitor called MakeClone to compute and return a copy of the host. The
copy should not contain any non-empty substructure of the original. 5
pts
- Write a JUnit test class. 5 pts
- Write a visitor called GetNth to compute and return the n-th
element of the host. Here 0 <= n, and the case n equals 0 corresponds to the
first element of the list. Decide how to pass n to GetNth yourself.
5 pts
- Write a JUnit test class. 5 pts
- Write a visitor called LastElement to find and return the last element of the
host. Do this by traversing the host only once. 5 pts
- Write a JUnit test class. 5 pts
- Write a visitor called FirstNElements to compute and return an
IList that contains the first n elements of the host. Here
0 <= n, and the case n
equals 0 corresponds to the empty list. Decide how
to pass n to FirstNElements yourself.
5 pts
- Write a JUnit test class. 5 pts
- Write a visitor called Zip to weave
the host list with an input list in such a way that the elements in the
resulting list alternate between the elements in the host list and the
elements in the input list.
For example, when we Zip
(1
2)
with
(6
7 8),
we
get
(1
6 2 7 8).
Notice the
lists need not have the same length. 5 pts
- Write a JUnit test class. 5 pts
Each of the above problems should be done independently from each other, that
is you cannot use the result of one problem to solve another problem. We
want you to come up with the most direct (and hopefully most efficient) solution
possible.
II. The Tangled Web
Consider the
following description of 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.
- Design the the above web page structure using the composite and visitor
patterns. Draw a UML class diagram for the web page structure. The diagram
should show all relevant classes in your design with appropriate comment
boxes. 15 points
- Provide three distinct concrete examples of web pages that illustrate the
three concrete variants of web documents. 5 points
- Add a visitor called
CountStrings
for the web page class and appropriate helper visitors to count all the
String objects in a web page. 10 points
- Write a JUnit test
class. 5 pts
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 to be submitted
electronically via WEBCT. No late submission will be accepted. 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 should also contain the pledge of honor and 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
02/05/2006