Série 2 – Généricité

Cette série est la deuxième du micro-projet consacré aux collections. Comme pour la première série vous placerez tout votre code dans le paquetage ch.epfl.collections.

Le but de ce premier exercice est de rendre générique les listes de la série précédente afin qu'elles puissent stocker des éléments d'un type quelconque et plus seulement des chaînes de caractères. Cela implique de rendre génériques l'interface StringList (qui devient List) puis les deux classes StringArrayList (qui devient ArrayList) et StringLinkedList (qui devient LinkedList).

Pour faciliter votre travail, nous mettons à votre disposition la solution de la première série. Vous pouvez choisir de modifier directement votre propre code ou de partir de notre solution.

Lors de l'écriture de la classe ArrayList, une difficulté que vous rencontrerez très vite est celle de la création du tableau sous-jacent. Comme vu au cours, ce tableau doit logiquement avoir le type E[], où E est le paramètre de type de la classe ArrayList. Malheureusement, s'il est effectivement autorisé de déclarer un tableau de ce type en Java, il n'est pas possible d'en créer un à cause de limitations du langage. Pour résoudre ce problème, il n'y a rigoureusement qu'une solution, à savoir passer par ce qu'on appelle la réflexion. Comme vous n'avez pas encore vu ce concept, nous nous contenterons d'une solution moins propre mais qui fonctionne dans notre cas. Elle consiste à créer un tableau de Object, que l'on « transtype » ensuite pour pouvoir l'affecter au tableau sous-jacent de type E[].

Une fois vos classes rendues génériques, faites de même avec vos tests unitaires et vérifiez qu'ils s'exécutent sans erreur.

Après avoir implémenté les classe générique ArrayList et LinkedList, supprimez votre interface Iterator et utilisez celle de Java, java.util.Iterator, à sa place. Cela implique deux changements :

1. Vous devez ajouter la méthode remove à vos classes. Dans un premier temps, faites-lui simplement lever l'exception UnsupportedOperationException.
2. Vous devez garantir que la méthode next lève l'exception NoSuchElementException si on l'appelle alors que la fin de la liste a été atteinte (c-à-d si hasNext retournerait faux).

Une fois ces changements effectués, ajoutez un cas à vos tests de listes pour vérifier que next lève bien l'exception dans le cas décrit ci-dessus.

Il devient maintenant simple de permettre le parcours de vos listes au moyen de la boucle for-each de Java. Faites les modifications nécessaires pour que ce soit le cas, puis ajoutez une méthode à vos classes de tests de listes pour vérifier que ce type de parcours fonctionne.

Pour améliorer l'encapsulation de votre code, imbriquez (de manière statique) la classe des nœuds de la liste chaînée dans la classe de la liste.

Ensuite, transformez les classes des itérateurs en classes anonymes imbriquées dans leur méthode iterator. Une fois cela fait, il devient plus simple d'écrire la méthode remove de ces itérateurs. Comme spécifié dans la documentation Java, cette méthode doit supprimer le dernier élément retourné par next. Elle doit de plus lever l'exception IllegalStateException si next n'a pas encore été appelée, ou si deux appels à remove sont faits successivement sans appel à next entre les deux.

Une fois les méthodes remove écrites, ajoutez des méthodes à vos tests de listes pour vérifier qu'elles ont le comportement attendu, aussi bien en cas d'utilisation normale que lorsqu'une exception doit être levée.