Iterator

Gamma et al. 95

Intent

Provide a way to traverse a collection of elements without exposing its underlying representation: array, linked list, tree, etc.

Motivation

An aggregate object should give you a way to access its elements without exposing its internal structure.

Figure 1. A Linked List

Figure 2. A Tree

Motivation (Cont.)

The collection structure should be independent from the way it is traversed.

Figure 3. Deep-First Traversal

Figure 4. Breadth-First Traversal

Solution

Move the collection traversal behavior into a separate class called Iterator.
All iterators should provide the same interface for accessing and traversing elements, regardless of the class of the collection object and the kind of traversal that is performed.

Figure 5. The Iterator Interface

Structure

Participants

Iterator: defines an interface for accessing and traversing elements
ConcreteIterator: implements the Iterator interface and keeps track of the current position in the traversal of the aggregate
Aggregate: defines an interface for creating an Iterator object
ConcreteAggregate: creates and returns an instance of the proper ConcreteIterator

Consequences

It supports variations in the traversal of an Aggregate: you can use different ways of iterating by defining various concrete subclasses of Iterator for your collection.
Iterators simplify the Aggregate interface
More than one traversal can be pending on an Aggregate

Usage

Iterators are widely used in the Java Collection Framework (JFC)!

Iterator.java

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }

Usage (Cont.)

ListIterator.java

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

Implementation Tradeoffs

Who Controls the Iteration?

If it’s the client: External Iterator
It it’s the iterator: Internal Iterator

// External:
Iterator it = list.iterator();
while (iterator.hasNext())
   System.out.println(it.next());
// Internal:
list.stream().forEach(System.out::println);

External e Internal Iterators

External iterators

more flexible: easy to compare two collections for equality

Internal iterators

hard to implement on languages without anonymous functions or closures
easier to use

Who defines the Traversal Algorithm?

The Aggregator

The Iterator only stores the state of the iteration (it’s called a cursor)
The Client invokes the next() operation on the Aggregate, with the cursor as an argument
The next() operation changes the state of the cursor

The Iterator

Easy to use different iteration algorithms on the same Aggregate
Maybe easier to reuse the same algorithm on different Aggregates
The Iterator might need to access the private variables of the Aggregate, violating the encapsulation of the Aggregate.

How robust is the iterator?

What happens if the Aggregate is modified when an Iterator is traversing it?

Robust Iterators:

ensures that insertions and removals won’t interfere with traversal, without copying the Aggregate
in most implementations, robust Iterators are registered with the Aggregate:
- on changes, the Aggregate adjusts its Iterators

Robust Iterators in Java

Java Collections have a modification counter, called modCount
The counter is incremented after each add or removal
When created, Iterators copy the counter
The Iterator compares both counters before each iteration

Additional Iterator operations.

Minimal Iterator interface: First(), Next(), IsDone(), and CurrentItem().
Other useful operations: Previous() and SkipTo()

Iterators may have privileged access.

In C++: The Iterator is a friend of its Aggregate
In Java: The Iterator is an inner class of its Aggregate, which implements an external Interface.

Iterators for Composites.

It’s hard to implement an external Iterator over recursive Aggregates, like the Composite pattern.
Different traversal algorithms: Preorder, postorder, inorder, and breadth-first
Sometimes, it’s easier to implement an internal Iterator, and perform recursive calls (the path is stored in the call stack)
If the nodes in a Composite have an interface for moving from a node to its siblings, parents, and children: then a cursor-based Iterator may offer a better alternative.

Null Iterators.

A NullIterator is always done with traversal: operation IsDone() always evaluates to true.
NullIterators are helpful for handling boundary conditions.
Useful for tree-structured aggregates.