intervalsets

intervalsets is a family of crates for working with intervals and numeric sets.

• intervalsets-core no-std, no-alloc functionality.
• intervalsets extended functionality requiring allocation.

This guide is intended to cover information applicable to the family of crates. For specifics see the intervalsets-core or intervalsets api documentation.

Version

Limitations

This family of crates is intended to provide robust, general implementations of intervals with a convenient Set based api, and support pluggable user provided data-types. While attention has been given to performance, there are many optimizations that can not be included without a loss of generality.

Currently interval arithmetic is not supported, and while it may be in the future, it will never be as performant as a specialized library like inari.

Contributing

Contributions are welcome.

License

intervalsets is released under the MIT license.

api

types

operations

Most operations are provided via traits in order to present a consistent, easy to use API for each type.

Examples

Filter overlapping intervals

#![allow(unused)]
fn main() {
use intervalsets::prelude::*;

let reserved = Interval::closed_open(0, 100)
    .union(Interval::closed_open(200, 300))
    .union(Interval::closed_open(400, 500));

let requests: Vec<Interval<_>> = vec![
    [10, 20].into(),
    (150..160).into(),
    [200, 210].into(),
    (300, 400).into()
];

let (acceptable, rejected): (Vec<_>, Vec<_>) = requests.into_iter()
    .partition(|interval| !reserved.intersects(interval));

assert_eq!(acceptable, vec![
    Interval::closed_open(150, 160),
    Interval::open(300, 400),
]);

assert_eq!(rejected, vec![
    Interval::closed(10, 20),
    Interval::closed(200, 210),
])
}

Goals

intervalsets intends to provide flexible, reliable tools for working with intervals and numeric sets.

Correctness

None of the other goals matter if the results can't be trusted.

There is an extensive test suite to ensure that operations produce the intended results.

Generality

All set and interval types provided are generic over the type of element in the set.

Portability

These are low level abstractions which should be deployable in almost any environment.

intervalsets-core, by default, should be usable in any embedded environment - with or without an allocator. The crate does provide some optional features for externally defined element-types that require allocation. These must live in intervalsets-core due to rust's orphan rule since the required traits are defined there.

intervalsets should be usable in a no-std environment but does require an allocator to support collections of intervals.

Robustness

Fault tolerance is critical, especially in embedded environments.

Performance

todo:

Ease of use

todo:

Types

Errors

#![allow(unused)]
fn main() {
println!("hello world");
}

Footguns

Normalized Conversions

Most of the time normalization is transparent to the user, but it is a potential source of error, particularly when converting types that have implicit open bounds.

#![allow(unused)]
fn main() {
use intervalsets_core::prelude::*;

let discrete = EnumInterval::open(0, 10);
assert_eq!(discrete.lval(), Some(&1));
assert_eq!(discrete.rval(), Some(&9));
assert_eq!(discrete, (0, 10).into());
assert_eq!(discrete, [1, 9].into());
}

Floating Point Types

Making Ord a trait bound for most APIs would eliminate a whole class of errors (TotalOrderError), but floats come with a whole host of complexities regardless.

• NAN is not part of the default ordering, though there is a total_cmp available now.
• rounding error can cause issues with testing values near a finite bound.
• FiniteBound(f32::INFINITY) and FiniteBound(f32::NEG_INFINITY)are both valid syntax, though all manner of headache inducing semantically speaking.

Sometimes, floats are still the right tool for the job, and it is left to the user to choose the right approach for the given problem. Fixed precision decimal types like rust_decimal do side step some pitfalls.

Fallibility

#![allow(unused)]
fn main() {
use intervalsets_core::prelude::*;

let x = FiniteInterval::open(1.0, 0.0);
assert_eq!(x, FiniteInterval::empty());

// total order error -> panic
// infallible for properly implemented [`Ord`] types.
let result = std::panic::catch_unwind(|| {
    FiniteInterval::open(f32::NAN, 0.0);
});
assert!(result.is_err());

let x = FiniteInterval::strict_open(f32::NAN, 0.0);
assert_eq!(x.is_err(), true);

let x = FiniteInterval::strict_open(1.0, 0.0);
assert_eq!(x.unwrap(), FiniteInterval::empty());
}

Silent failures can make it difficult to isolate logic errors as they are able to propogate further from their source before detection.

#![allow(unused)]
fn main() {
use intervalsets_core::prelude::*;
let interval = EnumInterval::closed(0, 10);

let oops = interval
    .with_left_closed(20) // empty here
    .with_right(None);
assert_ne!(oops, EnumInterval::closed_unbound(20));
assert_eq!(oops, EnumInterval::empty());

let fixed = interval.with_right(None).with_left_closed(20);
assert_eq!(fixed, EnumInterval::closed_unbound(20));
}