Struct IntervalMap

Source

pub struct IntervalMap<T, V, Ix = u32> { /* private fields */ }

Expand description

An interval-value map, which support operations on dynamic sets of intervals.

Implementations§

Source §

impl<T, V, Ix> IntervalMap<T, V, Ix>
where T: Ord, Ix: IndexType,

Source

pub fn with_capacity(capacity: usize) -> Self

Creates a new IntervalMap with estimated capacity.

Source

pub fn insert(&mut self, interval: Interval<T>, value: V) -> Option<V>

Insert an interval-value pair into the map. If the interval exists, overwrite and return the previous value.

§Panics

This method panics when the tree is at the maximum number of nodes for its index

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
assert_eq!(map.insert(Interval::new(1, 3), 1), None);
assert_eq!(map.insert(Interval::new(1, 3), 2), Some(1));
assert_eq!(map.insert(Interval::new(1, 3), 3), Some(2));

Source

pub fn remove(&mut self, interval: &Interval<T>) -> Option<V>

Remove an interval from the map, returning the value at the interval if the interval exists

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(1, 3), 1);
map.insert(Interval::new(2, 4), 2);
assert_eq!(map.len(), 2);
assert_eq!(map.remove(&Interval::new(3, 6)), None);
assert_eq!(map.len(), 2);
assert_eq!(map.remove(&Interval::new(2, 4)), Some(2));
assert_eq!(map.len(), 1);

Source

pub fn overlaps(&self, interval: &Interval<T>) -> bool

Check if an interval in the map overlaps with the given interval.

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(1, 3), ());
map.insert(Interval::new(6, 7), ());
map.insert(Interval::new(9, 11), ());
assert!(map.overlaps(&Interval::new(2, 5)));
assert!(map.overlaps(&Interval::new(1, 17)));
assert!(!map.overlaps(&Interval::new(3, 6)));
assert!(!map.overlaps(&Interval::new(11, 23)));

Source

pub fn find_all_overlap( &self, interval: &Interval<T>, ) -> Vec<(&Interval<T>, &V)>

Find all intervals in the map that overlaps with the given interval.

§Note

This method’s returned data is unordered. To get ordered data, please use find_all_overlap_ordered.

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(1, 3), ());
map.insert(Interval::new(2, 4), ());
map.insert(Interval::new(6, 7), ());
map.insert(Interval::new(7, 11), ());
assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 3);
map.remove(&Interval::new(1, 3));
assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 2);

Source

pub fn find_all_overlap_ordered<'a>( &'a self, interval: &'a Interval<T>, ) -> Vec<(&Interval<T>, &V)>

Find all intervals in the map that overlaps with the given interval.

§Note

This method’s returned data is ordered. Generally, it’s much slower than find_all_overlap.

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(1, 3), ());
map.insert(Interval::new(2, 4), ());
map.insert(Interval::new(6, 7), ());
map.insert(Interval::new(7, 11), ());
assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 3);
map.remove(&Interval::new(1, 3));
assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 2);

Source

pub fn get(&self, interval: &Interval<T>) -> Option<&V>

Return reference to the value corresponding to the key.

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(1, 3), 1);
map.insert(Interval::new(7, 11), 4);
assert_eq!(map.get(&Interval::new(1, 3)), Some(&1));
assert_eq!(map.get(&Interval::new(7, 11)), Some(&4));
assert_eq!(map.get(&Interval::new(5, 17)), None);

Source

pub fn get_mut(&mut self, interval: &Interval<T>) -> Option<&mut V>

Return a reference to the value corresponding to the key.

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(3, 5), 0);
map.get_mut(&Interval::new(3, 5)).map(|v| *v += 1);
assert_eq!(map.get(&Interval::new(3, 5)), Some(&1));

Source

pub fn iter(&self) -> Iter<'_, T, V, Ix> ⓘ

Get an iterator over the entries of the map, sorted by key.

Source

pub fn unsorted_iter(&self) -> UnsortedIter<'_, T, V, Ix> ⓘ

Get an iterator over the entries of the map, unsorted.

Source

pub fn filter_iter<'a, 'b: 'a>( &'a self, query: &'b Interval<T>, ) -> FilterIter<'_, T, V, Ix> ⓘ

Get an iterator over the entries that overlap the query, sorted by key.

§Panics

The method panics when query contains a value that cannot be compared.

Source

pub fn contains(&self, interval: &Interval<T>) -> bool

Return true if the interval tree’s key cover the entire given interval.

§Example

use rb_interval_map::{Interval, IntervalMap};

let mut map = IntervalMap::new();
map.insert(Interval::new(3, 5), 0);
map.insert(Interval::new(5, 8), 1);
map.insert(Interval::new(9, 12), 1);
assert!(map.contains(&Interval::new(4, 6)));
assert!(!map.contains(&Interval::new(7, 10)));

Source

pub fn entry(&mut self, interval: Interval<T>) -> Entry<'_, T, V, Ix>

Get the given key’s corresponding entry in the map for in-place manipulation.

§Example

use rb_interval_map::{Interval, IntervalMap, Entry};

let mut map = IntervalMap::new();

assert!(matches!(map.entry(Interval::new(1, 2)), Entry::Vacant(_)));
map.entry(Interval::new(1, 2)).or_insert(0);
assert!(matches!(map.entry(Interval::new(1, 2)), Entry::Occupied(_)));
map.entry(Interval::new(1, 2)).and_modify(|v| *v += 1);
assert_eq!(map.get(&Interval::new(1, 2)), Some(&1));