:: Enseignements :: Master :: M1 :: 2023-2024 :: Java Avancé ::

Faites la queue

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

Exercice 1 - Maven

Pour ce TP nous allons utiliser la même configuration Maven qu'habituellement.

     <project xmlns="http://maven.apache.org/POM/4.0.0"
              xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
              xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">

       <modelVersion>4.0.0</modelVersion>
       <groupId>fr.uge.fifo</groupId>
       <artifactId>fifo</artifactId>
       <version>0.0.1-SNAPSHOT</version>

       <properties>
         <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
       </properties>

       <dependencies>
         <dependency>
           <groupId>org.junit.jupiter</groupId>
           <artifactId>junit-jupiter-api</artifactId>
           <version>5.10.0</version>
           <scope>test</scope>
         </dependency>
       </dependencies>

       <build>
         <plugins>
           <plugin>
             <groupId>org.apache.maven.plugins</groupId>
             <artifactId>maven-compiler-plugin</artifactId>
             <version>3.11.0</version>
             <configuration>
               <release>21</release>
             </configuration>
           </plugin>

           <plugin>
             <groupId>org.apache.maven.plugins</groupId>
             <artifactId>maven-surefire-plugin</artifactId>
             <version>3.1.2</version>
           </plugin>
         </plugins>
       </build>
     </project>

Comme précédemment, créer un projet Maven, au niveau du premier écran, cocher create simple project puis passer à l'écran suivant en indiquant Next.
Pour ce TP, le groupId est fr.uge.fifo , l'artefactId est fifo et la version est 0.0.1-SNAPSHOT. Puis cliquer sur Finish.

Exercice 2 - Fifo

On souhaite écrire une structure de données pour représenter un file (first-in first-out ou FIFO) utilisant un tableau circulaire qui aura, au moins pour les premières questions, une taille fixée à la création. La taille doit être d'au moins 1 case et il est impossible de stocker null dans la file.
Les deux opérations principales sont offer qui permet d'insérer un élément à la fin de la file et poll qui permet de retirer un élément en début de la file.
L'idée est d'utiliser deux indices, un correspondant à la tête (head) de la file pour retirer les éléments et un correspondant à la queue (tail) de la file pour ajouter des éléments.
Prenons un exemple avec un tableau de 4 cases. Par défaut, la file est vide, on a head et tail à 0 :

       head   |
             xx xx xx xx
       tail   |

Si on ajoute l'élément 42 avec offer, on ajoute celui-ci à la fin de la liste, donc au niveau de tail, et on décale tail :

       head   |
             42 xx xx xx
       tail      |

Ensuite, si on ajoute respectivement 12 et 34, on obtient :

       head   |
             42 12 34 xx
       tail            |

Si on retire un élément (ici 42) avec poll, on retire l'élément à la position head et on décale head :

      head       |
             xx 12 34 xx
      tail             |

Enfin, si on ajoute les éléments 78 et 89, comme le tableau est vu comme un tableau circulaire, on obtient :

      head       |
             89 12 34 78
      tail       |

On peut remarquer que comme le tableau est plein, head et tail ont la même valeur.
Remarquez que si head et tail sont égaux, on ne sait pas si le tableau est vide ou si le tableau est plein... Il y a deux façons classiques de résoudre ce problème : soit le tableau n'est jamais plein et on garde toujours une case libre ; soit on ajoute un champ size qui contient le nombre d'éléments. Pour notre implantation, nous allons choisir la seconde solution.

Les tests JUnit 5 de cet exercice sont FifoTest.java.

On souhaite écrire une classe Fifo générique (avec une variable de type E) dans le package fr.uge.fifo prenant en paramètre une capacité (un entier), le nombre d’éléments maximal que peut stocker la structure de données.
On souhaite de plus, écrire la méthode offer qui permet d'ajouter des éléments à la fin (tail) du tableau circulaire sachant que pour l'instant on ne se préoccupera pas du cas où le tableau est plein. Et une méthode size qui renvoie le nombre d'éléments ajoutés.
Écrire le code correspondant.
Vérifier que les tests marqués "Q1" passent !
Note : la capacité n'est pas nécessairement une puissance de 2.

Avez-vous pensé aux préconditions ?
Vérifier que les tests marqués "Q2" passent.

On souhaite écrire une méthode poll qui retire un élément du tableau circulaire et une méthode peek qui récupère cet élement sans le retirer. Que faire si la file est vide ?
Écrire le code de les méthodes poll et peek.
Vérifier que les tests marqués "Q3" passent.

Rappelez ce qu'est un memory leak en Java et assurez-vous que votre implantation n'a pas ce comportement indésirable.
Pour cela, vous pouvez vérifier que les tests marqués "Q4" passent.

On souhaite agrandir le tableau circulaire dynamiquement en doublant sa taille quand le tableau est plein. Attention, il faut penser au cas où le début de la liste (head) a un indice qui est supérieur à l'indice indiquant la fin de la file (tail).
De plus, on va ajouter un nouveau constructeur sans paramètre qui, par défaut, crée un tableau circulaire de taille 16.
Modifier votre implantation pour que le tableau s'agrandisse dynamiquement en ajoutant une méthode resize.
Vérifier que les tests marqués "Q5" passent.
Note : il existe les méthodes Arrays.copyOf et System.arraycopy.

On souhaite ajouter une méthode d'affichage qui affiche les éléments dans l'ordre dans lequel ils seraient sortis en utilisant poll. L'ensemble des éléments devra être affiché entre crochets ('[' et ']') avec les éléments séparés par des virgules (suivies d'un espace).
Écrire la méthode d'affichage.
Vérifier que les tests marqués "Q6" passent.
Note : attention à bien faire la différence entre la file pleine et la file vide.
Note 2 : Il existe une classe StringJoiner qui est ici plus pratique à utiliser qu'un StringBuilder !

En fait, le code que vous avez écrit est peut-être faux (oui, les testent passent, et alors ?)... Le calcul sur les entiers n'est pas sûr/sécurisé en Java (ou en C, car Java à copié le modèle de calcul du C). En effet, une opération '+' sur deux nombres suffisamment grand devient négatif.
Si celà peut se produire dans votre code, modifiez-le ! L'astuce est d'utiliser deux indices, pour qu'il soit correct.
Dé-commenter le code du test correspondant à la question "Q7" et vérifier que votre code passe le test (comme on manipule des milliards d'objets, cela prend plusieurs dizaines de secondes).
Optionnellement, pour les plus balèzes, vous pouvez écrire aussi une version avec un Stream en faisant attention de ne pas avoir le même bug.

Rappelez quel est le principe d'un itérateur.
Quel doit être le type de retour de la méthode iterator() ? Implanter la méthode iterator().
Vérifier que les tests marqués "Q8" passent.
Note : ici, pour simplifier le problème, on considérera que l'itérateur ne peut pas supprimer des éléments pendant son parcours.

On souhaite que le tableau circulaire soit parcourable en utilisant une boucle for-each-in, comme ceci :
```
    var fifo = ...
    for(var value: fifo) {
      ...
    }
  
```
Quelle interface doit implanter la classe Fifo ?
Implanter cette interface et vérifier que les tests "Q9" passent.

Enfin, il existe déjà en Java une interface pour les files d'éléments, java.util.Queue, on souhaite maintenant que notre implantation de tableau circulaire Fifo implante cette interface.
Pour nous aider, il existe une classe abstraite java.util.AbstractQueue, qui implante déjà un certain nombre de méthodes de l'interface Queue, il ne vous reste plus qu'à implanter les méthodes manquantes.
Vérifier que les tests marqués "Q10" passent.