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/Last

尋找最接近的元素

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() — 回傳以鍵反向排序的 Map 視圖。

範例：

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 中刪除元素，它也會從原集合中消失。

範例：

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]

注意：如果你對原始集合做了變更，導致某元素「落在」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：未提供 Comparable 或 Comparator 即使用 NavigableSet/NavigableMap。
這些集合要求元素（或鍵）可比較（Comparable），或提供 Comparator；否則會拋出 ClassCastException。

錯誤 5：以為 pollFirst/pollLast 不會改變集合。
這些方法會刪除元素！若只需查看 — 請使用 first()/last()。