Java Language
Comparable et Comparateur

Syntaxe

• la classe publique MyClass implémente Comparable <MyClass >
• classe publique MyComparator implémente Comparator <SomeOtherClass >
• public int compareTo (MyClass autre)
• public int compare (SomeOtherClass o1, SomeOtherClass o2)

Remarques

public int comareTo(MyClass other) {
    return (int)(doubleField - other.doubleField); //THIS IS BAD
}

public int comareTo(MyClass other) {
    return Double.compare(doubleField,other.doubleField); //THIS IS GOOD
} 

public class A implements Comparable<A>

Trier une liste en utilisant Comparable ou un comparateur

Supposons que nous travaillons sur une classe représentant une personne par son nom et son prénom. Nous avons créé une classe de base pour ce faire et implémenté des méthodes equals et hashCode appropriées.

public class Person {

    private final String lastName; //invariant - nonnull
    private final String firstName; //invariant - nonnull

    public Person(String firstName, String lastName){
        this.firstName = firstName != null ? firstName : "";
        this.lastName = lastName != null ? lastName : "";
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public String toString() {
        return lastName + ", " + firstName;
    }

    @Override
    public boolean equals(Object o) {
        if (! (o instanceof Person)) return false;
        Person p = (Person)o;
        return firstName.equals(p.firstName) && lastName.equals(p.lastName);
    }

    @Override
    public int hashCode() {
        return Objects.hash(firstName, lastName);
    }
}

Maintenant, nous aimerions trier une liste d'objets Person par leur nom, comme dans le scénario suivant:

public static void main(String[] args) {
    List<Person> people = Arrays.asList(new Person("John", "Doe"),
                                     new Person("Bob", "Dole"),
                                     new Person("Ronald", "McDonald"),
                                     new Person("Alice", "McDonald"),
                                     new Person("Jill", "Doe"));
    Collections.sort(people); //This currently won't work.
}

Malheureusement, comme indiqué ci-dessus, ce qui précède ne sera pas compilé. Collections.sort(..) sait seulement trier une liste si les éléments de cette liste sont comparables ou si une méthode de comparaison personnalisée est fournie.

Si on vous demandait de trier la liste suivante: 1,3,5,4,2 , vous n'auriez aucun problème à dire que la réponse est 1,2,3,4,5 . Cela est dû au fait que les entiers (à la fois en Java et en mathématiques) ont un classement naturel , un classement de base de comparaison standard par défaut. Pour donner à notre classe Person un ordre naturel, nous implémentons Comparable<Person> , qui nécessite l'implémentation de la méthode compareTo(Person p):

public class Person implements Comparable<Person> {

    private final String lastName; //invariant - nonnull
    private final String firstName; //invariant - nonnull

    public Person(String firstName, String lastName) {
        this.firstName = firstName != null ? firstName : "";
        this.lastName = lastName != null ? lastName : "";
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public String toString() {
        return lastName + ", " + firstName;
    }

    @Override
    public boolean equals(Object o) {
        if (! (o instanceof Person)) return false;
        Person p = (Person)o;
        return firstName.equals(p.firstName) && lastName.equals(p.lastName);
    }

    @Override
    public int hashCode() {
        return Objects.hash(firstName, lastName);
    }

    @Override
    public int compareTo(Person other) {
        // If this' lastName and other's lastName are not comparably equivalent,
        // Compare this to other by comparing their last names.
        // Otherwise, compare this to other by comparing their first names
        int lastNameCompare = lastName.compareTo(other.lastName);
        if (lastNameCompare != 0) {
            return lastNameCompare;
        } else {
            return firstName.compareTo(other.firstName);
        }
    }
}

Maintenant, la méthode principale donnée fonctionnera correctement

public static void main(String[] args) {
    List<Person> people = Arrays.asList(new Person("John", "Doe"),
                                     new Person("Bob", "Dole"),
                                     new Person("Ronald", "McDonald"),
                                     new Person("Alice", "McDonald"),
                                     new Person("Jill", "Doe"));
    Collections.sort(people); //Now functions correctly

    //people is now sorted by last name, then first name:
    // --> Jill Doe, John Doe, Bob Dole, Alice McDonald, Ronald McDonald
}

Si, toutefois, vous ne souhaitez pas ou ne pouvez pas modifier la classe Person , vous pouvez fournir un Comparator<T> personnalisé Comparator<T> qui gère la comparaison de deux objets Person . Si on vous demandait de trier la liste suivante: circle, square, rectangle, triangle, hexagon vous ne le pouviez pas, mais si vous deviez trier cette liste en fonction du nombre de coins , vous pourriez le faire. De même, fournir un comparateur indique à Java comment comparer deux objets normalement non comparables.

public class PersonComparator implements Comparator<Person> {

