intervalmap

A Rust library for working with sets and maps of intervals. Inspired by Boost.Icl.

What it does

IntervalSet stores non-overlapping intervals and automatically merges them when they touch or overlap:

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(5..15);  // merges into [0, 15)

assert!(set.contains(12));
assert_eq!(set.len(), 1);  // just one interval after merge

IntervalMap associates values with intervals. When you insert overlapping ranges, the new value takes over:

use intervalmap::IntervalMap;

let mut map = IntervalMap::new();
map.insert(0..10, "a");
map.insert(5..15, "b");

// Result: [0,5) -> "a", [5,15) -> "b"
assert_eq!(map.get(3), Some(&"a"));
assert_eq!(map.get(7), Some(&"b"));

Adjacent intervals with the same value get merged automatically.

Macros

use intervalmap::{interval_set, interval_map};

let set = interval_set!{ 0..10, 20..30, 40..50 };
let map = interval_map!{ 0..10 => "first", 20..30 => "second" };

Range types

All standard Rust range types work:

set.insert(0..10);       // [0, 10)
set.insert(0..=10);      // [0, 11)
set.insert(10..);        // [10, MAX)
set.insert(..10);        // [MIN, 10)
set.insert(..);          // [MIN, MAX)

Set operations

IntervalSet supports the usual set operations:

let a = interval_set!{ 0..10, 20..30 };
let b = interval_set!{ 5..25 };

let union = &a | &b;              // or a.union(&b)
let intersection = &a & &b;       // or a.intersection(&b)
let difference = &a - &b;         // or a.difference(&b)
let symmetric_diff = &a ^ &b;     // or a.symmetric_difference(&b)

Other useful bits

// Query methods
set.first();              // lowest interval
set.last();               // highest interval
set.span();               // bounding range from first.start to last.end
set.overlaps(5..15);      // does any interval overlap this range?
set.covers(5..15);        // is the entire range covered?

// Iteration
set.gaps();               // iterate over gaps between intervals
set.iter_overlapping(5..25);  // only intervals that overlap the range

// Modification
set.retain(|r| r.start >= 10);  // filter intervals
set.split_at(50);               // split interval containing this point

Index types

The default index type is u32, but any primitive integer works:

let set: IntervalSet<i64> = IntervalSet::new();
let set: IntervalSet<u8> = IntervalSet::new();

License

MIT