interval_tree/
lib.rs

1//! Interval tree for overlap queries on half-open `[lo, hi)` intervals.
2//!
3//! An `Interval<T>` is a tagged pair `(lo, hi)` with an associated
4//! payload. This crate builds the simple static interval tree described by
5//! the CLRS-style construction:
6//!
7//! * median-split on `mid = (lo + hi) / 2`
8//! * store intervals whose midpoint lies on the left of `mid` in `left`
9//! * store intervals whose midpoint lies on the right of `mid` in `right`
10//! * store intervals that contain `mid` in `middle` (their `lo <= mid <= hi`)
11//!
12//! [`IntervalTree::query`] returns every interval whose `[lo, hi)` overlaps
13//! a query interval `[qlo, qhi)`.
14//!
15//! The implementation is the canonical `O(n log n)` build / `O(k log n)`
16//! query variant; it is built once on construction and immutable
17//! thereafter.
18
19/// A half-open interval `[lo, hi)` carrying a payload.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub struct Interval<T> {
22    /// Inclusive lower bound.
23    pub lo: i64,
24    /// Exclusive upper bound.
25    pub hi: i64,
26    /// Associated payload.
27    pub value: T,
28}
29
30impl<T> Interval<T> {
31    /// Construct a new interval.
32    pub fn new(lo: i64, hi: i64, value: T) -> Self {
33        debug_assert!(lo <= hi, "interval must satisfy lo <= hi");
34        Self { lo, hi, value }
35    }
36
37    /// Return the midpoint `(lo + hi) / 2`.
38    fn mid(&self) -> i64 {
39        (self.lo + self.hi) / 2
40    }
41
42    /// Does this interval overlap `[qlo, qhi)`?
43    fn overlaps(&self, qlo: i64, qhi: i64) -> bool {
44        self.lo < qhi && qlo < self.hi
45    }
46
47    fn contains_point(&self, p: i64) -> bool {
48        self.lo <= p && p <= self.hi
49    }
50}
51
52/// Static interval tree.
53#[derive(Debug)]
54pub struct IntervalTree<T> {
55    root: Option<Node<T>>,
56}
57
58/// Internal node.
59#[derive(Debug)]
60struct Node<T> {
61    mid: i64,
62    middle: Vec<Interval<T>>,
63    left: Option<Box<Node<T>>>,
64    right: Option<Box<Node<T>>>,
65}
66
67impl<T: Clone> IntervalTree<T> {
68    /// Build an interval tree from a slice of intervals.
69    ///
70    /// # Panics
71    ///
72    /// Panics if any interval has `lo > hi`.
73    pub fn new(intervals: &[Interval<T>]) -> Self {
74        Self { root: build(intervals, 0, intervals.len()) }
75    }
76
77    /// Return all intervals whose `[lo, hi)` overlaps `[qlo, qhi)`.
78    pub fn query(&self, qlo: i64, qhi: i64) -> Vec<Interval<T>> {
79        let mut out = Vec::new();
80        if let Some(root) = self.root.as_ref() {
81            query_node(root, qlo, qhi, &mut out);
82        }
83        out
84    }
85}
86
87fn build<T: Clone>(intervals: &[Interval<T>], lo: usize, hi: usize) -> Option<Node<T>> {
88    if lo >= hi {
89        return None;
90    }
91    // Split point of the slice
92    let mid_idx = (lo + hi) / 2;
93    let mid_point = intervals[mid_idx].mid();
94
95    let mut middle = Vec::new();
96    let mut left_intervals = Vec::new();
97    let mut right_intervals = Vec::new();
98    for it in &intervals[lo..hi] {
99        if it.contains_point(mid_point) {
100            middle.push(it.clone());
101        } else if it.hi < mid_point {
102            left_intervals.push(it.clone());
103        } else if it.lo > mid_point {
104            right_intervals.push(it.clone());
105        } else {
106            // Shouldn't happen: interval ends on one side, starts on other, but doesn't contain mid.
107            // Fall back to the midpoint comparison.
108            if it.mid() < mid_point {
109                left_intervals.push(it.clone());
110            } else {
111                right_intervals.push(it.clone());
112            }
113        }
114    }
115
116    Some(Node {
117        mid: mid_point,
118        middle,
119        left: build(&left_intervals, 0, left_intervals.len()).map(Box::new),
120        right: build(&right_intervals, 0, right_intervals.len()).map(Box::new),
121    })
122}
123
124fn query_node<T: Clone>(node: &Node<T>, qlo: i64, qhi: i64, out: &mut Vec<Interval<T>>) {
125    // Check middle (intervals that contain the node's `mid`).
126    for it in &node.middle {
127        if it.overlaps(qlo, qhi) {
128            out.push(it.clone());
129        }
130    }
131    if qlo < node.mid {
132        if let Some(left) = node.left.as_deref() {
133            query_node(left, qlo, qhi, out);
134        }
135    }
136    if qhi > node.mid {
137        if let Some(right) = node.right.as_deref() {
138            query_node(right, qlo, qhi, out);
139        }
140    }
141}
interval_tree/lib.rs

interval_tree/
lib.rs
