:: Enseignements :: ESIPE :: E4INFO :: 2018-2019 :: Java Avancé ::

Structure de donnée persistante (fonctionnelle)

Le but de ce TP est d'implanter une classe fr.umlv.seq.Seq qui représente une séquence (comme une liste) non mutable d'éléments non null. Les élément sont stockés en interne dans un tableau, avec une implantation un tout petit peu astucieuse pour essayer de partager les tableaux stockant les éléments entre les différentes instances de Seq.

Exercice 1 - Seq

La classe fr.umlv.seq.Seq est paramétrée par le type des éléments qu'elle contient.

La classe Seq est munie des opérations initiales suivantes:

empty qui permet de créer une séquence vide (avec un tableau de 4 cases vides au départ);
append(element) que l'on appelle sur une séquence et qui crée et renvoie une nouvelle séquence (une nouvelle instance) qui possède tous les éléments de la première séquence plus l’élément passé en paramètre ajouté à la fin.
La méthode append ne détruit pas et ne modifie pas la séquence sur laquelle elle est appelée, mais renvoie une nouvelle séquence.
Par contre, en terme d'implantation, on essaie de faire en sorte que la séquence sur laquelle on appelle append et la séquence renvoyée par append partagent le même tableau, si c'est possible.
Dans le cas où le tableau doit être agrandi car il est plein, on doublera sa taille pour éviter de faire trop d'allocations de tableaux.
size qui indique le nombre d'éléments dans la séquence (en O(1), bien sûr).
Comme la séquence est non mutable, le nombre d'éléments de la séquence ne change pas.

Par exemple, le code suivant crée trois séquences, une séquence vide, une séquence contenant la valeur "toto" et une séquence contenant les valeurs "toto" et "titi".

      var seq1 = Seq.<String>empty();
      var seq2 = seq1.append("toto");
      var seq3 = seq2.append("titi");

On peut noter que dans l'exemple ci-dessus, les séquences seq1, seq2 et seq3 peuvent toutes partager le même tableau (initialisé à 4 cases par empty) qui contient les valeurs "toto", "titi", null et null. En effet, si chaque séquence connaît sa taille, elle sait combien de cases elle a le droit de lire dans le tableau.
Par contre avec le code suivant, il n'est pas possible de partager le tableau entre toutes les séquences.

      var seq1 = Seq.<String>empty();
      var seq2 = seq1.append("toto");
      var seq3 = seq1.append("titi");

Ici, seq2 contient la valeur "toto" tandis que seq3 contient la valeur "titi". Dans ce cas, il faut que lors de la création de seq3, on se rende compte que seq1 (la séquence sur laquelle on appelle append) partage déjà son tableau avec seq2.

Important: les séquences doivent rester non mutables en terme d'implantation.

Les tests unitaires JUnit 5 correspondant à l'implantation sont ici: SeqTest.java.

Écrire la classe Seq, ainsi que les méthodes empty, append et size de telle façon à ce que les tests correspondant à la question 1 passent.
Note: java.util.Arrays.copyOf() permet de dupliquer un tableau avec une nouvelle taille.
Vérifier que les tests correspondants à la question 2 passent aussi. Vérifier également qu'il ne reste pas de warning et que vous pouvez justifier leur suppression quand c'est nécessaire.
Écrire une méthode forEach qui prend une fonction qui prend un élément en paramètre et appelle cette fonction avec l'ensemble des éléments de la séquence.
Vérifier que les tests correspondant à la question passent.
Écrire la méthode d'affichage d'une séquence de telle façon que si la séquence contient les valeurs 3, 5 et 8, alors l'affichage est <3, 5, 8>.
Écrire une méthode map qui prend en paramètre une fonction qui elle-même prend un paramètre et renvoie une valeur. Cette méthode renvoie une nouvelle séquence qui, si on la parcourt avec forEach (ou que l'on ajoute un élément avec append) montre que chaque élément de la séquence renvoyée est égal à l'élément de la séquence sur laquelle on a appelé map et auquel on applique la fonction prise en paramètre par map.
Quelle doit être la signature de map?

On veut une implantation paresseuse (lazy) de la méthode map, c'est à dire que l'on ne veut pas que map calcule les valeurs de la séquence renvoyée mais que les valeurs de la séquence renvoyée soient calculées uniquement si l'on appelle la méthode forEach (ou append) sur la séquence renvoyée.
Si vous préférez, tant que l'on observe pas les valeurs de la séquence renvoyée par map alors la fonction prise en paramètre par map ne doit pas être appelée, par contre celle-ci peut être appelée à chaque appel de forEach sur la séquence renvoyée.
Quel doit être le type du tableau contenu dans un objet Seq désormais? Pourquoi?
Vérifier que les tests correspondant à la question passent.
Écrire une méthode findFirst qui renvoie le premier élément sous la forme d'un Optional car le premier élément peut ne pas exister.
Vérifier que les tests correspondant à la question passent.
Écrire une méthode appendAll qui prend en paramètre une séquence et renvoie une nouvelle séquence contenant tous les éléments de celle-ci ajoutés aux élément de la séquence sur laquelle on appelle appenAll.
appendAll est équivalent à appeler autant de fois append qu'il y a d'éléments dans la séquence prise en paramètre.
Vérifier que les tests correspondant à la question passent.
Écrire une méthode of qui permet de créer une séquence à partir des élément passés en arguments de la méthode of (dans le même ordre).
Vérifier que les tests correspondant à la question passent.
Écrire une méthode iterator qui permet de parcourir les éléments d'une séquence puis faite en sorte de pouvoir parcourir une séquence avec une boucle for(:).
Vérifier que les tests correspondant à la question passent.