Iterator Pattern Use Cases and Examples in TypeScript

6.4.4 Use Cases and Examples

The Iterator Pattern is a powerful design pattern that provides a way to access elements of a collection sequentially without exposing the underlying representation. In TypeScript, this pattern can be implemented using the built-in iterator protocol, which allows us to create custom iterators for various data structures. In this section, we’ll explore practical scenarios where the Iterator Pattern can be effectively applied, such as iterating over binary trees, implementing pagination, and creating infinite sequences.

Iterating Over a Binary Tree

Binary trees are hierarchical data structures that are widely used in computer science for various applications, including search trees and heaps. Traversing a binary tree can be done in several orders, such as in-order, pre-order, and post-order. The Iterator Pattern allows us to encapsulate these traversal algorithms and provide a consistent interface for iterating over the tree.

In-Order Traversal

In-order traversal of a binary tree visits the left subtree, the root node, and then the right subtree. This order is particularly useful for binary search trees, as it visits nodes in ascending order.

 1class TreeNode<T> {
 2    value: T;
 3    left: TreeNode<T> | null = null;
 4    right: TreeNode<T> | null = null;
 5
 6    constructor(value: T) {
 7        this.value = value;
 8    }
 9}
10
11class InOrderIterator<T> implements Iterator<T> {
12    private stack: TreeNode<T>[] = [];
13    private current: TreeNode<T> | null;
14
15    constructor(root: TreeNode<T> | null) {
16        this.current = root;
17    }
18
19    next(): IteratorResult<T> {
20        while (this.current || this.stack.length > 0) {
21            while (this.current) {
22                this.stack.push(this.current);
23                this.current = this.current.left;
24            }
25            this.current = this.stack.pop()!;
26            const value = this.current.value;
27            this.current = this.current.right;
28            return { value, done: false };
29        }
30        return { value: undefined, done: true };
31    }
32}
33
34// Usage
35const root = new TreeNode<number>(10);
36root.left = new TreeNode<number>(5);
37root.right = new TreeNode<number>(15);
38
39const iterator = new InOrderIterator(root);
40let result = iterator.next();
41while (!result.done) {
42    console.log(result.value);
43    result = iterator.next();
44}

Pre-Order and Post-Order Traversals

Similarly, we can implement pre-order and post-order iterators by adjusting the order in which nodes are visited.

Implementing Pagination

Pagination is a common requirement when dealing with large datasets or API results. The Iterator Pattern can be used to abstract the logic of retrieving and iterating over paginated data.

 1class PaginatedIterator<T> implements Iterator<T> {
 2    private data: T[];
 3    private currentIndex: number = 0;
 4    private pageSize: number;
 5
 6    constructor(data: T[], pageSize: number) {
 7        this.data = data;
 8        this.pageSize = pageSize;
 9    }
10
11    next(): IteratorResult<T> {
12        if (this.currentIndex < this.data.length) {
13            const value = this.data[this.currentIndex];
14            this.currentIndex++;
15            return { value, done: false };
16        } else {
17            return { value: undefined, done: true };
18        }
19    }
20
21    reset(): void {
22        this.currentIndex = 0;
23    }
24}
25
26// Usage
27const data = Array.from({ length: 100 }, (_, i) => i + 1);
28const pageSize = 10;
29const iterator = new PaginatedIterator(data, pageSize);
30
31let result = iterator.next();
32while (!result.done) {
33    console.log(result.value);
34    result = iterator.next();
35}

Creating Infinite Sequences

Infinite sequences, such as the Fibonacci series, can be elegantly implemented using generators in TypeScript. Generators provide a convenient way to create iterators with complex logic.

 1function* fibonacci(): Generator<number> {
 2    let [prev, curr] = [0, 1];
 3    while (true) {
 4        yield curr;
 5        [prev, curr] = [curr, prev + curr];
 6    }
 7}
 8
 9// Usage
10const fibIterator = fibonacci();
11console.log(fibIterator.next().value); // 1
12console.log(fibIterator.next().value); // 1
13console.log(fibIterator.next().value); // 2
14console.log(fibIterator.next().value); // 3
15console.log(fibIterator.next().value); // 5

Benefits of the Iterator Pattern

The Iterator Pattern offers several benefits, particularly in terms of abstraction and code readability:

• Encapsulation: By encapsulating the traversal logic within iterators, we can change the underlying data structure or traversal algorithm without affecting client code.
• Consistency: Iterators provide a consistent interface for accessing elements, making it easier to work with different data structures.
• Readability: Using iterators can make code more readable by abstracting complex traversal logic into simple, reusable components.

Encouragement to Implement Custom Iterators

When working with complex or non-standard collections, consider implementing custom iterators. This approach can greatly enhance the flexibility and maintainability of your code. By defining a clear iteration protocol, you can separate the logic of how elements are accessed from the details of how they are stored.

Visualizing Iteration Over a Binary Tree

To better understand the concept of iterating over a binary tree, let’s visualize the process using a diagram. Below is a representation of an in-order traversal of a binary tree:

    graph TD;
	    A["Root: 10"] --> B["Left: 5"];
	    A --> C["Right: 15"];
	    B --> D["Left: 3"];
	    B --> E["Right: 7"];
	    C --> F["Left: 13"];
	    C --> G["Right: 17"];

In this diagram, the in-order traversal would visit the nodes in the following sequence: 3, 5, 7, 10, 13, 15, 17.

Try It Yourself

To deepen your understanding of the Iterator Pattern, try modifying the examples provided:

• Implement a pre-order and post-order iterator for the binary tree.
• Extend the PaginatedIterator to support fetching additional pages from an API.
• Create a generator for another infinite sequence, such as prime numbers.

References and Links

For further reading on iterators and generators in TypeScript, consider the following resources:

• MDN Web Docs: Iterators and Generators
• TypeScript Handbook: Iterators and Generators

Knowledge Check

Before moving on, let’s reinforce what we’ve learned:

• What are the advantages of using the Iterator Pattern?
• How can generators be used to create infinite sequences?
• Why is encapsulating traversal logic within iterators beneficial?

Remember, mastering design patterns like the Iterator Pattern can greatly enhance your ability to write clean, maintainable code. Keep experimenting, stay curious, and enjoy the journey!

Quiz Time!