Collection 03 : Set

Tu as vu précédemment comment ajouter et trier des éléments dans une List. C'est pratique, mais il y a un inconvénient : un élément sera forcément ajouté à une liste, même s'il est déjà présent. On se retrouve fatalement avec des doublons.

Il existe une interface pour pallier ce problème : Set !

Objectifs

• Savoir utiliser et parcourir un ensemble
• Créer un ensemble trié par ordre d'insertion
• Créer un ensemble trié par valeur

Set

Contrairement à une liste, un ensemble n'est pas ordonné : il ne faut pas imaginer cela comme un tableau, mais plus comme un tiroir dans lequel tu rangerais tes éléments.

La duplication n'est pas possible : si tu insères un élément déjà existant dans un ensemble, il ne se passera rien. C'est aussi valable pour la valeur null : un ensemble ne pourra la contenir qu'une seule fois !

Les ensembles sont représentés en Java par l'interface Set, qui hérite de Collection.

Comme dit précédemment, à la différence d'une List, les éléments ajoutés à un Set ne sont pas ordonnés : à l'ajout d'un élément, aucun index numérique ne lui est attribué.

Il existe plusieurs implémentations de l'interface Set, notamment :

• sans ordre défini, avec HashSet

• par ordre d'insertion, avec LinkedHashSet

• par ordre de valeur, avec TreeSet

HashSet

Si l'ordre des éléments importe peu, il est conseillé d'utiliser l'implémentation HashSet.

Pour créer un nouvel HashSet vide, tu vas devoir créer une instance de la classe et la stocker dans une référence :

HashSet<Food> lunch = new HashSet<>();

Un HashSet va fonctionner de façon presque identique à une ArrayList, avec comme avantage de ne pas pouvoir contenir d'élément dupliqué, mais comme inconvénient de ne pas posséder d'ordre.

Les méthodes sont sensiblement les mêmes que pour une ArrayList, avec comme différences notables :

1. Insertion

Food burger = new Food("Big Wac", 450);
Food fries = new Food("French fries", 275);
Food cheeseburger = new Food("Cheeseburger", 300);
Food sunday = new Food("Chocolate Sunday", 175);

HashSet<Food> lunch = new HashSet<>();
lunch.add(burger);
lunch.add(fries);
lunch.add(cheeseburger);

L'ajout d'un élément dans un ensemble retourne un booléen : il indique si l'élément a réellement été ajouté, ou non (dans le cas d'un doublon) :

boolean addSunday = lunch.add(sunday); // true
boolean addAgain = lunch.add(sunday); // false

2. Suppression

Un élément n'ayant pas d'indice dans un ensemble, tu ne peux le supprimer qu'avec l'objet d'origine en paramètre :

boolean removeBurger = lunch.remove(burger); // true
boolean removeAgain = lunch.remove(burger); // false

3. Parcours

Un ensemble n'ayant pas d'indice, tu ne peux le parcourir qu'avec une boucle for-earch :

HashSet<Food> lunch = new HashSet<>();
lunch.add(burger);
lunch.add(fries);
lunch.add(cheeseburger);
lunch.add(sunday);

for (Food food : lunch) {
    System.out.println(food.getName());
}

Attention : l'ordre de parcours des éléments n'est pas garanti !

$ Sunday
$ French fries
$ Big Wac
$ Cheeseburger

Performances

Tu dois donc te poser la question : quand le cas où limiter la duplication des objets n'est pas ta priorité, y a-t-il un intérêt à utiliser un HashSet ?

Ça dépend : c'est en fonction des performances. Lors des actions d'ajout et de suppression répétées dans une collection d'éléments :

• avec peu d'éléments, une ArrayList est plus performante qu'un HashSet

• au-delà de ce seuil, plus tu auras d'éléments, plus un HashSet sera performant face à une ArrayList

_Credit _Jeff Bridgman

Tu trouveras en ressource le détail de la procédure.

Si tu ne dois pas parcourir ta collection d'éléments dans un ordre spécifique et que tu as régulièrement des actions d'ajout et de suppression : utilise un HashSet !

LinkedHashSet

Un ensemble LinkedHashSet permet toujours d'éviter la duplication, mais permet aussi de trier les éléments par ordre d'insertion.

Ainsi, si l'on ajoute des éléments dans un ensemble et que l'on parcourt ensuite ce dernier, l'itération se fera par ordre du premier au dernier élément ajouté.

LinkedHashSet<Food> lunch = new LinkedHashSet<>();
lunch.add(burger);
lunch.add(fries);
lunch.add(cheeseburger);
lunch.add(sunday);

for (Food food : lunch) {
    System.out.println(food.getName());
}

Cette fois l'ordre sera garanti :

$ Big Wac
$ French fries
$ Cheeseburger
$ Sunday

Supprimer un élément d'un LinkedHashSet ne modifiera pas l'ordre d'origine (l'élément supprimé en moins, forcément !).

