:: Enseignements :: ESIPE :: E4INFO :: 2014-2015 :: Java Avancé ::

The universe is the limit

Implantation spécifique des Map/Set dans le cas où on connait l'ensemble des valeurs pouvant être contenues dans un Set ou pouvant être utilisées en tant que clé d'une Map.

Exercice 1 - Universe et UniverseSet

On cherche à créer une implantation spécifique de Set dans le cas où on connait l'ensemble de toutes les valeurs possibles que peut contenir le Set. On appelle univers un ensemble d'éléments. Chaque élément à l'intérieur de l'univers est numéroté, à partir de 0. A partir d'un univers, on va pouvoir créer des Set dont les éléments devront appartenir à l'univers sur lequel le Set a été créé. Comme les éléments dans l'univers sont numérotés, il est possible d'implanter ces Set de façon compacte en mémoire.

Expliquer pourquoi il est alors possible d'utiliser un bitset pour stocker les éléments du Set créé sur un univers. Comment est le nom de la classe Java qui représente un bitset.
On cherche, dans un premier temps, à créer la classe Universe permettant de stocker les éléments de l'univers.
Comment faire pour que deux objets égaux au sens de equals puissent être présents dans un même univers ?
Expliquer pourquoi, malgré cela, l'univers est un Set.
Implanter la classe Universe en tant que Set ainsi que sa méthode add.
Créer deux méthodes static factory nommées universe qui permettent de créer un Universe soit à partir d'une collection soit à partir d'une série d'éléments séparés par des virgules.
Pourquoi la static factory qui prend une série d'éléments affiche un warning ?
A quoi sert l'annotation SafeVarargs ? Peut-on l'utiliser ici ?
Quelle est la complexité de la méthode contains ? Changer son implantation pour améliorer la complexité.
Ecrire une méthode newSet qui crée un Set vide (appelons le UniverseSet) dont les éléments doivent être des éléments de l'Universe sur lequel il a été créé.
Que doit faire la méthode add de UniverseSet dans le cas où l'élément n'appartient pas à l'univers ?
Attention à bien lire la doc de BitSetlorsque vous implanterez size(). De plus, à quoi servent les méthodes BitSet.nextClearBit et BitSet.nextSetBit?
Pourquoi doit-on implanter isEmpty, remove, contains et clear ?
Implanter-les.
Comment peut-on spécialiser addAll, removeAll, containAll et retainAll dans le cas où le paramètre est aussi un UniverseSet.
Implanter-les.
Modifier addAll, removeAll, containAll et retainAll pour les spécialiser au cas où la collection en paramètre est l'univers.
Ecrire deux autres implantations de newSet prenant en paramètres une collection et des arguments séparés par des virgules.
Comment peut-on utiliser l'annotation @SafeVarargs ici ?

Le test Junit correspondant est UniverseTest.java.

Exercice 2 - UniverseMap

On cherche maintenant à créer une implantation de Map dont les clés sont des objets de l'univers.
L'implantation demandée devra être paresseuse (lazy), c'est-à-dire ne créer les objets que si nécessaire. Par exemple, une Map vide ne devra pas allouer de structure de données pour stocker ces éléments.
De plus, alors que null est interdit comme valeur de clé, null doit être permis en temps que valeur dans la Map. Cela veut dire que l'implantation devra faire la différence entre un null dû au fait que la structure de données n'est pas initialisée et un null dû au fait que l'utilisateur a mis null en tant que valeur dans la map.

Comment peut-on représenter de façon compacte en mémoire une Map sachant que ses clés sont des objets de l'univers ?
Créer la classe UniverseMap qui va représenter ces Map sachant que l'on peut créer une Map attachée à un univers en appelant une des trois méthodes surchargées newMap sur un Universe.
La première méthode newMap ne prend pas de paramètre et renvoie une Map vide. La second méthode newMap prend une Map en paramètre et recopie les clés/valeurs dans la nouvelle Map. Enfin, la dernière méthode newMap prend un tableau de valeurs de taille inférieure ou égale au nombre d'éléments dans l'univers et crée une Map dont les valeurs sont les objets passés en paramètre et les clés les objets de l'univers dans le même ordre.
Pourquoi doit-on fournir une implantation spécifique pour les méthodes size, get, put, containsKey ?
Implanter ces méthodes.
Implanter putAll en spécialisant le cas où le paramètre est aussi une UniverseMap.