Struct NonOverlappingIntervalTree

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

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

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

pub fn new() -> Self

Construct a new non-overlapping interval tree.

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

pub 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.

Note

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.

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");

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.

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.

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.

pub fn range(&self, range: Range<K>) -> ValueRange<'_, K, IntervalValue<K, 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.

pub fn range_mut( &mut self, range: Range<K>, ) -> ValueRangeMut<'_, K, IntervalValue<K, 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.

pub fn clear(&mut self)

Remove all elements in the tree.

pub fn iter(&self) -> Iter<'_, K, IntervalValue<K, V>>

Return an iterator for the tree, sorted by key.

pub fn iter_mut(&mut self) -> IterMut<'_, K, IntervalValue<K, V>>

Return an iterator for the tree, sorted by key.

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.

Trait Implementations

impl<K: Clone, V: Clone> Clone for NonOverlappingIntervalTree<K, V>

fn clone(&self) -> NonOverlappingIntervalTree<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for NonOverlappingIntervalTree<K, V>

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

Formats the value using the given formatter.

impl<K, V> Default for NonOverlappingIntervalTree<K, V>

fn default() -> Self

Returns the “default value” for a type.