Examen de Java Avancé - session 2

Exercice 1 - FastSearchSeq

       FastSearchSeq<String> seq = ...
       for(String s: seq) {
         ...
       }
     

1. Dans un premier temps, on souhaite implanter la classe FastSearchSeq dans le package fr.umlv.util avec deux champs, le tableau des éléments dans un champ array, ainsi qu'un champ size qui indique le nombre d'éléments dans la structure de données.
   Le tableau sera initialisé avec une taille de 16, et pour l'instant on ne vous demande pas que la structure de données gère plus de 16 éléments.
   Écrire la classe FastSearchSeq et implanter les méthodes add et size.
   Vérifier que les tests unitaires marqués "Q1" passent.


2. On souhaite pouvoir afficher le contenu de la structure de données (les éléments séparés par des virgules suivies d'un espace) avec le code suivant :

           FastSearchSeq<String> seq = ...
           System.out.println(seq);
         

   
   Modifier votre code en conséquence sachant que l'on demande que votre implantation utilise un Stream.
   Vérifier que les tests unitaires marqués "Q2" passent.
   Indice : la classe java.util.Arrays contient plusieurs méthodes nommées stream.
   Note : si vous n'arrivez pas à implanter le code requis avec un Stream, essayer de faire différemment mais vous n'aurez pas tous les points correspondant à la question.


3. On veut maintenant que le tableau s’agrandisse automatiquement lorsque la structure de données doit contenir plus de 16 éléments, en s’agrandissant d'un facteur de 2 à chaque redimensionnement.
   Changer le code en conséquence et vérifier que tests unitaires marqués "Q3" passent.


4. On souhaite écrire une méthode contains qui renvoie vrai si un objet est contenu dans la structure de donnée et faux sinon.
   Implanter la méthode contains en utilisant là aussi un Stream.
   Vérifier que les tests unitaires marqués "Q4" passent.


5. Nous allons modifier le comportement la méthode contains, commencez par mettre votre précédente version en commentaire.
   En fait, on veut accélérer la recherche dans le cas où un même élément est recherché plusieurs fois de suite. Pour cela, lors d'une recherche, si l'objet recherché est présent, on va le déplacer vers le début du tableau.
   Nous allons utiliser l'algorithme suivant (pseudo code) :

          Après la recherche, si l'élément est présent à l'index index1
            On calcule le logarithme du nombre d'éléments (* voir indication ci-dessous *)
            Si la valeur d'index1  est inférieure ou égale à ce logarithme,
              alors l'élément est déjà devant dans le tableau, donc on ne fait rien.
            Sinon
              on tire un nombre aléatoire random (* voir indication ci-dessous *)
              on calcule une nouvelle position index2 comme étant le reste de la division
                entière de random par la valeur du logarithme calculé précédemment.
              on permute les éléments aux index index1 et index2.
         

   L'idée est que si l'élément n'est pas au début du tableau, on le déplace au début du tableau, mais pas toujours à la même place car lors du déplacement, on déplace aussi l'ancien élément vers la fin du tableau. Pour cela, on utilise une valeur pseudo aléatoire.
   Indication 1 : pour calculer une approximation entière du logarithme de façon rapide, vous devez utiliser le fait c'est équivalent à 31 moins le nombre de 0 en début du nombre d'éléments (Integer.numberOfLeadingZeros() en Java).
   Indication 2 : pour obtenir un nombre aléatoire de façon rapide, on utilise la valeur renvoyée par la méthode nextRandom suivante, en déclarant un champ random de type int initialisé avec 1.

           private int nextRandom() {
             var x = this.random;
             x ^= x << 13;
             x ^= x >> 17;
             x ^= x << 5;
             return this.random = x;
           }
         

   Modifier votre code pour implanter l'algorithme ci-dessus (et n'oubliez pas de commenter la partie de code correspondant à l'ancienne version de contains).
   Vérifier que les tests unitaires marqués "Q5" passent.
   Note : si vous n'y arrivez pas, passez aux questions suivantes !


6. On souhaite pouvoir faire une boucle sur les éléments présents dans la structure de données avec le code ci-dessous

           FastSearchSeq<String> seq = ...
           for(String s: seq) {
             ...
           }
         

   
   De plus, si jamais la structure de données est altérée pendant le parcours, c'est à dire si on ajoute un élément dans le code à l'intérieur de la boucle, l'exception habituelle doit être levée. On ne considère pas que les modifications apportées par un appel à contains altèrent la structures de données.
   Modifier votre code en conséquence et vérifier que les tests unitaires marqués "Q6" passent.
   Indice : la seule façon d'altérer la structure est d'ajouter un élément. On peut donc simplement vérifier si la taille change.


7. On souhaite ajouter une méthode forEachIndexed qui permet de parcourir tous les éléments présents dans la structure de données ainsi que leur indice actuel dans le tableau. Par exemple, si on a ajouté les éléments "j'aime", "le", "Java" à l'instance seq,

           seq.forEachIndexed((element, index) -> {
             System.out.println(element + " " + index);
           });
         

   alors le code ci-dessus affiche

           j'aime 0
           le 1
           Java 2
         

   
   Implanter la méthode forEachIndexed.
   Vérifier que les tests unitaires marqués "Q7" passent.
   Note : vous aurez besoin de définir votre propre interface fonctionnelle que l'on va appeler IndexedConsumer.


8. On souhaite ajouter une méthode onlyElement dans l'interface fonctionnelle IndexedConsumer de telle sorte qu'avec la même structure de données contenant "j'aime", "le", "Java", le code suivant

           seq.forEachIndexed(IndexedConsumer.onlyElement(System.out::println));
         

   affiche uniquement les éléments sans leur indice :

          j'aime
          le
          Java
         

   
   Ajouter la méthode onlyElement et vérifier que les tests unitaires marqués "Q8" passent.


9. On souhaite ajouter une méthode stream qui renvoie les éléments de 0 à la taile de la structure sous forme d'un Stream parallélisable (la taille est la taille au moment où la méthode stream est appelée). Contrairement au code pour le support de la boucle, on ne vous demande pas de détecter les modifications de la structure de données.
   Modifier le code que vous avez écrit précédemment pour que la méthode stream renvoie un Stream qui sache se paralléliser.
   Vérifier que les tests unitaires marqués "Q9" passent.