NavigableSet/NavigableMap

1. Introduction

La bibliothèque standard de Java propose de nombreuses collections, mais lorsqu’il s’agit de plages, de recherche d’éléments « proches », de priorisation et de gestion de créneaux horaires, les interfaces NavigableSet et NavigableMap entrent en scène.

NavigableSet étend SortedSet, en ajoutant des méthodes pour rechercher des éléments par rapport à une valeur donnée (plus petit, plus grand, le plus proche, etc.), ainsi que pour travailler avec des plages.
NavigableMap étend SortedMap, en ajoutant des méthodes similaires pour la recherche par clefs et le travail avec des plages.

Implémentations les plus connues : TreeSet et TreeMap.

Quand utiliser NavigableSet/NavigableMap ?

• Quand il est important non seulement de stocker des éléments/clefs uniques dans l’ordre trié, mais aussi de trouver rapidement les « voisins » (par exemple, le créneau libre le plus proche, la tâche prioritaire, une plage de valeurs).
• Quand il faut travailler avec des plages : « tous les éléments entre X et Y », « toutes les clefs supérieures/inférieures à une valeur donnée », « trouver la clef la plus proche ».

2. Plages : subSet, headSet, tailSet

Méthodes pour travailler avec des plages

NavigableSet et NavigableMap permettent d’obtenir des représentations « live » (view) de sous-ensembles de la collection :

• subSet(fromElement, fromInclusive, toElement, toInclusive) — les éléments dans la plage [fromElement; toElement], inclus/exclus.
• headSet(toElement, inclusive) — tous les éléments inférieurs (ou inférieurs ou égaux) à toElement.
• tailSet(fromElement, inclusive) — tous les éléments supérieurs (ou supérieurs ou égaux) à fromElement.

Exemple :

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

// Plage de 15 (inclus) à 45 (exclus)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

// Tous les éléments <= 30
NavigableSet<Integer> head = set.headSet(30, true); // [10, 20, 30]

// Tous les éléments > 20
NavigableSet<Integer> tail = set.tailSet(20, false); // [30, 40, 50]

Inclusivité / exclusivité :

• true — inclus (l’élément appartient à la plage)
• false — exclus (l’élément n’y appartient pas)

Pour NavigableMap, les méthodes sont analogues, mais s’appliquent aux clefs.

3. Opérations sur les valeurs voisines : floor, ceiling, lower, higher ; pollFirst/Last

Recherche des éléments les plus proches

NavigableSet :

• lower(E e) — plus grand élément < e (strictement inférieur)
• floor(E e) — plus grand élément ≤ e (inférieur ou égal)
• ceiling(E e) — plus petit élément ≥ e (supérieur ou égal)
• higher(E e) — plus petit élément > e (strictement supérieur)

Exemple :

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

System.out.println(set.lower(30));   // 20
System.out.println(set.floor(30));   // 30
System.out.println(set.ceiling(25)); // 30
System.out.println(set.higher(40));  // 50

pollFirst() / pollLast()

• pollFirst() — supprime et renvoie le plus petit élément (ou null si vide)
• pollLast() — supprime et renvoie le plus grand élément

Exemple :

System.out.println(set.pollFirst()); // 10
System.out.println(set.pollLast());  // 50
System.out.println(set);             // [20, 30, 40]

NavigableMap : méthodes analogues pour les clefs — lowerKey, floorKey, ceilingKey, higherKey, ainsi que pollFirstEntry, pollLastEntry.

4. Vues : descendingSet/descendingMap ; vues (« view ») et leur caractère « vivant »

Ordre inverse : descendingSet/descendingMap

• descendingSet() — renvoie une représentation de l’ensemble dans l’ordre inverse.
• descendingMap() — renvoie une représentation de la map dans l’ordre inverse des clefs.

Exemple :

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> desc = set.descendingSet();
System.out.println(desc); // [50, 40, 30, 20, 10]

Important : ce n’est pas une copie, mais une vue « live » (view) des mêmes données. Les modifications de l’un se reflètent dans l’autre.

Vues (view) et leur caractère « vivant »

