rb_interval_map/
intervalmap.rs

1use crate::entry::{Entry, OccupiedEntry, VacantEntry};
2use crate::index::{DefaultIx, IndexType, NodeIndex};
3use crate::interval::{Interval, IntervalRef};
4use crate::iter::{FilterIter, IntoIter, Iter, UnsortedIter};
5use crate::node::{Color, Node};
6
7use std::collections::VecDeque;
8use std::fmt::Debug;
9
10#[cfg(feature = "serde")]
11use serde::{Deserialize, Serialize};
12
13#[cfg(feature = "graphviz")]
14use std::fmt::Display;
15#[cfg(feature = "graphviz")]
16use std::fs::OpenOptions;
17#[cfg(feature = "graphviz")]
18use std::io::Write;
19
20/// An interval-value map, which support operations on dynamic sets of intervals.
21#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
22#[derive(Debug)]
23pub struct IntervalMap<T, V, Ix = DefaultIx> {
24    /// Vector that stores nodes
25    pub(crate) nodes: Vec<Node<T, V, Ix>>,
26    /// Root of the interval tree
27    pub(crate) root: NodeIndex<Ix>,
28    /// Number of elements in the map
29    pub(crate) len: usize,
30}
31
32impl<T, V, Ix> IntervalMap<T, V, Ix>
33where
34    T: Ord,
35    Ix: IndexType,
36{
37    /// Creates a new `IntervalMap` with estimated capacity.
38    #[inline]
39    #[must_use]
40    pub fn with_capacity(capacity: usize) -> Self {
41        let mut nodes = vec![Node::new_sentinel()];
42        nodes.reserve(capacity);
43        IntervalMap {
44            nodes,
45            root: NodeIndex::SENTINEL,
46            len: 0,
47        }
48    }
49
50    /// Insert an interval-value pair into the map.
51    /// If the interval exists, overwrite and return the previous value.
52    ///
53    /// # Panics
54    ///
55    /// This method panics when the tree is at the maximum number of nodes for its index
56    ///
57    /// # Example
58    /// ```rust
59    /// use rb_interval_map::{Interval, IntervalMap};
60    ///
61    /// let mut map = IntervalMap::new();
62    /// assert_eq!(map.insert(Interval::new(1, 3), 1), None);
63    /// assert_eq!(map.insert(Interval::new(1, 3), 2), Some(1));
64    /// assert_eq!(map.insert(Interval::new(1, 3), 3), Some(2));
65    /// ```
66    #[inline]
67    pub fn insert(&mut self, interval: Interval<T>, value: V) -> Option<V> {
68        let node_idx = NodeIndex::new(self.nodes.len());
69        let node = Node::new(interval, value, node_idx);
70        // check for max capacity, except if we use usize
71        assert!(
72            <Ix as IndexType>::max().index() == !0
73                || <NodeIndex<_> as IndexType>::max() != node_idx,
74            "Reached maximum number of nodes"
75        );
76        self.nodes.push(node);
77        self.insert_inner(node_idx)
78    }
79
80    /// Remove an interval from the map, returning the value at the interval if the interval exists
81    ///
82    /// # Example
83    /// ```rust
84    /// use rb_interval_map::{Interval, IntervalMap};
85    ///
86    /// let mut map = IntervalMap::new();
87    /// map.insert(Interval::new(1, 3), 1);
88    /// map.insert(Interval::new(2, 4), 2);
89    /// assert_eq!(map.len(), 2);
90    /// assert_eq!(map.remove(&Interval::new(3, 6)), None);
91    /// assert_eq!(map.len(), 2);
92    /// assert_eq!(map.remove(&Interval::new(2, 4)), Some(2));
93    /// assert_eq!(map.len(), 1);
94    /// ```
95    #[inline]
96    pub fn remove(&mut self, interval: &Interval<T>) -> Option<V> {
97        if let Some(node_idx) = self.search_exact(interval) {
98            self.remove_inner(node_idx);
99            // Swap the node with the last node stored in the vector and update indices
100            let mut node = self.nodes.swap_remove(node_idx.index());
101            let old = NodeIndex::<Ix>::new(self.nodes.len());
102            self.update_idx(old, node_idx);
103
104            return node.value.take();
105        }
106        None
107    }
108
109    /// Check if an interval in the map overlaps with the given interval.
110    ///
111    /// # Example
112    /// ```rust
113    /// use rb_interval_map::{Interval, IntervalMap};
114    ///
115    /// let mut map = IntervalMap::new();
116    /// map.insert(Interval::new(1, 3), ());
117    /// map.insert(Interval::new(6, 7), ());
118    /// map.insert(Interval::new(9, 11), ());
119    /// assert!(map.overlaps(&Interval::new(2, 5)));
120    /// assert!(map.overlaps(&Interval::new(1, 17)));
121    /// assert!(!map.overlaps(&Interval::new(3, 6)));
122    /// assert!(!map.overlaps(&Interval::new(11, 23)));
123    /// ```
124    #[inline]
125    pub fn overlaps(&self, interval: &Interval<T>) -> bool {
126        let node_idx = self.search(interval);
127        !self.node_ref(node_idx, Node::is_sentinel)
128    }
129
130    /// When `interval_map.len() < Self::BFS_MIN_THRESHOLD`, directly traversing the inner vec of `interval_map`
131    /// is faster than BFS.
132    const BFS_MIN_THRESHOLD: usize = 20;
133
134    /// Find all intervals in the map that overlaps with the given interval.
135    ///
136    /// # Note
137    /// This method's returned data is unordered. To get ordered data, please use `find_all_overlap_ordered`.
138    ///
139    /// # Example
140    /// ```rust
141    /// use rb_interval_map::{Interval, IntervalMap};
142    ///
143    /// let mut map = IntervalMap::new();
144    /// map.insert(Interval::new(1, 3), ());
145    /// map.insert(Interval::new(2, 4), ());
146    /// map.insert(Interval::new(6, 7), ());
147    /// map.insert(Interval::new(7, 11), ());
148    /// assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 3);
149    /// map.remove(&Interval::new(1, 3));
150    /// assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 2);
151    /// ```
152    #[inline]
153    pub fn find_all_overlap(&self, interval: &Interval<T>) -> Vec<(&Interval<T>, &V)> {
154        if self.node_ref(self.root, Node::is_sentinel) {
155            return Vec::new();
156        }
157        if self.len() > Self::BFS_MIN_THRESHOLD {
158            self.find_all_overlap_inner(self.root, interval)
159        } else {
160            self.unsorted_iter()
161                .filter(|v| v.0.overlaps(interval))
162                .collect()
163        }
164    }
165
166    /// Find all intervals in the map that overlaps with the given interval.
167    ///
168    /// # Note
169    /// This method's returned data is ordered. Generally, it's much slower than `find_all_overlap`.
170    ///
171    /// # Example
172    /// ```rust
173    /// use rb_interval_map::{Interval, IntervalMap};
174    ///
175    /// let mut map = IntervalMap::new();
176    /// map.insert(Interval::new(1, 3), ());
177    /// map.insert(Interval::new(2, 4), ());
178    /// map.insert(Interval::new(6, 7), ());
179    /// map.insert(Interval::new(7, 11), ());
180    /// assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 3);
181    /// map.remove(&Interval::new(1, 3));
182    /// assert_eq!(map.find_all_overlap(&Interval::new(2, 7)).len(), 2);
183    /// ```
184    #[inline]
185    pub fn find_all_overlap_ordered<'a>(
186        &'a self,
187        interval: &'a Interval<T>,
188    ) -> Vec<(&Interval<T>, &V)> {
189        if self.node_ref(self.root, Node::is_sentinel) {
190            Vec::new()
191        } else {
192            self.filter_iter(interval).collect()
193        }
194    }
195
196    /// Return reference to the value corresponding to the key.
197    ///
198    /// # Example
199    /// ```rust
200    /// use rb_interval_map::{Interval, IntervalMap};
201    ///
202    /// let mut map = IntervalMap::new();
203    /// map.insert(Interval::new(1, 3), 1);
204    /// map.insert(Interval::new(7, 11), 4);
205    /// assert_eq!(map.get(&Interval::new(1, 3)), Some(&1));
206    /// assert_eq!(map.get(&Interval::new(7, 11)), Some(&4));
207    /// assert_eq!(map.get(&Interval::new(5, 17)), None);
208    /// ```
209    #[inline]
210    pub fn get(&self, interval: &Interval<T>) -> Option<&V> {
211        self.search_exact(interval)
212            .map(|idx| self.node_ref(idx, Node::value))
213    }
214
215    /// Return a reference to the value corresponding to the key.
216    ///
217    /// # Example
218    /// ```rust
219    /// use rb_interval_map::{Interval, IntervalMap};
220    ///
221    /// let mut map = IntervalMap::new();
222    /// map.insert(Interval::new(3, 5), 0);
223    /// map.get_mut(&Interval::new(3, 5)).map(|v| *v += 1);
224    /// assert_eq!(map.get(&Interval::new(3, 5)), Some(&1));
225    /// ```
226    #[inline]
227    pub fn get_mut(&mut self, interval: &Interval<T>) -> Option<&mut V> {
228        self.search_exact(interval)
229            .map(|idx| self.node_mut(idx, Node::value_mut))
230    }
231
232    /// Get an iterator over the entries of the map, sorted by key.
233    #[inline]
234    #[must_use]
235    pub fn iter(&self) -> Iter<'_, T, V, Ix> {
236        Iter::new(self)
237    }
238
239    /// Get an iterator over the entries of the map, unsorted.
240    #[inline]
241    pub fn unsorted_iter(&self) -> UnsortedIter<T, V, Ix> {
242        UnsortedIter::new(self)
243    }
244
245    /// Get an iterator over the entries that overlap the `query`, sorted by key.
246    ///
247    /// # Panics
248    ///
249    /// The method panics when `query` contains a value that cannot be compared.
250    #[inline]
251    pub fn filter_iter<'a, 'b: 'a>(&'a self, query: &'b Interval<T>) -> FilterIter<T, V, Ix> {
252        FilterIter::new(self, query)
253    }
254
255    /// Return true if the interval tree's key cover the entire given interval.
256    ///
257    /// # Example
258    /// ```rust
259    /// use rb_interval_map::{Interval, IntervalMap};
260    ///
261    /// let mut map = IntervalMap::new();
262    /// map.insert(Interval::new(3, 5), 0);
263    /// map.insert(Interval::new(5, 8), 1);
264    /// map.insert(Interval::new(9, 12), 1);
265    /// assert!(map.contains(&Interval::new(4, 6)));
266    /// assert!(!map.contains(&Interval::new(7, 10)));
267    /// ```
268    #[inline]
269    pub fn contains(&self, interval: &Interval<T>) -> bool {
270        let mut max_end: Option<&T> = None;
271        let mut min_begin: Option<&T> = None;
272
273        let mut continuous = true;
274        self.filter_iter(interval).find(|v| {
275            if min_begin.is_none() {
276                min_begin = Some(&v.0.low);
277                max_end = Some(&v.0.high);
278                return false;
279            }
280            if max_end.map(|mv| mv < &v.0.low).unwrap() {
281                continuous = false;
282                return true;
283            }
284            if max_end.map(|mv| mv < &v.0.high).unwrap() {
285                max_end = Some(&v.0.high);
286            }
287            false
288        });
289
290        continuous
291            && min_begin.is_some()
292            && max_end.map(|mv| mv >= &interval.high).unwrap()
293            && min_begin.map(|mv| mv <= &interval.low).unwrap()
294    }
295
296    /// Get the given key's corresponding entry in the map for in-place manipulation.
297    ///
298    /// # Example
299    /// ```rust
300    /// use rb_interval_map::{Interval, IntervalMap, Entry};
301    ///
302    /// let mut map = IntervalMap::new();
303    ///
304    /// assert!(matches!(map.entry(Interval::new(1, 2)), Entry::Vacant(_)));
305    /// map.entry(Interval::new(1, 2)).or_insert(0);
306    /// assert!(matches!(map.entry(Interval::new(1, 2)), Entry::Occupied(_)));
307    /// map.entry(Interval::new(1, 2)).and_modify(|v| *v += 1);
308    /// assert_eq!(map.get(&Interval::new(1, 2)), Some(&1));
309    /// ```
310    #[inline]
311    pub fn entry(&mut self, interval: Interval<T>) -> Entry<'_, T, V, Ix> {
312        match self.search_exact(&interval) {
313            Some(node_idx) => Entry::Occupied(OccupiedEntry {
314                map_ref: self,
315                node_idx,
316            }),
317            None => Entry::Vacant(VacantEntry {
318                map_ref: self,
319                interval,
320            }),
321        }
322    }
323
324    /// Remove all elements from the map
325    #[inline]
326    pub fn clear(&mut self) {
327        self.nodes.clear();
328        self.nodes.push(Node::new_sentinel());
329        self.root = NodeIndex::SENTINEL;
330        self.len = 0;
331    }
332
333    /// Return the number of elements in the map.
334    #[inline]
335    #[must_use]
336    pub fn len(&self) -> usize {
337        self.len
338    }
339
340    /// Return `true` if the map contains no elements.
341    #[inline]
342    #[must_use]
343    pub fn is_empty(&self) -> bool {
344        self.len() == 0
345    }
346}
347
348impl<T, V, Ix> IntoIterator for IntervalMap<T, V, Ix>
349where
350    T: Ord,
351    Ix: IndexType,
352{
353    type Item = (Interval<T>, V);
354
355    type IntoIter = IntoIter<T, V, Ix>;
356
357    /// Get an into iterator over the entries of the map, sorted by key.
358    fn into_iter(self) -> Self::IntoIter {
359        IntoIter::new(self)
360    }
361}
362
363impl<T, V> IntervalMap<T, V>
364where
365    T: Ord,
366{
367    /// Create an empty `IntervalMap`
368    #[inline]
369    #[must_use]
370    pub fn new() -> Self {
371        Self::with_capacity(0)
372    }
373}
374
375impl<T, V> Default for IntervalMap<T, V>
376where
377    T: Ord,
378{
379    #[inline]
380    fn default() -> Self {
381        Self::with_capacity(0)
382    }
383}
384
385impl<T, V, Ix> IntervalMap<T, V, Ix>
386where
387    T: Ord,
388    Ix: IndexType,
389{
390    /// insert a node into the tree.
391    fn insert_inner(&mut self, z: NodeIndex<Ix>) -> Option<V> {
392        let mut y = NodeIndex::SENTINEL;
393        let mut x = self.root;
394
395        while !self.node_ref(x, Node::is_sentinel) {
396            y = x;
397            if self.node_ref(z, Node::interval) == self.node_ref(y, Node::interval) {
398                let zval = self.node_mut(z, Node::take_value);
399                let old_value = self.node_mut(y, Node::set_value(zval));
400                return Some(old_value);
401            }
402            if self.node_ref(z, Node::interval) < self.node_ref(x, Node::interval) {
403                x = self.node_ref(x, Node::left);
404            } else {
405                x = self.node_ref(x, Node::right);
406            }
407        }
408        self.node_mut(z, Node::set_parent(y));
409        if self.node_ref(y, Node::is_sentinel) {
410            self.root = z;
411        } else {
412            if self.node_ref(z, Node::interval) < self.node_ref(y, Node::interval) {
413                self.node_mut(y, Node::set_left(z));
414            } else {
415                self.node_mut(y, Node::set_right(z));
416            }
417            self.update_max_bottom_up(y);
418        }
419        self.node_mut(z, Node::set_color(Color::Red));
420
421        self.insert_fixup(z);
422
423        self.len = self.len.wrapping_add(1);
424        None
425    }
426
427    /// Remove a node from the tree.
428    fn remove_inner(&mut self, z: NodeIndex<Ix>) {
429        let mut y = z;
430        let mut y_orig_color = self.node_ref(y, Node::color);
431        let x;
432        if self.left_ref(z, Node::is_sentinel) {
433            x = self.node_ref(z, Node::right);
434            self.transplant(z, x);
435            self.update_max_bottom_up(self.node_ref(z, Node::parent));
436        } else if self.right_ref(z, Node::is_sentinel) {
437            x = self.node_ref(z, Node::left);
438            self.transplant(z, x);
439            self.update_max_bottom_up(self.node_ref(z, Node::parent));
440        } else {
441            y = self.tree_minimum(self.node_ref(z, Node::right));
442            let mut p = y;
443            y_orig_color = self.node_ref(y, Node::color);
444            x = self.node_ref(y, Node::right);
445            if self.node_ref(y, Node::parent) == z {
446                self.node_mut(x, Node::set_parent(y));
447            } else {
448                self.transplant(y, x);
449                p = self.node_ref(y, Node::parent);
450                self.node_mut(y, Node::set_right(self.node_ref(z, Node::right)));
451                self.right_mut(y, Node::set_parent(y));
452            }
453            self.transplant(z, y);
454            self.node_mut(y, Node::set_left(self.node_ref(z, Node::left)));
455            self.left_mut(y, Node::set_parent(y));
456            self.node_mut(y, Node::set_color(self.node_ref(z, Node::color)));
457
458            self.update_max_bottom_up(p);
459        }
460
461        if matches!(y_orig_color, Color::Black) {
462            self.remove_fixup(x);
463        }
464
465        self.len = self.len.wrapping_sub(1);
466    }
467
468    /// Find all intervals in the map that overlaps with the given interval.
469    ///
470    /// The result is unordered because of breadth-first search to save stack size
471    fn find_all_overlap_inner(
472        &self,
473        x: NodeIndex<Ix>,
474        interval: &Interval<T>,
475    ) -> Vec<(&Interval<T>, &V)> {
476        let mut list = Vec::new();
477        let mut queue = VecDeque::new();
478        queue.push_back(x);
479        while let Some(p) = queue.pop_front() {
480            if self.node_ref(p, Node::interval).overlaps(interval) {
481                list.push(self.node_ref(p, |np| (np.interval(), np.value())));
482            }
483            let p_left = self.node_ref(p, Node::left);
484            let p_right = self.node_ref(p, Node::right);
485            if self.max(p_left) >= Some(&interval.low) {
486                queue.push_back(p_left);
487            }
488            if self
489                .max(self.node_ref(p, Node::right))
490                .map(|rmax| IntervalRef::new(&self.node_ref(p, Node::interval).low, rmax))
491                .is_some_and(|i| i.overlap(interval))
492            {
493                queue.push_back(p_right);
494            }
495        }
496
497        list
498    }
499
500    /// Search for an interval that overlaps with the given interval.
501    fn search(&self, interval: &Interval<T>) -> NodeIndex<Ix> {
502        let mut x = self.root;
503        while self
504            .node_ref(x, Node::sentinel)
505            .map(Node::interval)
506            .is_some_and(|xi| !xi.overlaps(interval))
507        {
508            if self.max(self.node_ref(x, Node::left)) > Some(&interval.low) {
509                x = self.node_ref(x, Node::left);
510            } else {
511                x = self.node_ref(x, Node::right);
512            }
513        }
514        x
515    }
516
517    /// Search for the node with exact the given interval
518    fn search_exact(&self, interval: &Interval<T>) -> Option<NodeIndex<Ix>> {
519        let mut x = self.root;
520        while !self.node_ref(x, Node::is_sentinel) {
521            if self.node_ref(x, Node::interval) == interval {
522                return Some(x);
523            }
524            if self.max(x) < Some(&interval.high) {
525                return None;
526            }
527            if self.node_ref(x, Node::interval) > interval {
528                x = self.node_ref(x, Node::left);
529            } else {
530                x = self.node_ref(x, Node::right);
531            }
532        }
533        None
534    }
535
536    /// Restore red-black tree properties after an insert.
537    fn insert_fixup(&mut self, mut z: NodeIndex<Ix>) {
538        while self.parent_ref(z, Node::is_red) {
539            if self.grand_parent_ref(z, Node::is_sentinel) {
540                break;
541            }
542            if self.is_left_child(self.node_ref(z, Node::parent)) {
543                let y = self.grand_parent_ref(z, Node::right);
544                if self.node_ref(y, Node::is_red) {
545                    self.parent_mut(z, Node::set_color(Color::Black));
546                    self.node_mut(y, Node::set_color(Color::Black));
547                    self.grand_parent_mut(z, Node::set_color(Color::Red));
548                    z = self.parent_ref(z, Node::parent);
549                } else {
550                    if self.is_right_child(z) {
551                        z = self.node_ref(z, Node::parent);
552                        self.left_rotate(z);
553                    }
554                    self.parent_mut(z, Node::set_color(Color::Black));
555                    self.grand_parent_mut(z, Node::set_color(Color::Red));
556                    self.right_rotate(self.parent_ref(z, Node::parent));
557                }
558            } else {
559                let y = self.grand_parent_ref(z, Node::left);
560                if self.node_ref(y, Node::is_red) {
561                    self.parent_mut(z, Node::set_color(Color::Black));
562                    self.node_mut(y, Node::set_color(Color::Black));
563                    self.grand_parent_mut(z, Node::set_color(Color::Red));
564                    z = self.parent_ref(z, Node::parent);
565                } else {
566                    if self.is_left_child(z) {
567                        z = self.node_ref(z, Node::parent);
568                        self.right_rotate(z);
569                    }
570                    self.parent_mut(z, Node::set_color(Color::Black));
571                    self.grand_parent_mut(z, Node::set_color(Color::Red));
572                    self.left_rotate(self.parent_ref(z, Node::parent));
573                }
574            }
575        }
576        self.node_mut(self.root, Node::set_color(Color::Black));
577    }
578
579    /// Restore red-black tree properties after a remove.
580    fn remove_fixup(&mut self, mut x: NodeIndex<Ix>) {
581        while x != self.root && self.node_ref(x, Node::is_black) {
582            let mut w;
583            if self.is_left_child(x) {
584                w = self.parent_ref(x, Node::right);
585                if self.node_ref(w, Node::is_red) {
586                    self.node_mut(w, Node::set_color(Color::Black));
587                    self.parent_mut(x, Node::set_color(Color::Red));
588                    self.left_rotate(self.node_ref(x, Node::parent));
589                    w = self.parent_ref(x, Node::right);
590                }
591                if self.node_ref(w, Node::is_sentinel) {
592                    break;
593                }
594                if self.left_ref(w, Node::is_black) && self.right_ref(w, Node::is_black) {
595                    self.node_mut(w, Node::set_color(Color::Red));
596                    x = self.node_ref(x, Node::parent);
597                } else {
598                    if self.right_ref(w, Node::is_black) {
599                        self.left_mut(w, Node::set_color(Color::Black));
600                        self.node_mut(w, Node::set_color(Color::Red));
601                        self.right_rotate(w);
602                        w = self.parent_ref(x, Node::right);
603                    }
604                    self.node_mut(w, Node::set_color(self.parent_ref(x, Node::color)));
605                    self.parent_mut(x, Node::set_color(Color::Black));
606                    self.right_mut(w, Node::set_color(Color::Black));
607                    self.left_rotate(self.node_ref(x, Node::parent));
608                    x = self.root;
609                }
610            } else {
611                w = self.parent_ref(x, Node::left);
612                if self.node_ref(w, Node::is_red) {
613                    self.node_mut(w, Node::set_color(Color::Black));
614                    self.parent_mut(x, Node::set_color(Color::Red));
615                    self.right_rotate(self.node_ref(x, Node::parent));
616                    w = self.parent_ref(x, Node::left);
617                }
618                if self.node_ref(w, Node::is_sentinel) {
619                    break;
620                }
621                if self.right_ref(w, Node::is_black) && self.left_ref(w, Node::is_black) {
622                    self.node_mut(w, Node::set_color(Color::Red));
623                    x = self.node_ref(x, Node::parent);
624                } else {
625                    if self.left_ref(w, Node::is_black) {
626                        self.right_mut(w, Node::set_color(Color::Black));
627                        self.node_mut(w, Node::set_color(Color::Red));
628                        self.left_rotate(w);
629                        w = self.parent_ref(x, Node::left);
630                    }
631                    self.node_mut(w, Node::set_color(self.parent_ref(x, Node::color)));
632                    self.parent_mut(x, Node::set_color(Color::Black));
633                    self.left_mut(w, Node::set_color(Color::Black));
634                    self.right_rotate(self.node_ref(x, Node::parent));
635                    x = self.root;
636                }
637            }
638        }
639        self.node_mut(x, Node::set_color(Color::Black));
640    }
641
642    /// Binary tree left rotate.
643    fn left_rotate(&mut self, x: NodeIndex<Ix>) {
644        if self.right_ref(x, Node::is_sentinel) {
645            return;
646        }
647        let y = self.node_ref(x, Node::right);
648        self.node_mut(x, Node::set_right(self.node_ref(y, Node::left)));
649        if !self.left_ref(y, Node::is_sentinel) {
650            self.left_mut(y, Node::set_parent(x));
651        }
652
653        self.replace_parent(x, y);
654        self.node_mut(y, Node::set_left(x));
655
656        self.rotate_update_max(x, y);
657    }
658
659    /// Binary tree right rotate.
660    fn right_rotate(&mut self, x: NodeIndex<Ix>) {
661        if self.left_ref(x, Node::is_sentinel) {
662            return;
663        }
664        let y = self.node_ref(x, Node::left);
665        self.node_mut(x, Node::set_left(self.node_ref(y, Node::right)));
666        if !self.right_ref(y, Node::is_sentinel) {
667            self.right_mut(y, Node::set_parent(x));
668        }
669
670        self.replace_parent(x, y);
671        self.node_mut(y, Node::set_right(x));
672
673        self.rotate_update_max(x, y);
674    }
675
676    /// Replace parent during a rotation.
677    fn replace_parent(&mut self, x: NodeIndex<Ix>, y: NodeIndex<Ix>) {
678        self.node_mut(y, Node::set_parent(self.node_ref(x, Node::parent)));
679        if self.parent_ref(x, Node::is_sentinel) {
680            self.root = y;
681        } else if self.is_left_child(x) {
682            self.parent_mut(x, Node::set_left(y));
683        } else {
684            self.parent_mut(x, Node::set_right(y));
685        }
686        self.node_mut(x, Node::set_parent(y));
687    }
688
689    /// Update the max value after a rotation.
690    fn rotate_update_max(&mut self, x: NodeIndex<Ix>, y: NodeIndex<Ix>) {
691        self.node_mut(y, Node::set_max_index(self.node_ref(x, Node::max_index)));
692        self.recaculate_max(x);
693    }
694
695    /// Update the max value towards the root
696    fn update_max_bottom_up(&mut self, x: NodeIndex<Ix>) {
697        let mut p = x;
698        while !self.node_ref(p, Node::is_sentinel) {
699            self.recaculate_max(p);
700            p = self.node_ref(p, Node::parent);
701        }
702    }
703
704    /// Recaculate max value from left and right childrens
705    fn recaculate_max(&mut self, x: NodeIndex<Ix>) {
706        self.node_mut(x, Node::set_max_index(x));
707        let x_left = self.node_ref(x, Node::left);
708        let x_right = self.node_ref(x, Node::right);
709        if self.max(x_left) > self.max(x) {
710            self.node_mut(
711                x,
712                Node::set_max_index(self.node_ref(x_left, Node::max_index)),
713            );
714        }
715        if self.max(x_right) > self.max(x) {
716            self.node_mut(
717                x,
718                Node::set_max_index(self.node_ref(x_right, Node::max_index)),
719            );
720        }
721    }
722
723    /// Find the node with the minimum interval.
724    fn tree_minimum(&self, mut x: NodeIndex<Ix>) -> NodeIndex<Ix> {
725        while !self.left_ref(x, Node::is_sentinel) {
726            x = self.node_ref(x, Node::left);
727        }
728        x
729    }
730
731    /// Replace one subtree as a child of its parent with another subtree.
732    fn transplant(&mut self, u: NodeIndex<Ix>, v: NodeIndex<Ix>) {
733        if self.parent_ref(u, Node::is_sentinel) {
734            self.root = v;
735        } else if self.is_left_child(u) {
736            self.parent_mut(u, Node::set_left(v));
737        } else {
738            self.parent_mut(u, Node::set_right(v));
739        }
740        self.node_mut(v, Node::set_parent(self.node_ref(u, Node::parent)));
741    }
742
743    /// Check if a node is a left child of its parent.
744    fn is_left_child(&self, node_idx: NodeIndex<Ix>) -> bool {
745        self.parent_ref(node_idx, Node::left) == node_idx
746    }
747
748    /// Check if a node is a right child of its parent.
749    fn is_right_child(&self, node_idx: NodeIndex<Ix>) -> bool {
750        self.parent_ref(node_idx, Node::right) == node_idx
751    }
752
753    /// Update nodes indices after remove
754    ///
755    /// This method has a time complexity of `O(logn)`, as we need to
756    /// update the max index from bottom to top.
757    fn update_idx(&mut self, old: NodeIndex<Ix>, new: NodeIndex<Ix>) {
758        if self.root == old {
759            self.root = new;
760        }
761        if self.nodes.get(new.index()).is_some() {
762            if !self.parent_ref(new, Node::is_sentinel) {
763                if self.parent_ref(new, Node::left) == old {
764                    self.parent_mut(new, Node::set_left(new));
765                } else {
766                    self.parent_mut(new, Node::set_right(new));
767                }
768            }
769            self.left_mut(new, Node::set_parent(new));
770            self.right_mut(new, Node::set_parent(new));
771
772            let mut p = new;
773            while !self.node_ref(p, Node::is_sentinel) {
774                if self.node_ref(p, Node::max_index) == old {
775                    self.node_mut(p, Node::set_max_index(new));
776                }
777                p = self.node_ref(p, Node::parent);
778            }
779        }
780    }
781}
782
783#[cfg(feature = "graphviz")]
784impl<T, V, Ix> IntervalMap<T, V, Ix>
785where
786    T: Ord + Copy + Display,
787    V: Display,
788    Ix: IndexType,
789{
790    /// writes dot file to `filename`. `T` and `V` should implement `Display`.
791    pub fn draw(&self, filename: &str) -> std::io::Result<()> {
792        let mut file = OpenOptions::new()
793            .write(true)
794            .create(true)
795            .truncate(true)
796            .open(filename)?;
797        writeln!(file, "digraph {{")?;
798        // begin at 1, because 0 is sentinel node
799        for i in 1..self.nodes.len() {
800            self.nodes[i].draw(i, &mut file)?;
801        }
802        writeln!(file, "}}")
803    }
804}
805
806#[cfg(feature = "graphviz")]
807impl<T, V, Ix> IntervalMap<T, V, Ix>
808where
809    T: Ord + Copy + Display,
810    Ix: IndexType,
811{
812    /// Writes dot file to `filename` without values. `T` should implement `Display`.
813    pub fn draw_without_value(&self, filename: &str) -> std::io::Result<()> {
814        let mut file = OpenOptions::new()
815            .write(true)
816            .create(true)
817            .truncate(true)
818            .open(filename)?;
819        writeln!(file, "digraph {{")?;
820        // begin at 1, because 0 is sentinel node
821        for i in 1..self.nodes.len() {
822            self.nodes[i].draw_without_value(i, &mut file)?;
823        }
824        writeln!(file, "}}")
825    }
826}
827
828// Convenient methods for reference or mutate current/parent/left/right node
829impl<'a, T, V, Ix> IntervalMap<T, V, Ix>
830where
831    T: Ord,
832    Ix: IndexType,
833{
834    pub(crate) fn node_ref<F, R>(&'a self, node_idx: NodeIndex<Ix>, op: F) -> R
835    where
836        R: 'a,
837        F: FnOnce(&'a Node<T, V, Ix>) -> R,
838    {
839        op(&self.nodes[node_idx.index()])
840    }
841
842    pub(crate) fn node_mut<F, R>(&'a mut self, node_idx: NodeIndex<Ix>, op: F) -> R
843    where
844        R: 'a,
845        F: FnOnce(&'a mut Node<T, V, Ix>) -> R,
846    {
847        op(&mut self.nodes[node_idx.index()])
848    }
849
850    pub(crate) fn left_ref<F, R>(&'a self, node_idx: NodeIndex<Ix>, op: F) -> R
851    where
852        R: 'a,
853        F: FnOnce(&'a Node<T, V, Ix>) -> R,
854    {
855        let idx = self.nodes[node_idx.index()].left().index();
856        op(&self.nodes[idx])
857    }
858
859    pub(crate) fn right_ref<F, R>(&'a self, node_idx: NodeIndex<Ix>, op: F) -> R
860    where
861        R: 'a,
862        F: FnOnce(&'a Node<T, V, Ix>) -> R,
863    {
864        let idx = self.nodes[node_idx.index()].right().index();
865        op(&self.nodes[idx])
866    }
867
868    fn parent_ref<F, R>(&'a self, node_idx: NodeIndex<Ix>, op: F) -> R
869    where
870        R: 'a,
871        F: FnOnce(&'a Node<T, V, Ix>) -> R,
872    {
873        let idx = self.nodes[node_idx.index()].parent().index();
874        op(&self.nodes[idx])
875    }
876
877    fn grand_parent_ref<F, R>(&'a self, node_idx: NodeIndex<Ix>, op: F) -> R
878    where
879        R: 'a,
880        F: FnOnce(&'a Node<T, V, Ix>) -> R,
881    {
882        let parent_idx = self.nodes[node_idx.index()].parent().index();
883        let grand_parent_idx = self.nodes[parent_idx].parent().index();
884        op(&self.nodes[grand_parent_idx])
885    }
886
887    fn left_mut<F, R>(&'a mut self, node_idx: NodeIndex<Ix>, op: F) -> R
888    where
889        R: 'a,
890        F: FnOnce(&'a mut Node<T, V, Ix>) -> R,
891    {
892        let idx = self.nodes[node_idx.index()].left().index();
893        op(&mut self.nodes[idx])
894    }
895
896    fn right_mut<F, R>(&'a mut self, node_idx: NodeIndex<Ix>, op: F) -> R
897    where
898        R: 'a,
899        F: FnOnce(&'a mut Node<T, V, Ix>) -> R,
900    {
901        let idx = self.nodes[node_idx.index()].right().index();
902        op(&mut self.nodes[idx])
903    }
904
905    fn parent_mut<F, R>(&'a mut self, node_idx: NodeIndex<Ix>, op: F) -> R
906    where
907        R: 'a,
908        F: FnOnce(&'a mut Node<T, V, Ix>) -> R,
909    {
910        let idx = self.nodes[node_idx.index()].parent().index();
911        op(&mut self.nodes[idx])
912    }
913
914    fn grand_parent_mut<F, R>(&'a mut self, node_idx: NodeIndex<Ix>, op: F) -> R
915    where
916        R: 'a,
917        F: FnOnce(&'a mut Node<T, V, Ix>) -> R,
918    {
919        let parent_idx = self.nodes[node_idx.index()].parent().index();
920        let grand_parent_idx = self.nodes[parent_idx].parent().index();
921        op(&mut self.nodes[grand_parent_idx])
922    }
923
924    pub(crate) fn max(&self, node_idx: NodeIndex<Ix>) -> Option<&T> {
925        let max_index = self.nodes[node_idx.index()].max_index?.index();
926        self.nodes[max_index].interval.as_ref().map(|i| &i.high)
927    }
928}
929
930#[cfg(test)]
931mod test {
932    use super::*;
933
934    #[derive(Debug, PartialEq, Eq)]
935    pub struct VisitedInterval<T> {
936        key: Interval<T>,
937        left: Option<Interval<T>>,
938        right: Option<Interval<T>>,
939        color: Color,
940        depth: i32,
941    }
942
943    impl<T> VisitedInterval<T> {
944        pub fn new(
945            key: Interval<T>,
946            left: Option<Interval<T>>,
947            right: Option<Interval<T>>,
948            color: Color,
949            depth: i32,
950        ) -> Self {
951            Self {
952                key,
953                left,
954                right,
955                color,
956                depth,
957            }
958        }
959    }
960
961    impl<T, V, Ix> IntervalMap<T, V, Ix>
962    where
963        T: Ord + Clone,
964        Ix: IndexType,
965    {
966        fn visit_level(&self) -> Vec<VisitedInterval<T>> {
967            let mut res: Vec<VisitedInterval<T>> = Vec::new();
968            let mut queue = VecDeque::new();
969            queue.push_back(self.root);
970            let mut depth = 0;
971            while !queue.is_empty() {
972                for _ in 0..queue.len() {
973                    let p = queue.pop_front().unwrap();
974                    let node = &self.nodes[p.index()];
975                    let p_left_node = &self.nodes[node.left().index()];
976                    let p_right_node = &self.nodes[node.right().index()];
977
978                    res.push(VisitedInterval {
979                        key: node.interval.clone().unwrap(),
980                        left: p_left_node.interval.clone(),
981                        right: p_right_node.interval.clone(),
982                        color: node.color(),
983                        depth,
984                    });
985                    if !p_left_node.is_sentinel() {
986                        queue.push_back(node.left())
987                    }
988                    if !p_right_node.is_sentinel() {
989                        queue.push_back(node.right())
990                    }
991                }
992                depth += 1;
993            }
994            res
995        }
996    }
997
998    #[test]
999    fn test_interval_tree_insert() {
1000        let mut map = IntervalMap::new();
1001        map.insert(Interval::new(16, 21), 30);
1002        map.insert(Interval::new(8, 9), 23);
1003        map.insert(Interval::new(0, 3), 3);
1004        map.insert(Interval::new(5, 8), 10);
1005        map.insert(Interval::new(6, 10), 10);
1006        map.insert(Interval::new(15, 23), 23);
1007        map.insert(Interval::new(17, 19), 20);
1008        map.insert(Interval::new(25, 30), 30);
1009        map.insert(Interval::new(26, 27), 26);
1010        map.insert(Interval::new(19, 20), 20);
1011
1012        let expected = vec![
1013            VisitedInterval::new(
1014                Interval::new(16, 21),
1015                Some(Interval::new(8, 9)),
1016                Some(Interval::new(25, 30)),
1017                Color::Black,
1018                0,
1019            ),
1020            VisitedInterval::new(
1021                Interval::new(8, 9),
1022                Some(Interval::new(5, 8)),
1023                Some(Interval::new(15, 23)),
1024                Color::Red,
1025                1,
1026            ),
1027            VisitedInterval::new(
1028                Interval::new(25, 30),
1029                Some(Interval::new(17, 19)),
1030                Some(Interval::new(26, 27)),
1031                Color::Red,
1032                1,
1033            ),
1034            VisitedInterval::new(
1035                Interval::new(5, 8),
1036                Some(Interval::new(0, 3)),
1037                Some(Interval::new(6, 10)),
1038                Color::Black,
1039                2,
1040            ),
1041            VisitedInterval::new(Interval::new(15, 23), None, None, Color::Black, 2),
1042            VisitedInterval::new(
1043                Interval::new(17, 19),
1044                None,
1045                Some(Interval::new(19, 20)),
1046                Color::Black,
1047                2,
1048            ),
1049            VisitedInterval::new(Interval::new(26, 27), None, None, Color::Black, 2),
1050            VisitedInterval::new(Interval::new(0, 3), None, None, Color::Red, 3),
1051            VisitedInterval::new(Interval::new(6, 10), None, None, Color::Red, 3),
1052            VisitedInterval::new(Interval::new(19, 20), None, None, Color::Red, 3),
1053        ];
1054
1055        let res = map.visit_level();
1056        assert_eq!(res, expected);
1057    }
1058
1059    #[test]
1060    fn test_interval_tree_self_balanced() {
1061        let mut map = IntervalMap::new();
1062        map.insert(Interval::new(0, 1), 0);
1063        map.insert(Interval::new(1, 2), 0);
1064        map.insert(Interval::new(3, 4), 0);
1065        map.insert(Interval::new(5, 6), 0);
1066        map.insert(Interval::new(7, 8), 0);
1067        map.insert(Interval::new(8, 9), 0);
1068
1069        let expected = vec![
1070            VisitedInterval::new(
1071                Interval::new(1, 2),
1072                Some(Interval::new(0, 1)),
1073                Some(Interval::new(5, 6)),
1074                Color::Black,
1075                0,
1076            ),
1077            VisitedInterval::new(Interval::new(0, 1), None, None, Color::Black, 1),
1078            VisitedInterval::new(
1079                Interval::new(5, 6),
1080                Some(Interval::new(3, 4)),
1081                Some(Interval::new(7, 8)),
1082                Color::Red,
1083                1,
1084            ),
1085            VisitedInterval::new(Interval::new(3, 4), None, None, Color::Black, 2),
1086            VisitedInterval::new(
1087                Interval::new(7, 8),
1088                None,
1089                Some(Interval::new(8, 9)),
1090                Color::Black,
1091                2,
1092            ),
1093            VisitedInterval::new(Interval::new(8, 9), None, None, Color::Red, 3),
1094        ];
1095
1096        let res = map.visit_level();
1097        assert_eq!(res, expected);
1098    }
1099
1100    #[test]
1101    fn test_interval_tree_delete() {
1102        let mut map = IntervalMap::new();
1103        map.insert(Interval::new(510, 511), 0);
1104        map.insert(Interval::new(82, 83), 0);
1105        map.insert(Interval::new(830, 831), 0);
1106        map.insert(Interval::new(11, 12), 0);
1107        map.insert(Interval::new(383, 384), 0);
1108        map.insert(Interval::new(647, 648), 0);
1109        map.insert(Interval::new(899, 900), 0);
1110        map.insert(Interval::new(261, 262), 0);
1111        map.insert(Interval::new(410, 411), 0);
1112        map.insert(Interval::new(514, 515), 0);
1113        map.insert(Interval::new(815, 816), 0);
1114        map.insert(Interval::new(888, 889), 0);
1115        map.insert(Interval::new(972, 973), 0);
1116        map.insert(Interval::new(238, 239), 0);
1117        map.insert(Interval::new(292, 293), 0);
1118        map.insert(Interval::new(953, 954), 0);
1119
1120        let expected_before_delete = vec![
1121            VisitedInterval::new(
1122                Interval::new(510, 511),
1123                Some(Interval::new(82, 83)),
1124                Some(Interval::new(830, 831)),
1125                Color::Black,
1126                0,
1127            ),
1128            VisitedInterval::new(
1129                Interval::new(82, 83),
1130                Some(Interval::new(11, 12)),
1131                Some(Interval::new(383, 384)),
1132                Color::Black,
1133                1,
1134            ),
1135            VisitedInterval::new(
1136                Interval::new(830, 831),
1137                Some(Interval::new(647, 648)),
1138                Some(Interval::new(899, 900)),
1139                Color::Black,
1140                1,
1141            ),
1142            VisitedInterval::new(Interval::new(11, 12), None, None, Color::Black, 2),
1143            VisitedInterval::new(
1144                Interval::new(383, 384),
1145                Some(Interval::new(261, 262)),
1146                Some(Interval::new(410, 411)),
1147                Color::Red,
1148                2,
1149            ),
1150            VisitedInterval::new(
1151                Interval::new(647, 648),
1152                Some(Interval::new(514, 515)),
1153                Some(Interval::new(815, 816)),
1154                Color::Black,
1155                2,
1156            ),
1157            VisitedInterval::new(
1158                Interval::new(899, 900),
1159                Some(Interval::new(888, 889)),
1160                Some(Interval::new(972, 973)),
1161                Color::Red,
1162                2,
1163            ),
1164            VisitedInterval::new(
1165                Interval::new(261, 262),
1166                Some(Interval::new(238, 239)),
1167                Some(Interval::new(292, 293)),
1168                Color::Black,
1169                3,
1170            ),
1171            VisitedInterval::new(Interval::new(410, 411), None, None, Color::Black, 3),
1172            VisitedInterval::new(Interval::new(514, 515), None, None, Color::Red, 3),
1173            VisitedInterval::new(Interval::new(815, 816), None, None, Color::Red, 3),
1174            VisitedInterval::new(Interval::new(888, 889), None, None, Color::Black, 3),
1175            VisitedInterval::new(
1176                Interval::new(972, 973),
1177                Some(Interval::new(953, 954)),
1178                None,
1179                Color::Black,
1180                3,
1181            ),
1182            VisitedInterval::new(Interval::new(238, 239), None, None, Color::Red, 4),
1183            VisitedInterval::new(Interval::new(292, 293), None, None, Color::Red, 4),
1184            VisitedInterval::new(Interval::new(953, 954), None, None, Color::Red, 4),
1185        ];
1186
1187        let res = map.visit_level();
1188        assert_eq!(res, expected_before_delete);
1189
1190        // delete the node "514"
1191        let range514 = Interval::new(514, 515);
1192        let deleted = map.remove(&range514);
1193        assert!(deleted.is_some());
1194
1195        let expected_after_delete514 = vec![
1196            VisitedInterval::new(
1197                Interval::new(510, 511),
1198                Some(Interval::new(82, 83)),
1199                Some(Interval::new(830, 831)),
1200                Color::Black,
1201                0,
1202            ),
1203            VisitedInterval::new(
1204                Interval::new(82, 83),
1205                Some(Interval::new(11, 12)),
1206                Some(Interval::new(383, 384)),
1207                Color::Black,
1208                1,
1209            ),
1210            VisitedInterval::new(
1211                Interval::new(830, 831),
1212                Some(Interval::new(647, 648)),
1213                Some(Interval::new(899, 900)),
1214                Color::Black,
1215                1,
1216            ),
1217            VisitedInterval::new(Interval::new(11, 12), None, None, Color::Black, 2),
1218            VisitedInterval::new(
1219                Interval::new(383, 384),
1220                Some(Interval::new(261, 262)),
1221                Some(Interval::new(410, 411)),
1222                Color::Red,
1223                2,
1224            ),
1225            VisitedInterval::new(
1226                Interval::new(647, 648),
1227                None,
1228                Some(Interval::new(815, 816)),
1229                Color::Black,
1230                2,
1231            ),
1232            VisitedInterval::new(
1233                Interval::new(899, 900),
1234                Some(Interval::new(888, 889)),
1235                Some(Interval::new(972, 973)),
1236                Color::Red,
1237                2,
1238            ),
1239            VisitedInterval::new(
1240                Interval::new(261, 262),
1241                Some(Interval::new(238, 239)),
1242                Some(Interval::new(292, 293)),
1243                Color::Black,
1244                3,
1245            ),
1246            VisitedInterval::new(Interval::new(410, 411), None, None, Color::Black, 3),
1247            VisitedInterval::new(Interval::new(815, 816), None, None, Color::Red, 3),
1248            VisitedInterval::new(Interval::new(888, 889), None, None, Color::Black, 3),
1249            VisitedInterval::new(
1250                Interval::new(972, 973),
1251                Some(Interval::new(953, 954)),
1252                None,
1253                Color::Black,
1254                3,
1255            ),
1256            VisitedInterval::new(Interval::new(238, 239), None, None, Color::Red, 4),
1257            VisitedInterval::new(Interval::new(292, 293), None, None, Color::Red, 4),
1258            VisitedInterval::new(Interval::new(953, 954), None, None, Color::Red, 4),
1259        ];
1260
1261        let res = map.visit_level();
1262        assert_eq!(res, expected_after_delete514);
1263
1264        // delete the node "11"
1265        let range11 = Interval::new(11, 12);
1266        let deleted = map.remove(&range11);
1267        assert!(deleted.is_some());
1268
1269        let expected_after_delete11 = vec![
1270            VisitedInterval::new(
1271                Interval::new(510, 511),
1272                Some(Interval::new(383, 384)),
1273                Some(Interval::new(830, 831)),
1274                Color::Black,
1275                0,
1276            ),
1277            VisitedInterval::new(
1278                Interval::new(383, 384),
1279                Some(Interval::new(261, 262)),
1280                Some(Interval::new(410, 411)),
1281                Color::Black,
1282                1,
1283            ),
1284            VisitedInterval::new(
1285                Interval::new(830, 831),
1286                Some(Interval::new(647, 648)),
1287                Some(Interval::new(899, 900)),
1288                Color::Black,
1289                1,
1290            ),
1291            VisitedInterval::new(
1292                Interval::new(261, 262),
1293                Some(Interval::new(82, 83)),
1294                Some(Interval::new(292, 293)),
1295                Color::Red,
1296                2,
1297            ),
1298            VisitedInterval::new(Interval::new(410, 411), None, None, Color::Black, 2),
1299            VisitedInterval::new(
1300                Interval::new(647, 648),
1301                None,
1302                Some(Interval::new(815, 816)),
1303                Color::Black,
1304                2,
1305            ),
1306            VisitedInterval::new(
1307                Interval::new(899, 900),
1308                Some(Interval::new(888, 889)),
1309                Some(Interval::new(972, 973)),
1310                Color::Red,
1311                2,
1312            ),
1313            VisitedInterval::new(
1314                Interval::new(82, 83),
1315                None,
1316                Some(Interval::new(238, 239)),
1317                Color::Black,
1318                3,
1319            ),
1320            VisitedInterval::new(Interval::new(292, 293), None, None, Color::Black, 3),
1321            VisitedInterval::new(Interval::new(815, 816), None, None, Color::Red, 3),
1322            VisitedInterval::new(Interval::new(888, 889), None, None, Color::Black, 3),
1323            VisitedInterval::new(
1324                Interval::new(972, 973),
1325                Some(Interval::new(953, 954)),
1326                None,
1327                Color::Black,
1328                3,
1329            ),
1330            VisitedInterval::new(Interval::new(238, 239), None, None, Color::Red, 4),
1331            VisitedInterval::new(Interval::new(953, 954), None, None, Color::Red, 4),
1332        ];
1333
1334        let res = map.visit_level();
1335        assert_eq!(res, expected_after_delete11);
1336    }
1337
1338    impl Interval<String> {
1339        fn new_point(x: &str) -> Interval<String> {
1340            let mut hx = x.to_owned();
1341            hx.push('\0');
1342            Interval {
1343                low: x.to_owned(),
1344                high: hx,
1345            }
1346        }
1347    }
1348
1349    #[test]
1350    fn test_interval_tree_intersects() {
1351        let mut map = IntervalMap::<String, i32>::new();
1352        map.insert(Interval::new(String::from("1"), String::from("3")), 123);
1353
1354        assert!(!map.overlaps(&Interval::new_point("0")), "contains 0");
1355        assert!(map.overlaps(&Interval::new_point("1")), "missing 1");
1356        assert!(map.overlaps(&Interval::new_point("11")), "missing 11");
1357        assert!(map.overlaps(&Interval::new_point("2")), "missing 2");
1358        assert!(!map.overlaps(&Interval::new_point("3")), "contains 3");
1359    }
1360
1361    #[test]
1362    fn test_interval_tree_find_all_overlap() {
1363        let mut map = IntervalMap::<String, i32>::new();
1364        map.insert(Interval::new(String::from("0"), String::from("1")), 123);
1365        map.insert(Interval::new(String::from("0"), String::from("2")), 456);
1366        map.insert(Interval::new(String::from("5"), String::from("6")), 789);
1367        map.insert(Interval::new(String::from("6"), String::from("8")), 999);
1368        map.insert(Interval::new(String::from("0"), String::from("3")), 0);
1369
1370        let tmp = map.node_ref(map.node_ref(map.root, Node::max_index), Node::interval);
1371        assert_eq!(tmp, &Interval::new(String::from("6"), String::from("8")));
1372
1373        assert_eq!(map.find_all_overlap(&Interval::new_point("0")).len(), 3);
1374        assert_eq!(map.find_all_overlap(&Interval::new_point("1")).len(), 2);
1375        assert_eq!(map.find_all_overlap(&Interval::new_point("2")).len(), 1);
1376        assert_eq!(map.find_all_overlap(&Interval::new_point("3")).len(), 0);
1377        assert_eq!(map.find_all_overlap(&Interval::new_point("5")).len(), 1);
1378        assert_eq!(map.find_all_overlap(&Interval::new_point("55")).len(), 1);
1379        assert_eq!(map.find_all_overlap(&Interval::new_point("6")).len(), 1);
1380    }
1381
1382    type TestCaseBFn = dyn Fn(&(&Interval<i32>, &())) -> bool;
1383    struct TestCaseB {
1384        f: Box<TestCaseBFn>,
1385        wcount: i32,
1386    }
1387    #[test]
1388    fn test_interval_tree_visit_exit() {
1389        let ivls = vec![
1390            Interval::new(1, 10),
1391            Interval::new(2, 5),
1392            Interval::new(3, 6),
1393            Interval::new(4, 8),
1394        ];
1395        let ivl_range = Interval::new(0, 100);
1396
1397        let tests = [
1398            TestCaseB {
1399                f: Box::new(|_| false),
1400                wcount: 1,
1401            },
1402            TestCaseB {
1403                f: Box::new({
1404                    let ivls = ivls.clone();
1405                    move |v| v.0.low <= ivls[0].low
1406                }),
1407                wcount: 2,
1408            },
1409            TestCaseB {
1410                f: Box::new({
1411                    let ivls = ivls.clone();
1412                    move |v| v.0.low < ivls[2].low
1413                }),
1414                wcount: 3,
1415            },
1416            TestCaseB {
1417                f: Box::new(|_| true),
1418                wcount: 4,
1419            },
1420        ];
1421
1422        for (i, tt) in tests.iter().enumerate() {
1423            let mut map = IntervalMap::new();
1424            ivls.iter().for_each(|v| {
1425                map.insert(v.clone(), ());
1426            });
1427            let mut count = 0;
1428            map.filter_iter(&ivl_range).find(|v| {
1429                count += 1;
1430                !(tt.f)(v)
1431            });
1432            assert_eq!(count, tt.wcount, "#{}: error", i);
1433        }
1434    }
1435
1436    struct TestCaseC {
1437        ivls: Vec<Interval<i32>>,
1438        chk_ivl: Interval<i32>,
1439
1440        w_contains: bool,
1441    }
1442    #[test]
1443    fn test_interval_tree_contains() {
1444        let tests = [
1445            TestCaseC {
1446                ivls: vec![Interval::new(1, 10)],
1447                chk_ivl: Interval::new(0, 100),
1448
1449                w_contains: false,
1450            },
1451            TestCaseC {
1452                ivls: vec![Interval::new(1, 10)],
1453                chk_ivl: Interval::new(1, 10),
1454
1455                w_contains: true,
1456            },
1457            TestCaseC {
1458                ivls: vec![Interval::new(1, 10)],
1459                chk_ivl: Interval::new(2, 8),
1460
1461                w_contains: true,
1462            },
1463            TestCaseC {
1464                ivls: vec![Interval::new(1, 5), Interval::new(6, 10)],
1465                chk_ivl: Interval::new(1, 10),
1466
1467                w_contains: false,
1468            },
1469            TestCaseC {
1470                ivls: vec![Interval::new(1, 5), Interval::new(3, 10)],
1471                chk_ivl: Interval::new(1, 10),
1472
1473                w_contains: true,
1474            },
1475            TestCaseC {
1476                ivls: vec![
1477                    Interval::new(1, 4),
1478                    Interval::new(4, 7),
1479                    Interval::new(3, 10),
1480                ],
1481                chk_ivl: Interval::new(1, 10),
1482
1483                w_contains: true,
1484            },
1485            TestCaseC {
1486                ivls: vec![],
1487                chk_ivl: Interval::new(1, 10),
1488
1489                w_contains: false,
1490            },
1491        ];
1492        for (i, tt) in tests.iter().enumerate() {
1493            let mut map = IntervalMap::new();
1494            tt.ivls.iter().for_each(|v| {
1495                map.insert(v.clone(), ());
1496            });
1497            assert_eq!(map.contains(&tt.chk_ivl), tt.w_contains, "#{}: error", i);
1498        }
1499    }
1500
1501    struct TestCaseA {
1502        ivls: Vec<Interval<i32>>,
1503        visit_range: Interval<i32>,
1504    }
1505    #[test]
1506    fn test_interval_tree_sorted_visit() {
1507        let tests = [
1508            TestCaseA {
1509                ivls: vec![
1510                    Interval::new(1, 10),
1511                    Interval::new(2, 5),
1512                    Interval::new(3, 6),
1513                ],
1514                visit_range: Interval::new(0, 100),
1515            },
1516            TestCaseA {
1517                ivls: vec![
1518                    Interval::new(1, 10),
1519                    Interval::new(10, 12),
1520                    Interval::new(3, 6),
1521                ],
1522                visit_range: Interval::new(0, 100),
1523            },
1524            TestCaseA {
1525                ivls: vec![
1526                    Interval::new(2, 3),
1527                    Interval::new(3, 4),
1528                    Interval::new(6, 7),
1529                    Interval::new(5, 6),
1530                ],
1531                visit_range: Interval::new(0, 100),
1532            },
1533            TestCaseA {
1534                ivls: vec![
1535                    Interval::new(2, 3),
1536                    Interval::new(2, 4),
1537                    Interval::new(3, 7),
1538                    Interval::new(2, 5),
1539                    Interval::new(3, 8),
1540                    Interval::new(3, 5),
1541                ],
1542                visit_range: Interval::new(0, 100),
1543            },
1544        ];
1545        for (i, tt) in tests.iter().enumerate() {
1546            let mut map = IntervalMap::new();
1547            tt.ivls.iter().for_each(|v| {
1548                map.insert(v.clone(), ());
1549            });
1550            let mut last = tt.ivls[0].low;
1551            let count = map
1552                .iter()
1553                .filter(|v| v.0.overlaps(&tt.visit_range))
1554                .fold(0, |acc, v| {
1555                    assert!(
1556                        last <= v.0.low,
1557                        "#{}: expected less than {}, got interval {:?}",
1558                        i,
1559                        last,
1560                        v.0
1561                    );
1562                    last = v.0.low;
1563                    acc + 1
1564                });
1565            assert_eq!(count, tt.ivls.len(), "#{}: did not cover all intervals.", i);
1566        }
1567    }
1568}
rb_interval_map/intervalmap.rs

rb_interval_map/
intervalmap.rs
