Comment trier des objets en Java avec Comparable et Comparator ?

Nous avons discuté de “l’ordre” pour les classes TreeSet et TreeMap. Pour les nombres, l’ordre est évident —c’est l’ordre numérique. Pour les objets String, l’ordre est défini selon le mappage des caractères Unicode.

Lorsque vous travaillez avec un String, souvenez-vous que les chiffres sont triés avant les lettres, et les lettres majuscules sont triées avant les lettres minuscules.

Nous utilisons Collections.sort() dans plusieurs de ces exemples. Il renvoie void car le paramètre de méthode est ce qui est trié.

Vous pouvez également trier des objets que vous créez vous-même. Java fournit une interface appelée Comparable. Si votre classe implémente Comparable, elle peut être utilisée dans des structures de données qui nécessitent une comparaison. Il existe également une classe appelée Comparator, qui est utilisée pour spécifier que vous souhaitez utiliser un ordre différent de celui fourni par l’objet lui-même.

Comparable et Comparator sont suffisamment similaires pour être délicats. Dans cette section, nous discutons d’abord de Comparable. Ensuite, en parcourant Comparator, nous soulignons toutes les différences.

Création d’une Classe Comparable

L’interface Comparable n’a qu’une seule méthode. En fait, c’est l’interface entière :

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

Le générique T vous permet d’implémenter cette méthode et de spécifier le type de votre objet. Cela vous permet d’éviter un cast lors de l’implémentation de compareTo(). N’importe quel objet peut être Comparable. Par exemple, nous avons un groupe de canards et voulons les trier par nom. D’abord, nous mettons à jour la déclaration de classe pour hériter de Comparable<Canard>, puis nous implémentons la méthode compareTo :

import java.util.*;
public class Canard implements Comparable<Canard> {
    private String nom;
    public Canard(String nom) {
        this.nom = nom;
    }
    public String toString() { // utiliser une sortie lisible
        return nom;
    }
    public int compareTo(Canard c) {
        return nom.compareTo(c.nom); // trie par nom en ordre croissant
    }
    public static void main(String[] args) {
        var canards = new ArrayList<Canard>();
        canards.add(new Canard("Coin"));
        canards.add(new Canard("Barboteur"));
        Collections.sort(canards); // trier par nom
        System.out.println(canards); // [Barboteur, Coin]
    }
}

Sans implémenter cette interface, tout ce que nous avons est une méthode nommée compareTo(), mais ce ne serait pas un objet Comparable. Nous pourrions également implémenter Comparable<Object> ou une autre classe pour T, mais ce ne serait pas aussi utile pour trier un groupe d’objets Canard.

La classe Canard surcharge la méthode toString() de Object. Cette surcharge fournit une sortie utile lors de l’impression des canards. Sans cette surcharge, la sortie serait quelque chose comme [Canard@70dea4e, Canard@5c647e05] — difficilement utile pour voir quel nom de canard vient en premier.

Enfin, la classe Canard implémente compareTo(). Comme Canard compare des objets de type String et que la classe String a déjà une méthode compareTo(), elle peut simplement déléguer.

Nous devons encore savoir ce que la méthode compareTo() renvoie pour que nous puissions écrire la nôtre. Il y a trois règles à connaître :

• Le nombre 0 est renvoyé lorsque l’objet actuel est équivalent à l’argument de compareTo().
• Un nombre négatif (inférieur à 0) est renvoyé lorsque l’objet actuel est plus petit que l’argument de compareTo().
• Un nombre positif (supérieur à 0) est renvoyé lorsque l’objet actuel est plus grand que l’argument de compareTo().

Examinons une implémentation de compareTo() qui compare des nombres au lieu d’objets String :

public class Animal implements Comparable<Animal> {
    private int id;
    public int compareTo(Animal a) {
        return id - a.id; // trie par id en ordre croissant
    }
    public static void main(String[] args) {
        var a1 = new Animal();
        var a2 = new Animal();
        a1.id = 5;
        a2.id = 7;
        System.out.println(a1.compareTo(a2)); // -2
        System.out.println(a1.compareTo(a1)); // 0
        System.out.println(a2.compareTo(a1)); // 2
    }
}

Les lignes 3-5 montrent une façon de comparer deux valeurs int. Nous aurions pu utiliser Integer.compare(id, a.id) à la place. Assurez-vous de reconnaître les deux approches.

Souvenez-vous que id – a.id trie en ordre croissant, et a.id – id trie en ordre décroissant.

