☕ JavaCollections Framework

NavigableSet

NavigableSet extends SortedSet with a rich set of navigation methods that go beyond the simple range-view operations of SortedSet. It adds the ability to find the closest element to a given value (floor, ceiling, lower, higher), to poll (retrieve and remove) the minimum and maximum elements, to obtain a reversed view of the set, to obtain an iterator in descending order, and to control the inclusivity of range bounds precisely. NavigableSet is the interface that TreeSet and ConcurrentSkipListSet implement, and understanding it completely unlocks the full power of sorted collections in Java. This entry covers every NavigableSet method in depth, the descending set and iterator, the extended subSet with inclusivity control, and the practical patterns that navigation methods enable.

NavigableSet Methods — The Complete API

NavigableSet extends SortedSet and adds four categories of methods. The element-finding methods (floor, ceiling, lower, higher) return the closest element to a target in the appropriate direction. The polling methods (pollFirst, pollLast) combine minimum/maximum retrieval with removal. The descending-view methods (descendingSet, descendingIterator) provide reverse-order access. The extended range methods (subSet with four arguments, headSet and tailSet with inclusivity parameter) give precise control over range boundaries. The four element-finding methods form two pairs based on inclusivity. floor(e) and ceiling(e) are inclusive: floor returns the greatest element less than or equal to e; ceiling returns the least element greater than or equal to e. lower(e) and higher(e) are exclusive: lower returns the greatest element strictly less than e (less than only, never equal); higher returns the least element strictly greater than e. All four return null when no such element exists. These four methods answer the four fundamental "closest element" questions: what is the best element I can use that does not exceed e (floor), what is the smallest element I need to wait for that is at least e (ceiling), what came just before e in the sequence (lower), and what comes just after e in the sequence (higher). Together they enable efficient binary-search-like algorithms on any sorted set. pollFirst() and pollLast() are the atomic retrieve-and-remove operations for the minimum and maximum elements. They are useful for priority-queue-like processing of sorted sets and for simulation of ordered event queues. Both return null when the set is empty, matching the Queue interface's non-throwing convention.

Java

// ── All four navigation methods with semantics ───────────────────────
NavigableSet<Integer> set = new TreeSet<>(
    Set.of(10, 20, 30, 40, 50));

// floor(e): greatest element <= e
System.out.println(set.floor(25));   // 20 — 25 not in set, greatest <= 25 is 20
System.out.println(set.floor(30));   // 30 — exact match
System.out.println(set.floor(5));    // null — nothing <= 5

// ceiling(e): least element >= e
System.out.println(set.ceiling(25)); // 30 — 25 not in set, least >= 25 is 30
System.out.println(set.ceiling(30)); // 30 — exact match
System.out.println(set.ceiling(55)); // null — nothing >= 55

// lower(e): greatest element STRICTLY < e (never equal)
System.out.println(set.lower(25));   // 20 — strictly less than 25
System.out.println(set.lower(30));   // 20 — strictly less than 30 (not 30 itself!)
System.out.println(set.lower(10));   // null — nothing strictly less than 10

// higher(e): least element STRICTLY > e (never equal)
System.out.println(set.higher(25));  // 30 — strictly greater than 25
System.out.println(set.higher(30));  // 40 — strictly greater than 30 (not 30!)
System.out.println(set.higher(50));  // null — nothing strictly greater than 50

// ── pollFirst and pollLast ────────────────────────────────────────────
NavigableSet<String> names = new TreeSet<>(
    Set.of("Alice", "Bob", "Carol", "Dave"));

String first = names.pollFirst();   // "Alice" — removed from set
String last  = names.pollLast();    // "Dave"  — removed from set
System.out.println(names);          // [Bob, Carol]

// Safe on empty set — returns null, does not throw:
NavigableSet<Integer> empty = new TreeSet<>();
System.out.println(empty.pollFirst());  // null
System.out.println(empty.pollLast());   // null

