:: Enseignements :: ESIPE :: E4INFO :: 2009-2010 :: Java Avancé ::

Capture, implanter une nouvelle collection

Exercice 1 - Capture de carte sauvage

On souhaite implanter un algorithme permettant de répartir une liste dans un ordre aléatoire.

Indiquer un algorithme possible pour cela. Quel est la complexité de celui-ci ?
Implanter une méthode swap suivant la documentation suivante :
Que doit-on changer pour que la méthode swap ait la signature suivante :
Ecrire une méthode shuffle utilisant la méthode swap pour permuter les valeurs.
La classe java.util.Random est un générateur pseudo-aléatoire.
En supposant que l'on veuille répartir les élements de façon aléatoire entre deux listes, expliquer pourquoi la capture ne marche pas avec une méthode ayant la signature suivante :
Quelle est la complexité du code que vous avez écrit pour shuffle ? Dans le cas où la liste est une LinkedList ? Comment améliorer cette dernière complexité ?

Exercice 2 - Pris la main dedans

Il est classique dans plusieurs algorithmes d'utiliser une structure de données appelée Bag . Celle-ci permet de stocker des objets un certain nombre de fois, la structure garde en mémoire le nombre de fois qu'un même objet (au sens de equals ) est stocké.

Écrire l'interface fr.umlv.util.bag.Bag possédant les méthodes add , remove et count qui respectivement ajoute un objet, retire un objet et renvoie le nombre d'occurences d'un objet.
Commenter l'interface écrite.
Fournir une implantation BagImpl de cette interface permettant d'ajouter et de retirer des élements en temps constant moyen.
Ajouter une méthode Iterator<Map.Entry<T,Integer>> iterator() qui renvoie un itérateur sur les couples (objet, nombre d'occurences).
Faire en sorte que l'on puisse choisir l'ordre des objets lors de l'itération par une constante lors de la construction du Bag :

Quelles sont les contraintes sur T en fonction de la collection utilisée ?
Remplacer les constantes passées lors de la construction par une énumération ( enum ).
Discuter de l'utilité d'une enumération abstraite ici. Implanter la solution proposée.
On souhaite que le code suivant marche :

Que doit-on faire ?
Pourquoi le code suivant ne marche pas ?

Comment changer le code pour qu'il marche ?
De quelle interface des collections en Java peut hériter l'interface Bag ?
Quelles sont les problèmes que cela pose par rapport au code existant ?
Le code suivant :
Doit afficher :
```
Remi
Remi
Guillaume 
				
```