Java

Java Reskilling Data-Structures 01: Comparable and Comparators

Quête 29 sur 43 · 2 images archivées

FrançaisEnglish (original)

Structures de données Java : Comparable et Comparator

Dans les quêtes sur les structures de données Java de base, tu apprends à partir d'exemples tirés du domaine de notre application d'exemple Tariff-Manager.

Dans la vie, il y a deux sortes de listes : celles qui sont triées, et celles qui ne le sont pas. Dans cette quête, tu vas découvrir comment trier une liste de clients de Tariff-Manager en Java.

🤓 À la fin de cette quête, tu sauras :

✅ Comment trier une liste d'éléments ✅ Comment implémenter l'interface Comparable (interface qui définit comment un objet se compare à un autre) ✅ Comment implémenter Comparator (classe externe qui définit une stratégie de comparaison) pour différentes stratégies de comparaison ✅ Comprendre les différences entre l'usage de Comparable et de Comparator

👀 Contenu de la quête

Comparer des objets
Comparer avec Comparable
Comparer avec Comparator
Comparer les stratégies de comparaison
Lambdas et références de méthode

Comparer des objets

Pour tous nos exemples, nous utiliserons la classe Customer que tu connais déjà. Elle a plusieurs attributs, mais nous l'avons réduite à seulement deux attributs pour les besoins de ces exemples de tri :

java

class Customer {    
 
    private String name;
    private LocalDate birthDate;
    
}

Ces deux attributs sont de type String et de type LocalDate. Pour String, le tri naturel est lexical, pour LocalDate il est séquentiel.

Nous allons voir comment des objets Customer peuvent être triés par l'un ou l'autre attribut, voire par les deux.

Mettre en place une liste de clients

java

Customer joe = new Customer("Average Joe", LocalDate.now().minusYears(45));
Customer cat = new Customer("Chatty Cathy", LocalDate.now().minusYears(25));
Customer deb = new Customer("Debbie Downer", LocalDate.now().minusYears(37));
Customer sue = new Customer("Gloomy Gus", LocalDate.now().minusYears(58));
Customer sim = new Customer("Simple Simon", LocalDate.now().minusYears(19));

List<Customer> market = new ArrayList<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(sue);
market.add(sim);

