Struct nonoverlapping_interval_tree::NonOverlappingIntervalTree

source · [−]

pub struct NonOverlappingIntervalTree<K, V> { /* private fields */ }

Expand description

An implementation of a non-overlapping interval tree.

Keys are ranges, Range, and values are stored for a given range. Ranges inside the tree map not overlap, and the insert function enforces this. Internally managed by a BTreeMap.

Implementations

source

impl<K, V> NonOverlappingIntervalTree<K, V>

source

pub fn new() -> Self

Construct a new non-overlapping interval tree.

source

impl<K: Ord + Clone, V> NonOverlappingIntervalTree<K, V>

source

pub unsafe fn insert(&mut self, int: Range<K>, val: V) -> Option<V>

Insert a value into the tree for a given range, not checking to see if any overlapping occurs. If there’s an element whose range starts with int’s start, that element is removed and returned.

Safety

This function can potentially corrupt the tree, since the normal operation functions rely on there being no overlaps. Care must be taken when using this function to ensure the no-overlap property manually.

source

pub fn insert_replace(&mut self, int: Range<K>, val: V) -> Vec<(Range<K>, V)>

Insert a value into the tree for a given range, removing and returning all K,V pairs that are in the tree that overlap with the inserted range.

Examples

use nonoverlapping_interval_tree::NonOverlappingIntervalTree;
let mut it = NonOverlappingIntervalTree::new();
it.insert_replace(1..3, "hello");

source

pub fn get(&self, point: &K) -> Option<&V>

Get an immutable reference to the value of a single point in the interval tree, returning the value for a range that contains this point if one exists.

source

pub fn get_mut(&mut self, point: &K) -> Option<&mut V>

Get a mutable reference to the value of a single point in the interval tree, returning the value for a range that contains this point if one exists.

source

pub fn remove(&mut self, point: &K) -> Option<V>

Remove the value associated with the range that contains the point argument. If one is present, it is removed and returned, otherwise None is returned.

source

pub fn range(&self, range: Range<K>) -> ValueRange<'_, K, IntervalValue<K, V>>ⓘ
Notable traits for Range<'a, K, V>
`impl<'a, K, V> Iterator for Range<'a, K, V> type Item = (&'a K, &'a V);`

Returns a double-ended iterator over a sub-range of elements in the map. The resulting range may contain individual points that are not in the provided range if the stored ranges overlap with the terminating point. For example, if the tree contains [[1..3], [4..6]], and you call tree.range(1..5), you’ll get back [[1..3], [4..6]], since the 4..6 range contains 4 as requested by the call to range.

source

pub fn range_mut(
&mut self,
range: Range<K>
) -> ValueRangeMut<'_, K, IntervalValue<K, V>>ⓘ
Notable traits for RangeMut<'a, K, V>
`impl<'a, K, V> Iterator for RangeMut<'a, K, V> type Item = (&'a K, &'a mut V);`

Returns a mutable double-ended iterator over a sub-range of elements in the map. The resulting range may contain individual points that are not in the provided range if the stored ranges overlap with the terminating point. For example, if the tree contains [[1..3], [4..6]], and you call tree.range(1..5), you’ll get back [[1..3], [4..6]], since the 4..6 range contains 4 as requested by the call to range.

source