# Iterator

> Walk the elements of a collection one at a time through a standard interface, without exposing how the collection stores or fetches them.

- kind: pattern
- category: behavioral
- aliases: Cursor
- canonical: https://aipatterns.dev/design-patterns/iterator
- inspired-by: https://refactoring.guru/design-patterns/iterator

## Intent

Give a collection a separate object that knows how to step through its elements and remembers where it is. Callers ask for the next element until there are none left, and never see whether the data lives in an array, a tree, a file, or a paginated remote API.

## Forces

- **Simple loops for callers** vs **complex storage behind them**: a caller wants `for each invoice`, not cursor tokens and page sizes.
- **Lazy access** vs **loading everything**: fetching ten thousand records to find the first overdue one wastes time and memory.
- **Several traversals at once** vs **position stored in the collection**: if the collection holds the cursor, two loops over it corrupt each other.
- **Hiding the representation** vs **letting callers stop early, filter, or map**: the iteration contract must stay small and still compose.

## Therefore

**Move the traversal state (current position, buffer, cursor) out of the collection into an iterator object that implements the language's standard iteration protocol.**

The collection exposes a factory method that returns a fresh iterator, so each loop gets its own position. Callers use the language's native loop (`for...of`, `for ... in`, `range`, enhanced `for`) and stop whenever they want. In most modern languages you should write the iterator as a generator function (`function*`, `yield`, `iter.Seq`). Write an explicit iterator class only when you need extra methods, explicit resource cleanup, or a language without generators.

## Structure

```mermaid
classDiagram
  class IterableCollection {
    <<interface>>
    +iterator() Iterator
  }
  class Iterator {
    <<interface>>
    +next() Invoice
    +hasNext() bool
  }
  class Invoices {
    -InvoiceApi api
    +iterator() Iterator
  }
  class InvoiceIterator {
    -Invoice[] buffer
    -String cursor
    +next() Invoice
    +hasNext() bool
  }
  class InvoiceApi {
    +fetchPage(cursor) Page
  }
  IterableCollection <|.. Invoices
  Iterator <|.. InvoiceIterator
  Invoices ..> InvoiceIterator : creates
  InvoiceIterator --> InvoiceApi
  Invoices --> InvoiceApi
```

### Participants

- **Iterator** (`Iterator`): the language's protocol for "give me the next element, or tell me you're done". Use the built-in one instead of defining your own.
- **Concrete iterator** (`InvoiceIterator`): holds the traversal state and fetches more data when its buffer runs dry.
- **Iterable collection** (`IterableCollection`): the protocol that says "I can produce an iterator".
- **Concrete collection** (`Invoices`): returns a new iterator on each call, so traversals stay independent.
- **Client**: loops with the language's native syntax and can stop at any element.

## Use it when

- The data comes from pages, cursors, streams, or files, and callers should see one flat sequence.
- The collection has a non-trivial structure (tree, graph, sparse matrix, ring buffer) and callers should not depend on it.
- You need several traversal orders over the same data, such as depth-first and breadth-first, newest-first and oldest-first.
- Callers often stop early, and producing all elements up front is expensive.
- Two pieces of code must traverse the same collection at the same time without interfering.

## Do not use it when