Si nous voulons trier cette List, Collections.sort (méthode qui prend une liste d'objets et la trie) est notre candidate. Elle prend une liste d'objets et la trie. Essayons.

java

Collections.sort(market);
System.out.println("Sorted Customers: " + market);

Pourtant, ça ne va pas marcher, tu obtiendras une erreur à la compilation :

The method sort(List<T>) in the type Collections 
  is not applicable for the arguments (ArrayList<Customer>)

Pourquoi ça ne compile pas ? Il semble qu'il manque quelque chose dans notre liste ou dans les objets qu'elle contient.

Utiliser `Comparable` pour comparer des objets

Comparable est une interface qui définit une stratégie pour comparer des objets de la classe qui l'implémente. La stratégie est définie dans la méthode int compareTo(TYPE that) (méthode qui compare l'objet courant avec l'objet passé en paramètre) qui doit se comparer elle-même avec l'objet du même type passé en paramètre.

La façon dont la comparaison est implémentée est précisée dans la méthode et ne fait pas partie de l'interface (le contrat), mais le résultat doit être :

-1 (ou < 0) pour plus petit
0 pour égal
1 (ou > 0) pour plus grand

de l'objet this par rapport à l'objet that.

Exemple de comparaison de Customer

Pour pouvoir trier avec la méthode Collections.sort(...), nous devons définir notre objet Customer comme comparable en implémentant l'interface Comparable et la méthode compareTo :

java

public class Customer implements Comparable<Customer> {

    @Override
    public int compareTo(Customer that) {
        return this.getName().compareTo(that.getName());
    }

}

Dans ce cas, la stratégie de comparaison consiste à déléguer au compareTo(...) de String avec l'attribut name. Quand compareTo est appelée avec l'"autre" objet that, le name de l'objet this est comparé au name de cet objet.

Pour comparer ces noms, on utilise l'ordre naturel du type String, qui implémente lui-même Comparable<String> et précise une méthode compareTo(String...) qui ordonne les String (par ordre alphanumérique).

Comparer avec `Comparable`

Supposons que nous prenions ces deux clients et que nous voulions les comparer :

java

Customer joe = new Customer("Average Joe");
Customer cat = new Customer("Chatty Cathy");
List customers = List.of(joe, cat);

Maintenant, nous voulons comparer Joe et Cathy.

java

int result = joe.compareTo(cat);

if (result == 0) {
    System.out.println("The Objects 'joe' and 'cat' are equal.");
} else if (result < 0) {
    System.out.println("The Objects 'joe' is smaller than 'cat'.");
} else {
    System.out.println("The Objects 'joe' is bigger than 'cat'.");
}

// Result: "The Objects 'joe' is smaller than 'cat'." 
// as "Average Joe" < "Chatty Cathy" lexically.

Notre appel est délégué à "Average Joe".compareTo("Chatty Cathy") qui renvoie -1 car l'ordre lexical de "A..." est plus petit que celui de "C...".

Comparer avec `Comparator`

Comme ci-dessus, supposons que nous prenions ces deux clients et que nous voulions les comparer :

java

Customer joe = new Customer("Average Joe");
Customer cat = new Customer("Chatty Cathy");
List customers = List.of(joe, cat);

Ces objets Customer sont des Plain Old Java Objects (POJO : objets Java tout simples, qui n'ont que des getters et des setters), ce qui veut dire qu'ils ne précisent rien de plus que les getters et les setters. Ils n'implémentent pas Comparable.

À la place, nous créons des classes séparées qui sont responsables de l'ordonnancement des objets Customer. Nous allons utiliser les Generics (génériques : permettent de préciser le type d'objet concerné) pour indiquer que la nouvelle classe est responsable des objets Customer et ne peut pas être utilisée pour des objets d'autres types.

Ici tu vois l'implémentation d'une classe anonyme (anonymous class : classe qui est créée et instanciée en même temps). Cette classe est créée et instanciée en même temps, puis affectée à la variable nameComparator.

java

Comparator<Customer> nameComparator = new Comparator<> {
    @Override
    public int compare(Customer o1, Customer o2) {
        return o1.getName().compareTo(o2.getName());
    }    
};

Maintenant, nous voulons comparer Joe et Cathy.

java

int result = nameComparator.compare(joe, cat);

if (result == 0) {
    System.out.println("The Objects 'joe' and 'cat' are equal.");
} else if (result < 0) {
    System.out.println("The Objects 'joe' is smaller than 'cat'.");
} else {
    System.out.println("The Objects 'joe' is bigger than 'cat'.");
}

// Result: "The Objects 'joe' is smaller than 'cat'." 
// as "Average Joe" < "Chatty Cathy" lexically.

La grande différence avec l'exemple utilisant Comparable est la comparaison "externe" faite par le nameComparator. Dans ce cas, la stratégie de comparaison des objets Customer est externalisée et n'est pas incluse dans les objets eux-mêmes. Cela a des avantages et des inconvénients, et il est important de bien le comprendre.

Avec Comparator, la stratégie de comparaison d'objets d'un certain type est séparée de l'objet lui-même.

Mais dans ce cas aussi, notre appel est délégué à "Average Joe".compareTo("Chatty Cathy") qui renvoie -1 car l'ordre lexical de "A..." est plus petit que celui de "C...".

Comparer les stratégies de comparaison

Nous avons vu deux stratégies différentes pour comparer des objets : l'une définie dans l'objet lui-même en implémentant Comparable, et l'autre qui définit une stratégie de comparaison indépendante de l'objet lui-même avec Comparator.

Tu devrais utiliser :

Comparable pour définir l'ordre par défaut qui est "naturel" à l'objet, par exemple name pour les clients.
Comparator si tu ne peux pas ou ne veux pas modifier la classe elle-même. Si quelqu'un t'a donné la classe Customer et que tu ne dois pas ou ne peux pas la modifier, tu dois utiliser un Comparator externe.
Comparator pour définir une stratégie de comparaison indépendante de la classe elle-même, ce qui mène à un code propre.
Comparator pour définir plusieurs stratégies de comparaison différentes, ce qui n'est pas possible avec Comparable.

Lambdas et références de méthode

Avec la version 8, Java a introduit les expressions lambda (lambda : écriture courte d'une fonction) et les références de méthode (method reference : façon de pointer directement vers une méthode existante), qui simplifient beaucoup la création d'implémentations d'interfaces fonctionnelles (functional interface : interface avec une seule méthode abstraite, comme celle utilisée pour Comparator).

Pour notre exemple avec la classe anonyme, avec les expressions lambda c'est plus simple, plus facile à lire et à comprendre :

java

Comparator nameComparator = 
  (Customer customer1, Customer customer2) -> 
    customer1.getName().compareTo(customer2.getName()));

La méthode Comparator.comparing prend une référence de méthode pour l'attribut à utiliser pour la comparaison et renvoie une instance de Comparator correspondante :

java

Comparator<Customer> byName = Comparator.comparing(Customer::getName);
Comparator<Customer> byBirthdate = Comparator.comparing(Customer::getBirthdate);

🔬Exercice

Les Comparator peuvent aussi être chaînés. Cela veut dire qu'une collection peut être triée d'abord par un attribut, puis, pour les éléments qui sont égaux sur cet attribut, par un autre attribut, et ainsi de suite. La collection obtenue peut aussi être inversée.

Clone le dépôt Tariff-Manager, bascule sur la branche block_2_complete et regarde le test unitaire CustomerComparisonTest.shouldImplementAllOptionsForComparator. Tu verras un exemple qui utilise

java

Collections.sort(customers, birthdayComparator.reversed())

qui inverse le premier Comparator triant par birthdate, c'est-à-dire que le résultat sera une liste triée par date de naissance, mais en ordre décroissant (l'ordre croissant étant celui par défaut).

