NavigableSet/NavigableMap

1. Einführung

Die Standardbibliothek von Java bietet viele Collections, aber wenn es um Bereiche, die Suche nach „nächsten“ Elementen, Priorisierung und die Arbeit mit Zeitslots geht, kommen die Schnittstellen NavigableSet und NavigableMap ins Spiel.

NavigableSet erweitert SortedSet und fügt Methoden hinzu, um Elemente relativ zu einem gegebenen Wert zu finden (kleiner, größer, nächstgelegen usw.) sowie um mit Bereichen zu arbeiten.
NavigableMap erweitert SortedMap und bietet ähnliche Methoden für die Suche nach Schlüsseln und die Arbeit mit Bereichen.

Die bekanntesten Implementierungen: TreeSet und TreeMap.

Wann benötigt man NavigableSet/NavigableMap?

• Wenn es nicht nur wichtig ist, eindeutige Elemente/Schlüssel in sortierter Reihenfolge zu speichern, sondern auch schnell „Nachbarelemente“ zu finden (z. B. den nächstfreien Termin, eine priorisierte Aufgabe, einen Wertebereich).
• Wenn man mit Bereichen arbeiten muss: „alle Elemente zwischen X und Y“, „alle Schlüssel größer/kleiner als der gegebene“, „den nächstgelegenen Schlüssel finden“.

2. Bereiche: subSet, headSet, tailSet

Methoden zum Arbeiten mit Bereichen

NavigableSet und NavigableMap ermöglichen „lebende“ Sichten (View) auf Teilmengen der Collection:

• subSet(fromElement, fromInclusive, toElement, toInclusive) – Elemente im Bereich [fromElement; toElement], jeweils einschließlich/ausschließlich.
• headSet(toElement, inclusive) – alle Elemente kleiner (oder kleiner bzw. gleich) toElement.
• tailSet(fromElement, inclusive) – alle Elemente größer (oder größer bzw. gleich) fromElement.

Beispiel:

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

// Bereich von 15 (einschließlich) bis 45 (ausschließlich)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

// Alle Elemente <= 30
NavigableSet<Integer> head = set.headSet(30, true); // [10, 20, 30]

// Alle Elemente > 20
NavigableSet<Integer> tail = set.tailSet(20, false); // [30, 40, 50]

Einschluss/Ausschluss:

• true – einschließlich (Element gehört zum Bereich)
• false – ausschließlich (Element gehört nicht dazu)

Für NavigableMap sind die Methoden analog, arbeiten jedoch mit Schlüsseln.

3. Operationen für benachbarte Werte: floor, ceiling, lower, higher; pollFirst/Last

Suche nach nächsten Elementen

NavigableSet:

• lower(E e) – größtes Element < e (streng kleiner)
• floor(E e) – größtes Element ≤ e (kleiner oder gleich)
• ceiling(E e) – kleinstes Element ≥ e (größer oder gleich)
• higher(E e) – kleinstes Element > e (streng größer)

Beispiel:

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() – entfernt und gibt das kleinste Element zurück (oder null, wenn leer)
• pollLast() – entfernt und gibt das größte Element zurück

Beispiel:

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

NavigableMap: analoge Methoden für Schlüssel – lowerKey, floorKey, ceilingKey, higherKey sowie pollFirstEntry, pollLastEntry.

4. Sichten: descendingSet/descendingMap; Views und ihre „Lebendigkeit“

Umgekehrte Reihenfolge: descendingSet/descendingMap

• descendingSet() – gibt eine Sicht der Menge in umgekehrter Reihenfolge zurück.
• descendingMap() – gibt eine Sicht der Map in umgekehrter Schlüsselreihenfolge zurück.

Beispiel:

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]

Wichtig: Das ist keine Kopie, sondern eine „lebende“ Sicht (View) auf denselben Datenbestand. Änderungen in der einen spiegeln sich in der anderen wider.

Sichten (View) und ihre „Lebendigkeit“

• Die Methoden subSet, headSet, tailSet, descendingSet, descendingMap geben eine View zurück – eine „lebende“ Sicht auf die Ausgangs-Collection.
• Alle Änderungen in der View spiegeln sich in der Ausgangs-Collection wider und umgekehrt.
• Wenn Sie ein Element aus subSet entfernen, verschwindet es auch aus der ursprünglichen Menge.

Beispiel:

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]

Vorsicht: Wenn Sie die Ausgangs-Collection so verändern, dass ein Element aus dem Bereich der View „herausfällt“, erhalten Sie beim nächsten Zugriff auf die View eine ConcurrentModificationException.

5. Anwendungsfälle für NavigableSet/NavigableMap

1. Zeitslots/Terminpläne

Aufgabe: den nächstfreien Zeitslot für ein Meeting finden.

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("Nächster Slot: " + nextSlot);

2. Priorisierung (Prioritätswarteschlange)

Aufgabe: stets schnell das Element mit höchster/niedrigster Priorität abrufen.

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

Task next = tasks.pollFirst(); // Aufgabe mit höchster Priorität (1)

3. „Der nächstgelegene Schlüssel“ (z. B. zur Bereichssuche in einer Map)

Aufgabe: den Wertebereich zu einem Schlüssel oder den nächstgelegenen Schlüssel finden.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Ungenügend");
grades.put(65, "Ausreichend");
grades.put(75, "Gut");
grades.put(85, "Sehr gut");

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

6. Praxis: Mini-Beispiele

Beispiel 1: Datumsbereich

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]

Beispiel 2: Suche nach dem nächstliegenden Wert

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Kleiner: " + numbers.lower(x));              // 20
System.out.println("Kleiner oder gleich: " + numbers.floor(x));  // 20
System.out.println("Größer oder gleich: " + numbers.ceiling(x)); // 30
System.out.println("Größer: " + numbers.higher(x));              // 30

7. Typische Fehler und Feinheiten

Fehler Nr. 1: Verwechslung von Einschluss/Ausschluss in subSet/headSet/tailSet.
Achten Sie immer genau auf den Parameter inclusive – standardmäßig waren Bereiche in älteren Java-Versionen ausschließlich; in NavigableSet/NavigableMap kann man Einschluss/Ausschluss explizit angeben.

Fehler Nr. 2: Die Erwartung, dass die View eine Kopie ist.
Eine View ist eine „lebende“ Sicht, keine Kopie! Änderungen in der View spiegeln sich in der Ausgangs-Collection wider.

Fehler Nr. 3: ConcurrentModificationException beim Ändern der Ausgangs-Collection außerhalb der View.
Wenn Sie die Ausgangs-Collection so ändern, dass ein Element aus dem Bereich der View „herausfällt“, erhalten Sie beim nächsten Zugriff auf die View die Ausnahme.

Fehler Nr. 4: Verwendung von NavigableSet/NavigableMap ohne Comparable oder Comparator.
Diese Collections erfordern, dass Elemente (oder Schlüssel) vergleichbar sind (Comparable) oder ein Comparator übergeben wird. Andernfalls erhalten Sie eine ClassCastException.

Fehler Nr. 5: Die Annahme, dass pollFirst/pollLast die Collection nicht verändern.
Diese Methoden entfernen Elemente! Wenn Sie nur einen Blick werfen möchten, verwenden Sie first()/last().