Examen de Java Avancé - Session 1

Exercice 1 - CactusList

  var cactus = new CactusList<String>();
  cactus.add("foo");
  
  var cactus2 = new CactusList<String>();
  cactus2.add("bar");
  cactus2.add("baz");
  
  cactus.addCactus(cactus2);
  cactus.add("booz");
  
  System.out.println(s.size());  // prints 4
  
  for(var s : cactus) {
    System.out.println(s);  // prints foo then bar then baz then booz
  }
     

1. Écrire une classe CactusList avec
   • un constructeur public sans paramètre
   • les méthodes add et addCactus
   • une méthode size renvoyant le nombre d'éléments (en O(1))
   Et vérifier que les tests marqués "Q1" passent.


2. En fait, votre code ne marche (très probablement) pas, en effet, si on ajoute des éléments à une liste-cactus après l'avoir ajoutée dans une autre liste, la taille de cette autre liste n'est pas mise à jour. Nous choisissons de corriger ce problème en interdisant que l'on puisse ajouter des éléments à une liste-cactus cactusList si celle-ci a déjà été ajoutée à une liste-cactus. Pour cela, on marque la liste cactusList comme frozen. en d'autre termes, si une liste-cactus est frozen alors elle n'admet plus de nouveaux éléments.
   On veut, de plus, empêcher les cycles : par exemple, cactus1 qui contient cactus2 qui contient cactus1. On peut remarquer qu'avec le mécanisme frozen, il suffit juste de tester qu'une liste-cactus ne se contient pas elle-même.
   Implanter le mécanisme de frozen, ajouter une méthode publique frozen qui renvoie vrai si une liste-cactus est frozen et faire en sorte qu'il ne soit pas possible de créer de cycles.
   Vérifier que les tests marqués "Q2" passent.


3. Ajouter une méthode forEach qui permet de parcourir tous les éléments de la liste-cactus.
   Par exemple:

     var cactus = new CactusList<String>();
     cactus.add("foo");
     
     var cactus2 = new CactusList<String>();
     cactus2.add("bar");
     cactus2.add("baz");
     
     cactus.addCactus(cactus2);
     cactus.add("booz");
     
     cactus.forEach(System.out::println); // prints foo then bar then baz then booz
         

   Et vérifier que les tests marqués "Q3" passent.
   Note: attention à ne pas laisser de warning dans votre code et à ne supprimer des warnings qu'il ne faudrait pas supprimer.


4. Ajouter une méthode permettant l'affichage de l'ensemble des éléments de la liste-cactus séparés par des virgules et encadrés par '<' et '>'.
   Par exemple:

     var cactus = new CactusList<String>();
     cactus.add("foo");
     
     var cactus2 = new CactusList<String>();
     cactus2.add("bar");
     cactus2.add("baz");
     
     cactus.addCactus(cactus2);
     cactus.add("booz");
     
     System.out.println(cactus); // prints <foo, bar, baz, booz>
         

   
   Et vérifier que les tests marqués "Q4" passent.


5. On souhaite maintenant pouvoir initialiser une liste-cactus non mutable directement à partir une liste (java.util.List) d'éléments. La liste ne devra pas contenir de listes-cactus.
   Écrire une méthode from qui prend en paramètre une liste (typée comme une java.util.List) et renvoie une cactus liste non mutable.
   Vérifier que les tests marqués "Q5" passent.
   Note : pour éviter les copies inutiles, si la liste prise en argument est non mutable alors faire en sorte que l'implantation essaie de ne pas faire de copie des éléments.


6. On souhaite ajouter une méthode get(index) qui permet d'obtenir un élément de la liste-cactus courante en fonction d'un index.
   Pour éviter que l'implantation de la méthode get(index) ne soit en O(n), il faut aplatir la liste en insérant tous les éléments des liste-cactus contenues dans la liste-cactus sur laquelle on fait appel à get(index) (et seulement à ce moment là !). On appelle cette opération normaliser la liste.
   Normaliser une liste revient à supprimer les liste-cactus internes et à stocker les éléments de ces listes dans la liste-cactus courante en conservant l'ordre d'insertion.
   Écrire la méthode get(index) ainsi que la méthode normalized qui indique si la liste-cactus est normalisée ou non. Et vérifier que les tests marqués "Q6" passent.
   Attention : par défaut, une liste-cactus est normalisée. Elle ne l'est plus dès lors qu'on ajoute une liste-cactus dedans. Et elle le redevient si on appelle get(index) dessus.


7. On souhaite maintenant que les liste-cactus se comportent comme de vraies listes (une java.util.List) donc la méthode iterator doit fonctionner et il doit être possible de faire un parcours d'une cactus liste en utilisant la boucle for( : ) comme dans l'exemple en tout début de cet exercice.
   Vérifier que les tests marqués "Q7" passent.
   Note : n'oubliez pas java.util.RandomAccess !
   Note 2 : si vous êtes allés en cours, vous savez comment éviter (proprement) de ré-implémenter toutes les méthodes d'une liste...


8. Les questions 8 et 9 sont indépendantes et peuvent être traitées dans n'importe quel ordre.
   On veut qu'il soit possible de créer un Stream sur une liste-cactus sans forcer à ce que la liste-cactus soit normalisée.
   Écrire la méthode stream qui renvoie un Stream (séquentiel) et vérifier que les tests marqués "Q8" passent.
   Note : parcourir un arbre (une liste-cactus est une sorte d'arbre après tout) de façon itérative requiert de gérer votre propre pile.


9. Les questions 8 et 9 sont indépendantes et peuvent traitées dans n'importe quel ordre.
   On veut qu'il soit possible de créer un Iterator sur une liste-cactus sans forcer à ce que la liste-cactus soit normalisée.
   Écrire la méthode iterator qui renvoie un Iterator (non mutable) et vérifier que les tests marqués "Q9" passent.
   Note : parcourir un arbre (une liste-cactus est une sorte d'arbre après tout) de façon itérative requiert de gérer votre propre pile.