En utilisant le même mécanisme de chaînage de méthodes, tu dois écrire un Comparator pour Customer avec trois implémentations différentes : classe anonyme, lambda et référence de méthode, pour trier d'abord par names, puis par birthdate, les deux en ordre croissant, et enfin en inversant la collection obtenue.

hidden

Reveal implementation options for Comparator (name, birthday).reverse|||java||||||1|||
// Option 1: With Anonymous Classes
Comparator<SortableCustomer> nameComparator = new Comparator<SortableCustomer>() {
    @Override
    public int compare(SortableCustomer o1, SortableCustomer o2) {
        return o1.getName().compareTo(o2.getName());
    }
};

Comparator<SortableCustomer> birthdateComparator = new Comparator<SortableCustomer>() {
    @Override
    public int compare(SortableCustomer o1, SortableCustomer o2) {
        return o1.getBirthdate().compareTo(o2.getBirthdate());
    }
};

// combine the Comparators
Comparator<SortableCustomer> firstNamesThenBirthdateThenReverseAnon = nameComparator.thenComparing(birthdateComparator).reversed();
Collections.sort(customers, firstNamesThenBirthdateThenReverseAnon);
assertThat(customers).containsSequence(sim, cat, joe2, joe3, joe1);

// Option 2: with lambdas
Comparator<SortableCustomer> namesLambda = (c1, c2) -> (c1.getName().compareTo(c2.getName()));
Comparator<SortableCustomer> birthdateLambda = (c1, c2) -> (c1.getName().compareTo(c2.getName()));
Comparator<SortableCustomer> firstNamesThenBirthdateThenReverseLambda = namesLambda.thenComparing(birthdateLambda).reversed();
Collections.sort(customers, firstNamesThenBirthdateThenReverseLambda);
assertThat(customers).containsSequence(sim, cat, joe2, joe3, joe1);

// Option 3: with Method References
Comparator<SortableCustomer> firstNamesThenBirthdateThenReverseRef = Comparator.comparing(SortableCustomer::getName).thenComparing(SortableCustomer::getBirthdate).reversed();
Collections.sort(customers, firstNamesThenBirthdateThenReverseRef);
assertThat(customers).containsSequence(sim, cat, joe2, joe3, joe1);

Challenge

C'est un challenge de type quiz.

Références

Photo de Heather Ford sur Unsplash

Java Data-Structures: Comparable and Comparators

In the quests about basic Java Data-Structures you will learn with examples from the domain of our sample application Tariff-Manager.

In life, there are two kinds of lists: those that are sorted, and those that are not. In this quest, you will discover how to sort a list of Tariff-Manager customers in Java.

🤓 By the end of this quest, you will:

✅ Know how to sort a list of items ✅ Know how to implement the Comparable interface ✅ Know how to implement Comparator for different comparison strategies ✅ Understand the differences between using Comparable and Comparator

👀 Content of the quest

Comparing Objects
Comparing with Comparable
Comparing with Comparator
Comparing Comparison Strategies
Lambdas & Method References

Comparing Objects

Our class for all samples with be the already known Customer class. It has several attributes, we stripped it down to just two attributes for the sake of these sorting examples:

java

class Customer {    
 
    private String name;
    private LocalDate birthDate;
    
}

These two attributes are of type String and of type LocalDate. For String the natural sorting is lexically, for LocalDate it is sequentially.

We will see how Customer objects can be sorted by either attribute or even by both.

Setup a List of Customers

java

Customer joe = new Customer("Average Joe", LocalDate.now().minusYears(45));
Customer cat = new Customer("Chatty Cathy", LocalDate.now().minusYears(25));
Customer deb = new Customer("Debbie Downer", LocalDate.now().minusYears(37));
Customer sue = new Customer("Gloomy Gus", LocalDate.now().minusYears(58));
Customer sim = new Customer("Simple Simon", LocalDate.now().minusYears(19));

