CHAPITRE 27 – ITERATOR | Faites Entrer Les Design Pattern

Le classeur métallique gris. Des centaines de dossiers, classés par ordre chronologique, avec des codes couleur et des séparateurs. Pour y trouver quelque chose, on ne plongeait pas la main au hasard. On ouvrait le tiroir, on prenait le premier dossier, puis le suivant, puis le suivant. On parcourait. La structure interne (tiroirs, intercalaires) restait cachée. On avait juste une séquence. C’était ça, l’Iterator. Un moyen de parcourir une collection sans savoir comment elle est faite à l’intérieur.

Parcours sans exposer la structure

Le pattern Iterator fournit un moyen d’accéder séquentiellement aux éléments d’un objet agrégé (une collection) sans exposer sa représentation sous-jacente. Il découple l’algorithme de parcours de la structure de données sur laquelle il itère.

Le principe est simple : au lieu que le client manipule directement le tableau, la liste, l’arbre ou tout autre structure, il demande un itérateur. Cet itérateur connaît la structure interne et sait comment en extraire les éléments, un par un, dans un certain ordre.

Implémentation classique

// Interface de l'itérateur
interface Iterator<T> {
    // Y a-t-il un élément suivant ?
    hasNext(): boolean;
    // Retourne l'élément courant et avance.
    next(): T;
    // Optionnel : réinitialiser
    reset?(): void;
}

// Interface de la collection (Aggregate)
interface Collection<T> {
    createIterator(): Iterator<T>;
}

// --- Collection concrète : un simple tableau ---
class DossierCollection implements Collection<string> {
    private dossiers: string[] = [];

    constructor(dossiers: string[]) {
        this.dossiers = dossiers;
    }

    createIterator(): Iterator<string> {
        return new DossierIterator(this.dossiers);
    }

    // On peut avoir d'autres méthodes (ajouter, supprimer) sans affecter l'itérateur.
    ajouterDossier(dossier: string): void {
        this.dossiers.push(dossier);
    }
}

// Itérateur concret pour un tableau
class DossierIterator implements Iterator<string> {
    private position: number = 0;

    constructor(private dossiers: string[]) {}

    hasNext(): boolean {
        return this.position < this.dossiers.length;
    }

    next(): string {
        if (!this.hasNext()) {
            throw new Error("No more elements");
        }
        return this.dossiers[this.position++];
    }

    reset(): void {
        this.position = 0;
    }
}

Cas collections avancées : Parcours d’un arbre (Binary Tree)

Là où Iterator brille, c’est pour des structures non linéaires, où le parcours n’est pas évident.

// Structure de données complexe : un nœud d'arbre binaire
class TreeNode<T> {
    constructor(
        public value: T,
        public left: TreeNode<T> | null = null,
        public right: TreeNode<T> | null = null
    ) {}
}

// L'arbre lui-même (Aggregate)
class BinaryTree<T> {
    constructor(private root: TreeNode<T> | null = null) {}

    createIterator(order: 'inorder' | 'preorder' | 'postorder'): Iterator<T> {
        // L'itérateur sait comment parcourir l'arbre selon un ordre donné.
        return new BinaryTreeIterator(this.root, order);
    }
}

// Itérateur pour un arbre binaire
class BinaryTreeIterator<T> implements Iterator<T> {
    private stack: TreeNode<T>[] = [];
    private current: TreeNode<T> | null = null;
    private order: 'inorder' | 'preorder' | 'postorder';

    constructor(root: TreeNode<T> | null, order: 'inorder' | 'preorder' | 'postorder') {
        this.order = order;
        this.resetToRoot(root);
    }

    private resetToRoot(root: TreeNode<T> | null): void {
        this.stack = [];
        this.current = root;
        // Préparation initiale selon l'ordre de parcours
        if (this.order === 'preorder' && this.current) {
            this.stack.push(this.current);
        }
    }

    hasNext(): boolean {
        return this.stack.length > 0 || this.current !== null;
    }

    next(): T {
        if (!this.hasNext()) throw new Error("No more elements");

        switch (this.order) {
            case 'inorder':
                return this.nextInorder();
            case 'preorder':
                return this.nextPreorder();
            case 'postorder':
                return this.nextPostorder();
            default:
                throw new Error("Unknown traversal order");
        }
    }

    private nextInorder(): T {
        // Parcours infixe (gauche, racine, droite)
        while (this.current !== null) {
            this.stack.push(this.current);
            this.current = this.current.left;
        }
        this.current = this.stack.pop()!;
        const value = this.current.value;
        this.current = this.current.right;
        return value;
    }

    private nextPreorder(): T {
        // Parcours préfixe (racine, gauche, droite)
        this.current = this.stack.pop()!;
        const value = this.current.value;
        if (this.current.right) this.stack.push(this.current.right);
        if (this.current.left) this.stack.push(this.current.left);
        return value;
    }

