rudac/tree/
interval.rs

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

rudac/tree/
interval.rs
