int-interval-set

int-interval-set provides immutable canonical interval-set containers for integer half-open intervals.

The crate is built around a single generic set type:

IntCOSet<I>

where:

I: IntCO

Concrete interval-set types such as U8COSet and I32COSet are now simple type aliases.

The library no longer uses builders, concurrent mutable phases, or generated set implementations.

Instead, interval sets are constructed directly from iterators and immediately canonicalized into compact immutable arrays.

---

Interval semantics

All intervals are half-open:

[start, end_excl)

For example:

[10, 20)

contains:

10, 11, ..., 19

but does not contain:

20

Intervals are canonicalized automatically during construction.

Adjacent intervals are merged:

[0, 5) + [5, 10) -> [0, 10)

Overlapping intervals are also merged:

[10, 20) + [15, 30) -> [10, 30)

The canonical invariant is:

for every adjacent pair a, b:
    a.end_excl() < b.start()

This means canonical interval sets are:

• sorted;
• non-overlapping;
• non-adjacent;
• already merged.

---

Core type

pub struct IntCOSet<I: IntCO>

Internally:

Arc<[I]>

is used as the immutable storage representation.

Cloning a set is therefore cheap.

---

Provided aliases

Unsigned:

U8COSet
U16COSet
U32COSet
U64COSet
U128COSet
UsizeCOSet

Signed:

I8COSet
I16COSet
I32COSet
I64COSet
I128COSet
IsizeCOSet

These are aliases only:

pub type U8COSet = IntCOSet<U8CO>;

---

Construction

Interval sets are usually constructed through FromIterator.

Example:

use int_interval::U8CO;
use int_interval_set::U8COSet;

let set: U8COSet = [
    U8CO::try_new(10, 20).unwrap(),
    U8CO::try_new(15, 30).unwrap(),
    U8CO::try_new(40, 50).unwrap(),
]
.into_iter()
.collect();

assert_eq!(
    set.as_slice(),
    &[
        U8CO::try_new(10, 30).unwrap(),
        U8CO::try_new(40, 50).unwrap(),
    ]
);

Parallel construction is also supported through Rayon:

use rayon::iter::{IntoParallelIterator, ParallelIterator};
use int_interval::U8CO;
use int_interval_set::U8COSet;

let set: U8COSet = vec![
    U8CO::try_new(0, 10).unwrap(),
    U8CO::try_new(10, 20).unwrap(),
]
.into_par_iter()
.collect();

assert_eq!(
    set.as_slice(),
    &[U8CO::try_new(0, 20).unwrap()]
);

---

Basic accessors

set.interval_count();
set.is_empty();
set.as_slice();
set.iter_intervals();

Example:

assert_eq!(set.interval_count(), 2);

for interval in set.iter_intervals() {
    println!("{interval:?}");
}

---

Predicate APIs

Predicate APIs answer yes-or-no questions.

set.contains_point(x);
set.contains_interval(query);
set.intersects_interval(query);

Example:

use int_interval::U8CO;

let query = U8CO::try_new(15, 25).unwrap();

assert!(set.intersects_interval(query));
assert!(!set.contains_interval(query));

---

Search APIs

Find interval containing a point

let hit = set.interval_containing_point(18);

Because sets are canonical, at most one interval can contain a point.

---

Iterate intersecting intervals

let hits: Vec<_> = set
    .intervals_intersecting(
        U8CO::try_new(15, 45).unwrap()
    )
    .collect();

Example:

set:   [10, 20), [30, 40)
query: [15, 35)

out:
  [10, 20), [30, 40)

---

Interval-vs-set algebra

Intersection

set.intersection_with_interval(query);

Example:

set:   [10, 20), [30, 40)
query: [15, 35)

out:
  [15, 20), [30, 35)

---

Union

set.union_with_interval(query);

Example:

set:   [10, 20), [30, 40)
query: [20, 30)

out:
  [10, 40)

---

Difference

set.difference_with_interval(query);

Example:

set:   [10, 20), [30, 40), [50, 60)
query: [15, 55)

out:
  [10, 15), [55, 60)

---

Symmetric difference

set.symmetric_difference_with_interval(query);

Example:

set:   [10, 20), [30, 40)
query: [15, 35)

out:
  [10, 15), [20, 30), [35, 40)

---

Set-vs-set algebra

Intersection

left.intersection_with_set(&right);

---

Union

left.union_with_set(&right);

---

Difference

left.difference_with_set(&right);

---

Symmetric difference

left.symmetric_difference_with_set(&right);

Example:

left:  [0, 10), [20, 30)
right: [5, 15), [25, 35)

xor:
  [0, 5), [10, 15), [20, 25), [30, 35)

---

Coverage APIs

Coverage APIs measure how much of a query interval is covered by the set.

set.covered_len_of(query);
set.uncovered_len_of(query);

set.coverage_ratio_f32_of(query);
set.coverage_ratio_f64_of(query);

Example:

set:   [10, 20), [30, 40)
query: [15, 35)

covered:
  [15, 20), [30, 35)

covered length:
  10

query length:
  20

coverage ratio:
  0.5

---

Complexity

Most query operations are logarithmic or linear in the number of matching intervals.

Representative costs:

Operation	Complexity
contains_point	O(log n)
contains_interval	O(log n)
intersects_interval	O(log n)
intervals_intersecting	O(log n + k)
intersection_with_interval	O(log n + k)
union_with_interval	O(log n + n)
difference_with_interval	O(log n) to O(n)
intersection_with_set	O(n + m)
union_with_set	O(n + m)
difference_with_set	O(n + m)
symmetric_difference_with_set	O(n + m)

where:

n = self interval count
m = other interval count
k = number of matching intervals

---

Design goals

The crate prioritizes:

• immutable canonical representations;
• predictable interval algebra;
• low-overhead binary-search queries;
• generic implementations over all integer interval types;
• zero code generation;
• simple semantics and explicit APIs.