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.13.4</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

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

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

Exercice 2 - UnorderedVec

              private static int start(int size) {
                return size == 0 ? 0 : (int) ((size * 0x5DEECE66DL + 11) & 0x7FFFFFFF) % size;
              }
            

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

              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.
   Note : pensez à l'ordre dans lequel vous allez initialiser les choses dans le constructeur !


2. On veut maintenant pouvoir parcourir les éléments du tableau à partir de l'index donné par la fonction start en utilisant la boucle for avec la syntaxe ":" (deux points).
   

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

   
   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.
   Le plus grand tableau possible doit être un tableau de taille Integer.MAX_VALUE - 16 (la machine virtuelle Java n'est pas capable de créer des tableaux de taille Integer.MAX_VALUE). Il vous faut donc gérer ce cas particulier.
   Vérifier que les tests unitaires marqués Q3 passent.
   Attention : penser à la gestion de l'overflow sur les entiers, Integer.MAX_VALUE / 2 * 2 est un nombre négatif !
   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 pouvez le commenter, il n'est pas vital pour la suite.


4. On souhaite maintenant implanter la méthode remove(value) qui supprime la première occurrence (en partant de l'indice 0) de la valeur et la remplace par le dernier élément ajouté (si la valeur est présente).
   Par exemple, si on ajoute foo, bar et baz puis que l'on supprime foo, le UnorderedVec devra maintenant contenir les éléments baz et bar car foo a été remplacé par baz (le dernier élément ajouté).
   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. Par exemple, avec les valeurs foo, bar et baz, l'affichage doit être <bar, baz, foo> car 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.
   Comme notre collection n'a pas de notion d'ordre, l'idée est de l'on doit avoir les mêmes éléments autant de fois dans chaque collection (par ex: 2 foo, 3 bar, 1 baz).
   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 la différence conceptuelle entre l'interface List et l'interface Collection ?
   Qu'elle interface notre classe doit-elle implémenter ?
   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.
   Note : prenez du papier et faite un dessin avant d'écrire quoi que ce soit, cette question est difficile si on ne réfléchit pas en amont.