Struct iset::IntervalMap

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

Map with interval keys (x..y).

Range bounds should implement PartialOrd and Copy, for example any integer or float types. However, you cannot use values that cannot be used in comparison (such as NAN), although infinity is allowed. There are no restrictions on values.

Example

 let mut map = iset::interval_map!{ 20..30 => 'a', 15..25 => 'b', 10..20 => 'c' };
 assert_eq!(map.insert(10..20, 'd'), Some('c'));
 assert_eq!(map.insert(5..15, 'e'), None);

 // Iterator over all pairs (range, value). Output is sorted.
 let a: Vec<_> = map.iter(..).collect();
 assert_eq!(a, &[(5..15, &'e'), (10..20, &'d'), (15..25, &'b'), (20..30, &'a')]);

 // Iterate over intervals that overlap query (..20 here). Output is sorted.
 let b: Vec<_> = map.intervals(..20).collect();
 assert_eq!(b, &[5..15, 10..20, 15..25]);

 assert_eq!(map[15..25], 'b');
 // Replace 15..25 => 'b' into 'z'.
 *map.get_mut(15..25).unwrap() = 'z';

 // Iterate over values that overlap query (20.. here). Output is sorted by intervals.
 let c: Vec<_> = map.values(20..).collect();
 assert_eq!(c, &[&'z', &'a']);

 // Remove 10..20 => 'd'.
 assert_eq!(map.remove(10..20), Some('d'));

Insertion, search and removal

All three operations take O(log N). By default, this crate does not allow duplicate keys, insert replaces and returns the old value if the interval was already present in the map. Note, that the key is not updated even if the value is replaced. This matters for types that can be == without being identical.

Search operations contains, get and get_mut is usually faster than insertion or removal, as the tree does not need to be rebalanced.

You can remove nodes from the tree using remove method given the interval key. Currently, it is not feasible to have a method that removes multiple nodes at once (for example based on a predicate).

It is possible to store entries with equal intervals by calling force_insert. This method should be used with care, as methods get, get_mut and remove only return/remove a single entry (see force_insert for more details). Nevertheless, functions values_at and values_mut_at allow to iterate over all values with exactly matching query, and remove_where allows to remove an entry with matching interval based on a predicate.

Additionally, it is possible to get or remove the entry with the smallest/largest interval in the map (in lexicographical order), see smallest, largest, etc. These methods take O(log N) as well.

Method range allows to extract interval range (min_start, max_end) in O(1). Method covered_len is designed to calculate the total length of a query that is covered by the intervals in the map. Method has_overlap allows to quickly find if the query overlaps any intervals in the map.

Iteration

Interval map allows to quickly find all intervals that overlap a query interval in O(log N + K) where K is the size of the output. All iterators traverse entries in a sorted order (sorted lexicographically by intervals). Iteration methods include:

• iter: iterate over pairs (x..y, &value),
• intervals: iterate over interval keys x..y,
• values: iterate over values &value,
• Mutable iterators iter_mut and values_mut,
• Into iterators into_iter, into_intervals and into_values,
• Iterators over values with exactly matching intervals values_at and values_mut_at.

Additionally, most methods have their unsorted_ counterparts (for example unsorted_iter). These iterators traverse the whole map in an arbitrary unsorted order. Although both map.iter(..) and map.unsorted_iter() output all entries in the map and both take O(N), unsorted iterator is slightly faster as it reads the memory consecutively instead of traversing the tree.

Methods iter, intervals, values, iter_mut and values_mut have alternatives overlap, overlap_intervals, …, that allow to iterate over all entries that cover a single point x (same as x..=x).

Index types

Every node in the tree stores three indices (to the parent and two children), and as a result, memory usage can be reduced by reducing index sizes. In most cases, number of items in the map does not exceed u32::MAX, therefore we store indices as u32 numbers by default (iset::DefaultIx = u32). You can use four integer types (u8, u16, u32 or u64) as index types. Number of elements in the interval map cannot exceed IndexType::MAX - 1: for example a map with u8 indices can store up to 255 items.

