Implementing the Iterable Interface

This is a set of extra notes on implementing the Iterable interface, an optional component of HW11: Histogram. These notes are written with the assumption that you're reading them in order to make an iterable List 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. 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. public boolean hasNext()
2. public T next()
3. void remove()

So the iterator() method in your ArrayListImplementation 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 MysteryListImplementation class has a private class inside it called MysteryListIterator — 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 MysteryListImplementation<T> implements List<T> {
    // Private data members go here...
    // Loads of public and private methods go here...
    
    private class MysteryListIterator implements Iterator<T> {
        // Private data members go here...
        public MysteryListIterator() {
            // ...
        }
        public boolean hasNext() {
            // ...
        }
        public T next() {
            // ...
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
    
    // 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.
     * Note that the remove() method is unsupported for this iterator, and will
     * throw an exception if called.
     */
    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.

The Java folks don't provide as much guidance as I think they ought to regarding how remove() is supposed to work. Having an iterator that can change your structure while it's iterating over it is a hard thing to pull off safely, and it's not clear what the canonical behavior is supposed to be. So you can just say that's an unsupported operation and leave it at that.

The bodies for the other three iterator methods are very simple for an array-based List implementation. Each one may be written in just one line. They're easy to write because the inner class has access to all the data members of the outer class.

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) {
        x = _x;
    }
    public Innie makeInnie(int offset) {
        return new Innie(x + offset);
    }
    
    private class Innie {
        private int y;
        public Innie(int _y) {
            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.)