Les lignes 11-13 confirment que nous avons correctement implémenté compareTo(). La ligne 11 compare un id plus petit à un plus grand, et imprime donc un nombre négatif. La ligne 12 compare des animaux avec le même id, et imprime donc 0. La ligne 13 compare un id plus grand à un plus petit, et renvoie donc un nombre positif.

Cast de l’Argument compareTo()

Lorsque vous travaillez avec du code legacy ou du code qui n’utilise pas les génériques, la méthode compareTo() nécessite un cast car elle reçoit un Object.

public class CanardLegacy implements Comparable {
    private String nom;
    public int compareTo(Object obj) {
        CanardLegacy c = (CanardLegacy) obj; // cast car pas de génériques
        return nom.compareTo(c.nom);
    }
}

Comme nous ne spécifions pas de type générique pour Comparable, Java suppose que nous voulons un Object, ce qui signifie que nous devons caster en CanardLegacy avant d’accéder aux variables d’instance.

Vérification pour null

Lorsque vous travaillez avec Comparable et Comparator dans ce chapitre, nous avons tendance à supposer que les données ont des valeurs, mais ce n’est pas toujours le cas. Lorsque vous écrivez vos propres méthodes de comparaison, vous devriez vérifier les données avant de les comparer si elles ne sont pas validées à l’avance.

public class CanardManquant implements Comparable<CanardManquant> {
    private String nom;
    public int compareTo(CanardManquant canard) {
        if (canard == null)
            throw new IllegalArgumentException("Canard mal formé !");
        if (this.nom == null && canard.nom == null)
            return 0;
        else if (this.nom == null) return -1;
        else if (canard.nom == null) return 1;
        else return nom.compareTo(canard.nom);
    }
}

Cette méthode lance une exception si elle reçoit un objet CanardManquant null. Qu’en est-il de l’ordre ? Si le nom d’un canard est null, il est trié en premier.

Maintenir compareTo() et equals() Cohérents

Si vous écrivez une classe qui implémente Comparable, vous introduisez une nouvelle logique métier pour déterminer l’égalité. La méthode compareTo() renvoie 0 si deux objets sont égaux, tandis que votre méthode equals() renvoie true si deux objets sont égaux. Un ordre naturel qui utilise compareTo() est dit être cohérent avec equals si, et seulement si, x.equals(y) est true chaque fois que x.compareTo(y) égale 0.

De même, x.equals(y) doit être false chaque fois que x.compareTo(y) n’est pas 0. Vous êtes fortement encouragés à rendre vos classes Comparable cohérentes avec equals car toutes les classes de collection ne se comportent pas de manière prévisible si les méthodes compareTo() et equals() ne sont pas cohérentes.

Par exemple, la classe Produit suivante définit une méthode compareTo() qui n’est pas cohérente avec equals :

public class Produit implements Comparable<Produit> {
    private int id;
    private String nom;
    
    public int hashCode() { return id; }
    public boolean equals(Object obj) {
        if(!(obj instanceof Produit)) return false;
        var autre = (Produit) obj;
        return this.id == autre.id;
    }
    public int compareTo(Produit obj) {
        return this.nom.compareTo(obj.nom);
    }
}

Vous pourriez trier des objets Produit par nom, mais les noms ne sont pas uniques. La méthode compareTo() n’a pas besoin d’être cohérente avec equals. Une façon de corriger cela est d’utiliser un Comparator pour définir le tri ailleurs.

Maintenant que vous savez comment implémenter des objets Comparable, vous allez examiner un Comparator et vous concentrer sur les différences.

Comparer des Données avec un Comparator

Parfois, vous voulez trier un objet qui n’a pas implémenté Comparable, ou vous voulez trier des objets de différentes manières à différents moments. Supposons que nous ajoutons un poids à notre classe Canard. Nous avons maintenant ce qui suit :

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Canard implements Comparable<Canard> {
    private String nom;
    private int poids;
    
    // Supposons que getters/setters/constructeurs sont fournis
    
    public String toString() { return nom; }
    
    public int compareTo(Canard c) {
        return nom.compareTo(c.nom);
    }
    
    public static void main(String[] args) {
        Comparator<Canard> parPoids = new Comparator<Canard>() {
            public int compare(Canard c1, Canard c2) {
                return c1.getPoids()-c2.getPoids();
            }
        };
        var canards = new ArrayList<Canard>();
        canards.add(new Canard("Coin", 7));
        canards.add(new Canard("Barboteur", 10));
        Collections.sort(canards);
        System.out.println(canards); // [Barboteur, Coin]
        Collections.sort(canards, parPoids);
        System.out.println(canards); // [Coin, Barboteur]
    }
}

