Les collections

Chapitres traités    Les tableaux pour gérer des ensembles d'éléments Les collections pour gérer des ensembles d'objets Comparaison d'objets

Nous allons ici faire l'étude du regroupement mémoire d'éléments de même type que nous appelons collections. Nous en profiterons pour revoir les tableaux classiques pour mieux cerner l'intérêt de proposer d'autres alternatives. Cette étude ne sera pas exhaustive. Je vous invite juste à connaître quelques classes qui peuvent être bien utiles pour stockers des objets de même nature en mémoire (qui peut être une mémoire de masse, ce qui peut donc nous intéresser pour le stockage d'informations sur disque dur).

Les tableaux pour gérer des ensembles d'éléments

Un tableau (array en anglais) est le type d'objet le plus simple à programmer pour gérer un ensemble d'éléments :

1. Les éléments d'un tableau sont tous du même type.
2. Ces éléments peuvent être des données de type primitif ou des références d'une classe donnée.
3. La taille d'un tableau est déterminée lors de sa création et ne peut être modifiée par la suite.
4. Le tableau est considéré comme un objet et possède un attribut public length qui donne la taille du tableau.
5. La position d'un élément dans un tableau est déterminée par un indice entier.
6. L'indice du prmier élément du tableau est toujours 0 et l'indice du dernier élément d'un tableau est le nombre d'éléments moins 1.
7. La JVM vérifie à l'exécution que les indices utilisés pour accéder à un élément figurent bien dans l'intervalle autorisé et que le type d'un objet est compatible avec le type du tableau.

Les tableaux permettent donc de regrouper une suite de variables de même type. Chaque élément du tableau est une variable que vous pouvez utiliser comme n'importe quelle variable de ce type. Il est possible de définir des tableaux pour les types primaires ou les classes. Cependant, tous les éléments doivent être du même type. En Java, les tableaux sont des objets.

Pour pouvoir utiliser un tableau, vous devez respecter les trois étapes suivantes :

1. Déclarer une variable pour référencer le tableau.
2. Créer un objet de type tableau en initialisant la référence à ce tableau.
3. Utiliser et manipuler les éléments de ce tableau.

Déclaration d'un tableau

Effectivement, comme un tableau est un objet, la création d'un tableau commence par la mise en place de sa référence afin de pointer ultérieurement vers l'objet tableau lui-même. Voici comment se déclare une telle référence t de type tableau d'entiers :

int t[];

Elle précise que t est destiné à contenir la référence à un tableau d'entiers. Vous constatez qu'aucune dimension ne figure dans cette déclaration et, pour l'instant, aucune valeur n'a été attribuée à t. Comme toute référence, une référence de type tableau peut être égale à null ou désigner un objet tableau.

Voici quelques exemples de déclarations :

int t[]; // peut s'écrire int[] t ;
int [] t1, t2; // t1 et t2 sont des références à des tableaux d'entiers
int t3[], t4[]; // écritures équivalentes
int t5[], n, t6[]; // t5 et t6 sont des tableaux d'entiers, n est entier
Point tp[]; // tp est une référence à un tableau d'objets de type Point
Point a, tp[]; // a est une référence à un objet de type Point, 
tp est une référence à un tableau d'objets de type Point
int tab[5]; // erreur : nous ne pouvons pas indiquer de dimension ici.

Création et initialisation d'un tableau

Nous pouvons effectuer la création et l'initialisation d'un tableau de trois façons différentes :

Création par l'opérateur new

Après avoir déclaré la variable tableau, il faut allouer les éléments de ce tableau. On utilise pour ce faire l'opérateur new. Vous avez déjà mis en oeuvre cet opérateur pour créer des objets. A ce niveau, il est obligatoire de préciser le nombre d'éléments du tableau. Ces derniers sont initialisés automatiquement en fonction du type de tableau (0 pour les numériques, '\0' pour les caractères, false pour les boolean et null pour les éléments de type objet).

package test;

import java.awt.*;

public class Main {
  public static void main(String[] args) {
    int[] tabEntier = new int[30]; 
    // tableau de 30 entiers de valeur nulle
    String[] semaine = new String[7];
    /* tableau de 7 références vers des objets
     *  de type String. Par la suite, il sera nécessaire
     * pour chaque élément du tableau de 
     * créer un objet de type String
    */
  }
}

Utilisation d'un initialiseur

Lors de la déclaration d'une référence, il est possible de fournir la valeur à chacune des cases du tableau. Il suffit de donner la liste entre accolades sans utiliser l'opérateur new. Java se sert du nombre de valeurs figurant dans l'initialiseur pour en déduire la taille du tableau à créer.

int[] t = {1, 3, 5, 7}; 
/* création d'un tableau de 4 entiers de
  * valeurs respectives 1, 3, 5, 7 et place
  * la référence dans t. Elle remplace les 
  * instructions suivantes :
*/
int t[];
t = new int[4];
t[0]=1;  t[1]=3;  t[2]=5; t[3]=7;

tableau anonyme

A tout moment en utilisant l'opérateur new et une liste entre accolades de valeurs. Cette notation est très pratique pour passer un tableau en paramètres à une méthode sans qu'il faille créer une variable locale pour ce tableau. En imaginant la déclaration de la méthode suivante :

afficheSemaine(String[] joursSemaine);

Voici un exemple de tableau anonyme que nous pouvons passer en argument de la méthode :

afficheSemaine(new String[] {"Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche"});

Cette écriture est à la fois un raccourci et évite d'utiliser une variable intermédiaire :

String[] jours = {"Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche"} ;
afficheSemaine(jours);

Utilisation d'un tableau

Nous pouvons manipuler un élément de tableau comme nous le ferions avec n'importe quelle variable ou n'importe quel objet de ses éléments. On désigne un élément particulier en plaçant entre crochets, à la suite du nom du tableau, une expression entière nommée indice indiquant sa position. Le premier élément correspond à l'indice 0 (et non 1).

int t[] = new int[5], a; 
t[0] = 15; // place la valeur 15 dans le premier élément du tableau
t[2]++; // incrémente de 1 le troisième élément de t
a = t[4]+23; // utilisation dans un calcul
t[1] = t[0]+5; // initialisation d'un élément à partir d'un autre
t[a-20] = -85; // calcul sur l'indice

Affectation de tableaux

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    String[] liste = {"Salut", "Bonjour"};
    String[] copie = new String[2];
    System.arraycopy(liste, 0, copie, 0, 2);
    Arrays.sort(liste);    
    boolean test = Arrays.equals(copie, liste);
  }
}

