SUNY Geneseo, Department of Computer Science

Lab 9

CSci 141 , Fall 2003

Prof. Doug Baldwin

Due Wednesday, Oct. 29

Purpose

This lab's goal is to introduce you to the design and analysis of algorithms for lists. The lab also introduces you to some subtleties of working with objects that contain other objects.

Background

This lab asks you to design and code a list class that provides a handful of recursive algorithms for lists. This class will be a subclass of a library class that provides primitive lists. You will thus need to know how to work with the library class, and how to deal with some surprising subtleties of Java and object oriented programming in general that arise when working with data structures.

The List Class

A list is a sequence of objects, defined formally as follows:

A list is either...

Empty, or
An object followed by another list

I have written a simple class, named List, that captures this definition in Java. The List class provides constructors for creating either empty or non-empty lists, a message that determines whether a list is empty or not, and messages that provide access to the two parts of a non-empty list. There are a few other messages, but for the most part think of List as a primitive toolkit, from which you can build more powerful kinds of list by defining subclasses of the List class.

You can find complete Documentation on List on the Web, at http://cs.geneseo.edu/~baldwin/sc/doc/ Click on "List" in the left-hand pane to see the documentation on the List class.

You can Download a copy of the List class (file "List.java") from the Web, at http://cs.geneseo.edu/~baldwin/sc/List.java. I have also put a copy in our folder on the "Course Materials" server.

Working with Container Subclasses

List is a "container" class, i.e., a class that represents something that contains other objects. Two issues arise frequently when creating a subclass of a container class in Java: providing the right constructors, and "casting" the results of certain messages.

Constructors

One often wants to initialize one container to contain the same objects as another. The best way to allow this is to give each container class a constructor that takes another container as its parameter. For example, class List might (but doesn't -- remember, it's a bare-bones toolkit) have a constructor such as this:

    public List( List source ) {
        // ... Copy the objects in "source"
        // into the new list ...
    }

Notice that the parameter to this constructor is a List object. Thus this one constructor can actually initialize a List from any other List object, or any object in a subclass of List. You don't need to write a separate constructor corresponding to every possible kind of source container.

You will generally want to write such a copying constructor for any container class you write. For example, if your subclass for this lab is named ExtendedList, you will want to give it a constructor that begins

    public ExtendedList( List source ) {
        ...
    }

In addition to the copying constructor, container subclasses generally need constructors that parallel those of their superclass, just as many other subclasses do. For example, an ExtendedList subclass of List will probably need constructors

    public ExtendedList ( ) {
        // ... Initialize an extended list
        // to be empty ...
    }

and

    public ExtendedList( Object head, ExtendedList tail ) {
        // ... Initialize an extended list to have first
        // element "head" and rest "tail" ...
    }

Such constructors can often do most or all of what they need to do simply by calling the corresponding superclass constructor.

In the second of the above constructors, it is important that the second parameter is an ExtendedList, not a List, in order to ensure that the sublists inside an extended list are themselves extended lists.

Casts

A big problem with containers is that it's not obvious to a compiler what exact class an object has when it comes out of a container. For example, the message that returns the head of a list (first) is declared as returning something of type Object. This is good in terms of generality, because it means that any kind of object can be put into a list and later retrieved. However, when that object is retrieved, the declaration of first gives a compiler no way of knowing what kind of object has been retrieved, and thus what can legally be done with it. For example, a Java compiler should claim that there is an error on the second line of this code, because as far as the compiler can tell, that line tries to assign what could be an arbitrary object to a variable that can only refer to String objects:

    List stringList = new List( "A string", new List() );
    String s = stringList.first();

Java provides something called a "cast" to solve this problem. In brief, a cast allows a programmer to assert that a value has a particular type, over-ruling the compiler's sense of that value's type if necessary. For example, the above code could be rewritten in a form that does compile as follows:

    List stringList = new List( "A string", new List() );
    String s = (String) stringList.first();

The notation (String) in front of stringList.first() is a cast, which tells the compiler that stringList.first() will, in this use, return a String.

See Section 5.2 of the appendix to The Science of Computing for a fuller description of casts.

Casts are particularly important when writing recursive methods in subclasses of data structures such as List, because the problem described above also applies to the messages that extract substructures (e.g., rest in List): rest is declared as returning a List, and so Java compilers will not let you send a message defined in a subclass to the list returned by rest. Unfortunately, that is exactly what you want to do in many recursive algorithms. For example, the following recursive algorithm to print the elements of a PrintableList subclass of List won't compile:

    // In class PrintableList...
    public void print() {
        if ( ! this.isEmpty() ) {
            System.out.println( this.first() );
            this.rest().print();
        }
    }

The problem is that a Java compiler refuses to believe that this.rest() is returning a PrintableList to which a print() message can be sent, in the statement this.rest().print(). The solution is to cast the result of this.rest() to class PrintableList:

    // In class PrintableList...
    public void print() {
        if ( ! this.isEmpty() ) {
            System.out.println( this.first() );
            ((PrintableList)this.rest()).print();
        }
    }

Exercise

Design and code a subclass of List that has the following features (in addition to what it inherits from List). I call this class ExtendedList in the following, although you can name it anything you like:

A copying constructor, as described under "Constructors" in the "Background" section Above. This constructor should take a List as its parameter, and should initialize a new ExtendedList to contain the same items, in the same order, as the parameter contains.
length, a parameterless message that returns the number of items in an ExtendedList. This returned value is an integer.
everyOtherItem, a parameterless message that returns a new ExtendedList that contains every other item from the original list. Start extracting with the first item, so that the returned list should contain the first, third, fifth, etc. items of the original list.

Each of the above should be handled by a recursive algorithm (even the constructor!)

In addition to writing Java code for the above algorithms, prove that each algorithm correctly does what it is supposed to, and derive a mathematical expression for the number of primitive List operations it performs, in terms of the length of the list on which it operates. A primitive List operation is any operation defined in class List, e.g., first, rest, isEmpty, uses of either List constructor, etc.

Also write a main program that tests and demonstrates what your subclass can do.

To help you test your subclass, I have created 3 files that contain lists. These files are all in our folder on the "Course Materials" server, and are named as follows:

AnimalList: A list of 4 strings that are the kinds of animal
ColorList: A list of 11 strings that are the names of colors
EmptyList: An empty list

If you copy these files to the directory in which your program runs (the subdirectory named "build" in the project directory, if you are using ProjectBuilder), you can use the restore message to read the lists they contain. These lists are ordinary List objects, not ExtendedList objects, but you can use your copying constructor to make ExtendedList objects from them.

Follow-Up

Turn in printouts of the code you write. Also turn in your correctness proofs and operation count derivations. The proofs and derivations can be comments in the program files, or can be on separate pieces of paper.