litcheck_core/
range.rs

1use core::{
2    cmp::Ordering,
3    fmt,
4    ops::{Add, AddAssign, Bound, Index, IndexMut, RangeBounds, Sub},
5};
6
7pub trait NumericRangeBound:
8    Add<Output = Self> + AddAssign + Sub<Output = Self> + Copy + PartialEq + Ord
9{
10    const ZERO: Self;
11    const ONE: Self;
12
13    fn saturating_sub(self, rhs: Self) -> Self;
14}
15
16macro_rules! numeric_bound_impl {
17    ($type:ty) => {
18        impl NumericRangeBound for $type {
19            const ZERO: Self = 0;
20            const ONE: Self = 0;
21
22            #[inline(always)]
23            fn saturating_sub(self, rhs: Self) -> Self {
24                <$type>::saturating_sub(self, rhs)
25            }
26        }
27    };
28}
29
30numeric_bound_impl!(usize);
31numeric_bound_impl!(u8);
32numeric_bound_impl!(u16);
33numeric_bound_impl!(u32);
34numeric_bound_impl!(u64);
35
36pub struct Range<T> {
37    pub start: T,
38    pub end: T,
39}
40impl<T: fmt::Debug> fmt::Debug for Range<T> {
41    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
42        f.debug_struct("Range")
43            .field("start", &self.start)
44            .field("end", &self.end)
45            .finish()
46    }
47}
48impl<T: fmt::Display> fmt::Display for Range<T> {
49    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
50        write!(f, "{}..{}", &self.start, &self.end)
51    }
52}
53impl<T> core::ops::RangeBounds<T> for Range<T> {
54    #[inline]
55    fn start_bound(&self) -> Bound<&T> {
56        Bound::Included(&self.start)
57    }
58    #[inline]
59    fn end_bound(&self) -> Bound<&T> {
60        Bound::Excluded(&self.end)
61    }
62}
63impl<T: PartialOrd + fmt::Debug> Range<T> {
64    pub fn new(start: T, end: T) -> Self {
65        assert!(
66            start <= end,
67            "invalid range: start {:?} must not be larger than end {:?}",
68            start,
69            end,
70        );
71        Self { start, end }
72    }
73}
74impl<T: PartialOrd> Range<T> {
75    #[inline]
76    pub fn into_range(self) -> core::ops::Range<T> {
77        self.start..self.end
78    }
79
80    #[inline]
81    pub fn is_empty(&self) -> bool {
82        !matches!(self.start.partial_cmp(&self.end), Some(Ordering::Less))
83    }
84
85    #[inline]
86    pub fn contains<U>(&self, item: &U) -> bool
87    where
88        T: PartialOrd<U>,
89        U: PartialOrd<T> + ?Sized,
90    {
91        <Self as core::ops::RangeBounds<T>>::contains(self, item)
92    }
93}
94impl<T: NumericRangeBound> Range<T> {
95    #[inline(always)]
96    pub fn len(&self) -> T {
97        self.end - self.start
98    }
99
100    /// Shrink the length of this range by one element from the front, returning the first item in the range.
101    #[inline]
102    pub fn pop_front(&mut self) -> Option<T> {
103        let item = self.start;
104        let next = item + <T as NumericRangeBound>::ONE;
105        if next <= self.end {
106            self.start = next;
107            Some(item)
108        } else {
109            None
110        }
111    }
112
113    /// Shrink the length of this range by one element from the end, returning the last item in the range.
114    #[inline]
115    pub fn pop_back(&mut self) -> Option<T> {
116        if self.start == self.end {
117            None
118        } else {
119            let item = self.end.saturating_sub(<T as NumericRangeBound>::ONE);
120            self.end = item;
121            Some(item)
122        }
123    }
124
125    /// Shrink this range by advancing the start of the range `n` elements, i.e. `(start + n)..end`
126    ///
127    /// NOTE: This function will saturate to `self.end` to ensure the range remains valid.
128    #[inline]
129    pub fn shrink_front(&mut self, n: T) {
130        self.start = core::cmp::min(self.start + n, self.end);
131    }
132
133    /// Truncate this range such that it's length is `new_len`, i.e. `start..(start + new_len)`
134    ///
135    /// This effectively drops elements from the back of the range;
136    ///
137    /// NOTE: This function will panic if `new_len` is greater than the current length
138    #[inline]
139    pub fn truncate(&mut self, new_len: T) {
140        assert!(self.len() > new_len);
141        self.end = self.start + new_len;
142    }
143}
144impl<T: Copy> Copy for Range<T> {}
145impl<T: Clone> Clone for Range<T> {
146    fn clone(&self) -> Self {
147        Self {
148            start: self.start.clone(),
149            end: self.end.clone(),
150        }
151    }
152}
153impl<T: Eq> Eq for Range<T> {}
154impl<T: PartialEq> PartialEq for Range<T> {
155    fn eq(&self, other: &Self) -> bool {
156        self.start.eq(&other.start) && self.end.eq(&other.end)
157    }
158}
159impl<T: PartialOrd> PartialOrd for Range<T> {
160    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
161        self.start.partial_cmp(&other.start).and_then(|o| match o {
162            Ordering::Equal => self.end.partial_cmp(&other.end),
163            o => Some(o),
164        })
165    }
166}
167impl<T: Ord> Ord for Range<T> {
168    fn cmp(&self, other: &Self) -> Ordering {
169        self.start
170            .cmp(&other.start)
171            .then_with(|| self.end.cmp(&other.end))
172    }
173}
174impl<T: NumericRangeBound> From<core::ops::Range<T>> for Range<T> {
175    #[inline(always)]
176    fn from(range: core::ops::Range<T>) -> Self {
177        debug_assert!(
178            range.end >= range.start,
179            "invalid range: start must not pass end"
180        );
181        Self {
182            start: range.start,
183            end: range.end,
184        }
185    }
186}
187impl<T: NumericRangeBound> From<Range<T>> for core::ops::Range<T> {
188    #[inline(always)]
189    fn from(range: Range<T>) -> core::ops::Range<T> {
190        range.start..range.end
191    }
192}
193impl<T> Index<Range<usize>> for [T] {
194    type Output = [T];
195
196    #[inline(always)]
197    fn index(&self, idx: Range<usize>) -> &Self::Output {
198        <[T] as Index<core::ops::Range<usize>>>::index(self, idx.start..idx.end)
199    }
200}
201impl<T> IndexMut<Range<usize>> for [T] {
202    #[inline(always)]
203    fn index_mut(&mut self, idx: Range<usize>) -> &mut Self::Output {
204        <[T] as IndexMut<core::ops::Range<usize>>>::index_mut(self, idx.start..idx.end)
205    }
206}
207
208pub fn range_from_bounds<R: RangeBounds<usize>>(
209    range: R,
210    allowed: Range<usize>,
211) -> Result<Range<usize>, Range<usize>> {
212    let start = match range.start_bound() {
213        Bound::Included(&i) => i,
214        Bound::Excluded(&i) => i + 1,
215        Bound::Unbounded => allowed.start,
216    };
217    let end = match range.end_bound() {
218        Bound::Included(&i) => i + 1,
219        Bound::Excluded(&i) => i,
220        Bound::Unbounded => allowed.end,
221    };
222    if start < allowed.start || end > allowed.end {
223        Err(Range::new(start, end))
224    } else {
225        Ok(Range::new(start, end))
226    }
227}
228
229pub fn range_from_bounds_with_defaults<R: RangeBounds<usize>>(
230    range: R,
231    default_start: usize,
232    default_end: usize,
233) -> Range<usize> {
234    let start = match range.start_bound() {
235        Bound::Included(&i) => i,
236        Bound::Excluded(&i) => i + 1,
237        Bound::Unbounded => default_start,
238    };
239    let end = match range.end_bound() {
240        Bound::Included(&i) => i + 1,
241        Bound::Excluded(&i) => i,
242        Bound::Unbounded => default_end,
243    };
244    Range::new(start, end)
245}
litcheck_core/range.rs

litcheck_core/
range.rs