• Les méthodes subSet, headSet, tailSet, descendingSet, descendingMap renvoient une view — une représentation « vivante » de la collection d’origine.
• Toute modification dans la view se reflète dans la collection d’origine et inversement.
• Si vous supprimez un élément depuis subSet — il disparaîtra aussi de l’ensemble d’origine.

Exemple :

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> sub = set.subSet(20, true, 40, true); // [20, 30, 40]
sub.remove(30);
System.out.println(set); // [10, 20, 40, 50]

Attention : si vous modifiez la collection d’origine de sorte qu’un élément « sorte » de la plage de la view, au prochain accès à la view vous obtiendrez une ConcurrentModificationException.

5. Cas d’utilisation de NavigableSet/NavigableMap

1. Créneaux horaires / planning

Objectif : trouver le créneau horaire libre le plus proche pour un rendez-vous.

NavigableSet<LocalTime> slots = new TreeSet<>(List.of(
    LocalTime.of(9, 0),
    LocalTime.of(10, 0),
    LocalTime.of(11, 0),
    LocalTime.of(14, 0)
));

LocalTime requested = LocalTime.of(10, 30);
LocalTime nextSlot = slots.ceiling(requested); // 11:00
System.out.println("Heure la plus proche: " + nextSlot);

2. Priorisation (file à priorité)

Objectif : toujours récupérer rapidement l’élément avec la priorité la plus haute/la plus basse.

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("E-mail", 2));
tasks.add(new Task("Appel", 1));
tasks.add(new Task("Rapport", 3));

Task next = tasks.pollFirst(); // Tâche avec la priorité la plus élevée (1)

3. « Clé la plus proche » (par exemple pour rechercher une plage dans une Map)

Objectif : trouver une plage de valeurs par clef, ou la clef la plus proche.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Insuffisant");
grades.put(65, "Satisfaisant");
grades.put(75, "Bien");
grades.put(85, "Excellent");

int score = 78;
int key = grades.floorKey(score); // 75
System.out.println("Note: " + grades.get(key)); // Bien

6. Pratique : mini-exemples

Exemple 1 : Plage de dates

NavigableSet<LocalDate> holidays = new TreeSet<>(List.of(
    LocalDate.of(2024, 1, 1),
    LocalDate.of(2024, 5, 1),
    LocalDate.of(2024, 12, 31)
));
LocalDate from = LocalDate.of(2024, 1, 1);
LocalDate to = LocalDate.of(2024, 6, 1);
NavigableSet<LocalDate> spring = holidays.subSet(from, true, to, false);
System.out.println(spring); // [2024-01-01, 2024-05-01]

Exemple 2 : Recherche de la valeur la plus proche

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Inférieur: " + numbers.lower(x));              // 20
System.out.println("Inférieur ou égal: " + numbers.floor(x));    // 20
System.out.println("Supérieur ou égal: " + numbers.ceiling(x));  // 30
System.out.println("Supérieur: " + numbers.higher(x));             // 30

7. Erreurs courantes et subtilités

Erreur n° 1 : Confusion entre inclusivité/exclusivité dans subSet/headSet/tailSet.
Vérifiez toujours attentivement les paramètres inclusive — par défaut, dans les anciennes versions de Java les plages étaient exclusives ; dans NavigableSet/NavigableMap vous pouvez préciser explicitement inclusif/exclusif.

Erreur n° 2 : Penser que la view est une copie.
Une view est une représentation « vivante », pas une copie ! Les modifications dans la view se reflètent dans la collection d’origine.

Erreur n° 3 : ConcurrentModificationException lors de la modification de la collection d’origine en dehors de la view.
Si vous modifiez la collection d’origine de sorte qu’un élément « sorte » de la plage de la view, au prochain accès à la view vous obtiendrez une exception.

Erreur n° 4 : Utiliser NavigableSet/NavigableMap sans Comparable ou Comparator.
Ces collections exigent que les éléments (ou les clefs) soient comparables (Comparable) ou qu’un Comparator soit fourni. Sinon, vous obtiendrez une ClassCastException.

Erreur n° 5 : Penser que pollFirst/pollLast ne modifient pas la collection.
Ces méthodes suppriment des éléments ! Si vous voulez seulement consulter — utilisez first()/last().