Série 1 – Test unitaire

Le but de cette série est de vous exercer à écrire des tests unitaires, en en écrivant pour une classe que nous vous fournissons et qui contient quelques erreurs.

La classe que vous devrez tester (et corriger par la suite) met en œuvre ce qu'on appelle une queue bornée d'entiers. En informatique, une queue (bornée ou non) est une collection, c-à-d un objet qui sert de conteneur à d'autres objets. Vous connaissez déjà trois types de collections, à savoir les tableaux, les listes et les piles. Ces deux dernières collections ont été brièvement évoquées lors de la dernière leçon du semestre précédent.

La particularité d'une queue est que les éléments qu'elle contient en ressortent dans le même ordre que celui dans lequel ils ont été insérés. Pour cette raison, une queue est parfois appelée FIFO en anglais, pour first in, first out (premier entré, premier sorti). Une queue est donc simplement une liste dans laquelle on ajoute toujours les éléments à une extrémité, tandis qu'on les ressort depuis l'autre extrémité. Pour mémoire, une pile est quant-à-elle LIFO (last in, first out) puisque les éléments en ressortent dans l'ordre inverse de leur insertion.

Lorsqu'elle est bornée, une queue est caractérisée par sa capacité, c-à-d le nombre maximum d'éléments qu'elle peut contenir. Une queue qui ne contient aucun élément est dite vide, tandis qu'une queue qui en contient autant que sa capacité le permet est dite pleine. Notez que, d'après ces définitions, une queue de capacité 0 est à la fois vide et pleine.

Pour illustrer ces notions au moyen d'un exemple, imaginons que l'on crée une queue bornée d'entiers d'une capacité de 5 éléments. Initialement, cette queue est vide, ce qu'on peut représenter ainsi, les points d'interrogation représentant la capacité non utilisée de la queue :

?

?

?

?

?

Ensuite, admettons que l'on ajoute l'entier 2014 à la queue. Elle ressemble alors à ceci :

2014

?

?

?

?

Ajoutons ensuite l'entier 12. On obtient alors la queue suivante :

2014

12

?

?

?

Finalement, ajoutons les entiers 1, 2 et 3, dans cet ordre. La queue est maintenant pleine, et ressemble à ceci :

2014

12

1

2

3

Si on retire maintenant un élément de cette queue, on retire celui qui se trouve au début, conformément au principe FIFO. On obtient alors l'entier 2014, et la queue n'est maintenant plus pleine, puisqu'on pourrait lui ajouter un nouvel entier.

12

1

2

3

?

Si l'on ajoute maintenant un dernier entier, disons 50, la queue ressemble à ceci :

12

1

2

3

50

Pour travailler sur cette série nous vous recommandons de créer un nouveau projet Java et d'y créer un paquetage ch.epfl.ppo dans lequel vous travaillerez. Toutes les classes que nous distribuons se trouvent dans ce paquetage.

Les différentes mises en œuvre des queues d'entiers bornées avec lesquelles vous travaillerez pour cette série implémentent toutes l'interface BoundedIntQueue.java du paquetage ch.epfl.ppo que nous vous fournissons et que vous devez télécharger et intégrer à votre projet. Les commentaires JavaDoc attachés aux méthodes de cette interface spécifient leur comportement.

En plus de cette interface, nous vous fournissons une classe nommée ch.epfl.ppo.BoundedIntQueueBuggy qui implémente BoundedIntQueue mais qui, comme son nom l'indique, a quelques problèmes. Le but de ce premier exercice est de détecter ces problèmes au moyen de tests unitaires, sans regarder le code de la classe, ce qu'on appelle généralement test en boîte noire. Pour cette raison, nous vous fournissons uniquement un fichier JAR, c-à-d une archive contenant la version compilée de la classe à tester. Pour l'ajouter à votre projet, procédez ainsi :

