willow_data_model/groupings/
willow_range.rs

1use core::cmp::Ordering;
2use core::fmt::{self, Debug, Formatter};
3use core::hash::Hash;
4use core::ops::{Bound, RangeBounds};
5
6#[cfg(feature = "dev")]
7use arbitrary::{Arbitrary, size_hint};
8
9use order_theory::{
10    GreatestElement, LeastElement, SuccessorExceptForGreatest,
11};
12
13use crate::prelude::EmptyGrouping;
14
15/// A non-empty [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) with an inclusive start value and a strictly-greater exclusive end value.
16///
17/// It includes all values that are greater than or equal to the start value *and* strictly less than the end value.
18///
19/// ```
20/// use willow_data_model::prelude::*;
21///
22/// let r = ClosedRange::new(2, 7);
23/// assert_eq!(r.start(), &2);
24/// assert_eq!(r.end(), &7);
25///
26/// assert!(ClosedRange::try_new(7, 2).is_err());
27/// assert!(ClosedRange::try_new(2, 2).is_err());
28/// ```
29#[derive(Clone, Copy, PartialEq, Eq, Hash)]
30#[repr(C)]
31pub struct ClosedRange<T> {
32    start: T,
33    end: T,
34}
35
36impl<T: Debug> Debug for ClosedRange<T> {
37    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
38        self.start.fmt(f)?;
39        write!(f, "..")?;
40        self.end.fmt(f)?;
41        Ok(())
42    }
43}
44
45impl<T> PartialOrd for ClosedRange<T>
46where
47    T: PartialOrd,
48{
49    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
50        match (
51            self.start.partial_cmp(&other.start)?,
52            self.end.partial_cmp(&other.end)?,
53        ) {
54            (Ordering::Equal, Ordering::Equal) => Some(Ordering::Equal),
55            (cmp_start, cmp_end) => {
56                if cmp_start.is_le() && cmp_end.is_ge() {
57                    Some(Ordering::Greater)
58                } else if cmp_start.is_ge() && cmp_end.is_le() {
59                    Some(Ordering::Less)
60                } else {
61                    None
62                }
63            }
64        }
65    }
66}
67
68impl<T> ClosedRange<T>
69where
70    T: PartialOrd,
71{
72    /// Creates a new closed range, or an [`EmptyGrouping`] error if `start >= end`.
73    ///
74    /// ```
75    /// use willow_data_model::prelude::*;
76    ///
77    /// assert!(ClosedRange::try_new(2, 7).is_ok());
78    /// assert!(ClosedRange::try_new(7, 2).is_err());
79    /// assert!(ClosedRange::try_new(2, 2).is_err());
80    /// ```
81    pub fn try_new(start: T, end: T) -> Result<Self, EmptyGrouping> {
82        let ret = Self { start, end };
83
84        if ret.is_empty() {
85            Err(EmptyGrouping)
86        } else {
87            Ok(ret)
88        }
89    }
90
91    /// Creates a new closed range, panicking if it would be empty.
92    ///
93    /// ```
94    /// use willow_data_model::prelude::*;
95    ///
96    /// let yay = ClosedRange::new(2, 7);
97    /// ```
98    ///
99    /// ```should_panic
100    /// use willow_data_model::prelude::*;
101    ///
102    /// let nope = ClosedRange::new(7, 2);
103    /// ```
104    pub fn new(start: T, end: T) -> Self {
105        Self::try_new(start, end).unwrap()
106    }
107
108    /// Returns whether the given value is included in `self`.
109    ///
110    /// ```
111    /// use willow_data_model::prelude::*;
112    ///
113    /// let r = ClosedRange::new(2, 7);
114    /// assert!(r.includes_value(&2));
115    /// assert!(!r.includes_value(&1));
116    /// assert!(!r.includes_value(&7));
117    /// ```
118    pub fn includes_value(&self, t: &T) -> bool {
119        self.start <= *t && self.end > *t
120    }
121
122    /// Returns whether the given value is included in `self` and `other`.
123    ///
124    /// ```
125    /// use willow_data_model::prelude::*;
126    ///
127    /// let r1 = ClosedRange::new(2, 7);
128    /// let r2 = ClosedRange::new(5, 9);
129    /// assert!(r1.includes_value_in_intersection(&r2, &5));
130    /// assert!(!r1.includes_value_in_intersection(&r2, &2));
131    /// assert!(!r1.includes_value_in_intersection(&r2, &7));
132    /// assert!(!r1.includes_value_in_intersection(&r2, &22));
133    /// ```
134    pub fn includes_value_in_intersection(&self, other: &Self, t: &T) -> bool {
135        self.includes_value(t) && other.includes_value(t)
136    }
137
138    /// Returns whether the given closed range is included in `self`.
139    ///
140    /// ```
141    /// use willow_data_model::prelude::*;
142    ///
143    /// let r = ClosedRange::new(2, 7);
144    /// assert!(r.includes_closed_range(&ClosedRange::new(3, 6)));
145    /// assert!(r.includes_closed_range(&ClosedRange::new(2, 5)));
146    /// assert!(r.includes_closed_range(&ClosedRange::new(3, 7)));
147    /// assert!(r.includes_closed_range(&ClosedRange::new(2, 7)));
148    /// assert!(!r.includes_closed_range(&ClosedRange::new(1, 7)));
149    /// assert!(!r.includes_closed_range(&ClosedRange::new(2, 8)));
150    /// assert!(!r.includes_closed_range(&ClosedRange::new(9, 14)));
151    /// ```
152    pub fn includes_closed_range(&self, other: &Self) -> bool {
153        self.start <= other.start && self.end >= other.end
154    }
155
156    /// Returns whether the given closed range is strictly included in `self`.
157    ///
158    /// ```
159    /// use willow_data_model::prelude::*;
160    ///
161    /// let r = ClosedRange::new(2, 7);
162    /// assert!(r.strictly_includes_closed_range(&ClosedRange::new(2, 6)));
163    /// assert!(r.strictly_includes_closed_range(&ClosedRange::new(3, 7)));
164    /// assert!(r.strictly_includes_closed_range(&ClosedRange::new(3, 6)));
165    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(2, 7)));
166    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(1, 7)));
167    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(2, 8)));
168    /// assert!(!r.strictly_includes_closed_range(&ClosedRange::new(9, 14)));
169    /// ```
170    pub fn strictly_includes_closed_range(&self, other: &Self) -> bool {
171        self != other && self.includes_closed_range(other)
172    }
173
174    // Private because we never expose empty ranges.
175    fn is_empty(&self) -> bool {
176        self.start >= self.end
177    }
178}
179
180impl<T> ClosedRange<T>
181where
182    T: PartialOrd + Clone,
183{
184    /// Returns the intersection between `self` and `other`, or an [`EmptyGrouping`] error if it would be empty.
185    ///
186    /// assert_eq!(
187    ///     ClosedRange::new(2, 7).intersection_closed_range(ClosedRange::new(5, 9)),
188    ///     Ok(ClosedRange::new(5, 7)),
189    /// );
190    /// assert!(
191    ///     ClosedRange::new(2, 5).intersection_closed_range(ClosedRange::new(7, 9)).is_error(),
192    /// );
193    pub fn intersection_closed_range(&self, other: &Self) -> Result<Self, EmptyGrouping> {
194        let start = match self.start.partial_cmp(other.start()) {
195            None => return Err(EmptyGrouping),
196            Some(Ordering::Less) => other.start().clone(),
197            Some(_) => self.start().clone(),
198        };
199
200        let end = match self.end.partial_cmp(other.end()) {
201            None => return Err(EmptyGrouping),
202            Some(Ordering::Greater) => other.end().clone(),
203            Some(_) => self.end().clone(),
204        };
205
206        Self::try_new(start, end)
207    }
208}
209
210impl<T> ClosedRange<T> {
211    /// Creates a new closed range, without enforcing non-emptyness.
212    ///
213    /// #### Safety
214    ///
215    /// Calling this method with `start >= end` is undefined behaviour.
216    ///
217    /// ```
218    /// use willow_data_model::prelude::*;
219    ///
220    /// let yay = unsafe { ClosedRange::new_unchecked(2, 7) };
221    /// ```
222    pub unsafe fn new_unchecked(start: T, end: T) -> Self {
223        Self { start, end }
224    }
225
226    /// Returns a reference to the start value of this closed range.
227    ///
228    /// ```
229    /// use willow_data_model::prelude::*;
230    ///
231    /// let r = ClosedRange::new(2, 7);
232    /// assert_eq!(r.start(), &2);
233    /// ```
234    pub fn start(&self) -> &T {
235        &self.start
236    }
237
238    /// Returns a reference to the end value of this closed range.
239    ///
240    /// ```
241    /// use willow_data_model::prelude::*;
242    ///
243    /// let r = ClosedRange::new(2, 7);
244    /// assert_eq!(r.end(), &7);
245    /// ```
246    pub fn end(&self) -> &T {
247        &self.end
248    }
249
250    /// Takes ownership of a closed range and returns its start and end value.
251    ///
252    /// ```
253    /// use willow_data_model::prelude::*;
254    ///
255    /// let r = ClosedRange::new(2, 7);
256    /// assert_eq!(r.into_components(), (2, 7));
257    /// ```
258    pub fn into_components(self) -> (T, T) {
259        (self.start, self.end)
260    }
261}
262
263impl<T> RangeBounds<T> for ClosedRange<T> {
264    fn start_bound(&self) -> Bound<&T> {
265        Bound::Included(&self.start)
266    }
267
268    fn end_bound(&self) -> Bound<&T> {
269        Bound::Excluded(&self.end)
270    }
271}
272
273#[cfg(feature = "dev")]
274impl<'a, T> Arbitrary<'a> for ClosedRange<T>
275where
276    T: Arbitrary<'a> + PartialOrd,
277{
278    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
279        let start = T::arbitrary(u)?;
280        let end = T::arbitrary(u)?;
281
282        Self::try_new(start, end).map_err(|_| arbitrary::Error::IncorrectFormat)
283    }
284
285    fn try_size_hint(
286        depth: usize,
287    ) -> arbitrary::Result<(usize, Option<usize>), arbitrary::MaxRecursionReached> {
288        Ok(size_hint::and_all(&[
289            T::try_size_hint(depth)?,
290            T::try_size_hint(depth)?,
291        ]))
292    }
293}
294
295/// A non-empty continuous subset of a type implementing [`PartialOrd`].
296///
297/// It is either a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) consisting of an inclusive start value and a strictly-greater exclusive end value, or an [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) consisting only of an inclusive start value.
298///
299/// ```
300/// use std::ops::RangeBounds;
301/// use willow_data_model::prelude::*;
302///
303/// assert!(WillowRange::<u8>::new_closed(4, 9).contains(&6));
304/// assert!(!WillowRange::<u8>::new_closed(4, 9).contains(&12));
305/// ```
306#[derive(Clone, Copy, PartialEq, Eq, Hash)]
307#[repr(C)]
308pub enum WillowRange<T> {
309    /// A [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) with an inclusive start value and an exclusive end value.
310    Closed(ClosedRange<T>),
311    /// An [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) with an inclusive start value.
312    ///
313    /// It includes all values greater than or equal to that start value.
314    Open(T),
315}
316
317impl<T: Debug> Debug for WillowRange<T> {
318    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
319        match self {
320            Self::Closed(closed) => closed.fmt(f),
321            Self::Open(start) => {
322                start.fmt(f)?;
323                write!(f, "..")?;
324                Ok(())
325            }
326        }
327    }
328}
329
330impl<T> RangeBounds<T> for WillowRange<T> {
331    fn start_bound(&self) -> Bound<&T> {
332        match self {
333            Self::Closed(inner) => inner.start_bound(),
334            Self::Open(start) => Bound::Included(start),
335        }
336    }
337
338    fn end_bound(&self) -> Bound<&T> {
339        match self {
340            Self::Closed(inner) => inner.end_bound(),
341            Self::Open(_) => Bound::Unbounded,
342        }
343    }
344}
345
346#[cfg(feature = "dev")]
347impl<'a, T> Arbitrary<'a> for WillowRange<T>
348where
349    T: Arbitrary<'a> + PartialOrd,
350{
351    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
352        if bool::arbitrary(u)? {
353            Ok(Self::Closed(ClosedRange::<T>::arbitrary(u)?))
354        } else {
355            Ok(Self::Open(T::arbitrary(u)?))
356        }
357    }
358
359    fn try_size_hint(
360        depth: usize,
361    ) -> arbitrary::Result<(usize, Option<usize>), arbitrary::MaxRecursionReached> {
362        Ok(size_hint::or(
363            size_hint::and_all(&[
364                bool::try_size_hint(depth)?,
365                ClosedRange::<T>::try_size_hint(depth)?,
366            ]),
367            size_hint::and(bool::try_size_hint(depth)?, T::try_size_hint(depth)?),
368        ))
369    }
370}
371
372impl<T> WillowRange<T> {
373    /// Creates a new open range.
374    ///
375    /// ```
376    /// use willow_data_model::prelude::*;
377    ///
378    /// let open = WillowRange::new_open(2);
379    ///
380    /// assert!(open.is_open());
381    /// assert_eq!(open.start(), &2);
382    /// ```
383    pub fn new_open(start: T) -> Self {
384        Self::Open(start)
385    }
386
387    /// Returns a reference to the start value of this range.
388    ///
389    /// ```
390    /// use willow_data_model::prelude::*;
391    ///
392    /// let closed = WillowRange::new_closed(2, 7);
393    /// assert_eq!(closed.start(), &2);
394    ///
395    /// let open = WillowRange::new_open(2);
396    /// assert_eq!(open.start(), &2);
397    /// ```
398    pub fn start(&self) -> &T {
399        match self {
400            Self::Closed(inner) => inner.start(),
401            Self::Open(start) => start,
402        }
403    }
404
405    /// Returns a reference to the end value of this range, or `None` of it is open.
406    ///
407    /// ```
408    /// use willow_data_model::prelude::*;
409    ///
410    /// let closed = WillowRange::new_closed(2, 7);
411    /// assert_eq!(closed.end(), Some(&7));
412    ///
413    /// let open = WillowRange::new_open(2);
414    /// assert_eq!(open.end(), None);
415    /// ```
416    pub fn end(&self) -> Option<&T> {
417        match self {
418            Self::Closed(inner) => Some(inner.end()),
419            Self::Open(_) => None,
420        }
421    }
422
423    /// Takes ownership of a willow range and returns its start and end.
424    ///
425    /// ```
426    /// use willow_data_model::prelude::*;
427    ///
428    /// let closed = WillowRange::new_closed(2, 7);
429    /// assert_eq!(closed.into_components(), (2, Some(7)));
430    ///
431    /// let open = WillowRange::new_open(2);
432    /// assert_eq!(open.into_components(), (2, None));
433    /// ```
434    pub fn into_components(self) -> (T, Option<T>) {
435        match self {
436            Self::Closed(inner) => (inner.start, Some(inner.end)),
437            Self::Open(start) => (start, None),
438        }
439    }
440
441    /// Returns whether `self` is a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range).
442    ///
443    /// ```
444    /// use willow_data_model::prelude::*;
445    ///
446    /// assert_eq!(WillowRange::<u8>::new_closed(3, 8).is_closed(), true);
447    /// assert_eq!(WillowRange::<u8>::new_open(3).is_closed(), false);
448    /// ```
449    pub fn is_closed(&self) -> bool {
450        matches!(self, Self::Closed(_))
451    }
452
453    /// Returns whether `self` is an [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range).
454    ///
455    /// ```
456    /// use willow_data_model::prelude::*;
457    ///
458    /// assert_eq!(WillowRange::<u8>::new_closed(3, 8).is_open(), false);
459    /// assert_eq!(WillowRange::<u8>::new_open(3).is_open(), true);
460    /// ```
461    pub fn is_open(&self) -> bool {
462        matches!(self, Self::Open(_))
463    }
464
465    /// Converts this range into a different range by applying a function to all endpoints. Returns an error if the new range would be empty.
466    ///
467    /// ```
468    /// use willow_data_model::prelude::*;
469    ///
470    /// assert_eq!(
471    ///     WillowRange::<u8>::new_closed(3, 8).try_map(|x| (x + 1) as u16),
472    ///     Ok(WillowRange::<u16>::new_closed(4, 9)),
473    /// );
474    /// ```
475    pub fn try_map<U, F>(self, mut f: F) -> Result<WillowRange<U>, EmptyGrouping>
476    where
477        F: FnMut(T) -> U,
478        U: PartialOrd,
479    {
480        match self {
481            Self::Closed(ClosedRange { start, end }) => {
482                Ok(WillowRange::Closed(ClosedRange::try_new(f(start), f(end))?))
483            }
484            Self::Open(start) => Ok(WillowRange::Open(f(start))),
485        }
486    }
487
488    /// Converts this range into a different range by applying a function to all endpoints. Panics if the new range would be empty.
489    ///
490    /// ```
491    /// use willow_data_model::prelude::*;
492    ///
493    /// assert_eq!(
494    ///     WillowRange::<u8>::new_closed(3, 8).map(|x| (x + 1) as u16),
495    ///     WillowRange::<u16>::new_closed(4, 9),
496    /// );
497    /// ```
498    pub fn map<U, F>(self, mut f: F) -> WillowRange<U>
499    where
500        F: FnMut(T) -> U,
501        U: PartialOrd,
502    {
503        match self {
504            Self::Closed(ClosedRange { start, end }) => {
505                WillowRange::Closed(ClosedRange::new(f(start), f(end)))
506            }
507            Self::Open(start) => WillowRange::Open(f(start)),
508        }
509    }
510
511    /// Converts this range into a different range by applying a function to all endpoints, without checking if the resulting range would be empty.
512    ///
513    /// ## Safety
514    ///
515    /// Undefined behaviour may occur if the resulting range would be empty.
516    ///
517    /// ```
518    /// use willow_data_model::prelude::*;
519    ///
520    /// assert_eq!(
521    ///     unsafe {
522    ///         WillowRange::<u8>::new_closed(3, 8).map_unchecked(|x| (x + 1) as u16)
523    ///     },
524    ///     WillowRange::<u16>::new_closed(4, 9),
525    /// );
526    /// ```
527    pub unsafe fn map_unchecked<U, F>(self, mut f: F) -> WillowRange<U>
528    where
529        F: FnMut(T) -> U,
530        U: PartialOrd,
531    {
532        match self {
533            Self::Closed(ClosedRange { start, end }) => {
534                // SAFETY: the unsafety of this call is exactly why this method is unsafe itself.
535                WillowRange::Closed(unsafe { ClosedRange::new_unchecked(f(start), f(end)) })
536            }
537            Self::Open(start) => WillowRange::Open(f(start)),
538        }
539    }
540
541    /// Unsafely reinterprets a reference to a range as a reference to a range of a different type of boundaries.
542    ///
543    /// # Safety
544    ///
545    /// This is safe only if `&T` and `&U` have an identical layout in memory, and if the resulting range is non-empty.
546    pub unsafe fn cast<U>(&self) -> &WillowRange<U> {
547        // SAFETY: WillowRange and ClosedRanged are `repr(C)`, so if `T` and `U` have identical
548        // layout, then so do `WillowRange<T>` and `WillowRange<U>`
549        unsafe { &*(self as *const Self as *const WillowRange<U>) }
550    }
551
552    /// Creates a new Willow range, without enforcing non-emptyness.
553    ///
554    /// #### Safety
555    ///
556    /// Calling this method with `start >= end` is undefined behaviour.
557    ///
558    /// ```
559    /// use willow_data_model::prelude::*;
560    ///
561    /// let yay = unsafe { WillowRange::new_unchecked(2, Some(7)) };
562    /// ```
563    pub unsafe fn new_unchecked(start: T, end: Option<T>) -> Self {
564        match end {
565            // SAFETY: the unsafety of this call is exactly why this method is unsafe itself.
566            Some(end) => Self::Closed(unsafe { ClosedRange::new_unchecked(start, end) }),
567            None => Self::new_open(start),
568        }
569    }
570
571    /// Creates a new closed Willow range, without enforcing non-emptyness.
572    ///
573    /// #### Safety
574    ///
575    /// Calling this method with `start >= end` is undefined behaviour.
576    ///
577    /// ```
578    /// use willow_data_model::prelude::*;
579    ///
580    /// let yay = unsafe { WillowRange::new_closed_unchecked(2, 7) };
581    /// ```
582    pub unsafe fn new_closed_unchecked(start: T, end: T) -> Self {
583        // SAFETY: the unsafety of this call is exactly why this method is unsafe itself.
584        Self::Closed(unsafe { ClosedRange::new_unchecked(start, end) })
585    }
586}
587
588impl<T> WillowRange<T>
589where
590    T: PartialOrd,
591{
592    /// Creates a new Willow range from a start value and an optional end value, or returns an [`EmptyGrouping`] error if the created range would be empty.
593    ///
594    /// ```
595    /// use willow_data_model::prelude::*;
596    ///
597    /// assert!(WillowRange::try_new(2, Some(7)).is_ok());
598    /// assert!(WillowRange::try_new(7, Some(2)).is_err());
599    /// assert!(WillowRange::try_new(2, Some(2)).is_err());
600    /// ```
601    pub fn try_new(start: T, end: Option<T>) -> Result<Self, EmptyGrouping> {
602        let ret = match end {
603            Some(end) => Self::Closed(ClosedRange { start, end }),
604            None => Self::Open(start),
605        };
606
607        if ret.is_empty() {
608            Err(EmptyGrouping)
609        } else {
610            Ok(ret)
611        }
612    }
613
614    /// Creates a new Willow range from a start value and an optional end value, panicking if the created range would be empty.
615    ///
616    /// ```
617    /// use willow_data_model::prelude::*;
618    ///
619    /// let yay = WillowRange::new_closed(2, 7);
620    /// ```
621    ///
622    /// ```should_panic
623    /// use willow_data_model::prelude::*;
624    ///
625    /// let nope = WillowRange::new(7, Some(2));
626    /// ```
627    pub fn new(start: T, end: Option<T>) -> Self {
628        Self::try_new(start, end).unwrap()
629    }
630
631    /// Creates a new closed Willow range, or returns an [`EmptyGrouping`] error if the created range would be empty.
632    ///
633    /// ```
634    /// use willow_data_model::prelude::*;
635    ///
636    /// assert!(WillowRange::try_new_closed(2, 7).is_ok());
637    /// assert!(WillowRange::try_new_closed(7, 2).is_err());
638    /// assert!(WillowRange::try_new_closed(2, 2).is_err());
639    /// ```
640    pub fn try_new_closed(start: T, end: T) -> Result<Self, EmptyGrouping> {
641        Ok(Self::Closed(ClosedRange::try_new(start, end)?))
642    }
643
644    /// Creates a new Willow range from a start value and an optional end value, panicking if the created range would be empty.
645    ///
646    /// ```
647    /// use willow_data_model::prelude::*;
648    ///
649    /// let yay = WillowRange::new_closed(2, 7);
650    /// ```
651    ///
652    /// ```should_panic
653    /// use willow_data_model::prelude::*;
654    ///
655    /// let nope = WillowRange::new_closed(7, 2);
656    /// ```
657    pub fn new_closed(start: T, end: T) -> Self {
658        Self::Closed(ClosedRange::new(start, end))
659    }
660
661    /// Returns whether the given value is included in `self`.
662    ///
663    /// ```
664    /// use willow_data_model::prelude::*;
665    ///
666    /// let closed = WillowRange::new_closed(2, 7);
667    /// assert!(closed.includes_value(&2));
668    /// assert!(!closed.includes_value(&1));
669    /// assert!(!closed.includes_value(&7));
670    ///
671    /// let open = WillowRange::new_open(2);
672    /// assert!(open.includes_value(&2));
673    /// assert!(!open.includes_value(&1));
674    /// assert!(open.includes_value(&7));
675    /// ```
676    pub fn includes_value(&self, t: &T) -> bool {
677        self.start() <= t && self.end().map(|end| end > t).unwrap_or(true)
678    }
679
680    /// Returns whether the given value is included in `self` and `other`.
681    ///
682    /// ```
683    /// use willow_data_model::prelude::*;
684    ///
685    /// let r1 = WillowRange::new_closed(2, 7);
686    /// let r2 = WillowRange::new_open(5);
687    /// assert!(r1.includes_value_in_intersection(&r2, &5));
688    /// assert!(!r1.includes_value_in_intersection(&r2, &2));
689    /// assert!(!r1.includes_value_in_intersection(&r2, &7));
690    /// assert!(!r1.includes_value_in_intersection(&r2, &1));
691    /// assert!(!r1.includes_value_in_intersection(&r2, &22));
692    /// ```
693    pub fn includes_value_in_intersection(&self, other: &Self, t: &T) -> bool {
694        self.includes_value(t) && other.includes_value(t)
695    }
696
697    /// Returns whether the given Willow range is included in `self`.
698    ///
699    /// ```
700    /// use willow_data_model::prelude::*;
701    ///
702    /// let r = WillowRange::new_closed(2, 7);
703    /// assert!(r.includes_willow_range(&WillowRange::new_closed(2, 7)));
704    /// assert!(!r.includes_willow_range(&WillowRange::new_closed(1, 7)));
705    /// assert!(!r.includes_willow_range(&WillowRange::new_closed(2, 8)));
706    /// assert!(!r.includes_willow_range(&WillowRange::new_closed(9, 14)));
707    /// assert!(!r.includes_willow_range(&WillowRange::new_open(2)));
708    /// ```
709    pub fn includes_willow_range(&self, other: &Self) -> bool {
710        self.start() <= other.start()
711            && match (self.end(), other.end()) {
712                (None, None) => true,
713                (Some(_), None) => false,
714                (None, Some(_)) => true,
715                (Some(self_end), Some(other_end)) => self_end >= other_end,
716            }
717    }
718
719    /// Returns whether the given Willow range is strictly included in `self`.
720    ///
721    /// ```
722    /// use willow_data_model::prelude::*;
723    ///
724    /// let r = WillowRange::new_closed(2, 7);
725    /// assert!(r.strictly_includes_willow_range(&WillowRange::new_closed(2, 6)));
726    /// assert!(r.strictly_includes_willow_range(&WillowRange::new_closed(3, 7)));
727    /// assert!(r.strictly_includes_willow_range(&WillowRange::new_closed(3, 6)));
728    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(2, 7)));
729    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(1, 7)));
730    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(2, 8)));
731    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_closed(9, 14)));
732    /// assert!(!r.strictly_includes_willow_range(&WillowRange::new_open(2)));
733    /// ```
734    pub fn strictly_includes_willow_range(&self, other: &Self) -> bool {
735        self != other && self.includes_willow_range(other)
736    }
737
738    /// Only use this internally to check whether the non-emptyness invariant would be upheld by something. Not a public method because we *never publicly expose empty ranges.
739    fn is_empty(&self) -> bool {
740        match self {
741            WillowRange::Closed(inner) => inner.is_empty(),
742            WillowRange::Open(_) => false,
743        }
744    }
745}
746
747impl<T> WillowRange<T>
748where
749    T: PartialOrd + Clone,
750{
751    /// Returns the intersection between `self` and `other`, or an [`EmptyGrouping`] error if it would be empty.
752    ///
753    /// assert_eq!(
754    ///     WillowRange::new(2, 7).intersection_willow_range(WillowRange::new(5, 9)),
755    ///     Ok(WillowRange::new(5, 7)),
756    /// );
757    /// assert!(
758    ///     WillowRange::new(2, 5).intersection_willow_range(WillowRange::new(7, 9)).is_error(),
759    /// );
760    pub fn intersection_willow_range(&self, other: &Self) -> Result<Self, EmptyGrouping> {
761        let start = match self.start().partial_cmp(other.start()) {
762            None => return Err(EmptyGrouping),
763            Some(Ordering::Less) => other.start().clone(),
764            Some(_) => self.start().clone(),
765        };
766
767        let end = match (self.end(), other.end()) {
768            (None, None) => None,
769            (Some(start), None) | (None, Some(start)) => Some(start.clone()),
770            (Some(self_end), Some(other_end)) => match self_end.partial_cmp(other_end) {
771                None => return Err(EmptyGrouping),
772                Some(Ordering::Greater) => Some(other_end.clone()),
773                _ => Some(self_end.clone()),
774            },
775        };
776
777        Self::try_new(start, end)
778    }
779}
780
781/// A range is less than another iff all values contained in the first are also contained in the other.
782impl<T> PartialOrd for WillowRange<T>
783where
784    T: PartialOrd,
785{
786    fn partial_cmp(&self, other: &WillowRange<T>) -> Option<Ordering> {
787        match (self, other) {
788            (Self::Closed(self_closed), Self::Closed(other_closed)) => {
789                self_closed.partial_cmp(other_closed)
790            }
791            (Self::Closed(self_closed), Self::Open(other_open)) => {
792                match self_closed.start().partial_cmp(other_open)? {
793                    Ordering::Less => None,
794                    Ordering::Equal | Ordering::Greater => Some(Ordering::Less),
795                }
796            }
797            (Self::Open(self_open), Self::Closed(other_closed)) => {
798                match self_open.partial_cmp(other_closed.start())? {
799                    Ordering::Greater => None,
800                    Ordering::Equal | Ordering::Less => Some(Ordering::Greater),
801                }
802            }
803            (Self::Open(self_open), Self::Open(other_open)) => {
804                match self_open.partial_cmp(other_open)? {
805                    Ordering::Less => Some(Ordering::Greater),
806                    Ordering::Equal => Some(Ordering::Equal),
807                    Ordering::Greater => Some(Ordering::Less),
808                }
809            }
810        }
811    }
812}
813
814impl<T> WillowRange<T>
815where
816    T: SuccessorExceptForGreatest,
817{
818    /// Returns the [`WillowRange`] which [includes](core::ops::RangeBounds::contains) `t` but no other value.
819    ///
820    /// Panicks if `T::try_successor` returns a valid which is not greater than `t`.
821    ///
822    /// ```
823    /// use willow_data_model::prelude::*;
824    ///
825    /// assert_eq!(WillowRange::<u8>::singleton(5), WillowRange::<u8>::new_closed(5, 6));
826    /// assert_eq!(WillowRange::<u8>::singleton(255), WillowRange::<u8>::new_open(255));
827    /// ```
828    pub fn singleton(t: T) -> Self {
829        match t.try_successor() {
830            Some(succ) => Self::Closed(ClosedRange::new(t, succ)),
831            None => Self::Open(t),
832        }
833    }
834}
835
836impl<T> WillowRange<T>
837where
838    T: LeastElement,
839{
840    /// Returns the `WillowRange` which [includes](core::ops::RangeBounds::contains) every value of type `T`.
841    ///
842    /// ```
843    /// use willow_data_model::prelude::*;
844    ///
845    /// assert_eq!(WillowRange::<u8>::full(), WillowRange::<u8>::new_open(0));
846    /// ```
847    pub fn full() -> Self {
848        Self::Open(T::least())
849    }
850
851    /// Returns whether `self` is the full range, i.e., the range which [includes](core::ops::RangeBounds::contains) every value of type `T`.
852    ///
853    /// ```
854    /// use willow_data_model::prelude::*;
855    ///
856    /// assert_eq!(WillowRange::<u8>::full().is_full(), true);
857    /// assert_eq!(WillowRange::<u8>::new_open(1).is_full(), false);
858    /// ```
859    pub fn is_full(&self) -> bool {
860        match self {
861            Self::Closed(_) => false,
862            Self::Open(start) => start.is_least(),
863        }
864    }
865}
866
867impl<T> GreatestElement for WillowRange<T>
868where
869    T: LeastElement,
870{
871    fn greatest() -> Self {
872        Self::Open(T::least())
873    }
874}
willow_data_model/groupings/willow_range.rs

willow_data_model/groupings/
willow_range.rs
