Computer Science & Engineering 505
Assignment 5 (revised)

Due: Nov 19, 1999

  1. The purpose of this question is to give a small amout of experience in writing Java, and in particular to use the inner class mechanism and types and interfaces. It isn't intended to require that you understand the Java class library in detail (so in particular just write the BinaryTree class from scratch).

    Write and test a class BinaryTree in Java that implements sorted binary trees. (Use whichever Java compiler is convenient.) The nodes in the tree should hold objects that implement the Comparable interface (this includes String, Integer, Float, etc). Your binary tree should provide the following methods:

    You don't need to implement delete. Also, you don't need to worry about synchronization issues (inserting a new element into a tree while there is an iterator in use for that tree). Finally, to keep things simple, you don't need to have your BinaryTree implement the Collection interface. (If you were providing this as part of a Java library for practical use, this would be the right thing to do however.)

    There are several possible ways of handling the tree traversal method. The issue is that the iterator must return one value at a time from the next() method, so you can't just implement the traditional recursive procedure directly. Pick an technique, and discuss why you chose that particular technique.

  2. Discuss how Java's type system supported and/or hindered you in writing the binary tree.

  3. Sketch how you would implement the binary tree example in Pizza (giving in particular the method headers, including type information).

  4. This question concerns abstract types and subtypes, parameterized types, and the contravariant rule. We have an abstract type Consumer, parameterized by T, the type of object that the Consumer consumes. Consumer has a single operation eat, which takes a single argument of type T and doesn't return anything.

    We also have an abstract type Producer, again parameterized by T. Producer has a single operation make, which takes no arguments and returns an object of type T.

    Finally we have an abstract type ProducerConsumer, again parameterized by T, the type of object that the ProducerConsumer contains. ProducerConsumer has two operations: eat and make.

    Using the contravariant rule, what is the subtype relation between the following pairs of types? (The answer to each question would be either X is a subtype of Y, Y is a subtype of X, or neither is a subtype of the other.)

    1. ProducerConsumer[Integer] and ProducerConsumer[Number]
    2. Consumer[Integer] and Consumer[Number]
    3. Producer[Integer] and Producer[Number]
    4. ProducerConsumer[Integer] and Producer[Number]
    5. ProducerConsumer[Number] and Producer[Integer]
    6. ProducerConsumer[Integer] and Consumer[Number]
    7. ProducerConsumer[Number] and Consumer[Integer]

  5. The same as the previous question, except use the covariant rule. If the covariant rule gives an incorrect answer, give an example of a program that breaks; or one that will always execute without type errors, even though the covariant rule says it is incorrect.