Java permet aussi de manipuler globalement des tableaux, par le biais d'affectations de leurs références.

Exécutons maintenant l'affectation :

t1 = t2; // la référence contenue dans t2 est recopiée dans t1

Nous aboutissons à la situation présentée ci-dessous. Dorénavant, t1 et t2 désigne le même tableau.

Ainsi, avec :

t1[1] = 5;
System.out.println (t2[1]);

on obtiendra l'affichage de la valeur 5, et non 11.

Si l'objet que constitue le tableau de trois entiers anciennement désigné par t1 n'est plus référencé par ailleurs, il deviendra candidat au ramasse-miettes.

Il est très important de noter que l'affectation de références de tableaux n'entraine aucune recopie des valeurs des éléments du tableau. On retrouve exactement le même phénomène que pour l'affectation d'objets.

Nombre d'éléments d'un tableau

Pour connaître le nombre d'éléments d'un tableau, vous pouvez utiliser l'attribut public length. Cet attribut peut être utilisé pour tous les types de tableaux. Considérez le code suivant :

int tab[] = new int [10];
int taille = tab.length; // taille est égal à 10

Après avoir déclaré un tableau, utilisez length pour récupérer le nombre d'éléments du tableau (ici 10).

Le mot length désigne en quelque sorte un attribut du tableau, attribut que l'on peut d'ailleurs uniquement lire ; ce n'est pas un attribut au même titre que les attributs d'une classe. Remarquons qu'il n'y a pas d'autre attribut pour une variable de type tableau.

