Reading

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

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. For example, the following program reads through a file, reports and duplicate strings it finds, and prints out the contents of the file with duplicates removed.

Just to make clear the tremendous value of this program, we'll use it to remove duplicates from a well-known pop song (by a Grammy award winning artist). You'll see that with this technology we can substantially reduce the time required to listen to this song!
shake.txt
i stay out too late
got nothing in my brain
that's what people say mmm-mmm
that's what people say mmm-mmm

i go on too many dates
but i can't make them stay
at least that's what people say mmm-mmm
that's what people say mmm-mmm

but i keep cruising
can't stop won't stop moving
it's like i got this music
in my mind
saying it's gonna be alright

'cause the players gonna play play play play play
and the haters gonna hate hate hate hate hate
baby i'm just gonna shake shake shake shake shake
i shake it off i shake it off
heart-breakers gonna break break break break break
and the fakers gonna fake fake fake fake fake
baby i'm just gonna shake shake shake shake shake
i shake it off i shake it off
~/$ java Ex2 shake.txt
duplicate that's duplicate what [...] duplicate off

i stay out too late got nothing in my brain that's what people say mmm-mmm go on many dates but can't make them at least keep cruising stop won't moving it's like this music mind saying gonna be alright 'cause the players play and haters hate baby i'm just shake it off heart-breakers break fakers fake

So now we move on to the real question: how do we implement HasaQueue? The answer is that we let the iterator do the work for us! Iterators give us a nice, well-defined interface that we can separate away from the implementation (i.e. the linked-list stuff). You'll see in this code that we can iterate through the elements of the Queue (without actually dequeuing anything) without referring to Node in an way.