Superintervals rust API

Superintervals implements IntervalMap which is a multimap like data structure for interval intersection queries. 'Keys' correspond to start and end coordinates of reference intervals of type i32. 'Values' are your data of interest of type T.

Add to your project using cargo add superintervals

use superintervals::IntervalMap;

let mut imap = IntervalMap::new();
imap.add(1, 5, "A");
imap.build();

// Collect results into a Vec
let mut results = Vec::new();
imap.search_values(4, 11, &mut results);

// Or use lazy iterator interfaces
for value in imap.search_values_iter(query_start, query_end) {
    println!("Found: {}", value);
}

API Reference

IntervalMap struct (also IntervalMapEytz for Eytzinger layout):

• fn new() -> Self
  Create new IntervalMap

• fn add(&mut self, start: i32, end: i32, value: T)
  Add interval with associated value

• fn build(&mut self)
  Build index (required before queries)

• fn clear(&mut self)
  Remove all intervals

• fn reserve(&mut self, n: usize)
  Reserve space for n intervals

• fn size(&self) -> usize
  Get number of intervals

• fn at(&self, index: usize) -> Interval<T>
  Get Interval at index

• fn has_overlaps(&mut self, start: i32, end: i32) -> bool
  Check if any intervals overlap range

• fn count(&mut self, start: i32, end: i32) -> usize
  Count overlapping intervals (SIMD optimized)

• fn count_linear(&mut self, start: i32, end: i32) -> usize
  Count overlapping intervals (linear)

• fn count_large(&mut self, start: i32, end: i32) -> usize
  Count optimized for large ranges

• fn search_values(&mut self, start: i32, end: i32, found: &mut Vec<T>)
  Fill vector with values of overlapping intervals

• fn search_values_large(&mut self, start: i32, end: i32, found: &mut Vec<T>)
  Search optimized for large ranges

• fn search_idxs(&mut self, start: i32, end: i32, found: &mut Vec<usize>)
  Fill vector with indices of overlapping intervals

• fn search_keys(&mut self, start: i32, end: i32, found: &mut Vec<(i32, i32)>)
  Fill vector with (start,end) pairs

• fn search_items(&mut self, start: i32, end: i32, found: &mut Vec<Interval<T>>)
  Fill vector with Interval objects

• fn search_stabbed(&mut self, point: i32, found: &mut Vec<T>)
  Find intervals containing single point

• fn coverage(&mut self, start: i32, end: i32) -> (usize, i32)
  Get (count, total_coverage) for range

• fn search_idxs_iter(&mut self, start: i32, end: i32) -> IndexIterator<T>
  Iterator over indices

• fn search_items_iter(&mut self, start: i32, end: i32) -> ItemIterator<T>
  Iterator over intervals

• fn search_keys_iter(&mut self, start: i32, end: i32) -> KeyIterator<T>
  Iterator over keys

• fn search_values_iter(&mut self, start: i32, end: i32) -> ValueIterator<T>
  Iterator over values

Set Operations

These build new disjoint interval sets from one or two maps. Results are returned unindexed — call build() on the result before querying it (or before passing it as other to another set operation). The _with variants take a closure FnMut(&T, &T) -> T to decide which value survives when intervals merge; the plain variants default to keeping the first.

let mut a = IntervalMap::new();
let mut b = IntervalMap::new();
// ... add() intervals to both ...
a.build();
b.build();

let mut merged = a.merge_overlaps();   // collapse self-overlaps
let u          = a.union(&b);          // a ∪ b
let i          = a.intersection(&b);   // a ∩ b
let d          = a.difference(&b);     // a \ b
merged.build();                        // build() before querying a result

• fn merge_overlaps(&self) -> IntervalMap<T>
  Collapse self-overlapping intervals into a disjoint set

• fn merge_overlaps_with<F: FnMut(&T,&T)->T>(&self, combine: F) -> IntervalMap<T>
  As above, with a custom value combiner

• fn gaps(&self, lo: i32, hi: i32, fill: T) -> IntervalMap<T>
  Uncovered regions within [lo, hi]

• fn union(&self, other: &IntervalMap<T>) -> IntervalMap<T>
  Union of the two sets (also union_with with a combiner)

• fn intersection(&self, other: &IntervalMap<T>) -> IntervalMap<T>
  Intersection of the two sets (also intersection_with with a combiner)

• fn difference(&self, other: &IntervalMap<T>) -> IntervalMap<T>
self \ other

• fn symmetric_difference(&self, other: &IntervalMap<T>) -> IntervalMap<T>
  Regions in exactly one of the two sets

• fn span(&self) -> Option<(i32, i32)>
(min start, max end), or None if empty