Manipuler un tableau d'objets

Attention : Pour définir un tableau d'objets, il faut commencer par définir un tableau de références, puis, pour chaque référence, créer l'objet associé. Un tableau d'objets est en fait un tableau de références, et chaque référence pointe vers l'objet associé.

Le résultat est le suivant :

Point : 1, 2
Point : 4, 5
Point : 8, 9

Il est possible d'avoir une écriture plus concise de la classe TabPoint en utilisant l'initialiseur de tableau.

Afficher un tableau dans la sortie standard

Il existe une méthode très très simple pour afficher toutes les valeurs d'un tableau dans la sortie standard, et ce grâce à la méthode toString() de la classe Arrays. L'appel Arrays.toString(tableau) renvoie une chaîne de caractères contenant les éléments du tableau, insérés entre crochets et séparés par des virgules :

System.out.println(Arrays.toString(tableau)); // affichepar exemple à l'écran "[2, 3, 5, 7, 11, 13]"

Copie des tableaux

Il est possible de copier une variable tableau dans une autre, mais attention, comme nous l'avons vu plus haut, les deux variables feront alors référence au même tableau :

int[ ] suite = {17, 19, 23, 29, 31, 37};
int[ ] entier = suite;
entier[3] = 12; // suite[3] vaut maintenant 12

• Si vous voulez effectivement copier toutes les valeurs d'un tableau dans un autre, il faut employer la méthode copyTo() de la classe Arrays :

  int[ ] suite = {17, 19, 23, 29, 31, 37};
  int[ ] entier = Arrays.copyOf(suite, suite.length);

• Le second paramètre correspond à la longueur du nouveau tableau. Cette méthode est souvent employée pour augmenter la taille d'un tableau :

  int[ ] suite = {17, 19, 23, 29, 31, 37};
  suite = Arrays.copyOf(suite, 2 * suite.length);

  Les autres éléments sont remplis de 0 si le tableau contient des nombres, false si le tableau contient des valeurs booléennes. A l'inverse, si la longueur est inférieure à celle du tableau initial, seules les valeurs initiales sont copiées.

Tri d'un tableau

Si vous voulez trier un tableau de nombres, utilisez une des méthodes sort() de la classe Arrays :

int[ ] nombre = new int[100];
...
Arrays.sort(nombre);

Cette méthode utilise une version adaptée de l'algorithme QuickSort qui se révèle très efficace sur la plupart des ensembles de données.
§

Parcourt et affichage d'un tableau multidimentionnel

Une boucle "for each" ne traverse pas automatiquement toutes les entrées d'un tableau multidimensionnel. Elle parcourt plutôt les lignes, qui sont elles-mêmes des tableaux à une dimension. Pour visiter tous les éléments d'un tableau bidimensionnel, imbriquer deux boucles :

int[ ][ ] tableau =
  {
     {16, 3, 2, 13},
     {5, 10, 11, 8},
     {9, 6, 7, 12},
     {4, 15, 14, 1}
  };
...

for (int[ ] ligne : tableau)
   for (int élément : ligne)
     // faire quelque chose avec élément

Les collections pour gérer des ensembles d'objets

Les tableaux sont inadéquats pour gérer une quantité importante d'informations du même type quand leur nombre n'est pas connu à l'avance. Par exemple, le nombre de messages postés dans un forum n'étant pas limité, il existe des solutions plus simples que des tableaux pour stocker ces messages.

Le paquetage java.util contient plusieurs classes de collection utilisées pour gérer un ensemble d'éléments de type d'objet et résoudre les limitations inhérentes aux tableaux. Chaque classe est prévue pour gérer un ensemble avec des caractéristiques différentes :

