ranges/
generic_range.rs

1use core::{
2    cmp::Ordering,
3    ops::{Bound, Range, RangeBounds, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive},
4};
5
6pub use into_iter::GenericIterator;
7
8use crate::Domain;
9
10/// Trait implementation of `Arbitrary` for use in fuzzers.
11#[cfg(feature = "arbitrary")]
12mod arbitrary;
13/// Method implementation to calculate if an object is contained in a range.
14mod contains;
15/// Method implementations to calculate difference of two ranges. Includes support for `Sub` operation trait.
16mod difference;
17/// Method implementation to calculate if a range is empty.
18/// Range inversion ending in an empty range is in the `invert` module.
19mod empty;
20/// Range formatting with several base implementations for all formatting traits.
21mod format;
22/// Trait implementation of `Hash`.
23mod hash;
24/// Method implementations for intersecting two ranges. Includes support for `BitAnd` operation trait.
25mod intersect;
26/// Method implementations for making a discrete start-bound range into an `Iterator`.
27mod into_iter;
28/// Method implementation, related functions and structs to invert a range.
29pub(crate) mod invert;
30/// Trait implementation of `Arbitrary` for use in proptest.
31#[cfg(any(feature = "proptest", test))]
32mod proptest;
33/// Method implementation and related functions to calculate relation of ranges.
34pub(crate) mod relation;
35/// Method implementations for singleton construction and checking.
36mod singleton;
37/// Method implementations to calculate symmetric difference of two ranges. Includes support for `BitXor` operation trait.
38mod symmetric_difference;
39/// Method implementations to calculate union of two ranges. Includes support for `BitOr` operation trait.
40mod union;
41
42/// A generic analog to core/std ranges.
43///
44/// Because this type allows more range types, it comes with the cost of a few guarantees that need
45/// to be uphold.
46///
47/// First of all, `start` is always less than or equal to `end`.
48/// Secondly, both bounds are in the `Domain` that is implemented for `T`.
49/// In case the constructor encounters a value outside of the domain, the value is clamped to the
50/// full domain range.
51///
52/// # Note
53/// The notation of `(-inf` and `+inf)` is used as an equivalent to the domain minimum and maximum,
54/// even if the implementing domain may not be unbound or excluding in either direction.
55#[derive(Copy, Clone, Debug)]
56pub struct GenericRange<T> {
57    /// Start of range. It is assumed to be smaller or equal to `end`.
58    pub(crate) start: Bound<T>,
59    /// End of range. It is assumed to be bigger or equal to `start`.
60    pub(crate) end: Bound<T>,
61}
62
63/// Constructors and relevant comparison methods.
64impl<T: Domain> GenericRange<T> {
65    /// Creates a new [`GenericRange`](#) using the domain minimum and maximum as start and end.
66    ///
67    /// # core/std equivalent
68    /// [`RangeFull`](https://doc.rust-lang.org/core/ops/struct.RangeFull.html) or `..`.
69    ///
70    /// # Interval notation
71    /// `(-inf, +inf)`
72    #[must_use]
73    pub fn full() -> Self {
74        Self {
75            start: T::minimum(),
76            end: T::maximum(),
77        }
78    }
79
80    /// Returns true if the start is the domain minimum and the end is the domain maximum.
81    #[must_use]
82    pub fn is_full(&self) -> bool {
83        *self == Self::full()
84    }
85
86    /// Returns true if the range start is open/excluded.
87    #[must_use]
88    pub const fn is_left_open(&self) -> bool {
89        match self.start {
90            Bound::Excluded(_) => true,
91            Bound::Included(_) | Bound::Unbounded => false,
92        }
93    }
94
95    /// Returns true if the range start is closed/included.
96    #[must_use]
97    pub const fn is_left_closed(&self) -> bool {
98        match self.start {
99            Bound::Included(_) => true,
100            Bound::Excluded(_) | Bound::Unbounded => false,
101        }
102    }
103
104    /// Returns true if the range start is unbounded.
105    #[must_use]
106    pub const fn is_left_unbounded(&self) -> bool {
107        match self.start {
108            Bound::Unbounded => true,
109            Bound::Excluded(_) | Bound::Included(_) => false,
110        }
111    }
112
113    /// Returns true if the range end is open/excluded.
114    #[must_use]
115    pub const fn is_right_open(&self) -> bool {
116        match self.end {
117            Bound::Excluded(_) => true,
118            Bound::Included(_) | Bound::Unbounded => false,
119        }
120    }
121
122    /// Returns true if the range end is closed/included.
123    #[must_use]
124    pub const fn is_right_closed(&self) -> bool {
125        match self.end {
126            Bound::Included(_) => true,
127            Bound::Excluded(_) | Bound::Unbounded => false,
128        }
129    }
130
131    /// Returns true if the range end is unbounded.
132    #[must_use]
133    pub const fn is_right_unbounded(&self) -> bool {
134        match self.end {
135            Bound::Unbounded => true,
136            Bound::Excluded(_) | Bound::Included(_) => false,
137        }
138    }
139
140    //
141
142    /// Convenience method calling [`new_left_open_right_unbounded`](#method.new_left_open_right_unbounded).
143    #[must_use]
144    pub fn new_greater_than(start: T) -> Self {
145        Self::new_left_open_right_unbounded(start)
146    }
147
148    /// Creates a new [`GenericRange`](#) with an open/excluded start and an unbound end.
149    /// Convenience method equivalent is [`new_greater_than`](#method.new_greater_than).
150    ///
151    /// # core/std equivalent
152    /// There is no equivalent because open/excluded starts are not representable.
153    ///
154    /// # Interval notation
155    /// `(start, +inf)`
156    #[must_use]
157    pub fn new_left_open_right_unbounded(start: T) -> Self {
158        Self::new_with_bounds(Bound::Excluded(start), Bound::Unbounded)
159    }
160
161    /// Returns true if the range start is open/excluded and the end is unbounded.
162    #[must_use]
163    pub const fn is_left_open_right_unbounded(&self) -> bool {
164        self.is_left_open() && self.is_right_unbounded()
165    }
166
167    //
168
169    /// Convenience method calling [`new_left_closed_right_unbounded`](#method.new_left_closed_right_unbounded).
170    #[must_use]
171    pub fn new_at_least(start: T) -> Self {
172        Self::new_left_closed_right_unbounded(start)
173    }
174
175    /// Creates a new [`GenericRange`](#) with a closed/included start and an unbound end.
176    /// Convenience method equivalent is [`new_at_least`](#method.new_at_least).
177    ///
178    /// # core/std equivalent
179    /// [`RangeFrom`](https://doc.rust-lang.org/core/ops/struct.RangeFrom.html) or `start..`.
180    ///
181    /// # Interval notation
182    /// `[start, +inf)`
183    #[must_use]
184    pub fn new_left_closed_right_unbounded(start: T) -> Self {
185        Self::new_with_bounds(Bound::Included(start), Bound::Unbounded)
186    }
187
188    /// Returns true if the range start is closed/included and the end is unbounded.
189    #[must_use]
190    pub const fn is_left_closed_right_unbounded(&self) -> bool {
191        self.is_left_closed() && self.is_right_unbounded()
192    }
193
194    //
195
196    /// Convenience method calling [`new_left_unbounded_right_open`](#method.new_left_unbounded_right_open).
197    #[must_use]
198    pub fn new_less_than(end: T) -> Self {
199        Self::new_left_unbounded_right_open(end)
200    }
201
202    /// Creates a new [`GenericRange`](#) with an unbounded start and an open/excluded end.
203    /// Convenience method equivalent is [`new_less_than`](#method.new_less_than).
204    ///
205    /// # core/std equivalent
206    /// [`RangeTo`](https://doc.rust-lang.org/core/ops/struct.RangeTo.html) or `..end`.
207    ///
208    /// # Interval notation
209    /// `(-inf, end)`
210    #[must_use]
211    pub fn new_left_unbounded_right_open(end: T) -> Self {
212        Self::new_with_bounds(Bound::Unbounded, Bound::Excluded(end))
213    }
214
215    /// Returns true if the range start is unbounded and the end is open/excluded.
216    #[must_use]
217    pub const fn is_left_unbounded_right_open(&self) -> bool {
218        self.is_left_unbounded() && self.is_right_open()
219    }
220
221    //
222
223    /// Convenience method calling [`new_left_unbounded_right_closed`](#method.new_left_unbounded_right_closed).
224    #[must_use]
225    pub fn new_at_most(end: T) -> Self {
226        Self::new_left_unbounded_right_closed(end)
227    }
228
229    /// Creates a new [`GenericRange`](#) with an unbounded start and a closed/included end.
230    /// Convenience method equivalent is [`new_at_most`](#method.new_at_most).
231    ///
232    /// # core/std equivalent
233    /// [`RangeToInclusive`](https://doc.rust-lang.org/core/ops/struct.RangeToInclusive.html) or `..=end`.
234    ///
235    /// # Interval notation
236    /// `(-inf, end]`
237    #[must_use]
238    pub fn new_left_unbounded_right_closed(end: T) -> Self {
239        Self::new_with_bounds(Bound::Unbounded, Bound::Included(end))
240    }
241
242    /// Returns true if the range start is unbounded and the end is closed/included.
243    #[must_use]
244    pub const fn is_left_unbounded_right_closed(&self) -> bool {
245        self.is_left_unbounded() && self.is_right_closed()
246    }
247
248    //
249
250    /// Convenience method calling [`new_left_open_right_open`](#method.new_left_open_right_open).
251    #[must_use]
252    pub fn new_open(start: T, end: T) -> Self {
253        Self::new_left_open_right_open(start, end)
254    }
255
256    /// Creates a new [`GenericRange`](#) with an open/excluded start and end.
257    /// Convenience method equivalent is [`new_open`](#method.new_open).
258    ///
259    /// # core/std equivalent
260    /// There is no equivalent because open/excluded starts are not representable.
261    ///
262    /// # Interval notation
263    /// `(start, end)`
264    #[must_use]
265    pub fn new_left_open_right_open(start: T, end: T) -> Self {
266        Self::new_with_bounds(Bound::Excluded(start), Bound::Excluded(end))
267    }
268
269    /// Returns true if the range start and end are open/excluded.
270    #[must_use]
271    pub const fn is_left_open_right_open(&self) -> bool {
272        self.is_left_open() && self.is_right_open()
273    }
274
275    //
276
277    /// Convenience method calling [`new_left_closed_right_closed`](#method.new_left_closed_right_closed).
278    #[must_use]
279    pub fn new_closed(start: T, end: T) -> Self {
280        Self::new_left_closed_right_closed(start, end)
281    }
282
283    /// Creates a new [`GenericRange`](#) with a closed/included start and end.
284    /// Convenience method equivalent is [`new_closed`](#method.new_closed).
285    ///
286    /// # core/std equivalent
287    /// [`RangeInclusive`](https://doc.rust-lang.org/core/ops/struct.RangeInclusive.html) or `start..=end`.
288    ///
289    /// # Interval notation
290    /// `[start, end]`
291    #[must_use]
292    pub fn new_left_closed_right_closed(start: T, end: T) -> Self {
293        Self::new_with_bounds(Bound::Included(start), Bound::Included(end))
294    }
295
296    /// Returns true if the range start and end are closed/included.
297    #[must_use]
298    pub const fn is_left_closed_right_closed(&self) -> bool {
299        self.is_left_closed() && self.is_right_closed()
300    }
301
302    //
303
304    /// Convenience method calling [`new_left_closed_right_open`](#method.new_left_closed_right_open).
305    #[must_use]
306    pub fn new_closed_open(start: T, end: T) -> Self {
307        Self::new_left_closed_right_open(start, end)
308    }
309
310    /// Creates a new [`GenericRange`](#) with a closed/included start and an open/excluded end.
311    /// Convenience method equivalent is [`new_closed_open`](#method.new_closed_open).
312    ///
313    /// # core/std equivalent
314    /// [`Range`](https://doc.rust-lang.org/core/ops/struct.Range.html) or `start..end`.
315    ///
316    /// # Interval notation
317    /// `[start, end)`
318    #[must_use]
319    pub fn new_left_closed_right_open(start: T, end: T) -> Self {
320        Self::new_with_bounds(Bound::Included(start), Bound::Excluded(end))
321    }
322
323    /// Returns true if the range start is closed/included and the end is open/excluded.
324    #[must_use]
325    pub const fn is_left_closed_right_open(&self) -> bool {
326        self.is_left_closed() && self.is_right_open()
327    }
328
329    //
330
331    /// Convenience method calling [`new_left_open_right_closed`](#method.new_left_open_right_closed).
332    #[must_use]
333    pub fn new_open_closed(start: T, end: T) -> Self {
334        Self::new_left_open_right_closed(start, end)
335    }
336
337    /// Creates a new [`GenericRange`](#) with a closed/included start and an open/excluded end.
338    /// Convenience method equivalent is [`new_open_closed`](#method.new_open_closed).
339    ///
340    /// # core/std equivalent
341    /// There is no equivalent because open/excluded starts are not representable.
342    ///
343    /// # Interval notation
344    /// `(start, end]`
345    #[must_use]
346    pub fn new_left_open_right_closed(start: T, end: T) -> Self {
347        Self::new_with_bounds(Bound::Excluded(start), Bound::Included(end))
348    }
349
350    /// Returns true if the range start is open/excluded and the end is closed/included.
351    #[must_use]
352    pub const fn is_left_open_right_closed(&self) -> bool {
353        self.is_left_open() && self.is_right_closed()
354    }
355
356    //
357
358    /// Custom range from [`Bound`s](https://doc.rust-lang.org/core/ops/enum.Bound.html).
359    ///
360    /// # Panics
361    /// It is asserted that `start <= end`.
362    #[must_use]
363    #[allow(clippy::panic, clippy::shadow_reuse)]
364    pub fn new_with_bounds(start: Bound<T>, end: Bound<T>) -> Self {
365        let domain_range = Self::full();
366
367        let start = match Self::cmp_start_start(bound_owned_to_ref(&start), domain_range.start_bound()) {
368            Ordering::Less | Ordering::Equal => T::minimum(),
369            Ordering::Greater => start,
370        };
371
372        let end = match Self::cmp_end_end(bound_owned_to_ref(&end), domain_range.end_bound()) {
373            Ordering::Less | Ordering::Equal => end,
374            Ordering::Greater => T::maximum(),
375        };
376
377        match (bound_owned_to_ref(&start), bound_owned_to_ref(&end)) {
378            (Bound::Unbounded, _) | (_, Bound::Unbounded) => (),
379            (Bound::Included(start) | Bound::Excluded(start), Bound::Included(end) | Bound::Excluded(end)) => {
380                assert!(start <= end, "range start has to be less or equal to the end");
381            }
382        }
383
384        Self { start, end }
385    }
386}
387
388impl<T: Domain> RangeBounds<T> for GenericRange<T> {
389    #[must_use]
390    fn start_bound(&self) -> Bound<&T> {
391        bound_owned_to_ref(&self.start)
392    }
393
394    #[must_use]
395    fn end_bound(&self) -> Bound<&T> {
396        bound_owned_to_ref(&self.end)
397    }
398
399    fn contains<U>(&self, item: &U) -> bool
400    where
401        T: PartialOrd<U>,
402        U: ?Sized + PartialOrd<T>,
403    {
404        Self::generic_start_end_contains(&self.start, &self.end, item)
405    }
406}
407
408/// Converts a reference of a bound with owned data to a owned Bound with referenced data.
409const fn bound_owned_to_ref<T>(bound: &Bound<T>) -> Bound<&T> {
410    match *bound {
411        Bound::Included(ref end) => Bound::Included(end),
412        Bound::Excluded(ref end) => Bound::Excluded(end),
413        Bound::Unbounded => Bound::Unbounded,
414    }
415}
416
417impl<T: Domain> PartialEq for GenericRange<T> {
418    fn eq(&self, other: &Self) -> bool {
419        self.is_equal(other)
420    }
421}
422
423impl<T: Domain> Eq for GenericRange<T> {}
424
425/// Converts the `Range` using [`Self::closed_open(range.start, range.end)`](#method.closed_open).
426impl<T: Domain> From<Range<T>> for GenericRange<T> {
427    #[must_use]
428    fn from(range: Range<T>) -> Self {
429        Self::new_closed_open(range.start, range.end)
430    }
431}
432
433/// Converts the `RangeFrom` using [`Self::at_least(range.start)`](#method.at_least).
434impl<T: Domain> From<RangeFrom<T>> for GenericRange<T> {
435    #[must_use]
436    fn from(range: RangeFrom<T>) -> Self {
437        Self::new_at_least(range.start)
438    }
439}
440
441/// Converts the `RangeFull` using [`Self::full()`](#method.full).
442impl<T: Domain> From<RangeFull> for GenericRange<T> {
443    #[must_use]
444    fn from(_range: RangeFull) -> Self {
445        Self::full()
446    }
447}
448
449/// Converts the `RangeInclusive` using [`Self::closed(start, end)`](#method.closed).
450impl<T: Domain> From<RangeInclusive<T>> for GenericRange<T> {
451    #[must_use]
452    fn from(range: RangeInclusive<T>) -> Self {
453        let (start, end) = range.into_inner();
454        Self::new_closed(start, end)
455    }
456}
457
458/// Converts the `RangeTo` using [`Self::less_than(range.end)`](#method.less_than).
459impl<T: Domain> From<RangeTo<T>> for GenericRange<T> {
460    #[must_use]
461    fn from(range: RangeTo<T>) -> Self {
462        Self::new_less_than(range.end)
463    }
464}
465
466/// Converts the `RangeToInclusive` using [`Self::at_most(range.end)`](#method.at_most).
467impl<T: Domain> From<RangeToInclusive<T>> for GenericRange<T> {
468    #[must_use]
469    fn from(range: RangeToInclusive<T>) -> Self {
470        Self::new_at_most(range.end)
471    }
472}
473
474/// Converts the tuple using [`Self::with_bounds(tuple.0, tuple.1)`](#method.with_bounds).
475impl<T: Domain> From<(Bound<T>, Bound<T>)> for GenericRange<T> {
476    #[must_use]
477    fn from(range: (Bound<T>, Bound<T>)) -> Self {
478        Self::new_with_bounds(range.0, range.1)
479    }
480}
481
482/// Result of a unary or binary operation.
483#[allow(clippy::missing_inline_in_public_items, clippy::exhaustive_enums)]
484#[derive(Debug, Clone, Copy, Eq, PartialEq)]
485#[must_use = "a range operation might not always return another range and should be handled"]
486pub enum OperationResult<T: Domain> {
487    /// The operation resulted in an empty range.
488    Empty,
489    /// The operation resulted in a single range.
490    Single(GenericRange<T>),
491    /// The operation resulted in two ranges.
492    Double(GenericRange<T>, GenericRange<T>),
493}
494
495#[cfg(test)]
496pub(crate) mod tests {
497    use core::{
498        cmp::Ordering,
499        iter::once,
500        ops::{Bound, RangeBounds},
501    };
502
503    use proptest::prelude::*;
504
505    use crate::GenericRange;
506
507    #[test]
508    #[allow(clippy::shadow_unrelated)]
509    fn from_core_ranges() {
510        // [x, y) - x..y
511        let generic = GenericRange::from(1..5);
512        assert_eq!(generic.start_bound(), Bound::Included(&1));
513        assert_eq!(generic.end_bound(), Bound::Excluded(&5));
514
515        // [x, y] - x..=y
516        let generic = GenericRange::from(6..=10);
517        assert_eq!(generic.start_bound(), Bound::Included(&6));
518        assert_eq!(generic.end_bound(), Bound::Included(&10));
519
520        // [x, +inf) - x..
521        let generic = GenericRange::from(12..);
522        assert_eq!(generic.start_bound(), Bound::Included(&12));
523        assert_eq!(generic.end_bound(), Bound::Included(&2_147_483_647));
524
525        // (-inf, y) - ..y
526        let generic = GenericRange::from(..15);
527        assert_eq!(generic.start_bound(), Bound::Included(&-2_147_483_648));
528        assert_eq!(generic.end_bound(), Bound::Excluded(&15));
529
530        // (-inf, y] - ..=y
531        let generic = GenericRange::from(..=20);
532        assert_eq!(generic.start_bound(), Bound::Included(&-2_147_483_648));
533        assert_eq!(generic.end_bound(), Bound::Included(&20));
534
535        // (-inf, +inf) - ..
536        let generic: GenericRange<usize> = GenericRange::from(..);
537        assert_eq!(generic.start_bound(), Bound::Included(&0));
538        assert_eq!(generic.end_bound(), Bound::Included(&18_446_744_073_709_551_615));
539
540        // (x, y) - has no Rust equivalent
541        let generic = GenericRange::from((Bound::Excluded(30), Bound::Excluded(42)));
542        assert_eq!(generic.start_bound(), Bound::Excluded(&30));
543        assert_eq!(generic.end_bound(), Bound::Excluded(&42));
544
545        // (x, y] - has no Rust equivalent
546        let generic = GenericRange::from((Bound::Excluded(45), Bound::Included(50)));
547        assert_eq!(generic.start_bound(), Bound::Excluded(&45));
548        assert_eq!(generic.end_bound(), Bound::Included(&50));
549
550        // (x, +inf) - has no Rust equivalent
551        let generic = GenericRange::from((Bound::Excluded(55), Bound::Unbounded));
552        assert_eq!(generic.start_bound(), Bound::Excluded(&55));
553        assert_eq!(generic.end_bound(), Bound::Included(&2_147_483_647));
554    }
555
556    #[allow(clippy::single_call_fn, clippy::absolute_paths)]
557    pub(crate) fn exhaustive_discrete_range() -> impl Iterator<Item = GenericRange<Ordering>> {
558        exhaustive_discrete_bound()
559            .flat_map(|x| core::iter::repeat(x).zip(exhaustive_discrete_bound()))
560            .filter_map(|(start, end)| match (start, end) {
561                (Bound::Unbounded, _) | (_, Bound::Unbounded) => Some(GenericRange::new_with_bounds(start, end)),
562                (Bound::Included(s) | Bound::Excluded(s), Bound::Included(e) | Bound::Excluded(e)) => {
563                    (s <= e).then(|| GenericRange::new_with_bounds(start, end))
564                }
565            })
566    }
567
568    fn exhaustive_discrete_bound() -> impl Iterator<Item = Bound<Ordering>> {
569        let unbound_iter = once(Bound::Unbounded);
570        let included_iter = [Ordering::Less, Ordering::Equal, Ordering::Greater]
571            .iter()
572            .copied()
573            .map(Bound::Included);
574        let excluded_iter = [Ordering::Less, Ordering::Equal, Ordering::Greater]
575            .iter()
576            .copied()
577            .map(Bound::Excluded);
578
579        unbound_iter.chain(included_iter).chain(excluded_iter)
580    }
581
582    #[test]
583    fn check_exhaustive_bound() {
584        assert_eq!(exhaustive_discrete_bound().count(), 7);
585    }
586
587    #[test]
588    fn check_exhaustive_range() {
589        assert_eq!(exhaustive_discrete_range().count(), 37);
590    }
591
592    prop_compose! {
593        pub fn random_discrete_range()((start, end) in any::<usize>().prop_flat_map(|end| (0..=end, Just(end))), range_type in 0..=7_usize) -> GenericRange<usize> {
594            match range_type {
595                0 => GenericRange::new_open(start, end),
596                1 => GenericRange::new_closed(start, end),
597                2 => GenericRange::new_open_closed(start, end),
598                3 => GenericRange::new_closed_open(start, end),
599                4 => GenericRange::new_greater_than(start),
600                5 => GenericRange::new_at_least(start),
601                6 => GenericRange::new_less_than(end),
602                7 => GenericRange::new_at_most(end),
603                _ => unreachable!(),
604            }
605        }
606    }
607}
ranges/generic_range.rs

ranges/
generic_range.rs
