:: Enseignements :: ESIPE :: E4INFO :: 2011-2012 :: Java Avancé ::

The universe is the limit

Implantation specifique des Map/Set dans le cas où on connait l'ensemble des valeurs pouvant être contenu dans un Set ou pouvant être utilisé 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 kes valeurs possible que peut contenir le Set. On appel univers un ensemble d'élements. Chaque élement à 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éer. Comme les élements dans l'univers sont numéroté, 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 élements du Set créer 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 élements de l'univers.
Expliquer pourquoi on ne peut pas utiliser equals pour tester si un élement est déjà présent dans l'univers.
Expliquer pourquoi, malgrès cela, l'univers est un Set.
Implanter la classe Universe en tant que Set ansi 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 serie d'élements séparés par des virgules.
Pourquoi la static factory qui prend une serie d'élement 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éer un Set (appelons le UniverseSet) dont les élements doivent être des élements de l'Universe sur lequel il a été créé.
Que doit faire la méthode add de UniverseSet dans le cas ou l'élement 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ètre 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é 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ée pour stocker ces élements.
De plus, alors que null est interdit comme valeur de clé, null doit être permit en temps que valeur dans la Map. Cela veut dire que l'implantation devra faire la différence entre un null du au fait que la structure de donnée n'est pas initialisé et un null du au fait que l'utilisateur à mis null en tant que valeur dans la map.

Comment peut-on représenté 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é à 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érieur ou égal au nombre d'élements dand l'univers et crée une Map dont les valeurs sont les objets passés en paramètre et les clés les objet 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.