1. Les collections gérées par les classes ArrayList et LinkedList gèrent des ensembles ordonnés d'éléments accessible par leur indice. Ces collections peuvent contenir des élements égaux. Chaque élément mémorisé ayant une position déterminée, ces classes ressemblent aux tableaux Java mais ne sont pas limitées en taille.
2. Les collections gérées par les classes HashSet et TreeSet permettent de mettre en oeuvre la théorie des ensembles et ne peuvent donc pas contenir des éléments égaux. La classe TreeSet stocke stocke les éléments de son ensemble dans l'ordre ascendant.
3. Les collections gérées par les classes HashMap et TreeMap utilisent une clé pour accéder aux élements au lieu d'un indice entier. La classe TreeMap stocke les éléments de sa collection dans l'ordre ascendant des clés.

Liste ordonnées d'objets - java.util.ArrayList et java.util.LinkedList

Ces deux classes ArrayList et LinkedList gèrent des collections ordonnées d'éléments accessibles par leur indice.

Le tableau classique en Java, comme nous l'avons découvert dans le chapitre précédent, fait parti des collections d'éléments ordonnés accessible par indice. L'utilisation des tableaux impose cependant de spécifier une taille avant de pouvoir être utilisé. En java, il est possible de préciser la taille juste au moment où nous en avons besoin. En contre partie, une fois que la taille est prise en compte, il n'est pas facile de la changer.

La classe ArrayList est semblable à un tableau, mais elle ajuste automatiquement sa capacité à mesure que vous ajoutez et supprimez des éléments, sans que vous n'ayez rien à faire.

En fait, en interne, la classe ArrayList mémorise ses éléments dans un tableau Java. Si ce tableau interne est trop petit lors de l'ajout d'un nouvel élément à la collection, il est automatiquement remplacé par un nouveau tableau, plus grand, initialisé avec les références de l'ancien tableau.

La classe ArrayList est très séduisante. Il s'agit ni plus ni moins d'un tableau dynamique. Elle est totalement adaptée lorsque nous devons ajouter ou supprimer des éléments en fin de tableau.

Elle possède toutefois, un inconvénient majeur. Effectivement, la suppression d'un élément au milieu d'un tableau nécessite beaucoup de temps machine, car tous les éléments situés après l'élément supprimé doivent être décallés d'une case. Le même problème se pose pour insérer des éléments au milieu d'un tableau.

Il existe une autre structure de données très répandue, la liste chaînée, qui permet de résoudre ces problèmes. Alors que les objets d'un tableau occupent des emplacements mémoires successifs, une liste chaînée stocke chaque objet avec un lien qui y fait référence. Chaque lien possède également une référence vers le lien suivant de la liste. Avec Java, chaque élément d'une liste chaînée possède en fait deux liens, c'est-à-dire que chaque élément est aussi relié à l'élément précédent. Il existe donc une classe qui met en oeuvre toute cette infrastructure, il s'agit de la classe LinkedList.

La classe LinkedList mémorise ses éléments avec une liste doublement chaînée, ce qui permet d'insérer plus rapidement un élément dans la collection, mais par contre, ralentit l'accès à un élément par son indice.

Ci-dessous se trouve un exemple où nous prenons comme collection un tableau dynamique ArrayList. Les méthodes utilisées sont les méthodes communes aux deux types de collection. Remplacez, d'ailleurs, la classe ArrayList par LinkedList, vous remarquerez que votre programme vous donnera le même résultat. Le choix entre les deux types de collection doit correspondre uniquement au critère de performance. Si vous devez insérer ou supprimer des éléments n'importe où dans la collection, il faut alors choisir LinkerList. Si vous n'avez pas ce genre de contrainte et que vous voulez juste remplacer un tableau statique par un tableau dynamique, n'hésitez pas à prendre le conteneur ArrayList.

import java.util.*;
import static java.lang.System.*;

