Episode 9 — System Design / 9.5 — Behavioral Design Patterns

9.5.d Iterator Pattern

Overview

The Iterator Pattern provides a way to access the elements of a collection sequentially without exposing its underlying representation. It extracts the traversal behavior into a separate object called an iterator.

JavaScript has this pattern built into the language through the Iteration Protocol (Symbol.iterator), for...of loops, and generator functions.

+--------------------------------------------------------------+
|                     ITERATOR PATTERN                          |
|                                                               |
|  Collection                   Iterator                        |
|  +-----------------+         +------------------+             |
|  |  [a, b, c, d]  |-------->|  - current: 0    |             |
|  |                 | creates |                  |             |
|  | [Symbol.iterator]()       |  + next()        |             |
|  +-----------------+         |    { value, done }|             |
|                              |                  |             |
|                              |  + return()      |             |
|                              |  (cleanup)       |             |
|                              +------------------+             |
|                                                               |
|  for (const item of collection) { ... }                       |
|  // Uses the iterator protocol under the hood                 |
+--------------------------------------------------------------+

JavaScript Iteration Protocol

+------------------------------------------------------------------+
|  ITERABLE PROTOCOL                                                |
|                                                                    |
|  An object is "iterable" if it has a [Symbol.iterator]() method   |
|  that returns an ITERATOR.                                         |
|                                                                    |
|  ITERATOR PROTOCOL                                                |
|                                                                    |
|  An "iterator" is an object with a next() method that returns:     |
|    { value: <any>, done: <boolean> }                              |
|                                                                    |
|  Built-in iterables in JavaScript:                                 |
|  - Arrays                                                          |
|  - Strings                                                         |
|  - Maps                                                            |
|  - Sets                                                            |
|  - NodeLists (DOM)                                                 |
|  - TypedArrays                                                     |
|  - arguments object                                                |
|  - Generator objects                                               |
+------------------------------------------------------------------+

// How for...of works under the hood:
const arr = [10, 20, 30];

// This:
for (const value of arr) {
  console.log(value);
}

// Is equivalent to this:
const iterator = arr[Symbol.iterator]();
let result = iterator.next();
while (!result.done) {
  console.log(result.value);  // 10, 20, 30
  result = iterator.next();
}

Implementation 1: Custom Iterable Collection

// ============================================
// CUSTOM RANGE: Iterable number range
// ============================================
class Range {
  constructor(start, end, step = 1) {
    if (step === 0) throw new Error('Step cannot be zero');
    this.start = start;
    this.end = end;
    this.step = step;
  }

  // Makes this object iterable (usable with for...of)
  [Symbol.iterator]() {
    let current = this.start;
    const end = this.end;
    const step = this.step;

    return {
      next() {
        if ((step > 0 && current <= end) || (step < 0 && current >= end)) {
          const value = current;
          current += step;
          return { value, done: false };
        }
        return { value: undefined, done: true };
      },

      // Optional: called when iterator is abandoned early (break, return, throw)
      return() {
        console.log('[Range] Iterator closed early');
        return { value: undefined, done: true };
      }
    };
  }

  // Utility: convert to array
  toArray() {
    return [...this];
  }

  // Utility: count without creating an array
  count() {
    let n = 0;
    for (const _ of this) n++;
    return n;
  }
}

// ============================================
// USAGE
// ============================================
const range = new Range(1, 10);

// for...of
for (const num of range) {
  process.stdout.write(`${num} `);
}
// Output: 1 2 3 4 5 6 7 8 9 10

console.log();

// Spread operator
console.log([...new Range(0, 20, 5)]);
// [0, 5, 10, 15, 20]

// Destructuring
const [a, b, c] = new Range(100, 500, 100);
console.log(a, b, c);  // 100 200 300

// Countdown
for (const n of new Range(5, 1, -1)) {
  console.log(`${n}...`);
}
// 5... 4... 3... 2... 1...

// Works with Array.from
console.log(Array.from(new Range(1, 5)));
// [1, 2, 3, 4, 5]

