Columnar

Le but de cet exercice est d'implanter une base de données en mémoire orientée colonne (colmunar in memory database).
Contrairement à une base de données relationnelle classique, une base de données orientée colonne, comme Cassandra ou HBase, stocke les données non pas ligne par ligne mais colonne par colonne.
Par exemple, la base de données suivante est stockée comme deux listes de même taille, une liste pet: [dog, cat] et une liste count : [1, 2].

      pet   | count
     ---------------
      dog   | 1
     ---------------
      cat   | 2
    

Et les valeurs d'une même ligne sont stockées au même index de chaque liste.

On se propose de créer une classe Colmunar permettant de représenter ce genre de base de données en mémoire.
Voici un exemple d'utilisation, décrivant la base de données ci-dessus :

     var name = Columnar.column("pet", String.class);
     var count = Columnar.column("count", Integer.class);
     var columnar = Columnar.of(name, count);
     columnar.addValues("dog", 1);
     columnar.addValues("cat", 2);
    

La méthode column permet de créer une colonne avec un nom et le type des éléments que doit contenir la colonne. La méthode of permet de créer l'objet Colmunar en indiquant les colonnes qui le composent. La méthode addValues permet d'ajouter des valeurs en spécifiant une ligne de la base, les valeurs sont alors réparties dans les colonnes correspondantes.

Un Columnar contiendra des colonnes de type Column une colonne ne peut appartenir qu'à un seul Columnar. Les données sont stockées dans les Column et toutes les Column d'un Columnar ont la même taille.

Les tests JUnit sont ici ColumnarTest.java.

1. On souhaite écrire une méthode column dans la classe Columnar qui prend en paramètre un nom et un type et qui renvoie une instance de la classe interne Column qui représente une colonne.
   Une colonne est paramétrée par le type des éléments que l'on peut mettre dans la colonne et pour l'instant on considère que le type ne peut pas être un type primitif (donc on utilisera par exemple Integer.class à la place de int.class).
   L'affichage d'une colonne est son nom, qui n'est pas nécessairement unique car il sert pour le debug, suivi de "of" suivi du nom du type. Par exemple, avec la colonne créée par column("name", String.class), on obtient l'affichage suivant.

    
        name of java.lang.String
      

   Note : en Java, la classe java.lang.Class permet de représenter le type d'un ensemble de valeurs, la méthode Class.cast(Object) permet de vérifier qu'un objet est de la bonne classe et la méthode Class.getName() permet de renvoyer le nom de la classe.
   Écrire la classe Columnar, ainsi que sa classe interne Column et vérifier que les tests marqués "Q1" passent.


2. On souhaite écrire une méthode of qui prend en paramètre des colonnes séparées par des virgules et renvoie une instance de Columnar configurée avec ces colonnes.
   La méthode d'affichage d'un Columnar permet d'afficher les noms des colonnes séparés par des pipes (et des espaces). Par exemple, avec les deux colonnes pet et count de l'exemple ci-dessus, l'affichage est : pet | count.
   Un Columnar doit avoir au moins une colonne, sinon on ne pourra pas stocker de valeurs dans le Columnar.
   Une colonne ne peut appartenir qu'à une seule instance de Columnar, sinon, si on a deux Columnar qui possèdent la même colonne, l'ajout de valeurs dans l'un va ajouter au moins une valeur dans l'autre (puisque les données sont stockées dans les colonnes). En termes d'implantation, cela vaut dire que l'on doit au moins savoir (marquer) si la colonne appartient déjà à un Columnar ou pas.
   De même, un Columnar ne peut pas avoir deux fois la même colonne.
   Écrire la méthode of et vérifier que les tests marqués "Q2" passent.


3. On souhaite écrire une méthode addValues qui prend en paramètre des valeurs séparées par des virgules et les ajoute dans les bonnes colonnes (en vérifiant que le type est correct) et une méthode size qui renvoie le nombre de lignes du Columnar.
   Ajouter les méthodes addValues et size et vérifier que les test marqués "Q3" passent.
   Note : il n'est pas nécessaire d'avoir un champ size dans Columnar !


4. On souhaite maintenant écrire une méthode get qui prend en paramètre une colonne et un numéro de ligne et renvoie la valeur associée.
   Bien sûr, demander la valeur d'une colonne qui ne fait pas partie du Columnar ne doit pas marcher. Comme on veut que ce test s'exécute en temps constant, vous aurez donc besoin de faire en sorte qu'une colonne sache dans quel Columnar elle est utilisée.
   Écrire la méthode get. Elle doit avoir une complexité en O(1) par rapport au nombre de lignes et au nombre de colonnes du Columnar. Vérifier que les tests marqués "Q4" passent.
   Note : comme les colonnes sont paramétrées, la méthode get peut renvoyer le bon type !