public class TableauDynamique {
   public static void main(String[] args) {
      // tableau d'entier par la classe enveloppe Integer
      ArrayList<Integer> tableau = new ArrayList<Integer>();
      out.println("Tableau vide ? "+tableau.isEmpty());
      tableau.add(-45);
      tableau.add(13);
      tableau.add(24);
      afficheTableau(tableau);
      // ajout de la valeur 89 à la position 1
      tableau.add(1, 89);
      afficheTableau(tableau);
      // remplacer la valeur 89 par la valeur 3
      tableau.set(1, 3);
      afficheTableau(tableau);
      // enlève la valeur 13
      if (tableau.contains(13))
         tableau.remove((Integer)13);
      afficheTableau(tableau);
      //ajout d'une nouvelle valeur et affichage en ligne
      tableau.add(-45); out.print("tableau[] = { ");
      for(Integer valeur : tableau) out.print(valeur+" ");
      out.println("}");
      // position de la valeur -45
      out.println("Position de la valeur -45 : "+tableau.indexOf(-45));
      out.println("Position de la valeur -45 : "+tableau.lastIndexOf(-45));
      // effacer le tableau en entier
      tableau.clear();
      out.println("Taille du tableau : "+tableau.size());
   }
   public static void afficheTableau(ArrayList<Integer> tableau) {
      out.println("Taille du tableau : "+tableau.size());
      for (int i=0; i<tableau.size(); i++)
         out.println("tableau["+i+"] = "+tableau.get(i));      
   }
}

Ensembles d'objets uniques - java.util.HashSet et java.util.TreeSet

Ces deux classes gèrent des collections d'éléments qui doivent être différents les uns des autres. La méthode equals() est utilisée pour comparer les éléments.

Les listes chaînées et les tableaux vous permettent de spécifier l'ordre dans lequel vous voulez organiser vos éléments. Cependant, si vous recherchez un élément particulier et que vous ne vous rapeliez pas sa position, vous aurez besoin de parcourir tous les éléments jusqu'à ce que vous trouviez l'élément recherché. Cela requiert beaucoup de temps, surtout lorsque la collection contient pas mal d'éléments. Si l'ordre des éléments n'a pas d'importance, il existe des structures de données qui vous permettent de retrouver un élement très rapidement. L'inconvénient est que ces structures de données ne vous permettent pas de contrôler l'ordre des éléments. En effet, elles les organisent selon l'ordre qui leur permet de les retrouver facilement.

Une structure de données classique pour retrouver simplement un élément est la table de hachage. Une table de hachage calcule un nombre entier, appelé code de hachage, pour chacun des éléments.

Il existe deux classes qui mettent en oeuvre les tables de hachage, d'une part la classe HashSet qui mémorise ses éléments dans un ordre quelconque (et donc plus rapide si l'ordre n'a pas d'importance), et la classe TreeSet qui mémorise ses éléments dans l'ordre ascendant avec un arbre, pour maintenir plus rapidement le tri des éléments stockées.

Ci-dessous se trouve une collection d'entiers non répliquables dans l'ordre croissant.

import java.util.*;
import static java.lang.System.*;

public class Ensemble {
   public static void main(String[] args) {
      // ensemble d'entier par la classe enveloppe Integer
      TreeSet<Integer> ensemble = new TreeSet<Integer>();
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(-45);
      ensemble.add(13);
      ensemble.add(-24);
      afficheEnsemble(ensemble);
      // enlève la valeur 13
      if (ensemble.contains(13))
         ensemble.remove((Integer)13);
      afficheEnsemble(ensemble);
      //ajout d'une nouvelle valeur et affichage en ligne
      ensemble.add(-45); 
      afficheEnsemble(ensemble);
      // effacer le ensemble en entier
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Integer> ensemble) {
      out.print("ensemble = { ");
      for(Integer valeur : ensemble) out.print(valeur+" ");
      out.println("} : nombre = "+ensemble.size());
   }
}

Dictionnaires d'objets - java.util.HashMap et java.util.TreeMap

