INF 441 - TD 7
Itérateurs en Java

Votre opinion sur le cours de ce matin : Votre opinion sur le TD de la semaine dernière :

Java fournit une syntaxe agréable pour parcourir les éléments de toute classe qui implémente l'interface Iterable. Ainsi, on peut écrire : 

  void print (Iterable<Integer> it) {
    for (int v : it) {
      System.out.println(v);
    }
  }
On peut écrire une telle boucle for pour toute classe faisant partie des collections Java, telle que LinkedList par exemple. On peut également définir sa propre classe Iterable, de la manière suivante : 
class C implements Iterable<Integer> {
  public Iterator<Integer> iterator() {
    return new Iterator<Integer> () {
      public boolean hasNext() {...}
      public Integer next() {...}
    }
  }
}

Ici, la classe C implémente une structure de données dont on veut pouvoir parcourir les éléments. Elle fournit pour cela une méthode iterator qui renvoie une nouvelle instance de la classe Iterator, qui elle-même fournit des méthodes hasNext et next. La méthode hasNext renvoie true s'il reste des éléments à parcourir, et false sinon. La méthode next renvoie le prochain élément de l'itération; s'il n'y a plus d'élément à renvoyer, elle lève l'exception NoSuchElementException.

Intervalles

Implémenter une classe Interval dont le constructeur prend deux entiers beginning et end. L'itérateur de la classe Interval doit parcourir les entiers compris entre beginning (inclus) et end (exclus), dans l'ordre croissant. Tester votre code avec plusieurs intervalles, par exemple [-10,10], [10,10], ou [1,0]. Vérifier également que l'on peut itérer plusieurs fois sur un même object de classe Interval.

Faites d'abord vos propres tests. Puis vérifiez à l'aide de nos tests.

Déposer le fichier Interval.java :

Fusion de séquences croissantes

On suppose données deux instances de Iterator<Integer>, chacune énumérant une séquence d'entiers dans l'ordre croissant. Écrire une classe MergeIterator qui énumère la réunion de ces deux séquences, dans l'ordre croissant. On pourra utiliser deux champs qui stockent le prochain élément de chaque itérateur, s'il existe, et null sinon. 

public class MergeIterator implements Iterator<Integer> {
  public MergeIterator(Iterator<Integer> it1, Iterator<Integer> it2) {
    ...
  }
  ...
}
Pour tester votre code, vous pouvez utiliser les itérateurs sur un intervalle écrits lors de la question précédente. N'oubliez pas de tester les cas où l'une des séquences est vide, les cas où l'une des séquences est plus longue que l'autre, les cas où les séquences ont des éléments communs, etc.

Faites d'abord vos propres tests. Puis vérifiez à l'aide de nos tests.

Déposer le fichier MergeIterator.java :

Arbres

On considère une classe Tree<V> représentant des arbres binaires dont les nœuds contiennent des valeurs de type V : 

public class Tree<V> {
  V val;
  Tree<V> left, right;
  Tree<V> parent;
  public Tree(V val, Tree<V> left, Tree<V> right) {...}
}
Noter que les champs left et right peuvent contenir le pointeur null. Noter également que chaque nœud contient un pointeur, stocké dans le champ parent, vers son père, s'il en a un. Ce pointeur est nul si ce nœud n'a pas de père. Votre constructeur doit faire en sorte que ce champ soit correctement initialisé.

L'objectif est ici de faire de la classe Tree une classe Iterable. Définir un itérateur pour le parcours infixe (in-order en anglais) : d'abord le sous-arbre gauche, puis la racine, enfin le sous-arbre droit. La classe de l'itérateur maintient un champ current contenant le prochain nœud à visiter. Attention: les arbres ne doivent pas être modifiés (pas même le champ parent).

Testez directement à l'aide de nos tests.

Déposer le fichier Tree.java :

Question optionnelle

Réaliser un autre itérateur qui parcourt les éléments de l'arbre dans l'ordre préfixe (pre-order en anglais) : la racine, le sous-arbre gauche, enfin le sous-arbre droit.

Déposer le fichier Tree.java :

Une solution vous est proposée.