range_utils/
lib.rs

1use std::ops::{Bound, RangeBounds, RangeInclusive, Sub};
2
3/// Basic operations (increase decrease) for numbers
4pub trait BasicNum {
5    const MIN_VALUE: Self;
6    const MAX_VALUE: Self;
7    fn dec(&self) -> Self;
8    fn inc(&self) -> Self;
9}
10macro_rules! impl_primitive_basic_num {
11    ($($t:ty),*) => {
12        $(
13            impl BasicNum for $t {
14                const MIN_VALUE: Self = Self::MIN;
15                const MAX_VALUE: Self = Self::MAX;
16                fn dec(&self) -> Self {
17                    self - 1
18                }
19                fn inc(&self) -> Self {
20                    self + 1
21                }
22            }
23        )*
24    };
25}
26// no f32/f64 since range useless on these
27impl_primitive_basic_num!(usize, isize, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128);
28
29/// Note that this implementation is inefficient if cloning is extremely expensive.
30pub trait RangeUtil<T: Ord + Clone + BasicNum>: Sized + Clone {
31    /// Start bound inclusive
32    fn starts_at(&self) -> T;
33    /// End bound inclusive
34    fn ends_at(&self) -> T;
35
36    /// The length of the range
37    fn len(&self) -> Option<T>
38    where
39        T: Sub<Output = T>,
40    {
41        (self.ends_at() >= self.starts_at()).then(|| self.ends_at().inc() - self.starts_at())
42    }
43    /// Using different name to prevent name clash, this does not require `Self: RangeBound`
44    fn includes(&self, x: &T) -> bool {
45        &self.starts_at() <= x && x <= &self.ends_at()
46    }
47    /// Whether two ranges intersect, e.g. `0..=3` and `1..=4` intersect while `0..=3` and `4..` don't
48    ///
49    /// This also works for "different ranges", e.g. `0..=3` and `2..` returns `true`
50    fn intersects(&self, other: &impl RangeUtil<T>) -> bool {
51        self.ends_at() >= other.starts_at() && self.starts_at() <= other.ends_at()
52    }
53    /// The intersection of two ranges, e.g. `0..=3` and `1..=4` is `1..=3`
54    ///
55    /// This also works for "different ranges", e.g. `0..=3` and `2..` is `1..=3`
56    fn intersection(&self, other: &impl RangeUtil<T>) -> Option<RangeInclusive<T>> {
57        self.intersects(other)
58            .then(|| self.starts_at().max(other.starts_at())..=self.ends_at().min(other.ends_at()))
59    }
60    /// The result of substracting `other` from `self`, e.g. `0..=3`\`1..=4` is `(0..=0, None)`
61    ///
62    /// If there are two sets representing the result, then the smaller range comes first. If only one range represents the result, then either result may be `None` (implementation detail, may change in the future).
63    ///
64    /// This also works for "different ranges", e.g. `0..=3`\`2..` is `0..=1`
65    fn setminus(
66        &self,
67        other: &impl RangeUtil<T>,
68    ) -> (Option<RangeInclusive<T>>, Option<RangeInclusive<T>>) {
69        let Some(other) = self.intersection(other) else {
70            return (
71                Some(self.starts_at().clone()..=self.ends_at().clone()),
72                None,
73            );
74        };
75        let (a, b) = (self.starts_at().clone(), self.ends_at().clone());
76        let (c, d) = (other.start().clone(), other.ends_at().clone());
77        (
78            (self.includes(&c))
79                .then(|| a..=c.dec())
80                .filter(|r| !r.is_empty()),
81            self.includes(&d)
82                .then(|| d.inc()..=b)
83                .filter(|r| !r.is_empty()),
84        )
85    }
86}
87impl<T: Ord + Clone + BasicNum, R: RangeBounds<T> + Clone> RangeUtil<T> for R {
88    fn starts_at(&self) -> T {
89        match self.start_bound() {
90            Bound::Excluded(x) => x.inc(),
91            Bound::Included(x) => x.clone(),
92            Bound::Unbounded => T::MIN_VALUE,
93        }
94    }
95    fn ends_at(&self) -> T {
96        match self.end_bound() {
97            Bound::Excluded(x) => x.dec(),
98            Bound::Included(x) => x.clone(),
99            Bound::Unbounded => T::MAX_VALUE,
100        }
101    }
102}
103
104#[cfg(test)]
105mod tests {
106    use std::ops::RangeFull;
107
108    use crate::RangeUtil;
109
110    #[test]
111    fn test_intersection_range_inclusive() {
112        assert_eq!((0..=3).intersection(&(1..=2)), Some(1..=2));
113        assert_eq!((0..=3).intersection(&(1..=30)), Some(1..=3));
114        assert_eq!((0..=3).intersection(&(-10..1)), Some(0..=0));
115        assert_eq!((0..=3).intersection(&(-10..=1)), Some(0..=1));
116        assert_eq!((0..=3).intersection(&(-10..=-1)), None);
117        assert_eq!((0..=3).intersection(&(4..=10)), None);
118    }
119
120    #[test]
121    fn test_difference_range_inclusive() {
122        assert_eq!((0..=3).setminus(&(4..=100)), (Some(0..=3), None));
123        assert_eq!((0..=3).setminus(&(-100..=-1)), (Some(0..=3), None));
124        assert_eq!((0..=3).setminus(&(1..=2)), (Some(0..=0), Some(3..=3)));
125        assert_eq!((0..=3).setminus(&(0..=2)), (None, Some(3..=3)));
126        assert_eq!((0..=3).setminus(&(1..=3)), (Some(0..=0), None));
127    }
128
129    #[test]
130    fn test_from_incl() {
131        assert_eq!((0..).starts_at(), 0);
132        assert_eq!((0..1).starts_at(), 0);
133        assert_eq!((0..=1).starts_at(), 0);
134        assert_eq!((..=10).starts_at(), 0usize);
135        assert_eq!((..=10).starts_at(), isize::MIN);
136        assert_eq!(RangeUtil::<usize>::starts_at(&RangeFull), 0);
137        assert_eq!(RangeUtil::<isize>::starts_at(&RangeFull), isize::MIN);
138    }
139
140    #[test]
141    fn test_to_incl() {
142        assert_eq!((0..).ends_at(), usize::MAX);
143        assert_eq!((0..1).ends_at(), 0);
144        assert_eq!((0..=1).ends_at(), 1);
145        assert_eq!((..=10).ends_at(), 10);
146        assert_eq!((10..).ends_at(), isize::MAX);
147        assert_eq!(RangeUtil::<usize>::ends_at(&RangeFull), usize::MAX);
148        assert_eq!(RangeUtil::<isize>::ends_at(&RangeFull), isize::MAX);
149    }
150}
range_utils/lib.rs

range_utils/
lib.rs
