Homework #8

Q: The compiler says it doesn't know what java.util.HashTable is?

A: Oops: my mistake. It is java.util.Hashtable. (The t should be lowercase.)

Q: How do we implement the iterator classes?

A: The three concrete set classes use very different techniques:

TreeIntSet

This is the most complex -- the iterator class needs a linked list of tree nodes of subtrees that still need to be traversed. Sometimes in CS 351, I ask you to implement an iterator over binary search trees using a stack of nodes. This is the idea. If you get stuck, you can get partial credit by decanting the entire contents of the tree (using inorder traversal) into a list and then iterator over that).

LinkedIntSet

This is the easiest iterator: the iterator simply keeps a pointer to the current link and moves it along every time next is called.

HashedIntSet

This is easy if you use the hint given in the homework. Get an Enumeration from the hash table and then use casts (as in Homework #7: ((Integer)...) to get the values.

NB: Many people are confused about iterators. Here is a brief explanation:

Many of you took CS 351 where you implemented external iterators for traversing data structures such as lists or trees. In C++, an iterator is a class that implements member functions named operator++ and operator*. The container class didn't have member functions with these names, rather they had functions such as begin or end that returned instances of nested classes that did the work. The nested class was usually called Iterator.

In Java, external iterator classes must implement an iterator interface. For Homework #8, we use our own home-grown interface IntIterator. Again, the container class itself does not implement the hasNext and next methods; instead it has a method iterator() that creates an instance of a nested class (perhaps named Iterator) that does implement the IntIterator interface and has methods hasNext and next.

For those who don't recall the purpose of iterators: an iterator gives access to all the elements of a set, so if one writes:

for (IntIterator it = someSet.iterator(); it.hasNext(); ) {
  System.out.println(it.next());
}

It will print out all the elements. This is the equivalent of the loop in C++ that looks like:

for (SomeSet::iterator it = some_set.begin(); it != some_set.end(); ++it) {
   cout << *it;
}

Notice that in neither C++ nor Java, does one get the elements directly from the container. In C++, you don't write *some_set or some_set++. Similarly in Java, one never writes someSet.hasNext() or someSet.next(); it just doesn't make sense to do that.

Q: What should I do about unchecked warnings when I use the raw type Hashtable?

A: Ignore them -- we're using Java 4 here. If you want, you can compile with -source 1.4