unbounded_interval_tree/
interval_tree.rs

1use crate::node::{Node, Range};
2
3use std::borrow::Borrow;
4use std::cmp::Ordering;
5use std::cmp::Ordering::*;
6use std::fmt;
7use std::mem;
8use std::ops::Bound;
9use std::ops::Bound::*;
10use std::ops::RangeBounds;
11#[cfg(any(feature="serde", test))]
12use serde::{Serialize, Deserialize};
13
14/// The interval tree storing all the underlying intervals.
15///
16/// There are three ways to create an interval tree.
17/// ```
18/// use unbounded_interval_tree::interval_tree::IntervalTree;
19///
20/// // 1. Create an empty default interval tree.
21/// let mut interval_tree = IntervalTree::default();
22/// assert!(interval_tree.is_empty());
23/// interval_tree.insert(0..9);
24/// interval_tree.insert(27..);
25/// assert_eq!(interval_tree.len(), 2);
26///
27/// // 2. Create an interval tree from an iterator.
28/// let ranges = vec!["hello"..="hi", "Allo"..="Bonjour"];
29/// let interval_tree = ranges.into_iter().collect::<IntervalTree<_>>();
30/// assert_eq!(interval_tree.len(), 2);
31///
32/// // 3. Create an interval tree from an array.
33/// let ranges = [(1, 5)..(1,9), (2, 3)..(3, 7)];
34/// let interval_tree = IntervalTree::from(ranges);
35/// assert_eq!(interval_tree.len(), 2);
36/// ```
37#[cfg_attr(any(feature="serde", test), derive(Serialize, Deserialize))]
38#[derive(Clone, Debug, PartialEq)]
39pub struct IntervalTree<K> {
40    root: Option<Box<Node<K>>>,
41    size: usize,
42}
43
44impl<K> fmt::Display for IntervalTree<K>
45where
46    K: fmt::Display,
47{
48    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
49        match self.root {
50            Some(ref root) => write!(f, "{}", root),
51            None => write!(f, "Empty tree"),
52        }
53    }
54}
55
56impl<K> Default for IntervalTree<K> {
57    fn default() -> IntervalTree<K> {
58        IntervalTree {
59            root: None,
60            size: 0,
61        }
62    }
63}
64
65/// Creates an [`IntervalTree`] from an iterator of elements
66/// satisfying the [`RangeBounds`] trait.
67impl<K, R> FromIterator<R> for IntervalTree<K>
68where
69    K: Ord + Clone,
70    R: RangeBounds<K>,
71{
72    fn from_iter<T: IntoIterator<Item = R>>(iter: T) -> Self {
73        let mut interval_tree = Self::default();
74
75        for interval in iter {
76            interval_tree.insert(interval);
77        }
78
79        interval_tree
80    }
81}
82
83impl<K, R, const N: usize> From<[R; N]> for IntervalTree<K>
84where
85    K: Ord + Clone,
86    R: RangeBounds<K>,
87{
88    fn from(intervals: [R; N]) -> Self {
89        let mut interval_tree = Self::default();
90
91        for interval in intervals {
92            interval_tree.insert(interval);
93        }
94
95        interval_tree
96    }
97}
98
99impl<K> IntervalTree<K> {
100    /// Produces an inorder iterator for the interval tree.
101    ///
102    /// # Examples
103    ///
104    /// ```
105    /// use std::ops::Bound::Included;
106    /// use unbounded_interval_tree::interval_tree::IntervalTree;
107    ///
108    /// let mut tree = IntervalTree::default();
109    ///
110    /// tree.insert((Included(0), Included(10)));
111    /// tree.insert((Included(-5), Included(-1)));
112    /// tree.insert((Included(20), Included(30)));
113    ///
114    /// let mut iter = tree.iter();
115    /// assert_eq!(iter.next(), Some(&(Included(-5), Included(-1))));
116    /// assert_eq!(iter.next(), Some(&(Included(0), Included(10))));
117    /// assert_eq!(iter.next(), Some(&(Included(20), Included(30))));
118    /// assert_eq!(iter.next(), None);
119    /// ```
120    pub fn iter<'a>(&'a self) -> IntervalTreeIter<'a, K> {
121        IntervalTreeIter {
122            to_visit: vec![],
123            curr: &self.root,
124        }
125    }
126
127    /// Inserts an interval `range` into the interval tree. Insertions respect the
128    /// binary search properties of this tree.
129    /// It is ok to insert a `range` that overlaps with an existing interval in the tree.
130    ///
131    /// An improvement to come is to rebalance the tree (following an AVL or a red-black scheme).
132    ///
133    /// # Examples
134    ///
135    /// ```
136    /// use std::ops::Bound::{Included, Excluded, Unbounded};
137    /// use unbounded_interval_tree::interval_tree::IntervalTree;
138    ///
139    /// let mut int_tree = IntervalTree::default();
140    ///
141    /// int_tree.insert((Included(5), Excluded(9)));
142    /// int_tree.insert(..=10);
143    ///
144    /// let mut str_tree: IntervalTree<&str> = IntervalTree::default();
145    ///
146    /// str_tree.insert("Noria"..);
147    /// ```
148    pub fn insert<R>(&mut self, range: R)
149    where
150        K: Ord + Clone,
151        R: RangeBounds<K>,
152    {
153        let range = (range.start_bound().cloned(), range.end_bound().cloned());
154        self.size += 1;
155
156        // If the tree is empty, put new node at the root.
157        if self.root.is_none() {
158            self.root = Some(Box::new(Node::new(range)));
159            return;
160        }
161
162        // Otherwise, walk down the tree and insert when we reach leaves.
163        // TODO(jonathangb): Rotate tree?
164        let mut curr = self.root.as_mut().unwrap();
165        loop {
166            curr.maybe_update_value(&range.1);
167
168            match Self::cmp(&curr.key, &range) {
169                Equal => return, // Don't insert a redundant key.
170                Less => {
171                    match curr.right {
172                        None => {
173                            curr.right = Some(Box::new(Node::new(range)));
174                            return;
175                        }
176                        Some(ref mut node) => curr = node,
177                    };
178                }
179                Greater => {
180                    match curr.left {
181                        None => {
182                            curr.left = Some(Box::new(Node::new(range)));
183                            return;
184                        }
185                        Some(ref mut node) => curr = node,
186                    };
187                }
188            };
189        }
190    }
191
192    /// A "stabbing query" in the jargon: returns whether or not a point `p`
193    /// is contained in any of the intervals stored in the tree.
194    ///
195    /// The given point may be of a borrowed form of the stored type `K`.
196    ///
197    /// # Examples
198    ///
199    /// ```
200    /// use std::ops::Bound::{Excluded, Unbounded};
201    /// use unbounded_interval_tree::interval_tree::IntervalTree;
202    ///
203    /// let mut int_tree = IntervalTree::default();
204    ///
205    /// int_tree.insert((Excluded(5), Unbounded));
206    ///
207    /// assert!(int_tree.contains_point(&100));
208    /// assert!(!int_tree.contains_point(&5));
209    /// ```
210    ///
211    /// Note that we can work with any type that implements the [`Ord`] trait, so
212    /// we are not limited to just integers.
213    ///
214    /// ```
215    /// use std::ops::Bound::{Excluded, Unbounded};
216    /// use unbounded_interval_tree::interval_tree::IntervalTree;
217    ///
218    /// let mut str_tree = IntervalTree::default();
219    ///
220    /// str_tree.insert((Excluded(String::from("Noria")), Unbounded));
221    ///
222    /// // Borrowed form (`str`) of `String`.
223    /// assert!(!str_tree.contains_point("Noria"));
224    /// // Also works with non-borrowed form.
225    /// assert!(str_tree.contains_point(&String::from("Zebra")));
226    /// ```
227    pub fn contains_point<Q>(&self, p: &Q) -> bool
228    where
229        K: Ord + Borrow<Q>,
230        Q: Ord + ?Sized,
231    {
232        self.contains_interval(&(Included(p), Included(p)))
233    }
234
235    /// An alternative "stabbing query": returns whether or not an interval `range`
236    /// is fully covered by the intervals stored in the tree.
237    ///
238    /// The given `range` may have bounds that are of a borrowed form of the stored type `K`.
239    ///
240    /// # Examples
241    ///
242    /// ```
243    /// use std::ops::Bound::{Included, Excluded, Unbounded};
244    /// use unbounded_interval_tree::interval_tree::IntervalTree;
245    ///
246    /// let mut tree = IntervalTree::default();
247    ///
248    /// tree.insert((Included(20), Included(30)));
249    /// tree.insert((Excluded(30), Excluded(50)));
250    ///
251    /// assert!(tree.contains_interval(&(20..=40)));
252    /// // Borrowed form of the key works as well.
253    /// assert!(!tree.contains_interval(&(&30..=&50)));
254    /// ```
255    ///
256    /// Again, the given `range` can be any type implementing [`Ord`].
257    ///
258    /// ```
259    /// use std::ops::Bound::{Included, Excluded, Unbounded};
260    /// use unbounded_interval_tree::interval_tree::IntervalTree;
261    ///
262    /// let mut tree: IntervalTree<&str> = IntervalTree::default();
263    ///
264    /// let key1 = (Included("a"), Excluded("h"));
265    /// let key2 = (Excluded("M"), Excluded("O"));
266    ///
267    /// tree.insert(key1.clone());
268    /// tree.insert(key2);
269    ///
270    /// assert!(tree.contains_interval(&("a".."h")));
271    /// assert!(!tree.contains_interval(&("N"..="O")));
272    /// // Sometimes, we have to disambiguate the key type.
273    /// assert!(tree.contains_interval::<&str, _>(&key1));
274    /// ```
275    pub fn contains_interval<Q, R>(&self, range: &R) -> bool
276    where
277        K: Ord + Borrow<Q>,
278        R: RangeBounds<Q>,
279        Q: Ord + ?Sized,
280    {
281        self.get_interval_difference(range).is_empty()
282    }
283
284    /// Returns the inorder list of all references to intervals stored in the tree that overlaps
285    /// with the given `range` (partially or completely).
286    ///
287    /// The given `range` may have bounds that are of a borrowed form of the stored type `K`.
288    ///
289    /// # Examples
290    ///
291    /// ```
292    /// use std::ops::Bound::{Included, Excluded, Unbounded};
293    /// use unbounded_interval_tree::interval_tree::IntervalTree;
294    ///
295    /// let mut tree = IntervalTree::default();
296    ///
297    /// tree.insert((Included(0), Included(5)));
298    /// tree.insert((Included(7), Excluded(10)));
299    ///
300    /// assert_eq!(tree.get_interval_overlaps(&(-5..7)),
301    ///            vec![&(Included(0), Included(5))]);
302    /// // Borrowed form of the key works as well.
303    /// assert!(tree.get_interval_overlaps(&(&10..)).is_empty());
304    /// ```
305    pub fn get_interval_overlaps<Q, R>(&self, range: &R) -> Vec<&Range<K>>
306    where
307        K: Ord + Borrow<Q>,
308        R: RangeBounds<Q>,
309        Q: Ord + ?Sized,
310    {
311        let curr = &self.root;
312        let mut acc = Vec::new();
313
314        Self::get_interval_overlaps_rec(curr, range, &mut acc);
315        acc
316    }
317
318    /// Returns the ordered list of subintervals in `range` that are not covered by the tree.
319    /// This is useful to compute what subsegments of `range` that are not covered by the intervals
320    /// stored in the tree.
321    ///
322    /// If `range` is not covered at all, this simply returns a one element vector
323    /// containing the bounds of `range`.
324    ///
325    /// The given `range` may have bounds that are of a borrowed form of the stored type `K`.
326    /// Because all the bounds returned are either from the interval tree of from the `range`, we return
327    /// references to these bounds rather than clone them.
328    ///
329    /// # Examples
330    ///
331    /// ```
332    /// use std::ops::Bound::{Included, Excluded, Unbounded};
333    /// use unbounded_interval_tree::interval_tree::IntervalTree;
334    ///
335    /// let mut tree = IntervalTree::default();
336    ///
337    /// tree.insert((Included(0), Excluded(10)));
338    /// tree.insert((Excluded(10), Included(30)));
339    /// tree.insert((Excluded(50), Unbounded));
340    ///
341    /// assert_eq!(tree.get_interval_difference(&(-5..=30)),
342    ///            vec![(Included(&-5), Excluded(&0)),
343    ///                 (Included(&10), Included(&10))]);
344    /// assert_eq!(tree.get_interval_difference(&(..10)),
345    ///            vec![(Unbounded, Excluded(&0))]);
346    /// assert!(tree.get_interval_difference(&(100..)).is_empty());
347    /// ```
348    pub fn get_interval_difference<'a, Q, R>(&'a self, range: &'a R) -> Vec<Range<&'a Q>>
349    where
350        K: Ord + Borrow<Q>,
351        R: RangeBounds<Q>,
352        Q: Ord + ?Sized,
353    {
354        let overlaps = self.get_interval_overlaps(range);
355
356        // If there is no overlap, then the difference is the query `q` itself.
357        if overlaps.is_empty() {
358            let min = match range.start_bound() {
359                Included(x) => Included(x),
360                Excluded(x) => Excluded(x),
361                Unbounded => Unbounded,
362            };
363            let max = match range.end_bound() {
364                Included(x) => Included(x),
365                Excluded(x) => Excluded(x),
366                Unbounded => Unbounded,
367            };
368            return vec![(min, max)];
369        }
370
371        let mut acc = Vec::new();
372        let first = overlaps.first().unwrap();
373
374        // If q.min < first.min, we have a difference to append.
375        match (range.start_bound(), first.start_bound()) {
376            (Unbounded, Included(first_min)) => acc.push((Unbounded, Excluded(first_min.borrow()))),
377            (Unbounded, Excluded(first_min)) => acc.push((Unbounded, Included(first_min.borrow()))),
378            (Included(q_min), Included(first_min)) if q_min < first_min.borrow() => {
379                acc.push((Included(q_min), Excluded(first_min.borrow())))
380            }
381            (Excluded(q_min), Included(first_min)) if q_min < first_min.borrow() => {
382                acc.push((Excluded(q_min), Excluded(first_min.borrow())))
383            }
384            (Excluded(q_min), Excluded(first_min)) if q_min < first_min.borrow() => {
385                acc.push((Excluded(q_min), Included(first_min.borrow())))
386            }
387            (Included(q_min), Excluded(first_min)) if q_min <= first_min.borrow() => {
388                acc.push((Included(q_min), Included(first_min.borrow())))
389            }
390            _ => {}
391        };
392
393        // If the max is unbounded, there can't be any difference going forward.
394        if first.1 == Unbounded {
395            return acc;
396        }
397
398        let mut contiguous = &first.1; // keeps track of the maximum of a contiguous interval.
399        for overlap in overlaps.iter().skip(1) {
400            // If contiguous < overlap.min:
401            //   1. We have a difference between contiguous -> overlap.min to fill.
402            //     1.1: Note: the endpoints of the difference appended are the opposite,
403            //          that is if contiguous was Included, then the difference must
404            //          be Excluded, and vice versa.
405            //   2. We need to update contiguous to be the new contiguous max.
406            // Note: an Included+Excluded at the same point still is contiguous!
407            match (&contiguous, &overlap.0) {
408                (Included(contiguous_max), Included(overlap_min))
409                    if contiguous_max < overlap_min =>
410                {
411                    acc.push((
412                        Excluded(contiguous_max.borrow()),
413                        Excluded(overlap_min.borrow()),
414                    ));
415                    contiguous = &overlap.1;
416                }
417                (Included(contiguous_max), Excluded(overlap_min))
418                    if contiguous_max < overlap_min =>
419                {
420                    acc.push((
421                        Excluded(contiguous_max.borrow()),
422                        Included(overlap_min.borrow()),
423                    ));
424                    contiguous = &overlap.1;
425                }
426                (Excluded(contiguous_max), Included(overlap_min))
427                    if contiguous_max < overlap_min =>
428                {
429                    acc.push((
430                        Included(contiguous_max.borrow()),
431                        Excluded(overlap_min.borrow()),
432                    ));
433                    contiguous = &overlap.1;
434                }
435                (Excluded(contiguous_max), Excluded(overlap_min))
436                    if contiguous_max <= overlap_min =>
437                {
438                    acc.push((
439                        Included(contiguous_max.borrow()),
440                        Included(overlap_min.borrow()),
441                    ));
442                    contiguous = &overlap.1;
443                }
444                _ => {}
445            }
446
447            // If contiguous.max < overlap.max, we set contiguous to the new max.
448            match (&contiguous, &overlap.1) {
449                (_, Unbounded) => return acc,
450                (Included(contiguous_max), Included(overlap_max))
451                | (Excluded(contiguous_max), Excluded(overlap_max))
452                | (Included(contiguous_max), Excluded(overlap_max))
453                    if contiguous_max < overlap_max =>
454                {
455                    contiguous = &overlap.1
456                }
457                (Excluded(contiguous_max), Included(overlap_max))
458                    if contiguous_max <= overlap_max =>
459                {
460                    contiguous = &overlap.1
461                }
462                _ => {}
463            };
464        }
465
466        // If contiguous.max < q.max, we have a difference to append.
467        match (&contiguous, range.end_bound()) {
468            (Included(contiguous_max), Included(q_max)) if contiguous_max.borrow() < q_max => {
469                acc.push((Excluded(contiguous_max.borrow()), Included(q_max)))
470            }
471            (Included(contiguous_max), Excluded(q_max)) if contiguous_max.borrow() < q_max => {
472                acc.push((Excluded(contiguous_max.borrow()), Excluded(q_max)))
473            }
474            (Excluded(contiguous_max), Excluded(q_max)) if contiguous_max.borrow() < q_max => {
475                acc.push((Included(contiguous_max.borrow()), Excluded(q_max)))
476            }
477            (Excluded(contiguous_max), Included(q_max)) if contiguous_max.borrow() <= q_max => {
478                acc.push((Included(contiguous_max.borrow()), Included(q_max)))
479            }
480            _ => {}
481        };
482
483        acc
484    }
485
486    fn get_interval_overlaps_rec<'a, Q, R>(
487        curr: &'a Option<Box<Node<K>>>,
488        range: &R,
489        acc: &mut Vec<&'a Range<K>>,
490    ) where
491        K: Ord + Borrow<Q>,
492        R: RangeBounds<Q>,
493        Q: Ord + ?Sized,
494    {
495        // If we reach None, stop recursing along this subtree.
496        let node = match curr {
497            None => return,
498            Some(node) => node,
499        };
500
501        // See if subtree.max < q.min. If that is the case, there is no point
502        // in visiting the rest of the subtree (we know that the rest of the intervals
503        // will necessarily be smaller than `q`).
504        // ~ Recall the ordering rules (as defined in `fn cmp` below). ~
505        // -> If subtree.max is Unbounded, subtree.max < q.min is impossible.
506        // -> If q.min is Unbounded, subtree.max < q.min is impossible.
507        // -> If they are equal, we have 4 cases:
508        //  * subtree.max: Included(x) / q.min: Included(x) -> =, we keep visiting the subtree
509        //  * subtree.max: Included(x) / q.min: Excluded(x) -> <, condition satisfied
510        //  * subtree.max: Excluded(x) / q.min: Included(x) -> <, condition satisfied
511        //  * subtree.max: Excluded(x) / q.min: Excluded(x) -> <, condition satisfied
512        let max_subtree = match &node.value {
513            Included(x) => Some((x.borrow(), 2)),
514            Excluded(x) => Some((x.borrow(), 1)),
515            Unbounded => None,
516        };
517        let min_q = match range.start_bound() {
518            Included(x) => Some((x, 2)),
519            Excluded(x) => Some((x, 3)),
520            Unbounded => None,
521        };
522        match (max_subtree, min_q) {
523            (Some(max_subtree), Some(min_q)) if max_subtree < min_q => return,
524            _ => {}
525        };
526
527        // Search left subtree.
528        Self::get_interval_overlaps_rec(&node.left, range, acc);
529
530        // Visit this node.
531        // If node.min <= q.max AND node.max >= q.min, we have an intersection.
532        // Let's start with the first inequality, node.min <= q.max.
533        // -> If node.min is Unbounded, node.min <= q.max is a tautology.
534        // -> If q.max is Unbounded, node.min <= q.max is a tautology.
535        // -> If they are equal, we have 4 cases:
536        //  * node.min: Included(x) / q.max: Included(x) -> =, we go to 2nd inequality
537        //  * node.min: Included(x) / q.max: Excluded(x) -> >, 1st inequality not satisfied
538        //  * node.min: Excluded(x) / q.max: Included(x) -> >, 1st inequality not satisfied
539        //  * node.min: Excluded(x) / q.max: Excluded(x) -> >, 1st inequality not satisfied
540        //
541        // Notice that after we visit the node, we should visit the right subtree. However,
542        // if node.min > q.max, we can skip right visiting the right subtree.
543        // -> If node.min is Unbounded, node.min > q.max is impossible.
544        // -> If q.max is Unbounded, node.min > q.max is impossible.
545        //
546        // It just so happens that we already do this check in the match to satisfy
547        // the previous first condition. Hence, we decided to add an early return
548        // in there, rather than repeat the logic afterwards.
549        let min_node = match &node.key.0 {
550            Included(x) => Some((x.borrow(), 2)),
551            Excluded(x) => Some((x.borrow(), 3)),
552            Unbounded => None,
553        };
554        let max_q = match range.end_bound() {
555            Included(x) => Some((x, 2)),
556            Excluded(x) => Some((x, 1)),
557            Unbounded => None,
558        };
559        match (min_node, max_q) {
560            // If the following condition is met, we do not have an intersection.
561            // On top of that, we know that we can skip visiting the right subtree,
562            // so we can return eagerly.
563            (Some(min_node), Some(max_q)) if min_node > max_q => return,
564            _ => {
565                // Now we are at the second inequality, node.max >= q.min.
566                // -> If node.max is Unbounded, node.max >= q.min is a tautology.
567                // -> If q.min is Unbounded, node.max >= q.min is a tautology.
568                // -> If they are equal, we have 4 cases:
569                //  * node.max: Included(x) / q.min: Included(x) -> =, 2nd inequality satisfied
570                //  * node.max: Included(x) / q.min: Excluded(x) -> <, 2nd inequality not satisfied
571                //  * node.max: Excluded(x) / q.min: Included(x) -> <, 2nd inequality not satisfied
572                //  * node.max: Excluded(x) / q.min: Excluded(x) -> <, 2nd inequality not satisfied
573                let max_node = match &node.key.1 {
574                    Included(x) => Some((x.borrow(), 2)),
575                    Excluded(x) => Some((x.borrow(), 1)),
576                    Unbounded => None,
577                };
578
579                match (max_node, min_q) {
580                    (Some(max_node), Some(min_q)) if max_node < min_q => {}
581                    _ => acc.push(&node.key),
582                };
583            }
584        };
585
586        // Search right subtree.
587        Self::get_interval_overlaps_rec(&node.right, range, acc);
588    }
589
590    /// Removes a random leaf from the tree,
591    /// and returns the range stored in the said node.
592    ///
593    /// The returned value will be `None` if the tree is empty.
594    ///
595    /// # Examples
596    ///
597    /// ```
598    /// use std::ops::Bound::{Included, Excluded, Unbounded};
599    /// use unbounded_interval_tree::interval_tree::IntervalTree;
600    ///
601    /// let mut tree = IntervalTree::default();
602    ///
603    /// tree.insert((Included(5), Excluded(9)));
604    /// tree.insert((Unbounded, Included(10)));
605    ///
606    /// assert!(tree.contains_point(&10));
607    /// assert!(tree.contains_point(&6));
608    ///
609    /// let deleted = tree.remove_random_leaf();
610    /// assert!(deleted.is_some());
611    /// assert!(!tree.contains_point(&10));
612    /// assert!(tree.contains_point(&6));
613    ///
614    /// let deleted = tree.remove_random_leaf();
615    /// assert!(deleted.is_some());
616    /// assert!(!tree.contains_point(&6));
617    ///
618    /// let deleted = tree.remove_random_leaf();
619    /// assert!(deleted.is_none());
620    /// ```
621    pub fn remove_random_leaf(&mut self) -> Option<Range<K>>
622    where
623        K: Ord + Clone,
624    {
625        use rand::random;
626
627        // If interval tree is empty, just return None.
628        if self.root.is_none() {
629            return None;
630        }
631
632        self.size -= 1;
633
634        let mut curr = self.root.as_mut().unwrap();
635
636        // If we only have one node, delete it right away.
637        if curr.left.is_none() && curr.right.is_none() {
638            let root = mem::take(&mut self.root).unwrap();
639            return Some(root.key);
640        }
641
642        // Keep track of visited nodes, because we will need to walk up
643        // the tree after deleting the leaf in order to possibly update
644        // their value stored.
645        // The first element of the tuple is a &mut to the value of the node,
646        // whilst the second element is the new potential value to store, based
647        // on the non-visited path (recall that this is a BST). It
648        // is very much possible that both elements are equal: that would imply that the
649        // current value depends solely on the non-visited path, hence the deleted
650        // node will have no impact up the tree, at least from the current point.
651        let mut path: Vec<(_, _)> = Vec::new();
652
653        // Used to keep track of the direction taken from a node.
654        enum Direction {
655            LEFT,
656            RIGHT,
657        }
658
659        // Traverse the tree until we find a leaf.
660        let (deleted, new_max) = loop {
661            // Note that at this point in the loop, `curr` can't be a leaf.
662            // Indeed, we traverse the tree such that `curr` is always an
663            // internal node, so that it is easy to replace a leaf from `curr`.
664            let direction = if curr.left.is_none() {
665                Direction::RIGHT
666            } else if curr.right.is_none() {
667                Direction::LEFT
668            } else if random() {
669                Direction::LEFT
670            } else {
671                Direction::RIGHT
672            };
673            // End-bound of the current node.
674            let curr_end = &curr.key.1;
675
676            // LEFT and RIGHT paths are somewhat repetitive, but this way
677            // was the only way to satisfy the borrowchecker...
678            match direction {
679                Direction::LEFT => {
680                    // If we go left and the right path is `None`,
681                    // then the right path has no impact towards
682                    // the value stored by the current node.
683                    // Otherwise, the current node's value might change
684                    // to the other branch's max value once we remove the
685                    // leaf, so let's keep track of that.
686                    let max_other = if curr.right.is_none() {
687                        curr_end
688                    } else {
689                        let other_value = &curr.right.as_ref().unwrap().value;
690                        match Self::cmp_endbound(curr_end, other_value) {
691                            Greater | Equal => curr_end,
692                            Less => other_value,
693                        }
694                    };
695
696                    // Check if the next node is a leaf. If it is, then we want to
697                    // stop traversing, and remove the leaf.
698                    let next = curr.left.as_ref().unwrap();
699                    if next.is_leaf() {
700                        curr.value = max_other.clone();
701                        break (mem::take(&mut curr.left).unwrap(), max_other);
702                    }
703
704                    // If the next node is *not* a leaf, then we can update the visited path
705                    // with the current values, and move on to the next node.
706                    path.push((&mut curr.value, max_other));
707                    curr = curr.left.as_mut().unwrap();
708                }
709                Direction::RIGHT => {
710                    let max_other = if curr.left.is_none() {
711                        curr_end
712                    } else {
713                        let other_value = &curr.left.as_ref().unwrap().value;
714                        match Self::cmp_endbound(curr_end, other_value) {
715                            Greater | Equal => curr_end,
716                            Less => other_value,
717                        }
718                    };
719
720                    let next = curr.right.as_ref().unwrap();
721                    if next.is_leaf() {
722                        curr.value = max_other.clone();
723                        break (mem::take(&mut curr.right).unwrap(), max_other);
724                    }
725
726                    path.push((&mut curr.value, max_other));
727                    curr = curr.right.as_mut().unwrap();
728                }
729            };
730        };
731
732        // We have removed the leaf. Now, we bubble-up the visited path.
733        // If the removed node's value impacted its ancestors, then we update
734        // the ancestors' value so that they store the new max value in their
735        // respective subtree.
736        while let Some((value, max_other)) = path.pop() {
737            if Self::cmp_endbound(value, max_other) == Equal {
738                break;
739            }
740
741            match Self::cmp_endbound(value, new_max) {
742                Equal => break,
743                Greater => *value = new_max.clone(),
744                Less => unreachable!("Can't have a new max that is bigger"),
745            };
746        }
747
748        Some(deleted.key.clone())
749    }
750
751    /// Returns the number of ranges stored in the interval tree.
752    ///
753    /// # Examples
754    ///
755    /// ```
756    /// use std::ops::Bound::{Included, Excluded, Unbounded};
757    /// use unbounded_interval_tree::interval_tree::IntervalTree;
758    ///
759    /// let mut tree = IntervalTree::default();
760    ///
761    /// assert_eq!(tree.len(), 0);
762    ///
763    /// tree.insert((Included(5), Excluded(9)));
764    /// tree.insert((Unbounded, Included(10)));
765    ///
766    /// assert_eq!(tree.len(), 2);
767    /// ```
768    pub fn len(&self) -> usize {
769        self.size
770    }
771
772    /// Returns `true` if the map contains no element.
773    ///
774    /// # Examples
775    ///
776    /// ```
777    /// use std::ops::Bound::{Included, Excluded, Unbounded};
778    /// use unbounded_interval_tree::interval_tree::IntervalTree;
779    ///
780    /// let mut tree = IntervalTree::default();
781    ///
782    /// assert!(tree.is_empty());
783    ///
784    /// tree.insert((Included(5), Excluded(9)));
785    ///
786    /// assert!(!tree.is_empty());
787    /// ```
788    pub fn is_empty(&self) -> bool {
789        self.len() == 0
790    }
791
792    /// Clear the interval tree, removing all values stored.
793    ///
794    /// # Examples
795    ///
796    /// ```
797    /// use std::ops::Bound::{Included, Excluded, Unbounded};
798    /// use unbounded_interval_tree::interval_tree::IntervalTree;
799    ///
800    /// let mut tree = IntervalTree::default();
801    ///
802    /// tree.insert((Included(5), Unbounded));
803    /// tree.clear();
804    ///
805    /// assert!(tree.is_empty());
806    /// ```
807    pub fn clear(&mut self) {
808        self.root = None;
809        self.size = 0;
810    }
811
812    fn cmp(r1: &Range<K>, r2: &Range<K>) -> Ordering
813    where
814        K: Ord,
815    {
816        // Sorting by lower bound, then by upper bound.
817        //   -> Unbounded is the smallest lower bound.
818        //   -> Unbounded is the biggest upper bound.
819        //   -> Included(x) < Excluded(x) for a lower bound.
820        //   -> Included(x) > Excluded(x) for an upper bound.
821
822        // Unpacking from a Bound is annoying, so let's map it to an Option<K>.
823        // Let's use this transformation to encode the Included/Excluded rules at the same time.
824        // Note that topological order is used during comparison, so if r1 and r2 have the same `x`,
825        // only then will the 2nd element of the tuple serve as a tie-breaker.
826        let r1_min = match &r1.0 {
827            Included(x) => Some((x, 1)),
828            Excluded(x) => Some((x, 2)),
829            Unbounded => None,
830        };
831        let r2_min = match &r2.0 {
832            Included(x) => Some((x, 1)),
833            Excluded(x) => Some((x, 2)),
834            Unbounded => None,
835        };
836
837        match (r1_min, r2_min) {
838            (None, None) => {} // Left-bounds are equal, we can't return yet.
839            (None, Some(_)) => return Less,
840            (Some(_), None) => return Greater,
841            (Some(r1), Some(ref r2)) => {
842                match r1.cmp(r2) {
843                    Less => return Less,
844                    Greater => return Greater,
845                    Equal => {} // Left-bounds are equal, we can't return yet.
846                };
847            }
848        };
849
850        // Both left-bounds are equal, we have to
851        // compare the right-bounds as a tie-breaker.
852        Self::cmp_endbound(&r1.1, &r2.1)
853    }
854
855    fn cmp_endbound(e1: &Bound<K>, e2: &Bound<K>) -> Ordering
856    where
857        K: Ord,
858    {
859        // Based on the encoding idea used in `cmp`.
860        // Note that we have inversed the 2nd value in the tuple,
861        // as the Included/Excluded rules are flipped for the upper bound.
862        let e1 = match e1 {
863            Included(x) => Some((x, 2)),
864            Excluded(x) => Some((x, 1)),
865            Unbounded => None,
866        };
867        let e2 = match e2 {
868            Included(x) => Some((x, 2)),
869            Excluded(x) => Some((x, 1)),
870            Unbounded => None,
871        };
872
873        match (e1, e2) {
874            (None, None) => Equal,
875            (None, Some(_)) => Greater,
876            (Some(_), None) => Less,
877            (Some(r1), Some(ref r2)) => r1.cmp(r2),
878        }
879    }
880}
881
882/// An inorder interator through the interval tree.
883pub struct IntervalTreeIter<'a, K> {
884    to_visit: Vec<&'a Box<Node<K>>>,
885    curr: &'a Option<Box<Node<K>>>,
886}
887
888impl<'a, K> Iterator for IntervalTreeIter<'a, K> {
889    type Item = &'a Range<K>;
890
891    fn next(&mut self) -> Option<Self::Item> {
892        if self.curr.is_none() && self.to_visit.is_empty() {
893            return None;
894        }
895
896        while self.curr.is_some() {
897            self.to_visit.push(self.curr.as_ref().unwrap());
898            self.curr = &self.curr.as_ref().unwrap().left;
899        }
900
901        let visited = self.to_visit.pop();
902        self.curr = &visited.as_ref().unwrap().right;
903        Some(&visited.unwrap().key)
904    }
905}
906
907#[cfg(test)]
908mod tests {
909    use super::*;
910    use serde_json::{Value, from_str, json, to_string};
911    
912    #[test]
913    fn serialize_deserialize_identity() {
914	let mut tree = IntervalTree::default();
915	let serialized_empty_tree = to_string(&tree).unwrap();
916	let deserialized_empty_tree = from_str(&serialized_empty_tree).unwrap();
917	assert_eq!(tree, deserialized_empty_tree);
918
919	tree.insert((Included(1), Excluded(3)));
920	let serialized_tree = to_string(&tree).unwrap();
921	let deserialized_tree = from_str(&serialized_tree).unwrap();
922	assert_eq!(tree, deserialized_tree);
923    }
924
925    #[test]
926    fn serialize() {
927	let mut tree = IntervalTree::default();
928	let serialized_empty_tree = to_string(&tree).unwrap();
929	let deserialized_empty_value: Value = from_str(&serialized_empty_tree).unwrap();
930	let expected_empty_value = json!({
931	    "root": null,
932	    "size": 0,
933	});
934	assert_eq!(expected_empty_value, deserialized_empty_value);
935
936	tree.insert((Included(2), Included(4)));
937	tree.insert((Included(1), Excluded(3)));
938	
939	let serialized_tree = to_string(&tree).unwrap();
940	let deserialized_tree: Value = from_str(&serialized_tree).unwrap();
941	let expected_value = json!({
942	    "root": {
943		"key": [
944		    {"Included": 2},
945		    {"Included": 4},
946		],
947		"left": {
948		    "key": [
949			{"Included": 1},
950			{"Excluded": 3},
951		    ],
952		    "left": null,
953		    "right": null,
954		    "value": {"Excluded": 3},
955		},
956		"right": null,
957		"value": {"Included": 4},
958	    },
959	    "size": 2,
960	});
961	assert_eq!(expected_value, deserialized_tree);
962    }
963
964    #[test]
965    fn deserialize() {
966	let mut expected_tree = IntervalTree::default();
967	let empty_value = json!({
968	    "root": null,
969	    "size": 0,
970	});
971	let serialized_empty_value = empty_value.to_string();
972	let deserialized_empty_tree = from_str(&serialized_empty_value).unwrap();
973	assert_eq!(expected_tree, deserialized_empty_tree);
974
975	expected_tree.insert((Included(2), Included(4)));
976	expected_tree.insert((Included(1), Excluded(3)));
977	let value = json!({
978	    "root": {
979		"key": [
980		    {"Included": 2},
981		    {"Included": 4},
982		],
983		"left": {
984		    "key": [
985			{"Included": 1},
986			{"Excluded": 3},
987		    ],
988		    "left": null,
989		    "right": null,
990		    "value": {"Excluded": 3},
991		},
992		"right": null,
993		"value": {"Included": 4},
994	    },
995	    "size": 2,
996	});
997	let serialized_value = value.to_string();
998	let deserialized_tree = from_str(&serialized_value).unwrap();
999	assert_eq!(expected_tree, deserialized_tree);
1000    }
1001    
1002    #[test]
1003    fn it_inserts_root() {
1004        let mut tree = IntervalTree::default();
1005        assert!(tree.root.is_none());
1006
1007        let key = (Included(1), Included(3));
1008
1009        tree.insert(key.clone());
1010        assert!(tree.root.is_some());
1011        assert_eq!(tree.root.as_ref().unwrap().key, key);
1012        assert_eq!(tree.root.as_ref().unwrap().value, key.1);
1013        assert!(tree.root.as_ref().unwrap().left.is_none());
1014        assert!(tree.root.as_ref().unwrap().right.is_none());
1015    }
1016
1017    #[test]
1018    fn creates_from_iterator() {
1019        let ranges = vec![0..5, 6..10, 10..15];
1020        let interval_tree: IntervalTree<_> = ranges.into_iter().collect();
1021
1022        assert_eq!(interval_tree.len(), 3);
1023    }
1024
1025    #[test]
1026    fn creates_from_array() {
1027        let ranges = [0..5, 6..10, 10..15];
1028        let interval_tree = IntervalTree::from(ranges.clone());
1029        let other_interval_tree = ranges.into();
1030
1031        assert_eq!(interval_tree, other_interval_tree);
1032        assert_eq!(interval_tree.len(), 3);
1033    }
1034
1035    #[test]
1036    fn it_inserts_left_right_node() {
1037        let mut tree = IntervalTree::default();
1038
1039        let root_key = (Included(2), Included(3));
1040        let left_key = (Included(0), Included(1));
1041        let left_right_key = (Excluded(1), Unbounded);
1042
1043        tree.insert(root_key.clone());
1044        assert!(tree.root.is_some());
1045        assert!(tree.root.as_ref().unwrap().left.is_none());
1046
1047        tree.insert(left_key.clone());
1048        assert!(tree.root.as_ref().unwrap().right.is_none());
1049        assert!(tree.root.as_ref().unwrap().left.is_some());
1050        assert_eq!(
1051            tree.root.as_ref().unwrap().left.as_ref().unwrap().value,
1052            left_key.1
1053        );
1054
1055        tree.insert(left_right_key.clone());
1056        assert!(tree
1057            .root
1058            .as_ref()
1059            .unwrap()
1060            .left
1061            .as_ref()
1062            .unwrap()
1063            .right
1064            .is_some());
1065    }
1066
1067    #[test]
1068    fn it_updates_value() {
1069        let mut tree = IntervalTree::default();
1070
1071        let root_key = (Included(2), Included(3));
1072        let left_key = (Included(0), Included(1));
1073        let left_left_key = (Included(-5), Excluded(10));
1074        let right_key = (Excluded(3), Unbounded);
1075
1076        tree.insert(root_key.clone());
1077        assert_eq!(tree.root.as_ref().unwrap().value, root_key.1);
1078
1079        tree.insert(left_key.clone());
1080        assert_eq!(tree.root.as_ref().unwrap().value, root_key.1);
1081        assert!(tree.root.as_ref().unwrap().left.is_some());
1082        assert_eq!(
1083            tree.root.as_ref().unwrap().left.as_ref().unwrap().value,
1084            left_key.1
1085        );
1086
1087        tree.insert(left_left_key.clone());
1088        assert_eq!(tree.root.as_ref().unwrap().value, left_left_key.1);
1089        assert_eq!(
1090            tree.root.as_ref().unwrap().left.as_ref().unwrap().value,
1091            left_left_key.1
1092        );
1093        assert!(tree
1094            .root
1095            .as_ref()
1096            .unwrap()
1097            .left
1098            .as_ref()
1099            .unwrap()
1100            .left
1101            .is_some());
1102        assert_eq!(
1103            tree.root
1104                .as_ref()
1105                .unwrap()
1106                .left
1107                .as_ref()
1108                .unwrap()
1109                .left
1110                .as_ref()
1111                .unwrap()
1112                .value,
1113            left_left_key.1
1114        );
1115
1116        tree.insert(right_key.clone());
1117        assert_eq!(tree.root.as_ref().unwrap().value, right_key.1);
1118        assert!(tree.root.as_ref().unwrap().right.is_some());
1119        assert_eq!(
1120            tree.root.as_ref().unwrap().left.as_ref().unwrap().value,
1121            left_left_key.1
1122        );
1123        assert_eq!(
1124            tree.root.as_ref().unwrap().right.as_ref().unwrap().value,
1125            right_key.1
1126        );
1127    }
1128
1129    #[test]
1130    fn cmp_works_as_expected() {
1131        let key0 = (Unbounded, Excluded(20));
1132        let key1 = (Included(1), Included(5));
1133        let key2 = (Included(1), Excluded(7));
1134        let key3 = (Included(1), Included(7));
1135        let key4 = (Excluded(5), Excluded(9));
1136        let key5 = (Included(7), Included(8));
1137        let key_str1 = (Included("abc"), Excluded("def"));
1138        let key_str2 = (Included("bbc"), Included("bde"));
1139        let key_str3: (_, Bound<&str>) = (Included("bbc"), Unbounded);
1140
1141        assert_eq!(IntervalTree::cmp(&key1, &key1), Equal);
1142        assert_eq!(IntervalTree::cmp(&key1, &key2), Less);
1143        assert_eq!(IntervalTree::cmp(&key2, &key3), Less);
1144        assert_eq!(IntervalTree::cmp(&key0, &key1), Less);
1145        assert_eq!(IntervalTree::cmp(&key4, &key5), Less);
1146        assert_eq!(IntervalTree::cmp(&key_str1, &key_str2), Less);
1147        assert_eq!(IntervalTree::cmp(&key_str2, &key_str3), Less);
1148    }
1149
1150    #[test]
1151    fn overlap_works_as_expected() {
1152        let mut tree = IntervalTree::default();
1153
1154        let root_key = (Included(2), Included(3));
1155        let left_key = (Included(0), Included(1));
1156        let left_left_key = (Included(-5), Excluded(10));
1157        let right_key = (Excluded(3), Unbounded);
1158
1159        tree.insert(root_key.clone());
1160        tree.insert(left_key.clone());
1161        assert_eq!(tree.get_interval_overlaps(&root_key), vec![&root_key]);
1162
1163        tree.insert(left_left_key.clone());
1164        assert_eq!(
1165            tree.get_interval_overlaps(&(..)),
1166            vec![&left_left_key, &left_key, &root_key]
1167        );
1168        assert!(tree.get_interval_overlaps(&(100..)).is_empty());
1169
1170        tree.insert(right_key);
1171        assert_eq!(
1172            tree.get_interval_overlaps(&root_key),
1173            vec![&left_left_key, &root_key]
1174        );
1175        assert_eq!(
1176            tree.get_interval_overlaps(&(..)),
1177            vec![&left_left_key, &left_key, &root_key, &right_key]
1178        );
1179        assert_eq!(tree.get_interval_overlaps(&(100..)), vec![&right_key]);
1180        assert_eq!(
1181            tree.get_interval_overlaps(&(3..10)),
1182            vec![&left_left_key, &root_key, &right_key]
1183        );
1184        assert_eq!(
1185            tree.get_interval_overlaps(&(Excluded(3), Excluded(10))),
1186            vec![&left_left_key, &right_key]
1187        );
1188        assert_eq!(
1189            tree.get_interval_overlaps(&(..2)),
1190            vec![&left_left_key, &left_key]
1191        );
1192        assert_eq!(
1193            tree.get_interval_overlaps(&(..=2)),
1194            vec![&left_left_key, &left_key, &root_key]
1195        );
1196        assert_eq!(
1197            tree.get_interval_overlaps(&(..=3)),
1198            vec![&left_left_key, &left_key, &root_key]
1199        );
1200    }
1201
1202    #[test]
1203    fn difference_and_overlaps_with_tuple_works_as_expected() {
1204        let mut tree = IntervalTree::default();
1205
1206        let root_key = (Included((1, 2)), Excluded((1, 4)));
1207        let right_key = (5, 10)..=(5, 20);
1208
1209        tree.insert(root_key.clone());
1210        tree.insert(right_key);
1211
1212        assert!(tree.get_interval_overlaps(&((2, 0)..=(2, 30))).is_empty());
1213        assert_eq!(
1214            tree.get_interval_overlaps(&((1, 3)..=(1, 5))),
1215            vec![&root_key]
1216        );
1217        assert_eq!(
1218            tree.get_interval_difference(&(Excluded((1, 1)), Included((1, 5)))),
1219            vec![
1220                (Excluded(&(1, 1)), Excluded(&(1, 2))),
1221                (Included(&(1, 4)), Included(&(1, 5)))
1222            ]
1223        );
1224    }
1225
1226    #[test]
1227    fn difference_works_as_expected() {
1228        let mut tree = IntervalTree::default();
1229
1230        let key1 = 2..10;
1231        let key2 = 4..=6;
1232        let key3 = (Excluded(10), Excluded(20));
1233        let key4 = (Excluded(30), Included(35));
1234        let key5 = 30..=40;
1235        let key6 = 30..=35;
1236        let key7 = (Excluded(45), Unbounded);
1237        let key8 = (Included(60), Included(70));
1238
1239        tree.insert(key1);
1240        tree.insert(key2);
1241        tree.insert(key3);
1242        tree.insert(key4);
1243        tree.insert(key5);
1244        tree.insert(key6);
1245        tree.insert(key7);
1246        tree.insert(key8);
1247
1248        assert_eq!(
1249            tree.get_interval_difference(&(Excluded(0), Included(100))),
1250            vec![
1251                (Excluded(&0), Excluded(&2)),
1252                (Included(&10), Included(&10)),
1253                (Included(&20), Excluded(&30)),
1254                (Excluded(&40), Included(&45))
1255            ]
1256        );
1257        assert_eq!(
1258            tree.get_interval_difference(&(19..=40)),
1259            vec![(Included(&20), Excluded(&30))]
1260        );
1261        assert_eq!(
1262            tree.get_interval_difference(&(20..=40)),
1263            vec![(Included(&20), Excluded(&30))]
1264        );
1265        assert_eq!(
1266            tree.get_interval_difference(&(20..=45)),
1267            vec![
1268                (Included(&20), Excluded(&30)),
1269                (Excluded(&40), Included(&45))
1270            ]
1271        );
1272        assert_eq!(
1273            tree.get_interval_difference(&(20..45)),
1274            vec![
1275                (Included(&20), Excluded(&30)),
1276                (Excluded(&40), Excluded(&45))
1277            ]
1278        );
1279        assert_eq!(
1280            tree.get_interval_difference(&(2..=10)),
1281            vec![(Included(&10), Included(&10))]
1282        );
1283    }
1284
1285    #[test]
1286    fn consecutive_excluded_non_contiguous_difference_works_as_expected() {
1287        let mut tree = IntervalTree::default();
1288
1289        let key1 = (Included(10), Excluded(20));
1290        let key2 = (Excluded(30), Excluded(40));
1291
1292        tree.insert(key1);
1293        tree.insert(key2);
1294
1295        assert_eq!(
1296            tree.get_interval_difference(&(0..=40)),
1297            vec![
1298                (Included(&0), Excluded(&10)),
1299                (Included(&20), Included(&30)),
1300                (Included(&40), Included(&40))
1301            ]
1302        );
1303    }
1304
1305    #[test]
1306    fn get_interval_difference_str_works_as_expected() {
1307        let mut tree: IntervalTree<&str> = IntervalTree::default();
1308
1309        let key1 = (Included("a"), Excluded("h"));
1310        let key2 = (Excluded("M"), Excluded("O"));
1311
1312        tree.insert(key1.clone());
1313        tree.insert(key2);
1314
1315        assert!(tree.get_interval_difference(&("a".."h")).is_empty());
1316        assert_eq!(
1317            tree.get_interval_difference(&("M"..="P")),
1318            vec![
1319                (Included(&"M"), Included(&"M")),
1320                (Included(&"O"), Included(&"P"))
1321            ]
1322        );
1323
1324        let not_covered_range = "h".."k";
1325        assert_eq!(
1326            tree.get_interval_difference(&not_covered_range),
1327            vec![(
1328                not_covered_range.start_bound(),
1329                not_covered_range.end_bound()
1330            )]
1331        );
1332    }
1333
1334    #[test]
1335    fn contains_point_works_as_expected() {
1336        let mut tree = IntervalTree::default();
1337
1338        let key1 = (Included(10), Excluded(20));
1339        let key2 = (Excluded(30), Excluded(40));
1340        let key3 = 40..;
1341
1342        tree.insert(key1);
1343        tree.insert(key2);
1344        tree.insert(key3);
1345
1346        assert!(tree.contains_point(&10));
1347        assert!(!tree.contains_point(&20));
1348        assert!(tree.contains_point(&40));
1349        assert!(tree.contains_point(&100));
1350    }
1351
1352    #[test]
1353    fn contains_string_point_works_as_expected() {
1354        let mut tree = IntervalTree::default();
1355
1356        let key1 = String::from("a")..String::from("h");
1357        let key2 = (Excluded(String::from("M")), Excluded(String::from("O")));
1358
1359        tree.insert(key1);
1360        tree.insert(key2);
1361
1362        assert!(tree.contains_point("b"));
1363        assert!(!tree.contains_point("n"));
1364        assert!(tree.contains_point(&String::from("N")));
1365        assert!(tree.contains_point("g"));
1366    }
1367
1368    #[test]
1369    fn contains_str_point_works_as_expected() {
1370        let mut tree: IntervalTree<&str> = IntervalTree::default();
1371
1372        let key1 = "a".."h";
1373        let key2 = (Excluded("M"), Excluded("O"));
1374
1375        tree.insert(key1);
1376        tree.insert(key2);
1377
1378        assert!(tree.contains_point("b"));
1379        assert!(!tree.contains_point("n"));
1380        assert!(tree.contains_point(&"N"));
1381        assert!(tree.contains_point("g"));
1382    }
1383
1384    #[test]
1385    fn contains_works_as_expected() {
1386        let mut tree = IntervalTree::default();
1387
1388        let key1 = (Included(10), Excluded(20));
1389        let key2 = (Excluded(30), Excluded(40));
1390        let key3 = 40..;
1391
1392        tree.insert(key1.clone());
1393        tree.insert(key2.clone());
1394        tree.insert(key3.clone());
1395
1396        assert!(tree.contains_interval(&key1));
1397        assert!(!tree.contains_interval(&(Included(&10), Included(&20))));
1398        assert!(!tree.contains_interval(&(..=0)));
1399        assert!(tree.contains_interval(&(Included(35), Included(37))));
1400    }
1401
1402    #[test]
1403    fn contains_str_works_as_expected() {
1404        let mut tree: IntervalTree<&str> = IntervalTree::default();
1405
1406        let key1 = "a".."h";
1407        let key2 = (Excluded("M"), Excluded("O"));
1408
1409        tree.insert(key1.clone());
1410        tree.insert(key2);
1411
1412        assert!(tree.contains_interval(&("a".."h")));
1413        assert!(tree.contains_interval(&("N"..="N")));
1414        assert!(tree.contains_interval::<&str, _>(&key1));
1415        assert!(!tree.contains_interval(&("N"..="O")));
1416    }
1417
1418    #[test]
1419    fn iter_works_as_expected() {
1420        let mut tree = IntervalTree::default();
1421
1422        assert_eq!(tree.iter().next(), None);
1423
1424        let key1 = (Included(10), Excluded(20));
1425        let key2 = (Included(40), Unbounded);
1426        let key3 = (Excluded(30), Excluded(40));
1427        let key4 = (Unbounded, Included(50));
1428        let key5 = (Excluded(-10), Included(-5));
1429        let key6 = (Included(-10), Included(-4));
1430
1431        tree.insert(key1.clone());
1432        tree.insert(key2.clone());
1433        tree.insert(key3.clone());
1434        tree.insert(key4.clone());
1435        tree.insert(key5.clone());
1436        tree.insert(key6.clone());
1437
1438        let inorder = vec![&key4, &key6, &key5, &key1, &key3, &key2];
1439        for (idx, interval) in tree.iter().enumerate() {
1440            assert_eq!(interval, inorder[idx]);
1441        }
1442
1443        assert_eq!(tree.iter().count(), inorder.len());
1444    }
1445
1446    #[test]
1447    fn remove_random_leaf_empty_tree_works_as_expected() {
1448        let mut tree: IntervalTree<i32> = IntervalTree::default();
1449
1450        assert_eq!(tree.remove_random_leaf(), None);
1451    }
1452
1453    #[test]
1454    fn remove_random_leaf_one_node_tree_works_as_expected() {
1455        let mut tree = IntervalTree::default();
1456
1457        let key1 = (Included(10), Excluded(20));
1458        tree.insert(key1.clone());
1459
1460        let deleted = tree.remove_random_leaf();
1461        assert!(deleted.is_some());
1462        assert_eq!(deleted.unwrap(), key1);
1463
1464        assert!(tree.remove_random_leaf().is_none());
1465    }
1466
1467    #[test]
1468    fn remove_random_leaf_works_as_expected() {
1469        let mut tree = IntervalTree::default();
1470
1471        let key1 = (Included(16), Unbounded);
1472        let key2 = (Included(8), Excluded(9));
1473        let key3 = (Included(5), Excluded(8));
1474        let key4 = (Excluded(15), Included(23));
1475        let key5 = (Included(0), Included(3));
1476        let key6 = (Included(13), Excluded(26));
1477
1478        tree.insert(key1.clone());
1479        tree.insert(key2.clone());
1480        tree.insert(key3.clone());
1481        tree.insert(key4.clone());
1482        tree.insert(key5.clone());
1483        tree.insert(key6.clone());
1484
1485        let mut tree_deleted_key5 = IntervalTree::default();
1486
1487        let key1_deleted5 = (Included(16), Unbounded);
1488        let key2_deleted5 = (Included(8), Excluded(9));
1489        let key3_deleted5 = (Included(5), Excluded(8));
1490        let key4_deleted5 = (Excluded(15), Included(23));
1491        let key6_deleted5 = (Included(13), Excluded(26));
1492
1493        tree_deleted_key5.insert(key1_deleted5.clone());
1494        tree_deleted_key5.insert(key2_deleted5.clone());
1495        tree_deleted_key5.insert(key3_deleted5.clone());
1496        tree_deleted_key5.insert(key4_deleted5.clone());
1497        tree_deleted_key5.insert(key6_deleted5.clone());
1498
1499        let mut tree_deleted_key6 = IntervalTree::default();
1500
1501        let key1_deleted6 = (Included(16), Unbounded);
1502        let key2_deleted6 = (Included(8), Excluded(9));
1503        let key3_deleted6 = (Included(5), Excluded(8));
1504        let key4_deleted6 = (Excluded(15), Included(23));
1505        let key5_deleted6 = (Included(0), Included(3));
1506
1507        tree_deleted_key6.insert(key1_deleted6.clone());
1508        tree_deleted_key6.insert(key2_deleted6.clone());
1509        tree_deleted_key6.insert(key3_deleted6.clone());
1510        tree_deleted_key6.insert(key4_deleted6.clone());
1511        tree_deleted_key6.insert(key5_deleted6.clone());
1512
1513        use std::collections::HashSet;
1514        let mut all_deleted = HashSet::new();
1515        let num_of_leaves = 2; // Key5 & Key6
1516
1517        // This loop makes sure that the deletion is random.
1518        // We delete and reinsert leaves until we have deleted
1519        // all possible leaves in the tree.
1520        while all_deleted.len() < num_of_leaves {
1521            let deleted = tree.remove_random_leaf();
1522            assert!(deleted.is_some());
1523            let deleted = deleted.unwrap();
1524
1525            // Check that the new tree has the right shape,
1526            // and that the value stored in the various nodes are
1527            // correctly updated following the removal of a leaf.
1528            if deleted == key5 {
1529                assert_eq!(tree, tree_deleted_key5);
1530            } else if deleted == key6 {
1531                assert_eq!(tree, tree_deleted_key6);
1532            } else {
1533                unreachable!();
1534            }
1535
1536            // Keep track of deleted nodes, and reinsert the
1537            // deleted node in the tree so we come back to
1538            // the initial state every iteration.
1539            all_deleted.insert(deleted.clone());
1540            tree.insert(deleted);
1541        }
1542    }
1543
1544    #[test]
1545    fn len_and_is_empty_works_as_expected() {
1546        let mut tree = IntervalTree::default();
1547
1548        assert_eq!(tree.len(), 0);
1549        assert!(tree.is_empty());
1550
1551        let key1 = (Included(16), Unbounded);
1552        let key2 = (Included(8), Excluded(9));
1553
1554        tree.insert(key1);
1555
1556        assert_eq!(tree.len(), 1);
1557        assert!(!tree.is_empty());
1558
1559        tree.insert(key2);
1560
1561        assert_eq!(tree.len(), 2);
1562        assert!(!tree.is_empty());
1563
1564        tree.remove_random_leaf();
1565
1566        assert_eq!(tree.len(), 1);
1567        assert!(!tree.is_empty());
1568
1569        tree.remove_random_leaf();
1570
1571        assert_eq!(tree.len(), 0);
1572        assert!(tree.is_empty());
1573    }
1574
1575    #[test]
1576    fn clear_works_as_expected() {
1577        let mut tree = IntervalTree::default();
1578
1579        tree.clear();
1580
1581        let key1 = (Included(16), Unbounded);
1582        let key2 = (Included(8), Excluded(9));
1583
1584        tree.insert(key1.clone());
1585        tree.insert(key2.clone());
1586
1587        assert_eq!(tree.len(), 2);
1588
1589        tree.clear();
1590
1591        assert!(tree.is_empty());
1592        assert_eq!(tree.root, None);
1593    }
1594}
unbounded_interval_tree/interval_tree.rs

unbounded_interval_tree/
interval_tree.rs
