Notes on Implementing an Iterator

This is a set of notes on implementing the Iterable interface, an optional component of HW05: Country Displayer Redux. These notes are written with the assumption that you're reading them in order to make an iterable SortedList implementation; if you're trying to do something else, then you'll have to translate the examples in your head a little bit.

Implementing the Iterable<T> interface allows objects that were constructed with your list implementation to be used directly in for-each loops (the for-loop with the colon syntax). Take a look at the Java documentation for Iterable: the interface requires you to implement only one method, iterator(), which returns an Iterator<T>.

So what's an Iterator<T>? Well, it's a thing that knows how to step, one-by-one, through the elements of some structure, given that those elements are of type T. In practice, as the documentation indicates, an iterator is just something that implements these three methods:

1. boolean hasNext()
2. T next()
3. void remove()

So the iterator() method in your SortedLinkedList class should return something that implements the Iterator<T> interface. But how do you do that?

The answer is that you create a private inner class. My MysterySortedListImplementation class has a private class inside it called SortedMysteryListIterator — that's why you have to download two .class files when you want to use this implementation. Here's an abstract of the source code:

public class MysterySortedListImplementation<T> implements SortedList<T> {
    //Private fields (instance variables and any static variables) go here...
    //Public and private methods go here...
    
    private class SortedMysteryListIterator implements Iterator<T> {
        // Private fields go here...
        public MysteryListIterator() {
            // ...
        }
        public boolean hasNext() {
            // ...
        }
        public T next() {
            // ...
        }
        public void remove() {
            // ...
        }
    }
    
    // With that in place, the iterator() method of MysteryListImplementation
    // is easy to write:
    /** 
	 * Returns an iterator over the list, starting from just before index 0.
     */
    public Iterator<T> iterator() {
        return new MysteryListIterator();
    }
}   

Note that MysteryListIterator doesn't take a generic type argument; the T that it uses inside it is the T that was defined for the entire MysteryListImplementation class. For the SortedLinkedList, we don't have generic type parameters so you'd instead use private class SortedLinkedList implements Iterator<Country>.

The bodies for the three iterator methods and the constructor are relatively concise for a Linked List implementation. They're much easier to write because the inner class has access to all the data members of the outer class. For the assignment, you should implement the constructor, hasNext, and next. next returns the item after the one you returned previously (e.g., the first call to next gives item 0, the second call gives item 1, and so on). hasNext tells you whether there are any items remaining in the list that you haven't iterated over. If next is called when there are no items left, you can throw an exception.

Implementing remove is optional. If you choose not to implement remove, have that method throw an UnsupportedOperationException. When writing the iterator, you can assume that items are not removed from the list while the iterator is stepping through the items.

Non-static private inner classes can see all of the internals, public or private, of the outer class that contains them — since they're non-static, they must be instantiated from an existing object of the outer type, and therefore that outer-type object has values for all its data members. Let's look at a simplified example:

public class Outie {
    private int x;
    public Outie(int x) {
        this.x = x;
    }
    public Innie makeInnie(int offset) {
        return new Innie(x + offset);
    }
    
    private class Innie {
        private int y;
        public Innie(int y) {
            this.y = y;
        }
        public void compareAndPrint() {
            System.out.format("y = %d; Outie.this.x = %d", y, Outie.this.x);
            if(y < Outie.this.x) {
                System.out.print(" (y is less!)");
            }
            System.out.println("");
        }
    }
    
    public static void main(String[] args) {
        Outie o1 = new Outie(10);
        Innie i1 = o1.makeInnie(5);
        
        Outie o2 = new Outie(20);
        Innie i2 = o2.makeInnie(-5);
        
        i1.compareAndPrint();
        i2.compareAndPrint();
    }
}

Copy that code to a file called Outie.java, compile it, and run it.

Note that the value of Outie.this.x that each Innie object sees is the value associated with the Outie object from which that Innie object was created. So i1 and i2 happen to have the same value of y, but since they were generated by different Outie objects, they see different values of Outie.this.x, and therefore behave differently when we call compareAndPrint() on both of them!

Note also that since Innie is a non-static class, we can't create instances of it directly; we always have to ask Outie objects to make them for us. So, for example, adding the following line to the main method would cause a compiler error: Innie i3 = new Innie(15);.

(A small side note on syntactic conventions for accessing members of the outer class: strictly speaking, since the name x is unambiguous inside compareAndPrint(), it would be fine to just say x instead of Outie.this.x. But the latter is preferred because it more clearly conveys to someone reading your code that this method is getting information from the Outie object from which it was instantiated.)