Applied Design Patterns with Java

Behavioral :: Iterator (257) {C ch 19}

Implementation

The Iterator has many implementation variants and alternatives. Some important ones follow. The trade-offs often depend on the control structures a language provides. Some languages support this pattern directly. Iterator is not defined in Java, but it is defined in the Java 2 standard package installed with Java.

  1. Who controls the iteration? A fundamental issue is deciding which party controls the iteration, the Iterator or the client that uses the Iterator. When the client controls the iteration, the Iterator is called an External Iterator, and when the Iterator controls it, the Iterator is an Internal Iterator. Clients that use an External Iterator must advance the traversal and request the next element explicitly from the Iterator. In contrast, the client hands an Internal Iterator an operation to perform, and the Iterator applies that operation to EVERY ELEMENT in the aggregate. External Iterators are more flexible than Internal Iterators. Internal Iterators are especially weak in a language like C++ that does not provide anonymous functions, closures, or continuations like Smalltalk. But Internal Iterators are easier to use, because they define the iteration logic.
  2. Who defines the traversal algorithm? The Iterator is not the only place where the traversal algorithm can be defined. The aggregate might define the traversal algorithm and use the Iterator to store just the state of the iteration. This kind of Iterator is called a cursor, since it merely points to the current position in the aggregate. A client will invoke the Next operation on the aggregate with the cursor as an argument, and the Next operation will change the state of the cursor. If the Iterator is responsible for the traversal algorithm, it's easy to use different iteration algorithms on the same aggregate, and it can also be easier to reuse the same algorithm on different aggregates. But, the traversal algorithm might need to access the private variables of the aggregate. If so, putting the traversal algorithm in the iterator violates the encapsulation of the aggregate.
  3. How robust is the Iterator? It can be dangerous to modify an aggregate while traversing it. If elements are added or deleted from the aggregate, an element might be accessed twice or missed completely. A simple solution is to copy the aggregate and traverse the copy, but that's too expensive in general. A robust Iterator ensures that insertions and removals won't interfere with traversal, and it does it without copying the aggregate. There are many ways to implement robust iterators. Most rely on registering the Iterator with the aggregate. On insertion or removal, the aggregate either adjusts the internal state of Iterators it has produced, or it maintains information internally to ensure proper traversal.
  4. Additional Iterator operations. The minimal interface to Iterator consists of the operations First, Next, IsDone, and CurrentItem. Some other operations might prove useful. For example, ordered aggregates can have a Previous operation that positions the iterator to the previous element. A SkipTo operation is useful for sorted or indexed collections. SkipTo positions the iterator to an object matching specific criteria.
  5. Using polymorphic Iterators. Polymorphic Iterators have their cost. They require the Iterator object to be allocated dynamically by a Factory Method. Hence they should be used only when there's a need for polymorphism. Otherwise use concrete Iterators, which can be allocated locally. Polymorphic Iterators have another drawback: the client is responsible for deleting them. This is not an issue in Java, since it has automatic garbage collection.
  6. Iterators may have privileged access. An Iterator can be viewed as an extension of the aggregate that created it. The Iterator and the aggregate are tightly coupled. In C++ the Iterator can be made a friend of its aggregate; this is not an option in Java. To avoid this problem, the Iterator class can include protected operations for accessing important but publicly unavailable members of the aggregate. Iterator subclasses (and only Iterator subclasses) may use these protected operations to gain privileged access to the aggregate.
  7. Iterators for composites. External Iterators can be difficult to implement over recursive aggregate structures like those in the Composite (163) pattern, because a position in the structure may span many levels of nested aggregates. Thus, an External Iterator has to store a path through the Composite to keep track of the current object. Sometimes it's easier just to use an Internal Iterator. It can record the current position by calling itself recursively, storing the path implicitly 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. The cursor only needs to keep track of the current node; it can rely on the node interface to traverse the Composite. Composites often need to be traversed in more than one way. Preorder, postorder, inorder, and breadth-first traversals are common. Each kind of traversal can be supported with a different class of Iterator.
  8. Null iterators. A NullIterator is a degenerate Iterator that's helpful for handling boundary conditions. By definition, a NullIterator is always done with traversal; that is, its IsDone operation always evaluates to true. NullIterator can make traversing tree-structured aggregates (like Composites) easier. At each point in the traversal, ask the current element for an Iterator for its children. Aggregate elements return a concrete Iterator as usual. But leaf elements return an instance of NullIterator. That allows implementing traversal over the entire structure in a uniform way.

Related Patterns

Composite (163): Iterators are often applied to recursive structures such as Composites.

Factory Method (107): Polymorphic Iterators rely on Factory Methods to instantiate the appropriate Iterator subclass.

Memento (283) is often used in conjunction with the Iterator pattern. An Iterator can use a Memento to capture the state of an iteration. The Iterator stores the Memento internally.

Catalog Behavioral Prev Next