Using smaller index types saves memory and may reduce running time.

Interval map creation

An interval map can be created using the following methods:

use iset::{interval_map, IntervalMap};

// Creates an empty interval map with the default index type (u32):
let mut map = IntervalMap::new();
map.insert(10..20, 'a');

// Creates an empty interval map and specifies index type (u16 here):
let mut map = IntervalMap::<_, _, u16>::default();
map.insert(10..20, 'a');

let mut map = IntervalMap::<_, _, u16>::with_capacity(10);
map.insert(10..20, 'a');

// Creates an interval map with the default index type:
let map = interval_map!{ 0..10 => 'a', 5..15 => 'b' };

// Creates an interval map and specifies index type:
let map = interval_map!{ [u16] 0..10 => 'a', 5..15 => 'b' };

// Creates an interval map from a sorted iterator, takes O(N):
let vec = vec![(0..10, 'b'), (5..15, 'a')];
let map = IntervalMap::<_, _, u32>::from_sorted(vec.into_iter());

// Alternatively, you can use `.collect()` method that creates an interval map
// with the default index size. `Collect` does not require sorted intervals,
// but takes O(N log N).
let vec = vec![(5..15, 'a'), (0..10, 'b')];
let map: IntervalMap<_, _> = vec.into_iter().collect();

Entry API

IntervalMap implements Entry, for updating and inserting values directly after search was made.

let mut map = iset::IntervalMap::new();
map.entry(0..100).or_insert("abc".to_string());
map.entry(100..200).or_insert_with(|| "def".to_string());
let val = map.entry(200..300).or_insert(String::new());
*val += "ghi";
map.entry(200..300).and_modify(|s| *s += "jkl").or_insert("xyz".to_string());

assert_eq!(map[0..100], "abc");
assert_eq!(map[100..200], "def");
assert_eq!(map[200..300], "ghijkl");

Implementation, merge and split

To allow for fast retrieval of all intervals overlapping a query, we store the range of the subtree in each node of the tree. Additionally, each node stores indices to the parent and to two children. As a result, size of the map is approximately n * (4 * sizeof(T) + sizeof(V) + 3 * sizeof(Ix)), where n is the number of elements.

In order to reduce number of heap allocations and access memory consecutively, we store tree nodes in a vector. This does not impact time complexity of all methods except for merge and split. In a heap-allocated tree, merge takes O(M log (N / M + 1)) where M is the size of the smaller tree. Here, we are required to merge sorted iterators and construct a tree using the sorted iterator as input, which takes O(N + M).

Because of that, this crate does not implement merge or split, however, these procedures can be emulated using from_sorted, itertools::merge and Iterator::partition in linear time.

Implementations

impl<T: PartialOrd + Copy, V> IntervalMap<T, V>

pub fn new() -> Self

Creates an empty IntervalMap with default index type DefaultIx.

impl<T: PartialOrd + Copy, V, Ix: IndexType> IntervalMap<T, V, Ix>

pub fn with_capacity(capacity: usize) -> Self

Creates an empty IntervalMap with capacity.

pub fn from_sorted<I>(iter: I) -> Selfwhere I: Iterator<Item = (Range<T>, V)>,

Creates an interval map from a sorted iterator over pairs (range, value). Takes O(N).

Panics if the intervals are not sorted or if there are equal intervals.

pub fn len(&self) -> usize

Returns the number of elements in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn clear(&mut self)

Clears the map, removing all values. This method has no effect on the allocated capacity.

pub fn shrink_to_fit(&mut self)

Shrinks inner contents.

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

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

let mut counts = iset::IntervalMap::new();
for x in [0..5, 3..9, 2..6, 0..5, 2..6, 2..6] {
    counts.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
}
assert_eq!(counts[0..5], 2);
assert_eq!(counts[3..9], 1);
assert_eq!(counts[2..6], 3);

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

