Struct IntervalTree

Source

pub struct IntervalTree<T: Ord + Clone + Default, V, A: Allocator = Global> { /* private fields */ }

Available on crate feature interval-tree only.

Expand description

Am interval tree that supports O(log n) overlap queries.

Built on an augmented red-black tree where each subtree tracks the maximum upper bound (hi) of all intervals it contains. This enables efficient pruning during overlap queries.

§Type Parameters

T: The endpoint type. Must be Ord + Clone.
V: The value associated with each interval.
A: Allocator (defaults to Global]).

§Examples

use augmented_rbtree::interval_tree::{Interval, IntervalTree};

let mut tree = IntervalTree::new();
tree.insert(Interval::new(1, 5), "a");
tree.insert(Interval::new(3, 9), "b");
tree.insert(Interval::new(7, 10), "c");

let overlapping: Vec<_> = tree.query_overlap(4, 8).map(|(iv, v)| (*iv, *v)).collect();
assert_eq!(overlapping.len(), 3);

Implementations§

Source §

impl<T: Ord + Clone + Default, V> IntervalTree<T, V>

Source

pub fn new() -> Self

Creates a new, empty interval tree.

Source §

impl<T: Ord + Clone + Default, V, A: Allocator> IntervalTree<T, V, A>

Source

pub fn new_in(alloc: A) -> Self

Creates a new interval tree with the given allocator.

Source

pub fn inner_tree(&self) -> &AugmentedRBTree<Interval<T>, V, MaxHi<T>, A>

Returns a reference to the underlying augmented red-black tree. This can be used for advanced operations or visualization.

Source

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

Inserts an interval-value pair.

If the exact interval already exists, the old value is replaced and returned.

Source

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

Removes an interval from the tree, returning its value if it existed.

Source

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

Returns a reference to the value associated with interval, if present.

Source

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

Returns true if the tree contains the exact interval.

Source

pub fn len(&self) -> usize

Returns the number of intervals in the tree.

Source

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

Source

pub fn iter(&self) -> impl Iterator<Item = (&Interval<T>, &V)>

Returns an iterator over all (interval, value) pairs in sorted order (by lo, then hi).

Source

pub fn query_overlap<K>( &self, lo: K, hi: K, ) -> impl Iterator<Item = (&Interval<T>, &V)>
where K: Borrow<T>,

Returns an iterator over all intervals that overlap with [lo, hi].

Complexity: O(k log n) where k is the number of overlapping intervals.

§Examples

use augmented_rbtree::interval_tree::{Interval, IntervalTree};

let mut tree = IntervalTree::new();
tree.insert(Interval::new(1, 5), ());
tree.insert(Interval::new(6, 10), ());
tree.insert(Interval::new(3, 8), ());

let overlapping: Vec<_> = tree.query_overlap(4, 7).collect();
assert_eq!(overlapping.len(), 3); // [1,5], [3,8] and [6,10] all overlap [4,7]