- The data is already an array, list or map in memory. Return it, or return a read-only view, and let callers use the native loop.
- The traversal is a linear walk where the only state is a cursor. Write a generator function (`function*` in TypeScript, `yield` in Python, `iter.Seq` in Go 1.23+, a `Stream` or `Spliterator` in Java); every modern language ships them, and they give the same laziness with a third of the code. A hand-written iterator class earns its place when iteration state outgrows a cursor - bookmarks, multiple simultaneous positions, or state callers must inspect and close.
- Callers always need every element and the set is small. A function that returns a list is simpler to test and debug.
- You are inventing a custom `hasNext`/`next` interface. Implement the language's protocol (`Symbol.iterator`, `__iter__`, `java.util.Iterator`) so the result works with every built-in loop and library.
- The traversal needs to run an operation that differs per element type. That is [Visitor](https://aipatterns.dev/design-patterns/visitor.md), possibly fed by an iterator.

## Application grill

**Inspect first:** the collections callers reach into directly (index access, `.data`, pagination params leaking into business code); the language's built-in iteration (generators, iterables, channels); how large result sets flow from the database today.

**Missing pieces:** the language's built-ins are the pattern; nothing to install. For database results, keyset pagination or a driver cursor, never OFFSET on large tables.

**Ask before you build:**

- **Scale:** what result sizes must stream instead of materialize (a memory bound per request)?
- **Performance:** does the walk hit the network per element or per page, and what page size fits?
- **Reliability:** what does the iteration do when the source changes mid-walk (an invalidated cursor)?
- **Budget:** unifying N ad-hoc loops into one iterator - who migrates the callers?
- **Implementation:** is the iterator lazy (pull) or buffered, and do errors surface at first pull or at construction?

## Implementation steps

1. Write down what the caller loops over today, and where the paging, indexing or recursion leaks into the calling code.
2. Choose the language's standard iteration protocol. Prefer a generator; fall back to an iterator class if you need state you can inspect or close.
3. Put all traversal state (index, cursor token, buffer, stack) in the iterator, not in the collection.
4. Make the collection return a fresh iterator from its factory method on each call.
5. Fetch lazily: load the next page or node only when the buffer is empty.
6. Replace the caller's manual paging loop with the native loop, and add a test that stops early and checks how much data was fetched.

## Example

A billing service exports invoices from a provider API that returns three invoices per page with a cursor to the next page. Callers loop over invoices without seeing pages, and stopping at the first overdue invoice fetches only the pages it needs.

```ts title="invoices.ts"
interface Invoice { id: string; amountCents: number; overdue: boolean }
interface Page { items: Invoice[]; next?: string }

class InvoiceApi {
  calls = 0;
  constructor(private readonly all: Invoice[], private readonly pageSize: number) {}
  fetchPage(cursor: string): Page {
    this.calls++;
    const start = Number(cursor);
    const end = start + this.pageSize;
    return { items: this.all.slice(start, end), next: end < this.all.length ? String(end) : undefined };
  }
}

class InvoiceIterator implements Iterator<Invoice> {
  private buffer: Invoice[] = [];
  private cursor: string | undefined = "0"; // undefined means no more pages

  constructor(private readonly api: InvoiceApi) {}

  next(): IteratorResult<Invoice> {
    while (this.buffer.length === 0 && this.cursor !== undefined) {
      const page = this.api.fetchPage(this.cursor);
      this.buffer = page.items;
      this.cursor = page.next;
    }
    const item = this.buffer.shift();
    return item ? { done: false, value: item } : { done: true, value: undefined };
  }
}

class Invoices implements Iterable<Invoice> {
  constructor(private readonly api: InvoiceApi) {}
  [Symbol.iterator](): Iterator<Invoice> {
    return new InvoiceIterator(this.api); // fresh state per loop
  }
}

// The same traversal as a generator. Prefer this form in real TypeScript code.
function* invoices(api: InvoiceApi): Generator<Invoice> {
  for (let cursor: string | undefined = "0"; cursor !== undefined; ) {
    const page = api.fetchPage(cursor);
    yield* page.items;
    cursor = page.next;
  }
}

const data = Array.from({ length: 7 }, (_, i) => ({
  id: `INV-${i + 1}`,
  amountCents: (i + 1) * 1000,
  overdue: i === 4,
}));
const api = new InvoiceApi(data, 3);

for (const inv of new Invoices(api)) {
  if (inv.overdue) {
    console.log("first overdue:", inv.id); // INV-5
    break;
  }
}
console.log("pages fetched:", api.calls); // 2

let total = 0;
for (const inv of invoices(api)) total += inv.amountCents;
console.log(total, "pages fetched:", api.calls); // 28000 pages fetched: 5
```

```python title="invoices.py"
from collections import deque
from dataclasses import dataclass
from typing import Iterator, Optional

@dataclass(frozen=True)
class Invoice:
    id: str
    amount_cents: int
    overdue: bool = False

@dataclass(frozen=True)
class Page:
    items: list[Invoice]
    next_cursor: Optional[str]

class InvoiceApi:
    def __init__(self, invoices: list[Invoice], page_size: int) -> None:
        self._all, self._page_size, self.calls = invoices, page_size, 0

    def fetch_page(self, cursor: str) -> Page:
        self.calls += 1
        start = int(cursor)
        end = start + self._page_size
        return Page(self._all[start:end], str(end) if end < len(self._all) else None)

class InvoiceIterator:
    def __init__(self, api: InvoiceApi) -> None:
        self._api = api
        self._buffer: deque[Invoice] = deque()
        self._cursor: Optional[str] = "0"  # None means no more pages

    def __iter__(self) -> "InvoiceIterator":
        return self

    def __next__(self) -> Invoice:
        while not self._buffer and self._cursor is not None:
            page = self._api.fetch_page(self._cursor)
            self._buffer.extend(page.items)
            self._cursor = page.next_cursor
        if not self._buffer:
            raise StopIteration
        return self._buffer.popleft()

class Invoices:
    def __init__(self, api: InvoiceApi) -> None:
        self._api = api

    def __iter__(self) -> Iterator[Invoice]:
        return InvoiceIterator(self._api)  # fresh state per loop

def invoices(api: InvoiceApi) -> Iterator[Invoice]:
    """The same traversal as a generator. Prefer this form in real Python code."""
    cursor: Optional[str] = "0"
    while cursor is not None:
        page = api.fetch_page(cursor)
        yield from page.items
        cursor = page.next_cursor

if __name__ == "__main__":
    data = [Invoice(f"INV-{i}", i * 1000, overdue=(i == 5)) for i in range(1, 8)]
    api = InvoiceApi(data, page_size=3)

    first = next(inv for inv in Invoices(api) if inv.overdue)
    print("first overdue:", first.id)  # INV-5
    print("pages fetched:", api.calls)  # 2

    print(sum(inv.amount_cents for inv in invoices(api)), "pages fetched:", api.calls)  # 28000 5
```

```go title="invoices.go"
package main

import (
	"fmt"
	"iter"
	"strconv"
)

type Invoice struct {
	ID          string
	AmountCents int
	Overdue     bool
}

type InvoiceAPI struct {
	all      []Invoice
	pageSize int
	Calls    int
}

func (a *InvoiceAPI) FetchPage(cursor string) (items []Invoice, next string) {
	a.Calls++
	start, _ := strconv.Atoi(cursor)
	end := min(start+a.pageSize, len(a.all))
	if end < len(a.all) {
		next = strconv.Itoa(end) // stays empty on the last page
	}
	return a.all[start:end], next
}

// InvoiceIterator follows the Next/Value shape of bufio.Scanner and sql.Rows.
type InvoiceIterator struct {
	api    *InvoiceAPI
	buf    []Invoice
	cursor string // empty means no more pages
	cur    Invoice
}

func (it *InvoiceIterator) Next() bool {
	for len(it.buf) == 0 && it.cursor != "" {
		it.buf, it.cursor = it.api.FetchPage(it.cursor)
	}
	if len(it.buf) == 0 {
		return false
	}
	it.cur, it.buf = it.buf[0], it.buf[1:]
	return true
}

func (it *InvoiceIterator) Value() Invoice { return it.cur }

type Invoices struct{ api *InvoiceAPI }

func (c Invoices) Iterator() *InvoiceIterator {
	return &InvoiceIterator{api: c.api, cursor: "0"}
}

// All adapts the iterator to range-over-func (Go 1.23+), the idiomatic form today.
func (c Invoices) All() iter.Seq[Invoice] {
	return func(yield func(Invoice) bool) {
		for it := c.Iterator(); it.Next(); {
			if !yield(it.Value()) {
				return
			}
		}
	}
}

func main() {
	var data []Invoice
	for i := 1; i <= 7; i++ {
		data = append(data, Invoice{ID: fmt.Sprintf("INV-%d", i), AmountCents: i * 1000, Overdue: i == 5})
	}
	api := &InvoiceAPI{all: data, pageSize: 3}
	invoices := Invoices{api: api}

	for inv := range invoices.All() {
		if inv.Overdue {
			fmt.Println("first overdue:", inv.ID) // INV-5
			break
		}
	}
	fmt.Println("pages fetched:", api.Calls) // 2

	total := 0
	for it := invoices.Iterator(); it.Next(); {
		total += it.Value().AmountCents
	}
	fmt.Println(total, "pages fetched:", api.Calls) // 28000 pages fetched: 5
}
```

```java title="InvoiceExport.java"
import java.util.*;

public class InvoiceExport {
    record Invoice(String id, long amountCents, boolean overdue) {}

    record Page(List<Invoice> items, String next) {} // next is null on the last page

    static final class InvoiceApi {
        private final List<Invoice> all;
        private final int pageSize;
        int calls;

        InvoiceApi(List<Invoice> all, int pageSize) { this.all = all; this.pageSize = pageSize; }

        Page fetchPage(String cursor) {
            calls++;
            int start = Integer.parseInt(cursor);
            int end = Math.min(start + pageSize, all.size());
            return new Page(all.subList(start, end), end < all.size() ? String.valueOf(end) : null);
        }
    }

    static final class InvoiceIterator implements Iterator<Invoice> {
        private final InvoiceApi api;
        private final Deque<Invoice> buffer = new ArrayDeque<>();
        private String cursor = "0"; // null means no more pages

        InvoiceIterator(InvoiceApi api) { this.api = api; }

        @Override
        public boolean hasNext() {
            while (buffer.isEmpty() && cursor != null) {
                Page page = api.fetchPage(cursor);
                buffer.addAll(page.items());
                cursor = page.next();
            }
            return !buffer.isEmpty();
        }

        @Override
        public Invoice next() {
            if (!hasNext()) throw new NoSuchElementException();
            return buffer.removeFirst();
        }
    }

    record Invoices(InvoiceApi api) implements Iterable<Invoice> {
        public Iterator<Invoice> iterator() { return new InvoiceIterator(api); } // fresh state per loop
    }

    public static void main(String[] args) {
        List<Invoice> data = new ArrayList<>();
        for (int i = 1; i <= 7; i++) data.add(new Invoice("INV-" + i, i * 1000L, i == 5));
        InvoiceApi api = new InvoiceApi(data, 3);
        Invoices invoices = new Invoices(api);

        for (Invoice inv : invoices) {
            if (inv.overdue()) {
                System.out.println("first overdue: " + inv.id()); // INV-5
                break;
            }
        }
        System.out.println("pages fetched: " + api.calls); // 2

        long total = 0;
        for (Invoice inv : invoices) total += inv.amountCents();
        System.out.println(total + " pages fetched: " + api.calls); // 28000 pages fetched: 5
    }
}
```

## Trade-offs

**Gains**
- Callers use one native loop, whatever the storage or transport.
- Lazy fetching: early exits load only what was read.
- Each iterator has its own position, so traversals don't interfere.
- New traversal orders are new iterators; the collection does not change.

**Costs**
- A hand-written iterator class is more code than a generator and easier to get wrong (idempotent `hasNext`, end-of-data handling).
- Lazy iteration hides I/O inside a loop. Errors and latency show up far from the call that started them.
- Iterating while the underlying collection changes is undefined unless you design for it.
- For small in-memory collections, the indirection buys nothing.

## Relations

- [Composite](https://aipatterns.dev/design-patterns/composite.md) trees are a common reason to write an iterator: depth-first or breadth-first over nested nodes.
- [Visitor](https://aipatterns.dev/design-patterns/visitor.md) runs a type-specific operation on each element. An iterator supplies the elements.
- [Factory Method](https://aipatterns.dev/design-patterns/factory-method.md) is how the collection's `iterator()` returns the right concrete iterator.
- [Memento](https://aipatterns.dev/design-patterns/memento.md) can capture an iterator's position so a long export can resume after a crash.

## Agent checklist

- [ ] You checked whether a generator or the language's built-in iteration covers the need before writing an iterator class.
- [ ] The iterator implements the language's standard protocol, not a custom `hasNext`/`next` interface.
- [ ] Traversal state lives in the iterator, and each call to the factory returns a fresh one.
- [ ] Data is fetched lazily, and a test stops early and asserts how many pages or nodes were loaded.
- [ ] End-of-data, empty collections and fetch errors are handled and tested.