Crate closed_interval_set

The closed_interval_set crate manipulates disjoint unions of closed intervals that are represented as vectors (RangeVec) or iterators (NormalizedRangeIter) of pairs of endpoints. These intervals are always closed (inclusive at both ends), so the crate can naturally represent both the empty set (no interval), and the universe (a closed interval from min to max).

The crate is designed for usage patterns where sets are constructed ahead of time (perhaps by combining different sets together), then frozen (as vectors, internally) for read-only access. That said, its iterator implementations of set complementation, union, and intersection are closed over the NormalizedRangeIter trait, so it’s feasible to build up a complex expression (not so complex to need type erasure though) before materializing the result to a RangeVec.

Using this crate usually starts by constructing Vecs of closed ranges (pairs of Endpoints), and passing that to RangeVec::from_vec. From that point, we have access to the set operations on RangeVec and NormalizedRangeIter. The toplevel functions (e.g., intersect_vec and normalize_vec) may be helpful to avoid excessive chaining or in subtle situations, e.g., when the compiler knows whether the input is a RangeVec or a Vec but it’s annoying to track that by hand.

Complementation is tricky when one Handles only closed intervals. We assume Endpoint types can enumerate values in total order via Endpoint::decrease_toward and Endpoint::increase_toward. That’s nonsense for densely ordered sets like \(\mathbb{Q}\), but tends to work OK on computers: it’s trivial to enumerate bounded integers, and there is such a total order for the finite set of floating point values. This sorted enumeration of floating point values rarely makes sense mathematically, but is reasonable in some domains, e.g., static program analysis.

All operations take at most linear space and \(\mathcal{O}(n \log n)\) time, where \(n\) is the total number of ranges in all the inputs, before any normalization (simplification). Set operations on NormalizedRangeIter always use constant space, and many operations on RangeVec reuse storage.

The container type (Vec) is currently hardcoded, for simplicity. The Endpoint trait, however, is fully generic. This crate comes with an implementation of Endpoint for all primitive fixed-width integer types (i8, i16, i32, i64, i128, u8, u16, u32, u64 and u128), for isize and usize, and for the standard floating point types f32 and f64.

Modules

iterator_wrapper

Branded wrapper to mark iterators that yield a normalized sequence of ranges, ranges that are known to contain sorted and disjoint non-empty ranges.

Structs

RangeCase

Some functions don’t care whether their input is normalized; they take impl Into<RangeCase<...>>.

RangeVec

A RangeVec<T> is a normalized Vec of (T, T)

Traits

ClosedRange

A ClosedRange represents a closed range of values with pairs of Endpoints.

Endpoint

An Endpoint is the left or right limit of a closed interval [left, right].

IntoNormalizedRangeIter

A IntoNormalizedRangeIter is an IntoIterator that turns into an NormalizedRangeIter.

NormalizedRangeIter

A NormalizedRangeIter yields a sorted sequence of non-overlapping, non-adjacent, non-empty closed ranges.

Functions

complement_vec

Returns the complement of a vector of closed intervals.

intersect_vec

Constructs the intersection of two normalized vectors of ranges.

is_normalized

Determines whether the input sequence is in normalized format:

normalize_vec

Normalizes the vector of intervals and returns a vector that represents the same set of values, without redundancy.

union_vec

Computes the normalized union of acc and src.