Recherche dans une ArrayList

Bonjour à tous,

J'ai un petit soucis avec une ArrayList<Coordinate>. Je définis la classe Coordinate de la façon suivante :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public class Coordinate{   public int x; public int y;   public Coordinate(int i, int j){ x = i; y = j; }   public Coordinate(Coordinate c){ x = c.x; y = c.y; }   }

---

J'ai donc une ArrayList<Coordinate> qu'on appelera "alc". Je souhaite pouvoir savoir rapidement si pour deux entier i et j donnés, il existe dans "alc" un élément "c" tel que, c.x = i et c.y = j.

Je préférerais éviter de parcourir l'ensemble de l'ArrayList pour faire cela (je dois en fait afficher un grand tableau dans une JTable et pour chaque case correspondant à une des coordonnées de l'ArrayList, il y a un traitement spécial). J'ai donc pensé à utiliser la fonction "contains" de la classe ArrayList. Mais comme les références des objets ne sont pas les mêmes mon test me renvoie toujours false :

Code:

---

1 2 3 4 5 6 7

Coordinate c1 = new Coordinate(1, 1); Coordinate c2 = new Coordinate(1, 1);   ArrayList<Coordinate> al = new ArrayList<Coordinate>(); al.add(c1);   System.out.println(al.contains(c2)); // Affiche "false"

---

Auriez-vous une solution à mon problème ? Suis-je obligé de parcourir toutes la liste ?

Merci d'avance.

Citation:

---

Envoyé par SAKDOSS

Je préférerais éviter de parcourir l'ensemble de l'ArrayList pour faire cela

---

Euh ? Ça va s'arrêter au premier objet correspondant trouvé, bien sûr, ça va pas continuer après... Mais si c'est une ArrayList, il va bien falloir parcourir toute la liste jusqu'à trouver ce qu'on cherche.
Si tu veux faire une recherche plus rapide, tourne-toi vers les Set ou SortedSet... Qui ne tolèrent pas de doublon et ne te laissent pas définir l'ordre des éléments comme le ferait une List.

Citation:

---

Envoyé par SAKDOSS

Auriez-vous une solution à mon problème ? Suis-je obligé de parcourir toutes la liste ?

---

Pour pouvoir utiliser le contains() des collections, il faut que ta classe Coordinate redéfinisse les méthodes equals() et hashCode().

Bonjour,

Question ouverte, est-ce que pour utiliser contains() il peut suffire de faire en sorte que ta classe implémente l'interface Comparable, en définissant toi-même le critère pour que deux éléments soient considérés comme égaux ?

Par exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

public class Coordinate implements Comparable<Coordinate> {   // Le code de la classe   @Override public int compareTo(Coordinate c) { // Doit retourner : // - une valeur > 0 si this > c // - une valeur < 0 si this < c // - 0 si this == c } }

---

Mako.

Non je ne le crois pas, la méthode contains est définit ainsi:

Code:

---

1 2	Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).

---

On en revient donc à la méthode equals qui elle dépend (si elle n'est pas surchargée) du hashCode.

Par defaut Comparable n'entre pas en jeu, sauf si on redéfinit une des méthodes au-dessus.

tu peux implementer l'interface comparable ou directement le mettre dans le contsructeur de ton Set (c'est assez propre je trouve comme solution).

Code:

---

1 2 3 4 5 6

Set<Coordinate> set = new TreeSet<Coordinate>(new Comparator<Coordinate>() { public int compareTo(Coordinate c1, Coordinate c2) { // compare method } });

---

Je crois ca s'écrit comme ca (après j'ai pas vérifié sur l'éditeur)....

Merci pour vos réponses.

@thelvin : Je me suis mal exprimé. La recherche s'arrêtera, effectivement, une fois le Coordinate trouvé dans l'ArrayList. Cependant la plupart des cellules de ma JTable auront des Coordinate ne figurant pas dans l'ArrayList (et donc la plupart du temps toute l'ArrayList sera parcourue). Les set semblent en effet me permettre de gagner du temps.

@ticroch : Merci pour le code. D'après Eclipse c'est la fonction "compare" qu'il faut implémenter plutôt que "compareTo" :

Code:

---

1 2 3 4 5

Set<Coordinate> set = new TreeSet<Coordinate>(new Comparator<Coordinate>(){ public int compare(Coordinate c1, Coordinate c2){ ... } });

---

Ouep ba comme je disais j'ai pas d'éditeur, j'ai fait ca de tête. Ces normal que tu gagne du temps, ce sont des ensembles ordonnés avec les TreeSet, donc il parcoure rerement tous le Set pour retrouver l'objet dont tu as besoin.

Par contre si je me rappelle bien il y a une grosse erreur a faire attention avec ce TreeSet, c'est si tu modifie l'intérieur de tes objets (ici tes coordonnées). Quand tu fais cela, il faut absolument retirer l'objet du Set,le modifierm, et le remettre après, sinon c'est possible que ton Set se retrouve mal ordonné et qu'il te donne ensuite de mauvais résultat en insérant des doublons, voir même en indiquant qu'un élément ne se trouve pas dans ton set alors qu'il s'y trouve. Je vais essayer d'écrire un exemple pour prouver ca, et je le POST.

Alors prenons une classe banale avec un entier en attribut :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public class Test { private int test;   public test(int test) { this.test = test; }   public int getTest() { return this.test(); }   public void setTest(int test) { this.test = test; }   }

---

j'exécute ensuite ce code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// je crée mon set d'objet Set<Test> set = new TreeSet<Test>(new Comparator<Test>(){ public int compare(Test t1, Test t2){ return t1.getTest() - t2.gettest(); } });   // j'insère les objets 1 et 2 Test t1 = new Test(1); Test t2 = new Test(2); set.add(t2); set.add(t1);   // ici le Set est bien dans l'ordre {1,2}, même si {2} a été inséré avant {1}   // je modifie le cotnenu de t1 t1.setInt(3);   // ici le Set sera dans l'ordre {3,2} en raison de la modication, donc dans un ordre faux   System.out.println(set.contains(t2)); // retourne false, alors que t2 est contenu

---

Ici pour tester si t2 est contenu, il va prendre le premier élément, qui sera donc {3}. Il va effectuer la méthode compare, il va trouver que 3 > 2, donc l'élément {2}, s'il existait, devrait se trouver avant le {3}, donc il n'existe pas. Ce qui est faux.

Pour ceci absolument utiliser ceci`quand tu veux modifier le contenu de ton objet:

Code:

---

1 2 3 4 5 6 7

// le set est {1,2} set.remove(t1); // le set est {2} t1.settest(3); set.add(t1) // le set est {2,3}   System.out.println(set.contains(t2)); // retourne true

---

Voilà j'espére c'était compréhensible comme explication :) Encore une fois je fais ca de tête donc possible qu'il y ait une légère faute dans mon code .....

Ok je vois. Merci pour la précision.