1. téléchargez le fichier BoundedIntQueueBuggy.jar,
2. ouvrez les propriétés de votre projet (menu Project puis Properties), et sélectionnez Java Build Path,
3. activez l'onglet Libraries puis cliquez sur Add External JARs…,
4. dans la fenêtre qui s'ouvre alors, choisissez le fichier JAR que vous venez de télécharger et confirmez,
5. fermez les propriétés de votre projet en cliquant sur Ok.

Vous avez maintenant la possiblité d'utiliser la classe BoundedIntQueueBuggy sans pour autant pouvoir voir son code source.

Ecrivez alors un test unitaire pour cette classe, en ouvrant le menu File, puis New et en sélectionnant JUnit Test Case. Cela créera un squelette de test, auquel vous devez maintenant ajouter des méthodes de test pour les différentes méthodes de la classe ch.epfl.ppo.BoundedIntQueueBuggy. A noter que cette classe possède un unique constructeur qui prend en argument la capacité de la queue, sous forme d'un entier. Ce constructeur devrait lever l'exception IllegalArgumentException si la capacité est inférieure à zéro.

Pensez à écrire au minimum une méthode de test par méthode existant dans l'interface BoundedIntQueue, et à tester également que les exceptions qui devraient être levées le sont bien. Lisez bien les commentaires dans le fichier BoundedIntQueue.java pour vous guider.

Vos tests devraient vous permettre de détecter un certain nombre de problèmes dans notre classe, dont vous devez prendre note avant de continuer.

Ecrivez maintenant une classe ch.epfl.ppo.BoundedIntQueueOk, qui implémente (correctement) l'interface BoundedIntQueue. Il va de soi que vous pouvez utiliser le test écrit lors de l'exercice précédent pour la tester.

Une manière simple (mais peu efficace) de mettre en œuvre une queue bornée consiste à stocker ses éléments dans un tableau de taille égale à la capacité de la queue, en s'assurant que l'élément en début de queue se trouve toujours à l'indice 0, exactement comme illustré plus haut.

Avec une telle représentation, l'opération removeFirst est chère à mettre en œuvre puisqu'elle implique la copie d'un nombre d'éléments égal à la taille de la queue après la suppression… Notez que cette copie peut se faire au moyen d'un simple appel à la méthode statique arraycopy de la classe System.

Une manière plus efficace, mais plus complexe, de mettre en œuvre une queue bornée consiste à autoriser l'élément en début de queue de se trouver n'importe où dans le tableau, et pas uniquement en position 0. Vous pouvez également essayer d'utiliser cette idée pour mettre en œuvre la queue bornée, mais attention, cela n'est pas facile !

Quelle que soit la solution que vous choisissez, pensez à placer des assertions dans votre code, aux endroits où cela vous semble judicieux.

Une fois votre classe BoundedIntQueueOk écrite et correcte, téléchargez le fichier GetSecretURL.java. Il contient un petit programme qui utilise une queue bornée pour calculer une valeur secrète.

Si vous exécutez ce programme sans le modifier, il utilise la version incorrecte de la queue bornée que nous vous avons fournie (BoundedIntQueueBuggy), et imprime alors le message suivant :

Téléchargez le code source de BoundedIntQueueBuggy à cette adresse :
http://cs108.epfl.ch/files/wzc22k/BoundedIntQueueBuggy.java

Malheureusement, l'adresse fournie est invalide, justement parce qu'elle a été calculée avec une queue bornée incorrecte. Modifiez maintenant la méthode newBoundedIntQueue de la classe GetSecretURL pour qu'elle utilise votre mise en œuvre de la queue bornée, puis relancez le programme. Si votre mise en œuvre de la queue bornée est correcte, vous devriez voir une adresse différente, et en l'entrant dans un navigateur Web, vous devriez pouvoir télécharger le code source de notre classe BoundedIntQueueBuggy.

Si tel est le cas, importez cette classe dans votre projet puis essayez de trouver et de corriger toutes les erreurs qu'elle contient. Pour la tester, utilisez bien entendu votre classe de test ! Notez que cette classe utilise la mise en œuvre rapide, mais plus compliquée, mentionnée à la fin de l'exercice 2.