Trier efficacement les objets en Java – 1ère partie

Le tri d'objets en Java est facilité par l'utilisation de méthodes de comparaison.

Nous allons voir dans cette première partie quel est le contrat de ces méthodes, comment les écrire et comment s'effectue le tri d'objets en Java à l'aide de ces méthodes.

Nous verrons ainsi l'utilité de l'interface Comparable et de la classe Comparator.

Comparaison d'objets

Les méthodes de comparaison permettent de trier une liste d'objets. Pour cela, ces méthodes consistent, pour deux instances d'un même objet, à comparer chacune de leurs propriétés et à indiquer quelle instance se situe avant l'autre selon l'ordre voulu.

Le contrat de ces méthodes de comparaison est défini par :

Nous verrons que l'écriture de ces méthodes peuvent vite devenir fastidieuses et sources d'erreurs lorsque les objets à comparer ont beaucoup de propriétés à tester.

Nous prendrons comme exemple le tri d'une liste de livres.

Méthode compareTo de l'interface Comparable

L'objet lui-même étend l'interface Comparable. Cette interface implique l'écriture de la méthode de comparaison entre l'instance de l'objet et une autre instance de ce même objet.

int compareTo(T object);

Cette méthode compareTo retourne un nombre entier qui indique :

  • si < 0 : l'instance est avant la deuxième instance
  • si = 0 : les deux instances sont à la même position
  • si > 0 : l'instance est après la deuxième instance

Pour l'exemple des livres à trier, la classe Livre implémente Comparable et la méthode compareTo :

public class Livre
    implements Comparable<Livre>
{
    public int compareTo(Livre livre2) {
        (...)
    }
    (...)
}

Ainsi la méthode compareTo retourne un nombre entier qui indique :

  • si < 0, le livre est avant le livre 2
  • si = 0, le livre est à la même position que le livre 2
  • si > 0, le livre est après le livre 2

Méthode compare de la classe Comparator

La classe Comparator impose l'écriture de la méthode compare qui prend en paramètre les deux instances à comparer.

public class Comparator<T extends Object>
{
    int compare(T o1, T o2);
}

De même que pour la méthode compareTo de l'interface Comparable, la méthode compare retourne un nombre entier qui indique :

  • si < 0 : la première instance est avant la deuxième instance
  • si = 0 : les deux instances sont à la même position
  • si > 0 : la première instance est après la deuxième instance

Pour un livre, nous pouvons ainsi avoir le comparateur LivreComparator qui étend Comparator et qui implémente la méthode compare:

public class LivreComparator
    extends Comparator<Livre>
{
    public int compare(Livre livre1, Livre livre2) {
        (...)
    }
}

La méthode compare de la classe LivreComparator retourne un nombre entier qui indique :

  • si < 0 : le livre 1 est avant le livre 2
  • si = 0 : les deux livres sont à la même position
  • si > 0 : le livre 1 est après le livre 2

Trier une liste

A l'aide des méthodes de comparaison, nous pouvons trier une liste d'objets grâce à la méthode sort de java.util.Collections.

Via Comparable.compareTo

Dans le cas où on se base sur la méthode de comparaison compareTo via l'interface Comparable implémentée par l'objet, nous avons à appeler la méthode sort en indiquant uniquement la liste des objets.

// Liste des livres
List<Livre> livres = getLivres();

// Tri des livres selon la méthode compareTo de Livre
Collections.sort(livres);

via Comparator.compare

Dans le cas où on se base sur la méthode de comparaison compare du Comparator, nous avons à appeler la méthode sort en indiquant la liste des objets et le Comparator.

// liste des livres
List<Livre> livres = getLivres();

// Comparaison de livres
LivreComparator livreComparator = new LivreComparator();

// Tri des livres selon le Comparator
Collections.sort(livres, livreComparator);

Collections triées

Les collections TreeSet et TreeMap sont des collections dont les objets sont toujours triés selon une méthode de comparaison, soit via Comparable, soit à l'aide d'un Comparator.

