:: Enseignements :: Master :: M1 :: 2024-2025 :: Java Avancé ::

Structure de données spécialisée pour les types primitifs

Le but de ce TP noté est d'implanter une structure de données appelée NumericVec qui est une séquence de valeurs numériques d'entiers, d'entiers long ou de nombres flottants.
L'intérêt de cette structure de données est d'avoir une représentation très compacte en mémoire des données sans pour autant dupliquer le code pour chaque type primitif.

Exercice 1 - Maven

Pour ce TP, nous allons utiliser la même configuration Maven qu'habituellement.

  <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.numeric</groupId>
    <artifactId>numeric</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>
          </configuration>
        </plugin>

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

Comme précédemment, créer un projet Maven, au niveau du premier écran, cocher create simple project puis passer à l'écran suivant en indiquant Next.
Pour ce TP, le groupId est fr.uge.numeric , l'artefactId est numeric et la version est 0.0.1-SNAPSHOT. Puis cliquer sur Finish.

Exercice 2 - NumericVec

La classe fr.uge.numeric.NumericVec est un conteneur de valeurs numériques homogènes de type int, long ou double mais qui en interne stocke les valeurs dans un tableau de long.
En effet, un entier long 64 bits (long) peut contenir un int 32 bits ; il suffit de faire cast en int si on veut obtenir la valeur comme un int. Un entier long 64 bits (long) peut aussi contenir un nombre flottant 64 bits (double) car c'est la même taille en mémoire, il faut être capable pour cela de voir un double comme un long sans changer la représentation bit à bit. La méthode Double.doubleToRawLongBits(double valeur) renvoie le long correspondant bit à bit au double passé en paramètre et la méthode Double.longBitsToDouble(long value) fait l'opération inverse.
La classe NumericVec permet de créer des séquences d'int, de long ou de double de la façon suivante.

  NumericVec<Integer> seq1 = NumericVec.ints(1, 4, 7);  // séquence d'entiers 32 bits
  NumericVec<Long> seq2 = NumericVec.longs(123L, -45L);  // séquence d'entiers 64 bits
  NumericVec<Double> seq3 = NumericVec.doubles(48.0, 123.25);  // séquence de flottants 64 bits

La classe NumericVec possède, de plus,

les méthodes get(index), size() et add(value) qui permettent respectivement d'obtenir un élément à un index donné et d'obtenir le nombre d'éléments et d'ajouter un élément.
la méthode stream() qui permet d'obtenir un stream à partir d'un NumericVec.
l'ensemble des méthodes qui permettent de voir un NumericVec comme une liste.
les méthodes freeze et isFrozen qui respectivement renvoie un NumericVec non modifiable et indique si un NumericVec est non modifiable ou non.
les méthodes toNumericVec et toUnmodifiableNumericVec qui sont des Collectors créant respectivement un NumericVec modifiable et un NumericVec non-modifiable à partir d'un stream.

Des tests unitaires correspondant à l'implantation sont ici : NumericVecTest.java.

Dans la classe fr.uge.numeric.NumericVec, on souhaite écrire une méthode longs qui prend en paramètre des entiers longs séparés par des virgules qui permet de créer un NumericVec vide contenant les valeurs prises en paramètre. Cela doit être la seule façon de pouvoir créer un NumericVec.
Écrire la méthode longs puis ajouter les méthodes, get(index) et size.
Vérifier que les tests unitaires marqués "Q1" passent.

On souhaite ajouter une méthode add(element) qui permet d'ajouter un élément. Le tableau utilisé par NumericVec doit s'agrandir dynamiquement pour permettre d'ajouter un nombre arbitraire d'éléments.
Vérifier que les tests unitaires marqués "Q2" passent.
Note : agrandir un tableau une case par une case est très inefficace !

On veut maintenant ajouter les 2 méthodes ints, doubles qui permettent respectivement de créer des NumericVec d'int ou de double en prenant en paramètre des valeurs séparées par des virgules.
En termes d'implantation, l'idée est de convertir les int ou les double en long avant de les insérer dans le tableau. Et dans l'autre sens, lorsque l'on veut lire une valeur, c'est-à-dire quand on prend un long dans le tableau, on le convertit en le type numérique attendu. Pour cela, l'idée est de stocker dans chaque NumericVec une fonction into qui sait convertir un élément en long, et une fonction from qui sait convertir un long vers un élément.
Vérifier que les tests unitaires marqués "Q3" passent.

On souhaite écrire une méthode stream() qui renvoie un stream des éléments du NumericVec dans l'ordre d'insertion. Pour cela, on va créer une classe implantant l'interface Spliterator. Puis on utilisera, StreamSupport.stream() pour créer le stream à partir du spliterator.
Note : s'il y a moins d'éléments que 1024, on n'essayera pas de splitter le spliterator.
Écrire la méthode stream qui renvoie un stream parallélisable.
Vérifier que les tests unitaires marqués "Q4" passent.
Note : on peut remarquer qu'il n'est pas possible de changer la valeur d'un élément une fois que celui-ci a été ajouté au NumericVec (il n'y a pas de méthode set()).

On souhaite qu'un NumericVec implante l'interface java.util.List.
Modifier le code pour que NumericVec soit une liste.
Vérifier que les tests unitaires marqués "Q5" passent.
Rappel : il existe la classe AbstractList !

On souhaite ajouter une méthode addAll qui permet d'ajouter une collection à un NumericVec déjà existant. Techniquement, l'implantation de addAll que l'on reçoit de AbstractList marche déjà, mais ici, on va faire une implantation plus efficace dans le cas où le paramètre est aussi un NumericVec.
Écrire le code de la méthode addAll qui optimize le cas où le paramètre est aussi un NumericVec.
Vérifier que les tests unitaires marqués "Q6" passent.
Note : que se passe-t-il si on fait un addAll() avec deux NumericVec qui n'ont pas le même type ?

On souhaite écrire une méthode toNumericVec(factory) qui prend en paramètre une référence de méthode permettant de créer un NumericVec et renvoie un Collector qui peut être utilisé pour collecter des valeurs numériques dans un/des NumericVec créés par la référence de méthode.
Doit on utiliser la méthode Collector.of() avec 3 paramètre ou celle avec 4 paramètre ?
Écrire la méthode toNumericVec.
Vérifier que les tests unitaires marqués "Q7" passent.

[Revision] On souhaite pouvoir créer des NumericVec non modifiable à partir d'un NumericVec pré-existant. Pour cela, nous allons écrire une méthode freeze qui renvoie une version non modifiable d'un NumericVec.
Comme on veut que les NumericVec reste une structure de donnée compacte, on va implanter cette feature sans ajouter de nouveau champ, mais plutôt en faisant en sorte que la fonction qui transforme un élément en valeur dans le tableau lève une exception.
Quelle doit être l'exception levée ? Si vous ne vous souvenez plus, aller regarder la javadoc de java.util.Collection.add().
Implanter la méthode freeze ainsi qu'une méthode isFrozen qui indique si un NumericVec est non-modifiable ou pas.
Vérifier que les tests unitaires marqués "Q8" passent.
Note : est-il nécessaire de faire une copie défensive du tableau ?

[Revision] Enfin, on souhaite écrire une méthode toUnmodifiableNumericVec(factory) qui fonctionne comme toNumericVec(factory) mais renvoie un NumericVec non modifiable.
Écrire la méthode toUnmodifiableNumericVec(factory).
Vérifier que les tests unitaires marqués "Q9" passent.