Bien que les éléments soient triés par ordre d'insertion, ils n'ont pas d'index attribués. Chaque élément connait celui qui le précède et celui qui lui succède directement, mais il ne connait pas sa place dans la chaîne.

TreeSet

Un ensemble TreeSet permet, quant à lui, de trier les éléments par valeur.

Si tu essaies de stocker puis de parcourir les éléments Food contenus dans un TreeSet :

TreeSet<Food> lunch = new TreeSet<>();  
lunch.add(burger);  
lunch.add(fries);  
lunch.add(cheeseburger);  
lunch.add(sunday);  

for (Food food : lunch) { // iterate though the list  
  System.out.println(food.getName());  
}

Tu vas obtenir l'erreur suivante :

class Food cannot be cast to class java.lang.Comparable 

En effet : tu n'as jamais précisé comment les éléments devaient être triés !

Afin d'utiliser un TreeSet, il faut que ta classe d'éléments implémente Comparable.

Voici une implémentation permettant de trier les éléments par ordre alphabétique sur le nom :

public class Food implements Comparable<Food> {  

    @Override  
    public int compareTo(Food food) {  
        return this.getName().compareTo(food.getName());  
    }

    //...
}

Ainsi, le résultat du parcours sera :

$ Big Wac
$ Cheeseburger
$ Chocolate Sunday
$ French fries

Inutile d'utiliser la méthode sort avec un TreeSet : les éléments sont triés par défaut !

La classe TreeSet contient quelques méthodes supplémentaires, par exemple :

1. first() and last()

Permettent de récupérer respectivement le premier et le dernier élément d'un ensemble :

Food first = lunch.first();  
Food last = lunch.last();

boolean containFirst = lunch.contains(first); // true
boolean containLast = lunch.contains(last); // true

2. pollFirst() and pollLast()

Permettent de récupérer et de retirer les premier et dernier éléments d'un ensemble :

Food first = lunch.pollFirst();
Food last = lunch.pollLast();

boolean containFirst = lunch.contains(first); // false
boolean containLast = lunch.contains(last); // false

3. descendingSet()

Permet de parcourir un ensemble en sens inverse :

for (Food food : lunch.descendingSet()) { 
    System.out.println(food.getName());
}

4. subSet(E fromElement, E toElement)

Retourne un sous-ensemble d'éléments, compris entre fromElement (inclus) et toElement (non inclus).

Il est possible de décider de l'inclusion ou non des premier et dernier éléments, grâce à la surcharge de la méthode : subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

La sélection se fait sur l'implémentation de Comparable. Dans notre exemple, les éléments sont triés par noms : tu vas donc sélectionner les éléments compris entre le nom de départ (compris) et le nom d'arrivée (non compris) :

TreeSet<Food> lunch = new TreeSet<>();
lunch.add(burger);
lunch.add(fries);
lunch.add(cheeseburger);
lunch.add(sunday);
// lunch order : ["Big Wac", "Cheeseburger", "Chocolate Sunday", "French fries"]  

for (Food food : lunch.subSet(cheeseburger, fries)) {  
    System.out.println(food.getName());  
}

Les éléments par ordre alphabétique de noms, entre cheeseburger (compris) et fries (non compris) sont :

$ Cheeseburger
$ Chocolate Sunday

Challenge

Avengers : Pre-Sequel Part.1

Thanos aime tellement faire des statistiques inutiles qu'il en vient à manquer d'inspiration. Heureusement, il découvre les ensembles ! Il décide de bidouiller encore une fois son Gant de l'infini, afin d'y attacher cette nouvelle fonctionnalité.

Pour démarrer, fais un Fork du dépôt suivant puis clone-le en local.

Pense bien à faire un Fork, sinon tu ne pourras rien pousser !

Thanos possède un TreeSet de Heroes, implémentant Comparable avec un tri par age croissant.

1. En une seule ligne, récupère et supprime le héros le plus vieux de l'ensemble
2. Sans modifier l'ensemble d'origine, affiche la liste des héros par âge décroissant
3. Sans modifier l'ensemble d'origine, affiche la liste des héros par âge croissant, allant de Spider-Man (compris) à Iron Man (compris)

Résultat attendu lors de l'exécution de Thanos :

$ Oldest hero:
$ Thor
$ 
$ Heroes by age (descending) :
$ Captain America, 100
$ Hulk, 49
$ Doctor Strange, 42
$ Black Widow, 34
$ Scarlet Witch, 29
$ Vision, 3
$ 
$ Subset of heroes :
$ Spider-Man, 18
$ Scarlet Witch, 29
$ Black Widow, 34
$ Doctor Strange, 42
$ Iron Man, 48

Critères de validation

• Le dépôt GitHub contient bien les fichiers Hero.java et Thanos.java
• Seule la classe Thanos doit être modifiée
• La classe Thanos se compile sans erreur et affiche dans le terminal un résultatidentique à celui présenté précédemment