Table des matières

TD8 - Collections

Le but de cette séance est de manipuler différentes collections d’objets de façon à connaitre les fonctionnalités disponibles et à savoir choisir quelle collection est la plus adaptée à un problème donné.

On manipulera des collections de Point2D. Vous pouvez utiliser une version simplifiée de la classe écrite lors des premiers TD. La classe doit contenir au moins le constructeur basé sur les coordonnées, les accesseurs aux coordonnées, la méthode de translation, la méthode toString et la méthode equals ( Point2D.java ).

Pour vous repérer dans la hiérarchie des collections Java, vous pouvez consulter http://www.falkhausen.de/Java-8/java.util/Collection-Hierarchy.html

ArrayList

Est-il possible d’ajouter plusieurs points identiques à une liste de type ArrayList? Vérifiez votre réponse en testant.

Ecrivez la méthode suivante qui permet de créer une liste de type ArrayList contenant n points de coordonnées tirées aléatoirement dans l’intervalle [0,range].

public static ArrayList<Point2D> createRandom(int n, int range)

Dans le programme principal, créez une liste de 10000 points de coordonnées comprises entre 0 et 100 et écrivez trois versions différentes du code pour translater chacun des points d’un vecteur (-50, 50) : boucle for avec accès indicé à chacun des points, parcours de la liste avec itérateur, enhanced for loop. Quelle version est-elle préférable?

Evaluez le temps nécessaire pour modifier 100000 fois le point situé au milieu de la liste. Vous pourrez utiliser la fonction

System.currentTimeMillis()

Ecrivez la méthode suivante qui permet de supprimer d’une liste de Point2D tous les points situés dans le disque de centre c et de rayon r. Cette méthode retourne le nombre de points supprimés.

public static int removeInsideDisk(List<Point2D> l, Point2D c, int r)

Evaluez son temps d’exécution pour une liste de 1,000,000 points de coordonnées comprises entre -50 et 50 et pour le disque de centre (0, 0) et de rayon 50.

Ecrivez deux versions d’une méthode qui crée une liste correspondant à l’entrelacement de deux listes : une version avec accès indicés, une version utilisant des itérateurs. Evaluez le temps d’exécution de chacune des deux versions.

Créez une liste de Point2D et écrivez le code nécessaire pour la trier en utilisant la méthode sort de la classe Collections:

static <T> void	sort(List<T> list, Comparator<? super T> c)

La méthode compare de l’interface Comparator prend deux paramètres. Elle renvoie un entier soit négatif, soit nul, soit positif suivant que le premier paramètre est inférieur, égal ou supérieur au second paramètre. Pour plus de détail sur ce que doit vérifier cette méthode, consultez la documentation. Un point sera dit inférieur à un autre si son abscisse est inférieure. En cas d’égalité des abscisses, on comparera les ordonnées.

Remarque Pour utiliser la méthode sort il est nécessaire de créer une nouvelle classe MyComparator qui implémente l’interface Comparator puis de créer une instance de cette classe. L’appel de la méthode sort ressemblerait à ceci :

public class MyComparator implements Comparator<Point2D> {
	public int compare(Point2D p1, Point2D p2) {
		// TODO
		return 0;
	}	
}

   sort(l, new MyComparator<Point2D>());

Pour simplificier ce cas assez fréquent, il est possible d’utiliser des classes anonymes. La syntaxe est la suivante :

   sort(l, new Comparator<Point2D>() {
	 public int compare(Point2D o1, Point2D o2) {
		// TODO
		return 0;
	}  
   });

Le principe est qu’on instancie un objet d’une classe anonyme (le compilateur générera automatiquement un nom) qui implémente l’interface Comparator<Point2D>. Il est possible d’utiliser la même syntaxe pour une classe anonyme fille d’une classe donnée.

LinkedList

Reprenez les questions précédentes en utilisant le type LinkedList à la place d’ArrayList. Comparez les temps d’exécution dans l’un et l’autre cas. Concluez en précisant quelles sont les opérations coûteuses dans chacun des deux cas.

TreeSet

Créez une nouvelle collection de type TreeSet<Point2D> (constructeur sans paramètre). Testez l’ajout d’un point. Que doit vérifier la classe Point2D pour que cette opération soit possible? Pourquoi?

Ajoutez à l’ensemble 10000 points à coordonnées entières choisies aléatoirement dans l’intervalle [0, 100]. Quelle est la taille de l’ensemble après les ajouts? Rappelez la spécificité du type Set qui explique le résultat.

Sélection d’une sous-partie d’une collection

On veut sélectionner une sous-partie des points d’une collection (et créer une nouvelle collection contenant ces points) à partir de plusieurs critères différents : points situés dans un disque, points situés dans un rectangle, points de coordonnées positives, points d’abscisse supérieure à une valeur donnée… Comment organiser le code de façon à ce que l’ajout d’un nouveau critère de sélection ne nécessite que l’écriture du critère lui-même?

On propose la méthode générique suivante :

	public static <T> void selection(Collection<T> collIn, Collection<T> collOut, Predicate<T> f){
		for (T e : collIn){
			if (f.test(e))
				collOut.add(e);
		}
	}

Utilisez-la avec des collections de points de votre choix en implémentant au moins deux des critères de sélection listés ci-dessus.