Part 4 of 6 · 3 min read
Iterator
Visit every element in turn.
Think of a museum audio guide that takes you from room to room. You do not need the floor plan. You press next, and the guide takes you to the next exhibit. Two visitors can use two guides at the same time, each at their own place.
GoF's applicability for Iterator has three points: to reach the contents of a collection without exposing how it is stored, to allow several traversals of the same collection, and to give one interface for walking different structures.
An Iterator has a way to ask whether more elements remain, and a way to get the next one. It keeps its own position. In Java, the Iterable interface produces an iterator, and the for-each loop calls it. EJ Item 58 recommends the for-each loop over the older index loop, since it hides the iterator and so removes a source of bugs.
A depth-first walk of the folder tree shows the idea. The iterator keeps a stack of child iterators, one for each folder it is inside.
class Folder implements Node, Iterable<Node> {
// ... fields and methods as before ...
public Iterator<Node> iterator() {
Deque<Iterator<Node>> stack = new ArrayDeque<>();
stack.push(children.iterator());
return new Iterator<>() {
public boolean hasNext() {
while (!stack.isEmpty() && !stack.peek().hasNext()) stack.pop();
return !stack.isEmpty();
}
public Node next() {
if (!hasNext()) throw new NoSuchElementException();
Node n = stack.peek().next();
if (n instanceof Folder f) stack.push(f.children.iterator());
return n;
}
};
}
}
With the earlier tree, for (Node n : root) visits a.txt, docs, b.md, c.md, empty, in that order. The caller needs no knowledge of how the tree is stored.
Because each iterator keeps its own state, two walks can run at once. Take two iterators over the same root. After the first has been advanced twice, its next element is b.md, while the second iterator's first element is still a.txt. GoF lists this as one of three consequences, along with easy variation of traversal (replace the iterator with another, such as breadth-first) and a simpler collection interface, since the collection does not need its own traversal methods.
Take care with changes while walking. Adding or removing children during a walk can break an iterator. Java's standard collections throw a ConcurrentModificationException in that case. Observer (module 2) met the same problem.
Iterator pattern
The Iterator pattern gives a way to visit the elements of a collection one at a time, without showing how the collection is built, and keeps the position of the visit in a separate object.
Example: the iterator that for (Node n : root) uses.
Check yourself: 1. In what order does the for-each visit the example tree? 2. Why can two iterators run at once? 3. What happens in Java's standard collections if the collection changes during a walk?