Reading

Required: These notes!
Recommended: Java in a Nutshell, TO APPEAR

Exam post-mortem

Going over the exam questions is important!

The need for iterators

Remember our good friend The Queue?

It makes a nice example for us, because it's got a simple, small, well-defined interface, and it's dead useful. However, last lesson we saw a simple bit of extra functionality we wanted to add (a "peek" method that would allow us to see what was in the front of the queue without actually dequeueing it) that caused us some problems. We wanted to derive a new class, PeekaQueue, from our original Queue that added this bit of functionality, but we were originally flummoxed, because with only enqueue(), dequeue(), and empty() at our disposal, the "peek" operation was impossible to implement in a reasonable fashion.

Do you remember what our solution was? We changed the Node class (which was nested in Queue) from private to protected and did the same for the head and tail references. This allowed our PeekaQueue class access to head.data, which is what we needed to implement a peek() method. This worked, and it sure was an easy fix, but hopefully it left you feeling a bit queasy. Not that I want you to feel queasy, but I hope that you recognized that we were doing something a bit underhanded. The problem is that we strayed from the enlightened path of strict separation of interface from implementation. So now the custodian of the Queue class cannot change its implementation without worrying about breaking derived classes like PeekaQueue.

The problem is that there is no interface, whether public or protected, for traversing the elements of the Queue in a non-destructive way. If we added such an interface, even if only as protected, then new classes that extend Queue could implement a much wider range of features (like peek) and still be completely separated from the underlying implementation of the Queue as a linked list. So what would such an interface look like?

Iterators

This problem of how to produce a nice interface for iterating over data stored in some object has a standard solution: iterators. An iterator is an object that mimics the functionality that a Node pointer gives you: you know when there's more stuff (the Node pointer isn't null), and you can get the next piece of data in the collection. There are different kinds of of iterator interfaces in the world — different languages have different conventions. In the java convention, the simplest iterator interface (assuming String data) looks like this (note: the name "Iterator" is defined in the Java API, so we're going to call our example "Iter"):
class Iter
{
  public boolean hasNext(); // tells you whether there is a "next" string
  public String next();     // returns the "next" string and advances
}
Now, this iterator really belongs to our class Queue. It doesn't make any sense at all without a Queue object around. Therefore, we will define the Iter class inside the Queue class, just like we did with Node. Finally, we give Queue one new public method, iterator(), which returns an Iter initialized to the very first element in the Queue. With this functionality in place, PeekaQueue becomes quite easy.

Just to close the loop, let's take a look at a simple program that uses PeekaQueue. This is a funny program. It reads a ;-terminated sequence of words, and it prints success if the sequence of words is comprised of two intermingled copies of the same sequence of words. Like this:
a1 a2 a3 b1 a4 b2 b3 b4 b5 a5
where we assume ai = bi. It's just a cute application of a PeekaQueue.

One last thing to try

A good exercise with iterators is to extend PeekaQueue to add a new method
public boolean hasa(String s);
that returns true if String s is currently in the queue.