Ces deux classes gèrent des collections d'éléments accessibles par une clé correspondand (map en anglais) à un élément. Ces classes mémorisent en fait un ensemble d'entrées (entries) associant une clé et son élément (key-value). L'accès par clé dans une collection est comparable à l'accès par indice dans un tableau :

Un set (ensemble) est une collection qui vous permet de retrouver rapidement un élément. Pour cela, il faut le connaître exactement, ce qui n'est pas souvent le cas. En fait, nous disposons généralement de certaines informations importantes sur l'élément à rechercher, et il faut le retrouver à partir de ces informations. La structure de données cartes (ou map) permet d'effectuer ce genre de recherche. Une carte enregistre des paires clé / valeur. Une valeur peut être retrouvée à partir de la clé correspondante. Par exemple, vous pouvez disposer d'un répertoire téléphonique dans lequel les clés sont les noms des personnes et les valeurs les numéros de téléphone. La bibliothèque Java propose deux implémentations générales des cartes : HashMap et TreeMap.

La classe HashMap mémorise ses entrées dans un ordre quelconque, tandis que la classe TreeMap mémorise ses entrées dans l'ordre ascendant avec un arbre, pour maintenir plus rapidement le tri des éléments stockées.

Comme les clés peuvent être des chaînes de caractères, des instances des classes d'emballage ou d'autres classes, les classes HashMap et TreeMap permettent d'accéder à ces ensembles d'éléments de manière plus élaborée qu'avec un indice entier.

Dès qu'un nouvel objet est ajouté à une carte, il faut également fournir une clé associée. Ensuite, pour retrouver un objet, il faut se servir de la clé (et par conséquent, il faut la connaître). Si aucune valeur n'est stockée dans la carte pour une clé spécifiée, get() renvoie null.

Les clés doivent être uniques. Il n'est pas permis d'associer deux valeurs à la même clé. Si vous appelez la méthode put() deux fois avec la même clé, la seconde valeur remplace la première. En fait, put() renvoie la dernière valeur correspondant à la clé fournie.

Les cartes ne sont pas vraiment considérées comme des collections. Au sens de certains ensembles de structures de données, les cartes sont des collections de paires, c'est-à-dire des collections de valeurs indexés par des clés. Il reste néanmoins possible d'obtenir une vue d'une carte, c'est-à-dire un objet qui implémente l'interface Collection ou l'une de ses sous-interfaces.

L'ensemble des collections séquentielles implémentent l'interface Collection qui possède presque toutes les méthodes classiques comme add(), size(), isEmpty(), remove(), constains(), clear(), etc.

Il existe trois vues différentes :

1. Set<K> keySet() : procure l'ensemble des clés,
2. Collection<K> values() : délivre l'ensemble des valeurs,
3. Set<Map.Entry<K, V>> entrySet() : L'ensemble des paires clé / valeur.

L'ensemble des clés et des paires clé / valeur forme un set parce qu'il ne peut exister qu'un seul exemplaire d'une clé dans une carte. Les éléments de la troisième méthode font partie de la classe interne statique Map.Entry.

Il est généralement plus confortable de déclarer avec la structure de données cartes au travers de l'interface Map<K, V> plutôt que d'utiliser directement les classes HashMap et TreeMap. Effectivement, au travers de cette procédure, il est plus facile ensuite de récupérer chaque entrée séparément.

import java.util.*;
import java.util.Map;
import static java.lang.System.*;

