:: Enseignements :: ESIPE :: E4INFO :: 2024-2025 :: Java Avancé ::

Examen session 2 de Java Avancé 2024 - 2025

Le but de ce TP noté est d'implanter une classe UnorderedVec qui est une structure de données qui stocke des éléments dans un tableau et qui permet de supprimer les éléments lors d'un parcours en O(1) (en ne garantissant pas l'ordre d'insertion).

Vos sources Java produites pendant l'examen devront être placées sous le répertoire EXAM de votre compte ($HOME) (qui est vide dans l'environnement de TP noté). Sinon, elles ne seront pas récupérées.

Tout document papier est proscrit.
La javadoc 23 est https://igm.univ-mlv.fr/~juge/javadoc-23/.
Les seuls documents électroniques autorisés sont les supports de cours à l'url http://igm.univ-mlv.fr/~forax/ens/java-avance/cours/pdf/.

Vous avez le droit de lire le sujet jusqu'au bout, cela vous donnera une bonne idée de là où on veut aller !

Exercice 1 - UnorderedVec

La classe UnorderedVec représente une structure de données qui stocke les données dans l'ordre d'insertion lors des ajouts, mais qui ne conserve pas l'ordre d'insertion lors des suppressions.
En effet, lors de la suppression d'un élément, au lieu de décaler tous les éléments suivants (pour conserver l'ordre d'insertion), le dernier élément est mis à la place de l'élément que l'on veut supprimer, et la taille est réduite de 1.
De plus, pour éviter que les utilisateurs écrivent un programme qui dépende de l'ordre d'insertion sans faire attention, le parcours des éléments ne se fait pas dans l'ordre d'insertion. Au début du parcours, on appelle une fonction qui prend en paramètre la taille (size) de la structure de données renvoie un index entre 0 et size - 1 ; le parcours se fait à partir de cet index.
Pour notre implantation, nous utiliserons la fonction suivante

 private static int start(int size) {
   return size == 0 ? 0 : (int) ((size * 0x5DEECE66DL + 11) & 0x7FFFFFFF) % size;
 }

Par exemple, si on a 3 éléments foo, bar et baz, et que l'on exécute le code suivant...

var vec = new UnorderedVec<String>();
vec.add("foo");
vec.add("bar");
vec.add("baz");

for(String value : vec) {
  System.out.println(value);
}

... le programme affiche bar, puis baz, puis foo car start(3) renvoie la valeur 1, et donc on affiche les valeurs à partir de l'index 1.

La classe UnorderedVec est une classe paramétrée par le type des éléments (non null) que l'on va stocker dedans. Les éléments sont stockés dans un tableau qui s'agrandira si nécessaire.
La classe UnorderedVec possède les opérations suivantes

un constructeur qui permet de créer un UnorderedVec vide,
la méthode add(element) qui permet d'ajouter un élément,
la méthode size() qui renvoie le nombre d'éléments,
une méthode permettant le parcours des éléments dans l'ordre indiqué par la valeur renvoyée par la fonction start,
la méthode remove(value) qui supprime la première occurrence de la valeur si celle-ci est dans la structure de données.
La méthode d'affichage habituelle, qui affiche les éléments séparés par des virgules (le tout entre '<' et '>') avec les éléments dans le même ordre que lors d'un parcours.

Des tests unitaires correspondant à l'implantation sont ici : UnorderedVecTest.java
Note : comme on utilise les tests unitaires JUnit sans Maven, dans la configuration de votre projet, il faut ajouter la librairie JUnit 5, soit à partir du fichier UnorderedVecTest.java, en cliquant sur l'annotation @Test et en sélectionnant le quickfix "Fixup project ...", soit en sélectionnant les "Properties" du projet (avec le bouton droit de la souris sur le projet) puis en ajoutant la librairie JUnit 5 (jupiter) au ClassPath.

