Collection sans ordre

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.unorderedvec</groupId>
    <artifactId>unorderedvec</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.14.4</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.16.0</version>
                <configuration>
                    <release>27</release>
                </configuration>
            </plugin>

            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-surefire-plugin</artifactId>
                <version>3.6.0</version>
            </plugin>
        </plugins>
    </build>
</project>
   

Exercice 2 - UnorderedVec

              var vec = new UnorderedVec<String>();
              vec.add("foo");
              vec.add("bar");
              vec.add("baz");

              vec.remove("foo");

              for(String value : vec) {
                System.out.println(value);
              }
            

1. Dans un premier temps, on cherche à écrire la classe UnorderedVec, son constructeur, ainsi que les méthodes add et size.
   Pour le stockage des éléments, on va utiliser un tableau de 16 cases. Nous verrons plus tard comment agrandir dynamiquement le tableau.
   Écrire la classe UnorderedVec.
   Vérifier que les tests unitaires marqués Q1 passent.


2. On veut maintenant pouvoir parcourir les éléments du tableau.
   

                   var vec = ...
                   for(var value : vec) {
                     ...
                   }
               

   
   A quoi sert l'interface Iterable ?
   Quelle méthode doit-on implanter ? Quelle est le type de retour de cette méthode.
   Sachant que l'on va utiliser une classe anonyme pour implanter la valeur renvoyée, modifier le code de la classe en conséquence.
   Vérifier que les tests unitaires marqués Q2 passent.


3. On souhaite maintenant pouvoir agrandir dynamiquement le tableau s'il y a plus de 16 éléments. L'agrandissement doit se faire en multipliant la taille du tableau par 2 (les tailles successives sont donc des puissances de 2).
   La taille théorique des tableaux en Java doit être un entier positif (donc codé sur 31 bits), pourtant la taille maximale théorique n'est pas 2^31, expliquez pourquoi ?
   Dans la pratique, en Java, un tableau en mémoire ne possède pas que les cases du tableau, il a aussi une zone, le header, juste avant les cases, qui contient les propriétés du tableau : le type des éléments, la taille du tableau, etc. En pratique, le JDK utilise la valeur Integer.MAX_VALUE - 8 comme taille maximale de tableau.
   En termes de code, l'idée est donc d'agrandir le tableau jusqu'à Integer.MAX_VALUE - 8 et sinon de lever l'exception OutOfMemoryError.
   On se propose d'écrire le code suivant:

                if (array.length == Integer.MAX_VALUE - 8) {
                  ...  // too big
                }
                int newLength = ...
                if (newLength > Integer.MAX_VALUE) {
                   newLength = Integer.MAX_VALUE - 8;
                }
                ...
               

   
   Expliquer pourquoi ce code ne marche pas dans notre cas ?
   Comment doit-on détecter que la taille du tableau est trop grande ?
   Modifier le code de la méthode add.
   Vérifier que les tests marqués Q3 passent.
   Note : le test vecVeryBiiiiiig demande 16 Go de RAM, il faut donc lancer les tests avec -Xmx16G (au niveau des paramètres de la Machine Virtuelle (VM arguments). Si ce test passe, comme il est très lent (36 sec. sur ma machine), vous n'êtes pas obligé de garder le flag -Xmx pour la suite du TP.


4. On souhaite maintenant implanter la méthode remove(element) qui supprime la première occurrence de l'élément et le remplace par le dernier élément du tableau (si l'élément est présent).
   Par exemple, si on ajoute 1, 2 et 3 puis que l'on supprime 1, le UnorderedVec devra maintenant contenir les éléments 3 et 2 car 1 a été remplacé par 3 (le dernier élément).
   La valeur de retour de remove(value) est un booléen qui est vrai si un élément est effectivement supprimé.
   Écrire la méthode remove(value).
   Vérifier que les tests unitaires marqués Q4 passent.


5. On souhaite pouvoir afficher un UnorderedVec. L'affichage se fait dans le même ordre qu'un parcours.
   On vous demande de faire une implantation en utilisant la classe StringJoiner.
   Modifier le code la classe UnorderedVec en conséquence.
   Vérifier que les tests unitaires marqués Q5 passent.


6. On souhaite pouvoir savoir si deux UnorderedVec sont égaux. Pour cela, ils doivent avoir les mêmes éléments pas forcément dans le même ordre, dans leurs tableaux sous-jacents.
   On se propose d'ajouter une méthode d'aide countOccurrences() (helper method) qui compte le nombre d'occurrences de chaque élément.
   Modifier la classe UnorderedVec pour pouvoir tester si deux UnorderedVec sont égaux.
   Vérifier que les tests unitaires marqués Q6 passent.


7. Si votre implantation est correcte, les tests marqués Q7 devraient aussi passer, si ce n'est pas le cas, identifier ce que vous avez oublié de faire et modifier votre implantation en conséquence.


8. Quelle est la différence conceptuelle entre l'interface List et l'interface Collection ?
   Quelle interface notre classe doit-elle implémenter ?
   Existe-t-il une classe abstraite d'aide pour implanter cette interface ?
   Modifier votre implantation en conséquence.
   Vérifier que les tests marqués "Q8" passent.
   Note : il existe déjà les classes java.util.AbstractList ou java.util.AbstractCollection.


9. Pour les plus balèzes, notre implantation est presque complète, il reste à implanter la méthode remove de l'itérateur.
   Bien sûr, comme la méthode remove(value) de UnorderedVec, la méthode remove de l'itérateur doit aussi remplacer l'élément supprimé par le dernier élément du tableau (pour ne pas avoir une complexité pire cas en O(n^2)).
   Écrire la méthode remove de l'itérateur.
   Vérifier que les tests marqués "Q9" passent.