Crate irange 

A data structure to store and manipulate ranges of integers with set operations.

RangeSet holds an arbitrary set of integers as a sorted collection of non-overlapping inclusive ranges. It is compact for values that come in runs: a set such as “every codepoint that is a word character” costs a handful of bounds rather than one entry per value. It supports the usual set algebra: union, intersection, difference, complement, and the containment queries contains and contains_all.

Supported types: u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128 and isize.

Example

use irange::range::AnyRange;
use irange::RangeSet;

let range1 = RangeSet::<i64>::new_from_ranges(&[AnyRange::from(3..=4), AnyRange::from(7..9)]);
let range2 = RangeSet::<i64>::new_from_range(-2..=4);

assert_eq!("[ -2..=4 7..=8 ]", range1.union(&range2).to_string());
assert_eq!("[ 3..=4 ]", range1.intersection(&range2).to_string());
assert_eq!("[ 7..=8 ]", range1.difference(&range2).to_string());

let values: Vec<i64> = range1.union(&range2).iter().collect();
assert_eq!(vec![-2, -1, 0, 1, 2, 3, 4, 7, 8], values);

Representation

A RangeSet is a flat Vec of inclusive bounds: the elements at an even index are lower bounds and the elements at an odd index are the matching upper bounds, so [ 3..=4 7..=8 ] is stored as vec![3, 4, 7, 8].

Every set has exactly one such representation. The bounds are even in number, no range is inverted, and consecutive ranges are sorted and separated by at least one value, so two ranges that touch, like 1..=2 and 3..=4, are merged into 1..=4. The constructors maintain this invariant, and RangeSet::new_from_bounds checks it when you build a set from raw bounds. Writing to the public field directly bypasses the check and gives unspecified (but never panicking) results.

Complexity

n is the total number of ranges involved. Every operation makes a single ordered pass over the bounds, so nothing here is worse than linear.

Operation	Time	Space
union, intersection, difference, complement	O(n)	O(n)
has_intersection, contains_all	O(n)	O(1)
contains	O(log n)	O(1)
is_total, is_empty	O(1)	O(1)

Operators

The four operations that build a new set also have an operator, taking references like those of BTreeSet: | for union, & for intersection, - for difference and ! for complement.

use irange::RangeSet;

let a = RangeSet::new_from_range(3..=8);
let b = RangeSet::new_from_range(7..=12);

assert_eq!(a.union(&b), &a | &b);
assert_eq!(a.intersection(&b), &a & &b);
assert_eq!(a.difference(&b), &a - &b);
assert_eq!(a.complement(), !&a);

Iteration

RangeSet::iter walks the individual values in order, and &RangeSet implements IntoIterator, so a for loop over a set works directly. The iterator is double-ended, so rev walks the values from the largest down.

use irange::RangeSet;

let range = RangeSet::new_from_range(2..=5);

let ascending: Vec<i32> = (&range).into_iter().collect();
assert_eq!(vec![2, 3, 4, 5], ascending);

let descending: Vec<i32> = range.iter().rev().collect();
assert_eq!(vec![5, 4, 3, 2], descending);

Feature flags

• serde: implement Serialize and Deserialize for RangeSet, using the flat list of bounds as the serialized form. Deserializing validates the invariant above and fails with a descriptive error rather than accepting a malformed set.

Modules

integer

The integer types a RangeSet can hold.

range

A single range of integers, used to build a RangeSet.

Structs

RangeSet

A structure holding a collection of u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128 or isize.

RangeSetIter

A structure to hold the iterator of a RangeSet instance.