Tout d’abord, notez que ce programme importe java.util.Comparator. Nous ne montrons pas toujours les imports car vous pouvez supposer qu’ils sont présents s’ils ne sont pas montrés. Ici, nous montrons l’import pour attirer l’attention sur le fait que Comparable et Comparator sont dans des packages différents : java.lang et java.util, respectivement. Cela signifie que Comparable peut être utilisé sans instruction d’import, tandis que Comparator ne le peut pas.

La classe Canard elle-même ne peut définir qu’une seule méthode compareTo(). Dans ce cas, le nom a été choisi. Si nous voulons trier par autre chose, nous devons définir cet ordre de tri en dehors de la méthode compareTo() en utilisant une classe séparée ou une expression lambda.

Les lignes 18-22 de la méthode main() montrent comment définir un Comparator en utilisant une classe interne. Aux lignes 26-29, nous trions sans le Comparator puis avec le Comparator pour voir la différence dans la sortie.

Comparator est une interface fonctionnelle car il n’y a qu’une seule méthode abstraite à implémenter. Cela signifie que nous pouvons réécrire le Comparator des lignes 18-22 en utilisant une expression lambda, comme illustré ici :

Comparator<Canard> parPoids = (c1, c2) -> c1.getPoids()-c2.getPoids();

Alternativement, nous pouvons utiliser une référence de méthode et une méthode auxiliaire pour spécifier que nous voulons trier par poids.

Comparator<Canard> parPoids = Comparator.comparing(Canard::getPoids);

Dans cet exemple, Comparator.comparing() est une méthode d’interface statique qui crée un Comparator à partir d’une expression lambda ou d’une référence de méthode. Pratique, n’est-ce pas ?

Comparable est-il une Interface Fonctionnelle ?

Nous avons dit que Comparator est une interface fonctionnelle car elle a une seule méthode abstraite. Comparable est également une interface fonctionnelle puisqu’elle a aussi une seule méthode abstraite. Cependant, utiliser une lambda pour Comparable serait absurde. Le but de Comparable est de l’implémenter à l’intérieur de l’objet à comparer.

Comparaison de Comparable et Comparator

Il existe plusieurs différences entre Comparable et Comparator. Nous les avons répertoriées pour vous dans le tableau suivant.

Différence	Comparable	Comparator
Nom du package	java.lang	java.util
Interface doit être implémentée par la classe comparée ?	Oui	Non
Nom de méthode dans l’interface	compareTo()	compare()
Nombre de paramètres	1	2
Commun de déclarer en utilisant une lambda	Non	Oui

Mémorisez ce tableau — vraiment. Portez une attention particulière aux noms de méthode et au nombre de paramètres lorsque vous voyez Comparator et Comparable dans des questions.

Voyez-vous pourquoi ceci ne compile pas ?

var parPoids = new Comparator<Canard>() { // NE COMPILE PAS
    public int compareTo(Canard c1, Canard c2) {
        return c1.getPoids()-c2.getPoids();
    }
};

Le nom de la méthode est incorrect. Un Comparator doit implémenter une méthode nommée compare().

Comparaison de Plusieurs Champs

Lorsque vous écrivez un Comparator qui compare plusieurs variables d’instance, le code devient un peu désordonné. Supposons que nous avons une classe Ecureuil, comme montré ici :

public class Ecureuil {
    private int poids;
    private String espece;
    // Supposons que getters/setters/constructeurs sont fournis
}

Nous voulons écrire un Comparator pour trier par nom d’espèce. Si deux écureuils sont de la même espèce, nous voulons trier celui qui pèse le moins d’abord. Nous pourrions le faire avec un code qui ressemble à ceci :

public class ComparateurMultiChamp implements Comparator<Ecureuil> {
    public int compare(Ecureuil e1, Ecureuil e2) {
        int resultat = e1.getEspece().compareTo(e2.getEspece());
        if (resultat != 0) return resultat;
        return e1.getPoids()-e2.getPoids();
    }
}

Ceci fonctionne en supposant qu’aucun nom d’espèce n’est null. Il vérifie un champ. S’ils ne correspondent pas, nous avons terminé le tri. S’ils correspondent, on regarde le champ suivant. Ce n’est pas facile à lire cependant. C’est aussi facile de se tromper. Changer != à == casse complètement le tri.

Alternativement, nous pouvons utiliser des références de méthode et construire le Comparator. Ce code représente la logique pour la même comparaison :

Comparator<Ecureuil> c = Comparator.comparing(Ecureuil::getEspece)
    .thenComparingInt(Ecureuil::getPoids);

