Iterable and the Iterator

What is needed is something that walks a collection without needing positions, and remembers where it got to.

That is an iterator, and Java describes it with two tiny interfaces.

public interface Iterable<T> {
    Iterator<T> iterator();
}

public interface Iterator<T> {
    boolean hasNext();
    T next();
}

Iterable says: I can give you something that walks me. Iterator says: I know where I am, and whether there is more.

That is the whole design. One method on the top interface of the entire framework.

The for-each loop is this, in disguise

for (String s : names) {
    System.out.println(s);
}

The compiler rewrites that into:

Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

Which explains everything the for-each does and does not do.

It works on anything that implements Iterable. A list, a set, a tree set, your own class. The same line, unchanged, because all of them can hand back an iterator.

It does not give you an index, because an iterator has no idea what position it is at. It only knows “here” and “is there more”.

Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.

1. Why can you not walk every collection with `for (int i = 0; i < c.size(); i++) c.get(i);`?

   Show the answer

   Two reasons, and either one is enough.

   Most collections have no get(i). A Set has no positions. Neither does a Map or a Queue. Only List offers indexed access, so the loop does not even compile for the rest.

   Even where it compiles, it can be terrible. A LinkedList has get(i), and every call walks from the front. Looping by index over 40,000 elements takes about 806 ms. The same walk with a for-each takes under 1 ms.

   An iterator fixes both. It does not need positions, and it remembers where it is instead of starting again.

2. What does the compiler turn `for (String s : names)` into?

   Show the answer

   Into an iterator loop:

   Iterator<String> it = names.iterator(); then a while (it.hasNext()) loop whose first line is String s = it.next();

   That is the whole trick. Iterable has one method, iterator(), and anything that implements it can be used in a for-each.

   It is why the same line works on an ArrayList, a HashSet, a TreeSet and your own class. Arrays get the same treatment through a special case in the compiler, since an array is not really a class.

3. Removing an element inside a for-each usually throws `ConcurrentModificationException`. Why is 'usually' the worrying word?

   Show the answer

   Because the check is not a guarantee. Removing the second to last element does not throw at all.

   The iterator checks for changes inside next(). Remove the second to last element and the size drops to match the cursor, so hasNext() returns false, the loop exits, and next() is never called again. No check, no exception, and you quietly skipped an element.

   Try it on [A, B, C, D]: removing A, B or D throws. Removing C does not.

   So the exception is a helpful warning, not a safety net. The fix is to use it.remove() or removeIf, both of which are always correct.

Start with the warm-ups. Continue to practice exercises when the basic idea works. Challenges are optional: skip them on a first pass and return after the next lesson.

1. Warm up: one idea with close guidance.
2. Practice: combine the idea with earlier material.
3. Challenge: investigate an edge case or implementation detail.

4 exercises90 pointsabout 100 minutes

class WhyIterator {
    static long sumByIndex(List<Integer> l)
    static long sumByForEach(Iterable<Integer> l)
    static long timeMs(Runnable work)
}

import java.util.*;

public class WhyIterator {

    // Must use get(i). That is what makes it slow on a LinkedList.
    static long sumByIndex(List<Integer> l) {
        return 0; // TODO
    }

    // Must use a for-each loop. Iterable, not List, so a Set works too.
    static long sumByForEach(Iterable<Integer> l) {
        return 0; // TODO
    }

    // Run the work, return how many milliseconds it took.
    static long timeMs(Runnable work) {
        return 0; // TODO
    }

    public static void main(String[] args) {
        for (int n : new int[]{10_000, 20_000, 40_000}) {
            List<Integer> al = new ArrayList<>();
            List<Integer> ll = new LinkedList<>();
            for (int i = 0; i < n; i++) { al.add(i); ll.add(i); }

            // TODO: print all four timings for this n, using timeMs
        }
    }
}

class Cme {
    static boolean throwsWhenRemoving(String target)
    static List<String> removeWithIterator(List<String> l, String target)
    static List<String> removeWithRemoveIf(List<String> l, String target)
}

import java.util.*;

public class Cme {

    // Build a fresh [A, B, C, D], walk it with for-each, remove target through the
    // LIST (not the iterator), and report whether the exception came out.
    static boolean throwsWhenRemoving(String target) {
        return true; // TODO
    }

    // Same job, done safely with an explicit Iterator.
    static List<String> removeWithIterator(List<String> l, String target) {
        return l; // TODO
    }

    // Same job again, in one line.
    static List<String> removeWithRemoveIf(List<String> l, String target) {
        return l; // TODO
    }

    public static void main(String[] args) {
        System.out.println("removing each element from [A, B, C, D]:");
        for (String t : new String[]{"A", "B", "C", "D"}) {
            // TODO: print t and whether it threw
        }

        // TODO: one of the four does NOT throw. Which one, and why?
    }
}

class MyRegistry {
    public Iterator<String> iterator()
}

import java.util.*;

public class MyRegistry implements Iterable<String> {

    private final String[] names = {"Atlas", "Beacon", "Cipher", "Drift"};

    @Override
    public Iterator<String> iterator() {
        return null; // TODO
    }

    public static void main(String[] args) {
        MyRegistry r = new MyRegistry();

        // TODO: this should work once iterator() is written
        // for (String name : r) System.out.println(name);

        // TODO: two nested loops over the same object. Do they interfere?
        // TODO: add a forEach call and note where that method came from
    }
}

class WalkAll {
    static List<String> walk(Iterable<?> items)
}

import java.util.*;

public class WalkAll {

    // One method that walks anything with an iterator.
    static List<String> walk(Iterable<?> items) {
        return List.of(); // TODO
    }

    public static void main(String[] args) {
        // TODO: call it with an ArrayList, LinkedList, HashSet, TreeSet, ArrayDeque
        // TODO: try to call it with an int[]. Read the error, then comment it out
        // TODO: try to call it with a HashMap. Read that error too
        // TODO: make the map work, three ways
    }
}