// ── Navigation chaining — walk the sequence ───────────────────────────
NavigableSet<Integer> primes = new TreeSet<>(
    Set.of(2, 3, 5, 7, 11, 13, 17, 19, 23));

// Walk in steps: next prime after 10, then after that, etc.
Integer current = primes.higher(10);   // 11
while (current != null) {
    System.out.print(current + " ");
    current = primes.higher(current);  // next prime
}
// 11 13 17 19 23

Descending Views and Iterators

NavigableSet provides two mechanisms for reverse-order access. descendingIterator() returns an Iterator that traverses elements from highest to lowest — the reverse of the set's natural ascending order. descendingSet() returns a NavigableSet that is a live view of the set with reversed ordering: its first() is the original set's last(), its floor() and ceiling() are swapped, and its headSet() and tailSet() operate in the reverse direction. The descending set is a proper view, not a copy. Modifications to the descending set modify the original, and modifications to the original are visible in the descending set. The descending set's comparator is the reverse of the original comparator. Calling descendingSet() twice returns the original (or an equivalent) view — reversal of reversal is the identity. The practical use of descendingSet() is processing elements in reverse order while still using NavigableSet's navigation methods on the reversed view. Rather than manually managing reverse comparisons, the descending set transparently reverses all operations. A call to descendingSet().floor(x) is equivalent to calling ceiling(x) on the original set — the highest element less than or equal to x becomes the lowest in the reversed view, which is the floor. descendingIterator() is slightly more efficient than creating a full descendingSet() when only iteration in reverse is needed. It avoids the overhead of creating the view object and is more memory-efficient for single-pass reverse traversal.

Java

// ── descendingIterator — efficient reverse traversal ─────────────────
NavigableSet<String> set = new TreeSet<>(
    Set.of("Alice", "Bob", "Carol", "Dave", "Eve"));

// Ascending (default):
for (String s : set) System.out.print(s + " ");
// Alice Bob Carol Dave Eve

// Descending via iterator:
Iterator<String> desc = set.descendingIterator();
while (desc.hasNext()) System.out.print(desc.next() + " ");
// Eve Dave Carol Bob Alice

// Enhanced for on descendingSet():
for (String s : set.descendingSet()) System.out.print(s + " ");
// Eve Dave Carol Bob Alice — same result

// ── descendingSet — live view with reversed NavigableSet semantics ────
NavigableSet<Integer> original = new TreeSet<>(Set.of(1, 3, 5, 7, 9));
NavigableSet<Integer> reversed = original.descendingSet();

// The reversed view's first/last are swapped:
System.out.println(original.first());  // 1  — minimum
System.out.println(reversed.first());  // 9  — maximum in original = first in reversed
System.out.println(original.last());   // 9
System.out.println(reversed.last());   // 1

// Navigation methods operate in the reversed direction:
System.out.println(reversed.floor(6));    // 7  — in reversed view, floor means
                                           //       greatest of the elements <= 6 in reversed order
                                           //       which is ceiling(6) in original = 7
System.out.println(reversed.ceiling(6));  // 5  — ceiling in reversed = floor in original

// ── Mutations through descending view ─────────────────────────────────
NavigableSet<Integer> descView = original.descendingSet();
descView.add(6);    // adds 6 to original
System.out.println(original);   // [1, 3, 5, 6, 7, 9] — 6 added

descView.remove(9); // removes 9 from original
System.out.println(original);   // [1, 3, 5, 6, 7] — 9 removed

// ── Double reversal returns to original ordering ──────────────────────
NavigableSet<Integer> doubleReversed = original.descendingSet().descendingSet();
// doubleReversed is functionally equivalent to original
System.out.println(doubleReversed.first());  // 1 — same as original.first()

Extended subSet — Full Inclusivity Control

