ENIT
Programmation Orient e Ojet et g nie logiciel
2 re ann e TA, MINDS, INFO et TEL
2015/2016
Les collections (suite)
Recherche et tri des objets
Sommaire
Sommaire .................................................................................................................................... 1
Introduction ................................................................................................................................ 2
1
2
La notion d galit et la recherche dobjets complexes ...................................................... 2
La notion dordre et la comparaison des objets complexes ............................................... 4
2.1
2.2
2.3
Les types comparables ................................................................................................ 4
Les comparateurs ........................................................................................................ 5
Le tri des tableaux ....................................................................................................... 6
Mohamed Ramzi HADDAD
ENIT
Programmation Orient e Ojet et g nie logiciel
2 re ann e TA, MINDS, INFO et TEL
2015/2016
Introduction
D s sa version 1.2, Java propose diff rents types de collections permettant de regrouper
plusieurs objets dans une m me structure de donn es. Chaque type de collection propose ses
propres m thodes, conventions et contraintes afin de r pondre tous les besoins. Ceci dit, les
collections (Map, List, Queue et Set) sont un moyen simple, performant et l gant pour la
manipulation des ensembles dobjets.
Dans ce contexte, les collections peuvent contenir indiff remment des objets instances de
classes standards pr d finies que de classes nouvellement d finies par un programmeur. En dautres
termes, les instances de nimporte quelle classe implant e en Java peuvent tre stock es dans une
collection. Par contre, les collections dobjets instances de classes non pr d finies n cessitent
lintervention du programmeur pour pouvoir tre utilis es correctement.
La notion d galit et la recherche dobjets complexes
Examinons les sorties du programme suivant :
public class Personne {
String nom;
String prenom;
int age;
public Personne(String nom, String prenom, int age) {
super();
this.nom = nom;
this.prenom = prenom;
this.age = age;
}
}
public static void main(String[] args) {
Publicité
List<Personne> liste = new ArrayList<Personne>();
Personne p1 = new Personne("nom1", "prenom1", 25);
Personne p2 = new Personne("nom2", "prenom2", 28);
liste.add(p1);
liste.add(p2);
System.out.println("voici la liste : "+liste);
Personne p3 = new Personne("nom2", "prenom2", 28);
System.out.println("Recherche de "+p3+" : "+liste.contains(p3));
liste.remove(p3);
System.out.println("voici la liste : "+liste);
}
R sultat :
voici la liste : [ , ]
Recherche de : false
voici la liste : [ , ]
Remarquons ici que malgr que lobjet p2 et p3 sont identiques (de point de vue valeur
des attributs), ils ne le sont pas par rapport la m thode de recherche et par cons quence par la
m thode de suppression.
Mohamed Ramzi HADDAD
ENIT
Programmation Orient e Ojet et g nie logiciel
2 re ann e TA, MINDS, INFO et TEL
2015/2016
Ceci est d au fait que le test d galit repose sur la comparaison des adresses de objets et
non pas de leurs valeurs. En effet les m thodes cit es font usage de la m thode equals de la classe
Object celle-ci retourne vrai quand les objets compar s repr sentent la m me instance et donc la
m me adresse en m moire. Le code suivant prouve ces faits :
System.out.println(p2.equals(p3));
System.out.println(p2.equals(p2));
R sultat:
false
true
Donc, pour palier ce probl me, il est n cessaire de red finir la m thode equals dans les
classes d riv es de la classe Object chaque fois quun test d galit est pr vu. Cette m thode a la
signature suivante :
public boolean equals(Object obj);
La m thode equals prend comme param tre un objet et le compare celui dont elle fait
partie. Pour la classe personne, la red finition de la m thode equals est la suivante. Nous supposons
ici que deux personnes ayant les m mes valeurs nom, pr nom et ge sont gales.
public boolean equals(Object obj) {
Personne p = (Personne)obj;
return((this.nom.equals(p.nom))&&(this.prenom.equals(p.prenom))&&(thi
s.age==p.age));
}
Examinons maintenant la sortie du programme pr c dent :
voici la liste : [ , ]
Recherche de : true
voici la liste : [ ]
p2.equals(p3) : true
Publicité
p2.equals(p2) : true
La red finition de la m thode equals d pend de la s mantique des objets et des besoins du
programmeur. Il est donc possible de consid rer que deux objets sont gaux sils ne partagent quun
sous ensemble des valeurs de leurs attributs. Dans certains cas, il nest pas n cessaire deffectuer
cette red finition si chaque objet devrait tre consid r comme unique.
Dans ce cas, il est toujours possible de tester si deux variables font r f rence au m me objet
en utilisant lop rateur de comparaison ==. En effet la comparaison de deux personnes identiques
avec cet op rateur donne :
p2 == p3 : false
Mohamed Ramzi HADDAD
ENIT
Programmation Orient e Ojet et g nie logiciel
2 re ann e TA, MINDS, INFO et TEL
2015/2016
La notion dordre et la comparaison des objets complexes
2.1 Les types comparables
Examinons le code suivant utilisant la classe personne pr c demment sus indiqu e :
public static void main(String[] args) {
List<Personne> liste = new ArrayList<Personne>();
Personne p1 = new Personne("nom1", "prenom1", 29);
Personne p3 = new Personne("nom2", "prenom2", 25);
Personne p2 = new Personne("nom2", "prenom2", 28);
liste.add(p1);
liste.add(p2);
liste.add(p3);
System.out.println("liste initiale : "+liste);
Collections.sort(liste);
System.out.println("liste tri e : "+liste);
}
Bound mismatch: The generic method sort(List<T>) of type Collections is not applicable for the
arguments (List<Personne>). The inferred type Personne is not a valid substitute for the bounded parameter <T
extends Comparable<? super T>>
Le code pr sente une erreur lors de sa compilation indiquant que les l ments de la liste ne
sont pas comparables. Ceci est attendu puisque nous navons fournis la m thode sort ni le moyen
de comparer les personnes, ni la d finition de la notion dordre entre elles. En effet, la m thode sort,
qui prend quun seul param tre et qui trie la collection dans un ordre croissant, a la signature
suivante :
public static <T extends Comparable<? super T>> void sort(List<T> list)
Ceci implique que les l ments de la liste doivent impl menter linterface comparable. Celle-
ci ne contient quune seule m thode abstraite nomm e compareTo qui permet de comparer lobjet
sur lequel elle est invoqu e et celui quelle prend en param tre. De cette mani re les objets dune
classe qui impl mente cette interface deviennent mutuellement comparables. Voici le code
rajouter la classe Personne pour corriger le code pr c dent.
public class Personne implements Comparable<Personne>
Limpl mentation de linterface comparable requi re la d finition de la m thode compareTo.
Celle-ci compare deux objets et est invoqu e comme suit :
int x = objetCourant.compareTo(unAutreObjet);
compareTo retourne :
" une valeur n gative si objetCourant est inf rieur au sens de la comparaison lautre objet,
Publicité
"
" une valeur positive si objetCourant est sup rieur lobjet unAutreObjet.
z ro si les deux objets sont gaux, et
Mohamed Ramzi HADDAD
ENIT
Programmation Orient e Ojet et g nie logiciel
2 re ann e TA, MINDS, INFO et TEL
2015/2016
Voici donc un exemple dimpl mentation de la m thode compareTo pour la classe personne
et dans lequel nous supposons quune personne pr c de une autre si elles est moins ag e :
public int compareTo(Personne o) { return this.age - o.age; }
Dans ce cas, sachant que la m thode sort trie les l ments dans lordre croissant au sens de
la comparaison (c'est- -dire que si la comparaison dun l ment avec son suivant donne une valeur
positive, ils seront permut s), le tri de la liste ordonnera les personnes selon lordre croissant de
leurs ges. Voici le r sultat de lexemple pr c dent :
liste initiale: [ , , ]
liste tri e: [ , , ]
Attention limpl mentation de la m thode compareTo lors de la sp cification de la valeur
de retour. En effet, limpl mentation suivante donne que les personnes seront tri es dans le sens
d croissant.
public int compareTo(Personne o) { return o.age - this.age; }
2.2 Les comparateurs
Dans la r alit , il est possible davoir besoin dordonner les personnes de diff rente mani re
(par rapport au nom, au pr nom, l ge, au salaire, etc&), mais il ny a quune seule m thode
compareTo . Dans ces cas, il est n cessaire davoir recours la deuxi me version surcharg e de la
m thode sort et qui prend comme param tres la collection trier ainsi quun comparateur. Voici la
signature de la m thode sort :
public static <T> void sort(List<T> list, Comparator<? super T> c)
Linterface Comparator donne au programmeur le moyen de comparer et dintroduire une
notion dordre entre les objets dune classe. Parmi les avantages de cette classe, citons :
"
"
"
il est d sormais possible de d finir plusieurs comparateurs pour la m me classe.
il devient possible de d finir un ordre non pas seulement entre les objets des classes
nouvellement d finies mais aussi pour celles qui sont d j pr d finies dans Java
(String, Integer, etc&).
Il nest plus n cessaire de modifier le code des classes trier ou comparer pour
introduire la m thode compareTo et impl menter linterface Comparable.
Le recours linterface Comparator est simple ; il suffit de limpl menter et de d finir la
m thode compare. Voici un exemple de comparateur de personne, utilisant l ge comme crit re de
comparaison.
public class TriPersonneSelonAge implements Comparator<Personne> {
public int compare(Personne p1, Personne p2) {
return p1.age - p2.age;
}
}
Mohamed Ramzi HADDAD
ENIT
Publicité
Programmation Orient e Ojet et g nie logiciel
2 re ann e TA, MINDS, INFO et TEL
2015/2016
Enfin la ligne suivante permet de trier la liste des personnes selon l ordre croissant des ges:
TriPersonneSelonAge triAge = new TriPersonneSelonAge();
Collections.sort(liste,triAge);
La classe String impl mente linterface Comparable, donc elle propose la m thode
compareTo pour comparer deux chaines de caract res. Nous pouvons utiliser cette m thode pour
d finir un comparateur de personnes se basant sur lordre lexicographique de leurs noms :
import java.util.Comparator;
public class TriPersonneSelonNom implements Comparator<Personne> {
public int compare(Personne p1, Personne p2) {
return p1.nom.compareTo(p2.nom);
}
}
Les comparateurs sont aussi utiles pour
les algorithmes de recherche. En effet
analogiquement aux algorithmes de tri, il est parfois n cessaire davoir plusieurs crit res de
recherche pour un type de donn es. Par exemple, pour la classe personne il est possible deffectuer
une recherche par nom, par pr nom ou par ge. Dans ces cas de figure les comparateurs sont utiles
dans la mesure o ils donnent le moyen de comparer deux objets en termes dordre et d galit .
La
classe
Collections
la m thode binarySearch(collection,
objetcComparateur). Celle-ci prend comme param tres la collection, lobjet recherch et un
comparateur par rapport au crit re de recherche. Un comparateur mis nul indique que lordre
naturel (d finit dans la clase par la m thode compareTo) devrait tre utilis .
propose
Attention : La m thode binarySearch impl mente un algorithme de recherche binaire. Ceci
dit, il est imp ratif de trier la collection avant de linvoquer. Dans le cas contraire, le r sultat retourn
est ind termin .
La m thode binarySearch retourne :
" Un entier positif si l l ment existe.
" Si l l ment nexiste pas, la m thode retourne (- PositionDInsertion -1), o
PositionDInsertion indique la position o l l ment serait positionn sil est ins r
dans la collection.
2.3 Le tri des tableaux
Nous avons utilis la classe Collections pour trier les collections. Quen est-il pour les
tableaux de type Array ?
En fait, le tri des tableaux de type Array est similaire celui des collections. En effet, la classe
Arrays propose aussi la m thode sort. De mani re analogue la casse Collections, la classe Arrays
propose les m mes m thodes de tri statiques et surcharg es :
" Arrays.sort(tableau)
" Arrays.sort(tableau, Comparator)
Mohamed Ramzi HADDAD