Inserts an interval x..y and its value into the map. Takes O(log N).

If the map did not contain the interval, returns None. Otherwise returns the old value.

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

pub fn force_insert(&mut self, interval: Range<T>, value: V)

Inserts an interval x..y and its value into the map even if there was an entry with matching interval. Takes O(log N).

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

Warning: After force_insert, the map can contain several entries with equal intervals.
Calling get, get_mut or remove
will arbitrarily
return/remove only one of the entries.
Various iterators will output all appropriate intervals, however the order of entries with equal intervals
will be arbitrary.

let mut map = iset::interval_map!{};
map.force_insert(10..20, 1);
map.force_insert(15..25, 2);
map.force_insert(20..30, 3);
map.force_insert(15..25, 4);

// Returns either 2 or 4.
assert!(map.get(15..25).unwrap() % 2 == 0);
// Removes either 15..25 => 2 or 15..25 => 4.
assert!(map.remove(15..25).unwrap() % 2 == 0);
println!("{:?}", map);
// {10..20 => 1, 15..25 => 4, 20..30 => 3} OR
// {10..20 => 1, 15..25 => 2, 20..30 => 3}

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

Check if the interval map contains interval (exact match).

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

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

Returns value associated with interval (exact match). If there is no such interval, returns None.

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

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

Returns mutable value associated with interval (exact match). If there is no such interval, returns None.

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

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

Removes an entry, associated with interval (exact match is required), takes O(log N). Returns value if the interval was present in the map, and None otherwise.

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

pub fn remove_where( &mut self, interval: Range<T>, predicate: impl FnMut(&V) -> bool ) -> Option<V>

Removes an entry, associated with interval (exact match is required), where predicate(&value) returns true. After predicate returns true, it is not invoked again. Returns the value of the removed entry, if present, and None otherwise.

Takes O(log N + K) where K is the number of entries with interval.

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

Examples

let mut map = iset::IntervalMap::new();
map.force_insert(5..15, 0);
map.force_insert(10..20, 1);
map.force_insert(10..20, 2);
map.force_insert(10..20, 3);
map.force_insert(10..20, 4);
map.force_insert(15..25, 5);

// Remove an entry with an even value
let removed = map.remove_where(10..20, |&x| x % 2 == 0);
assert!(removed == Some(2) || removed == Some(4));

// Remove the entry with the minimum value
let minimum = map.values_at(10..20).cloned().min().unwrap();
assert_eq!(minimum, 1);
let removed = map.remove_where(10..20, |&x| x == minimum);
assert_eq!(removed, Some(1));
assert_eq!(map.len(), 4);

pub fn range(&self) -> Option<Range<T>>

Returns a range of interval keys in the map, takes O(1). Returns None if the map is empty. out.start is the minimal start of all intervals in the map, and out.end is the maximal end of all intervals in the map.

pub fn smallest(&self) -> Option<(Range<T>, &V)>

Returns the pair (x..y, &value) with the smallest interval x..y (in lexicographical order). Takes O(log N). Returns None if the map is empty.

pub fn smallest_mut(&mut self) -> Option<(Range<T>, &mut V)>

Returns the pair (x..y, &mut value) with the smallest interval x..y (in lexicographical order). Takes O(log N). Returns None if the map is empty.

pub fn remove_smallest(&mut self) -> Option<(Range<T>, V)>

Removes the smallest interval x..y (in lexicographical order) from the map and returns pair (x..y, value). Takes O(log N). Returns None if the map is empty.

pub fn largest(&self) -> Option<(Range<T>, &V)>

Returns the pair (x..y, &value) with the largest interval x..y (in lexicographical order). Takes O(log N). Returns None if the map is empty.

pub fn largest_mut(&mut self) -> Option<(Range<T>, &mut V)>