NavigableSet's subSet(fromElement, fromInclusive, toElement, toInclusive) extends SortedSet's subSet with boolean parameters that control whether each boundary is included or excluded. This enables all four interval types: closed [a, b], open (a, b), half-open [a, b) or (a, b]. SortedSet's subSet only supports [a, b); NavigableSet supports all four types. Similarly, headSet(toElement, inclusive) and tailSet(fromElement, inclusive) extend SortedSet's headSet and tailSet with an inclusivity parameter. headSet(e, true) returns elements less than or equal to e; headSet(e, false) returns elements strictly less than e (equivalent to SortedSet's headSet). These extended range methods are essential when the interval type is determined by the application domain. A query for "all appointments that end by 5pm" needs headSet(5pm, true) — inclusive. A query for "all scores strictly between 70 and 80" needs subSet(70, false, 80, false) — exclusive on both ends. SortedSet cannot express these queries without adjusting the boundary values. The combination of navigation methods and range views enables powerful interval queries. Finding all elements that fall within a given range is a subSet call. Counting elements in a range uses subSet().size(). Removing all elements in a range uses subSet().clear(). Adding an element that maintains a sorted property and then querying its neighbourhood uses a combination of add and floor/ceiling.

Java

// ── All four interval types ───────────────────────────────────────────
NavigableSet<Integer> set = new TreeSet<>(
    Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));

// Closed interval [3, 7]
NavigableSet<Integer> closed = set.subSet(3, true, 7, true);
System.out.println(closed);   // [3, 4, 5, 6, 7]

// Open interval (3, 7)
NavigableSet<Integer> open = set.subSet(3, false, 7, false);
System.out.println(open);     // [4, 5, 6]

// Half-open [3, 7) — same as SortedSet.subSet(3, 7)
NavigableSet<Integer> halfOpenLeft = set.subSet(3, true, 7, false);
System.out.println(halfOpenLeft);  // [3, 4, 5, 6]

// Half-open (3, 7]
NavigableSet<Integer> halfOpenRight = set.subSet(3, false, 7, true);
System.out.println(halfOpenRight); // [4, 5, 6, 7]

// ── headSet and tailSet with inclusivity ──────────────────────────────
// All elements <= 5 (inclusive)
NavigableSet<Integer> head = set.headSet(5, true);
System.out.println(head);    // [1, 2, 3, 4, 5]

// All elements > 5 (exclusive — same as default tailSet behaviour for > 5)
NavigableSet<Integer> tailExcl = set.tailSet(5, false);
System.out.println(tailExcl); // [6, 7, 8, 9, 10]

// ── Range operations on the view ─────────────────────────────────────
NavigableSet<Integer> range = set.subSet(3, true, 8, true);

// Count elements in range:
System.out.println(range.size());   // 6 (3,4,5,6,7,8)

// Remove all elements in range:
range.clear();
System.out.println(set);   // [1, 2, 9, 10] — range removed from original

// ── Practical: appointment scheduler ─────────────────────────────────
NavigableSet<LocalDateTime> appointments = new TreeSet<>();
appointments.add(LocalDateTime.of(2024, 3, 15, 9, 0));
appointments.add(LocalDateTime.of(2024, 3, 15, 10, 30));
appointments.add(LocalDateTime.of(2024, 3, 15, 14, 0));
appointments.add(LocalDateTime.of(2024, 3, 15, 16, 30));

LocalDateTime start = LocalDateTime.of(2024, 3, 15, 10, 0);
LocalDateTime end   = LocalDateTime.of(2024, 3, 15, 15, 0);

// Appointments strictly during the window (exclusive start and end):
NavigableSet<LocalDateTime> inWindow =
    appointments.subSet(start, false, end, false);
System.out.println(inWindow.size());  // 2 (10:30 and 14:00)

// Next appointment from now:
LocalDateTime now  = LocalDateTime.now();
LocalDateTime next = appointments.ceiling(now);
// If next is null, no upcoming appointments

NavigableSet Patterns — Algorithms and Real-World Use

