Quartz 4

16. Iterator Pattern

13 min read

This article is entirely based on a YouTube video by Christopher Okhravi. The original book was not consulted for this design pattern.

Intro

The Iterator Pattern is a design pattern focused on enumerating and traversing the items within a collection (traversing in Data Structure means systematically visiting every element of it; it’s a process in which each element of a data structure is accessed). A collection is a container for a group of items, which can be defined as anything, such as a bag of marbles, a pile of stones, a family tree, or a class of students. Most applications extensively use collections of some sort. For instance, in a video game, you might have a collection of enemies, or a magician might have a collection of spells.

The core idea of the Iterator pattern is to separate the concerns of data storage from data traversal. This aligns with the Single Responsibility Principle from the SOLID object-oriented design principles. The Single Responsibility Principle states that a class or module should have only one reason to change, meaning it should have only one responsibility.

In this context, the responsibility of a collection is to manage and store its items. The responsibility of iterating over or traversing these items is a separate concern. For example, if you have a World class in a game that contains a collection of enemies, the World class has its own responsibilities. However, you might also want to iterate over the collection of enemies to perform an action on each one, such as applying a boost or moving them. The notion of enumeration is as simple as running a “for each” loop over all the items in the collection.

The central concept is that when the users (not the collection author) want to iterate through a collection from the outside, they shouldn’t have to concern themselves with the collection’s internal structure. They should be able to simply say, “Give me each item one by one, sequentially.”

Benefits of the Iterator Pattern

The Iterator pattern provides several key benefits:

  1. Uniform Traversal: It provides a uniform interface for iterating over different types of collections. This means you can use the same code to iterate over a list, a tree, or any other data structure, regardless of its underlying implementation. For example, if you have a List and a LinkedList, you can iterate over both using the same methods because they implement the same Iterable interface. This is a crucial concept that is now standard in many modern programming languages like Java and C#. However, the pattern’s value extends beyond built-in collections. It allows you to create your own custom, complex data structures—like a House class with a two-dimensional array of windows—and provide a consistent way to iterate over its elements without exposing its internal structure.
  2. Information Hiding and Encapsulation: The Iterator pattern promotes encapsulation by hiding the internal representation of the collection. When you use an iterator, you aren’t given the entire collection at once. Instead, you get one item at a time and then ask for the next one. This prevents external code from inadvertently modifying the collection’s contents, a common danger when passing collections by reference.
  3. Lazy Evaluation and Infinite Collections: The pattern supports lazy evaluation, meaning items are only processed when requested. This is particularly useful for handling very large or even infinite collections. For example, you could create an iterator for a mathematical sequence like the Fibonacci sequence, which is, by definition, infinite. The iterator would produce the next number only when asked, without needing to pre-compute and store the entire sequence.
  4. Preserving Iteration State: An iterator object can maintain its state, allowing you to pause an iteration and resume it later from the same point. This is like a cursor or a pointer that remembers its current position. This is more powerful than a simple for loop with an index. An excellent example of this is a game inventory spinner. You can press “next” to move the cursor to the next item, “previous” to go back, and always know which item you are currently on.

The Iterator in Practice

While modern languages often provide syntactic sugar like the for each loop, which simplifies iteration, the underlying mechanism is the Iterator pattern.

