:: Enseignements :: Master :: M1 :: 2021-2022 :: Java Avancé ::

Examen de Java Avancé

Le but de ce TP noté est d'implanter une structure de données appelée SnapList qui est une liste contenant deux listes : une liste principale d'éléments et une liste d'éléments snapshot. Un élément snapshot est un élément qui résume une sous-liste des éléments déjà présents dans la liste principale.
L'intérêt de cette structure de données est qu'un élément snapshot correspond à un pré-calcul que l'on est pas obligé de faire de multiples fois : par exemple, on peut avoir une liste d'entiers, avec comme éléments snapshots des sommes intermédiaires des éléments de la liste principale ; comme ça, lorsque l'on veut faire la somme de la liste, on peut accélérer le calcul en faisant la somme des éléments snapshot plus la somme des éléments qui ne correspondent pas encore à un snapshot.

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 17 est là : https://igm.univ-mlv.fr/~juge/javadoc-17/api/index.html.
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 - SnapList

La classe SnapList contient deux listes : elements, qui est la liste principale de tous les éléments, et snapshots, qui est la liste des valeurs de snapshot déjà créés. Une SnapList est créée avec une fonction de snapshot qui est une fonction qui, à une sous-liste d'éléments, associe un seul élément de même type que ceux de la SnapList qui "résume" les éléments de la sous-liste.
La classe SnapList est paramétrée par le type des éléments et les éléments ne peuvent pas être null.
La classe SnapList possède les méthodes suivantes :

add(element), qui permet d'ajouter un élément dans la SnapList.
elementSize(), qui renvoie le nombre d'éléments de la SnapList.
snapshot(), qui appelle la fonction de snapshot avec tous les éléments pas encore snapshotés et stocke le résultat de la fonction dans la liste des snapshots
canSnapshot(), qui indique si un snapshot est possible, c'est à dire si la SnapList possède des éléments par encore snapshotés
snapshotList(), qui renvoie une liste non modifiable de tous les snapshots (les valeurs de retour des appels successifs à la fonction de snapshot).
forEach(fonction), qui appelle la fonction prise en paramètre avec tous les snapshots ainsi que tous les éléments pas encore snapshotés.
iterator(), qui permet de parcourir tous les snapshots ainsi que tous les éléments pas encore snapshotés.
autoSnapshot(n), qui demande à ce que la SnapList fasse un snapshot automatique après l'ajout de n éléments.

Voici un exemple d'utilisation. Si on reprend l'idée de faire une somme d'entiers, on va déclarer une SnapList ainsi :

       var snapList = new SnapList<Integer<(list -> list.stream().mapToInt(v -> v).sum());

c'est à dire une SnapList dont la fonction de snapshot prend une sous-liste des entiers en paramètre et fait la somme de ces entiers.
On peut ensuite ajouter des éléments avec la méthode add :

      snapList.add(10);
      snapList.add(20);
      snapList.snapshot();

Puis l'appel à la méthode snapshot récupère l'ensemble des éléments pas encore snapshotés (ici 10 et 20) et appelle la fonction de snapshot indiquée à la construction avec une liste non mutable des ces éléments. Dans notre exemple, list -> list.stream().mapToInt(v -> v).sum() est appelée avec une liste contenant les éléments 10 et 20. Le résultat est 30 (on fait la somme) et ce résultat est stocké dans la liste des snapshots.
Donc si on exécute

      snapList.snapshotList();  // [30]

on obtient le contenu de la liste des snapshot : dans notre exemple, une liste contenant la valeur 30.
Ensuite, on peut ajouter de nouvelles valeurs et appeller la méthode snapshot :

       snapList.add(30);
       snapList.add(40);
       snapList.add(50);
       snapList.snapshot();

La fonction de snapshot (list -> list.stream().mapToInt(v -> v).sum()) est, cette fois-ci, appelée avec une liste contenant les éléments 30, 40 et 50 qui n'ont pas encore été snapshotés. Le résultat est 120; il est stocké dans la liste des snapshots.
Ensuite, on refaire appel à snapshotList() :

       snapList.snapshotList();  // [30, 120]

