competitive/num/
discrete_steps.rs

1use super::Bounded;
2use std::{
3    convert::TryFrom,
4    ops::{Bound, Range, RangeBounds, RangeInclusive},
5};
6
7pub trait DiscreteSteps<Delta>: Clone {
8    fn delta() -> Delta;
9    fn steps_between(start: &Self, end: &Self) -> Option<Delta>;
10    fn forward_checked(start: Self, delta: Delta) -> Option<Self>;
11    fn backward_checked(start: Self, delta: Delta) -> Option<Self>;
12    fn forward(start: Self, delta: Delta) -> Self {
13        Self::forward_checked(start, delta).expect("overflow in `DiscreteSteps::forward`")
14    }
15    fn backward(start: Self, delta: Delta) -> Self {
16        Self::backward_checked(start, delta).expect("overflow in `DiscreteSteps::backward`")
17    }
18    fn forward_delta_checked(start: Self) -> Option<Self> {
19        Self::forward_checked(start, Self::delta())
20    }
21    fn backward_delta_checked(start: Self) -> Option<Self> {
22        Self::backward_checked(start, Self::delta())
23    }
24    fn forward_delta(start: Self) -> Self {
25        Self::forward(start, Self::delta())
26    }
27    fn backward_delta(start: Self) -> Self {
28        Self::backward(start, Self::delta())
29    }
30}
31
32macro_rules! impl_discrete_steps_integer {
33    (@common $u_source:ident) => {
34        fn delta() -> $u_source {
35            1
36        }
37        fn forward(start: Self, delta: $u_source) -> Self {
38            assert!(Self::forward_checked(start, delta).is_some(), "attempt to add with overflow");
39            start.wrapping_add(delta as Self)
40        }
41        fn backward(start: Self, delta: $u_source) -> Self {
42            assert!(Self::backward_checked(start, delta).is_some(), "attempt to subtract with overflow");
43            start.wrapping_sub(delta as Self)
44        }
45    };
46    ($u_source:ident $i_source:ident; $($u_narrower:ident $i_narrower:ident),*; $($u_wider:ident $i_wider:ident),*) => {
47        $(
48            impl DiscreteSteps<$u_source> for $u_narrower {
49                impl_discrete_steps_integer!(@common $u_source);
50                fn steps_between(start: &Self, end: &Self) -> Option<$u_source> {
51                    if *start <= *end {
52                        Some((*end - *start) as $u_source)
53                    } else {
54                        None
55                    }
56                }
57                fn forward_checked(start: Self, delta: $u_source) -> Option<Self> {
58                    Self::try_from(delta).ok().and_then(|delta| start.checked_add(delta))
59                }
60                fn backward_checked(start: Self, delta: $u_source) -> Option<Self> {
61                    Self::try_from(delta).ok().and_then(|delta| start.checked_sub(delta))
62                }
63            }
64            impl DiscreteSteps<$u_source> for $i_narrower {
65                impl_discrete_steps_integer!(@common $u_source);
66                fn steps_between(start: &Self, end: &Self) -> Option<$u_source> {
67                    if *start <= *end {
68                        Some((*end as $i_source).wrapping_sub(*start as $i_source) as $u_source)
69                    } else {
70                        None
71                    }
72                }
73                fn forward_checked(start: Self, delta: $u_source) -> Option<Self> {
74                    $u_narrower::try_from(delta).ok().and_then(|delta| {
75                        let wrapped = start.wrapping_add(delta as Self);
76                        if wrapped >= start { Some(wrapped) } else { None }
77                    })
78                }
79                fn backward_checked(start: Self, delta: $u_source) -> Option<Self> {
80                    $u_narrower::try_from(delta).ok().and_then(|delta| {
81                        let wrapped = start.wrapping_sub(delta as Self);
82                        if wrapped <= start { Some(wrapped) } else { None }
83                    })
84                }
85            }
86        )*
87        $(
88            impl DiscreteSteps<$u_source> for $u_wider {
89                impl_discrete_steps_integer!(@common $u_source);
90                fn steps_between(start: &Self, end: &Self) -> Option<$u_source> {
91                    if *start <= *end {
92                        $u_source::try_from(*end - *start).ok()
93                    } else {
94                        None
95                    }
96                }
97                fn forward_checked(start: Self, delta: $u_source) -> Option<Self> {
98                    start.checked_add(delta as Self)
99                }
100                fn backward_checked(start: Self, delta: $u_source) -> Option<Self> {
101                    start.checked_sub(delta as Self)
102                }
103            }
104            impl DiscreteSteps<$u_source> for $i_wider {
105                impl_discrete_steps_integer!(@common $u_source);
106                fn steps_between(start: &Self, end: &Self) -> Option<$u_source> {
107                    if *start <= *end {
108                        end.checked_sub(*start).and_then(|result| $u_source::try_from(result).ok())
109                    } else {
110                        None
111                    }
112                }
113                fn forward_checked(start: Self, delta: $u_source) -> Option<Self> {
114                    start.checked_add(delta as Self)
115                }
116                fn backward_checked(start: Self, delta: $u_source) -> Option<Self> {
117                    start.checked_sub(delta as Self)
118                }
119            }
120        )*
121    };
122}
123impl_discrete_steps_integer!(u16 i16; u8 i8, u16 i16, usize isize; u32 i32, u64 i64, u128 i128);
124impl_discrete_steps_integer!(u32 i32; u8 i8, u16 i16, u32 i32, usize isize; u64 i64, u128 i128);
125impl_discrete_steps_integer!(u64 i64; u8 i8, u16 i16, u32 i32, u64 i64, usize isize; u128 i128);
126impl_discrete_steps_integer!(u128 i128; u8 i8, u16 i16, u32 i32, u64 i64, u128 i128, usize isize;);
127// #[cfg(target_pointer_width = "16")]
128// impl_discrete_steps_integer!(usize isize; u8 i8, u16 i16, usize isize; u32 i32, u64 i64, u128 i128);
129// #[cfg(target_pointer_width = "32")]
130// impl_discrete_steps_integer!(usize isize; u8 i8, u16 i16, u32 i32, usize isize; u64 i64, u128 i128);
131// #[cfg(target_pointer_width = "64")]
132impl_discrete_steps_integer!(usize isize; u8 i8, u16 i16, u32 i32, u64 i64, usize isize; u128 i128);
133
134pub trait RangeBoundsExt<T> {
135    fn start_bound_included_checked(&self) -> Option<T>;
136    fn start_bound_excluded_checked(&self) -> Option<T>;
137    fn end_bound_included_checked(&self) -> Option<T>;
138    fn end_bound_excluded_checked(&self) -> Option<T>;
139    fn start_bound_included(&self) -> T;
140    fn start_bound_excluded(&self) -> T;
141    fn end_bound_included(&self) -> T;
142    fn end_bound_excluded(&self) -> T;
143    fn start_bound_included_bounded(&self, lb: T) -> Option<T>
144    where
145        T: Ord;
146    fn start_bound_excluded_bounded(&self, lb: T) -> Option<T>
147    where
148        T: Ord;
149    fn end_bound_included_bounded(&self, ub: T) -> Option<T>
150    where
151        T: Ord;
152    fn end_bound_excluded_bounded(&self, ub: T) -> Option<T>
153    where
154        T: Ord;
155
156    fn to_range_checked(&self) -> Option<Range<T>> {
157        match (
158            self.start_bound_included_checked(),
159            self.end_bound_excluded_checked(),
160        ) {
161            (Some(start), Some(end)) => Some(start..end),
162            _ => None,
163        }
164    }
165    fn to_range(&self) -> Range<T> {
166        self.start_bound_included()..self.end_bound_excluded()
167    }
168    fn to_range_bounded(&self, min: T, max: T) -> Option<Range<T>>
169    where
170        T: Ord,
171    {
172        Some(self.start_bound_included_bounded(min)?..self.end_bound_excluded_bounded(max)?)
173    }
174    fn to_range_inclusive_checked(&self) -> Option<RangeInclusive<T>> {
175        match (
176            self.start_bound_included_checked(),
177            self.end_bound_included_checked(),
178        ) {
179            (Some(start), Some(end)) => Some(start..=end),
180            _ => None,
181        }
182    }
183    fn to_range_inclusive(&self) -> RangeInclusive<T> {
184        self.start_bound_included()..=self.end_bound_included()
185    }
186    fn to_range_inclusive_bounded(&self, min: T, max: T) -> Option<RangeInclusive<T>>
187    where
188        T: Ord,
189    {
190        Some(self.start_bound_included_bounded(min)?..=self.end_bound_included_bounded(max)?)
191    }
192}
193
194macro_rules! impl_range_bounds_ext {
195    ($($source:ident => $($target:ident)+);* $(;)?) => {
196        $($(
197            impl<R> RangeBoundsExt<$target> for R
198            where
199                R: RangeBounds<$target>,
200            {
201                fn start_bound_included_checked(&self) -> Option<$target> {
202                    match self.start_bound() {
203                        Bound::Included(x) => Some(*x),
204                        Bound::Excluded(x) => DiscreteSteps::<$source>::forward_delta_checked(*x),
205                        Bound::Unbounded => Some(Bounded::minimum()),
206                    }
207                }
208                fn start_bound_excluded_checked(&self) -> Option<$target> {
209                    match self.start_bound() {
210                        Bound::Included(x) => DiscreteSteps::<$source>::backward_delta_checked(*x),
211                        Bound::Excluded(x) => Some(*x),
212                        Bound::Unbounded => None,
213                    }
214                }
215                fn end_bound_included_checked(&self) -> Option<$target> {
216                    match self.end_bound() {
217                        Bound::Included(x) => Some(*x),
218                        Bound::Excluded(x) => DiscreteSteps::<$source>::backward_delta_checked(*x),
219                        Bound::Unbounded => Some(Bounded::maximum()),
220                    }
221                }
222                fn end_bound_excluded_checked(&self) -> Option<$target> {
223                    match self.end_bound() {
224                        Bound::Included(x) => DiscreteSteps::<$source>::forward_delta_checked(*x),
225                        Bound::Excluded(x) => Some(*x),
226                        Bound::Unbounded => None,
227                    }
228                }
229                fn start_bound_included(&self) -> $target {
230                    match self.start_bound() {
231                        Bound::Included(x) => *x,
232                        Bound::Excluded(x) => DiscreteSteps::<$source>::forward_delta(*x),
233                        Bound::Unbounded => Bounded::minimum(),
234                    }
235                }
236                fn start_bound_excluded(&self) -> $target {
237                    match self.start_bound() {
238                        Bound::Included(x) => DiscreteSteps::<$source>::backward_delta(*x),
239                        Bound::Excluded(x) => *x,
240                        Bound::Unbounded => DiscreteSteps::<$source>::backward_delta(Bounded::minimum()),
241                    }
242                }
243                fn end_bound_included(&self) -> $target {
244                    match self.end_bound() {
245                        Bound::Included(x) => *x,
246                        Bound::Excluded(x) => DiscreteSteps::<$source>::backward_delta(*x),
247                        Bound::Unbounded => Bounded::maximum(),
248                    }
249                }
250                fn end_bound_excluded(&self) -> $target {
251                    match self.end_bound() {
252                        Bound::Included(x) => DiscreteSteps::<$source>::forward_delta(*x),
253                        Bound::Excluded(x) => *x,
254                        Bound::Unbounded => DiscreteSteps::<$source>::forward_delta(Bounded::maximum()),
255                    }
256                }
257                fn start_bound_included_bounded(&self, lb: $target) -> Option<$target>
258                where
259                    $target: Ord
260                {
261                    match self.start_bound() {
262                        Bound::Included(x) => Some(*x).filter(|&x| lb <= x),
263                        Bound::Excluded(x) => DiscreteSteps::<$source>::forward_delta_checked(*x).filter(|&x| lb <= x),
264                        Bound::Unbounded => Some(lb),
265                    }
266                }
267                fn start_bound_excluded_bounded(&self, lb: $target) -> Option<$target>
268                where
269                    $target: Ord
270                {
271                    match self.start_bound() {
272                        Bound::Included(x) => DiscreteSteps::<$source>::backward_delta_checked(*x).filter(|&x| lb <= x),
273                        Bound::Excluded(x) => Some(*x).filter(|&x| lb <= x),
274                        Bound::Unbounded => Some(lb),
275                    }
276                }
277                fn end_bound_included_bounded(&self, ub: $target) -> Option<$target>
278                where
279                    $target: Ord
280                {
281                    match self.end_bound() {
282                        Bound::Included(x) => Some(*x).filter(|&x| x <= ub),
283                        Bound::Excluded(x) => DiscreteSteps::<$source>::backward_delta_checked(*x).filter(|&x| x <= ub),
284                        Bound::Unbounded => Some(ub),
285                    }
286                }
287                fn end_bound_excluded_bounded(&self, ub: $target) -> Option<$target>
288                where
289                    $target: Ord
290                {
291                    match self.end_bound() {
292                        Bound::Included(x) => DiscreteSteps::<$source>::forward_delta_checked(*x).filter(|&x| x <= ub),
293                        Bound::Excluded(x) => Some(*x).filter(|&x| x <= ub),
294                        Bound::Unbounded => Some(ub),
295                    }
296                }
297            }
298        )+)*
299    };
300}
301impl_range_bounds_ext!(
302    u16 => u8 i8 u16 i16;
303    u32 => u32 i32;
304    u64 => u64 i64;
305    u128 => u128 i128;
306    usize => isize usize;
307);
308
309#[cfg(test)]
310mod tests {
311    use super::*;
312
313    #[test]
314    fn test_start_bound_included() {
315        assert_eq!((2..5).start_bound_included(), 2);
316        assert_eq!((..5usize).start_bound_included(), 0);
317    }
318
319    #[test]
320    fn test_start_bound_excluded() {
321        assert_eq!((2..5).start_bound_excluded(), 1);
322        assert_eq!((..5usize).start_bound_excluded_checked(), None);
323    }
324
325    #[test]
326    fn test_end_bound_included() {
327        assert_eq!((2..5).end_bound_included(), 4);
328        assert_eq!((2usize..).end_bound_included(), !0usize);
329    }
330
331    #[test]
332    fn test_end_bound_excluded() {
333        assert_eq!((2..5).end_bound_excluded(), 5);
334        assert_eq!((2usize..).end_bound_excluded_checked(), None);
335    }
336
337    #[test]
338    fn test_to_range() {
339        assert_eq!((2..5).to_range(), 2..5);
340        assert_eq!((2..=5).to_range(), 2..6);
341        assert_eq!((..5usize).to_range(), 0..5);
342    }
343
344    #[test]
345    fn test_to_range_bounded() {
346        assert_eq!((3..6).to_range_bounded(2, 7), Some(3..6));
347        assert_eq!((2..7).to_range_bounded(2, 7), Some(2..7));
348        assert_eq!((2..8).to_range_bounded(2, 7), None);
349        assert_eq!((1..7).to_range_bounded(2, 7), None);
350        assert_eq!((..).to_range_bounded(2, 7), Some(2..7));
351        assert_eq!((2..=6).to_range_bounded(2, 7), Some(2..7));
352        assert_eq!((2..=7).to_range_bounded(2, 7), None);
353    }
354
355    #[test]
356    fn test_to_range_inclusive() {
357        assert_eq!((2..5).to_range_inclusive(), 2..=4);
358        assert_eq!((2..=5).to_range_inclusive(), 2..=5);
359        assert_eq!((..5usize).to_range_inclusive(), 0..=4);
360    }
361
362    #[test]
363    fn test_to_range_inclusive_bounded() {
364        assert_eq!((3..6).to_range_inclusive_bounded(2, 6), Some(3..=5));
365        assert_eq!((2..7).to_range_inclusive_bounded(2, 6), Some(2..=6));
366        assert_eq!((2..8).to_range_inclusive_bounded(2, 6), None);
367        assert_eq!((1..7).to_range_inclusive_bounded(2, 6), None);
368        assert_eq!((..).to_range_inclusive_bounded(2, 6), Some(2..=6));
369        assert_eq!((2..=6).to_range_inclusive_bounded(2, 6), Some(2..=6));
370        assert_eq!((2..=7).to_range_inclusive_bounded(2, 6), None);
371    }
372}
competitive/num/discrete_steps.rs

competitive/num/
discrete_steps.rs
