Non-overlapping Interval Tree

Simple library for a map data structure that contains elements keyed on ranges, whose keys cannot overlap. Lookup queries can lookup a specific point in a range, and get back the value for that range.

Docs: docs.rs

This library supports no_std (but requires core and the alloc crate). To enable no_std, disable default features.

lib.rs:

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)