Returns the pair (x..y, &mut value) with the largest interval x..y (in lexicographical order). Takes O(log N). Returns None if the map is empty.

pub fn remove_largest(&mut self) -> Option<(Range<T>, V)>

Removes the largest interval x..y (in lexicographical order) from the map and returns pair (x..y, value). Takes O(log N). Returns None if the map is empty.

pub fn has_overlap<R>(&self, query: R) -> boolwhere R: RangeBounds<T>,

Checks, if the query overlaps any intervals in the interval map. Equivalent to map.iter(query).next().is_some(), but much faster.

let map = iset::interval_map!{ 5..8 => 'a', 10..15 => 'b' };
assert!(!map.has_overlap(8..10));
assert!(map.has_overlap(8..=10));

pub fn iter<'a, R>(&'a self, query: R) -> Iter<'a, T, V, R, Ix> where R: RangeBounds<T>,

Iterates over pairs (x..y, &value) that overlap the query. Takes O(log N + K) where K is the size of the output. Output is sorted by intervals, but not by values.

Panics if interval is empty or contains a value that cannot be compared (such as NAN).

pub fn intervals<'a, R>(&'a self, query: R) -> Intervals<'a, T, V, R, Ix> where R: RangeBounds<T>,

Iterates over intervals x..y that overlap the query. See iter for more details.

pub fn values<'a, R>(&'a self, query: R) -> Values<'a, T, V, R, Ix> where R: RangeBounds<T>,

Iterates over values that overlap the query. See iter for more details.

pub fn iter_mut<'a, R>(&'a mut self, query: R) -> IterMut<'a, T, V, R, Ix> where R: RangeBounds<T>,

Iterator over pairs (x..y, &mut value) that overlap the query. See iter for more details.

pub fn values_mut<'a, R>(&'a mut self, query: R) -> ValuesMut<'a, T, V, R, Ix> where R: RangeBounds<T>,

Iterator over mutable values that overlap the query. See iter for more details.

pub fn into_iter<R>(self, query: R) -> IntoIter<T, V, R, Ix> where R: RangeBounds<T>,

Consumes IntervalMap and iterates over pairs (x..y, value) that overlap the query. See iter for more details.

pub fn into_intervals<R>(self, query: R) -> IntoIntervals<T, V, R, Ix> where R: RangeBounds<T>,

Consumes IntervalMap and iterates over pairs (x..y, value) that overlap the query. See iter for more details.

pub fn into_values<R>(self, query: R) -> IntoValues<T, V, R, Ix> where R: RangeBounds<T>,

Consumes IntervalMap and iterates over values, for which intervals that overlap the query. See iter for more details.

pub fn overlap<'a>(&'a self, point: T) -> Iter<'a, T, V, RangeInclusive<T>, Ix>

Iterates over pairs (x..y, &value) that overlap the point. See iter for more details.

pub fn intervals_overlap<'a>( &'a self, point: T ) -> Intervals<'a, T, V, RangeInclusive<T>, Ix>

Iterates over intervals x..y that overlap the point. See iter for more details.

pub fn values_overlap<'a>( &'a self, point: T ) -> Values<'a, T, V, RangeInclusive<T>, Ix>

Iterates over values that overlap the point. See iter for more details.

pub fn overlap_mut<'a>( &'a mut self, point: T ) -> IterMut<'a, T, V, RangeInclusive<T>, Ix>

Iterator over pairs (x..y, &mut value) that overlap the point. See iter for more details.

pub fn values_overlap_mut<'a>( &'a mut self, point: T ) -> ValuesMut<'a, T, V, RangeInclusive<T>, Ix>

Iterates over mutable values that overlap the point. See iter for more details.

pub fn values_at<'a>(&'a self, query: Range<T>) -> ValuesExact<'a, T, V, Ix>

