rudac/util/
interval.rs

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

rudac/util/
interval.rs
