:: Enseignements :: Master :: M1 :: 2011-2012 :: Java Avancé ::
![[LOGO]](http://igm.univ-mlv.fr/ens/resources/mlv.png) | TP note de Java Avance |
Quelques conseils avant de commencer, prenez le temps de lire entièrement
le sujet, si vous ne comprenez pas quelque chose essayer de faire un dessin,
si des tests JUnits ne compile pas, cela veut dire que la signature
de votre méthode n'est pas la bonne (il n'y a pas de méthode surchargés dans
le sujet à part celles de l'API bien sur), si un test JUnit ne marche pas
et que vous ne comprenez pas pourquoi, relisez la doc de la méthode
que vous devez implanter plutôt que d'écrire la méthode pour quelle passe
le test.
Exercice 1 - BiMap
Le but de cet exercice est d'implanter une BiMap (pour bijective map),
qui assure que chaque clé est unique dans l'ensemble
des clés et que chaque valeur est unique dans l'ensemble des valeurs
(ce n'est donc pas une Map).
Dit autrement, pour un couple clé/valeur, il ne peut pas exister un autre couple
ayant la même clé ni un autre couple ayant la même valeur.
L'interface de
fr.umlv.tpnote.BiMap est la suivante
.
L'interface devra être modifiée pour répondre aux questions du tp noté.
-
La méthode put insère un couple clé/valeur dans la BiMap.
S'il existe un couple ayant la même clé ou un couple ayant la même valeur
ceux-ci sont retirer de la BiMap.
-
La méthode getValueFromKey prend en paramètre une clé et
renvoie la valeur correspondant ou null s'il n'existe pas
de couple ayant comme clé la clé passée en paramétre dans la BiMap.
-
La méthode getKeyFromValue prend en paramètre une valeur et
renvoie la clé correspondant ou null s'il n'existe pas
de couple ayant comme clé la clé passée en paramétre dans la BiMap.
-
Ecrire une classe fr.umlv.tpnote.SimpleBiMap qui implante l'interface BiMap
en utilisant deux tables de hachage, une stockant le couple clé/valeur et l'autre
le couple valeur/clé.
La classe devra donc implanter les méthodes put, getValueFromKey
et getKeyFromValue, avec une complexité de l'ordre de O(1).
De plus, la classe ne devra pas permettre de stocker null en tant que clé ou en tant que valeur.
Note: ce n'est pas la meilleur représentation pour une BiMap,
mais c'est celle qui vous est demandée.
-
Ajouter une méthode size à l'interface BiMap
qui renvoie le nombre de couple présent dans la BiMap.
Modifier la classe SimpleBiMap en conséquence.
-
Ajouter une méthode iterator à l'interface BiMap
qui renvoie un iterateur sur les couples présent dans la BiMap.
Modifier la classe SimpleBiMap en conséquence sachant que
la méthode remove de l'iterateur devra être implantée.
-
Modifier la classe SimpleBiMap pour que l'iterateur renvoie
les couples présents dans l'ordre d'insertion dans la BiMap.
-
Faite en sorte que l'on puisse utiliser la syntaxe for-each
sur une BiMap.
-
Ajouter une méthode putAll à l'interface et à l'implantation,
qui prend en paramètre une BiMap et ajoute tous les couples
de cette BiMap dans la BiMap courante.
L'ordre d'insertion dans la BiMap courante devra être l'ordre
de création des élements dans la BiMap passés en paramétre.
-
Ajouter une méthode asInverseBiMap à l'interface BiMap
qui renvoie une vue de la BiMap courante sous forme d'une nouvelle
BiMap pour laquelle l'ensemble des valeurs est l'ensemble des clés
de la BiMap courante et l'ensemble des clés est l'ensemble des valeurs
de la BiMap courante.
Modifier la classse SimpleBiMap en conséquence en sachant que comme le
résultat de asInverseBiMap est une vue toutes modifications de la
BiMap courante entraine une modification de la BiMap inverse
et vice-versa.
-
Ajouter à l'interface BiMap une méthode getEntryByKey qui
prend en paramètre une clé et renvoie le couple clé/valeur correspondant
(sous forme d'un objet typé java.util.Map.Entry) ou null
s'il n'existe pas un couple ayant pour clé la clé passée en paramètre.
L'entry renvoyée devra être une vue du couple clé/valeur,
donc toutes modifications de la valeur (par setValue)
devra entrainer la modification du couple clé/valeur correspondant dans la BiMap.
Modifier la classe SimpleBiMap en conséquence.
-
Ajouter à l'interface BiMap une méthode getEntryByValue qui
prend en paramètre une valeur et renvoie le couple valeur/clé correspondant
(sous forme d'un objet typé java.util.Map.Entry) ou null
s'il n'existe pas un couple ayant pour valeur la valeur passée en paramètre.
Modifier la classe SimpleBiMap en conséquence.
Le test JUnit est ici
BiMapTest.java.
Attention, cette classe utilise son propre package
fr.umlv.tpnote.test
et non pas celui de
BiMap.
© Université de Marne-la-Vallée