Cette fois, nous enchaînons les méthodes. D’abord, nous créons un Comparator sur l’espèce en ordre croissant. Ensuite, s’il y a égalité, nous trions par poids. Nous pouvons également trier en ordre décroissant. Certaines méthodes sur Comparator, comme thenComparingInt(), sont des méthodes par défaut.

Supposons que nous voulons trier en ordre décroissant par espèce.

var c = Comparator.comparing(Ecureuil::getEspece).reversed();

Le tableau suivant montre les méthodes auxiliaires que vous devriez connaître pour construire un Comparator. Nous avons omis les types de paramètres pour vous garder concentré sur les méthodes. Elles utilisent beaucoup des interfaces fonctionnelles que vous avez apprises dans le chapitre précédent.

Méthode	Description
comparing(fonction)	Compare par résultats de fonction qui renvoie n’importe quel Object (ou primitif autoboxé en Object).
comparingDouble(fonction)	Compare par résultats de fonction qui renvoie double.
comparingInt(fonction)	Compare par résultats de fonction qui renvoie int.
comparingLong(fonction)	Compare par résultats de fonction qui renvoie long.
naturalOrder()	Trier en utilisant l’ordre spécifié par l’implémentation Comparable sur l’objet lui-même.
reverseOrder()	Trier en utilisant l’inverse de l’ordre spécifié par l’implémentation Comparable sur l’objet lui-même.

Le tableau suivant montre les méthodes que vous pouvez enchaîner à un Comparator pour spécifier davantage son comportement.

Méthode	Description
reversed()	Inverse l’ordre du Comparator enchaîné.
thenComparing(fonction)	Si le Comparator précédent renvoie 0, utilise ce comparateur qui renvoie Object ou peut être autoboxé en un.
thenComparingDouble(fonction)	Si le Comparator précédent renvoie 0, utilise ce comparateur qui renvoie double. Sinon, renvoie la valeur du Comparator précédent.
thenComparingInt(fonction)	Si le Comparator précédent renvoie 0, utilise ce comparateur qui renvoie int. Sinon, renvoie la valeur du Comparator précédent.
thenComparingLong(fonction)	Si le Comparator précédent renvoie 0, utilise ce comparateur qui renvoie long. Sinon, renvoie la valeur du Comparator précédent.

Vous avez probablement remarqué que nous ignorons souvent les valeurs null lors de la vérification d’égalité et de la comparaison d’objets. Dans le monde réel, les choses ne sont pas si nettes. Vous devrez décider comment gérer les valeurs null ou les empêcher d’être dans votre objet.

Tri et Recherche

Maintenant que vous avez tout appris sur Comparable et Comparator, nous pouvons enfin faire quelque chose d’utile avec eux, comme le tri. La méthode Collections.sort() utilise la méthode compareTo() pour trier. Elle s’attend à ce que les objets à trier soient Comparable.

public class TriLapins {
    static record Lapin(int id) {}
    public static void main(String[] args) {
        List<Lapin> lapins = new ArrayList<>();
        lapins.add(new Lapin(3));
        lapins.add(new Lapin(1));
        Collections.sort(lapins); // NE COMPILE PAS
    }
}

Java sait que l’enregistrement Lapin n’est pas Comparable. Il sait que le tri échouera, donc il ne laisse même pas le code compiler. Vous pouvez corriger cela en passant un Comparator à sort(). Rappelez-vous qu’un Comparator est utile lorsque vous voulez spécifier l’ordre de tri sans utiliser une méthode compareTo().

Comparator<Lapin> c = (l1, l2) -> l1.id - l2.id;
Collections.sort(lapins, c);
System.out.println(lapins); // [Lapin[id=1], Lapin[id=3]]

Supposons que vous voulez trier les lapins en ordre décroissant. Vous pourriez changer le Comparator en l2.id – l1.id. Alternativement, vous pourriez inverser le contenu de la liste après :

Comparator<Lapin> c = (l1, l2) -> l1.id - l2.id;
Collections.sort(lapins, c);
Collections.reverse(lapins);
System.out.println(lapins); // [Lapin[id=3], Lapin[id=1]]

Les méthodes sort() et binarySearch() vous permettent de passer un objet Comparator lorsque vous ne voulez pas utiliser l’ordre naturel.

Révision de binarySearch()

La méthode binarySearch() nécessite une List triée.

List<Integer> liste = Arrays.asList(6,9,1,8);
Collections.sort(liste); // [1, 6, 8, 9]
System.out.println(Collections.binarySearch(liste, 6)); // 1
System.out.println(Collections.binarySearch(liste, 3)); // -2

