Crate intervalsets

intervalsets: Intervals as Sets in Rust

Intervalsets intends to provide the full functionality of sets for interval data.

• The Interval type is a Set implementation representing a contiguous set of values.

  • It is generic over any type that implements the [Domain] trait which is intended to make sure elements are comparable and allows us to differentiate between discrete and continuous data types.

• The IntervalSet type is a Set of disjoint, normalized Intervals maintained in sorted order.

Overview

Interval and IntervalSet are intended to be simple, versatile, and correct. If you find any bugs, please open an issue on the repository or open a pull request.

These types are immutable and as such can be easily be used in a multi-threaded environment, or as keys in hash-structures as long as the underlying generic type is Hash.

The vast majority of interactions with these Set types is governed by trait implementations in the ops module.

Getting Started

Constructing Sets

use intervalsets::prelude::*;
use intervalsets::{Bound, Side};

let x = Interval::closed(0, 10);
assert_eq!(x.is_empty(), false);
assert_eq!(x.is_finite(), true);
assert_eq!(x.is_fully_bounded(), true);
assert_eq!(*x.right().unwrap(), Bound::closed(10));
assert_eq!(*x.rval().unwrap(), 10);
assert_eq!(format!("x = {}", x), "x = [0, 10]");

let x = Interval::closed_unbound(0.0);
assert_eq!(x.right(), None);
assert_eq!(x.is_half_bounded(), true);
assert_eq!(x.is_half_bounded_on(Side::Left), true);

let x = Interval::closed_open(-100.0, -50.0);
assert_eq!(*x.right().unwrap(), Bound::open(-50.0));

let y = Interval::convex_hull([5.0, 10.0, 23.0, -3.0, 22.0, 9.0, 99.9]);
assert_eq!(y, Interval::closed(-3.0, 99.9));

let iset = IntervalSet::from_iter([x, y]);
assert_eq!(iset.intervals().len(), 2);

Set Operations

use intervalsets::prelude::*;

let x = Interval::closed(0.0, 100.0);
let y = Interval::closed(1000.0, 1100.0);
let z = Interval::open(2000.0, 2100.0);

let a = Interval::<f64>::unbounded()
    .difference(&x)
    .difference(&y)
    .difference(&z);

assert_eq!(a.contains(&50.0), false);

let b = x.union(&y).union(&z).complement();
assert_eq!(a, b);

let c = a.sym_difference(&b).expect_interval();
assert_eq!(c, Interval::<f64>::empty());

General Mapping

use intervalsets::prelude::*;

let x = Interval::closed(1, 5);
let y = x.flat_map_finite(|left, right| {
    Interval::new_finite(left.map(|v| 10 * v), right.map(|v| 20 * v))
});
assert_eq!(y, Interval::closed(10, 100));

let z = IntervalSet::from_iter([x.clone(), y.clone()]);
let z = z.collect_map(|mut sets, subset| {
    let mirror_image = subset.flat_map_finite(|left, right| {
        Interval::new_finite(right.map(|v| -v), left.map(|v| -v))
    });
    sets.push(mirror_image);
    sets.push(subset.clone());
});
assert_eq!(z, IntervalSet::from_iter([
    x,
    y,
    Interval::closed(-5, -1),
    Interval::closed(-100, -10),
]));

Measure of a Set

Two measures are provided.

They each return a Measurement which may be infinite.

Width for continuous data types

use intervalsets::prelude::*;

let x = Interval::open(0.0, 10.0);
assert_eq!(x.width().finite(), 10.0);

let x = Interval::closed(0.0, 10.0);
assert_eq!(x.width().finite(), 10.0);

let x = Interval::closed_unbound(0.0);
assert_eq!(x.width().is_finite(), false);

Count for discrete data types

use intervalsets::prelude::*;

let x = Interval::closed(0, 10);
assert_eq!(x.count().finite(), 11);

let x = Interval::closed_unbound(0);
assert_eq!(x.count().is_finite(), false);

Optional Features

