NavigableSet/NavigableMap

1. Wprowadzenie

W standardowej bibliotece Javy jest wiele kolekcji, lecz gdy w grę wchodzą zakresy, wyszukiwanie „najbliższych” elementów, priorytetyzacja i praca z oknami czasowymi, na scenę wkraczają interfejsy NavigableSet i NavigableMap.

NavigableSet rozszerza SortedSet, dodając metody wyszukiwania elementów względem zadanej wartości (mniejsze, większe, najbliższe itd.), a także do pracy z zakresami.
NavigableMap rozszerza SortedMap, dodając podobne metody wyszukiwania po kluczach i pracy z zakresami.

Najbardziej znane implementacje: TreeSet i TreeMap.

Kiedy warto używać NavigableSet/NavigableMap?

• Gdy ważne jest nie tylko przechowywanie unikalnych elementów/kluczy w porządku sortowania, lecz także szybkie znajdowanie „sąsiadów” (np. najbliższego wolnego terminu, zadania o najwyższym priorytecie, zakresu wartości).
• Gdy trzeba pracować z zakresami: „wszystkie elementy między X i Y”, „wszystkie klucze większe/mniejsze od zadanego”, „znaleźć najbliższy klucz”.

2. Zakresy: subSet, headSet, tailSet

Metody pracy z zakresami

NavigableSet i NavigableMap pozwalają uzyskiwać „żywe” przedstawienia (view) podzbiorów kolekcji:

• subSet(fromElement, fromInclusive, toElement, toInclusive) — elementy w zakresie [fromElement; toElement], włącznie/wyłącznie.
• headSet(toElement, inclusive) — wszystkie elementy mniejsze (lub mniejsze bądź równe) od toElement.
• tailSet(fromElement, inclusive) — wszystkie elementy większe (lub większe bądź równe) od fromElement.

Przykład:

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

// Zakres od 15 (włącznie) do 45 (wyłącznie)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

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

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

Włączność/wyłączność:

• true — włącznie (element należy do zakresu)
• false — wyłącznie (element nie należy)

Dla NavigableMap metody są analogiczne, tylko działają na kluczach.

3. Operacje najbliższych wartości: floor, ceiling, lower, higher; pollFirst/Last

Wyszukiwanie najbliższych elementów

NavigableSet:

• lower(E e) — największy element < e (ściśle mniejszy)
• floor(E e) — największy element ≤ e (mniejszy lub równy)
• ceiling(E e) — najmniejszy element ≥ e (większy lub równy)
• higher(E e) — najmniejszy element > e (ściśle większy)

Przykład:

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() — usuwa i zwraca najmniejszy element (lub null, jeśli pusty)
• pollLast() — usuwa i zwraca największy element

Przykład:

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

NavigableMap: analogiczne metody dla kluczy — lowerKey, floorKey, ceilingKey, higherKey, a także pollFirstEntry, pollLastEntry.

4. Widoki: descendingSet/descendingMap; widoki‑view i ich „żywość”

Porządek odwrotny: descendingSet/descendingMap

• descendingSet() — zwraca widok zbioru w odwrotnej kolejności.
• descendingMap() — zwraca widok mapy w odwrotnej kolejności kluczy.

Przykład:

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]

Ważne: to nie jest kopia, lecz „żywy” widok (view) tych samych danych. Zmiany w jednym odzwierciedlają się w drugim.

Widoki (view) i ich „żywość”

• Metody subSet, headSet, tailSet, descendingSet, descendingMap zwracają view — „żywe” przedstawienie kolekcji źródłowej.
• Wszelkie zmiany w view są widoczne w kolekcji źródłowej i odwrotnie.
• Jeśli usuniesz element z subSet — zniknie on także z oryginalnego zbioru.

Przykład:

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]

Uwaga: jeśli zmienisz kolekcję źródłową w taki sposób, że element „wypadnie” poza zakres view, przy następnym dostępie do view otrzymasz ConcurrentModificationException.

5. Przypadki użycia NavigableSet/NavigableMap

1. Sloty czasowe/harmonogramy

Zadanie: znaleźć najbliższy wolny slot czasowy na spotkanie.

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("Najbliższy czas: " + nextSlot);

2. Priorytetyzacja (kolejka priorytetowa)

Zadanie: zawsze szybko pobierać element o najwyższym/najniższym priorytecie.

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("Poczta", 2));
tasks.add(new Task("Telefon", 1));
tasks.add(new Task("Raport", 3));

Task next = tasks.pollFirst(); // Zadanie z najwyższym priorytetem (1)

3. „Najbliższy klucz” (np. do wyszukiwania zakresu w Map)

Zadanie: znaleźć zakres wartości po kluczu lub najbliższy klucz.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Niedostatecznie");
grades.put(65, "Dostatecznie");
grades.put(75, "Dobrze");
grades.put(85, "Bardzo dobrze");

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

6. Praktyka: mini-przykłady

Przykład 1: Zakres dat

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]

Przykład 2: Wyszukiwanie najbliższej wartości

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Mniejsze: " + numbers.lower(x));              // 20
System.out.println("Mniejsze lub równe: " + numbers.floor(x));    // 20
System.out.println("Większe lub równe: " + numbers.ceiling(x));  // 30
System.out.println("Większe: " + numbers.higher(x));             // 30

7. Typowe błędy i niuanse

Błąd nr 1: Mylona jest włączność/wyłączność w subSet/headSet/tailSet.
Zawsze zwracaj uwagę na parametry inclusive — domyślnie w starszych wersjach Javy zakresy były wyłączne; w NavigableSet/NavigableMap można jawnie wskazać włączenie/wyłączenie.

Błąd nr 2: Oczekiwanie, że view to kopia.
View to „żywe” przedstawienie, a nie kopia! Zmiany w view odzwierciedlają się w kolekcji źródłowej.

Błąd nr 3: ConcurrentModificationException przy zmianie kolekcji źródłowej poza view.
Jeśli zmienisz kolekcję źródłową w taki sposób, że element „wypadnie” poza zakres view, przy następnym dostępie do view otrzymasz wyjątek.

Błąd nr 4: Używanie NavigableSet/NavigableMap bez Comparable lub Comparator.
Te kolekcje wymagają, aby elementy (lub klucze) były porównywalne (Comparable) lub aby przekazać Comparator. W przeciwnym razie otrzymasz ClassCastException.

Błąd nr 5: Oczekiwanie, że pollFirst/pollLast nie modyfikują kolekcji.
Te metody usuwają elementy! Jeśli potrzebny jest tylko podgląd — użyj first()/last().