int-interval-stack

Canonical stack-height functions for integer half-open intervals.

int-interval-stack builds an immutable representation of interval overlap multiplicity. Given a collection of half-open integer intervals, it stores the resulting piecewise-constant height function as canonical change points.

[start, end) contributes +1 height on every covered coordinate.

This is useful when a boolean interval set is not enough and the number of overlapping intervals matters.

Model

Input intervals are interpreted as half-open ranges:

[start, end)

The stack height at coordinate x is:

height_at(x) = number of input intervals containing x

Internally, the stack is represented as ordered change points:

ChangePoint { at, height_after }

Each change point means that immediately after at, the active stack height becomes height_after.

The representation is canonical:

• change-point coordinates are strictly increasing;
• adjacent change points always have different heights;
• redundant zero-net boundaries are omitted;
• the final change point restores the height to zero when the stack is non-empty.

Installation

[dependencies]
int-interval-stack = "0.1"
int-interval = "0.9"

Basic usage

use int_interval::I32CO;
use int_interval_stack::IntCOStack;

fn iv(start: i32, end_excl: i32) -> I32CO {
    I32CO::try_new(start, end_excl).unwrap()
}

let stack: IntCOStack<I32CO> = [
    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_at(11), 1);
assert_eq!(stack.height_at(12), 0);

assert_eq!(stack.max_height(), 3);

Change points

use int_interval::I32CO;
use int_interval_stack::IntCOStack;

fn iv(start: i32, end_excl: i32) -> I32CO {
    I32CO::try_new(start, end_excl).unwrap()
}

let stack: IntCOStack<I32CO> = [
    iv(0, 10),
    iv(3, 7),
]
.into_iter()
.collect();

let points = stack.change_points();

assert_eq!(points[0].at, 0);
assert_eq!(points[0].height_after, 1);

assert_eq!(points[1].at, 3);
assert_eq!(points[1].height_after, 2);

assert_eq!(points[2].at, 7);
assert_eq!(points[2].height_after, 1);

assert_eq!(points[3].at, 10);
assert_eq!(points[3].height_after, 0);

Iterating covered segments

iter_intervals() returns canonical covered segments and their heights.

use int_interval::traits::IntCO;
use int_interval::I32CO;
use int_interval_stack::IntCOStack;

fn iv(start: i32, end_excl: i32) -> I32CO {
    I32CO::try_new(start, end_excl).unwrap()
}

let stack: IntCOStack<I32CO> = [
    iv(0, 10),
    iv(3, 7),
]
.into_iter()
.collect();

let segments: Vec<_> = stack
    .iter_intervals()
    .map(|(iv, height)| ((iv.start(), iv.end_excl()), height))
    .collect();

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

Height-filtered iteration

The stack can iterate only segments whose height matches a selected condition.

use int_interval::traits::IntCO;
use int_interval::I32CO;
use int_interval_stack::IntCOStack;

fn iv(start: i32, end_excl: i32) -> I32CO {
    I32CO::try_new(start, end_excl).unwrap()
}

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

let peak: Vec<_> = stack
    .peak_intervals()
    .map(|(iv, height)| ((iv.start(), iv.end_excl()), height))
    .collect();

assert_eq!(peak, vec![((5, 7), 3)]);

Available iterators:

stack.iter_intervals();
stack.iter_intervals_at_least(2);
stack.iter_intervals_at_most(2);
stack.iter_intervals_exactly(2);
stack.iter_intervals_between(1, 3);
stack.peak_intervals();

Predicates

use int_interval::I32CO;
use int_interval_stack::IntCOStack;

fn iv(start: i32, end_excl: i32) -> I32CO {
    I32CO::try_new(start, end_excl).unwrap()
}

let stack: IntCOStack<I32CO> = [
    iv(0, 10),
    iv(20, 30),
]
.into_iter()
.collect();

assert!(stack.contains_point(5));
assert!(!stack.contains_point(15));

assert!(stack.intersects_interval(iv(8, 12)));
assert!(!stack.intersects_interval(iv(12, 18)));

assert!(stack.contains_interval(iv(2, 8)));
assert!(!stack.contains_interval(iv(8, 22)));

Parallel construction

IntCOStack implements Rayon parallel collection.

use int_interval::I32CO;
use int_interval_stack::IntCOStack;
use rayon::prelude::*;

fn iv(start: i32, end_excl: i32) -> I32CO {
    I32CO::try_new(start, end_excl).unwrap()
}

let intervals = vec![
    iv(0, 10),
    iv(3, 7),
    iv(5, 12),
];

let stack: IntCOStack<I32CO> = intervals
    .into_par_iter()
    .collect();

assert_eq!(stack.max_height(), 3);

Parallel construction is intended for larger inputs. For small collections, sequential construction may be faster due to Rayon scheduling overhead.

Complexity

Let n be the number of input intervals and m be the number of canonical change points.

Here k is the number of change points scanned inside the query range.

Benchmarks

This crate includes Criterion / CodSpeed benchmarks for construction, point queries, interval predicates, height-filtered iteration, peak iteration, and parallel construction.

Run locally:

cargo bench

Generate the longer report profile:

BENCH_PROFILE=report cargo bench

License

Licensed under either of:

• MIT license
• Apache License, Version 2.0