Implementation 2: Linked List Iterator

// ============================================
// LINKED LIST with Iterator
// ============================================
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  append(value) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
    return this;
  }

  prepend(value) {
    const node = new ListNode(value);
    node.next = this.head;
    this.head = node;
    if (!this.tail) this.tail = node;
    this.size++;
    return this;
  }

  // Forward iterator
  [Symbol.iterator]() {
    let current = this.head;

    return {
      next() {
        if (current) {
          const value = current.value;
          current = current.next;
          return { value, done: false };
        }
        return { value: undefined, done: true };
      }
    };
  }

  // Reverse iterator (using a stack)
  reverse() {
    const self = this;
    return {
      [Symbol.iterator]() {
        // Collect all values first (LinkedList doesn't have back pointers)
        const values = [];
        let current = self.head;
        while (current) {
          values.push(current.value);
          current = current.next;
        }

        let index = values.length - 1;
        return {
          next() {
            if (index >= 0) {
              return { value: values[index--], done: false };
            }
            return { value: undefined, done: true };
          }
        };
      }
    };
  }

  // Filtered iterator
  filter(predicate) {
    const self = this;
    return {
      [Symbol.iterator]() {
        let current = self.head;
        return {
          next() {
            while (current) {
              const value = current.value;
              current = current.next;
              if (predicate(value)) {
                return { value, done: false };
              }
            }
            return { value: undefined, done: true };
          }
        };
      }
    };
  }

  toString() {
    return [...this].join(' -> ');
  }
}

// ============================================
// USAGE
// ============================================
const list = new LinkedList();
list.append(10).append(20).append(30).append(40).append(50);

// Standard iteration
console.log('Forward:', [...list]);           // [10, 20, 30, 40, 50]
console.log('Reverse:', [...list.reverse()]); // [50, 40, 30, 20, 10]
console.log('Evens:', [...list.filter(n => n % 20 === 0)]); // [20, 40]

// for...of
for (const value of list) {
  console.log(value);
}

// Destructuring
const [first, second, ...rest] = list;
console.log(first, second, rest);  // 10 20 [30, 40, 50]

// String representation
console.log(list.toString());  // "10 -> 20 -> 30 -> 40 -> 50"

Implementation 3: Generator Functions

Generator functions provide a simpler syntax for creating iterators using the function* and yield keywords.

// ============================================
// GENERATOR BASICS
// ============================================

// Simple generator
function* countdown(n) {
  while (n > 0) {
    yield n;
    n--;
  }
}

for (const num of countdown(5)) {
  console.log(num);  // 5, 4, 3, 2, 1
}