    private nextPostorder(): T {
        // Parcours postfixe (gauche, droite, racine) - plus complexe, nécessite deux piles ou un flag
        // Implémentation simplifiée avec deux piles
        if (!this.current) throw new Error("No current node");
        // Pour la démonstration, on simule un parcours déjà calculé.
        // Une vraie implémentation serait plus longue.
        const tempStack: TreeNode<T>[] = [];
        tempStack.push(this.current);
        const resultStack: T[] = [];

        while (tempStack.length > 0) {
            const node = tempStack.pop()!;
            resultStack.push(node.value);
            if (node.left) tempStack.push(node.left);
            if (node.right) tempStack.push(node.right);
        }
        // On inverse pour avoir l'ordre postfixe
        const value = resultStack.pop()!;
        // Pour simplifier, on vide le stack principal et on le remplit avec le reste
        this.stack = resultStack.reverse().map(v => new TreeNode(v)); // Approximation
        this.current = null;
        return value;
    }

    reset(): void {
        this.resetToRoot(this.current ? this.current : null); // Simplification
    }
}

// --- Scénario d'utilisation ---
console.log("=== PARCOURS D'ARBRE (Iterator Pattern) ===\n");

// Construction d'un arbre simple
//        A
//       / \
//      B   C
//     / \   \
//    D   E   F
const root = new TreeNode('A',
    new TreeNode('B',
        new TreeNode('D'),
        new TreeNode('E')
    ),
    new TreeNode('C',
        null,
        new TreeNode('F')
    )
);

const tree = new BinaryTree(root);

console.log("Parcours infixe (inorder):");
const inorderIt = tree.createIterator('inorder');
while (inorderIt.hasNext()) {
    console.log(inorderIt.next());
}
// Affiche: D, B, E, A, C, F

console.log("\nParcours préfixe (preorder):");
const preorderIt = tree.createIterator('preorder');
while (preorderIt.hasNext()) {
    console.log(preorderIt.next());
}
// Affiche: A, B, D, E, C, F

console.log("\nParcours postfixe (postorder):");
const postorderIt = tree.createIterator('postorder');
while (postorderIt.hasNext()) {
    console.log(postorderIt.next());
}
// Affiche: D, E, B, F, C, A (selon l'implémentation simplifiée)

Cas collections : Intégration native et génériques

En JavaScript/TypeScript moderne, le pattern Iterator est intégré au langage via le protocole itérable. Un objet est itérable s’il implémente une méthode [Symbol.iterator]() qui retourne un itérateur. Les boucles for...of, l’opérateur de décomposition (...), Array.from() utilisent ce protocole.

// Implémentation d'une collection personnalisée avec Symbol.iterator
class DossierClassifie implements Iterable<string> {
    private dossiersSecrets: Map<string, string> = new Map();

    ajouter(code: string, description: string): void {
        this.dossiersSecrets.set(code, description);
    }

    // Implémentation du protocole itérable
    *[Symbol.iterator](): Iterator<string> {
        // On peut utiliser un générateur, qui crée un itérateur implicitement.
        for (const [code, desc] of this.dossiersSecrets) {
            yield `[${code}] ${desc}`;
        }
    }

    // Itérateur personnalisé pour un parcours différent
    parcoursParCode(): Iterator<string> {
        const codes = Array.from(this.dossiersSecrets.keys()).sort();
        let index = 0;
        return {
            next: () => {
                if (index < codes.length) {
                    const code = codes[index++];
                    const desc = this.dossiersSecrets.get(code)!;
                    return { value: `CODE: ${code} -> ${desc}`, done: false };
                }
                return { value: undefined, done: true };
            }
        };
    }
}

// Utilisation avec for...of (protocole natif)
const archives = new DossierClassifie();
archives.ajouter('X-12', 'Affaire non classée');
archives.ajouter('A-01', 'Dossier prioritaire');
archives.ajouter('M-77', 'Mission confidentielle');

console.log("\n=== Parcours avec for...of (itérable natif) ===");
for (const dossier of archives) {
    console.log(dossier);
}
// Affiche:
// [X-12] Affaire non classée
// [A-01] Dossier prioritaire
// [M-77] Mission confidentielle

console.log("\n=== Parcours avec itérateur personnalisé ===");
const customIt = archives.parcoursParCode();
let result = customIt.next();
while (!result.done) {
    console.log(result.value);
    result = customIt.next();
}
// Affiche trié par code:
// CODE: A-01 -> Dossier prioritaire
// CODE: M-77 -> Mission confidentielle
// CODE: X-12 -> Affaire non classée

Pourquoi utiliser Iterator quand on a for...of ?

Parce que le pattern va au-delà de la simple itération native :

Parcours complexes : Comme l’arbre avec différents ordres.
Itérateurs spéciaux : Filtrer, mapper, paginer à la volée sans créer de nouveaux tableaux (comme les générateurs).
Contrôle fin : L’itérateur peut avoir des méthodes comme reset(), peek(), skip().
Découplage : Le client ne dépend pas de la structure concrète (Array, Map, Tree), mais de l’interface Iterator.

Résumé

L’Iterator est le passeur. Celui qui vous guide à travers une structure sans que vous ayez à savoir si vous marchez sur un sentier, un escalier ou une échelle. Il est tellement fondamental qu’on l’oublie. Mais quand on doit parcourir autrement que du premier au dernier, ou quand la collection n’est pas un simple tableau, il devient indispensable.

Le suivant, Memento, serait le gardien de la mémoire. Celui qui sait capturer et restaurer un état, pour permettre l’oubli temporaire ou le retour en arrière.