Iterator Pattern

Understanding the Iterator Pattern

The Iterator pattern is a behavioral design pattern that provides a way to access the elements of a collection object sequentially without exposing its underlying representation. It separates the traversal algorithm from the data structure, allowing for multiple ways to iterate over the same collection.

Problem

Imagine you have a custom collection class (like a tree structure, graph, or specialized list) and you want to provide a way for clients to access its elements without exposing the internal structure. Additionally, you might want to support different traversal methods (like depth-first vs breadth-first for trees) without cluttering the collection class with traversal code.

Traditionally, collection classes have provided methods for accessing elements, but this approach has several issues:

• Collection classes become bloated with traversal methods
• Adding new traversal methods requires modifying the collection class
• Clients need to know too much about the collection's internal structure
• It's difficult to maintain multiple concurrent traversals on the same collection

Solution

The Iterator pattern suggests extracting the traversal behavior of a collection into a separate object called an iterator. This iterator defines a standard interface for accessing collection elements sequentially, typically with methods like hasNext() and next().

The collection provides a method for creating an iterator object, allowing clients to use that iterator to traverse the elements. This separation enables multiple iterators to operate independently on the same collection, even supporting different traversal algorithms.

Structure

Participants

• Iterator: Interface that defines methods for traversing a collection (typically hasNext() and next()).
• Concrete Iterator: Implements the Iterator interface for a specific collection type. Keeps track of the current position in the traversal.
• Aggregate: Interface that defines a method for creating an Iterator object.
• Concrete Aggregate: Implements the Aggregate interface and returns an instance of the appropriate concrete iterator.

When to Use

Use the Iterator Pattern when:

• You want to access a collection's contents without exposing its internal structure
• You want to support multiple traversals of the same collection
• You want to provide a uniform interface for traversing different collection types
• You need to support different traversal algorithms for the same collection

Benefits

• Single Responsibility Principle: You can clean up the client code and collections by extracting traversal algorithms into separate classes.
• Open/Closed Principle: You can implement new types of collections and iterators without changing existing code.
• Simplified Client Code: Clients use a simple interface to traverse collections, regardless of their complexity.
• Parallel Iteration: You can have multiple iterators on the same collection simultaneously.
• Delayed/Lazy Iteration: Iterators calculate the next element only when it's requested, supporting infinite collections or lazy loading.

Real-World Uses

• Collection Frameworks: Most modern programming languages implement the Iterator pattern in their collection libraries (e.g., Java's Iterator interface, JavaScript's Iterators and Generators, Python's Iterators).
• Database Cursors: Database query results are often traversed using cursor objects that implement an iterator-like interface.
• File Systems: Directory traversal using iterators to navigate through file structures.
• UI Components: Traversing items in composite UI structures like trees and lists.
• Stream Processing: Processing large datasets in a streaming fashion where iterators provide elements on demand.

Implementation Example

Here's a JavaScript implementation of the Iterator pattern for different types of collections:

// Iterator Interface (implicit in JavaScript)
// - hasNext(): boolean
// - next(): Element

// Concrete Iterator for Array
class ArrayIterator {
    constructor(array) {
        this.array = array;
        this.index = 0;
    }
    
    hasNext() {
        return this.index < this.array.length;
    }
    
    next() {
        if (this.hasNext()) {
            return this.array[this.index++];
        }
        return null;
    }
    
    // Additional methods that could be useful
    reset() {
        this.index = 0;
    }
    
    current() {
        return this.array[this.index];
    }
}

// Concrete Iterator for TreeNode (depth-first)
class DepthFirstIterator {
    constructor(rootNode) {
        this.stack = [rootNode];
        this.visited = new Set();
    }
    
    hasNext() {
        return this.stack.length > 0;
    }
    
    next() {
        if (!this.hasNext()) {
            return null;
        }
        
        const node = this.stack.pop();
        this.visited.add(node);
        
        // Add children in reverse order so they'll be processed in the correct order
        if (node.children) {
            for (let i = node.children.length - 1; i >= 0; i--) {
                const child = node.children[i];
                if (!this.visited.has(child)) {
                    this.stack.push(child);
                }
            }
        }
        
        return node;
    }
}

// Concrete Collection implementing Aggregate
class Collection {
    constructor(items = []) {
        this.items = items;
    }
    
    // Factory method that creates an iterator
    createIterator() {
        return new ArrayIterator(this.items);
    }
    
    // Collection-specific methods
    add(item) {
        this.items.push(item);
    }
    
    remove(item) {
        const index = this.items.indexOf(item);
        if (index >= 0) {
            this.items.splice(index, 1);
        }
    }
}

// Example Tree structure
class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
    
    addChild(child) {
        this.children.push(child);
        return this;
    }
    
    // Factory method that creates a depth-first iterator
    createIterator() {
        return new DepthFirstIterator(this);
    }
}

// Client code
function clientCode() {
    console.log("Iterating through a collection:");
    const collection = new Collection([10, 20, 30, 40, 50]);
    const iterator = collection.createIterator();
    
    while (iterator.hasNext()) {
        console.log(iterator.next());
    }
    
    console.log("\nIterating through a tree structure (depth-first):");
    const root = new TreeNode('A');
    root.addChild(new TreeNode('B'))
        .addChild(new TreeNode('C'));
    
    root.children[0].addChild(new TreeNode('D'))
                    .addChild(new TreeNode('E'));
    root.children[1].addChild(new TreeNode('F'));
    
    const treeIterator = root.createIterator();
    while (treeIterator.hasNext()) {
        const node = treeIterator.next();
        console.log(node.value);
    }
}

clientCode();

In this example:

• We've defined two iterator classes: ArrayIterator for simple arrays and DepthFirstIterator for tree structures.
• The Collection class implements a method createIterator() that returns an iterator object specialized for that collection.
• The TreeNode class also provides a method to create its own specialized iterator that traverses the tree in depth-first order.
• The client code uses the iterators without knowing the internal structure of the collections, simply calling hasNext() and next().

This implementation showcases how the Iterator pattern allows different traversal strategies to be encapsulated in iterator objects, keeping the collections cleaner and client code simpler.