Lors du dernier concours du meilleur « Meilleur Développeur de France », dont on vous pouvez retrouver un résumé ici, une des épreuves consistait à programmer un Multirator. Ce terme est une invention personnelle pour désigner un Iterator piochant ses éléments suivants (next) dans une liste d’Iterators. Dans le concours le Multirator devait toujours choisir la plus petite valeur disponible.
Jusqu’à aujourd’hui, le besoin d’une telle fonctionnalité ne s’est jamais fait sentir dans mes programmes. Or j’en ai justement besoin aujourd’hui. Et au lieux de programmer un Multirator de mon coté et de le garder pour moi seul, je me propose de vous présenter ma démarche.
Avant de poursuivre, posons le stylo et posons-nous les bonnes questions. C’est quoi un Multirator ? Voici ma vision de la chose. A mon sens, c’est un objet qui étend (extends) les fonctionnalités des Iterators, en itérant sur plusieurs autres Iterators selon des règles spécifiques à chaque implémentation.
Plus concrètement, cela va ressembler à l’interface suivante en Java :
1 2 3 | public interface Multirator<E> extends Iterator<E> { ... } |
Pour des raisons pratiques évidentes, disons que ça étend également l’interface Iterable :
1 2 3 | public interface Multirator<E> extends Iterator<E>, Iterable<E> { ... } |
Et pour faire bonne mesure, je m’offre l’opportunité d’ajouter des Iterators tiers après l’instanciation :
1 2 3 4 5 6 | public interface Multirator<E> extends Iterator<E>, Iterable<E> { void add(final Iterator<E>... iterators); void add(final Iterable<E>... iterables); } |
Pour coller au plus près du concours, je vais donc écrire une implémentation qui prendra toujours les plus petits éléments disponibles :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | public class SortedMultirator<E> implements Multirator<E> { /* De Multirator.java */ @Override public void add(final Iterator<E>... iterators) { throw new UnsupportedOperationException("not yet"); } @Override public void add(final Iterable<E>... iterables) { throw new UnsupportedOperationException("not yet"); } /* De Iterator.java */ @Override public boolean hasNext() { throw new UnsupportedOperationException("not yet"); } @Override public E next() { throw new UnsupportedOperationException("not yet"); } @Override public void remove() { throw new UnsupportedOperationException("not yet"); } /* De Iterable.java */ @Override public Iterator<E> iterator() { throw new UnsupportedOperationException("not yet"); } } |
Pour que ce soit un minimum pratique, je vais ajouter simplement deux constructeurs :
1 2 3 4 5 6 7 8 9 10 11 12 | public class SortedMultirator<E> implements Multirator<E> { /* Construteurs */ public SortedMultirator(final Iterator<E>... iterators) { // ... } public SortedMultirator(final Iterable<E>... iterables) { // ... } ... |
Pour l’instant, ce code ne fait rien d’autre que compiler sans erreur. Cela me convient car je vais avoir une démarche qualité, à l’aide de la méthode 3T (Tests en Trois Temps), inspirée des TDD dans la suite.
Je vais donc écrire une série de tests :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | public class SortedMultiratorTest { @Test public void testOneIterator() { // Arrange final List<Integer> listA = newArrayList(7, 3, 5); final List<Integer> expected = newArrayList(7, 3, 5); // Act final Multirator<Integer> multirator = new SortedMultirator<>(listA); final List<Integer> result = newArrayList(multirator); // Assert Assert.assertEquals(expected, result); } @Test public void testTwoIterator() { // Arrange final List<Integer> listA = newArrayList(7, 3, 5); final List<Integer> listB = newArrayList(1, 2, 8, 4, 9); final List<Integer> expected = newArrayList(1, 2, 7, 3, 5, 8, 4, 9); // Act final Multirator<Integer> multirator = new SortedMultirator<>(listA, listB); final List<Integer> result = newArrayList(multirator); // Assert Assert.assertEquals(expected, result); } ... } |
Dans l’exemple, je ne présente les tests que pour une et deux listes en entrée, pour que ça reste lisible. Il faut imaginer des tests avec zéro, un, deux, trois, ..N listes. Et bien sur, il faut penser à factoriser tout cela.
Vous voyez que j’utilise aussi des méthodes utilitaires pour construire mes tests. Elles ne sont pas importantes. Voici néanmoins à quoi elles ressemblent pour les curieux :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | @SafeVarargs private static <E> List<E> newArrayList(final E... tab) { final List<E> list = new ArrayList<>(); for (final E elt : tab) { list.add(elt); } return list; } private static <E> List<E> newArrayList(final Multirator<E> multirator) { final List<E> list = new ArrayList<>(); for (final E elt : multirator) { list.add(elt); } return list; } |
quand je lance mes tests, ils sont bien évidement rouges, puisque les fonctionnalités n’ont pas encore été implémentées.
Je vais maintenant m’occuper des constructeurs qui ne font encore rien. Si je ne m’en occupe pas en premier, on ne risque pas de faire grand chose…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public class SortedMultirator<E> implements Multirator<E> { private final List<Iterator<E>> iterators = new ArrayList<>(); /* Construteurs */ @SafeVarargs public SortedMultirator(final Iterator<E>... iterators) { add(iterators); } @SafeVarargs public SortedMultirator(final Iterable<E>... iterables) { add(iterables); } ... |
Comme c’est vraiment trivial, on va enchaîner sur les deux méthodes add :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public class SortedMultirator<E> implements Multirator<E> { ... @SuppressWarnings("unchecked") @Override public void add(final Iterator<E>... iterators) { for (final Iterator<E> iter : iterators) { this.iterators.add(iter); } } @SuppressWarnings("unchecked") @Override public void add(final Iterable<E>... iterables) { for (final Iterable<E> iterable : iterables) { add(iterable.iterator()); } } |
Je vais commencer à préparer la recherche du prochain élément. J’avance un peu dans l’inconnu sans être allé jusqu’au bout pour que vous puissiez vraiment bien voir comment je procède.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | public class SortedMultirator<E> implements Multirator<E> { ... private List<Integer> nexts = new ArrayList<>(); ... @SuppressWarnings("unchecked") @Override public void add(final Iterator<E>... iterators) { for (final Iterator<E> iter : iterators) { this.iterators.add(iter); addNewNext(iter); } } ... private void addNewNext(final Iterator<E> iter) { E elt = null; if (iter.hasNext()) { elt = iter.next(); } nexts.add(elt); } ... } |
Dans la méthode addNewNext(), j’ajoute volontairement « null » dans la liste s’il n’y a pas de suivant. Cela me permet de conserver l’ordre des Iteratos.
La liste nexts va me servir de tampon pour stocker les éléments suivants de chaque Iterator et ainsi de déterminer le plus petit élément. Cela me permet de très facilement programmer la méthode hasNext() :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | public class SortedMultirator<E> implements Multirator<E> { ... @Override public boolean hasNext() { for(final E next : nexts) { if(next != null) { return true; } } for(final Iterator<E> iter : iterators) { if(iter.hasNext()) { return true; } } return false; } ... } |
Je peux donc passer à la méthode next(). Mais je me rend soudain compte que, dans cette implémentation spécifique, il faut que mes éléments soient comparables, ce qui m’oblige à légèrement changer la déclaration de la classe :
1 | public class SortedMultirator<E extends Comparable<E>> implements Multirator<E> { |
Et donc, cela donne, pour la méthode next() :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | public class SortedMultirator<E extends Comparable<E>> implements Multirator<E> { ... private void prepareNext() { for (int i = 0; i < iterators.size(); i++) { E elt = nexts.get(i); if (elt == null) { final Iterator<E> iter = iterators.get(i); if (iter.hasNext()) { elt = iter.next(); nexts.set(i, elt); } } } } @Override public E next() { // Preparation prepareNext(); ... } ... } |
Notez que je ne fais la préparation de l'élément suivant que lors de l'appel à la méthode next(). Je pourrais le faire plus tôt. Ce qui m’intéresse ici, c’est surtout que les têtes soient prises en compte lorsqu’on ajoute de nouvelles listes ou Iteratos au Multirator.
Et pour la suite :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | @Override public E next() { // Preparation prepareNext(); // Recherche du plus petit E smallest = null; int pos = -1; for(int i = 0; i < nexts.size(); i++) { E elt = nexts.get(i); if(smallest == null) { smallest = elt; pos = i; continue; } if(elt == null) { continue; } if(smallest.compareTo(elt) > 0) { smallest = elt; pos = i; } } if(smallest == null) { throw new NoSuchElementException(); } // On vide la case trouvee nexts.set(pos, null); return smallest; } |
On fait rapidement la méthode iterator() :
1 2 3 4 5 6 7 8 9 10 | public class SortedMultirator<E extends Comparable<E>> implements Multirator<E> { ... @Override public Iterator<E> iterator() { return this; } } |
On peut maintenant relancer les tests et vérifier qu’ils passent tous au vert.
On pourrait s’arrêter là en se disant qu’on est légitimement en droit de penser que tout est bon. Mais je me demande ce qui doit se passer si on trouve, au même moment la même valeur dans deux Iterators. Là il ne s’agit pas juste de prendre la valeur mais aussi de faire avancer un curseur. Je décide que le l’ordre d’ajout des Iterators fait office de règle. Le code semble d’ailleurs déjà fonctionner de cette façon mais je vais néanmoins coder un test pour le vérifier.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public class SortedMultiratorTest { ... @Test public void testTwoIteratorAvecEgalite() { // Arrange final List<Integer> listA = newArrayList(5, 3, 1); final List<Integer> listB = newArrayList(5, 4, 2); final List<Integer> expected = newArrayList(5, 3, 1, 5, 4, 2); // Act final Multirator<Integer> multirator = new SortedMultirator<>(listA, listB); final List<Integer> result = newArrayList(multirator); // Assert Assert.assertEquals(expected, result); } |
Oufs ça marche 
Je vous laisse trouver le code idéal pour la méthode remove() dont je ne me suis pas encore occupé. La façon dont je vois les choses est qu’elle doit permettre de supprimer du l’Iterator tiers le prochain plus petit élément.
Au fait, la prochaine édition du meilleur développeur de France se déroulera le 15 mars 2014 à l'école 42 : http://lemeilleurdevdefrance.com/2014/
Allé un petit dernier pour la route :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | public class SortedMultiratorTest { ... @Test public void testThreeIterator() { // Arrange final List<Integer> listA = newArrayList(5, 3, 1); final List<Integer> listB = newArrayList(5, 4, 2); final List<Integer> listC = newArrayList(5, 9, 2, 7, 3); final List<Integer> expected = newArrayList(5, 3, 1, 5, 4, 2, 5, 9, 2, 7, 3); // Act final Multirator<Integer> multirator = new SortedMultirator<>(listA, listB, listC); final List<Integer> result = newArrayList(multirator); // Assert Assert.assertEquals(expected, result); } |
Vous pouvez retrouver les fichiers Multirator.java, SortedMultirator.java et SortedMultiratorTest.java sur mon GitHub.
Pendant que j’y suis, j’ai demandé à David Gageot (qui au passage est arrivé second au Concours du Meilleur Développeur de France en 2013) comment il avait répondu à cette épreuve. Vous trouverez sa réponse (ici) sur GitHub.
Ce qui est intéressant dans la proposition de David, c’est qu’il utilise le PeekingIterator de Guava. Souvenez-vous que je vous avais déjà proposé une série d’articles sur Guava. Le PeekingIterator propose la méthode « peek() » qui fonctionne comme la méthode « next() » à la différence qu’elle ne fait pas avancer le « curseur ». C’est donc assez pratique dans notre cas spécifique.
Voici donc une version utilisant le PeekingIterator (il n’y a que les éléments qui changent) :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | public class SortedPeekingMultirator<E extends Comparable<E>> implements Multirator<E> { private final List<PeekingIterator<E>> iterators = new ArrayList<>(); @SuppressWarnings("unchecked") @Override public void add(final Iterator<E>... iterators) { for (final Iterator<E> iter : iterators) { final PeekingIterator<E> pi = Iterators.peekingIterator(iter); this.iterators.add(pi); } } @Override public boolean hasNext() { for (final PeekingIterator<E> pi : iterators) { if (pi.hasNext()) { return true; } } return false; } @Override public E next() { if (!hasNext()) { throw new NoSuchElementException(); } E smallest = null; int pos = 0; int i = 0; for (final PeekingIterator<E> pi : iterators) { if (pi.hasNext()) { final E elt = pi.peek(); if (smallest == null || smallest.compareTo(elt) > 0) { smallest = elt; pos = i; } } i++; } // next iterators.get(pos).next(); return smallest; } ... } |
Et vous, comment auriez-vous fait ça ?
Allé, encore un bonus. Voici ce que donnerait un multirator qui enchaînerait simplement ses iterators jusqu’à plus soif. On commence bien entendu par les tests :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | public class ChainedMultiratorTest { @SuppressWarnings("unchecked") @Test public void testOneIterator() { // Arrange final List<Integer> listA = newArrayList(7, 3, 5); final List<Integer> expected = newArrayList(7, 3, 5); // Act // Act and Assert doTestManyIterator(expected, listA); } @SuppressWarnings("unchecked") @Test public void testTwoIterator() { // Arrange final List<Integer> listA = newArrayList(1, 2, 3); final List<Integer> listB = newArrayList(4, 5, 6, 7); final List<Integer> expected = newArrayList(1, 2, 3, 4, 5, 6, 7); // Act // Act and Assert doTestManyIterator(expected, listA, listB); } @SuppressWarnings("unchecked") @Test public void testThreeIterator() { // Arrange final List<Integer> listA = newArrayList(1, 2, 3); final List<Integer> listB = newArrayList(4, 5, 6, 7); final List<Integer> listC = newArrayList(8, 9); final List<Integer> expected = newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9); // Act // Act and Assert doTestManyIterator(expected, listA, listB, listC); } @SuppressWarnings("unchecked") private void doTestManyIterator(final List<Integer> expected, final List<Integer>... lists) { // Act final Multirator<Integer> multirator = new ChainedMultirator<>(lists); final List<Integer> result = newArrayList(multirator); // Assert Assert.assertEquals(expected, result); } ... |
Et sans attendre le code qui va avec :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | public class ChainedMultirator<E> implements Multirator<E> { private final List<Iterator<E>> iterators = new ArrayList<>(); /* Construteurs */ @SafeVarargs public ChainedMultirator(final Iterator<E>... iterators) { add(iterators); } @SafeVarargs public ChainedMultirator(final Iterable<E>... iterables) { add(iterables); } /* De Multirator.java */ @Override public void add(Iterator<E>... iterators) { for (final Iterator<E> iter : iterators) { this.iterators.add(iter); } } @Override public void add(Iterable<E>... iterables) { for (final Iterable<E> iterable : iterables) { add(iterable.iterator()); } } /* De Iterator.java */ @Override public boolean hasNext() { for (final Iterator<E> iter : iterators) { if (iter.hasNext()) { return true; } } return false; } @Override public E next() { for (final Iterator<E> iter : iterators) { if (iter.hasNext()) { return iter.next(); } } throw new NoSuchElementException(); } ... |
Je rebondi sur le commentaire d’Issamm qui parle de ConcurrentModificationException. Comment est ce qu’une CME survient ? Voici un petit exemple :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | @Test(expected = ConcurrentModificationException.class) public void testSimple() { final List<Integer> elements = newArrayList(0, 1, 2, 3, 4, 5); System.out.println(elements); final Iterator<Integer> iter = elements.iterator(); final Integer elt0 = iter.next(); final Integer elt1 = iter.next(); System.out.println(elt0); // 0 System.out.println(elt1); // 1 iter.remove(); final Integer eltNext = iter.next(); // 2 System.out.println(eltNext); elements.add(6); // CME while (iter.hasNext()) { System.out.println(iter.next()); } } |
Cela vous montre une bonne façon de « niquer » un programme. Au passage c’est aussi pour ça que je n’aime pas définir des Iterators pour les parcourir à l’aide d’une boucle « while ». Je préfère faire le tout dans une boucle « for », ce qui permet de réduire et de mieux maîtriser la portée des variables :
1 2 3 | for(final Iterator<Integer> iter = elements.iterator(); iter.hasNext();) { System.out.println(iter.next()); } |
En effet, un des problèmes que je vois avec le « while », mais surtout avec la déclaration en dehors de la boucle, c’est qu’il peut se passer plein d’autres choses dans la méthode. Alors évidement, le fait d’être dans une boucle « for » ne va rien empêcher, mais j’ai le sentiment que ça limite les dégats car les développeurs auront tendance à faire moins de Rock’n Roll
J’ai ajouté une version utilisant un PeekingIterator
Bonjour Thierry,
J’aurais certainement procéder de la sorte, avec l’instanciation d’un TreeSet, afin d’avoir un Set trié sur les valeurs à comparer.
1 – Création d’une classe encapsulant un Integer, ainsi qu’une référence vers la liste d’Integer d’origine (vous allez comprendre pourquoi) : IntegerBox (nom choisi en moins d’une seconde).
class IntegerBox { private final Integer value; private final List list; }
2 РLors de la g̩n̩ration des valeurs en sortie :
a) Création des IntegerBox pour chaque valeur de chaque liste, avec initialisation de la référence sur la liste.
a) Création du TreeSet et initialisation avec les 1ères valeurs de chaque liste
b) lors du parcours, prendre la valeur la + petite du TreeSet (méthode first() ), et la retirer du TreeSet
c) placer dans le TreeSet, la valeur de next(), sur la liste contenue dans l’IntegerBox.
3 – Et voilÃ
Cordialement,
Issam El Hachimi
Bonjour,
Merci pour cette proposition. J’avoue toutefois n’avoir pas très bien compris
Un peu de code aiderait…
J’ai aussi pensé à une version encore mieux utilisant le PeekingIterator de Guava et que je vous montrerai la semaine prochaine.
En gros :
2
3
4
5
6
7
8
9
10
11
12
private final Integer value;
private final Iterator<Integer> iterator;
public IntegerBox(Integer value, Iterator<Integer> iterator) {
this.value = value;
this.iterator = iterator;
}
// Getter & setter
// hashcode + equals
L’itérateur :
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private final TreeSet<IntegerBox> valuesToCompare;
private final Comparator<IntegerBox> comparator;
public MultiIterator() {
comparator = new MyComparator();
valuesToCompare = new TreeSet<IntegerBox>(comparator);
}
public void addList(List<Integer> list){
if(list == null || list.size() < 1){
return;
}
Iterator<Integer> iterator = list.iterator();
IntegerBox integerBox = new IntegerBox(iterator.next(), iterator);
valuesToCompare.add(integerBox);
}
public void run(){
while(valuesToCompare.size() > 0){
IntegerBox integerBoxToDisplay = valuesToCompare.first();
Iterator<Integer> iterator = integerBoxToDisplay.getIterator();
System.out.println(integerBoxToDisplay);
valuesToCompare.remove(integerBoxToDisplay);
if(iterator.hasNext()){
IntegerBox integerBoxToAdd = new IntegerBox(iterator.next(), iterator);
valuesToCompare.add(integerBoxToAdd);
}
}
}
private class MyComparator implements Comparator<IntegerBox>{
@Override
public int compare(IntegerBox object1, IntegerBox object2) {
return object1.getValue().compareTo(object2.getValue());
}
}
}
Enfin, le main d’exemple :
2
3
4
5
6
7
8
9
10
// Arrange
final List<Integer> listA = Arrays.asList(4, 3, 1);
final List<Integer> listB = Arrays.asList(5, 4, 2);
MultiIterator multiIterator = new MultiIterator();
multiIterator.addList(listA);
multiIterator.addList(listB);
multiIterator.run();
}
Et que se passe-t-il si le contenu des iterator est changé durant l’execution ?
En utilisant des ListIterator, il ne devrait pas y avoir de ConcurrentModificationException.
A tester
C’est surtout que je voudrais que ce soit dynamique et qu’on puisse modifier les itérators pendant l’utilisation.
Précisions : Cela nécessite de créer un Comparator, comparant sur les champs IntegerBox.value.
pas mal l’exercice faudrait le proposer à tes élèves ;).
Si je comprends le but est de réaliser le travail de reconstruction du merge sort ?
J’aurais préféré un exercice autour de l’appareillage d’itérateur, une idée pour un prochain billet/exercice ?
Juste une petite remarque, la méthode remove() doit supprimer le dernier élément renvoyé par next() ! Il suffit de conserver l’itérateur qui a servi à renvoyer le dernier élément.
C’était pour un tri par insertion monotone mais ça marche pareil pour un tri fusion : bien vu.
Pour être franc, je n’ai jamais utilisé de ma vie la méthode remove() des Iterators. Du coup je ne me suis pas encore attaqué à la question.