int-intervals

A no_std-friendly closed-open integer interval algebra, canonical interval-set containers, and overlap-stack structures.

History

This crate consolidates and supersedes three previously independent crates:

The three crates formed a dependency chain — stack depended on set, which depended on interval. Maintaining them separately meant synchronising versions, duplicating CI workflows, and publishing across three repos. Merging them into a single crate with feature gates simplifies maintenance while keeping the same no_std-first posture: without any features, int-intervals compiles against core alone.

Quick start

use int_intervals::I32CO;

// Core interval algebra — always available, zero deps.
let a = I32CO::try_new(0, 10).unwrap();
let b = I32CO::try_new(5, 15).unwrap();
assert_eq!(a.intersection(b), Some(I32CO::try_new(5, 10).unwrap()));
assert_eq!(a.convex_hull(b), I32CO::try_new(0, 15).unwrap());

// With `set` feature: canonical interval sets.
#[cfg(feature = "set")]
{
    use int_intervals::I32COSet;
    let set: I32COSet = [a, b].into_iter().collect();
    assert!(set.contains_point(7));
}

// With `stack` feature: overlap-multiplicity stacks.
#[cfg(feature = "stack")]
{
    use int_intervals::I32COStack;
    let stack: I32COStack = [a, b].into_iter().collect();
    assert_eq!(stack.height_at(7), 2); // covered by both a and b
}

Migration from the old crates

All type aliases (I32CO, U8COSet, I16COStack, etc.) are re-exported at the crate root.

Modules

Interval model

Intervals are [start, end_excl) — closed at the start, open at the end:

start < end_excl
len = end_excl - start

Empty or reversed intervals are not representable. Construction returns Option:

let x = I32CO::try_new(2, 8).unwrap();   // [2, 8)
let y = I32CO::try_new(5, 3);            // None

12 concrete types are provided:

U8CO/I8CO, U16CO/I16CO, U32CO/I32CO, U64CO/I64CO,
U128CO/I128CO, UsizeCO/IsizeCO

Interval algebra

Core operations return fixed-capacity containers — no heap allocation:

let a = I32CO::try_new(2, 10).unwrap();
let b = I32CO::try_new(4, 6).unwrap();

let residues: Vec<_> = a.difference(b).into_iter().collect();
assert_eq!(residues.len(), 2);

All result containers implement Iterator, DoubleEndedIterator, ExactSizeIterator, FusedIterator.

Minkowski arithmetic

Checked (exact) and saturating (clamped) Minkowski operations are provided for both linear images and non-linear hulls:

a.checked_minkowski_add(b);               // exact sum
a.checked_minkowski_mul_hull(b);          // containing hull after multiplication
a.saturating_minkowski_add(b);            // clamped to representable domain
a.saturating_minkowski_mul_scalar_hull(3); // clamped scalar hull

Generic programming

The IntCO trait bundles the core capabilities needed by downstream algorithms:

fn residual_measure<I>(lhs: I, rhs: I) -> I::MeasureType
where
    I: IntCO,
{
    lhs.difference(rhs).into_iter().map(|iv| iv.len()).sum()
}

For a full trait catalogue, see the docs.

Interval sets (set feature)

IntCOSet<I> is an immutable canonical set of half-open intervals, stored as Arc<[I]>.

Construction

use int_intervals::I32CO;
use int_intervals::I32COSet;

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

// Automatically canonicalized: overlapping [10,20) + [15,30) → [10,30)
assert_eq!(set.as_slice(), &[
    I32CO::try_new(10, 30).unwrap(),
    I32CO::try_new(40, 50).unwrap(),
]);

Parallel construction via Rayon is available with the parallel feature.

Queries

// Predicates
set.contains_point(18);
set.contains_interval(query);
set.intersects_interval(query);

// Search
set.interval_containing_point(18);          // O(log n)
set.intervals_intersecting(query);           // O(log n + k)

// Algebra (set vs interval)
set.intersection_with_interval(query);
set.union_with_interval(query);
set.difference_with_interval(query);

// Algebra (set vs set)
left.intersection_with_set(&right);          // O(n + m)
left.union_with_set(&right);
left.difference_with_set(&right);
left.symmetric_difference_with_set(&right);

// Coverage
set.covered_len_of(query);                  // exact length
set.coverage_ratio_f32_of(query);           // 0.0 .. 1.0

Interval stacks (stack feature)

IntCOStack<I> builds a canonical piecewise-constant height function from interval endpoints.

input:  [0, 10), [3, 7), [5, 12)
height:   1        2        3        1     0
          ├────────┼────────┼────────┼─────┤
          0        3    5    7   10   12

Construction and queries

use int_intervals::{I32CO, IntCOStack};

fn iv(s: i32, e: i32) -> I32CO { I32CO::try_new(s, e).unwrap() }

let stack: IntCOStack = [iv(0, 10), iv(3, 7), iv(5, 12)]
    .into_iter().collect();

assert_eq!(stack.height_at(2), 1);
assert_eq!(stack.height_at(4), 2);
assert_eq!(stack.height_at(6), 3);
assert_eq!(stack.height_stats().max_height(), 3);

Height segments

let segments: Vec<_> = stack.iter_height_segments()
    .map(|seg| ((seg.interval.start(), seg.interval.end_excl()), seg.height.get()))
    .collect();

assert_eq!(segments, vec![
    ((0, 3), 1), ((3, 7), 2), ((7, 10), 1), ((10, 12), 0),
]);

Filtered iterators: at_least(n), at_most(n), exactly(n), between(lo, hi), peak.

Covered set

stack.covered() lazily projects the stack to an IntCOSet containing all coordinates with positive height. The result is cached after the first call.

Window iteration

Slide a fixed-length window across [from, to) and decompose each position into constant-height runs:

let windows: Vec<_> = stack.iter_windows(0, 10, 4)
    .map(|w| {
        let runs: Vec<_> = w.iter_height_runs()
            .map(|r| ((r.interval.start(), r.interval.end_excl()), r.height))
            .collect();
        ((w.interval().start(), w.interval().end_excl()), runs)
    })
    .collect();

Parallel window iteration is available with the parallel feature.

Features

License

MIT OR Apache-2.0