Java NavigableSet subSet: account for a live backed range

Last updated: 5 Oct 20265 min read

tutorial

NavigableSet.subSet returns a backed view of keys in a specified range. Mutations through either view or source are visible through the other.

Operational contract

The method returns a half-open receipt-ID range. Its caller owns the underlying set and must keep it alive and coordinate any concurrent access; TreeSet itself is not thread-safe. Inserting an out-of-range value through the view throws IllegalArgumentException. If a stable snapshot is needed, copy the view into a new TreeSet under appropriate synchronization. Comparator order defines the meaning of from and to; this sample assumes natural long ordering. The range validates reversed endpoints before construction.

Failure case

A report asks for IDs [40, 80). After the view is created, the owner adds ID 47 to the source set. The view now contains 47. Attempting to add 82 through the view fails as out of range.

Java code

import java.util.NavigableSet;
import java.util.Objects;

public class ReceiptIdRangeView {
    public static NavigableSet<Long> between(NavigableSet<Long> receiptIds,
            long fromInclusive, long toExclusive) {
        Objects.requireNonNull(receiptIds);
        if (toExclusive < fromInclusive)
            throw new IllegalArgumentException("Reversed receipt range");
        return receiptIds.subSet(fromInclusive, true, toExclusive, false);
    }
}

Performance and ownership cost

Creating the view uses O(1) wrapper state. Tree-based lookup or insertion through it is O(log N) for N stored IDs; iterating K matching IDs is O(K) after locating the start. A stable copy costs O(K) storage and additional insertion work.

Common Mistakes

Do not treat the returned range as a snapshot.
Do not insert outside its bounds.
Do not mutate an unsynchronized TreeSet concurrently through source and view.

Connected lessons

java

compact sets and views

treeset-backed-range-view