TD de Programmation autour de deux design patterns : itérateurs et visiteurs

1 - Itérateurs

Dans cette première partie, 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, 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

2 - Visiteurs

Nous avons maintenant des ensembles génériques qui vont nous servir à stocker des ensembles d'objets de la classe Composant et que nous pouvons parcourir facilement grâce à nos itérateurs. Justement, nous allons être amené à parcourir nos objets de multiples fois afin de réaliser les différents traitements requis par notre jeu, pour :

En outre, ces différents traitements sont bien des parcours successifs car ils dépendent les uns des autres : le traitement des collisions corrige les erreurs de positions dues aux déplacements, et le dessin est censé représenter les objets correctement positionnés.

Une solution pour réaliser ces parcours serait de les écrire, chacun dans une méthode distincte, et d'implémenter le traitement correspondant dans des méthodes de nos composants appelées lors de ces parcours. Les problèmes posés par ce genre d'approche sont les suivants :

Une autre solution est d'utiliser une interface permettant de transmettre une opération à utiliser lors du parcours. Cette opération ne fait pas partie du composant et peut être spécialisée pour chaque type de composant. Tout ce que le composant a besoin de faire est d'implémenter une méthode permettant d'accepter cette opération et d'appeler cette opération sur lui même (la bonne variante, dépendant de son type). Cette manière de faire correspond à un design pattern appelé visiteur. Le visiteur est l'objet qui implémente l'opération. Les avantages sont alors les suivants :

Exercices