Iterates over all values (&V) with intervals that match query exactly. Takes O(log N + K) where K is the size of the output.

pub fn values_mut_at<'a>( &'a mut self, query: Range<T> ) -> ValuesExactMut<'a, T, V, Ix>

Iterates over all mutable values (&mut V) with intervals that match query exactly.

pub fn unsorted_iter<'a>(&'a self) -> UnsIter<'a, T, V, Ix>

Creates an unsorted iterator over all pairs (x..y, &value). Slightly faster than the sorted iterator, although both take O(N).

pub fn unsorted_intervals<'a>(&'a self) -> UnsIntervals<'a, T, V, Ix>

Creates an unsorted iterator over all intervals x..y.

pub fn unsorted_values<'a>(&'a self) -> UnsValues<'a, T, V, Ix>

Creates an unsorted iterator over all values &value.

pub fn unsorted_iter_mut<'a>(&'a mut self) -> UnsIterMut<'a, T, V, Ix>

Creates an unsorted iterator over all pairs (x..y, &mut value).

pub fn unsorted_values_mut<'a>(&'a mut self) -> UnsValuesMut<'a, T, V, Ix>

Creates an unsorted iterator over all mutable values &mut value.

pub fn unsorted_into_iter(self) -> UnsIntoIter<T, V, Ix>

Consumes IntervalMap and creates an unsorted iterator over all pairs (x..y, value).

pub fn unsorted_into_intervals(self) -> UnsIntoIntervals<T, V, Ix>

Consumes IntervalMap and creates an unsorted iterator over all intervals x..y.

pub fn unsorted_into_values(self) -> UnsIntoValues<T, V, Ix>

Consumes IntervalMap and creates an unsorted iterator over all values.

impl<T, V, Ix> IntervalMap<T, V, Ix>where T: PartialOrd + Copy + Default + AddAssign + Sub<Output = T>, Ix: IndexType,

pub fn covered_len<R>(&self, query: R) -> Twhere R: RangeBounds<T>,

Calculates the total length of the query that is covered by intervals in the map. Takes O(log N + K) where K is the number of intervals that overlap query.

This method makes two assumptions:

• T::default() is equivalent to 0, which is true for numeric types,
• Single-point intersections are irrelevant, for example intersection between [0, 1] and [1, 2] is zero, This also means that the size of the interval (0, 1) will be 1 even for integer types.

let map = iset::interval_map!{ 0..10 => 'a', 4..8 => 'b', 12..15 => 'c' };
assert_eq!(map.covered_len(2..14), 10);
assert_eq!(map.covered_len(..), 13);

Trait Implementations

impl<T: Clone, V: Clone, Ix: Clone + IndexType> Clone for IntervalMap<T, V, Ix>

fn clone(&self) -> IntervalMap<T, V, Ix>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: PartialOrd + Copy + Debug, V: Debug, Ix: IndexType> Debug for IntervalMap<T, V, Ix>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialOrd + Copy, V, Ix: IndexType> Default for IntervalMap<T, V, Ix>

fn default() -> Self

Returns the “default value” for a type.

impl<T: PartialOrd + Copy, V> FromIterator<(Range<T>, V)> for IntervalMap<T, V>

Construct IntervalMap from pairs (x..y, value).

Panics, if the iterator contains duplicate intervals.

fn from_iter<I>(iter: I) -> Selfwhere I: IntoIterator<Item = (Range<T>, V)>,

Creates a value from an iterator.

impl<T: PartialOrd + Copy, V, Ix: IndexType> Index<Range<T>> for IntervalMap<T, V, Ix>

type Output = V

The returned type after indexing.

fn index(&self, range: Range<T>) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T: PartialOrd + Copy, V, Ix: IndexType> IntoIterator for IntervalMap<T, V, Ix>

type IntoIter = IntoIter<T, V, RangeFull, Ix>

Which kind of iterator are we turning this into?

type Item = (Range<T>, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.