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() — キーを逆順にしたマップのビューを返す。

例:

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）とその「ライブ」性

• 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() を使ってください。