Examen de Java Avancé 2025 - 2026

Exercice 1 - DeferredVec

1. Dans un premier temps, on veut pouvoir créer des instances de DeferredVec, pouvoir ajouter des éléments avec add, obtenir un élément avec get(index) et connaître le nombre d'éléments avec size.
   L'implantation doit stocker des éléments dans un tableau de taille 8. Pour l'instant, on ne s'occupe pas de redimensionner le tableau automatiquement.
   Écrire la classe DeferredVec, son constructeur, ses méthodes add, get et size.
   Vérifier que les tests marqués "Q1" passent.


2. On veut maintenant que le tableau se redimensionne automatiquement si on veut stocker plus d'éléments que la capacité actuelle du tableau. Le redimensionnement se fait en multipliant la capacité du tableau par 2.
   Ici, on ne s'occupera pas de la gestion de l'overflow.
   Modifier le code de la classe DeferredVec en conséquence.
   Vérifier que les tests marqués "Q2" passent.


3. On souhaite ajouter les méthodes remove(index) et undo(). La méthode remove(index) marque élément à l'index index à supprimer et renvoie l'élément. La méthode undo() supprime toutes les marques de suppressions.
   En termes d'implantation, vous utiliserez une instance de la classe java.util.BitSet pour marquer les éléments à supprimer. La classe BitSet possède les méthodes get(index), set(index), clear(from, to) et clear().
   Attention, il ne doit pas être possible d'accéder à un élément en utilisant get(index) si celui-ci est marqué pour la suppression. Même chose pour remove(index), il ne doit pas être possible de marquer pour la suppression un élément déjà marqué pour la suppression.
   Modifier le code de la classe DeferredVec et ajouter les méthodes remove et undo
   Vérifier que les tests marqués "Q3" passent.


4. On souhaite maintenant écrire la méthode compact qui supprime tous les éléments marqués et décale les éléments non-marqués sur la gauche (de sorte qu'il n'y ait pas de trous).
   En termes d'algorithme, l'idée est d'avoir deux curseurs, un qui parcourt tous les éléments et un qui correspond à l'endroit où il faut insérer le prochain élément non-marqué. Donc, on peut parcourir tous les éléments et n'ajouter que les éléments qui ne sont pas marqués. Et il faut faire attention à ne pas créer de memory leak.
   Implanter la méthode compact.
   Vérifier que les tests marqués "Q4" passent.


5. On veut écrire une méthode eachState(function) qui parcours chaque élément et indique l'élément et son statut : removed ou pas (un booléen).
   Voici un exemple d'utilisation :

     var vec = new DeferredVec<String>();
     vec.add("first");
     vec.add("second");
     vec.add("third");
     vec.add("fourth");
     vec.remove(1);
     vec.remove(3);
   
     vec.eachState((element, removed) -> {
       IO.println(element + " " + removed);
     });
     // first false
     // second true
     // third false
     // fourth true
          

   
   En termes d'implantation, on vous demande d'utiliser un Stream, si vous n'y arrivez pas, faites autrement.
   Implanter la méthode eachState(function).
   Vérifier que les tests marqués "Q5" passent.


6. On souhaite pouvoir parcourir un DeferredVec en utilisant une boucle. Dans ce cas, seuls les éléments non-marqués seront parcourus.
   Par exemple :

     var vec = new DeferredVec<String>();
     vec.add("first");
     vec.add("second");
     vec.add("third");
     vec.add("fourth");
     vec.remove(1);
     vec.remove(2);
   
     for (String element : vec) {
       IO.println(element);
     }
     // first
     // fourth
          

   
   De plus, on souhaite que si l'on supprime les éléments en utilisant l'itérateur, les éléments soient uniquement marqués pour la suppression.
   Modifier la classe DeferredVec en conséquence.
   Vérifier que les tests marqués "Q6" passent.


7. On veut ajouter une surcharge à la méthode compact, compact(from, to) qui compacte uniquement les éléments entre les index from inclus et to exclu.
   Implanter la méthode compact(from, to).
   Vérifier que les tests marqués "Q7" passent.


8. On souhaite ajouter la méthode stream qui permet de parcourir tous les éléments non-marqués.
   Écrire la méthode stream sachant que seule la version séquentielle nous intéresse pour l'instant.
   Vérifier que les tests marqués "Q8" passent.
   Note : votre implantation de Stream devrait être plus efficace si aucun éléments n'est marqués pour la suppression.


9. Modifier l'implantation de la méthode stream() pour que l'implantation parallèle marche aussi.
   Vérifier que les tests marqués "Q9" passent.