// Infinite generator (lazy!)
function* fibonacci() {
  let a = 0, b = 1;
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

// Take first 10 fibonacci numbers
function take(iterator, n) {
  const result = [];
  for (const value of iterator) {
    result.push(value);
    if (result.length >= n) break;
  }
  return result;
}

console.log(take(fibonacci(), 10));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// ============================================
// GENERATOR-BASED ITERATORS FOR COMPLEX STRUCTURES
// ============================================

// Tree traversal using generators
class TreeNode {
  constructor(value, children = []) {
    this.value = value;
    this.children = children;
  }

  // Depth-first traversal
  *[Symbol.iterator]() {
    yield this.value;
    for (const child of this.children) {
      yield* child;  // delegate to child's iterator
    }
  }

  // Breadth-first traversal
  *breadthFirst() {
    const queue = [this];
    while (queue.length > 0) {
      const node = queue.shift();
      yield node.value;
      queue.push(...node.children);
    }
  }

  // Depth-first with level info
  *depthFirst(level = 0) {
    yield { value: this.value, level };
    for (const child of this.children) {
      yield* child.depthFirst(level + 1);
    }
  }
}

// Build a tree
const tree = new TreeNode('root', [
  new TreeNode('A', [
    new TreeNode('A1'),
    new TreeNode('A2'),
  ]),
  new TreeNode('B', [
    new TreeNode('B1', [
      new TreeNode('B1a'),
      new TreeNode('B1b'),
    ]),
  ]),
  new TreeNode('C'),
]);

console.log('DFS:', [...tree]);
// ['root', 'A', 'A1', 'A2', 'B', 'B1', 'B1a', 'B1b', 'C']

console.log('BFS:', [...tree.breadthFirst()]);
// ['root', 'A', 'B', 'C', 'A1', 'A2', 'B1', 'B1a', 'B1b']

for (const { value, level } of tree.depthFirst()) {
  console.log(`${'  '.repeat(level)}${value}`);
}
// root
//   A
//     A1
//     A2
//   B
//     B1
//       B1a
//       B1b
//   C

Implementation 4: Lazy Evaluation Pipelines

// ============================================
// LAZY ITERABLE OPERATORS
// ============================================
class LazyIterable {
  constructor(source) {
    this.source = source;
  }

  static from(iterable) {
    return new LazyIterable(iterable);
  }

  static range(start, end, step = 1) {
    return new LazyIterable({
      *[Symbol.iterator]() {
        for (let i = start; step > 0 ? i <= end : i >= end; i += step) {
          yield i;
        }
      }
    });
  }

  static infinite(startOrFn = 0) {
    if (typeof startOrFn === 'function') {
      return new LazyIterable({
        *[Symbol.iterator]() {
          let i = 0;
          while (true) yield startOrFn(i++);
        }
      });
    }
    return new LazyIterable({
      *[Symbol.iterator]() {
        let i = startOrFn;
        while (true) yield i++;
      }
    });
  }

  // Lazy map: transforms each element
  map(fn) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        let index = 0;
        for (const item of source) {
          yield fn(item, index++);
        }
      }
    });
  }

  // Lazy filter: only yields matching elements
  filter(predicate) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        let index = 0;
        for (const item of source) {
          if (predicate(item, index++)) {
            yield item;
          }
        }
      }
    });
  }

  // Lazy take: limits the number of elements
  take(n) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        let count = 0;
        for (const item of source) {
          if (count >= n) return;
          yield item;
          count++;
        }
      }
    });
  }

  // Lazy skip: skips first n elements
  skip(n) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        let count = 0;
        for (const item of source) {
          if (count >= n) {
            yield item;
          }
          count++;
        }
      }
    });
  }

  // Lazy takeWhile: yields while predicate is true
  takeWhile(predicate) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        for (const item of source) {
          if (!predicate(item)) return;
          yield item;
        }
      }
    });
  }

  // Lazy flatMap
  flatMap(fn) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        for (const item of source) {
          yield* fn(item);
        }
      }
    });
  }

  // Lazy zip: combines two iterables
  zip(other) {
    const source = this.source;
    return new LazyIterable({
      *[Symbol.iterator]() {
        const iter1 = source[Symbol.iterator]();
        const iter2 = other[Symbol.iterator]();
        while (true) {
          const a = iter1.next();
          const b = iter2.next();
          if (a.done || b.done) return;
          yield [a.value, b.value];
        }
      }
    });
  }

  // Terminal operations (these consume the iterator)

  toArray() {
    return [...this.source];
  }

  forEach(fn) {
    let index = 0;
    for (const item of this.source) {
      fn(item, index++);
    }
  }

  reduce(fn, initial) {
    let acc = initial;
    for (const item of this.source) {
      acc = fn(acc, item);
    }
    return acc;
  }

  first() {
    for (const item of this.source) {
      return item;
    }
    return undefined;
  }

  count() {
    let n = 0;
    for (const _ of this.source) n++;
    return n;
  }

  // Make LazyIterable itself iterable
  [Symbol.iterator]() {
    return this.source[Symbol.iterator]();
  }
}

// ============================================
// USAGE: Lazy pipeline
// ============================================

