NavigableSet/NavigableMap

1. Introduction

The Java standard library offers many collections, but when it comes to ranges, finding “nearest” elements, prioritisation, and working with time slots, the interfaces NavigableSet and NavigableMap come into play.

NavigableSet extends SortedSet, adding methods to search for elements relative to a given value (less, greater, nearest, etc.) as well as to work with ranges.
NavigableMap extends SortedMap, adding similar methods for key-based searches and working with ranges.

The most well-known implementations are TreeSet and TreeMap.

When do you need NavigableSet/NavigableMap?

• When you not only need to store unique elements/keys in sorted order, but also quickly find “neighbours” (e.g., the nearest free time, the highest-priority task, a value range).
• When you need to work with ranges: “all elements between X and Y,” “all keys greater/less than a given one,” “find the nearest key.”

2. Ranges: subSet, headSet, tailSet

Methods for working with ranges

NavigableSet and NavigableMap let you obtain “live” views of collection subsets:

• subSet(fromElement, fromInclusive, toElement, toInclusive) — elements in the range [fromElement; toElement], inclusive/exclusive.
• headSet(toElement, inclusive) — all elements less than (or less than or equal to) toElement.
• tailSet(fromElement, inclusive) — all elements greater than (or greater than or equal to) fromElement.

Example:

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

// Range from 15 (inclusive) to 45 (exclusive)
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

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

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

Inclusivity/exclusivity:

• true — inclusive (the element is included in the range)
• false — exclusive (the element is not included)

For NavigableMap the methods are analogous, but operate on keys.

3. Nearest-value operations: floor, ceiling, lower, higher; pollFirst/Last

Finding nearest elements

NavigableSet:

• lower(E e) — the greatest element < e (strictly less than)
• floor(E e) — the greatest element ≤ e (less than or equal to)
• ceiling(E e) — the smallest element ≥ e (greater than or equal to)
• higher(E e) — the smallest element > e (strictly greater)

Example:

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() — removes and returns the smallest element (or null if empty)
• pollLast() — removes and returns the largest element

Example:

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

NavigableMap: similar methods for keys — lowerKey, floorKey, ceilingKey, higherKey, as well as pollFirstEntry, pollLastEntry.

4. Views: descendingSet/descendingMap; views and their “liveness”

Reverse order: descendingSet/descendingMap

• descendingSet() — returns a view of the set in reverse order.
• descendingMap() — returns a view of the map with keys in reverse order.

Example:

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]

Important: this is not a copy, but a “live” view of the same data set. Changes in one are reflected in the other.

Views and their “liveness”

• The methods subSet, headSet, tailSet, descendingSet, descendingMap return a view — a “live” representation of the original collection.
• Any changes in the view are reflected in the original collection and vice versa.
• If you remove an element from a subSet, it will also disappear from the original set.

Example:

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]

Beware: if you modify the original collection so that an element “falls out” of the view’s range, the next time you access the view you’ll get a ConcurrentModificationException.

5. Use cases for NavigableSet/NavigableMap

1. Time slots/scheduling

Task: find the nearest free time slot for a meeting.

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("Nearest time: " + nextSlot);

2. Prioritization (priority queue)

Task: always quickly get the element with the highest/lowest priority.

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("Mail", 2));
tasks.add(new Task("Call", 1));
tasks.add(new Task("Report", 3));

Task next = tasks.pollFirst(); // Task with the highest priority (1)

3. “Nearest key” (e.g., to find a range in a Map)

Task: find a value range by key, or the nearest key.

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "Unsatisfactory");
grades.put(65, "Satisfactory");
grades.put(75, "Good");
grades.put(85, "Excellent");

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

6. Practice: mini-examples

Example 1: Date range

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]

Example 2: Finding the nearest value

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("Less than: " + numbers.lower(x));              // 20
System.out.println("Less than or equal: " + numbers.floor(x));    // 20
System.out.println("Greater than or equal: " + numbers.ceiling(x));  // 30
System.out.println("Greater than: " + numbers.higher(x));             // 30

7. Common pitfalls and nuances

Error #1: Confusing inclusivity/exclusivity in subSet/headSet/tailSet.
Always pay close attention to the inclusive parameters — by default in older Java versions the ranges were exclusive; in NavigableSet/NavigableMap you can explicitly specify inclusive/exclusive.

Error #2: Expecting a view to be a copy.
A view is a “live” representation, not a copy! Changes in the view are reflected in the original collection.

Error #3: ConcurrentModificationException when modifying the original collection outside the view.
If you modify the original collection so that an element “falls out” of the view’s range, the next time you access the view you’ll get an exception.

Error #4: Using NavigableSet/NavigableMap without Comparable or Comparator.
These collections require that elements (or keys) be comparable (Comparable) or that a Comparator be provided. Otherwise you’ll get a ClassCastException.

Error #5: Expecting pollFirst/pollLast not to modify the collection.
These methods remove elements! If you only need to inspect, use first()/last().