store_interval_tree/
interval.rs

1use alloc::{
2    rc::Rc,
3    string::{String, ToString},
4};
5use core::{
6    cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd},
7    ops::Bound::{self, Excluded, Included, Unbounded},
8};
9use num::Num;
10
11/// A utility data structure to represent intervals.
12/// It supports open, close and unbounded intervals
13///
14/// # Examples
15/// ```
16/// use store_interval_tree::Interval;
17/// use std::ops::Bound::*;
18///
19/// // initialize interval [2,4]
20/// let interval1 = Interval::new(Included(2), Included(4));
21///
22/// // initialize interval [2,4)
23/// let interval2 = Interval::new(Included(2), Excluded(4));
24///
25/// // initialize point [4,4]
26/// let point1 = Interval::point(4);
27///
28/// // compare intervals
29/// // first, lower bounds are compared. if they're equal, higher bounds will be compared
30/// assert!(interval2 < interval1);
31///
32/// // check if two intervals overlap
33/// assert!(Interval::overlaps(&interval1, &interval2));
34///
35/// // check if one point and an interval overlap
36/// assert!(Interval::overlaps(&interval1, &point1));
37/// assert!(!Interval::overlaps(&interval2, &point1));
38///
39/// // check if one interval contains another interval
40/// assert!(Interval::contains(&interval1, &interval2));
41///
42/// // get overlapped interval between two intervals
43/// assert!(Interval::get_overlap(&interval1, &interval2).unwrap() == interval2);
44/// ```
45#[derive(Clone, Debug, Hash)]
46pub struct Interval<T: Ord> {
47    low: Rc<Bound<T>>,
48    high: Rc<Bound<T>>,
49}
50
51impl<T: Ord> Interval<T> {
52    /// Creates a new interval
53    ///
54    /// # Arguments
55    /// * `low`: lower bound of the interval
56    /// * `high`: higher bound of the interval
57    ///
58    /// # Panics
59    /// * panics if `low` > `high`. `low` == `high` is acceptable if interval is closed at both sides: [low, high]
60    ///
61    /// # Example
62    /// ```
63    /// use store_interval_tree::Interval;
64    /// use std::ops::Bound::*;
65    ///
66    /// // create the interval [2,4)
67    /// let interval1 = Interval::new(Included(2), Excluded(4));
68    ///
69    /// // create the interval (-inf,4)
70    /// let interval2 = Interval::new(Unbounded, Excluded(4));
71    ///
72    ///
73    /// // create the interval (1,+inf)
74    /// let interval3 = Interval::new(Excluded(1), Unbounded);
75    /// ```
76    pub fn new(low: Bound<T>, high: Bound<T>) -> Interval<T> {
77        let interval = Interval {
78            low: Rc::new(low),
79            high: Rc::new(high),
80        };
81
82        assert!(Interval::valid(&interval), "Interval is not valid");
83        interval
84    }
85
86    /// Creates a point.
87    ///
88    /// # Arguments
89    /// * `value`: value of the point
90    ///
91    /// # Examples
92    /// ```
93    /// use store_interval_tree::Interval;
94    /// use std::ops::Bound::*;
95    ///
96    /// // create point (2) or equivalently interval [2,2]
97    /// let point1 = Interval::point(2);
98    /// ```
99    pub fn point(value: T) -> Interval<T> {
100        let low = Rc::new(Included(value));
101        let high = Rc::clone(&low);
102
103        let interval = Interval { low, high };
104
105        assert!(Interval::valid(&interval), "Interval is not valid");
106
107        interval
108    }
109
110    /// Creates a duplicate of the interval
111    ///
112    /// # Examples
113    /// ```
114    /// use store_interval_tree::Interval;
115    /// use std::ops::Bound::*;
116    ///
117    /// let interval = Interval::new(Included(2), Unbounded);
118    /// let duplicate = interval.duplicate();
119    ///
120    /// assert!(interval == duplicate);
121    /// ```
122    #[must_use]
123    pub fn duplicate(&self) -> Interval<T> {
124        Interval {
125            low: self.get_low(),
126            high: self.get_high(),
127        }
128    }
129
130    fn valid(interval: &Interval<T>) -> bool {
131        match (&interval.low(), &interval.high()) {
132            (Included(low), Included(high)) => low <= high,
133
134            (Included(low) | Excluded(low), Excluded(high)) | (Excluded(low), Included(high)) => {
135                low < high
136            }
137
138            _ => true,
139        }
140    }
141
142    /// Get reference to lower bound of the interval
143    #[must_use]
144    pub fn low(&self) -> &Bound<T> {
145        self.low.as_ref()
146    }
147
148    /// Get a duplicate of lower bound of the interval
149    #[must_use]
150    pub fn get_low(&self) -> Rc<Bound<T>> {
151        Rc::clone(&self.low)
152    }
153
154    /// Get reference to higher bound of the interval
155    #[must_use]
156    pub fn high(&self) -> &Bound<T> {
157        self.high.as_ref()
158    }
159
160    /// Get a duplicate of higher bound of the interval
161    #[must_use]
162    pub fn get_high(&self) -> Rc<Bound<T>> {
163        Rc::clone(&self.high)
164    }
165
166    /// Returns true if `first` and `second` intervals overlap, false otherwise
167    ///
168    /// # Examples
169    /// ```
170    /// use store_interval_tree::Interval;
171    /// use std::ops::Bound::*;
172    ///
173    /// let interval1 = Interval::new(Included(2), Included(4));
174    /// let interval2 = Interval::new(Included(2), Excluded(4));
175    /// let point1 = Interval::point(4);
176    ///
177    /// assert!(Interval::overlaps(&interval1, &interval2));
178    /// assert!(Interval::overlaps(&interval1, &point1));
179    /// assert!(!Interval::overlaps(&interval2, &point1));
180    /// ```
181    #[must_use]
182    pub fn overlaps(first: &Interval<T>, second: &Interval<T>) -> bool {
183        let high: &Bound<T>;
184        let low: &Bound<T>;
185
186        if *first == *second {
187            return true;
188        } else if first < second {
189            low = second.low();
190            high = first.high();
191        } else {
192            low = first.low();
193            high = second.high();
194        }
195
196        match (low, high) {
197            (Included(low), Included(high)) => high >= low,
198            (Included(low) | Excluded(low), Excluded(high)) | (Excluded(low), Included(high)) => {
199                high > low
200            }
201            _ => true,
202        }
203    }
204
205    /// Returns true if `second` is a sub-interval of `first`, false otherwise
206    ///
207    /// # Examples
208    /// ```
209    /// use store_interval_tree::Interval;
210    /// use std::ops::Bound::*;
211    ///
212    /// let interval1 = Interval::new(Included(2), Included(4));
213    /// let interval2 = Interval::new(Included(2), Excluded(4));
214    ///
215    /// assert!(Interval::contains(&interval1, &interval2));
216    /// ```
217    #[must_use]
218    pub fn contains(first: &Interval<T>, second: &Interval<T>) -> bool {
219        if Interval::overlaps(first, second) {
220            let overlap = Interval::get_overlap(first, second).unwrap();
221
222            overlap == *second
223        } else {
224            false
225        }
226    }
227
228    /// Get overlapped interval of `first` and `second`, `None` otherwise
229    ///
230    /// # Examples
231    /// ```
232    /// use store_interval_tree::Interval;
233    /// use std::ops::Bound::*;
234    ///
235    /// // initialize intervals
236    /// let interval1 = Interval::new(Included(2), Included(4));
237    /// let interval2 = Interval::new(Included(2), Excluded(4));
238    ///
239    /// assert!(Interval::get_overlap(&interval1, &interval2).unwrap() == interval2);
240    /// ```
241    #[must_use]
242    pub fn get_overlap(first: &Interval<T>, second: &Interval<T>) -> Option<Interval<T>> {
243        if !Interval::overlaps(first, second) {
244            return None;
245        }
246
247        let low = match (&first.low(), &second.low()) {
248            (Included(low1) | Excluded(low1), Included(low2))
249            | (Excluded(low1), Excluded(low2)) => {
250                if low1 >= low2 {
251                    Rc::clone(&first.low)
252                } else {
253                    Rc::clone(&second.low)
254                }
255            }
256            (Included(low1), Excluded(low2)) => {
257                if low1 > low2 {
258                    Rc::clone(&first.low)
259                } else {
260                    Rc::clone(&second.low)
261                }
262            }
263            (Unbounded, Included(_) | Excluded(_)) => Rc::clone(&second.low),
264            (Included(_) | Excluded(_), Unbounded) => Rc::clone(&first.low),
265
266            (Unbounded, Unbounded) => Rc::new(Unbounded),
267        };
268
269        let high = match (&first.high(), &second.high()) {
270            (Included(high1) | Excluded(high1), Included(high2))
271            | (Excluded(high1), Excluded(high2)) => {
272                if high1 <= high2 {
273                    Rc::clone(&first.high)
274                } else {
275                    Rc::clone(&second.high)
276                }
277            }
278            (Included(high1), Excluded(high2)) => {
279                if high1 < high2 {
280                    Rc::clone(&first.high)
281                } else {
282                    Rc::clone(&second.high)
283                }
284            }
285            (Unbounded, Included(_) | Excluded(_)) => Rc::clone(&second.high),
286            (Included(_) | Excluded(_), Unbounded) => Rc::clone(&first.high),
287
288            (Unbounded, Unbounded) => Rc::new(Unbounded),
289        };
290
291        Some(Interval { low, high })
292    }
293}
294
295impl<T: Copy + Num + Ord> Interval<T> {
296    /// Returns the span between the start and the end of the interval.
297    /// None if the interval is unbounded.
298    #[must_use]
299    pub fn span(&self) -> Option<T> {
300        match (&self.low(), &self.high()) {
301            (Included(low), Included(high)) => Some(*high + T::one() - *low),
302            (Included(low), Excluded(high)) | (Excluded(low), Included(high)) => Some(*high - *low),
303            (Excluded(low), Excluded(high)) => Some(*high - T::one() - *low),
304            _ => None,
305        }
306    }
307}
308
309impl<T: Ord + core::fmt::Display> core::fmt::Display for Interval<T> {
310    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
311        let low = match &self.low() {
312            Included(low) => format!("[{}", low),
313            Excluded(low) => format!("({}", low),
314            Unbounded => "(_".to_string(),
315        };
316
317        let high: String = match &self.high() {
318            Included(high) => format!("{}]", high),
319            Excluded(high) => format!("{})", high),
320            Unbounded => "_)".to_string(),
321        };
322
323        write!(f, "{},{}", low, high)
324    }
325}
326
327impl<T: Ord> PartialEq for Interval<T> {
328    fn eq(&self, other: &Self) -> bool {
329        self.low == other.low && self.high == other.high
330    }
331}
332
333impl<T: Ord> Eq for Interval<T> {}
334
335impl<T: Ord> PartialOrd for Interval<T> {
336    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
337        // compare low end of the intervals
338        let mut result = match (&self.low(), &other.low()) {
339            (Included(low1), Included(low2)) | (Excluded(low1), Excluded(low2)) => {
340                if low1 < low2 {
341                    Some(Ordering::Less)
342                } else if low1 == low2 {
343                    None
344                } else {
345                    Some(Ordering::Greater)
346                }
347            }
348            (Included(low1), Excluded(low2)) => {
349                if low1 <= low2 {
350                    Some(Ordering::Less)
351                } else {
352                    Some(Ordering::Greater)
353                }
354            }
355            (Excluded(low1), Included(low2)) => {
356                if low1 < low2 {
357                    Some(Ordering::Less)
358                } else {
359                    Some(Ordering::Greater)
360                }
361            }
362
363            (Unbounded, Included(_) | Excluded(_)) => Some(Ordering::Less),
364
365            (Included(_) | Excluded(_), Unbounded) => Some(Ordering::Greater),
366
367            (Unbounded, Unbounded) => None,
368        };
369
370        // if low end was not enough to determine ordering, use high end
371        if result.is_none() {
372            result = match (&self.high(), &other.high()) {
373                (Included(high1), Included(high2)) | (Excluded(high1), Excluded(high2)) => {
374                    if high1 < high2 {
375                        Some(Ordering::Less)
376                    } else if high1 == high2 {
377                        Some(Ordering::Equal)
378                    } else {
379                        Some(Ordering::Greater)
380                    }
381                }
382                (Included(high1), Excluded(high2)) => {
383                    if high1 < high2 {
384                        Some(Ordering::Less)
385                    } else {
386                        Some(Ordering::Greater)
387                    }
388                }
389                (Excluded(high1), Included(high2)) => {
390                    if high1 <= high2 {
391                        Some(Ordering::Less)
392                    } else {
393                        Some(Ordering::Greater)
394                    }
395                }
396                (Unbounded, Included(_) | Excluded(_)) => Some(Ordering::Greater),
397
398                (Included(_) | Excluded(_), Unbounded) => Some(Ordering::Less),
399
400                (Unbounded, Unbounded) => Some(Ordering::Equal),
401            };
402        }
403
404        result
405    }
406}
407
408impl<T: Ord> Ord for Interval<T> {
409    fn cmp(&self, other: &Self) -> Ordering {
410        self.partial_cmp(other).unwrap()
411    }
412}
413
414#[cfg(test)]
415mod tests {
416    use super::*;
417
418    #[test]
419    fn interval_valid_1() {
420        assert!(Interval::valid(&Interval::new(Included(2), Included(2))));
421        assert!(Interval::valid(&Interval::new(Excluded(2), Included(3))));
422        assert!(Interval::valid(&Interval::new(Included(2), Excluded(3))));
423        assert!(Interval::valid(&Interval::new(Excluded(2), Excluded(3))));
424
425        assert!(Interval::valid(&Interval::new(Unbounded, Included(1))));
426        assert!(Interval::valid(&Interval::new(Excluded(2), Unbounded)));
427        assert!(Interval::<usize>::valid(&Interval::new(
428            Unbounded, Unbounded
429        )));
430    }
431
432    #[test]
433    #[should_panic(expected = "Interval is not valid")]
434    fn interval_panic_new_1() {
435        assert!(!Interval::valid(&Interval::new(Included(2), Included(1))));
436    }
437
438    #[test]
439    #[should_panic(expected = "Interval is not valid")]
440    fn interval_panic_new_2() {
441        assert!(!Interval::valid(&Interval::new(Excluded(2), Included(1))));
442    }
443
444    #[test]
445    #[should_panic(expected = "Interval is not valid")]
446    fn interval_panic_new_3() {
447        assert!(!Interval::valid(&Interval::new(Included(2), Excluded(1))));
448    }
449
450    #[test]
451    #[should_panic(expected = "Interval is not valid")]
452    fn interval_panic_new_4() {
453        assert!(!Interval::valid(&Interval::new(Excluded(2), Excluded(1))));
454    }
455
456    #[test]
457    fn interval_compare_1() {
458        let interval1 = Interval::new(Included(2), Included(3));
459        let interval2 = Interval::new(Included(2), Excluded(3));
460        let interval3 = Interval::new(Excluded(2), Included(3));
461        let interval4 = Interval::new(Excluded(2), Excluded(3));
462
463        let interval5 = Interval::new(Unbounded, Excluded(3));
464        let interval6 = Interval::new(Excluded(2), Unbounded);
465        let interval7 = Interval::new(Unbounded, Excluded(3));
466        let interval8 = Interval::<usize>::new(Unbounded, Unbounded);
467
468        assert!(interval1 == interval1);
469        assert!(interval1 > interval2);
470        assert!(interval2 < interval1);
471        assert!(interval2 < interval3);
472        assert!(interval3 > interval4);
473        assert!(interval5 < interval6);
474        assert!(interval7 < interval6);
475        assert!(interval5 < interval8);
476        assert!(interval6 > interval8);
477    }
478
479    #[test]
480    fn interval_overlaps_1() {
481        let interval1 = Interval::new(Included(1), Included(3));
482        let interval2 = Interval::new(Included(2), Included(4));
483
484        assert!(Interval::overlaps(&interval1, &interval2));
485    }
486
487    #[test]
488    fn interval_overlaps_2() {
489        let interval1 = Interval::new(Included(1), Included(3));
490        let interval2 = Interval::new(Included(2), Excluded(3));
491
492        assert!(Interval::overlaps(&interval1, &interval2));
493    }
494
495    #[test]
496    fn interval_overlaps_3() {
497        let interval1 = Interval::new(Included(1), Included(3));
498        let interval2 = Interval::new(Excluded(1), Excluded(3));
499
500        assert!(Interval::overlaps(&interval1, &interval2));
501    }
502
503    #[test]
504    fn interval_overlaps_4() {
505        let interval1 = Interval::new(Included(1), Included(3));
506        let interval2 = Interval::new(Excluded(3), Excluded(4));
507
508        assert!(!Interval::overlaps(&interval1, &interval2));
509    }
510
511    #[test]
512    fn interval_overlaps_5() {
513        let interval1 = Interval::new(Included(1), Included(3));
514        let interval2 = Interval::new(Excluded(0), Excluded(1));
515
516        assert!(!Interval::overlaps(&interval1, &interval2));
517    }
518
519    #[test]
520    fn interval_overlaps_6() {
521        let interval1 = Interval::new(Included(1), Included(3));
522        let interval2 = Interval::new(Excluded(4), Excluded(5));
523
524        assert!(!Interval::overlaps(&interval1, &interval2));
525    }
526
527    #[test]
528    fn interval_overlaps_7() {
529        let interval1 = Interval::new(Unbounded, Included(3));
530        let interval2 = Interval::new(Excluded(1), Excluded(5));
531
532        assert!(Interval::overlaps(&interval1, &interval2));
533    }
534
535    #[test]
536    fn interval_overlaps_8() {
537        let interval1 = Interval::new(Included(1), Included(3));
538        let interval2 = Interval::new(Excluded(4), Unbounded);
539
540        assert!(!Interval::overlaps(&interval1, &interval2));
541    }
542
543    #[test]
544    fn interval_get_overlap_1() {
545        let interval1 = Interval::new(Included(1), Included(3));
546        let interval2 = Interval::new(Included(2), Included(4));
547
548        assert!(
549            Interval::get_overlap(&interval1, &interval2).unwrap()
550                == Interval::new(Included(2), Included(3))
551        );
552    }
553
554    #[test]
555    fn interval_get_overlap_2() {
556        let interval1 = Interval::new(Included(1), Excluded(3));
557        let interval2 = Interval::new(Included(2), Included(4));
558
559        assert!(
560            Interval::get_overlap(&interval1, &interval2).unwrap()
561                == Interval::new(Included(2), Excluded(3))
562        );
563    }
564
565    #[test]
566    fn interval_get_overlap_3() {
567        let interval1 = Interval::new(Included(1), Excluded(3));
568        let interval2 = Interval::new(Included(2), Included(3));
569
570        assert!(
571            Interval::get_overlap(&interval1, &interval2).unwrap()
572                == Interval::new(Included(2), Excluded(3))
573        );
574    }
575
576    #[test]
577    fn interval_get_overlap_4() {
578        let interval1 = Interval::new(Excluded(1), Excluded(3));
579        let interval2 = Interval::new(Included(1), Included(4));
580
581        assert!(
582            Interval::get_overlap(&interval1, &interval2).unwrap()
583                == Interval::new(Excluded(1), Excluded(3))
584        );
585    }
586
587    #[test]
588    fn interval_get_overlap_5() {
589        let interval1 = Interval::new(Unbounded, Excluded(3));
590        let interval2 = Interval::new(Included(1), Included(2));
591
592        assert!(
593            Interval::get_overlap(&interval1, &interval2).unwrap()
594                == Interval::new(Included(1), Included(2))
595        );
596    }
597
598    #[test]
599    fn interval_get_overlap_6() {
600        let interval1 = Interval::new(Unbounded, Excluded(3));
601        let interval2 = Interval::new(Unbounded, Included(2));
602
603        assert!(
604            Interval::get_overlap(&interval1, &interval2).unwrap()
605                == Interval::new(Unbounded, Included(2))
606        );
607    }
608
609    #[test]
610    fn interval_get_overlap_7() {
611        let interval1 = Interval::new(Excluded(2), Excluded(3));
612        let interval2 = Interval::new(Unbounded, Included(3));
613
614        assert!(
615            Interval::get_overlap(&interval1, &interval2).unwrap()
616                == Interval::new(Excluded(2), Excluded(3))
617        );
618    }
619
620    #[test]
621    fn interval_get_overlap_8() {
622        let interval1 = Interval::new(Excluded(2), Unbounded);
623        let interval2 = Interval::new(Unbounded, Unbounded);
624
625        assert!(
626            Interval::get_overlap(&interval1, &interval2).unwrap()
627                == Interval::new(Excluded(2), Unbounded)
628        );
629    }
630
631    #[test]
632    fn interval_get_overlap_9() {
633        let interval1 = Interval::new(Excluded(2), Included(3));
634        let interval2 = Interval::new(Excluded(3), Included(4));
635
636        assert!(Interval::get_overlap(&interval1, &interval2).is_none());
637    }
638
639    #[test]
640    fn interval_get_overlap_10() {
641        let interval1 = Interval::new(Excluded(2), Included(3));
642        let interval2 = Interval::new(Included(4), Included(4));
643
644        assert!(Interval::get_overlap(&interval1, &interval2).is_none());
645    }
646
647    #[test]
648    fn interval_get_overlap_11() {
649        let interval1 = Interval::new(Included(3), Included(4));
650        let interval2 = Interval::new(Included(2), Included(3));
651
652        assert!(
653            Interval::get_overlap(&interval1, &interval2).unwrap()
654                == Interval::new(Included(3), Included(3))
655        );
656    }
657
658    #[test]
659    fn interval_contains_1() {
660        let interval1 = Interval::new(Included(1), Included(4));
661        let interval2 = Interval::new(Included(2), Included(3));
662
663        assert!(Interval::contains(&interval1, &interval2));
664    }
665
666    #[test]
667    fn interval_contains_2() {
668        let interval1 = Interval::new(Included(1), Included(4));
669        let interval2 = Interval::new(Excluded(1), Included(3));
670
671        assert!(Interval::contains(&interval1, &interval2));
672    }
673
674    #[test]
675    fn interval_contains_3() {
676        let interval1 = Interval::new(Included(1), Included(4));
677        let interval2 = Interval::new(Included(1), Included(3));
678
679        assert!(Interval::contains(&interval1, &interval2));
680    }
681
682    #[test]
683    fn interval_contains_4() {
684        let interval1 = Interval::new(Included(1), Included(4));
685        let interval2 = Interval::new(Included(2), Excluded(4));
686
687        assert!(Interval::contains(&interval1, &interval2));
688    }
689
690    #[test]
691    fn interval_contains_5() {
692        let interval1 = Interval::new(Included(1), Included(4));
693        let interval2 = Interval::new(Included(2), Included(4));
694
695        assert!(Interval::contains(&interval1, &interval2));
696    }
697
698    #[test]
699    fn interval_span_1() {
700        let interval1 = Interval::new(Included(2), Included(3));
701        let interval2 = Interval::new(Included(2), Excluded(3));
702        let interval3 = Interval::new(Excluded(2), Included(3));
703        let interval4 = Interval::new(Excluded(2), Excluded(3));
704
705        let interval5 = Interval::new(Unbounded, Excluded(3));
706        let interval6 = Interval::new(Excluded(2), Unbounded);
707        let interval7 = Interval::new(Unbounded, Excluded(3));
708        let interval8 = Interval::<usize>::new(Unbounded, Unbounded);
709
710        assert_eq!(interval1.span(), Some(2));
711        assert_eq!(interval2.span(), Some(1));
712        assert_eq!(interval3.span(), Some(1));
713        assert_eq!(interval4.span(), Some(0));
714        assert_eq!(interval5.span(), None);
715        assert_eq!(interval6.span(), None);
716        assert_eq!(interval7.span(), None);
717        assert_eq!(interval8.span(), None);
718    }
719}
store_interval_tree/interval.rs

store_interval_tree/
interval.rs
