TP de Programmation autour d'un design pattern : l'itérateur

Dans ce TP, nous supposons que nous disposons d'une structure de données correspondant à un ensemble ou un multi-ensemble d'éléments. Il peut s'agir d'une pile, d'une file, d'une file à priorité ou d'un ensemble tel que ceux que nous avons manipulés lors du dernier TP et de la dernière apnée. Nous supposerons que nous ne connaissons rien de l'implémentation de notre structure de données mais que nous avons néanmoins un moyen de désigner les éléments, par exemple un indice correspondant à un ordre total sur les éléments, soit arbitraire, soit induit par la structure de données elle-même. Nous disposons, en outre, des opérations supprime, lis et ajoute qui, étant donné un indice, appliquent l'opération indiquée par le nom de l'opérateur à l'élément d'indice donné.

Lorsqu'un algorithme consiste, par exemple, à parcourir les éléments de notre structure de données une seule fois et à décider de les supprimer, de les modifier ou d'insérer de nouveaux éléments à la position courante, les opérations supprime, lis et ajoute définies précédemment ont plusieurs défauts :

Par exemple, pour supprimer les éléments nuls d'un ensemble d'entiers :
i=0;
while (i<monEnsemble.taille()) {
    // On reparcourt potentiellement l'ensemble a l'intérieur de lis
    int n = monEnsemble.lis(i);

    // Si on supprime l'élément i, un autre le remplace, les numéros des
    // éléments changent. Ici on s'en sort, mais :
    // - nous sommes obligés de supposer que le remplaçant avait un indice supérieur au supprimé
    // - la boucle est un peu dure à écrire, dans ce cas, pas d'incrémentation de i
    if (n == 0)
        // On reparcourt potentiellement l'ensemble a l'intérieur de supprime
        monEnsemble.supprime(i);
    else
        i++;
}
Pour ne pas subir ces désagréments, nous pourrions envisager d'aller toucher directement à la structure de données pour écrire le parcours, mais :

Une solution "propre" est de créer une nouvelle classe dans le paquetage de gestion des listes qui implémente la notion de position dans l'ensemble et les opérations associées (déplacement et insertion/suppression à la position courante). Ce genre de structure intermédiaire, utilisée pour le parcours de collection d'objets, s'appelle un itérateur, il s'agit d'un concept bien connu en design patterns (voir par exemple le livre d'E. Gamma, R. Helm, R. Johnson et J. Vlissides donné en référence sur la page de l'UE). C'est l'itérateur qui s'occupe de maintenir l'information de position courante dans la liste et qui modifie de chaînage lorsque c'est nécessaire. En utilisant un itérateur, le code précédent devient :

Iterateur it = monEnsemble.iterateur();
while (it.aProchain()) {
    int n = it.prochain();
    if (n == 0)
        it.supprime();
}
Les avantages sont que : Pour avoir la description (en anglais) des méthodes de l'interface Iterateur qui correspond au code ci dessus, consultez ce lien.

Exercices