Homework # 8
due Tuesday, April 6, 4:00 PM

Integer Sets

In the previous Homework, you implemented a BST-based integer set ADT. Our solution is in the solutions directory. In this Homework, you will modify this code (your solution or our solution) so that we have an interface IntSet, and abstract base class (put keyword abstract before the class declaration) AbstractIntSet that implements this interface and provides default (possibly inefficient) implementations of some of the methods, and three concrete classes that inherit from the abstract base class and provide actual implementations:

TreeIntSet
This class will use the BST implementation from the previous Homework assignment.
LinkedIntSet
This class will use linked lists to implement the functionality.
HashedIntSet
This class will use a java.util.HashTable which maps Integer objects to themselves (if in the set) or null (if not in the set). The keys method of this class which returns a java.util.Enumeration will be very useful.
The IntSet interface requires the following functionality:
find
As in Homework #7.
add
As in Homework #7.
equals
Return true if the parameter implements IntSet and has the same elements.
hashCode
Returns the sum of the elements.
includedIn
Returns true if all this set's elements are in the parameter set.
iterator
Return an object of a class that implement IntIterator.
toString
Return a string for the set.
The IntIterator interface requires
hasNext
True if next() will return an integer.
next
Return the next integer in the set, or throw an exception.
Both these interfaces are available for you in files in
/afs/cs.uwm.edu/users/classes/cs431/src/homework8/
These interfaces should not be changed. We also provide a driver and a skeleton for AbstractIntSet.

Covariance and Contravariance

Do Exercise 4 in the textbook (page 318). You will need to do some internet research. Also answer the question:

d. How do parasitic methods address the problem of ``covariant overriding'' ?

Submitting Your Work

You submit your program work by putting it in the homework8 directory in your AFS class volume. You may do all your work in this directory, or you may wish to do your work in a different directory and copy things when correct into this directory. In any case, you will lose permission to write things in this directory after the deadline, which is 4:00pm on Tuesday, April 6th. In other words, you must be done before lecture starts.

The homework8 directory should include the following:

Additionally it should include unchanged versions of the two interfaces. You may change the driver if you wish.

About this document


John Tang Boyland
2004-03-30