Iterators

The need for iterators

Remember our good friend The Queue?

public class Queue {

  public void enqueue(String s) {
    if( head == null ) {
      head = tail = new Node(s,null);
    } else {
      tail.next = new Node(s,null);
      tail = tail.next;
    }
  }

  public String dequeue() {
    Node t = head;
    head = head.next;
    if( head == null ) {
      tail = null;
    }
    return t.data;
  }

  public boolean empty() { return head == null; }

  private class Node {
    public String data;
    public Node next;
    public Node(String d, Node n) { data = d; next = n; }
  }

  private Node head = null, tail = null;
}

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 dequeuing 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
}

public class PeekaQueue extends Queue {
  public String peek() {
    Iter i = iterator();
    return i.next();
  }
}

public class Queue {
  public void enqueue(String s) {
    if( head == null ) {
      head = tail = new Node(s, null);
    } else {
      tail.next = new Node(s, null);
      tail      = tail.next;
    }
  }

  public String dequeue() {
    Node t = head;
    head = head.next;

    if( head == null ) {
      tail = null;
    }
    return t.data;
  }

  public boolean empty() {
    return head == null;
  }

  public Iter iterator() {
    return new Iter(head);
  }

  protected class Iter {
    private Node curr;
    public Iter(Node start) {
      curr = start;
    }

    public boolean hasNext() {
      return curr != null;
    }

    public String next() {
      String s = curr.data;
      curr = curr.next;
      return s;
    }
  }

  private class Node {
    public String data;
    public Node   next;
    public Node(String d, Node n) {
      data = d;
      next = n;
    }
  }

  private Node head = null, tail = null;
}

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

import java.util.*;

public class Ex1 {
  public static void main(String[] args) {
    Scanner sc   = new Scanner(System.in);
    PeekaQueue Q = new PeekaQueue();
    String     s = sc.next();

    while( !s.equals(";") ) {
      if( Q.empty() || !s.equals(Q.peek()) ) {
        Q.enqueue(s);
      } else {
        Q.dequeue();
      }
      s = sc.next();
    }
    System.out.println(Q.empty() ? "success" : "failure");
  }
}

One last thing to try

A good exercise with iterators is to extend PeekaQueue to add a new method

public boolean hasa(String s);

import java.util.*;
import java.io.*;

public class Ex2 {
  public static void main(String[] args) {
    Scanner sc = null;

    try {
      sc = new Scanner(new FileReader(args[0]));
    } catch (IOException e) {
      e.printStackTrace();
      System.exit(1);
    }
    HasaQueue h = new HasaQueue();

    while( sc.hasNext() ) {
      String s = sc.next();

      if( h.hasa(s) ) {
        System.out.print("duplicate " + s + " ");
      } else {
        h.enqueue(s);
      }
    }

    System.out.println("\n");

    while( !h.empty() ) {
      System.out.print(h.dequeue() + " ");
    }

  System.out.println();
  }
}

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!

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

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.

public class HasaQueue extends PeekaQueue {
  public boolean hasa(String s) {
    boolean found = false;
    Iter    itr   = iterator();

    while( !found && itr.hasNext() ) {
      found = s.equals(itr.next());
    }
    return found;
  }
}