List<Customer> market = new ArrayList<>();
market.add(joe);
market.add(cat);
market.add(deb);
market.add(sue);
market.add(sim);

If we want to sort this List, Collections.sort is our candidate. It takes a list of objects and sorts it. Let's try.

java

Collections.sort(market);
System.out.println("Sorted Customers: " + market);

However, this won't work, you will get a compile-time error:

The method sort(List<T>) in the type Collections 
  is not applicable for the arguments (ArrayList<Customer>)

Why does this not compile? There seems to be something missing in our list or the objects inside.

Using `Comparable` for Object Comparisons

Comparable is an interface which defines a strategy for comparing objects of the class implementing it. The strategy is defined in the method int compareTo(TYPE that) which has to compare itself with the passed-in object of the same type.

How the comparison is implemented is specified in the method and not part of the interface (contract), but the result must be

-1 (or < 0) for smaller
0 for equal
1 (or > 0) for bigger

of this object in comparison to that object.

Sample for Customer Comparisons

In order to be able to sort using the Collections.sort(...) method, we must define our Customer object as comparable by implementing the Comparable interface and the compareTo method:

java

public class Customer implements Comparable<Customer> {

    @Override
    public int compareTo(Customer that) {
        return this.getName().compareTo(that.getName());
    }

}

In this case, the strategy for comparing is delegating to compareTo(...) of String with the attribute name. When compareTo is called with the "other" object that, this objects name is compared to that objects name.

To compare these names, the natural order of type String is used, which itself implements Comparable<String> and specifies a compareTo(String...) method which orders Strings (alphanummerically).

Comparing with `Comparable`

Let's assume we take these two customers and want to compare them:

java

Customer joe = new Customer("Average Joe");
Customer cat = new Customer("Chatty Cathy");
List customers = List.of(joe, cat);

Now we want to compare Joe and Cathy.

java

int result = joe.compareTo(cat);

if (result == 0) {
    System.out.println("The Objects 'joe' and 'cat' are equal.");
} else if (result < 0) {
    System.out.println("The Objects 'joe' is smaller than 'cat'.");
} else {
    System.out.println("The Objects 'joe' is bigger than 'cat'.");
}

// Result: "The Objects 'joe' is smaller than 'cat'." 
// as "Average Joe" < "Chatty Cathy" lexically.

Our call is delegated to "Average Joe".compareTo("Chatty Cathy") which returns -1 as the lexical order of "A..." is smaller than "C...".

Comparing with `Comparator`

Same as above, let's assume we take these two customers and want to compare them:

java

Customer joe = new Customer("Average Joe");
Customer cat = new Customer("Chatty Cathy");
List customers = List.of(joe, cat);

These Customer objects are Plain Old Java Objects, this means they don't have more specified than the Getters and Setters. They do not implement Comparable.

Instead, we are creating seperate classes which are responsible for ordering Customer objects. We will use Generics to state that the new class is responsible for Customer objects and cannot be used for objects of other types.

Here you see the implementation of an anonymous class. This class is created and instantiated at the same time and assigned to the variable nameComparator.

java

Comparator<Customer> nameComparator = new Comparator<> {
    @Override
    public int compare(Customer o1, Customer o2) {
        return o1.getName().compareTo(o2.getName());
    }    
};

Now we want to compare Joe and Cathy.

java

int result = nameComparator.compare(joe, cat);

if (result == 0) {
    System.out.println("The Objects 'joe' and 'cat' are equal.");
} else if (result < 0) {
    System.out.println("The Objects 'joe' is smaller than 'cat'.");
} else {
    System.out.println("The Objects 'joe' is bigger than 'cat'.");
}

// Result: "The Objects 'joe' is smaller than 'cat'." 
// as "Average Joe" < "Chatty Cathy" lexically.

The huge difference to the sample with Comparable is the "external" comparison by the nameComparator. In this case, the strategy for comparing Customer objects is externalized and not included in the objects itself. This has some advantages and disadvantages and it is important to understand.

With Comparator, the strategy for comparing objects or some type is seperated form the object itself.

But also in this case, our call is delegated to "Average Joe".compareTo("Chatty Cathy") which returns -1 as the lexical order of "A..." is smaller than "C...".

Comparing Comparison Strategies

We saw two different strategies for comparing objects, one which is defined in the object itself by implementing Comparable and one which defines a comparison strategy independent of the object itself with Comparator.

You should use:

