Expand description
A no-std friendly non-overlapping interval tree.
The tree maintains a set of elements that can be indexed by key, where the key is a range. Lookup queries return the value of a range if the lookup key is contained within the range.
This tree requires all elements’ ranges be non-overlapping, which is enforced by the insert_replace function. As a result, the insert_replace function has some extra runtime overhead, scaling with the number of current elements keyed by ranges that overlap with the range we are inserting. For faster insert, an unsafe insert function exists, where the caller is expected to ensure the non-overlapping property themselves.
To use the no-std version, turn off default features.
Examples
use nonoverlapping_interval_tree::NonOverlappingIntervalTree;
let mut it = NonOverlappingIntervalTree::new();
it.insert_replace(1..3, "hello");
assert_eq!(it.get(&2), Some(&"hello"));
assert_eq!(it.get(&7), None);
assert_eq!(it.get(&3), None); // Intervals are [1, 3)Structs
Tracks the size of intervals and owns values internally in the tree.
An implementation of a non-overlapping interval tree.
An iterator over a sub-range of entries in a BTreeMap.
A mutable iterator over a sub-range of entries in a BTreeMap.