    public int compare(Person p1, Person p2) {
        // If p1's lastName and p2's lastName are not comparably equivalent,
        // Compare p1 to p2 by comparing their last names.
        // Otherwise, compare p1 to p2 by comparing their first names
        if (p1.getLastName().compareTo(p2.getLastName()) != 0) {
            return p1.getLastName().compareTo(p2.getLastName());
        } else {
            return p1.getFirstName().compareTo(p2.getFirstName());
        }
    }
}

//Assume the first version of Person (that does not implement Comparable) is used here
public static void main(String[] args) {
    List<Person> people = Arrays.asList(new Person("John", "Doe"),
                                     new Person("Bob", "Dole"),
                                     new Person("Ronald", "McDonald"),
                                     new Person("Alice", "McDonald"),
                                     new Person("Jill", "Doe"));
    Collections.sort(people); //Illegal, Person doesn't implement Comparable.
    Collections.sort(people, new PersonComparator()); //Legal

    //people is now sorted by last name, then first name:
    // --> Jill Doe, John Doe, Bob Dole, Alice McDonald, Ronald McDonald
}

Les comparateurs peuvent également être créés / utilisés en tant que classe interne anonyme

//Assume the first version of Person (that does not implement Comparable) is used here
public static void main(String[] args) {
    List<Person> people = Arrays.asList(new Person("John", "Doe"),
                                     new Person("Bob", "Dole"),
                                     new Person("Ronald", "McDonald"),
                                     new Person("Alice", "McDonald"),
                                     new Person("Jill", "Doe"));
    Collections.sort(people); //Illegal, Person doesn't implement Comparable.

    Collections.sort(people, new PersonComparator()); //Legal

    //people is now sorted by last name, then first name:
    // --> Jill Doe, John Doe, Bob Dole, Alice McDonald, Ronald McDonald

    //Anonymous Class
    Collections.sort(people, new Comparator<Person>() { //Legal
        public int compare(Person p1, Person p2) {
            //Method code...
        }
    });
}

    //Lambda
    Collections.sort(people, (p1, p2) -> { //Legal
        //Method code....
    });

Collections.sort(people, Comparator.comparing(Person::getLastName)
                                .thenComparing(Person::getFirstName));

Les méthodes de comparaison et de comparaison

L'interface Comparable<T> nécessite une méthode:

public interface Comparable<T> {

    public int compareTo(T other);

}

Et l'interface Comparator<T> nécessite une méthode:

public interface Comparator<T> {

