Deduplication

Exercice 1 - Maven

 <project xmlns="http://maven.apache.org/POM/4.0.0"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">

    <modelVersion>4.0.0</modelVersion>
    <groupId>fr.uge.dedup</groupId>
    <artifactId>dedup</artifactId>
    <version>0.0.1-SNAPSHOT</version>

    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>5.11.0</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.13.0</version>
                <configuration>
                    <release>23</release>
                    <compilerArgs>
                      <compilerArg>--enable-preview</compilerArg>
                    </compilerArgs>
                </configuration>
            </plugin>

            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-surefire-plugin</artifactId>
                <version>3.5.0</version>
                <configuration>
                  <argLine>--enable-preview</argLine>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>
   

Exercice 2 - DedupVec

      record Point(int x, int y) {}
      ...
      Point point1 = new Point(2, 3);
      Point point2 = new Point(2, 3);
     

      DedupVec<Point> dedupVec = new DedupVec<Point>();
      dedupVec.add(point1);
      dedupVec.add(point2);
     

      point1.equals(dedupVec.get(0))  // true
      point1 == dedupVec.get(0)       // true
      point2.equals(dedupVec.get(1))  // true
      point2 == dedupVec.get(1)       // false
      point1 == dedupVec.get(1)       // true
     

1. On va dans un premier temps écrire une version simple de la classe DedupVec, avec un constructeur sans paramètre, les méthodes size et get(index) ainsi que la méthode add(element) qui pour l'instant n'effectue pas la déduplication.
   Quelle implantation de l'interface List allez-vous choisir pour stocker les éléments ?
   Implanter la classe DedupVec.
   Vérifier que les tests marqués "Q1" passent.


2. On souhaite maintenant que lorsque l'on ajoute un élément, l'implantation effectue la déduplication comme décrit ci-dessus.
   Quelle implantation de l'interface Map allez-vous choisir ?
   Modifier l'implantation de la classe DedupVec pour que la déduplication des instances soit faite.


3. On souhaite ajouter une méthode contains(element) qui teste si une valeur est un des éléments de DedupVec.
   Sachant que l'on veut une complexité pire cas en temps constant, comment doit-on faire ?
   Implanter la méthode contains(element).
   Vérifier que les tests marqués "Q3" passent.


4. On souhaite ajouter une méthode addAll(dedupVec) qui permet d'ajouter tous les éléments d'un DedupVec à un autre DedupVec.
   Quelle doit être la signature (le type des paramètres) d'une telle méthode ?
   Implanter la méthode addAll.
   Vérifier que les tests marqués "Q4" passent.


5. Dans le but d'implanter la méthode fromSet de façon efficace, on souhaite ajouter une méthode d'aide (helper method) pas publique, newMapFromSet(set) qui prend en paramètre un ensemble et renvoie une Map qui pour chaque élément de l'ensemble associe ce même élément. Par exemple, si l'ensemble contient uniquement la chaîne de caractères "toto", on obtient une Map map telle que si on appelle map.get("toto"), le résultat est "toto".
   Pour des questions d'efficacité (cf. question suivante) la Map renvoyée doit être une vue de l'ensemble pris en paramètre et si l'ensemble pris en paramètre contient la valeur null, l'appel à la méthode newMapFromSet(set) ne devra pas lever d'exception et c'est uniquement lorsque l'on essaye d'accéder à l'élément qu'une exception NullPointerException devra être levée.
   Sachant qu'il existe la classe AbstractMap, écrire la méthode newMapFromSet(set).
   Vérifier que les tests marqués "Q5" passent.


6. On va maintenant écrire la méthode fromSet(set) qui prend en paramètre un ensemble et créé un DedupVec avec l'ensemble des éléments de l'ensemble.
   Cette méthode doit être plus efficace que de créer un DedupVec puis de faire des add des éléments du Set car par définition, un ensemble (un Set) ne contient pas d'éléments dupliqués, donc il n'est pas nécessaire de dédupliquer les éléments à la création.
   Vérifier que les tests marqués "Q6" passent.
   Note: on va utiliser un constructeur "flexible", qui permet d'initialiser les champs AVANT l'appel à super().
   Note 2: un DedupVec n'est pas une vue, faite donc attention qu'un DedupVec créé en appelant fromSet(set) respecte bien l'encapsulation et ne se comporte pas comme une vue.


7. On souhaite changer l'implantation de addAll pour qu'elle soit un peu plus efficace (mais pas de quoi changer la complexité pire cas malheureusement).
   On peut remarquer que si l'on utilise un DedupVec plutôt qu'une liste classique, c'est parce qu'il y a de grandes chances qu'il y ait des doublons. Dans ce cas, l'ensemble des valeurs dans la Map est sûrement plus petit que les éléments dans la liste. On peut alors optimiser pour le cas où les ensembles des valeurs dans les Map des deux DedupVec sont disjoints. En effet, si c'est le cas, on peut directement faire un addAll des éléments des listes, car on est sûr qu'il n'y a pas de doublons créés par un élément qui serait dans chacun des deux DedupVec.
   On va donc utiliser l'algorithme suivant :

          addAll(dedupVec1, dedupVec2)
            on initialise un drapeau à faux
            pour chaque valeur de l'ensemble des clés de la map de dedupVec2
              on ajoute la clé à la map de dedupVec1 si la clé n'existe pas déjà
              si la clé existe déjà, on met le drapeau à vrai
                // Note : en Java, il existe une méthode putIfAbsent qui fait les 2 lignes précédentes
                // en un seul appel, il suffit de regarder la valeur de retour de putIfAbsent
   
            si le drapeau est faux
              on peut ajouter tous les éléments de la liste de dedupVec2 dans la liste de dedupVec1
            sinon
              pour chaque élément de la liste de dedupVec2
                on va rechercher l'élément dans la map de dedupVec1
                on ajoute le résultat dans la liste de dedupVec1
         

   
   Commenter votre précédente méthode addAll et écrire une nouvelle implantation.
   Note : Il n'y a pas de tests supplémentaires pour cette question, car c'est une optimisation, les tests précédents doivent continuer à fonctionner.


8. On souhaite que la classe DedupVec se comporte comme une java.util.List. Pour nous aider, nous allons utiliser la classe AbstractList qui fournit déjà une implantation de nombreuses méthodes de l'interface List.
   On a un petit problème avec addAll, car la méthode addAll que l'on a déjà écrite et celle de l'interface List n'ont pas la même signature. On va garder la signature de la méthode addAll de List mais on va tester dynamiquement si la collection prise en paramètre n'est pas un DedupVec pour utiliser l'algorithme que l'on a écrit à la question précédente pour ne pas perdre en efficacité.
   Faire les changements qui s'imposent pour que DedupVec implante l'interface List.
   Vérifier que les tests marqués "Q8" passent.


9. Enfin, on peut remarquer que sur DedupVec, il n'est pour l'instant pas possible d'ajouter un élément autre part qu'à la fin, une méthode comme addFirst ou un appel à la méthode add sur une subList() ne marchent pas. En relisant la documentation de la classe AbstractList, quelle méthode (une seule) doit-on implanter pour que ces méthodes fonctionnent ?
   Implanter la méthode nécessaire.
   Vérifier que les tests marqués "Q9" passent.