store_interval_tree/
lib.rs

1#![no_std]
2#![warn(clippy::cargo)]
3#![deny(rustdoc::broken_intra_doc_links)]
4#![deny(clippy::all)]
5#![warn(
6    missing_debug_implementations,
7    trivial_numeric_casts,
8    unused_extern_crates,
9    unused_import_braces,
10    unused_qualifications,
11    unused_must_use
12)]
13#![warn(clippy::pedantic)]
14#![allow(clippy::comparison_chain)]
15// TODO: check https://rust-lang.github.io/rust-clippy/master/index.html#derive_hash_xor_eq
16#![allow(clippy::derive_hash_xor_eq)]
17#![allow(clippy::missing_panics_doc)]
18
19#[macro_use]
20pub extern crate alloc;
21
22use alloc::{boxed::Box, rc::Rc, vec::Vec};
23use core::cmp::Ord;
24use core::fmt::Debug;
25use core::ops::Bound;
26
27mod interval;
28pub use interval::Interval;
29
30mod node;
31use node::Node;
32
33mod iterators;
34pub use iterators::{Entry, EntryMut, IntervalTreeIterator, IntervalTreeIteratorMut};
35
36/// An interval tree is a tree data structure to hold intervals.
37/// Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.
38///
39/// This data structure is backed by a `store_interval_tree:IntervalTree`
40///
41/// # Examples
42/// ```
43/// use store_interval_tree::IntervalTree;
44/// use store_interval_tree::Interval;
45/// use std::ops::Bound::*;
46///
47/// // initialize an interval tree with end points of type usize
48/// let mut interval_tree = IntervalTree::<usize, ()>::new();
49///
50/// // insert interval into the tree
51/// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
52/// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
53/// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
54/// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
55/// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
56/// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
57/// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
58/// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
59/// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
60///
61/// let interval1 = Interval::new(Excluded(23), Included(26));
62///
63/// // interval (25, 30] is overlapped with interval (23,26]
64/// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
65///
66/// // there is no interval in the tree that has interval with (10,15)
67/// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
68///
69/// // find all overlaps with an interval
70/// let interval = Interval::new(Included(8), Included(26));
71/// // intervals are: (8,9], [6,10],(19,20], [16,21), (15,23), [17,19), (25,30], [26,26]
72/// let intervals = interval_tree.find_overlaps(&interval);
73///
74/// // delete interval
75/// let interval = Interval::new(Included(15), Included(18));
76/// let overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
77/// interval_tree.delete(&overlapped_interval);
78///
79/// // find all intervals between two intervals/points
80/// let low = Interval::point(14);
81/// let high = Interval::point(24);
82/// // intervals are: (15,23), [16,21), [17,19), (19,20]
83/// let intervals = interval_tree.intervals_between(&low, &high);
84/// ```
85#[derive(Clone, Default, Hash)]
86pub struct IntervalTree<T: Ord, V> {
87    root: Option<Box<Node<T, V>>>,
88}
89
90impl<T: Ord, V> IntervalTree<T, V> {
91    /// Initialize an interval tree with end points of type usize
92    ///
93    /// # Examples
94    /// ```
95    /// use store_interval_tree::IntervalTree;
96    ///
97    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
98    /// ```
99    #[must_use]
100    pub fn new() -> IntervalTree<T, V> {
101        IntervalTree { root: None }
102    }
103
104    /// Returns true if there are no intervals in the tree, false otherwise
105    #[must_use]
106    pub fn is_empty(&self) -> bool {
107        self.root.is_none()
108    }
109
110    /// Returns total number of intervals in the tree
111    #[must_use]
112    pub fn size(&self) -> usize {
113        Node::size(&self.root)
114    }
115
116    /// Returns height of the tree
117    #[must_use]
118    pub fn height(&self) -> i64 {
119        Node::height(&self.root)
120    }
121
122    /// Find overlapping intervals in the tree and returns an
123    /// `IntervalTreeIterator` that allows access to the stored value
124    ///
125    /// # Arguments
126    /// * `interval`: interval to be searched for any overlaps
127    ///
128    /// # Examples
129    /// ```
130    /// use store_interval_tree::IntervalTree;
131    /// use store_interval_tree::Interval;
132    /// use std::ops::Bound::*;
133    ///
134    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
135    ///
136    /// // insert interval into the tree
137    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
138    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
139    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
140    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
141    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
142    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
143    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
144    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
145    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
146    ///
147    /// let interval1 = Interval::new(Excluded(23), Included(26));
148    ///
149    /// // interval (25, 30] is overlapped with interval (23,26]
150    /// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
151    ///
152    /// // there is no interval in the tree that has interval with (10,15)
153    /// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
154    /// ```
155    #[must_use]
156    pub fn query<'a, 'v, 'i>(
157        &'a self,
158        interval: &'i Interval<T>,
159    ) -> IntervalTreeIterator<'v, 'i, T, V>
160    where
161        'a: 'v,
162        'a: 'i,
163    {
164        if let Some(ref n) = self.root {
165            IntervalTreeIterator {
166                nodes: vec![n],
167                interval,
168            }
169        } else {
170            let nodes = vec![];
171            IntervalTreeIterator { nodes, interval }
172        }
173    }
174
175    /// Find overlapping intervals in the tree and returns an
176    /// `IntervalTreeIteratorMut` that allows mutable access to the stored value
177    ///
178    /// # Arguments
179    /// * `interval`: interval to be searched for any overlaps
180    ///
181    /// # Examples
182    /// ```
183    /// use store_interval_tree::IntervalTree;
184    /// use store_interval_tree::Interval;
185    /// use std::ops::Bound::*;
186    ///
187    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
188    ///
189    /// // insert interval into the tree
190    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
191    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
192    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
193    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
194    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
195    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
196    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
197    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
198    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
199    ///
200    /// let interval1 = Interval::new(Excluded(23), Included(26));
201    ///
202    /// // interval (25, 30] is overlapped with interval (23,26]
203    /// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
204    ///
205    /// // there is no interval in the tree that has interval with (10,15)
206    /// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
207    /// ```
208    pub fn query_mut<'a, 'v, 'i>(
209        &'a mut self,
210        interval: &'i Interval<T>,
211    ) -> IntervalTreeIteratorMut<'v, 'i, T, V>
212    where
213        'a: 'v,
214        'a: 'i,
215    {
216        if let Some(ref mut n) = self.root {
217            IntervalTreeIteratorMut {
218                nodes: vec![n],
219                interval,
220            }
221        } else {
222            let nodes = vec![];
223            IntervalTreeIteratorMut { nodes, interval }
224        }
225    }
226
227    /// Returns true if there exists an interval in the tree that overlaps with specified `interval`
228    ///
229    /// # Arguments
230    /// * `interval`: interval to be searched for any overlaps
231    ///
232    /// # Examples
233    /// ```
234    /// use store_interval_tree::IntervalTree;
235    /// use store_interval_tree::Interval;
236    /// use std::ops::Bound::*;
237    ///
238    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
239    ///
240    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
241    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
242    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
243    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
244    ///
245    /// assert!(!interval_tree.overlaps(&Interval::new(Included(4), Excluded(6))));
246    /// assert!(interval_tree.overlaps(&Interval::new(Included(4), Included(6))));
247    /// ```
248    #[must_use]
249    pub fn overlaps(&self, interval: &Interval<T>) -> bool {
250        self.find_overlap(interval).is_some()
251    }
252
253    /// Returns first interval that overlaps with specified `interval`
254    ///
255    /// # Arguments:
256    /// * `interval`: interval to be searched for any overlaps
257    ///
258    /// # Examples
259    /// ```
260    /// use store_interval_tree::IntervalTree;
261    /// use store_interval_tree::Interval;
262    /// use std::ops::Bound::*;
263    ///
264    /// // initialize an interval tree with end points of type usize
265    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
266    ///
267    /// // insert interval into the tree
268    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
269    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
270    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
271    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
272    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
273    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
274    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
275    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
276    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
277    ///
278    /// let interval1 = Interval::new(Excluded(23), Included(26));
279    ///
280    /// // interval (25, 30] is overlapped with interval (23,26]
281    /// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
282    ///
283    /// // there is no interval in the tree that has interval with (10,15)
284    /// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
285    /// ```
286    #[must_use]
287    pub fn find_overlap(&self, interval: &Interval<T>) -> Option<Interval<T>> {
288        IntervalTree::_find_overlap(&self.root, interval)
289    }
290
291    fn _find_overlap(
292        node: &Option<Box<Node<T, V>>>,
293        interval: &Interval<T>,
294    ) -> Option<Interval<T>> {
295        if node.is_none() {
296            return None;
297        }
298        let mut current = node;
299        while current.is_some() {
300            let node_ref = current.as_ref().unwrap();
301            if Interval::overlaps(node_ref.interval(), interval) {
302                break;
303            }
304
305            if node_ref.left_child.is_some()
306                && Node::<T, V>::is_ge(
307                    &node_ref.left_child.as_ref().unwrap().get_max(),
308                    &interval.get_low(),
309                )
310            {
311                current = &node_ref.left_child;
312            } else {
313                current = &node_ref.right_child;
314            }
315        }
316
317        if current.is_none() {
318            None
319        } else {
320            Some(current.as_ref().unwrap().interval().duplicate())
321        }
322    }
323
324    /// Returns all intervals that overlap with the specified `interval`
325    ///
326    /// # Arguments
327    /// * `interval`: interval to be searched for any overlaps
328    ///
329    /// # Examples
330    /// ```
331    /// use store_interval_tree::IntervalTree;
332    /// use store_interval_tree::Interval;
333    /// use std::ops::Bound::*;
334    ///
335    /// // initialize an interval tree with end points of type usize
336    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
337    ///
338    /// // insert interval into the tree
339    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
340    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
341    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
342    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
343    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
344    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
345    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
346    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
347    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
348    ///
349    /// // find all overlaps with an interval
350    /// let interval = Interval::new(Included(8), Included(26));
351    /// // intervals are: (8,9], [6,10],(19,20], [16,21), (15,23), [17,19), (25,30], [26,26]
352    /// let intervals = interval_tree.find_overlaps(&interval);
353    /// ```
354    #[must_use]
355    pub fn find_overlaps(&self, interval: &Interval<T>) -> Vec<Interval<T>> {
356        let mut overlaps = Vec::<Interval<T>>::new();
357
358        IntervalTree::_find_overlaps(&self.root, interval, &mut overlaps);
359
360        overlaps
361    }
362
363    fn _find_overlaps(
364        node: &Option<Box<Node<T, V>>>,
365        interval: &Interval<T>,
366        overlaps: &mut Vec<Interval<T>>,
367    ) {
368        if node.is_none() {
369            return;
370        }
371        let node_ref = node.as_ref().unwrap();
372        if Interval::overlaps(node_ref.interval(), interval) {
373            overlaps.push(node_ref.interval().duplicate());
374        }
375
376        if node_ref.left_child.is_some()
377            && Node::<T, V>::is_ge(
378                &node_ref.left_child.as_ref().unwrap().get_max(),
379                &interval.get_low(),
380            )
381        {
382            IntervalTree::_find_overlaps(&node_ref.left_child, interval, overlaps);
383        }
384        IntervalTree::_find_overlaps(&node_ref.right_child, interval, overlaps);
385    }
386
387    /// Inserts an interval in the tree. if interval already exists, `interval` will be ignored
388    ///
389    /// # Arguments
390    /// * `interval`: interval to be inserted in the tree
391    ///
392    /// # Examples
393    /// ```
394    /// use store_interval_tree::IntervalTree;
395    /// use store_interval_tree::Interval;
396    /// use std::ops::Bound::*;
397    ///
398    /// // initialize an interval tree with end points of type usize
399    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
400    ///
401    /// // insert interval into the tree
402    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
403    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
404    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
405    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
406    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
407    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
408    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
409    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
410    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
411    /// ```
412    pub fn insert(&mut self, interval: Interval<T>, value: V) {
413        let max = interval.get_high();
414
415        self.root = Some(IntervalTree::_insert(
416            self.root.take(),
417            interval,
418            value,
419            max,
420        ));
421    }
422
423    fn _insert(
424        node: Option<Box<Node<T, V>>>,
425        interval: Interval<T>,
426        value: V,
427        max: Rc<Bound<T>>,
428    ) -> Box<Node<T, V>> {
429        if node.is_none() {
430            return Box::new(Node::init(interval, value, max, 0, 1));
431        }
432
433        let mut node_ref = node.unwrap();
434
435        if interval < *node_ref.interval() {
436            node_ref.left_child = Some(IntervalTree::_insert(
437                node_ref.left_child,
438                interval,
439                value,
440                max,
441            ));
442        } else if interval > *node_ref.interval() {
443            node_ref.right_child = Some(IntervalTree::_insert(
444                node_ref.right_child,
445                interval,
446                value,
447                max,
448            ));
449        } else {
450            return node_ref;
451        }
452
453        node_ref.update_height();
454        node_ref.update_size();
455        node_ref.update_max();
456
457        IntervalTree::balance(node_ref)
458    }
459
460    fn balance(mut node: Box<Node<T, V>>) -> Box<Node<T, V>> {
461        if Node::balance_factor(&node) < -1 {
462            if Node::balance_factor(node.right_child.as_ref().unwrap()) > 0 {
463                node.right_child = Some(IntervalTree::rotate_right(node.right_child.unwrap()));
464            }
465            node = IntervalTree::rotate_left(node);
466        } else if Node::balance_factor(&node) > 1 {
467            if Node::balance_factor(node.left_child.as_ref().unwrap()) < 0 {
468                node.left_child = Some(IntervalTree::rotate_left(node.left_child.unwrap()));
469            }
470            node = IntervalTree::rotate_right(node);
471        }
472        node
473    }
474
475    fn rotate_right(mut node: Box<Node<T, V>>) -> Box<Node<T, V>> {
476        let mut y = node.left_child.unwrap();
477        node.left_child = y.right_child;
478        y.size = node.size;
479        node.update_height();
480        node.update_size();
481        node.update_max();
482
483        y.right_child = Some(node);
484        y.update_height();
485        y.update_max();
486
487        y
488    }
489
490    fn rotate_left(mut node: Box<Node<T, V>>) -> Box<Node<T, V>> {
491        let mut y = node.right_child.unwrap();
492        node.right_child = y.left_child;
493        y.size = node.size;
494
495        node.update_height();
496        node.update_size();
497        node.update_max();
498
499        y.left_child = Some(node);
500        y.update_height();
501        y.update_max();
502
503        y
504    }
505
506    /// Delete the specified `interval` if found
507    ///
508    /// # Arguments
509    /// * `interval`: interval to be deleted
510    ///
511    /// # Examples
512    /// ```
513    /// use store_interval_tree::IntervalTree;
514    /// use store_interval_tree::Interval;
515    /// use std::ops::Bound::*;
516    ///
517    /// // initialize an interval tree with end points of type usize
518    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
519    ///
520    /// // insert interval into the tree
521    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
522    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
523    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
524    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
525    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
526    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
527    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
528    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
529    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
530    ///
531    /// // delete interval
532    /// let interval = Interval::new(Included(15), Included(18));
533    /// let overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
534    /// interval_tree.delete(&overlapped_interval);
535    /// ```
536    pub fn delete(&mut self, interval: &Interval<T>) {
537        if !self.is_empty() {
538            self.root = IntervalTree::_delete(self.root.take(), interval);
539        }
540    }
541
542    fn _delete(node: Option<Box<Node<T, V>>>, interval: &Interval<T>) -> Option<Box<Node<T, V>>> {
543        match node {
544            None => None,
545            Some(mut node) => {
546                if *interval < *node.interval() {
547                    node.left_child = IntervalTree::_delete(node.left_child.take(), interval);
548                } else if *interval > *node.interval() {
549                    node.right_child = IntervalTree::_delete(node.right_child.take(), interval);
550                } else if node.left_child.is_none() {
551                    return node.right_child;
552                } else if node.right_child.is_none() {
553                    return node.left_child;
554                } else {
555                    let mut y = node;
556                    node = IntervalTree::_min(&mut y.right_child);
557                    node.right_child = IntervalTree::_delete_min(y.right_child.unwrap());
558                    node.left_child = y.left_child;
559                }
560
561                node.update_height();
562                node.update_size();
563                node.update_max();
564                Some(IntervalTree::balance(node))
565            }
566        }
567    }
568    fn _min(node: &mut Option<Box<Node<T, V>>>) -> Box<Node<T, V>> {
569        match node {
570            Some(node) => {
571                if node.left_child.is_none() {
572                    Box::new(Node::init(
573                        node.get_interval(),
574                        node.get_value(),
575                        node.get_max(),
576                        0,
577                        1,
578                    ))
579                } else {
580                    IntervalTree::_min(&mut node.left_child)
581                }
582            }
583            None => panic!("Called min on None node"),
584        }
585    }
586
587    /// Deletes minimum interval in the tree
588    ///
589    /// # Examples
590    /// ```
591    /// use store_interval_tree::IntervalTree;
592    /// use store_interval_tree::Interval;
593    /// use std::ops::Bound::*;
594    ///
595    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
596    ///
597    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
598    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
599    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
600    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
601    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
602    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
603    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
604    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
605    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
606    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
607    ///
608    /// interval_tree.delete_min();
609    /// interval_tree.delete_min();
610    ///
611    /// assert!(interval_tree.find_overlap(&Interval::new(Included(1), Excluded(6))).is_none());
612    /// ```
613    pub fn delete_min(&mut self) {
614        if !self.is_empty() {
615            self.root = IntervalTree::_delete_min(self.root.take().unwrap());
616        }
617    }
618
619    fn _delete_min(mut node: Box<Node<T, V>>) -> Option<Box<Node<T, V>>> {
620        if node.left_child.is_none() {
621            return node.right_child.take();
622        }
623
624        node.left_child = IntervalTree::_delete_min(node.left_child.unwrap());
625
626        node.update_height();
627        node.update_size();
628        node.update_max();
629
630        Some(IntervalTree::balance(node))
631    }
632
633    /// Deletes maximum interval in the tree
634    ///
635    /// # Examples
636    /// ```
637    /// use store_interval_tree::IntervalTree;
638    /// use store_interval_tree::Interval;
639    /// use std::ops::Bound::*;
640    ///
641    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
642    ///
643    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
644    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
645    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
646    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
647    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
648    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
649    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
650    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
651    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
652    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
653    ///
654    /// interval_tree.delete_max();
655    /// interval_tree.delete_max();
656    ///
657    /// assert!(interval_tree.find_overlap(&Interval::new(Included(25), Excluded(30))).is_none());
658    pub fn delete_max(&mut self) {
659        if !self.is_empty() {
660            self.root = IntervalTree::_delete_max(self.root.take().unwrap());
661        }
662    }
663
664    fn _delete_max(mut node: Box<Node<T, V>>) -> Option<Box<Node<T, V>>> {
665        if node.right_child.is_none() {
666            return node.left_child.take();
667        }
668
669        node.right_child = IntervalTree::_delete_max(node.right_child.unwrap());
670
671        node.update_height();
672        node.update_size();
673        node.update_max();
674
675        Some(IntervalTree::balance(node))
676    }
677
678    /// Returns the kth smallest interval
679    ///
680    /// # Arguments
681    /// * `k`: the order statistic
682    ///
683    /// # Panics
684    /// * panics if k is not in range: 0 <= k <= size - 1
685    ///
686    /// # Examples
687    /// ```
688    /// use store_interval_tree::IntervalTree;
689    /// use store_interval_tree::Interval;
690    /// use std::ops::Bound::*;
691    ///
692    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
693    ///
694    /// interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
695    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
696    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
697    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
698    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
699    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
700    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
701    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
702    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
703    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
704    ///
705    /// assert!(format!("{}", interval_tree.select(0).unwrap()) == String::from("[0,3)"));
706    /// assert!(format!("{}", interval_tree.select(1).unwrap()) == String::from("(0,1]"));
707    /// assert!(format!("{}", interval_tree.select(2).unwrap()) == String::from("[6,10]"));
708    /// assert!(format!("{}", interval_tree.select(3).unwrap()) == String::from("(8,9]"));
709    /// ```
710    #[must_use]
711    pub fn select(&self, k: usize) -> Option<Interval<T>> {
712        assert!(k <= self.size(), "K must be in range 0 <= k <= size - 1");
713        IntervalTree::_select(&self.root, k)
714    }
715
716    fn _select(node: &Option<Box<Node<T, V>>>, k: usize) -> Option<Interval<T>> {
717        if node.is_none() {
718            return None;
719        }
720        let node_ref = node.as_ref().unwrap();
721
722        let t = Node::size(&node_ref.left_child);
723        if t > k {
724            IntervalTree::_select(&node_ref.left_child, k)
725        } else if t < k {
726            IntervalTree::_select(&node_ref.right_child, k - t - 1)
727        } else {
728            return Some(node_ref.interval().duplicate());
729        }
730    }
731
732    /// Returns minimum interval in the tree
733    #[must_use]
734    pub fn min(&self) -> Option<Interval<T>> {
735        self.select(0)
736    }
737
738    /// Returns maximum interval in the tree
739    #[must_use]
740    pub fn max(&self) -> Option<Interval<T>> {
741        self.select(self.size() - 1)
742    }
743
744    /// Returns all intervals between two intervals/points
745    ///
746    /// # Arguments
747    /// * `low_bound`: lowest interval of the range
748    /// * `high_bound`: highest interval of the range
749    ///
750    /// # Examples
751    /// ```
752    /// use store_interval_tree::IntervalTree;
753    /// use store_interval_tree::Interval;
754    /// use std::ops::Bound::*;
755    ///
756    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
757    ///
758    /// interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
759    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
760    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
761    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
762    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
763    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
764    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
765    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
766    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
767    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
768    ///
769    /// let low = Interval::new(Included(14), Included(14));
770    /// let high = Interval::new(Included(24), Included(24));
771    /// let intervals = interval_tree.intervals_between(&low, &high);
772    ///
773    /// let accept = String::from("(15,23)[16,21)[17,19)(19,20]");
774    ///
775    /// let mut result = String::from("");
776    /// for interval in intervals {
777    ///     result.push_str(&format!("{}", interval))
778    /// }
779    ///
780    /// assert_eq!(result, accept);
781    /// ```
782    #[must_use]
783    pub fn intervals_between(
784        &self,
785        low_bound: &Interval<T>,
786        high_bound: &Interval<T>,
787    ) -> Vec<&Interval<T>> {
788        let mut intervals: Vec<&Interval<T>> = Vec::new();
789
790        IntervalTree::_intervals_between(&self.root, low_bound, high_bound, &mut intervals);
791
792        intervals
793    }
794
795    fn _intervals_between<'a>(
796        node: &'a Option<Box<Node<T, V>>>,
797        low_bound: &Interval<T>,
798        high_bound: &Interval<T>,
799        intervals: &mut Vec<&'a Interval<T>>,
800    ) {
801        if node.is_none() {
802            return;
803        }
804
805        let node_ref = node.as_ref().unwrap();
806        if *low_bound < *node_ref.interval() {
807            IntervalTree::_intervals_between(
808                &node_ref.left_child,
809                low_bound,
810                high_bound,
811                intervals,
812            );
813        }
814        if *low_bound <= *node_ref.interval() && *node_ref.interval() <= *high_bound {
815            intervals.push(node_ref.interval());
816        }
817        if *high_bound > *node_ref.interval() {
818            IntervalTree::_intervals_between(
819                &node_ref.right_child,
820                low_bound,
821                high_bound,
822                intervals,
823            );
824        }
825    }
826
827    /// Returns all intervals in the tree following an in-order traversal.
828    /// Therefore intervals are sorted from smallest to largest
829    #[must_use]
830    pub fn intervals(&self) -> Vec<Interval<T>> {
831        let mut intervals: Vec<Interval<T>> = Vec::new();
832
833        IntervalTree::_intervals_in_order(&self.root, &mut intervals);
834
835        intervals
836    }
837
838    fn _intervals_in_order(node: &Option<Box<Node<T, V>>>, intervals: &mut Vec<Interval<T>>) {
839        if node.is_none() {
840            return;
841        }
842
843        let node_ref = node.as_ref().unwrap();
844        IntervalTree::_intervals_in_order(&node_ref.left_child, intervals);
845        intervals.push(node_ref.interval().duplicate());
846        IntervalTree::_intervals_in_order(&node_ref.right_child, intervals);
847    }
848
849    /// Returns the number of intervals in the tree less than `interval`
850    ///
851    /// # Arguments
852    /// * `interval`: interval to be searched for
853    ///
854    /// # Examples
855    /// ```
856    /// use store_interval_tree::IntervalTree;
857    /// use store_interval_tree::Interval;
858    /// use std::ops::Bound::*;
859    ///
860    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
861    ///
862    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
863    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
864    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
865    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
866    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
867    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
868    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
869    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
870    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
871    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
872    ///
873    /// assert_eq!(interval_tree.rank(&Interval::point(5)), 1);
874    /// ```
875    #[must_use]
876    pub fn rank(&self, interval: &Interval<T>) -> usize {
877        IntervalTree::_rank(&self.root, interval)
878    }
879    fn _rank(node: &Option<Box<Node<T, V>>>, interval: &Interval<T>) -> usize {
880        if node.is_none() {
881            return 0;
882        }
883        let node_ref = node.as_ref().unwrap();
884        if *interval < *node_ref.interval() {
885            IntervalTree::_rank(&node_ref.left_child, interval)
886        } else if *interval >= *node_ref.interval() {
887            1 + Node::size(&node_ref.left_child)
888                + IntervalTree::_rank(&node_ref.right_child, interval)
889        } else {
890            Node::size(&node_ref.left_child)
891        }
892    }
893
894    /// Returns the number of intervals in the tree between `low_bound` and `high_bound`
895    ///
896    /// # Arguments
897    /// * `low_bound`: lowest interval of the range
898    /// * `high_bound`: highest interval of the range
899    ///
900    /// # Examples
901    /// ```
902    /// use store_interval_tree::IntervalTree;
903    /// use store_interval_tree::Interval;
904    /// use std::ops::Bound::*;
905    ///
906    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
907    ///
908    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
909    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
910    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
911    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
912    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
913    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
914    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
915    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
916    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
917    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
918    ///
919    /// let low = Interval::point(10);
920    /// let high = Interval::point(25);
921    /// assert_eq!(interval_tree.size_between(&low, &high), 5);
922    /// ```
923    #[must_use]
924    pub fn size_between(&self, low_bound: &Interval<T>, high_bound: &Interval<T>) -> usize {
925        if self.is_empty() {
926            return 0;
927        }
928        if *low_bound > *high_bound {
929            return 0;
930        }
931
932        self.rank(high_bound) - self.rank(low_bound) + 1
933    }
934}
935
936impl<T: Debug + Ord, V: Debug> Debug for IntervalTree<T, V> {
937    fn fmt(&self, fmt: &mut core::fmt::Formatter) -> core::fmt::Result {
938        fmt.write_str("IntervalTree ")?;
939        fmt.debug_set().entries(self.intervals().iter()).finish()
940    }
941}
942
943#[cfg(test)]
944mod tests {
945    use alloc::string::String;
946
947    use super::*;
948    use core::ops::Bound::{Excluded, Included, Unbounded};
949
950    #[test]
951    fn tree_interval_init() {
952        let interval_tree = IntervalTree::<usize, ()>::new();
953
954        assert!(interval_tree.is_empty());
955        assert_eq!(interval_tree.size(), 0);
956    }
957
958    #[test]
959    fn tree_interval_insert() {
960        let mut interval_tree = IntervalTree::<usize, ()>::new();
961
962        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
963        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
964        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
965        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
966        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
967        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
968        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
969        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
970        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
971        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
972
973        assert_eq!(interval_tree.size(), 10);
974    }
975
976    #[test]
977    fn tree_interval_find_overlap_1() {
978        let mut interval_tree = IntervalTree::<usize, ()>::new();
979
980        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
981        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
982        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
983        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
984        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
985        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
986        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
987        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
988        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
989        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
990
991        assert!(
992            format!(
993                "{}",
994                interval_tree
995                    .find_overlap(&Interval::new(Included(1), Included(2)))
996                    .unwrap()
997            ) == *"[0,3]"
998        );
999
1000        assert!(
1001            format!(
1002                "{}",
1003                interval_tree
1004                    .find_overlap(&Interval::new(Included(4), Included(5)))
1005                    .unwrap()
1006            ) == *"[5,8]"
1007        );
1008
1009        assert!(
1010            format!(
1011                "{}",
1012                interval_tree
1013                    .find_overlap(&Interval::new(Included(10), Included(14)))
1014                    .unwrap()
1015            ) == *"[6,10]"
1016        );
1017
1018        assert!(
1019            format!(
1020                "{}",
1021                interval_tree
1022                    .find_overlap(&Interval::new(Included(14), Included(15)))
1023                    .unwrap()
1024            ) == *"[15,23]"
1025        );
1026
1027        assert!(
1028            format!(
1029                "{}",
1030                interval_tree
1031                    .find_overlap(&Interval::new(Included(15), Included(18)))
1032                    .unwrap()
1033            ) == *"[16,21]"
1034        );
1035
1036        assert!(
1037            format!(
1038                "{}",
1039                interval_tree
1040                    .find_overlap(&Interval::new(Included(19), Included(19)))
1041                    .unwrap()
1042            ) == *"[19,20]"
1043        );
1044
1045        assert!(
1046            format!(
1047                "{}",
1048                interval_tree
1049                    .find_overlap(&Interval::new(Included(23), Included(23)))
1050                    .unwrap()
1051            ) == *"[15,23]"
1052        );
1053
1054        assert!(
1055            format!(
1056                "{}",
1057                interval_tree
1058                    .find_overlap(&Interval::new(Included(24), Included(26)))
1059                    .unwrap()
1060            ) == *"[25,30]"
1061        );
1062
1063        assert!(
1064            format!(
1065                "{}",
1066                interval_tree
1067                    .find_overlap(&Interval::new(Included(26), Included(36)))
1068                    .unwrap()
1069            ) == *"[25,30]"
1070        );
1071
1072        assert!(interval_tree
1073            .find_overlap(&Interval::new(Included(31), Included(36)))
1074            .is_none());
1075        assert!(interval_tree
1076            .find_overlap(&Interval::new(Included(12), Included(12)))
1077            .is_none());
1078        assert!(interval_tree
1079            .find_overlap(&Interval::new(Included(13), Included(13)))
1080            .is_none());
1081        assert!(interval_tree
1082            .find_overlap(&Interval::new(Included(12), Included(14)))
1083            .is_none());
1084    }
1085
1086    #[test]
1087    fn tree_interval_find_overlap_2() {
1088        let mut interval_tree = IntervalTree::<usize, ()>::new();
1089
1090        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
1091        interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
1092        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1093        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
1094        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1095        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
1096        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1097        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
1098        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
1099        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1100
1101        assert!(
1102            format!(
1103                "{}",
1104                interval_tree
1105                    .find_overlap(&Interval::new(Included(1), Included(2)))
1106                    .unwrap()
1107            ) == *"[0,3)"
1108        );
1109
1110        assert!(interval_tree
1111            .find_overlap(&Interval::new(Included(4), Included(5)))
1112            .is_none());
1113
1114        assert!(
1115            format!(
1116                "{}",
1117                interval_tree
1118                    .find_overlap(&Interval::new(Included(10), Included(14)))
1119                    .unwrap()
1120            ) == *"[6,10]"
1121        );
1122
1123        assert!(interval_tree
1124            .find_overlap(&Interval::new(Included(14), Included(15)))
1125            .is_none());
1126
1127        assert!(
1128            format!(
1129                "{}",
1130                interval_tree
1131                    .find_overlap(&Interval::new(Included(15), Included(18)))
1132                    .unwrap()
1133            ) == *"[16,21)"
1134        );
1135
1136        assert!(
1137            format!(
1138                "{}",
1139                interval_tree
1140                    .find_overlap(&Interval::new(Included(19), Included(19)))
1141                    .unwrap()
1142            ) == *"[16,21)"
1143        );
1144
1145        assert!(
1146            format!(
1147                "{}",
1148                interval_tree
1149                    .find_overlap(&Interval::new(Excluded(23), Included(26)))
1150                    .unwrap()
1151            ) == *"(25,30]"
1152        );
1153
1154        assert!(interval_tree
1155            .find_overlap(&Interval::new(Excluded(10), Excluded(15)))
1156            .is_none());
1157
1158        assert!(
1159            format!(
1160                "{}",
1161                interval_tree
1162                    .find_overlap(&Interval::new(Excluded(21), Included(23)))
1163                    .unwrap()
1164            ) == *"(15,23)"
1165        );
1166
1167        assert!(interval_tree
1168            .find_overlap(&Interval::new(Included(31), Included(36)))
1169            .is_none());
1170        assert!(interval_tree
1171            .find_overlap(&Interval::new(Included(12), Included(12)))
1172            .is_none());
1173        assert!(interval_tree
1174            .find_overlap(&Interval::new(Included(13), Included(13)))
1175            .is_none());
1176        assert!(interval_tree
1177            .find_overlap(&Interval::new(Included(12), Included(14)))
1178            .is_none());
1179    }
1180
1181    #[test]
1182    fn tree_interval_find_overlap_3() {
1183        let mut interval_tree = IntervalTree::<usize, ()>::new();
1184
1185        interval_tree.insert(Interval::new(Unbounded, Excluded(3)), ());
1186        interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
1187        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1188        interval_tree.insert(Interval::new(Unbounded, Included(9)), ());
1189        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1190        interval_tree.insert(Interval::new(Unbounded, Excluded(21)), ());
1191        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1192        interval_tree.insert(Interval::new(Excluded(19), Unbounded), ());
1193        interval_tree.insert(Interval::new(Unbounded, Included(30)), ());
1194        interval_tree.insert(Interval::new(Included(26), Unbounded), ());
1195
1196        assert!(
1197            format!(
1198                "{}",
1199                interval_tree
1200                    .find_overlap(&Interval::new(Included(1), Included(2)))
1201                    .unwrap()
1202            ) == *"(_,9]"
1203        );
1204
1205        assert!(
1206            format!(
1207                "{}",
1208                interval_tree
1209                    .find_overlap(&Interval::new(Included(4), Included(5)))
1210                    .unwrap()
1211            ) == *"(_,9]"
1212        );
1213
1214        assert!(
1215            format!(
1216                "{}",
1217                interval_tree
1218                    .find_overlap(&Interval::new(Included(10), Included(14)))
1219                    .unwrap()
1220            ) == *"(_,21)"
1221        );
1222
1223        assert!(
1224            format!(
1225                "{}",
1226                interval_tree
1227                    .find_overlap(&Interval::new(Included(14), Included(15)))
1228                    .unwrap()
1229            ) == *"(_,21)"
1230        );
1231
1232        assert!(
1233            format!(
1234                "{}",
1235                interval_tree
1236                    .find_overlap(&Interval::new(Included(15), Included(18)))
1237                    .unwrap()
1238            ) == *"(_,21)"
1239        );
1240
1241        assert!(
1242            format!(
1243                "{}",
1244                interval_tree
1245                    .find_overlap(&Interval::new(Included(19), Included(19)))
1246                    .unwrap()
1247            ) == *"(_,21)"
1248        );
1249
1250        assert!(
1251            format!(
1252                "{}",
1253                interval_tree
1254                    .find_overlap(&Interval::new(Excluded(23), Included(26)))
1255                    .unwrap()
1256            ) == *"(_,30]"
1257        );
1258
1259        assert!(
1260            format!(
1261                "{}",
1262                interval_tree
1263                    .find_overlap(&Interval::new(Excluded(21), Included(23)))
1264                    .unwrap()
1265            ) == *"(_,30]"
1266        );
1267
1268        assert!(
1269            format!(
1270                "{}",
1271                interval_tree
1272                    .find_overlap(&Interval::new(Unbounded, Included(0)))
1273                    .unwrap()
1274            ) == *"(_,9]"
1275        );
1276    }
1277
1278    #[test]
1279    fn tree_interval_delete_1() {
1280        let mut interval_tree = IntervalTree::<usize, ()>::new();
1281
1282        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
1283        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
1284        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1285        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
1286        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
1287        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
1288        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
1289        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
1290        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
1291        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1292        let mut interval = Interval::new(Included(1), Included(2));
1293        let mut overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
1294        interval_tree.delete(&overlapped_interval);
1295        assert!(interval_tree.find_overlap(&interval).is_none());
1296
1297        interval = Interval::new(Included(15), Included(18));
1298        overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
1299        interval_tree.delete(&overlapped_interval);
1300        overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
1301        interval_tree.delete(&overlapped_interval);
1302        overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
1303        interval_tree.delete(&overlapped_interval);
1304        assert!(interval_tree.find_overlap(&interval).is_none());
1305    }
1306
1307    #[test]
1308    fn tree_interval_delete_max_1() {
1309        let mut interval_tree = IntervalTree::<usize, ()>::new();
1310
1311        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
1312        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
1313        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1314        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
1315        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1316        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
1317        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1318        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
1319        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
1320        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1321        interval_tree.delete_max();
1322        interval_tree.delete_max();
1323
1324        assert!(interval_tree
1325            .find_overlap(&Interval::new(Included(23), Included(23)))
1326            .is_none());
1327    }
1328
1329    #[test]
1330    fn tree_interval_delete_min_1() {
1331        let mut interval_tree = IntervalTree::<usize, ()>::new();
1332
1333        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
1334        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
1335        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1336        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
1337        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
1338        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
1339        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
1340        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
1341        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
1342        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1343        interval_tree.delete_min();
1344        interval_tree.delete_min();
1345
1346        assert!(interval_tree
1347            .find_overlap(&Interval::new(Included(1), Excluded(6)))
1348            .is_none());
1349    }
1350
1351    #[test]
1352    fn tree_interval_select_1() {
1353        let mut interval_tree = IntervalTree::<usize, ()>::new();
1354
1355        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
1356        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
1357        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1358        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
1359        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1360        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
1361        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1362        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
1363        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
1364        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1365        assert!(format!("{}", interval_tree.select(0).unwrap()) == *"[0,3)");
1366        assert!(format!("{}", interval_tree.select(1).unwrap()) == *"(0,1]");
1367        assert!(format!("{}", interval_tree.select(2).unwrap()) == *"[6,10]");
1368        assert!(format!("{}", interval_tree.select(3).unwrap()) == *"(8,9]");
1369        assert!(format!("{}", interval_tree.select(4).unwrap()) == *"(15,23)");
1370        assert!(format!("{}", interval_tree.select(5).unwrap()) == *"[16,21)");
1371        assert!(format!("{}", interval_tree.select(6).unwrap()) == *"[17,19)");
1372        assert!(format!("{}", interval_tree.select(7).unwrap()) == *"(19,20]");
1373        assert!(format!("{}", interval_tree.select(8).unwrap()) == *"(25,30]");
1374        assert!(format!("{}", interval_tree.select(9).unwrap()) == *"[26,26]");
1375    }
1376
1377    #[test]
1378    fn tree_interval_intervals_between_1() {
1379        let mut interval_tree = IntervalTree::<usize, ()>::new();
1380
1381        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
1382        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
1383        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1384        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
1385        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1386        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
1387        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1388        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
1389        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
1390        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1391
1392        let low = Interval::new(Included(14), Included(14));
1393        let high = Interval::new(Included(24), Included(24));
1394        let intervals = interval_tree.intervals_between(&low, &high);
1395
1396        let accept = String::from("(15,23)[16,21)[17,19)(19,20]");
1397
1398        let mut result = String::from("");
1399        for interval in intervals {
1400            result.push_str(&format!("{}", interval));
1401        }
1402
1403        assert_eq!(result, accept);
1404    }
1405
1406    #[test]
1407    fn tree_interval_find_overlaps_1() {
1408        let mut interval_tree = IntervalTree::<usize, ()>::new();
1409
1410        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
1411        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
1412        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1413        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
1414        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1415        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
1416        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1417        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
1418        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
1419        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1420
1421        let interval = Interval::new(Included(8), Included(26));
1422        let intervals = interval_tree.find_overlaps(&interval);
1423
1424        let accept = String::from("(8,9][6,10](19,20][16,21)(15,23)[17,19)(25,30][26,26]");
1425
1426        let mut result = String::from("");
1427        for interval in intervals {
1428            result.push_str(&format!("{}", interval));
1429        }
1430
1431        assert_eq!(result, accept);
1432    }
1433
1434    #[test]
1435    fn tree_interval_query_1() {
1436        let mut interval_tree = IntervalTree::<usize, ()>::new();
1437
1438        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
1439        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
1440        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
1441        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
1442        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
1443        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
1444        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
1445        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
1446        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
1447        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
1448
1449        let interval = Interval::new(Included(8), Included(26));
1450        let iter = interval_tree.query(&interval);
1451
1452        let accept = String::from("(8,9][6,10](19,20][16,21)(15,23)[17,19)(25,30][26,26]");
1453
1454        let mut result = String::from("");
1455        for entry in iter {
1456            result.push_str(&format!("{}", entry.interval()));
1457        }
1458
1459        assert_eq!(result, accept);
1460    }
1461
1462    #[test]
1463    fn tree_interval_query_2() {
1464        let mut interval_tree = IntervalTree::<usize, bool>::new();
1465
1466        interval_tree.insert(Interval::new(Excluded(0), Included(1)), true);
1467        interval_tree.insert(Interval::new(Included(0), Excluded(3)), true);
1468        interval_tree.insert(Interval::new(Included(6), Included(10)), true);
1469        interval_tree.insert(Interval::new(Excluded(8), Included(9)), true);
1470        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), true);
1471        interval_tree.insert(Interval::new(Included(16), Excluded(21)), true);
1472        interval_tree.insert(Interval::new(Included(17), Excluded(19)), true);
1473        interval_tree.insert(Interval::new(Excluded(19), Included(20)), true);
1474        interval_tree.insert(Interval::new(Excluded(25), Included(30)), true);
1475        interval_tree.insert(Interval::new(Included(26), Included(26)), true);
1476
1477        let interval = Interval::new(Included(8), Included(26));
1478        let iter = interval_tree.query_mut(&interval);
1479
1480        for mut entry in iter {
1481            *entry.value() = false;
1482        }
1483
1484        let iter = interval_tree.query(&interval);
1485        for entry in iter {
1486            assert!(!*entry.value());
1487        }
1488    }
1489
1490    #[test]
1491    fn tree_interval_debug() {
1492        let mut interval_tree = IntervalTree::<usize, ()>::new();
1493        assert_eq!(format!("{:?}", &interval_tree), "IntervalTree {}");
1494        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
1495        assert_eq!(
1496            format!("{:?}", &interval_tree),
1497            "IntervalTree {Interval { low: Excluded(0), high: Included(1) }}"
1498        );
1499    }
1500}
store_interval_tree/lib.rs

store_interval_tree/
lib.rs