public class Carte {
   public static void main(String[] args) {
      Map<String, String> répertoire = new TreeMap<String, String>();
      répertoire.put("Virgule GUILLEMET", "08-71-63-18-08");
      répertoire.put("Gaston LAGAFE", "09-43-45-45-18");
      répertoire.put("Jules SCHMIDT", "10-12-34-26-33");
      afficheRépertoire(répertoire);
      // supprime une carte
      répertoire.remove("Jules SCHMIDT");
      // remplace une carte
      répertoire.put("Gaston LAGAFE", "33-33-45-45-33");
      // recherche un numéro de téléphone
      out.println("Virgule GUILLEMET = "+répertoire.get("Virgule GUILLEMET"));
      afficheRépertoire(répertoire);
       // affiche toutes les entrées
      out.println(répertoire);
  }
   public static void afficheRépertoire(Map<String, String> répertoire) {
      out.println("nombre = "+répertoire.size());
      out.println("Numéros de téléphones { ");
      for (String  numéro : répertoire.values()) out.println("...."+numéro);
      out.println("}");
      out.println("Personnes { ");      
      for (String  personne : répertoire.keySet()) out.println("...."+personne);
      out.println("}");
      out.println("Répertoire { ");      
      for (Map.Entry<String, String> fiche : répertoire.entrySet())
         out.println("...."+fiche.getKey()+" : "+fiche.getValue());
      out.println("}");
   }   
}

Comparaison d'objets

Comment TreeSet (ou TreeMap) sait-il dans quel ordre trier les éléments ? Par défaut, cette structure de données part de l'hypothèse que vous insérez des éléments qui implémentent l'interface Comparable, ce qui est d'ailleurs le cas des classes que nous avons déjà utilisé comme la classe Integer ou la classe String.

Que se passe t-il si nous essayons de stocker des objets qui n'implémentent pas cette interface ? Si vous tentez d'exécuter le code ci-dessous, vous obtiendrez une erreur d'exécution (Exception levée). Effectivement, nous créons une nouvelle classe Personne sans s'occuper de l'interface Comparable, ainsi le système est incapable de placer ces personnes dans l'ordre croissant puisque nous ne lui indiquons pas comment faire.

import java.util.*;
import static java.lang.System.*;

public class Liste {
   public static void main(String[] args) {
      Personne schmidt, lagafe;
      
      TreeSet<Personne> ensemble = new TreeSet<Personne>();
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(lagafe = new Personne("LAGAFE", "Gaston", 23));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(schmidt = new Personne("SCHMIDT", "Jules", 30));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(new Personne("TALON", "Achille", 13));
      afficheEnsemble(ensemble);
      if (ensemble.contains(schmidt))
         ensemble.remove(schmidt);
      afficheEnsemble(ensemble);
      ensemble.add(lagafe); 
      afficheEnsemble(ensemble);
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Personne> ensemble) {
      out.print("ensemble = { ");
      for(Personne valeur : ensemble) out.println(valeur+" ");
      out.println("} : nombre = "+ensemble.size());
   }
}

class Personne {
   private String nom, prénom;
   private int âge;  
   public Personne(String nom, String prénom, int âge) {
      this.nom = nom;
      this.prénom = prénom;
      this.âge = âge;
   }
   public String getNom() { return nom; }
   public String getPrénom() { return prénom; }
   public int getÂge() { return âge; } 
}

Interface Comparable<T>

Le but de l'interface Comparable est justement là pour spécifier les critères de tri des classes que nous construisons. Cette interface déclare une seule méthode, compareTo() :

public interface Comparable<T> {
	int compareTo(T autreObjet);
}  

L'appel a.compareTo(b) doit renvoyer 0 si a et b sont égaux, un nombre entier négatif si a est inférieur à b (selon l'ordre de tri choisi), et un nombre entier positif si a est supérieur à b. La valeur exacte renvoyée par cette méthode n'a pas grande importance. Seul le signe (>0, 0 ou <0) a une signification.

Si vous insérez vos propres objets, il vous faut définir un ordre de tri en implémentant l'interface Comparable. Il n'existe aucune implémentation par défaut de compareTo() dans la classe Object.

import java.util.*;
import static java.lang.System.*;