Comparable

Ainsi si nous souhaitons une liste de livres sans doublon et toujours triés, nous pouvons nous baser sur l'interface Comparable de l'objet Livre. Pour cela, nous définissons une instance de TreeSet. Cette implémentation va détecter que l'objet ajouté à la collection implémente l'interface Comparable et se servira alors de la méthode compareTo pour trier les objets insérés dans la collection.

// Liste de livres triés selon la méthode compareTo de Livre
Set<Livre> livres = new TreeSet<Livre>();

Comparator

Pour le tri de la liste, nous pouvons également spécifier un Comparator externe.

// Comparaison de livres
LivreComparator livreComparator = new LivreComparator();

// Liste de livres triés selon le Comparator
Set<Livre> livres = new TreeSet<Livre>(livreComparator);

Ecriture des méthodes de comparaison

Comme déjà dit plus haut, les méthodes de comparaisons consiste à indiquer la position d'un élément par rapport à un autre élément en comparant chacune de leurs propriétés selon l'ordre voulu.

Par exemple, nous souhaitons trier une liste de livres. Chaque livre dispose d'un auteur, d'un titre et d'une année de publication.

Nous souhaitons trier ces livres dans l'ordre suivant : d'abord par auteur, puis par année de publication et enfin par titre.

En pratique, nous allons d'abord comparer l'auteur de deux livres. Si les deux auteurs sont différents, on indique quel livre se situe avant l'autre suivant l'auteur dans l'ordre alphabétique. Dans le cas où les deux auteurs sont identiques, nous continuons la comparaison sur l'année de publication. Si les deux années sont différentes, on indique quel livre se situe avant l'autre suivant l'année. Enfin, dans le cas où les deux années sont égales, on compare sur le titre, en indiquant le livre qui se situe avant l'autre suivant le titre et d'après l'ordre alphabétique. Dans le cas où les deux titres sont identiques, comme il n'y a plus d'autres propriétés à comparer, on indique que les deux livres sont à la même position dans la liste.

Ecriture de la méthode compareTo de l'interface Comparable

L'écriture de la méthode de comparaison compareTo de l'interface Comparable consiste à comparer les propriétés de l'instance de l'objet avec les propriétés d'une autre instance de même type d'objet.

int compareTo(T object);

Par exemple, nous prenons l'exemple de la classe Livre et nous voulons trier suivant l'auteur, puis l'année, puis le titre. Nous avons ainsi le code suivant :

public class Livre
    implements Comparable<Livre>
{
    
    public int compareTo(Livre livre2)
    {
        // Comparaison sur l'auteur
        int compAuteur = this.getAuteur().compareTo(livre2.getAuteur());
        if(compAuteur != 0) { return compAuteur; }

        // Comparaison sur l'année
        int compAnnee = this.getAnnee().compareTo(livre2.getAnnee());
        if(compAnnee != 0) { return compAnnee; }

        // Comparaison sur le titre
        int compTitre = this.getTitre().compareTo(livre2.getTitre());
        if(compTitre != 0) { return compTitre; }

        // Les deux livres sont à la même position
        return 0;
    }

    (...)
}

Nous avons ainsi comparer chaque propriété des deux instances. Dès qu'une des propriétés ne correspond pas entre les deux instances, on retourne le nombre entier indiquant l'ordre entre les deux instances.

Classe Comparator

L'écriture de la méthode compare qui prend en paramètre les deux instances à comparer consiste à comparer les propriétés de ces deux instances. Cette méthode est quasiment identique à la méthode compareTo de l'interface Comparable, hormis que l'on travaille sur deux instances d'objets qui ne sont pas liées au Comparator. Cette séparation permet de séparer la logique de comparaison de l'objet lui-même.

