simd_intervaltree/
lib.rs

1//! # simd-intervaltree
2//!
3//! A SIMD-accelerated interval tree with zero-allocation queries.
4//!
5//! ## Features
6//!
7//! - **Zero-allocation queries**: Iterator and callback-based APIs that don't allocate
8//! - **SIMD acceleration**: Uses AVX2/AVX-512 on x86_64, NEON on ARM for fast scans
9//! - **Generic bounds**: Works with any `Ord` type, with fast paths for primitives
10//! - **Immutable after construction**: `Send + Sync` by default
11//! - **`no_std` compatible**: Only requires `alloc`
12//!
13//! ## Example
14//!
15//! ```
16//! use simd_intervaltree::IntervalTree;
17//!
18//! let tree = IntervalTree::builder()
19//!     .insert(0..10, "first")
20//!     .insert(5..15, "second")
21//!     .insert(20..30, "third")
22//!     .build();
23//!
24//! // Zero-allocation iteration
25//! for entry in tree.query(3..12) {
26//!     println!("{:?} => {}", entry.interval, entry.value);
27//! }
28//!
29//! // Early termination with callback
30//! use std::ops::ControlFlow;
31//! tree.query_with(3..12, |interval, value| {
32//!     println!("{interval:?} => {value}");
33//!     ControlFlow::<()>::Continue(())
34//! });
35//! ```
36
37#![cfg_attr(not(feature = "std"), no_std)]
38#![deny(clippy::all)]
39#![warn(clippy::pedantic, clippy::nursery)]
40#![allow(clippy::module_name_repetitions)]
41
42extern crate alloc;
43
44#[cfg(feature = "jemalloc")]
45#[global_allocator]
46static GLOBAL: tikv_jemallocator::Jemalloc = tikv_jemallocator::Jemalloc;
47
48mod builder;
49mod mutable;
50mod query;
51mod simd;
52mod tree;
53
54pub use builder::IntervalTreeBuilder;
55pub use mutable::{IntervalId, IntervalSet};
56pub use query::{QueryEntry, QueryIter};
57pub use tree::IntervalTree;
58
59/// A half-open interval `[start, end)`.
60#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
61pub struct Interval<T> {
62    /// Start bound (inclusive).
63    pub start: T,
64    /// End bound (exclusive).
65    pub end: T,
66}
67
68impl<T: Ord> Interval<T> {
69    /// Creates a new interval.
70    ///
71    /// # Panics
72    ///
73    /// Panics if `start > end`.
74    #[must_use]
75    pub fn new(start: T, end: T) -> Self {
76        assert!(start <= end, "interval start must be <= end");
77        Self { start, end }
78    }
79
80    /// Returns true if this interval overlaps with `other`.
81    ///
82    /// Two intervals `[a, b)` and `[c, d)` overlap iff `a < d && c < b`.
83    #[inline]
84    #[must_use]
85    pub fn overlaps(&self, other: &Self) -> bool {
86        self.start < other.end && other.start < self.end
87    }
88
89    /// Returns true if this interval contains the point.
90    #[inline]
91    #[must_use]
92    pub fn contains_point(&self, point: &T) -> bool {
93        self.start <= *point && *point < self.end
94    }
95}
96
97impl<T: Ord> From<core::ops::Range<T>> for Interval<T> {
98    fn from(range: core::ops::Range<T>) -> Self {
99        Self::new(range.start, range.end)
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn interval_overlap() {
109        let a = Interval::new(0, 10);
110        let b = Interval::new(5, 15);
111        let c = Interval::new(10, 20);
112        let d = Interval::new(20, 30);
113
114        assert!(a.overlaps(&b));
115        assert!(b.overlaps(&a));
116        assert!(!a.overlaps(&c)); // [0,10) and [10,20) don't overlap (half-open)
117        assert!(!a.overlaps(&d));
118    }
119
120    #[test]
121    fn interval_contains_point() {
122        let a = Interval::new(0, 10);
123        assert!(a.contains_point(&0));
124        assert!(a.contains_point(&5));
125        assert!(!a.contains_point(&10)); // half-open, 10 is excluded
126        assert!(!a.contains_point(&-1));
127    }
128
129    #[test]
130    fn interval_from_range() {
131        let interval: Interval<i32> = (0..10).into();
132        assert_eq!(interval.start, 0);
133        assert_eq!(interval.end, 10);
134    }
135}
simd_intervaltree/lib.rs

simd_intervaltree/
lib.rs
