space_partitioning/
interval_tree.rs

1//! According to Wikipedia:
2//! > An interval tree is a tree data structure to hold intervals.
3//! > Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.
4mod inorder_iterator;
5mod interval;
6mod interval_tree_entry;
7mod interval_tree_node;
8mod interval_type;
9
10pub use inorder_iterator::InorderIterator;
11pub use interval::{Interval, IntervalType};
12pub use interval_tree_entry::IntervalTreeEntry;
13
14use crate::interval_tree::interval_tree_node::{IntervalTreeNode, IntervalTreeNodeOption};
15use std::fmt::{Debug, Formatter};
16
17/// An Interval Tree.
18pub struct IntervalTree<T, D>
19where
20    T: IntervalType,
21{
22    /// The root node. May not exist if the tree is default constructed
23    /// or initialized from an empty iterator.
24    root: Option<IntervalTreeNode<T, D>>,
25}
26
27impl<T, D> Default for IntervalTree<T, D>
28where
29    T: IntervalType,
30{
31    /// Returns an empty `IntervalTree<T, D>`.
32    ///
33    /// # Example
34    /// ```rust
35    /// use space_partitioning::IntervalTree;
36    /// let tree = IntervalTree::<i32, ()>::default();
37    /// assert_eq!(tree.len(), 0);
38    /// ```
39    fn default() -> Self {
40        Self { root: None }
41    }
42}
43
44impl<T, D> IntervalTree<T, D>
45where
46    T: IntervalType,
47{
48    /// Creates a new `IntervalTree` from a root entry.
49    ///
50    /// # Parameters
51    /// * `entry` - The first entry.
52    ///
53    /// # Example
54    /// ```rust
55    /// use space_partitioning::IntervalTree;
56    /// let tree = IntervalTree::new_from_entry((15..=20, "data"));
57    /// assert_eq!(tree.len(), 1);
58    /// ```
59    pub fn new_from_entry<I>(entry: I) -> Self
60    where
61        I: Into<IntervalTreeEntry<T, D>>,
62    {
63        Self {
64            root: Some(IntervalTreeNode::new(entry.into())),
65        }
66    }
67
68    fn new_from_node(root: IntervalTreeNode<T, D>) -> Self {
69        Self { root: Some(root) }
70    }
71
72    /// Inserts a new entry to the `IntervalTree`.
73    ///
74    /// # Parameters
75    /// * `entry` - The entry to insert.
76    ///
77    /// # Example
78    /// ```rust
79    /// use space_partitioning::IntervalTree;
80    /// let mut tree = IntervalTree::default();
81    /// tree.insert((15..=20, "data"));
82    /// assert_eq!(tree.len(), 1);
83    /// ```
84    pub fn insert<I>(&mut self, entry: I) -> &Self
85    where
86        I: Into<IntervalTreeEntry<T, D>>,
87    {
88        let node = IntervalTreeNode::new(entry.into());
89        if self.root.is_none() {
90            self.root = Some(node);
91        } else {
92            self.root.as_mut().unwrap().insert(node);
93        }
94        self
95    }
96
97    /// Returns the number of elements in the `IntervalTree`.
98    ///
99    /// # Example
100    /// ```rust
101    /// use space_partitioning::IntervalTree;
102    /// let tree = IntervalTree::new_from_entry((15..=20, "data"));
103    /// assert_eq!(tree.len(), 1);
104    /// ```
105    pub fn len(&self) -> usize {
106        return if let Some(node) = &self.root {
107            node.len()
108        } else {
109            0
110        };
111    }
112
113    /// Returns whether the tree is empty, i.e., whether it has no elements.
114    ///
115    /// # Example
116    /// ```rust
117    /// use space_partitioning::IntervalTree;
118    /// let tree = IntervalTree::<i32, ()>::default();
119    /// assert!(tree.is_empty());
120    /// ```
121    pub fn is_empty(&self) -> bool {
122        self.len() == 0
123    }
124
125    /// Queries the tree for overlaps with the specified `interval`.
126    ///
127    /// /// # Parameters
128    /// * `interval` - The interval to query for.
129    ///
130    /// # Example
131    /// ```rust
132    /// use space_partitioning::IntervalTree;
133    /// use space_partitioning::interval_tree::Interval;
134    ///
135    /// let mut tree = IntervalTree::new_from_entry((15..=20, "A"));
136    /// tree.insert((100..=101, "B"));
137    ///
138    /// let matched_a = tree.overlap_search(&(18..=25).into()).unwrap();
139    /// assert_eq!(matched_a.interval.start, 15);
140    /// assert_eq!(matched_a.interval.end, 20);
141    /// assert_eq!(matched_a.data, "A");
142    ///
143    /// let matched_b = tree.overlap_search(&(100..=100).into()).unwrap();
144    /// assert_eq!(matched_b.interval.start, 100);
145    /// assert_eq!(matched_b.interval.end, 101);
146    /// assert_eq!(matched_b.data, "B");
147    ///
148    /// let no_match = tree.overlap_search(0..=5);
149    /// assert!(no_match.is_none());
150    /// ```
151    pub fn overlap_search<I>(&self, interval: I) -> Option<&IntervalTreeEntry<T, D>>
152    where
153        I: Into<Interval<T>>,
154    {
155        if let Some(node) = &self.root {
156            let interval = interval.into();
157            node.overlap_search(&interval)
158        } else {
159            None
160        }
161    }
162
163    /// Returns an `InorderIterator<T, D>` that iterates the tree elements in order
164    /// of their interval starts.
165    ///
166    /// # Example
167    /// ```rust
168    /// use space_partitioning::IntervalTree;
169    /// use std::iter::FromIterator;
170    ///
171    /// let tree = IntervalTree::from_iter([(18..=25, "abc"), (0..=20, "xyz")]);
172    /// let mut iter = tree.iter_inorder();
173    ///
174    /// let first = iter.next().unwrap();
175    /// assert_eq!(first.interval.start, 0);
176    /// assert_eq!(first.interval.end, 20);
177    /// assert_eq!(first.data, "xyz");
178    ///
179    /// let second = iter.next().unwrap();
180    /// assert_eq!(second.interval.start, 18);
181    /// assert_eq!(second.interval.end, 25);
182    /// assert_eq!(second.data, "abc");
183    ///
184    /// assert!(iter.next().is_none());
185    /// ```
186    pub fn iter_inorder(&self) -> InorderIterator<T, D> {
187        if let Some(node) = &self.root {
188            InorderIterator::new(node)
189        } else {
190            InorderIterator::empty()
191        }
192    }
193}
194
195impl<T, D> Debug for IntervalTree<T, D>
196where
197    T: Debug + IntervalType,
198{
199    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
200        write!(f, "len = {}", self.len())
201    }
202}
203
204impl<T> From<Interval<T>> for IntervalTree<T, ()>
205where
206    T: IntervalType,
207{
208    fn from(interval: Interval<T>) -> Self {
209        Self::new_from_node(IntervalTreeNode::new_from_pair(interval, ()))
210    }
211}
212
213impl<T, D> From<(Interval<T>, D)> for IntervalTree<T, D>
214where
215    T: IntervalType,
216{
217    fn from(value: (Interval<T>, D)) -> Self {
218        Self::new_from_node(IntervalTreeNode::new_from_pair(value.0, value.1))
219    }
220}
221
222impl<I, T, D> std::iter::FromIterator<I> for IntervalTree<T, D>
223where
224    I: Into<IntervalTreeEntry<T, D>>,
225    T: IntervalType,
226{
227    fn from_iter<Iter>(iter: Iter) -> Self
228    where
229        Iter: IntoIterator<Item = I>,
230    {
231        match IntervalTreeNodeOption::from_iter(iter) {
232            IntervalTreeNodeOption::Some(node) => IntervalTree::new_from_node(node),
233            IntervalTreeNodeOption::None => IntervalTree::default(),
234        }
235    }
236}
237
238#[cfg(test)]
239mod test {
240    use super::*;
241    use std::iter::FromIterator;
242
243    mod construction {
244        use super::*;
245
246        #[test]
247        fn insert_only_works() {
248            let mut tree = IntervalTree::default();
249            assert_eq!(tree.len(), 0);
250            tree.insert((15..=20, 4.2));
251            assert_eq!(tree.len(), 1);
252            tree.insert((10..=30, 13.37));
253            assert_eq!(tree.len(), 2);
254        }
255
256        #[test]
257        fn from_constructor_works() {
258            let mut tree = IntervalTree::new_from_entry(15..=20);
259            assert_eq!(tree.len(), 1);
260            tree.insert(15..=20);
261            assert_eq!(tree.len(), 2);
262        }
263    }
264
265    mod from_iter {
266        use super::*;
267
268        #[test]
269        fn range_without_data_works() {
270            let tree =
271                IntervalTree::from_iter([15..=20, 10..=30, 17..=19, 5..=20, 12..=15, 30..=40]);
272            assert_eq!(tree.len(), 6);
273        }
274
275        #[test]
276        fn interval_without_data_works() {
277            let tree = IntervalTree::from_iter([
278                Interval::from(15..=20),
279                (10..=30).into(),
280                (17..=19).into(),
281                (5..=20).into(),
282                (12..=15).into(),
283                (30..=40).into(),
284            ]);
285            assert_eq!(tree.len(), 6);
286        }
287
288        #[test]
289        fn range_with_data_works() {
290            let tree = IntervalTree::from_iter([
291                (15..=20, 1),
292                (10..=30, 2),
293                (17..=19, 3),
294                (5..=20, 4),
295                (12..=15, 5),
296                (30..=40, 6),
297            ]);
298            assert_eq!(tree.len(), 6);
299        }
300
301        #[test]
302        fn interval_with_data_works() {
303            let tree = IntervalTree::from_iter([
304                (Interval::from(15..=20), 1),
305                ((10..=30).into(), 2),
306                ((17..=19).into(), 3),
307                ((5..=20).into(), 4),
308                ((12..=15).into(), 5),
309                ((30..=40).into(), 6),
310            ]);
311            assert_eq!(tree.len(), 6);
312        }
313    }
314
315    mod iter {
316        use super::*;
317
318        #[test]
319        fn last_works() {
320            let tree =
321                IntervalTree::from_iter([15..=20, 10..=30, 17..=19, 5..=20, 12..=15, 30..=40]);
322            let last = tree.iter_inorder().last();
323            assert!(last.is_some());
324            let last = last.unwrap();
325            assert_eq!(last.interval.start, 30);
326            assert_eq!(last.interval.end, 40);
327        }
328    }
329
330    mod search {
331        use super::*;
332
333        #[test]
334        fn overlap_search_works() {
335            let tree =
336                IntervalTree::from_iter([15..=20, 10..=30, 17..=19, 5..=20, 12..=15, 30..=40]);
337            let overlap = tree.overlap_search(Interval::from(6..=7));
338            assert_eq!(overlap.unwrap().interval, Interval::from(5..=20));
339        }
340    }
341
342    mod utility {
343        use super::*;
344        use std::ops::RangeInclusive;
345
346        #[test]
347        fn len_works() {
348            let tree =
349                IntervalTree::from_iter([15..=20, 10..=30, 17..=19, 5..=20, 12..=15, 30..=40]);
350            assert_eq!(tree.len(), 6);
351        }
352
353        #[test]
354        fn len_when_empty_works() {
355            let tree = IntervalTree::from_iter([] as [RangeInclusive<i32>; 0]);
356            assert_eq!(tree.len(), 0);
357        }
358    }
359
360    mod multi_dimensional {
361        use super::*;
362
363        #[derive(Debug, PartialOrd, PartialEq, Copy, Clone, Default)]
364        struct Vec2d {
365            pub x: f64,
366            pub y: f64,
367        }
368
369        impl IntervalType for Vec2d {}
370
371        #[test]
372        fn it_works() {
373            let tree = IntervalTree::from_iter([
374                (
375                    Interval::new(Vec2d { x: 1., y: 2. }, Vec2d { x: 10., y: 10. }),
376                    "A",
377                ),
378                (
379                    Interval::new(Vec2d { x: -5., y: -5. }, Vec2d { x: 5., y: 5. }),
380                    "B",
381                ),
382                (
383                    Interval::new(Vec2d { x: -10., y: -10. }, Vec2d { x: -7., y: -7. }),
384                    "C",
385                ),
386            ]);
387
388            let test = Interval::new(Vec2d::default(), Vec2d::default());
389            let result = tree.overlap_search(test).unwrap();
390
391            assert_eq!(result.data, "B")
392        }
393    }
394}
space_partitioning/interval_tree.rs

space_partitioning/
interval_tree.rs
