:: Enseignements :: Master :: M1 :: 2014-2015 :: Java Avancé ::

Faites la queue

Le but de ce TD est d'implanter une file d'attente en utilisant un tableau de façon circulaire et de jouer un peu avec les types paramétrés.

Exercice 1 - Fifo

On souhaite écrire une structure de données first-in first-out (FIFO) utilisant un tableau circulaire qui aura, au moins au début, une taille fixée à la création.
Les deux opérations principales sont offer qui permet d'insérer un élement à la fin de la file et poll qui permet de retirer un élement en début de la file.
L'idée est d'utiliser deux index, un correspondant à la tête de la file pour retirer les élements et un index correspondant à la queue de la file pour ajouter des élements. Lorsque l'on insère un élement, on incrémentera la queue de la file, lorsque l'on retirera un élement, on incrémentera la tête de la file.
De plus, il est impossible de stocker null dans la file.

Cette représentation a un petit problème car si la tête et la queue ont la même valeur, il n'est pas facile de détecter si cela veux dire que la file est pleine ou vide.
Comment doit on faire pour détecter si la file est pleine ou vide ?
Cette question a plusieurs réponses :)
Ecrire une classe Fifo dans le package fr.umlv.queue prenant en paramètre le nombre maximal d'élements que peut stocker la structure de données. Penser à vérifier les préconditions.
Ajouter une méthode offer qui ajoute un élement de type Object dans la file. Penser à vérifier les préconditions sachant que, de plus, on veut interdire de pouvoir stocker null.
Comment détecter que la file est pleine ?
Que faire si la file est pleine ?
Ecrire une méthode poll qui retire un élement de type Object de la file. Penser à vérifier les préconditions.
Que faire si la file est vide ?
Rappeler ce qu'est un memory leak en Java et assurez-vous que votre implémentation n'a pas ce comportement indésirable.
Ajouter une méthode size et une méthode isEmpty.
Ajouter une méthode d'affichage qui affiche les élements dans l'ordre dans lequel ils seraient sortis en utilisant poll.
Note: attention à bien faire la différence entre la file pleine et la file vide.
L'ensemble des élements devra être affiché entre crochets ('[' et ']') avec les élements séparés par des virgules.

Vérifier avec le test unitaire suivant que votre implantation est bien conforme. FifoTest.java

Exercice 2 - Generics, generics

On souhaite générifier la classe Fifo.

Rappeler quel est l'intérêt de déclarer Fifo comme un type paramétré.
Rappeler pourquoi il n'est pas possible de creér un tableau de type paramétré.
Comment faire alors ?
Faire en sorte que la classe Fifo soit paramétrée.
Rappeler dans quel cas on peut utiliser @SuppressWarnings("unchecked").

Vérifier avec le test unitaire que votre implantation est bien conforme. Fifo2Test.java.

Exercice 3 - ResizableFifo

On souhaite maintenant que le tableau circulaire de la file puisse s'agrandir si jamais il n'y a plus assez de place.

Indiquer comment il faut agrandir la file si celle-ci est pleine et que l'on veut doubler sa taille. Attention, il faut penser au cas où le début de la liste à un index qui est supérieur à l'index indiquant la fin de la file.
Implanter la solution retenue dans une nouvelle classe ResizableFifo.
Note: il existe les méthodes Arrays.copyOf et System.arraycopy.
Rappeler quel est le principe d'un itérateur.
Implanter la méthode iterator() qui renvoie un Iterator<E>.
Note: ici, pour simplifier le problème, on considèrera que l'itérateur ne peut pas supprimer des éléments pendant son parcours.
Rappeler à quoi sert l'interface Iterable.
Faire en sorte que votre file implante Iterable.
En fait, il existe déjà une interface pour les files dans le JDK appelée java.util.Queue.
Sachant qu'il existe une classe AbstractQueue qui fournit déjà des implantations par défaut de l'interface Queue indiquer
1. quelles sont les méthodes supplémentaires à implanter.
2. quelles sont les méthodes dont l'implantation doit être modifiée.
3. quelles sont les méthodes que l'on peut supprimer.
Faire en sorte que la classe ResizableFifo implante l'interface Queue.

Vérifier avec le test unitaire suivant que votre implantation est bien conforme. ResizableFifoTest.java

Exercice 4 - [A la maison]

On souhaite utiliser la ResizableFifo créée ci-dessus pour faire un parcours en largeur d'un arbre (donc il n'y a pas de cycle).
On utilisera pour cela, la classe Tree fournie

Ecrire dans une classe Trees une méthode breadthFirstSearch prenant un objet Tree correspondant à la racine et renvoyant une liste de Tree correspondant à un parcours en largeur des noeuds de l'arbre.

Vérifier avec le test unitaire que votre implantation est bien conforme. TreesTest.java.