Examen de Java Avancée

Exercice 1 - Table cachée

1. On cherche à créer une classe HiddenTable permettant d'associer un entier à un élement et vice-versa. Pour ce faire, à chaque fois que l'on ajoutera un élement à une HiddenTable, l'élement sera ajouté dans une liste à la dernière position et cette position sera de plus enregistrée dans une table de hachage.
   La liste permet pour un index donné de trouver l'élement correspondant. La table de hachage permet pour un élement de trouver l'index correspondant.
   On vous propose l'implantation suivante:

          public class HiddenTable... {
            private final ... list = new ...();
            private final ... map = new ...();
     
            int size() {
              ...
            }
            ... element(int index) {
              ...
            }
            int index(... element) {
              ...
            }
            int add(... element) {
              ...
            }
          }
        

   avec
   • size renvoyant le nombre d'élements dans la table.
   • element qui pour un index renvoie l'élement correspondant ou IndexOutOfBoundsException si l'index n'est pas entre 0 et size - 1.
   • index qui pour un élement renvoie son index ou -1 si l'élement n'est pas un élement précédemment ajouté dans la table.
   • add qui renvoie l'index de l'élement si celui-ci est déjà présent dans la table et qui sinon ajoute l'élement dans la table au prochain index disponible (0 pour le premier élement, 1 pour le second, etc) et renvoie celui-ci.
   On peut noter que toutes ces méthodes ne sont pas publiques mais serviront par la suite.
   Ecrivez une version générifiée de cette classe et implantez les méthodes size, element, index et add sachant que null n'est pas une valeur d'élement valide.
2. Ecrivez une méthode allMatch qui renvoie vrai si un prédicat (une fonction qui peut être appelée sur chaque élement et qui renvoie un booléen) est vrai pour tous les élements stockés dans la table et faux sinon.
   Attention à vérifier que la signature de la méthode allMatch est bien la plus "générique" possible.
3. Ecrivez une méthode isContainedInto qui prend une HiddenTable en paramètre et indique si tous les élements de la table courante sont contenus dans la table passée en paramètre.
   Attention à vérifier que la signature de la méthode isContainedInto est bien la plus "générique" possible.
   Note: cette question suit la précédente et il y a un point supplémentaire si vous utilisez une méthode référence !
4. On cherche à écrire une méthode newCompactSet qui renvoie un nouvel ensemble d'élements vide par défaut. L'idée est d'utiliser une série de bits (la classe java.util.BitSet) pour implanter cet ensemble. Si on ajoute un élement à cet ensemble, l'idée est de demander à la table (HiddenTable) un index puis d'allumer le bit correspondant à cet index dans la série de bits de l'ensemble.
   Voici un exemple d'exécution en pseudo code

          table = créer une HiddenTable
          set1 = sur une table, créer un ensemble
          set2 = sur une table, créer un ensemble
          sur set1, ajouter l'élément "foo"   // "foo" est ajouté en position 0 de la table, set1 = 1
          sur set1, ajouter l'élément "bar"   // "bar" est ajouté en position 1 de la table, set1 = 11
          sur set2, ajouter l'élément "bar"   // "bar" est déjà en positon 1 de la table,    set2 = 01
          sur set2, ajouter l'élément "fob"   // "fob" est ajouté en position 2 de la table, set2 = 011
          sur set1, ajouter l'élément "baz"   // "baz" est ajouté en position 3 de la table, set1 = 1101
        

   
   Note d'implantation, si l'on veut parcourir une série de bits, on peut utiliser la méthode nexSetBit (prochain bit allumé) comme ceci.

         BitSet bitSet = ...
         for(int i = bits.nextSetBit(0); i != -1; i = bits.nextSetBit(i + 1)) {
           System.out.println(i);
         }
        

   
   Note d'implantation2: le nombre de bits allumés d'un BitSet s'obtient par la méthode cardinality.
   Implantez la méthode newCompactSet en utilisant une classe interne CompactSet sachant qu'il existe une classe java.util.AbstractSet, et n'oubliez pas, de plus, d'implanter la méthode add sur l'ensemble compact.
5. Implantez la méthode remove de l'itérateur.
6. Que fait votre implantation si on appelle clear sur un ensemble compact ? Changez le code pour qu'il soit plus efficace (en temps constant).
7. Que fait votre implantation si on appelle contains sur un ensemble compact ? Changer le code pour qu'il soit plus efficace (en temps constant).
8. Que fait votre implantation si on appelle remove sur un ensemble compact ? Changer le code pour qu'il soit plus efficace (en temps constant).
9. On souhaite changer l'implantation de addAll sur un ensemble compact pour la rendre plus efficace dans le cas où l'ensemble ajouté est aussi un ensemble compact. En effet, dans ce cas, il suffit de faire un 'ou' bit à bit sur les deux séries de bits (et cela tombe bien il existe une méthode or dans BitSet).
10. Indiquez à haute voix en début de TP le nom d'un animal commençant par la première lettre de votre prénom. Si vous ommettez de le faire en début de TP, votre TP ne sera pas corrigé. Et en plus cela va être trop drôle de voir la tête de vos petits camarades lorsque vous allez indiquer votre animal à haute voix, oui, on s'amuse comme on peut.