En termes d'implantation, une SnapList ne doit contenir que 4 champs, la liste des éléments (elements), la liste des snapshots (snapshots), la fonction de snapshot (snapshotFunction) et un entier (finger) qui indique le premier élément non snapshoté (ou si vous préférez, les éléments entre 0 et finger exclu sont les éléments déjà snapshotés).

Des tests unitaires correspondant à l'implantation sont ici : SnapListTest.java.

Écrire la classe SnapList avec son constructeur et ses méthodes add et elementSize ainsi que la méthode d'affichage classique telle que le code ci-dessous fonctionne :
```
        var snapList = new SnapList<String>(list -> "");
        snapList.add("1");
        snapList.add("2");
        snapList.add("3");
        assertEquals(3, snapList.elementSize());
        System.out.println(snapList);   // [1 | 2 | 3]
      
```
Pour l'affichage, les éléments doivent être séparés par des '|' avec un espace avant et un espace après, et la liste des éléments est entourée des caractères '[' et ']'.
Vérifier que les tests unitaires marqués "Q1" passent.

On souhaite ajouter les méthodes canSnapshot et snapshot sachant que canSnapshot indique s'il y a des éléments qui n'ont pas encore été snapshotés et que snapshot ne doit pas fonctionner si on appelle cette méthode alors que canSnapshot renvoie faux, parce qu'il ne doit pas être possible de faire un appel à snapshot sans nouveaux éléments.
Écrire les méthodes canSnapshot et snapshot et vérifier que les tests unitaires marqués "Q2" passent.

Ajouter la méthode snapshotList qui renvoie une liste non modifiable des valeurs des snapshots (les valeurs de retour de l'appel de la fonction de snapshot).
Vérifier que les tests unitaires marqués "Q3" passent.

On souhaite créer une version thread-safe de SnapList. Pour cela, dupliquer le code de SnapList dans une nouvelle classe ThreadSafeSnapList et modifier le code pour qu'il soit bel et bien thread-safe.
Note : attention au problème de publication.
Note2: attention à ne pas avoir des sections critiques trop grandes ou inutiles.
Vérifier avec que les tests unitaires du fichier ThreadSafeSnapListTest.java que vous n'avez pas fait d'erreurs bêtes...
Note : si les tests sont faux, vous savez qu'il y a un problème, si les tests sont bons, vous ne savez pas si votre code est thread-safe ou pas, car il peut manquer un test, par exemple...

On souhaite ajouter une méthode forEach(fonction) qui appelle la fonction prise en paramètre avec les valeurs des snapshots puis les éléments pas encore snapshotés.
Cela permet, par exemple, de faire la somme des éléments : il faut faire la somme des sommes intermédiaires (la somme des valeurs snapshots) et ajouter la somme des éléments pour lesquels il n'y a pas encore de snapshot.
Écrire la méthode forEach.
Vérifier que les tests unitaires marqués "Q5" passent.

On souhaite maintenant écrire une méthode iterator qui renvoie les mêmes valeurs et dans le même ordre que forEach.
On considère pour le moment qu'une fois l'itérateur créé, la SnapList correspondante ne sera pas modifiée.
On souhaite de plus, qu'il ne soit pas possible de supprimer des valeurs en utilisant l'itérateur.
Vérifier que les tests unitaires marqués "Q6" passent.

Ajouter à la classe SnapList un mécanisme de détection des mutations et changer l'implantation de l'itérateur pour que lorsque l'on appelle next, une exception ConcurrentModificationException soit levée si l'on effectue des mutations en même temps que l'on parcours la SnapList avec l'itérateur.
Vérifier que les tests unitaires marqués "Q7" passent.

Enfin, on souhaite ajouter une méthode autoSnapshot(n) qui demande à la SnapList d'appeler la méthode snapshot lorsque n éléments ont été ajoutés depuis la précédent appel à snapshot.
De plus, si on fait un second appel à autoSnapshot(n), la valeur de n devra être plus grande ou égale à la valeur précédente.
Note : contrairement aux questions précédentes, pour cette question, vous avez le droit d'ajouter un champ dans la classe SnapList.
Vérifier que les tests unitaires marqués "Q8" passent.