6.5 Itérations

Le pattern d'itération permet de généraliser à certaines structures de données le parcours itératif d'un intervalle d'entiers :

for (i=0; i<n; i++)

Les trois opérations de ce parcours étant l'initialisation, le test de fin de parcours et la transformation qui donne l'élément suivant. Un objet de type java.util.Iterator permet de parcourir une structure de données en gardant en mémoire un curseur, qui désigne non un élément, mais une position avant, ou après un élément. Au début du parcours, le curseur est avant le premier élément, et à la fin du parcours, il est après le dernier élément (figure ).

Figure: Un itérateur sur une structure de données : les éléments sont représentés par des disques, les positions du curseur par des carrés, et initialement, le curseur est avant le premier élément.

L'interface Iterator déclare les méthodes suivantes :

• boolean hasNext(), qui teste s'il existe un élément suivant le curseur;
• Object next(), qui retourne l'élément suivant le curseur (s'il n'y en a pas, il déclenche une exception de type NoSuchElementException), et avance le curseur d'une position ;
• void remove(), qui supprime le dernier élément qui a été retourné par next(), c'est-à-dire l'élément précédant le curseur (sa définition est optionnelle, elle peut consister à déclencher une exception de type UnsupportedOperationException).

Toutes les collections disposent d'une méthode Iterator iterator(), qui permet d'initialiser un itérateur, de façon analogue au int i=0 qui initialise un indice de boucle entier. Par exemple, la procédure suivante permet de supprimer d'une collection tous les éléments qui ne satisfont pas une condition représentée par une méthode boolean cond(A a), à l'aide d'une boucle while :

  static void filtre(Collection c) {
    Iterator i = c.iterator();
    while (i.hasNext()) {
      if (!cond((A) i.next())) i.remove();
    }
  }

ou d'une boucle for :

  static void filtre(Collection c) {
    for (Iterator i = c.iterator(); i.hasNext(); )
      if (!cond((A) i.next())) i.remove();
  }

6.5.0.0.1 Itération sur les listes

La sous-interface ListIterator est spécialisée pour l'itération sur les listes, permettant de les parcourir dans l'un ou l'autre sens et de les modifier au cours du parcours (figure ).

Figure: Le curseur d'un itérateur de liste peut se déplacer dans les deux sens et être initialisé à une position quelconque.

Figure: Insertion d'un objet par invocation de la méthode add(c).

Outre les méthodes héritées d'Iterator, elle déclare les méthodes suivantes :

• hasPrevious et previous, analogues à hasNext et next et permettant un parcours arrière ;
• add(Object o) insère o dans la liste juste avant le prochain élément retourné par next, et juste après le prochain élément retourné par previous, ou encore comme seul élément si la liste était vide, et avance le curseur d'une position (figure ) ;
• set(Object o) remplace le dernier élément qui a été retourné par next ou previous par l'objet o (figure ), à moins que add ou remove n'ait été appelé auparavant, auquel cas une exception de type IllegalStateException est déclenchée.

Figure: Remplacement d'un élément par invocation de la méthode set(d), invoquée après un next (en haut) et après un previous (en bas).

Les listes disposent aussi d'une méthode ListIterator listIterator(int n), qui retourne un itérateur respectant l'ordre des éléments de la liste et positionne le curseur devant l'élément d'indice n. Le parcours arrière d'une liste l se ferait ainsi :

    for (ListIterator i = l.listIterator(l.size()); 
         i.hasPrevious();) {
      ...
    }

6.5.0.0.2 Itérations sur les tables

À la différence des collections, les tables ne disposent pas directement d'un mécanisme d'itération. Cependant, il est possible d'itérer sur l'une des vues d'une table en tant que collection :

  Map m = ...;
  // pour imprimer l'ensemble des clés :
  for (Iterator i=m.keySet().iterator(); i.hasNext();)
    System.out.println(i.next());

  // pour imprimer la liste des valeurs :
  for (Iterator i=m.values.iterator(); i.hasNext();)
    System.out.println(i.next());

  // pour imprimer l'ensemble des associations :
  for (Iterator i=m.entrySet().iterator(); i.hasNext();) {
    Map.Entry e = (Map.Entry) i.next();
    System.out.println(e.getKey() + " -> " + e.getValue());
  }

Outre la simple énumération des éléments (par next), ces trois vues permettent l'opération remove.

6.5.0.0.3 Réalisation d'un itérateur

Bien que l'on utilise généralement les itérateurs fournis par les classes des bibliothèques, il est parfois nécessaire d'en définir un. Prenons l'exemple du type Feu (voir § ) et définissons un itérateur qui énumère de façon cyclique ses trois constantes Feu.ROUGE, Feu.ORANGE et Feu.VERT.

On ajoute à la classe Feu une fonction cycle() qui retourne un itérateur. Celui-ci est défini comme une instance d'une classe anonyme (voir § , page ) qui réalise l'interface Iterator. Cette instance a un champ privé curseur qui garde en mémoire une position entre deux invocations de next. Comme on veut une énumération cyclique, la méthode hasNext retourne toujours true. Dans next, le cas par défaut, qui est de déclencher l'exception NoSuchElementException, ne devrait pas se produire. La méthode remove déclenche toujours l'exception UnsupportedOperationException.

import java.util.Iterator;
import java.util.NoSuchElementException;

class Feu {
  // ...

  static Iterator cycle() {
    return new Iterator() {
      private int curseur = 0;
      public boolean hasNext() {
        return true;
      }
      public Object next() {
        switch (curseur) {
        case 0: 
          curseur = 1;
          return VERT;
        case 1: 
          curseur = 2;
          return ORANGE;
        case 2:
          curseur = 0;
          return ROUGE;
        default:
          throw new NoSuchElementException();
        }
      }
      public void remove() {
        throw new UnsupportedOperationException();
      }
    };
  }

  public static void main(String[] args) {
    Iterator c = Feu.cycle();
    for (int i=0; i<10; i++) {
      System.out.println(c.next());
    }
  }
}

6.5.0.0.4 Itération sur les chaînes

L'API de Java dispose d'une classe StringTokenizer, dans le paquet java.util qui permet de découper une chaîne en sous-chaînes séparées par des caractères délimiteurs. Cette classe a un constructeur à deux arguments : la chaîne à découper, et la chaîne des caractères délimiteurs. Une instance de cette classe fonctionne comme un itérateur, avec les méthodes hasMoreTokens, analogue à hasNext et nextToken, analogue à next, mais retournant un String. Par exemple,

import java.util.StringTokenizer;

class Token {
  public static void main(String[] args) {
    StringTokenizer st = 
      new StringTokenizer("/usr/local/java", "/");
    while (st.hasMoreTokens()) {
      System.out.println(st.nextToken());
    }
  }
}

imprime sur la sortie standard :

usr
local
java

Plusieurs caractères délimiteurs peuvent être spécifiés comme deuxième argument du constructeur. Ainsi, si l'on veut découper une ligne d'un texte en une suite de mots, on définira le StringTokenizer suivant :

  String ligne = ...;
  StringTokenizer st = 
    new StringTokenizer(ligne, "\t .,;:?!()\"'");