Programming in the Large with Design Patterns (2012)
Chapter 3. Iterator
Introduction
The iterator design pattern provides a way of traversing the elements of a collection object without exposing the underlying implementation.
A collection object (also called a container object) is an object that stores a group of related items. There are standard types of collection objects such as lists, sets and dictionaries as well as user-defined collection objects that group application-specific elements. For example, an application might have a ProductPortfolio class that groups related products:
public class ProductPortfolio {
private Product products[];
. . .
}
Clients of collection objects often need to visit each element of the collection. One way for a collection class like ProductPortfolio to support traversal of its elements is to simply give clients access to its internal data structure.
Figure 25 First candidate design for traversing the elements of a collection class
The following code fragment shows the implementation of the collection along with client code that traverses the elements of the collection:
public class ProductPortfolio {
private Product products[];
// Not recommended. Promotes high coupling
public Product[] getProducts() {
return products;
}
}
void static clientCode(ProductPortfolio portfolio) {
Product products[] = portfolio.getProducts();
for (int i=0; i<products.size; i++)
process(products[i]);
}
The main problem with this solution is it violates the principle of information hiding. Giving clients access to the internal data structure used to store product data increases coupling between clients and ProductPortfolio. This causes two potential problems. First, there is no language mechanism preventing clients from directly adding or deleting products from the internal data structure. Second, the cost of making changes to the internal data structure of ProductPortfolio goes up with each new client access. Should the internal implementation change from an array to say a linked list, all clients accessing the original array will also have to be updated to work with a linked list rather than an array. (Alternately, ProductPortfolio could create and return an array from the internal linked list, but this would be less efficient.)
Intent
The Iterator design pattern solves the problem of how to traverse the elements of a collection object in a way that keeps client code doing the traversing loosely coupled to the collection object as well as the traversal algorithm.
Solution
Rather than present the general design for the Iterator design pattern straightaway, it will be evolved from the example presented in the introduction. Doing so will provide some justification for why the final design looks the way it does as well as serve as a simple example of how design principles can be used to guide the design process.
As mentioned in the introduction, one way of supporting iteration is to simply give clients access to the internal data structure of the collection class. This design option is unappealing because it increases coupling between clients and the collection. One way of addressing this problem is to keep the internal data structure private and add traversal methods to the interface of the collection.
Figure 26 Second candidate design for traversing the elements of a collection class
Clients would use the traversal methods of the collection to visit each element of the collection:
public class ProductPortfolio {
private Product products[];
. . .
// Return first product or null
public Product getFirst() { . . . }
// Return next product or null
public Product getNext() { . . . }
}
void static clientCode(ProductPortfolio portfolio) {
Product product = portfolio.getFirst();
while (product != null) {
process(product);
product = portfolio.getNext();
}
}
While this solution better insolates clients from the implementation details of ProductPortfolio, it violates another principle of good design, which is the single responsibility principle. Including iteration logic in ProductPortfolio makes it responsible not only for operations specific to product portfolios (not shown) but also iteration.
To remedy this problem, iteration logic can be extracted from ProductPortfolio and placed in a separate class, Iterator.
Figure 27 Third candidate design for traversing the elements of a collection class
The traversal algorithm now resides in the class Iterator. To traverse the elements of ProductPortfolio, clients call the factory method createIterator() to request an iterator object and use the iterator object to traverse the elements in the container.
public class ProductPortfolio {
private Product products[];
. . .
public Iterator createIterator() {
return new Iterator(products)
}
}
public class Iterator {
private Product products[];
. . .
public Iterator(Product products[]) {
this.products = products;
}
// Return first product or null
public Product getFirst() { . . . }
// Return next product or null
public Product getNext() { . . . }
}
void clientCode(ProductPortfolio portfolio) {
Iterator iterator = portfolio.createIterator();
Product product = iterator.getFirst();
while (product != null) {
process(product);
product = iterator.getNext();
}
}
This design has a couple of other benefits besides having a cohesive container class. Representing iteration logic in a separate class makes it possible to have multiple iterations in progress on the same container. It also makes it possible for containers with similar implementation to reuse or share the same iterator.
While the current design doesn’t violate any major design principles, it is somewhat inflexible. Oftentimes there are multiple types of collection classes and multiple types of iteration algorithms. As it is now, client code is tightly coupled to a specific type of container (ProductPortfolio) and a specific type of iteration (Iterator). Clients that just need to traverse the elements of a collection and don’t care about the specific type of collection or iteration algorithm would benefit from more generality in the design.
The design can be made more flexible by adding abstract interfaces for container types and iteration algorithms.
Figure 28 Application-specific example of Iterator design pattern
Client code written in terms of the abstract interfaces AbstractCollection and AbstractItertor will work with any specific type of collection or iteration that conforms to these abstractions.
The following code fragment demonstrates polymorphic client code that works with instances of ProductPortfolio, DiscontinuedProducts and instances of any other class that implements the interface AbstractCollection.
interface AbstractCollection {
AbstractIterator createIterator();
}
interface AbstractIterator {
Product getFirst();
Product getNext();
}
class ProductPortfolio implements AbstractCollection {
private Product products[];
public AbstractIterator createIterator() {
return new StandardIterator(products);
}
}
class DiscontinuedProducts implements AbstractCollection {
private Product products[];
public AbstractIterator createIterator() {
return new StandardIterator(products);
}
}
class StandardIterator implements AbstractIterator {
. . .
public StandardIterator(Product products[]) {
. . .
}
public Object getFirst() {
. . .
}
public Object getNext() {
. . .
}
}
// Polymorphic client code.
// This method works for any object that
// implements the interface AbstractCollection.
public static void clientCode(AbstractCollection c) {
AbstractIterator iterator = c.createIterator();
Object item = iterator.getFirst();
while (item != null) {
process(item);
item = iterator.getNext();
}
}
public static void main(String[] args) {
DiscontinuedProducts dp = new DiscontinuedProducts();
ProductPortfolio pp = new ProductPortfolio();
. . .
clientCode(dp);
clientCode(pp);
}
The code fragment above also demonstrates flexibility with respect to the iteration algorithm used. Both ProductPortfolio and DiscountinuedProducts return an instance of StandardIteration, but since the client routine is written in terms of AbstractIterator, it will work with any iteration algorithm that implements the interface AbstractIterator.
The UML diagram in Figure 28 shows a box for FailFastIterator. Fail fast iteration is a safer form of iteration that throws an exception if the container is updated during iteration. ProductPortfolio could be modified to return an instance of FailFastIterator and the client code would work just fine.
The previous example introduced the iterator design pattern with an application-specific example. The structure diagram for the more general Iterator design pattern is shown in Figure 29.
Figure 29 Structure diagram for the Iterator design pattern
The Iterator design pattern has four components:
Collection – defines the interface for collection types. Included in the interface is createIterator(), a factory method for creating the iterator for the collection. Optionally, the interface may also include methods for managing (adding, removing, etc.) the elements of the collection.
Iterator –defines the interface for traversing the elements of a collection. There is no standard set of methods for iteration. The iterator interface in the Java API (Iterator) consists of hasNext(), next() and remove(). The iterator interface in the .NET framework (IEnumerator) consists of the attribute Current and the methods MoveNext() and Reset(). Some iterators also allow forward and backward traversal.
ConcreteCollection – a class that implements the Collection interface. The concrete collection decides which iterator to create.
ConcreteIterator – a class that implements the Iterator interface. A concrete iterator needs access to the internal data structure of the collection it traverses. A collection may grant its iterator privileged access to its internals (e.g. by friending the iterator in C++ or defining a nested class in Java) or pass a reference or copy of its internal data structure as an argument to the iterator’s constructor. How’s this different from giving clients access to the internal details of iterators? Granting an iterator privileged access is less of a concern because in general there will be many more clients than iterators.
Sample Code
Most object-oriented programming languages include support for collections. Those that do typically offer an assortment of concrete collection classes (e.g. Array, LinkedList, and Dictionary) along with abstractions (e.g. interfaces) for collections and their iterators. Figure 30 shows some of the key classes and interfaces in the Java collection framework.
Figure 30 Key classes and interfaces in the Java collection framework
The following Java program demonstrates polymorphic client code traversing the elements of two completely different data structures.
// Output:
// 1 2
// 3 4
import java.util.*;
public class IteratorExample
{
public static void main(String[] args)
{
ArrayList arrayList = new ArrayList();
arrayList.add(new Integer(1));
arrayList.add(new Integer(2));
LinkedList linkedList = new LinkedList();
linkedList.add(new Integer(3));
linkedList.add(new Integer(4));
clientCode(arrayList);
clientCode(linkedList);
}
public static void clientCode(Collection collection) {
Iterator i = collection.iterator();
while (i.hasNext())
{
Object o = i.next();
String s = o.toString();
System.out.print(s + " ");
}
System.out.println();
}
}
Discussion
The Iterator design pattern illustrates just how far some design patterns have come. The iterator design pattern, like all patterns, started out as a general solution to a reoccurring design problem. Later, support for the pattern began to appear in language class libraries. Today, several programming languages include support for the pattern in the language proper.
For example, C# includes a foreach statement, which is used to iterate over the elements of a collection or array:
foreach (ItemType item in someCollection)
someCollection is any object that implements the interface IEnumerable or declares the method GetEnumerator(). The interface IEnumberable has one method that returns an iterator of type IEnumerator:
interface IEnumerable {
IEnumerator GetEnumerator();
}
interface IEnumerator {
Object Current {get;}
bool MoveNext();
void Reset();
}
Here is a complete example showing the application-specific collection ProductPortfolio being used with the foreach statement. Notice that ProductPortfolio creates and returns an iterator.
// Output:
// Pencil $0.5
// Eraser $1
// Notebook $2
using System;
using System.Collections;
class Program {
static void Main(string[] args) {
ProductPortfolio currentProducts = new
ProductPortfolio();
foreach (Product p in currentProducts)
Console.WriteLine(p.name + " $" + p.amount);
Console.ReadLine();
}
}
public class Product {
public string name;
public double amount;
public Product(string name, double amount) {
this.name = name;
this.amount = amount;
}
}
public class ProductPortfolio : IEnumerable {
private Product[] products;
public ProductPortfolio() {
products = new Product[3] {
new Product("Pencil",.5),
new Product("Eraser",1.0),
new Product("Notebook",2.0) };
}
public IEnumerator GetEnumerator() {
return new StandardIterator(products);
}
private class StandardIterator : IEnumerator {
private Product[] products;
private int position;
public StandardIterator(Product[] products) {
this.products = products;
Reset();
}
public bool MoveNext() {
position++;
return (position < products.Length);
}
public void Reset() { position = -1; }
public object Current {
get { return products[position]; }
}
}
}
Related Patterns
The createIterator() method of the Collection interface is a factory method. Concrete collection classes decide which concrete iterator to create and return.