intervalsets has multiple Cargo features for controlling the underlying data types used by Interval and IntervalSet. None are enabled by default

• rust_decimal
• num-bigint
• chrono
• uom

Custom Data Types

If you have a data type that is not currently supported by intervalsets out of the box, there are a few traits that need to be implemented in order to get started.

Firstly, does your library or application own the type you want to use? Yes? Great! Skip Ahead

External Type Conflicts

Rust doesn’t allow us to implement traits for types if we don’t own at least one of them for fear that a future upstream change will introduce ambiguity. The solution to which is the New Type Idiom.

So, we need to proxy whatever type we want to work with.

use num_bigint::BigInt;
pub struct MyBigInt(BigInt);

// implement all the traits...

Required Custom Type Traits

intervalsets uses a handful of traits to fully define interval and set behavior.

• Domain

The Domain trait serves one purpose – to distinguish between types that represent discrete vs continuous data.

This allows us to do two important things:

1. Normalize discrete sets so that there is only a single valid representations of each possible Set. eg. [1, 9] == (0, 10) == (0, 9] == [1, 10).
2. Properly test the adjacency of sets.

The method try_adjacent is the mechanism by which both of these goals is accomplished. Implementations for continuous types should simply return None.

The macro continuous_domain_impl exists for exactly this purpose.

• LibZero

The LibZero trait is a direct knock-off of Zero. However, it is necessary to resolve issues of external traits and types. If a type already implements Zero the macro adapt_num_traits_zero_impl can be used directly.

The LibZero trait is necessary for the measure module, specifically in regards to the empty set.

• Countable

The Countable trait is only relevant to discrete data types. It is the mechanism by which a data type can say how many distinct values fall between some bounds of that type. There is a macro default_countable_impl which uses try_adjacent.

• Add and Sub

The Add and Sub traits are used by the measure module, and could be used elsewhere in the future. Presumably these are already implemented for most types that one would want to use as bounds of a Set.

Putting it all together

use core::ops::{Add, Sub};
use intervalsets::numeric::{Domain, LibZero};
use intervalsets::measure::Countable;
use intervalsets::Side;

// minimum required is: Clone, PartialEq, PartialOrd
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct MyInt(i32);

impl Domain for MyInt {
    fn try_adjacent(&self, side: Side) -> Option<Self> {
        Some(match side {
            Side::Left => Self(self.0 - 1),
            Side::Right => Self(self.0 + 1),
        })
    }
}

// MyInt does not already implement num_traits::Zero
// so the adapt_num_traits_zero_impl doesn't help us here,
// even though i32 does.
impl LibZero for MyInt {
    fn new_zero() -> Self {
        Self(0)
    }
}

// The default_countable_impl macro would work here just fine.
// This would be omitted for a continuous data type.
impl Countable for MyInt {
    type Output = Self;
    fn count_inclusive(left: &Self, right: &Self) -> Option<Self::Output> {
        Some(Self(right.0 - left.0 + 1))
    }
}

impl Add for MyInt {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self(self.0 + rhs.0)
    }
}

impl Sub for MyInt {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        Self(self.0 - rhs.0)
    }
}

Modules

measure

A Measure is a function of a set that gives a comparable size between sets.

numeric

Control behavior of data types that comprise the elements of a set.

ops

Operations on Set types.

prelude

Common operations & traits

Macros

adapt_num_traits_zero_impl

Create LibZero impl(s) that delegate to num_traits::Zero

continuous_domain_impl

Automatically implements Domain for a type.

default_countable_impl

Structs

Bound

Defines the Bound or limit that constrains a Set.

Interval

A Set representation of a contiguous interval on N, Z, or R.

IntervalSet

A Set in N, Z, or R consisting of disjoint contiguous intervals.

Enums

BoundType

The BoundType determines the inclusivity of the limit element in a set.

Side

Side( Left | Right ) on the number line.

Traits

Bounding

The boundaries of a Set on the number line.

ConvexHull

Defines the minimal contiguous Interval which fully contains every provided item.

MaybeEmpty

Defines an item that may be empty and a way to query it.