public class Liste {
   public static void main(String[] args) {
      Personne schmidt, lagafe;
      
      TreeSet<Personne> ensemble = new TreeSet<Personne>();
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(lagafe = new Personne("LAGAFE", "Gaston", 23));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(schmidt = new Personne("SCHMIDT", "Jules", 30));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(new Personne("TALON", "Achille", 13));
      afficheEnsemble(ensemble);
      if (ensemble.contains(schmidt))
         ensemble.remove(schmidt);
      afficheEnsemble(ensemble);
      ensemble.add(lagafe); 
      afficheEnsemble(ensemble);
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Personne> ensemble) {
      out.println("ensemble { ");
      for(Personne p : ensemble) 
         out.println("..."+p.getNom()+" "+p.getPrénom()+" : "+p.getÂge());
      out.println("} : nombre = "+ensemble.size());
   }
}

class Personne implements Comparable<Personne> {
   private String nom, prénom;
   private int âge;  
   public Personne(String nom, String prénom, int âge) {
      this.nom = nom;
      this.prénom = prénom;
      this.âge = âge;
   }
   public String getNom() { return nom; }
   public String getPrénom() { return prénom; }
   public int getÂge() { return âge; } 

   public int compareTo(Personne p) {
      if (!nom.equalsIgnoreCase(p.nom)) return nom.compareToIgnoreCase(p.nom);
      if (!prénom.equalsIgnoreCase(p.prénom)) return prénom.compareToIgnoreCase(p.prénom);   
      return âge - p.âge;
   }
}

Il est bien évident que l'utilisation de l'interface Comparable pour définir un ordre de tri possède certaines limitations. Cette interface ne peut être implémentée qu'une seule fois. Mais que peut-on faire pour trier une ensemble d'articles selon leur numéro de code dans une collection, et en fonction de leur description dans une autre ? De plus que pouvez-vous faire pour trier des objets d'une classe dont le concepteur n'a pas pris le soin d'implémenter l'interface Comparable ?

Interface Comparator<T>

Dans ces situations, il faut demander à la collection de recourir à une autre méthode de comparaison, en passant un objet Comparator dans le constructeur TreeSet (ou MapSet). L'interface Comparator déclare une méthode compare(), avec deux paramètres explicites :

public interface Comparator<T> {
	int compare(T a, T b);
}  

Comme la méthode compareTo(), la méthode compare() renvoie une valeur entière négative si a et inférieure à b, nulle si a et b sont identiques, et positive dans le dernier cas.

Reprenons le même exemple et remplaçons l'interface Comparable par l'interface Comparator.

import java.util.*;
import static java.lang.System.*;

public class Liste {
   public static void main(String[] args) {
      Personne schmidt, lagafe;
      
      TreeSet<Personne> ensemble = new TreeSet<Personne>(new TrierPersonne());
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(lagafe = new Personne("LAGAFE", "Gaston", 23));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(schmidt = new Personne("SCHMIDT", "Jules", 30));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(new Personne("TALON", "Achille", 13));
      afficheEnsemble(ensemble);
      if (ensemble.contains(schmidt))
         ensemble.remove(schmidt);
      afficheEnsemble(ensemble);
      ensemble.add(lagafe); 
      afficheEnsemble(ensemble);
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Personne> ensemble) {
      out.println("ensemble { ");
      for(Personne p : ensemble) 
         out.println("..."+p.getNom()+" "+p.getPrénom()+" : "+p.getÂge());
      out.println("} : nombre = "+ensemble.size());
   }
}

class Personne {
   private String nom, prénom;
   private int âge;  
   public Personne(String nom, String prénom, int âge) {
      this.nom = nom;
      this.prénom = prénom;
      this.âge = âge;
   }
   public String getNom() { return nom; }
   public String getPrénom() { return prénom; }
   public int getÂge() { return âge; } 
}

class TrierPersonne implements Comparator<Personne> {
   public int compare(Personne p1, Personne p2) {
      if (!p1.getNom().equalsIgnoreCase(p2.getNom())) 
         return p1.getNom().compareToIgnoreCase(p2.getNom());
      if (!p1.getPrénom().equalsIgnoreCase(p2.getPrénom())) 
         return p1.getPrénom().compareToIgnoreCase(p2.getPrénom());
      return p1.getÂge() - p2.getÂge();
   }
}