Embeded List

Exercice 1 - Maven

Exercice 2 - EmbedList

      class Node {
        private Node next;
        private final int value;

        Node(int value) {
          this.value = value;
        }

        @Override
        public String toString() {
          return "Node" + value;
        }

        public Node getNext() {
         return next;
        }

        public void setNext(Node next) {
          this.next = next;
        }
      }
     

      EmbedList<Node> list = new EmbedList<Node>(Node::getNext, Node::setNext);
      list.addFirst(new Node(1));
      list.addFirst(new Node(2));
      list.addFirst(new Node(3));
      System.out.println(list.size());  // 3
      System.out.println(list);  // [Node3, Node2, Node1]
     

1. On souhaite écrire la classe EmbedList définie par un pointeur sur la tête de la liste (head) ainsi que les deux fonctions getNext et setNext. Bien sûr, notre implantation ne va pas utiliser une structure de données déjà existante dans java.util car le but est de fournir une nouvelle implantation de liste chaînée.
   La classe EmbedList possède un constructeur qui prend en paramètre une fonction getNext qui, pour un maillon, renvoie le maillon suivant et une fonction setNext qui prend deux maillons en paramètres et affecte le champ suivant du premier maillon avec le second maillon.
   De plus, la classe EmbedList définit deux autres méthodes, size qui renvoie la taille de la liste (en temps constant) ainsi que addFirst(link) qui permet d'ajouter un maillon (link en Anglais) devant les maillons de la liste déjà existants.
   Écrire la classe EmbedList.
   Vérifier que les tests unitaires marqués "Q1" passent.
   Note : dans le cas où cela ne serait pas assez clair, le constructeur de EmbedList prend en paramètre deux interfaces fonctionnelles, à vous de trouver lesquelles.


2. On souhaite écrire la méthode forEach(lambda) qui prend en paramètre une fonction et appelle cette fonction avec chaque maillon de la liste.
   Écrire la méthode forEach(lambda) si possible avec une implantation utilisant un Stream.
   Vérifier que les tests unitaires marqués "Q2" passent.


3. On souhaite pouvoir parcourir la liste chaînée avec une boucle comme ceci :

          EmbedList<Node> list = new EmbedList<Node>(Node::getNext, Node::setNext);
          ...
          for(Node node: list) {
            System.out.println(node);
          }
         

   
   Modifier l'implantation de la classe EmbedList en conséquence.
   Vérifier que les tests unitaires marqués "Q3" passent.


4. On souhaite écrire la méthode get(index) qui renvoie l'élément à l'indice index dans la liste chaînée (le premier élément est à l'index 0).
   Écrire la méthode get(index)
   Vérifier que les tests unitaires marqués "Q4" passent.


5. On veut maintenant que la classe EmbedList soit une java.util.List, comme cela on pourra utiliser notre implantation à la place de n'importe quelle implantation de liste.
   Modifier votre implantation de la classe EmbedList pour que celle-ci soit une java.util.List.
   Vérifier que les tests unitaires marqués "Q5" passent.
   Note : il existe une classe AbstractList.
   Note 2 : il faut aussi résoudre les problèmes de performance de indexOf et lastIndexOf


6. On souhaite ajouter une méthode unmodifiable() qui renvoie une vue non modifiable de la liste chaînée, c'est-à-dire une nouvelle liste chaînée qui partage les mêmes maillons que la liste originale (donc pas de copie des maillons), mais qui ne permet pas de modifier le chaînage.
   De plus, on veut que si l'on demande une vue non modifiable d'une liste déjà non modifiable, la méthode unmodifiable() renvoie la liste non modifiable déjà existante.
   Écrire la méthode unmodifiable() qui renvoie une vue modifiable.
   Vérifier que les tests unitaires marqués "Q6" passent.
   Note : essayez de faire simple !
   Note 2 : créer une autre implantation de liste n'est pas une solution simple !


7. On souhaite pouvoir ajouter un maillon à la fin de la liste (en temps constant) en utilisant la méthode add.
   Modifier votre implantation pour que la méthode add ajoute un maillon à la fin de la liste chaînée.
   Vérifier que les tests unitaires marqués "Q7" passent.
   Note : add sur une liste non-modifiable ne doit pas marcher.
   Note2 : si on a une vue non-modifiable d'une liste modifiable, le maillon ajouté avec un add sur la vue modifiable ne doit pas être visible sur la vue non-modifiable.


8. On cherche à écrire une méthode valueStream(lambda) qui renvoie un Stream des valeurs renvoyées par la fonction prise en paramètre pour chaque maillon.
   Écrire la méthode valueStream(lambda).
   Vérifier que les tests unitaires marqués "Q8" passent.
   Note : couper une liste chaînée en deux revient à parcourir la liste, donc on préfère que la version parallèle du Stream ne distribue pas les valeurs sur plusieurs cœurs.


9. Enfin, on souhaite définir une interface Entry, à l'intérieur de la classe EmbedList, avec une méthode getNext et une méthode setNext, ainsi qu'une méthode of(type) dans EmbedList qui prend une classe qui implante l'interface Entry et renvoie une EmbedList configurée pour utiliser les méthodes getNext et setNext de l'interface.
   Voici un exemple d'utilisation

          class Data implements EmbedList.Entry<Data> {
            private Data next;
            private final int value;
   
            Data(int value) {
              this.value = value;
            }
   
            @Override
            public Data getNext() {
              return next;
            }
            @Override
            public void setNext(Data next) {
              this.next = next;
            }
          }
          ...
          var list = EmbedList.of(Data.class);
          list.add(new Data(29));
          list.add(new Data(81));
         

   
   Déclarer l'interface Entry dans la classe EmbedList et écrire la méthode of(type).
   Vérifier que les tests unitaires marqués "Q9" passent.