Documentation- Iterator Deisgn Pattern

Iterator:
The Iterator pattern separates the details of traversing a collection so that they can vary independently. Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. An aggregate object is an object that contains other objects for the purpose of grouping those objects as a unit. It is also called a container or a collection.


Motivation:
An aggregate object such as a list:
It should allow a way to traverse its elements without exposing its internal structure.
It should allow different traversal methods.
It should allow multiple traversals to be in progress concurrently.


Structure:

Participants

Iterator:
Defines an interface for accessing and traversing elements.
ConcreteIterator:
Implements the Iterator interface.
Keeps track of the current position in the traversal of the aggregate.
Aggregate:
Defines an interface for creating an Iterator object.
ConcreteAggregate:
Implements the Iterator creation interface to return an instance of the proper ConcreteIterator.


Implementation Issues:

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.
The client => more flexible; called an external iterator
The iterator itself => called an internal iterator

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. We call this kind of iterator a cursor, since it merely points to the current position in the aggregate.
The iterator => more common; easier to have variant traversal techniques
The aggregate => iterator only keeps state of the iteration.

3. How robust is the iterator?: It can be dangerous to modify an aggregate while you're traversing it. If elements are added or deleted from the aggregate, you might end up accessing an element twice or missing it completely.
An iterator that allows insertion and deletions without affecting the traversal and without making a copy of the aggregate is called a Robust Iterator.

4. Additional Iterator operations: The minimal interface to Iterator consists of the operations First,Next, IsDone, and CurrentItem. Some additional operations might prove useful.

5. Using polymorphic iterators in C++: 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 on the stack.

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. We can express this close relationship in C++ by making the iterator a friend of its aggregate.

7. Iterators for composites:External iterators can be difficult to implement over recursive aggregate structures like those in the Composite pattern, because a position in the structure may span many levels of nested aggregates. Therefore an external iterator has to store a path through the Composite to keep track of the current object.

8. Null iterators: A Null Iterator 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.
Null Iterator can make traversing tree-structured aggregates easier. At each point in the traversal, we 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 Null Iterator.

Applicability:

Use the Iterator pattern
· to access an aggregate object's contents without exposing its internal representation.
· to support multiple traversals of aggregate objects.
· to provide a uniform interface for traversing different aggregate structures (that is, to support polymorphic iteration).

Consequences:

The Iterator pattern has three important consequences:
1. It supports variations in the traversal of an aggregate. Complex aggregates may be traversed in many ways.
For example, code generation and semantic checking involve traversing parse trees. Code generation may traverse the parse tree in-order or pre-order. Iterators make it easy to change the traversal algorithm: Just replace the iterator instance with a different one. You can also define Iterator subclasses to support new traversals.

2. Iterators simplify the Aggregate interface. Iterator's traversal interface obviates the need for a similar interface in Aggregate, thereby simplifying the aggregate's interface.

3. More than one traversal can be pending on an aggregate.An iterator keeps
track of its own traversal state. Therefore you can have more than one
traversal in progress at once.

Known Uses:

1. ObjectSpace's Java Generic Library containers
2. Rogue Wave's Tools.h++ collections
3. java.util.Enumeration interface
4. Java 2 Collections Framework Iterator interface

Related Patterns

1.Factory Method
Polymorphic iterators use factory methods to instantiate the appropriate iterator subclass.
2.Composite
Iterators are often used to recursively traverse composite structures.