NavigableSet's navigation methods enable several important algorithmic patterns that are difficult or impossible to implement efficiently without sorted storage. Three patterns appear repeatedly: finding the closest preceding or following element, maintaining a sliding window of the k nearest elements, and binary search on arbitrary predicates. The order-statistics pattern uses floor and ceiling to implement rank queries: given a value, find how many elements are less than it (using headSet().size()), greater than it (tailSet().size()), or within a range (subSet().size()). These are O(log n) for the navigation part plus O(k) for the counting, where k is the count. For large sets with frequent rank queries, this is much faster than sorting a list on each query. The interval merge pattern: given a set of intervals, merge all overlapping intervals. Maintain a NavigableSet of interval endpoints; for each new interval, find all overlapping intervals using floor and ceiling on the endpoints, remove them, and add the merged interval. The sorted set makes finding overlapping intervals efficient. The k-nearest-to-target pattern finds k elements whose values are closest to a target. Use floor and ceiling to find the element at or below and at or above the target, then expand in both directions using lower and higher, always picking the closer candidate next. This produces the k nearest elements in O(k log n) time rather than O(n log n) sorting.

Java

// ── Order statistics — rank queries ──────────────────────────────────
NavigableSet<Integer> scores = new TreeSet<>(
    Set.of(45, 62, 71, 78, 85, 91, 96, 99));

int target = 80;
// How many scores are less than 80?
int rank = scores.headSet(target, false).size();  // 4 (45,62,71,78)
System.out.println("Scores below " + target + ": " + rank);

// What percentile is 80?
double percentile = (double) rank / scores.size() * 100;
System.out.printf("Percentile: %.0f%%
", percentile);  // 50%

// ── K-nearest elements to target ──────────────────────────────────────
public List<Integer> kNearest(NavigableSet<Integer> set,
                               int target, int k) {
    // Use two pointers: one scanning down (lower), one scanning up (higher)
    List<Integer> result = new ArrayList<>();
    Integer lower = set.floor(target);
    Integer upper = set.ceiling(target);

    // If target is in set, add it and advance upper
    if (lower != null && lower.equals(upper)) {
        result.add(lower);
        lower = set.lower(lower);
        if (result.size() == k) return result;
    }

    while (result.size() < k && (lower != null || upper != null)) {
        if (lower == null) {
            result.add(upper);
            upper = set.higher(upper);
        } else if (upper == null) {
            result.add(lower);
            lower = set.lower(lower);
        } else if (Math.abs(target - lower) <= Math.abs(target - upper)) {
            result.add(lower);
            lower = set.lower(lower);
        } else {
            result.add(upper);
            upper = set.higher(upper);
        }
    }
    return result;
}

NavigableSet<Integer> data = new TreeSet<>(
    Set.of(1, 5, 10, 15, 20, 25, 30));
System.out.println(kNearest(data, 12, 3));  // [10, 15, 5] — 3 nearest to 12

// ── Finding gaps in a sequence ────────────────────────────────────────
// Find the first missing integer in a sorted set of reserved IDs
public int firstAvailableId(NavigableSet<Integer> reserved, int start) {
    Integer next = reserved.ceiling(start);
    while (next != null && next.equals(start)) {
        start++;
        next = reserved.ceiling(start);
    }
    return start;
}

NavigableSet<Integer> reserved = new TreeSet<>(Set.of(1, 2, 3, 5, 6, 9));
System.out.println(firstAvailableId(reserved, 1));  // 4 — first gap after 1

// ── Using NavigableSet vs SortedSet in method signatures ──────────────
// Use SortedSet when only first(), last(), subSet(), headSet(), tailSet() needed
// Use NavigableSet when floor(), ceiling(), lower(), higher(),
//                      descendingSet(), pollFirst(), or inclusivity control needed

public static <T> Optional<T> findCeiling(NavigableSet<T> set, T target) {
    return Optional.ofNullable(set.ceiling(target));
}

public static <T> int countBetween(SortedSet<T> set, T from, T to) {
    return set.subSet(from, to).size();  // SortedSet sufficient for this
}

NavigableSet

NavigableSet Methods — The Complete API

Descending Views and Iterators

Extended subSet — Full Inclusivity Control

NavigableSet Patterns — Algorithms and Real-World Use

Related Topics in Collections Framework