10 6/12: Iterators, Iterables

The goal of this lab is to practice implementing and using iterators and iterables.

Home on the Half-open Range

In class today, there came a point when we wanted to iterate through a range of numbers. The code we would have liked to write was something like:

for (Integer i : new Integer(30)) {

table.add(new Empty<Pair<K,V>>());

}

This was just wishful thinking, but the idea was that if Integer had implemented the Iterable<Integer> interface, then its iterator could have produced the integers from 0 (inclusive) through 30 (exclusive).

Since the lackeys at Oracle didn’t do the leg work for us, let’s design our own class that makes this possible. What we’d like to write to carry out our original task is:

for (Integer i : new HalfOpen(0,30)) {

table.add(new Empty<Pair<K,V>>());

}

This should run through the integers in [0,30). The class is called HalfOpen because a [x,y) is known as a half-open interval.

Half-open intervals are useful for all kinds of programming tasks. For example, here’s how to compute the factorial function using an interval:

Integer fact(Integer n) {

Integer acc = 1;

for (Integer i : new HalfOpen(1, n+1)) {

acc = acc * i;

}

return acc;

}

Exercise 1. Design the HalfOpen class so that it can be used as shown above.

Exercise 2. Add a constructor to HalfOpen that consumes a single integer and whose iterator goes from 0 to that number.

Exercise 3. Add an integrity check to your constructors so that malformed intervals such as [3,-2) are rejected by raising an exception.

Exercise 4. Add a third constructor to HalfOpen that consumes three integers and whose iterator starts from the first integer and goes to the second integer by increments of the third integer. Eg. new HalfOpen(4, 12, 2) would iterate through 4, 6, 8, 10.

Exercise 5. Design the Open and Closed classes that represent (x,y) and [x,y] intervals, respectively. Include all of the constructor features above.

Now let’s do something with a slight twist: let’s construct an infinite iterator. An infinite iterator is just an iterator that will iterate through an infinite number of elements. As a first exercise, design an iterator for the natural numbers.

Exercise 6. Design a class Nat that implements Iterable<Integer> and whose iterator will produce the elements 0, 1, 2, 3, ... and so on without end.

At first glance it may not seem like an infinite iterator is useful since it will go on forever, but in fact they can be quite useful when combined with return. For example, if we want to find the first integer that makes a given function produce 0, we could do so as:

Integer findZero(Fun<Integer,Integer> f) {

for (Integer i : new Nat()) {

if (f.apply(i).equals(0)) {

return i;

}

}

throw new RuntimeException("Inconceivable");

}

Exercise 7. Add a constructor to Nat that consumes a single integer n so that its iterator will produce the elements n, n+1, n+2, n+3, ... and so on without end.

Exercise 8. Add a constructor to Nat that consumes two integers, n and step, so that its iterator will produce the elements n, n+step, n+2*step, n+3*step, ... and so on without end.

Iterable Hash Tables

Starting with the code we wrote in class today, add the following features to hash tables.

Exercise 9. Rewrite the hash table initialization to use an interval as we had orginally wanted to.

Exercise 10. Design the method void clean() that “cleans up” a hash table by removing elements in each list that are not reachable with lookup, i.e. any elements that have the same key as an earlier key in the list.

Exercise 11. Design the methods Iterator<K> iteratorKeys(), Iterator<V> iteratorVals(), and Iterator<Pair<K,V>> iterator() that produce iterators over the keys, the values, and pairs of keys and values in the table, respectively. Once you’ve done this, make HashTable<K,V> implement Iterable<Pair<K,V>>. (Hint: using clean as the first step should make this problem easier.)