:: Enseignements :: Master :: M1 :: 2009-2010 :: Java Avancé ::

Implanter une nouvelle collection

Exercice 1 - Capture de carte sauvage

On souhaite implanter un algorithme permettant de mélanger les éléments d'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 :

/** Swaps the elements at the specified positions in the specified list.
 * (If the specified positions are equal, invoking this method leaves the list
 *  unchanged.)
 * @param list the list in which to swap elements.
 * @param i the index of one element to be swapped.
 * @param j the index of the other element to be swapped.
 * @throws IndexOutOfBoundsException if either i or j is out of range.
 */

Que doit-on faire pour que la méthode swap ait la signature suivante :
```
void swap(List<?> list,int i,int j);
```
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 :
```
void shuffle(List<?> list1,List<?> list2);
```
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 
				
```