NavigableSet/NavigableMap

1. Вступ

У стандартній бібліотеці Java є чимало колекцій, але коли йдеться про діапазони, пошук найближчих елементів, пріоритизацію та роботу з часовими слотами, на перший план виходять інтерфейси NavigableSet і NavigableMap.

NavigableSet розширює SortedSet, додаючи методи для пошуку елементів щодо заданого значення (менше, більше, найближчий тощо), а також для роботи з діапазонами.
NavigableMap розширює SortedMap, додаючи подібні методи для пошуку за ключами та роботи з діапазонами.

Найвідоміші реалізації: TreeSet і TreeMap.

Коли потрібні NavigableSet/NavigableMap?

• Коли важливо не просто зберігати унікальні елементи/ключі у відсортованому порядку, а й швидко знаходити «сусідів» (наприклад, найближчий вільний час, пріоритетне завдання, діапазон значень).
• Коли потрібно працювати з діапазонами: «усі елементи між X і Y», «усі ключі більші/менші за заданий», «знайти найближчий ключ».

2. Діапазони: subSet, headSet, tailSet

Методи для роботи з діапазонами

NavigableSet і NavigableMap дають змогу отримувати «живі» подання (view) на підмножини колекції:

• subSet(fromElement, fromInclusive, toElement, toInclusive) — елементи у діапазоні [fromElement; toElement], включно/невключно.
• headSet(toElement, inclusive) — усі елементи, менші (або менші чи рівні) за toElement.
• tailSet(fromElement, inclusive) — усі елементи, більші (або більші чи рівні) за fromElement.

Приклад:

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

// Діапазон від 15 (включно) до 45 (невключно)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

// Усі елементи <= 30
NavigableSet<Integer> head = set.headSet(30, true); // [10, 20, 30]

// Усі елементи > 20
NavigableSet<Integer> tail = set.tailSet(20, false); // [30, 40, 50]

Включність/невключність:

• true — включно (елемент входить до діапазону)
• false — невключно (елемент не входить)

Для NavigableMap методи аналогічні, лише працюють із ключами.

3. Операції пошуку найближчих значень: floor, ceiling, lower, higher; pollFirst/pollLast

Пошук найближчих елементів

NavigableSet:

• lower(E e) — найбільший елемент < e (строго менший)
• floor(E e) — найбільший елемент ≤ e (менший або рівний)
• ceiling(E e) — найменший елемент ≥ e (більший або рівний)
• higher(E e) — найменший елемент > e (строго більший)

Приклад:

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() — видаляє та повертає найменший елемент (або null, якщо колекція порожня)
• pollLast() — видаляє та повертає найбільший елемент

Приклад:

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

NavigableMap: аналогічні методи для ключів — lowerKey, floorKey, ceilingKey, higherKey, а також pollFirstEntry, pollLastEntry.

4. Подання: descendingSet/descendingMap; подання‑view та їх «живість»

Зворотний порядок: descendingSet/descendingMap

• descendingSet() — повертає подання множини у зворотному порядку.
• descendingMap() — повертає подання мапи у зворотному порядку ключів.

Приклад:

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]

Важливо: це не копія, а «живе» подання (view) того самого набору даних. Зміни в одному відображаються в іншому.

Подання (view) та їх «живість»

• Методи subSet, headSet, tailSet, descendingSet, descendingMap повертають view — «живе» подання вихідної колекції.
• Будь-які зміни у view відображаються у вихідній колекції й навпаки.
• Якщо видалити елемент із subSet — він зникне і з початкової множини.

Обережно: якщо ви зміните початкову колекцію так, що елемент «випаде» з діапазону view, під час наступного звернення до view отримаєте ConcurrentModificationException.

5. Випадки використання NavigableSet/NavigableMap

1. Часові слоти/розклади

Завдання: знайти найближчий вільний часовий слот для зустрічі.

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("Найближчий час: " + nextSlot);

2. Пріоритизація (черга з пріоритетом)

Завдання: завжди швидко отримувати елемент із найвищим/найменшим пріоритетом.

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("Пошта", 2));
tasks.add(new Task("Дзвінок", 1));
tasks.add(new Task("Звіт", 3));

Task next = tasks.pollFirst(); // Завдання з найвищим пріоритетом (1)

3. «Найближчий ключ» (наприклад, для пошуку діапазону у Map)

Завдання: знайти діапазон значень за ключем або найближчий ключ.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Незадовільно");
grades.put(65, "Задовільно");
grades.put(75, "Добре");
grades.put(85, "Відмінно");

int score = 78;
int key = grades.floorKey(score); // 75
System.out.println("Оцінка: " + grades.get(key)); // Добре

6. Практика: міні‑приклади

Приклад 1: Діапазон дат

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]

Приклад 2: Пошук найближчого значення

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Менше: " + numbers.lower(x));              // 20
System.out.println("Менше або дорівнює: " + numbers.floor(x)); // 20
System.out.println("Більше або дорівнює: " + numbers.ceiling(x));  // 30
System.out.println("Більше: " + numbers.higher(x));            // 30

7. Типові помилки та нюанси

Помилка № 1: Плутають включність/невключність у subSet/headSet/tailSet.
Завжди уважно стежте за параметрами inclusive — за замовчуванням у старих версіях Java діапазони були невключними; у NavigableSet/NavigableMap можна явно вказати включно/невключно.

Помилка № 2: Очікування, що view — це копія.
View — це «живе» подання, а не копія! Зміни у view відображаються у вихідній колекції.

Помилка № 3: ConcurrentModificationException під час зміни вихідної колекції поза межами view.
Якщо ви змінюєте вихідну колекцію так, що елемент «випадає» з діапазону view, під час наступного звернення до view отримаєте виняток.

Помилка № 4: Використання NavigableSet/NavigableMap без Comparable або Comparator.
Ці колекції вимагають, щоб елементи (або ключі) були порівнюваними (Comparable) або щоб було передано Comparator. Інакше отримаєте ClassCastException.

Помилка № 5: Очікування, що pollFirst/pollLast не змінюють колекцію.
Ці методи видаляють елементи! Якщо потрібен просто перегляд — використовуйте first()/last().