Comp 212 Assignment #2
Immutable List

Due Sunday Sept. 16, 2000 11:59 PM - No Late Submission will be accepted

This homework exercise serves as a transition from functional programming to object-oriented programming.  It also serves as a "dry run" for the larger programming projects that will come later.  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.

1. Modify the toString() method that returns a String representation of AListwith 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 ().
2. 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.
3. 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.
4. 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. 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 using the length of the receiver.
6. 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.
7. 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).

II. List of lists (Generalized List)

A generalized list, GenList,  is a list that can contains lists as data objects.

• MTGList is a GenList; it contains no data.
• NonMTGList is a GenList; it contains a substructure called rest that is a GenList.
• AtomicGList is a NonMTGList ; it contains a data object called first, which is simply an Object.
• NonAtomGList is a NonMTGList ; it contains a data object called first, which is a GenList.

1. Draw a UML diagram for the GenList structure.
2. Provide three distinct concrete examples of GenList that illustrate the three concrete variants of GenList.
3. Add a method called countObjects() to GenList and appropriate methods to the supporting classes to count all the data objects in a GenList.  You are free to add your own private and protected methods to help countObjects().

III. General Instructions

For each of the above problems, be sure to add test cases which cover all reasonable cases.  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 header before each non-overridden function, reasonable indentation) will result in a substantial loss of points.  The code should be documented in javadoc style.  The provided java files in lab 03 can serve as examples of coding style and documentation format that are acceptable to us. 

IV. Submission

The homework is due Friday Sept. 14, 2000 11:59 PM.  It is to be submitted electronically.  Your labbies will give you specific submission instructions in the upcoming lab tutorial (lab 03).  No late submission will be accepted.  The complete homework set should contain the following:

• An ASCII README file to indicate what you have and/or have not done, and to point out specific details that you feel we need to know when grading your work. 
• StructureBuilder's UML diagrams of all your class designs.
• All the Java source code necessary to compile and execute your test code.