Spined buffer

Une SpinedBuffer est définie par la classe suivante

et s'utilise de la façon suivante

  SpinedBuffer seq = new SpinedBuffer(new Object[] { "a", "b" },
                                      new SpinedBuffer(new Object[] { "c" },
                                                       null));

Note: cette structure de données est appelée spined buffer (ou aussi spined list) car la structure ressemble à une colonne vertébrale (si si, de loin, en fermant un œil).

Exercice 1 - SpinedBuffer

1. La classe SpinedBuffer n'est pas générique, quel est l'intérêt de générifier celle-ci ?
   On voudrait, de plus, éviter à l'utilisateur d'écrire new Object[] { ... } à chaque fois que l'on veut transmettre des valeurs. Comment peut-on utiliser la syntaxe varargs (nombre d'arguments variable) pour simplifier l'utilisation?
   Quelle est la restriction sur l'utilisation des varargs ?
   Et quelle est la restriction sur l’utilisation des varargs de variable de type ?
   Modifiez le code en conséquence, sachant qu'il ne doit y avoir qu'un seul constructeur.
2. En fait, cette façon de faire est assez "bizarre", car on construit la liste chaînée à l'envers. De plus, l'utilisateur est obligé d'utiliser la valeur null pour indiquer le dernier maillon de la liste.
   Pour résoudre ces différents problèmes, l'idée est de modifier l'API de la classe SpinedBuffer en ajoutant des méthodes (factory) permettant de construire la liste chaînée plus facilement. De plus, pour éviter que l'utilisateur ne manipule null directement, on va cacher le constructeur.
   On souhaite créer une liste chaînée de séquences de la façon suivante:

      SpinedBuffer<String> seq = SpinedBuffer.of("c").prepend("a", "b");
    

   
   La méthode of permet de créer le dernier maillon de la chaîne, la méthode prepend permet d'ajouter un maillon devant un maillon existant.
   Modifiez votre implantation en conséquence.
   Vérifiez que votre implantation est correcte en utilisant les tests unitaires SpinedBufferTest
3. On souhaite écrire une méthode forEach qui prend un objet de type java.util.function.Consumer en paramètre et qui appelle le consommateur pour toutes les valeurs contenues dans tous les maillons de la liste chaînée.
   Quelle doit être la signature exacte de la méthode forEach ?
   Implantez la méthode forEach avec un algorithme récursif simple et vérifiez qu'elle passe les tests.
4. Pourquoi votre implantation ne fonctionne-t-elle pas avec le test testForEachBig ?
   Quel est le problème ?
   Comment doit-on modifier l'implantation ?
   Modifiez l'implantation en conséquence.
   En option (pour les courageux), il est possible d'implanter la méthode forEach avec un Stream.
5. Écrivez une méthode qui affiche la liste chaînée en affichant les valeurs contenues dans l'ensemble des maillons de la liste séparées par "->", par exemple avec une liste ayant 2 maillons stockant respectivement ["a", "b"] et ["c"], l'affichage est a -> b -> c.
   Note: ce n'est pas pour rien que cette question suit la précédente !
6. On souhaite écrire une méthode iterator qui renvoie un Iterateur non-mutable capable de parcourir l'ensemble des valeurs contenues dans l'ensemble des maillons.
   Il est très facile d'avoir une implantation qui ne suit pas complètement la spécification, donc pensez à vérifier que votre implantation est correcte en exécutant les tests unitaires correspondants.
    
   Une des difficultés ici, est de bien gérer le cas où un maillon contient un tableau vide... Sachant que les choix d'implantation sont cachés à l'utilisateur (et qu'il ne voit donc pas les maillons vides), comment peut-on gérer ce problème simplement ?
   Note: Le plus simple pour résoudre un problème est de ne pas en avoir !
   Écrivez la méthode iterator.
7. On souhaite pouvoir parcourir la liste chaînée avec une boucle for(:) comme ceci:

       SpinedBuffer<String> seq = ...
       for(String element : seq) {
         ...
       }
     

   
   Comment doit-on faire ?
   Pourquoi l'implantation de la méthode forEach n'est-elle plus nécessaire ?
   Faire les changements qui s'imposent.
8. On souhaite ajouter une méthode map sur le même modèle que Stream.map et qui produit une liste chaînée de séquences (pas un Stream, contrairement à map) obtenue en appliquant une méthode transformation pour chaque élément de chaque maillon.
   par exemple,

      SpinedBuffer<Integer> seq = SpinedBuffer.of(1, 2, 3);
      seq = seq.map(x -> x + 1);
      System.out.println(seq);  // 2 -> 3 -> 4
    

   
   Écrire la méthode map de façon récursive en faisant attention à sa signature.
   Note: Contrairement à Stream.map qui repousse le calcul jusqu'à l'appel d'une opération terminale, on se contentera ici d'une implantation plus "brutale", qui applique la transformation lors de l'appel à map.

Exercice 2 - This is spinal tap (Optionel)

1. Si map doit être implantée de façon paresseuse, cela veut dire que maintenant il y a deux implantations possibles pour un maillon. Une implantation sous forme d'un tableau de valeurs comme dans l'exercice précédent et une nouvelle implantation qui, au lieu de stocker des éléments, contient un pointeur vers un maillon ainsi que l'opération à effectuer sur ces valeurs.
   De plus, dans les deux cas, un maillon reste une structure chaînée, il est donc intéressant de séparer la notion de maillon de la notion de stockage des valeurs à l’intérieur d'un maillon, le stockage à l'intérieur d'un maillon ayant deux implantations possibles alors qu'un maillon, lui, ne possède qu'une seule implantation.
   Dans un premier temps, recopier le code de la classe SpinedBuffer de l'exercice précédent dans une nouvelle classe SpinalTap et modifier le code de celle-ci pour qu'il soit possible d'ajouter une nouvelle implantation pour le stockage des éléments d'un maillon.
   Note: l'idée est, pour l'instant, de ne pas modifier l'implantation de map mais juste de faire les changements qui s'imposent dans le but de faciliter après l'implantation de map de façon paresseuse en ajoutant une nouvelle façon de stocker des valeurs dans un maillon.
   Après avoir changé votre implantation, vérifier que les tests unitaires suivants SpinalTapTest (sauf testMapLazy) passent correctement (c'est à dire que vous n'avez pas introduit de régression de fonctionnalité en changeant le code).
   Info: La technique qui consiste à changer le code dans le but de faciliter l'ajout de fonctionnalités ultérieures s'appelle faire du "refactoring".
2. Changer l'implantation de map pour que celle-ci soit lazy en introduisant une nouvelle forme de "stockage" de éléments qui, au lieu de stocker les éléments, recalcule ceux-ci à la demande.
   Vérifier que le test testMapLazy passe correctement maintenant.
3. Pour ceux qui sont vraiment motivés... On peut remarquer que si l'on appelle deux fois map successivement sur une même liste chaînée, pour un maillon, au lieu d'avoir le "stockage" d'un maillon qui référence le "stockage" d'un maillon qui référence le tableau des éléments, il est possible de supprimer une étape en composant les fonctions des deux appels à map successifs.
   Comment faire pour détecter deux appels à map successifs ?
   Note: c'est tout con !
   Modifier votre implantation pour faire la composition des fonctions lors de deux appels à map successifs et vérifier que votre implantation passe l'ensemble des tests unitaires.