Comp 212 Assignment #3
Composite Immutable Structures and Visitors

See Course OWLSPACE 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.

  1. 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
  2. Write a visitor called Reverse to compute and return the host in reverse order.  3 pts
    • Write a JUnit test class.  2 pts
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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.

  1. 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
  2. Provide three distinct concrete examples of web pages that illustrate the three concrete variants of web documents.  5 points
  3. 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

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 to OWLSPACE.  No late submission will be accepted.   The complete homework set should contain the following:


dxnguyen at rice.edu         Please let us know of any broken links             Revised 01/29/2007