5. On veut ajouter une méthode qui surcharge addValues et qui prend en paramètre une liste des valeurs.
   Écrire la méthode addValues et vérifier que le test addValuesLinkedList passe.
   Si le test ne passe pas, expliquer pourquoi et corriger votre code. Si vous ne voyez pas, regarder les slides sur l'interface List et LinkedList dans le cours !
   
   Vérifier que les autres tests marqués "Q5" passent.


6. On cherche à écrire une méthode getValues() qui prend en paramètre un numéro de ligne et renvoie une List contenant les valeurs correspondantes.
   On souhaite que la liste renvoyée ne stocke pas les valeurs, c'est à dire qu'elle agisse comment une vue : les valeurs restent dans les colonnes et ne sont pas copiées dans le liste.
   Écrire la méthode getValues() et vérifier que les tests marqués "Q6" passent.
   Note 1 : penser qu'il existe la classe java.util.AbstractList ! Note 2 : vous vous êtes donnés du mal pour que get soit en O(1), penser à le signaler !


7. On souhaite écrire une méthode filter qui prend en paramètre une colonne et une fonction qui prend en paramètre une valeur et renvoie un booléen. La méthode filter renvoie un Columnar non mutable (addValues ne marche pas) qui ne contient que les lignes pour lesquelles la fonction renvoie vrai pour la valeur de la colonne.
   L'implantation ne doit PAS recopier les valeurs mais uniquement montrer les valeurs filtrées. Pour cela, on va ajouter à Columnar un tableau d'indirection qui indique les lignes qui sont visibles après l'appel à filter (c'est à dire un tableau des numéros des lignes auxquelles on peut accéder).
   Un Columnar créé à partir de colonnes a son tableau d'indirection null et lorsque l'on appelle filter, on renvoie un Columnar avec les mêmes colonnes plus un tableau d'indirection correspondant.
   Par exemple, si la fonction passée à filter rejette les lignes 0 et 2 d'un Columnar à 5 lignes, le tableau d'indirection est [1,3,4] et le Columnar renvoyé par filter ne permettra d’accéder qu'à ces 3 lignes, en utilisant des indices entre 0 et 2.
   Écrire la méthode filter() et vérifier que les tests marqués "Q7" passent.


8. On souhaite maintenant pourvoir parcourir les lignes de valeurs en utilisant une boucle for each in.
   Par exemple,

         var columnar = ...
         for(var values: columnar) {
           // values est une liste des valeurs d'une ligne
           ...
         }
        

   
   On souhaite que lors d'un parcours, on puisse ajouter de nouvelle valeurs avec addValues mais dans ce cas, les valeurs ne seront pas visibles pour la boucle en train de s'exécuter. C'est un peu comme si on faisait une photo des valeurs avant et que l'on ne parcourrait que les valeurs de la photo, même si de nouvelles valeurs sont ajoutées (on appelle communément cette sémantique snapshot at the beginning ou SATB).
   Modifier votre code en conséquence et vérifier que les tests marqués "Q8" passent.


9. (Optionnel) Enfin, pour les plus courageux, on a laissé de côté le fait qu'une colonne puisse contenir des types primitifs car cela veut dire que les colonnes doivent gérer des tableaux qui peuvent être soit des tableaux de types primitifs soit des tableaux de références.
   Java nous aide en peu, en fournissant la classe java.lang.Array (attention à ne pas confondre avec java.util.Arrays) qui permet de :
   • créer des tableaux à partir d'un objet de type Class (prismitif ou référence) avec la méthode Array.newInstance,
   • demander la taille du tableau avec Array.getLength,
   • changer la valeur d'une case du tableau avec Array.set
   • obtenir la valeur d'une case avec Array.get.
   De plus, la méthode System.arraycopy permet de copier les valeurs d'un tableau dans un autre, si les deux tableaux ont le même type. Enfin, un tableau connaît le type de son contenu est utilisant array.getClass().getComponentType().
   Avec ces méthodes, commenter le code de Column et le remplacer par un code capable de gérer les tableaux de types primitifs ou de références indifféremment.
   On peut aussi noter qu'une colonne configurée avec un type primitif n'acceptera pas null comme valeur contrairement aux colonnes de référence.
   Vérifier que les tests marqués "Q9" passent.
   Dernière remarque : vous n'avez plus besoin de conserver le type des éléments d'une colonne. Si ce n'est pas déjà fait, modifier le code en conséquence.