Comparable to define the default ordering which is "natural" to the object, eg. name for customers.
Comparator if you can't or don't want to change the class itself. If someone gave you the class Customer and you should not or can not change it, you have to use an external Comparator.
Comparator to define a strategy for comparing independent of the class itself which leads to clean code.
Comparator for defining multiple different comparison strategies, which isn't possible when using Comparable.

Lambdas & Method References

With version 8 Java introduced lambda expressions and method references which simplify creating implementation of functional interfaces (which we use for Comparator) a lot.

For our example with the anonymous class, with lambda expressions this is simpler and easier to read and understand:

java

Comparator nameComparator = 
  (Customer customer1, Customer customer2) -> 
    customer1.getName().compareTo(customer2.getName()));

The Comparator.comparing method takes a method reference for the attribute to be used for comparing and returns a matching Comparator instance:

java

Comparator<Customer> byName = Comparator.comparing(Customer::getName);
Comparator<Customer> byBirthdate = Comparator.comparing(Customer::getBirthdate);

🔬Exercise

Comparators can also be chained. This means a collection can be sorted by some attribute first and for the elements which are equal for this attribute, for another attribute as well, and so on. The resulting collection can also be reversed.

Clone the repo Tariff-Manager, switch to branch block_2_complete and look into unit test CustomerComparisonTest.shouldImplementAllOptionsForComparator. You will see an example using

java

Collections.sort(customers, birthdayComparator.reversed())

which reverses the first Comparator which sorts for birthdate, ie. the result will be a list sorted by birthdate, but descending (with ascending being the default).

Using the same mechanism of method chaining, you should write a Comparator for Customer with three different implementations: anonymous class, lambda, and method reference for sorting names first, then birthdate, both ascending, and then finally reversing the resulting collection.

hidden

Reveal implementation options for Comparator (name, birthday).reverse|||java||||||1|||
// Option 1: With Anonymous Classes
Comparator<SortableCustomer> nameComparator = new Comparator<SortableCustomer>() {
    @Override
    public int compare(SortableCustomer o1, SortableCustomer o2) {
        return o1.getName().compareTo(o2.getName());
    }
};

Comparator<SortableCustomer> birthdateComparator = new Comparator<SortableCustomer>() {
    @Override
    public int compare(SortableCustomer o1, SortableCustomer o2) {
        return o1.getBirthdate().compareTo(o2.getBirthdate());
    }
};

// combine the Comparators
Comparator<SortableCustomer> firstNamesThenBirthdateThenReverseAnon = nameComparator.thenComparing(birthdateComparator).reversed();
Collections.sort(customers, firstNamesThenBirthdateThenReverseAnon);
assertThat(customers).containsSequence(sim, cat, joe2, joe3, joe1);

// Option 2: with lambdas
Comparator<SortableCustomer> namesLambda = (c1, c2) -> (c1.getName().compareTo(c2.getName()));
Comparator<SortableCustomer> birthdateLambda = (c1, c2) -> (c1.getName().compareTo(c2.getName()));
Comparator<SortableCustomer> firstNamesThenBirthdateThenReverseLambda = namesLambda.thenComparing(birthdateLambda).reversed();
Collections.sort(customers, firstNamesThenBirthdateThenReverseLambda);
assertThat(customers).containsSequence(sim, cat, joe2, joe3, joe1);

// Option 3: with Method References
Comparator<SortableCustomer> firstNamesThenBirthdateThenReverseRef = Comparator.comparing(SortableCustomer::getName).thenComparing(SortableCustomer::getBirthdate).reversed();
Collections.sort(customers, firstNamesThenBirthdateThenReverseRef);
assertThat(customers).containsSequence(sim, cat, joe2, joe3, joe1);

Challenge

This is a quizz challenge.

References

Photo by Heather Ford on Unsplash

Structures de données Java : Comparable et Comparator

🤓 À la fin de cette quête, tu sauras :

👀 Contenu de la quête

Comparer des objets

Mettre en place une liste de clients

Utiliser Comparable pour comparer des objets

Exemple de comparaison de Customer

Comparer avec Comparable

Comparer avec Comparator

Comparer les stratégies de comparaison

Lambdas et références de méthode

🔬Exercice

Challenge

Références

Java Data-Structures: Comparable and Comparators

🤓 By the end of this quest, you will:

👀 Content of the quest

Comparing Objects

Setup a List of Customers

Using Comparable for Object Comparisons

Sample for Customer Comparisons

Comparing with Comparable

Comparing with Comparator

Comparing Comparison Strategies

Lambdas & Method References

🔬Exercise

Challenge

References

Utiliser `Comparable` pour comparer des objets

Comparer avec `Comparable`

Comparer avec `Comparator`

Using `Comparable` for Object Comparisons

Comparing with `Comparable`

Comparing with `Comparator`