    public int compare(T t1, T t2);

}

Ces deux méthodes font essentiellement la même chose, avec une différence mineure: compareTo compare this à l' other , alors que compare compare t1 à t2 , ne pas se soucier du tout this .

Outre cette différence, les deux méthodes ont des exigences similaires. Spécifiquement (pour compareTo), compare cet objet avec l'objet spécifié pour l'ordre. Renvoie un entier négatif, zéro ou un entier positif car cet objet est inférieur, égal ou supérieur à l'objet spécifié. Ainsi, pour la comparaison de a et b :

• Si a < b , a.compareTo(b) et compare(a,b) doivent renvoyer un entier négatif, et que b.compareTo(a) et compare(b,a) doivent retourner un entier positif
• Si a > b , a.compareTo(b) et compare(a,b) devraient renvoyer un entier positif, et b.compareTo(a) et compare(b,a) devraient retourner un entier négatif
• Si a égale à b pour la comparaison, toutes les comparaisons doivent renvoyer 0 .

Tri naturel (comparable) vs explicite (comparateur)

Il existe deux méthodes Collections.sort() :

• Celui qui prend List<T> comme paramètre où T doit implémenter Comparable et remplacer la méthode compareTo() qui détermine l'ordre de tri.
• L'un qui prend les listes et les comparateurs comme arguments, où le comparateur détermine l'ordre de tri.

Tout d'abord, voici une classe Person qui implémente Comparable:

public class Person implements Comparable<Person> {         
    private String name;  
    private int age;

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }         

    @Override
    public int compareTo(Person o) {
        return this.getAge() - o.getAge();
    }
    @Override
    public String toString() {
        return this.getAge()+"-"+this.getName();
    }

}

Voici comment utiliser la classe ci-dessus pour trier une liste dans l'ordre naturel de ses éléments, définie par la méthode compareTo() :

//-- usage
List<Person> pList = new ArrayList<Person>();
            Person p = new Person();
            p.setName("A");
            p.setAge(10);
            pList.add(p);
            p = new Person();
            p.setName("Z");
            p.setAge(20);
            pList.add(p);
            p = new Person();
            p.setName("D");
            p.setAge(30);
            pList.add(p);
            
            //-- natural sorting i.e comes with object implementation, by age
            Collections.sort(pList);

            System.out.println(pList);

Voici comment vous utiliseriez un comparateur en ligne anonyme pour trier une liste qui n’implémente pas Comparable ou, dans ce cas, pour trier une liste dans un ordre autre que le classement naturel:

            //-- explicit sorting, define sort on another property here goes with name
            Collections.sort(pList, new Comparator<Person>() {

                @Override
                public int compare(Person o1, Person o2) {
                    return o1.getName().compareTo(o2.getName());
                }
            });            
            System.out.println(pList);

Tri des entrées de la carte

A partir de Java 8, il existe des méthodes par défaut sur l'interface Map.Entry pour permettre le tri des itérations de carte.

Map<String, Integer> numberOfEmployees = new HashMap<>();
numberOfEmployees.put("executives", 10);
numberOfEmployees.put("human ressources", 32);
numberOfEmployees.put("accounting", 12);
numberOfEmployees.put("IT", 100);

// Output the smallest departement in terms of number of employees
numberOfEmployees.entrySet().stream()
    .sorted(Map.Entry.comparingByValue())
    .limit(1)
    .forEach(System.out::println);   // outputs : executives=10

Bien sûr, ceux-ci peuvent également être utilisés en dehors du flux api:

List<Map.Entry<String, Integer>> entries = new ArrayList<>(numberOfEmployees.entrySet());
Collections.sort(entries, Map.Entry.comparingByValue());

Création d'un comparateur à l'aide de la méthode de comparaison

Comparator.comparing(Person::getName)

Cela crée un comparateur pour la classe Person qui utilise ce nom de personne comme source de comparaison. Il est également possible d'utiliser la version de méthode pour comparer long, int et double. Par exemple:

Comparator.comparingInt(Person::getAge)

Ordre inversé

Pour créer un comparateur qui impose la méthode d'inversion en ordre reversed() :

Comparator.comparing(Person::getName).reversed()

Chaîne de comparateurs

Comparator.comparing(Person::getLastName).thenComparing(Person::getFirstName)

Cela va créer un comparateur comparé au nom de famille avec le prénom. Vous pouvez enchaîner autant de comparateurs que vous le souhaitez.