public class LivreComparator
    extends Comparator<Livre>
{
    
    public int compare(Livre livre1, Livre livre2)
    {
        // Comparaison sur l'auteur
        int compAuteur = livre1.getAuteur().compareTo(livre2.getAuteur());
        if(compAuteur != 0) { return compAuteur; }

        // Comparaison sur l'année
        int compAnnee = livre1.getAnnee().compareTo(livre2.getAnnee());
        if(compAnnee != 0) { return compAnnee; }

        // Comparaison sur le titre
        int compTitre = livre1.getTitre().compareTo(livre2.getTitre());
        if(compTitre != 0) { return compTitre; }

        // Les deux livres sont à la même position
        return 0;
    }

    (...)
}

Ainsi la méthode compare du Comparator ressemble à la méthode compareTo précédente.

Difficultés et pièges dans l'écriture des méthodes de comparaison

Ces méthodes de comparaison bien qu'utiles sont difficiles à écrire.

En effet, il est nécessaire de gérer plusieurs éléments:

  • la comparaison de deux propriétés change suivant le type de la propriété
  • il faut gérer le cas où un des deux objets ou une des propriétés n'est pas défini, pour ne pas avoir d'exception de type NullPointerException. Dans l'exemple, que se passe-t-il si l'auteur du livre 1 est non défini, c'est à dire null.

Voici par exemple, la méthode de comparaison avec la gestion des objets et des propriétés qui peuvent être non définis :

public class LivreComparator
    extends Comparator<Livre>
{
    
    public int compare(Livre livre1, Livre livre2)
    {
        if(livre1 == null) {
            if(livre2 == null) { 
                // Les deux livres ne sont pas définis
                return 0; 
            } else { 
                // Seul le livre 1 n'est pas défini
                return -1;
            }
        } else {
            // Seul le livre 2 n'est pas défini
            return 1;
        }

        // Comparaison sur l'auteur
        String auteurLivre1NonNull = 
            StringUtils.trimToEmpty(livre1.getAuteur());
        String auteurLivre2NonNull = 
            StringUtils.trimToEmpty(livre2.getAuteur());

        int compAuteur = 
            auteurLivre1NonNull.compareTo(auteurLivre2NonNull);
        if(compAuteur != 0) { return compAuteur; }

        // Comparaison sur l'année
        Integer anneeLivre1NonNull;
        if(livre1.getAnnee()==null) {
            anneeLivre1NonNull = 0;
        } else {
            anneeLivre1NonNull = livre1.getAnnee();
        }
        Integer anneeLivre2NonNull;
        if(livre2.getAnnee()==null) {
            anneeLivre2NonNull = 0;
        } else {
            anneeLivre2NonNull = livre2.getAnnee();
        }

        int compAnnee = 
            anneeLivre1NonNull.compareTo(anneeLivre2NonNull);
        if(compAnnee != 0) { return compAnnee; }

        // Comparaison sur le titre
        String titreLivre1NonNull = 
            StringUtils.trimToEmpty(livre1.getTitre());
        String titreLivre2NonNull = 
            StringUtils.trimToEmpty(livre2.getTitre());

        int compTitre = 
            titreLivre1NonNull.compareTo(titreLivre2NonNull);
        if(compTitre != 0) { return compTitre; }

        // Les deux livres sont à la même position
        return 0;
    }

    (...)
}

Conclusion

Il est important de maîtriser le tri des objets en Java avec l'utilisation de l'interface Comparable et de la classe Comparator.

Cependant, nous nous apercevons que l'écriture des méthodes de comparaison peut rapidement devenir un parcours du combattant où il faut déjouer tous les pièges.

L'écriture de tests unitaires peuvent aider, cependant le test de tous les cas possibles devient rapidement fastidieux.

C'est pourquoi je vous présenterai dans un second post des solutions pour faciliter l'écriture de ces méthodes de comparaison, notamment à l'aide de la bibliothèque Guava.

Référence

2 commentaires

  1. ipsde-il.com

    Good post, I want say thanks to author because i have found a lot exciting knowledge. I will definitely subscribe RSS. Best wishes…

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Captcha *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.