A class that is “iterable” (or “enumerable” in C#) has a method that returns an iterator object.

A classic implementation without the syntactic sugar looks like this:

House h = new House();
Iterator<Item> i = h.getIterator();
while (i.hasNext()) {
    Item currentItem = i.next();
    // do something with currentItem
}

This code explicitly asks the collection (h for a house) for an iterator object. The while loop then continues as long as the iterator has a next item. The next() method moves the internal pointer to the next item and returns it, making the process of traversal explicit and controlled.

This approach demonstrates how the iterator remembers its location and allows for flexible traversal, which is a significant advantage over simply returning a flat list. It separates the concerns of the collection from the process of traversing its elements, a testament to its value as a design pattern.

Definition in words

The Iterator pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

This definition comes from the book Design Patterns: Elements of Reusable Object-Oriented Software, often referred to as the “Gang of Four” book.

What is an “Aggregate Object”?

An aggregate object is simply an object that contains or holds a number of other objects. The author provides several examples:

  • A forest that contains animals.
  • A family tree that contains people.
  • A house that contains pieces (like windows, doors, and a roof).
  • A wizard that contains apples.

Core Tenets of the Definition

  • Sequential Access: The pattern’s goal is to access these elements one after the other, in a defined sequence. You get the first item, then the next, then the next, and so on.
  • Without Exposing the Underlying Representation: The user of the iterator should not need to know or care about how the aggregate object is internally structured. For example, the House object could store its windows in a simple list, a two-dimensional array, or any other complex data structure, but the iterator would still provide the same simple sequential access. This principle of information hiding is crucial to the pattern’s usefulness. It ensures that the way you traverse the data is decoupled from the data’s internal organization.

Definition in UML

The Iterator pattern’s structure can be represented with a Unified Modeling Language (UML) diagram. It consists of four main components:

Let’s explore all of them:

  • Iterable (or Aggregate / Enumerable): This is the interface for the collection of objects. It’s the “thing that contains things,” like a House or a Forest. It declares a method, getIterator(), that returns an object of type Iterator.
  • ConcreteIterable: This is the concrete class that implements the Iterable interface. Examples include House, Tree, or Forest. Because different concrete iterables have different internal data structures (e.g., a House might use a 2D array for windows, while a Tree might be a node-based structure), each concrete iterable must provide its own specific implementation for getIterator().
  • Iterator: This is the interface for traversing the collection. It defines the core methods for iteration, which are implemented by concrete iterators. It’s a unified interface that allows clients to use different iterators interchangeably.
  • ConcreteIterator: This is the concrete class that implements the Iterator interface. It is responsible for tracking the current position within its specific ConcreteIterable and providing access to the next element.

A Client is the user of the pattern. The client uses both the Iterable and the Iterator. It first gets an Iterable (e.g., an instance of House), then calls its getIterator() method to obtain an Iterator object. The client then uses the iterator to traverse the collection.

Key Methods and Relationships

The Iterator interface typically defines at least three methods:

  • hasNext(): Returns a boolean to indicate whether there are more elements to traverse. This method is a query; it asks a question about the iterator’s state without changing it.
  • next(): This is a void method that advances the iterator’s internal pointer to the next element. It is a command because it changes the state of the iterator.
  • current(): Returns the Item at the iterator’s current position. This is another query.

In principle, you could even merge some of these three methods (hasNext() with next() or current() with next()), but this separation of methods into queries and commands aligns with the Command-Query Separation principle, which suggests that a method should either change an object’s state (a command) or return a result (a query), but not both. This helps to prevent confusing side effects. For example, if hasNext() also moved the pointer, a client could get a misleading result.

The UML diagram also shows a key relationship: ConcreteIterables construct ConcreteIterators. The getIterator() method on a ConcreteIterable acts as a Factory Method, creating and returning a specific ConcreteIterator instance.

Furthermore, a ConcreteIterator may have a reference back to its ConcreteIterable. This is because the iterator often needs access to the underlying collection to traverse it. For example, when a ConcreteIterable (House) creates a ConcreteIterator, it might pass a reference to itself to the iterator’s constructor. This way, the iterator has the necessary context to perform its work.

Real-World Example: Game Inventory Systems

The Iterator pattern is highly valuable for designing complex systems where different data structures are needed for different parts of an application. Consider a game with various inventory types for a player:

  • Hand-based Inventory: This could hold a limited number of items, perhaps just one in the right hand and one in the left. This might be modeled with a simple array or a fixed-size data structure.
  • Backpack Inventory: This could be limited by weight, not just the number of items. A more complex data structure, like a hash table for fast lookups or a specialized list, might be more appropriate to efficiently manage item weights and capacities.
  • Magic Inventory: A more absurd example, like one that only ever contains apples. This could be an infinite, lazily evaluated list.

Each of these inventories has a different internal structure to meet its specific requirements. Without the Iterator pattern, a client would need to write different traversal code for each inventory type. However, by using the Iterator pattern, all three inventories can implement the same Iterable interface, and each would return a ConcreteIterator that knows how to traverse its specific internal structure. The client can then use the same generic iteration code (for each loop) for all of them, regardless of their underlying complexity. This exemplifies the power of the pattern in enabling uniform access to diverse data structures.

UML applied to an example

In the game example, the Iterator pattern enables us to treat different inventory types uniformly. This allows the client (the game’s code) to interact with them in a consistent way, regardless of their specific internal data structures.

Mapping the Game Example to the UML Diagram

Here’s an example of UML components and their corresponding elements in a game:

  • UML Component: Iterable. This is the interface that defines a collection of game items. All types of inventories will implement this interface. It would contain the getIterator() method.
    • Game Example: Inventory
  • UML Component: ConcreteIterable. These are the specific classes that implement the Inventory interface. Each has a different internal structure tailored to its requirements (e.g., HandheldInventory is a fixed size, while BackpackInventory is weight-based).
    • Game Example: HandheldInventory, BackpackInventory, MagicInventory,  `HomeInventory
  • UML Component: Iterator. This is the interface that defines the methods for traversing game items. It would include hasNext(), next(), and a method to get the current item.
    • Game Example: InventoryIterator
  • UML Component: ConcreteIterator. These are the specific classes that implement the InventoryIteratorinterface. A HandheldInventory would create a HandheldIterator, and a BackpackInventory would create a BackpackIterator. Each concrete iterator knows how to navigate its corresponding inventory’s unique data structure.
    • Game Example: HandheldIterator, BackpackIterator

The Item Type

The thing being iterated over is an Item. This would be a shared interface or supertype for all the things in the inventories, such as valuables, food, or other objects in the game. An alternative is to use a more specific name like GameItem or UsableItem which would make the system more intuitive and ensure that all items within an inventory share a common capability.

By applying the Iterator pattern, a game’s UI could first iterate through a HandheldInventory to display items in the player’s hands, then continue iterating through a BackpackInventory to display the rest. This uniform access is a crucial benefit for displaying all items on the same screen or for any other operation that needs to process all items in a player’s possession.

Code Example

Let’s look at a short example of the Iterator pattern applied to our game scenario. The goal is to show how the pattern allows us to iterate over a specific HandheldInventory in a generic, or polymorphic, manner.

The Inventory and HandheldInventory Classes

First, we define an Inventory interface that all inventories must implement. This interface contains a single method: getIterator(), which returns an InventoryIterator.

interface IInventory {
    IInventoryIterator getIterator();
}

Next, we create the concrete HandheldInventory class. This class holds two items, one for the right hand and one for the left. It implements the IInventory interface.

class HandheldInventory : IInventory {
    public IItem RightHand { get; private set; }
    public IItem LeftHand { get; private set; }
 
    public HandheldInventory(IItem right, IItem left) {
        this.RightHand = right;
        this.LeftHand = left;
    }
 
    public IInventoryIterator getIterator() {
        return new HandheldInventoryIterator(this);
    }
}

The key part is the getIterator() method. It acts as a factory method, creating a new HandheldInventoryIteratorand passing itself (this) to the iterator’s constructor. This is how the iterator gets a reference to the specific inventory it needs to traverse.

The InventoryIterator and HandheldInventoryIterator Classes

The InventoryIterator is an interface that defines the contract for iteration. It specifies the three methods we discussed: IsDone(), Next(), and Current().

interface IInventoryIterator {
    bool IsDone();
    void Next();
    IItem Current();
}

Finally, we have the HandheldInventoryIterator class, which implements the IInventoryIterator interface. It keeps a reference to the HandheldInventory instance it’s iterating over and an index to track its position.

class HandheldInventoryIterator : IInventoryIterator {
    private HandheldInventory inventory;
    private int index;
 
    public HandheldInventoryIterator(HandheldInventory inv) {
        this.inventory = inv;
        this.index = 0; // The iterator starts at index 0.
    }
 
    public bool IsDone() {
        return index >= 2;
    }
 
    public void Next() {
        if (!IsDone()) {
            this.index++;
        }
    }
 
    public IItem Current() {
        switch (index) {
            case 0:
                return inventory.RightHand;
            case 1:
                return inventory.LeftHand;
            default:
                return null;
        }
    }
}

The HandheldInventoryIterator’s methods use the index variable to provide sequential access to the HandheldInventory’s items.

Putting It All Together: The Client Code

The true benefit of this pattern is seen in the client code. A method that needs to process all inventory items can be written in a polymorphic way, so it works for any type of inventory.

void ProcessAllInventoryItems(IInventory inventory) {
    IInventoryIterator iterator = inventory.getIterator();
 
    while (!iterator.IsDone()) {
        IItem currentItem = iterator.Current();
        // Do something cool with the current item
        // e.g., display it on the screen
        Console.WriteLine($"Processing item: {currentItem.Name}");
 
        iterator.Next();
    }
}
 
// Example usage with a HandheldInventory
HandheldInventory myHandheldInv = new HandheldInventory(new Sword(), new Shield());
ProcessAllInventoryItems(myHandheldInv); // This method works with any IInventory.
 
// It would also work with a BackpackInventory or any other inventory type
// without any changes to the ProcessAllInventoryItems method.
BackpackInventory myBackpackInv = new BackpackInventory(someItems);
ProcessAllInventoryItems(myBackpackInv);

As you can see, the ProcessAllInventoryItems method doesn’t need to know if it’s dealing with a HandheldInventory or a BackpackInventory. It only interacts with the abstract IInventory interface and its corresponding IInventoryIterator. This showcases the power of the Iterator pattern in providing a uniform way to access the elements of different aggregate objects without exposing their underlying representations.

Graph View