Dans un premier temps, on cherche à écrire la classe UnorderedVec, son constructeur, ainsi que les méthodes add et size.
Pour le stockage des éléments, on va utiliser un tableau de 16 cases. Nous verrons plus tard comment agrandir dynamiquement le tableau.
Écrire la classe UnorderedVec.
Vérifier que les tests unitaires marqués Q1 passent.

On veut maintenant pouvoir parcourir les éléments du tableau à partir de l'index donné par la fonction start en utilisant la boucle for avec la syntaxe ":" (deux points).
```
var vec = ...
for(var value : vec) {
  ...
}
      
```
Modifier le code de la classe en conséquence.
Vérifier que les tests unitaires marqués Q2 passent.

On souhaite maintenant pouvoir agrandir dynamiquement le tableau s'il y a plus de 16 éléments. L'agrandissement doit se faire en multipliant la taille du tableau par 2.
Le plus grand tableau possible doit être un tableau de taille Integer.MAX_VALUE - 16 (la machine virtuelle Java n'est pas capable de créer des tableaux de taille Integer.MAX_VALUE). Il vous faut donc gérer ce cas particulier.
Vérifier que les tests unitaires marqués Q3 passent.
Attention : penser à la gestion de l'overflow sur les entiers, Integer.MAX_VALUE / 2 * 2 est un nombre négatif !
Note : le test vecVeryBiiiiiig demande 16 Go de RAM, il faut donc lancer les tests avec -Xmx16G (au niveau des paramètres de la Machine Virtuelle (VM arguments). Si ce test passe, comme il est très lent (36 sec. sur ma machine), vous pouvez le commenter, il n'est pas vital pour la suite. Si vous n'arrivez pas à faire fonctionner ce test, passer à la suite.

On souhaite maintenant implanter la méthode remove(value) qui supprime la première occurrence (en partant de l'indice 0) de la valeur et la remplace par le dernier élément ajouté (si la valeur est présente).
Par exemple, si on ajoute foo, bar et baz puis que l'on supprime foo, le UnorderedVec devra maintenant contenir les éléments baz et bar car foo a été remplacé par baz (le dernier élément ajouté).
La valeur de retour de remove(value) est un booléen qui est vrai si un élément est effectivement supprimé.
Écrire la méthode remove(value).
Vérifier que les tests unitaires marqués Q4 passent.

On souhaite pouvoir afficher un UnorderedVec. Par exemple, avec les valeurs foo, bar et baz, l'affichage doit être <bar, baz, foo> car l'affichage se fait dans le même ordre qu'un parcours.
On vous demande de faire une implantation en utilisant un Stream.
Modifier le code la classe UnorderedVec en conséquence.
Vérifier que les tests unitaires marqués Q5 passent.
Rappel : nous avons vu en cours comment créer un Stream à partir d'un itérateur.

On souhaite pouvoir savoir si deux UnorderedVec sont égaux.
Pour cela, ils doivent avoir les mêmes éléments dans le même ordre dans leurs tableaux sous-jacents.
Modifier la classe UnorderedVec pour pouvoir tester si deux UnorderedVec sont égaux.
Vérifier que les tests unitaires marqués Q6 passent.

Si votre implantation est correcte, les tests marqués Q7 devraient aussi passer, si ce n'est pas le cas, identifier ce que vous avez oublié de faire et modifier votre implantation en conséquence.

On souhaite que la classe UnorderedVec implante l'interface Collection.
Modifier votre implantation en conséquence.
Vérifier que les tests marqués "Q8" passent.

Enfin, notre implantation est presque complète, il reste à implanter la méthode remove de l'itérateur.
Bien sûr, comme la méthode remove(value) de UnorderedVec, la méthode remove de l'itérateur doit aussi remplacer l'élément supprimé par le dernier élément du tableau (pour ne pas avoir une complexité pire cas en O(n^2)).
Écrire la méthode remove de l'itérateur.
Vérifier que les tests marqués "Q9" passent.