// Process an infinite sequence lazily
const result = LazyIterable
  .infinite(0)           // 0, 1, 2, 3, 4, 5, ...  (infinite!)
  .filter(n => n % 2 === 0)  // 0, 2, 4, 6, 8, ...     (still infinite)
  .map(n => n * n)            // 0, 4, 16, 36, 64, ...  (still infinite)
  .skip(2)                    // 16, 36, 64, 100, ...    (still infinite)
  .take(5)                    // 16, 36, 64, 100, 144   (finite now)
  .toArray();                 // Actually evaluate

console.log(result);  // [16, 36, 64, 100, 144]
// Only 5 values were ever computed! Not millions.

// Fibonacci numbers less than 100
const fibs = LazyIterable
  .from({ *[Symbol.iterator]() {
    let a = 0, b = 1;
    while (true) {
      yield a;
      [a, b] = [b, a + b];
    }
  }})
  .takeWhile(n => n < 100)
  .toArray();

console.log(fibs);  // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

// Zip names with indices
const names = ['Alice', 'Bob', 'Charlie'];
const indexed = LazyIterable
  .from(names)
  .zip(LazyIterable.infinite(1))
  .toArray();

console.log(indexed);  // [['Alice', 1], ['Bob', 2], ['Charlie', 3]]

Implementation 5: Pagination Iterator

// ============================================
// ASYNC PAGINATION ITERATOR
// ============================================
class PaginatedAPI {
  constructor(baseUrl, pageSize = 10) {
    this.baseUrl = baseUrl;
    this.pageSize = pageSize;
  }

  // Async iterable protocol
  [Symbol.asyncIterator]() {
    let page = 1;
    let hasMore = true;
    const self = this;

    return {
      async next() {
        if (!hasMore) {
          return { value: undefined, done: true };
        }

        try {
          console.log(`[API] Fetching page ${page}...`);
          const response = await self._fetchPage(page);

          hasMore = response.hasNextPage;
          page++;

          return {
            value: {
              data: response.data,
              page: response.page,
              total: response.total
            },
            done: false
          };
        } catch (error) {
          console.error(`[API] Error fetching page ${page}:`, error);
          return { value: undefined, done: true };
        }
      },

      return() {
        hasMore = false;
        console.log('[API] Pagination stopped');
        return { value: undefined, done: true };
      }
    };
  }

  // Simulate API call
  async _fetchPage(page) {
    await new Promise(r => setTimeout(r, 50));  // Simulate latency

    const totalItems = 47;  // Simulated total
    const start = (page - 1) * this.pageSize;
    const end = Math.min(start + this.pageSize, totalItems);

    if (start >= totalItems) {
      return { data: [], page, total: totalItems, hasNextPage: false };
    }

    const data = Array.from(
      { length: end - start },
      (_, i) => ({
        id: start + i + 1,
        name: `Item ${start + i + 1}`,
        score: Math.random().toFixed(2)
      })
    );

    return {
      data,
      page,
      total: totalItems,
      hasNextPage: end < totalItems
    };
  }

  // Helper: iterate over individual items (not pages)
  items() {
    const paginatedIterator = this[Symbol.asyncIterator]();

    return {
      [Symbol.asyncIterator]() {
        let currentBatch = [];
        let batchIndex = 0;
        let paginationDone = false;

        return {
          async next() {
            // If we have items in current batch, return next one
            if (batchIndex < currentBatch.length) {
              return { value: currentBatch[batchIndex++], done: false };
            }

            // Fetch next page
            if (!paginationDone) {
              const pageResult = await paginatedIterator.next();
              if (pageResult.done || pageResult.value.data.length === 0) {
                paginationDone = true;
                return { value: undefined, done: true };
              }

              currentBatch = pageResult.value.data;
              batchIndex = 1;  // Return first item, advance index
              return { value: currentBatch[0], done: false };
            }

            return { value: undefined, done: true };
          }
        };
      }
    };
  }
}