La ligne 2 trie la List pour que nous puissions appeler correctement la recherche binaire. La ligne 3 imprime l’index auquel une correspondance est trouvée. La ligne 4 imprime un de moins que l’index négativé où la valeur demandée devrait être insérée. Le nombre 3 devrait être inséré à l’index 1 (après le nombre 1 mais avant le nombre 6). En négativant cela, on obtient −1, et en soustrayant 1, on obtient −2.

Il y a un piège lorsqu’on travaille avec binarySearch(). Que pensez-vous que ce qui suit affiche ?

var noms = Arrays.asList("Fluffy", "Hoppy");
Comparator<String> c = Comparator.reverseOrder();
var index = Collections.binarySearch(noms, "Hoppy", c);
System.out.println(index);

La réponse est -1. Avant de paniquer, vous n’avez pas besoin de savoir que la réponse est -1. Vous devez savoir que la réponse n’est pas définie. La ligne 1 crée une liste, [Fluffy, Hoppy]. Cette liste se trouve être triée en ordre croissant. La ligne 2 crée un Comparator qui inverse l’ordre naturel. La ligne 3 demande une recherche binaire en ordre décroissant. Comme la liste n’est pas dans cet ordre, nous ne remplissons pas la précondition pour effectuer une recherche.

Bien que le résultat de l’appel à binarySearch() sur une liste mal triée soit indéfini, parfois vous pouvez avoir de la chance. Par exemple, la recherche commence au milieu d’une liste avec un nombre impair d’éléments. Si vous demandez par hasard l’élément du milieu, l’index renvoyé sera ce que vous attendez.

Plus tôt dans ce chapitre, nous avons parlé des collections qui nécessitent que les classes implémentent Comparable. Contrairement au tri, elles ne vérifient pas que vous avez implémenté Comparable au moment de la compilation.

Revenons à notre Lapin qui n’implémente pas Comparable, nous essayons de l’ajouter à un TreeSet :

public class UtiliserTreeSet {
    static class Lapin{ int id; }
    public static void main(String[] args) {
        Set<Canard> canards = new TreeSet<>();
        canards.add(new Canard("Barboteur"));
        
        Set<Lapin> lapins = new TreeSet<>();
        lapins.add(new Lapin()); // ClassCastException
    }
}

La ligne 6 est correcte. Canard implémente bien Comparable. TreeSet peut le trier dans la bonne position dans l’ensemble. La ligne 9 est un problème. Lorsque TreeSet essaie de le trier, Java découvre que Lapin n’implémente pas Comparable. Java lance une exception qui ressemble à ceci :

Exception in thread "main" java.lang.ClassCastException:
    class Lapin cannot be cast to class java.lang.Comparable

Il peut sembler étrange que cette exception soit lancée lorsque le premier objet est ajouté à l’ensemble. Après tout, il n’y a encore rien à comparer. Java fonctionne ainsi par cohérence.

Tout comme pour la recherche et le tri, vous pouvez indiquer aux collections qui nécessitent un tri que vous souhaitez utiliser un Comparator spécifique. Par exemple :

Set<Lapin> lapins = new TreeSet<>((l1, l2) -> l1.id - l2.id);
lapins.add(new Lapin());

Maintenant Java sait que vous voulez trier par id, et tout va bien. Un Comparator est un objet utile. Il vous permet de séparer l’ordre de tri de l’objet à trier. Remarquez que la ligne 9 dans les deux exemples précédents est la même. C’est la déclaration du TreeSet qui a changé.

Tri d’une Liste

Bien que vous puissiez appeler Collections.sort(liste), vous pouvez également trier directement sur l’objet liste.

List<String> lapins = new ArrayList<>();
lapins.add("grandes oreilles");
lapins.add("sauteur");
lapins.add("duveteux");
System.out.println(lapins); // [grandes oreilles, sauteur, duveteux]
lapins.sort((l1, l2) -> l1.compareTo(l2));
System.out.println(lapins); // [duveteux, grandes oreilles, sauteur]

Sur la ligne 6, nous trions la liste par ordre alphabétique. La méthode sort() prend un Comparator qui fournit l’ordre de tri. Rappelez-vous que Comparator prend deux paramètres et renvoie un int. Si vous avez besoin de réviser ce que signifie la valeur de retour d’une opération compare(), consultez la section Comparator de ce chapitre.

Il n’y a pas de méthode de tri sur Set ou Map. Ces deux types sont non ordonnés, donc cela n’aurait pas de sens de les trier.