// ============================================
// USAGE
// ============================================
async function demo() {
  const api = new PaginatedAPI('https://api.example.com/items', 10);

  // Iterate over pages
  console.log('=== Iterating Pages ===');
  for await (const page of api) {
    console.log(`Page ${page.page}: ${page.data.length} items (total: ${page.total})`);

    // Break early if we want
    if (page.page >= 2) {
      console.log('Stopping after page 2');
      break;
    }
  }

  // Iterate over individual items
  console.log('\n=== Iterating Items ===');
  let count = 0;
  for await (const item of api.items()) {
    console.log(`  ${item.id}: ${item.name} (score: ${item.score})`);
    count++;
    if (count >= 5) break;  // Just show first 5 items
  }
}

// demo();

Generator-Based Async Patterns

// ============================================
// ASYNC GENERATOR: Stream processing
// ============================================
async function* streamLines(filePath) {
  // Simulating reading a file line by line
  const lines = [
    'id,name,age',
    '1,Alice,30',
    '2,Bob,25',
    '3,Charlie,35',
    '4,Diana,28'
  ];

  for (const line of lines) {
    await new Promise(r => setTimeout(r, 10));  // Simulate I/O
    yield line;
  }
}

async function* parseCSV(lineIterator) {
  let headers = null;

  for await (const line of lineIterator) {
    const values = line.split(',');

    if (!headers) {
      headers = values;
      continue;  // Skip header row
    }

    const record = {};
    headers.forEach((h, i) => record[h] = values[i]);
    yield record;
  }
}

async function* filterAge(recordIterator, minAge) {
  for await (const record of recordIterator) {
    if (parseInt(record.age) >= minAge) {
      yield record;
    }
  }
}

// Pipeline: stream -> parse -> filter
async function processCSV() {
  const lines = streamLines('data.csv');
  const records = parseCSV(lines);
  const filtered = filterAge(records, 28);

  for await (const record of filtered) {
    console.log(`${record.name} (age ${record.age})`);
  }
  // Alice (age 30)
  // Charlie (age 35)
  // Diana (age 28)
}

// processCSV();

Iterator vs Array Methods

+------------------------------------------------------------------+
|                                                                    |
|  ARRAY METHODS (Eager)              ITERATORS (Lazy)              |
|                                                                    |
|  const result = data               const result = Lazy.from(data) |
|    .filter(x => x > 10)              .filter(x => x > 10)        |
|    .map(x => x * 2)                  .map(x => x * 2)            |
|    .slice(0, 5);                      .take(5)                    |
|                                       .toArray();                  |
|                                                                    |
|  - Creates intermediate arrays      - No intermediate arrays      |
|  - Processes ALL items              - Processes only needed items  |
|  - Data must fit in memory          - Can handle infinite streams  |
|  - Simple, familiar API             - More complex setup           |
|  - Good for small datasets          - Good for large/infinite data |
|                                                                    |
|  When to use eager (Array):         When to use lazy (Iterator):  |
|  - Small arrays (< 10K items)       - Large datasets              |
|  - Need all results                 - Only need first N results    |
|  - Random access needed             - Streaming data               |
|  - Simple transformations           - Infinite sequences           |
|                                     - Memory-constrained           |
+------------------------------------------------------------------+

Key Takeaways

  1. Iterators decouple traversal from data structures -- you can iterate over arrays, linked lists, trees, and APIs with the same for...of syntax
  2. JavaScript's iteration protocol (Symbol.iterator + next()) is the standard way to make objects iterable
  3. Generator functions (function* + yield) provide a clean syntax for creating iterators
  4. Lazy evaluation means values are computed only when requested -- crucial for infinite sequences and large datasets
  5. Async iterators (Symbol.asyncIterator + for await...of) handle pagination, streams, and network data
  6. Compose generators into pipelines -- each stage lazily transforms data from the previous stage

Explain-It Challenge

You're building a search engine that needs to merge results from 5 different data sources (database, cache, external API, file system, CDN). Each source returns results in ranked order. Design an iterator that lazily merges these sources and returns the top K results without fetching all results from all sources. How would you handle: (a) one source being slow, (b) duplicate results across sources, (c) a source returning an error mid-iteration?