willow_data_model/groupings/
willow_range.rs

1use core::cmp::Ordering;
2use core::fmt::{self, Debug, Formatter};
3use core::hash::Hash;
4use core::ops::{
5    Bound, Range, RangeBounds, RangeFrom, RangeFull, RangeInclusive, RangeTo, RangeToInclusive,
6};
7
8#[cfg(feature = "dev")]
9use arbitrary::{Arbitrary, size_hint};
10
11use order_theory::{
12    GreatestElement, LeastElement, LowerSemilattice, PredecessorExceptForLeast,
13    SuccessorExceptForGreatest, UpperSemilattice, finite_range,
14};
15
16/// A continuous subset of a type implementing [`Ord`].
17///
18/// It is either a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) consisting of an inclusive start value and an exclusive end value, or an [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) consisting only of an inclusive start value.
19///
20/// ```
21/// use std::ops::RangeBounds;
22/// use willow_data_model::prelude::*;
23///
24/// assert!(WillowRange::<u8>::from(4..9).contains(&6));
25/// assert!(!WillowRange::<u8>::from(4..9).contains(&12));
26///
27/// // You can create `WillowRanges` from arbitrary Rust ranges.
28/// assert!(WillowRange::<u8>::from(4..=8) == WillowRange::<u8>::from(4..9));
29/// ```
30#[derive(Clone)]
31pub enum WillowRange<T> {
32    /// A [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) with an inclusive start value and an exclusive end value.
33    Closed(Range<T>),
34    /// An [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) with an inclusive start value.
35    Open(RangeFrom<T>),
36}
37
38impl<T> RangeBounds<T> for WillowRange<T> {
39    fn start_bound(&self) -> Bound<&T> {
40        match self {
41            Self::Closed(inner) => inner.start_bound(),
42            Self::Open(inner) => inner.start_bound(),
43        }
44    }
45
46    fn end_bound(&self) -> Bound<&T> {
47        match self {
48            Self::Closed(inner) => inner.end_bound(),
49            Self::Open(inner) => inner.end_bound(),
50        }
51    }
52}
53
54impl<T> WillowRange<T>
55where
56    T: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
57{
58    /// Returns whether every possible item that is [included](core::ops::RangeBounds::contains) in `other` is also [included](core::ops::RangeBounds::contains) in `self`.
59    ///
60    /// If `other` is a [`WillowRange`], you can equivalently check `self >= other`.
61    ///
62    /// ```
63    /// use willow_data_model::prelude::*;
64    ///
65    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(5..7)), true);
66    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(5..11)), false);
67    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(2..7)), false);
68    /// assert_eq!(WillowRange::<u8>::from(4..9).includes_range(&(4..9)), true);
69    /// ```
70    #[doc(alias = "contains_range")]
71    pub fn includes_range<R: RangeBounds<T>>(&self, other: &R) -> bool {
72        match finite_range::partial_cmp(self, other) {
73            None => false,
74            Some(ord) => ord.is_ge(),
75        }
76    }
77
78    /// Returns whether every possible item that is [included](core::ops::RangeBounds::contains) in `other` is also [included](core::ops::RangeBounds::contains) in `self` and there exists at least one item [included](core::ops::RangeBounds::contains) in `self` but not [included](core::ops::RangeBounds::contains) in `other`.
79    ///
80    /// If `other` is a [`WillowRange`], you can equivalently check `self > other`.
81    ///
82    /// ```
83    /// use willow_data_model::prelude::*;
84    ///
85    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(5..7)), true);
86    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(5..11)), false);
87    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(2..7)), false);
88    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(4..9)), false);
89    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(5..9)), true);
90    /// assert_eq!(WillowRange::<u8>::from(4..9).strictly_includes_range(&(4..8)), true);
91    /// ```
92    #[doc(alias = "strictly_contains_range")]
93    pub fn strictly_includes_range<R: RangeBounds<T>>(&self, other: &R) -> bool {
94        match finite_range::partial_cmp(self, other) {
95            None => false,
96            Some(ord) => ord.is_gt(),
97        }
98    }
99
100    /// Returns whether the [`intersection`](WillowRange::intersection) of `self` and `other` [includes](core::ops::RangeBounds::contains) the given value.
101    ///
102    /// More efficient than actually creating the intersection and then calling [`includes`](core::ops::RangeBounds::contains).
103    ///
104    /// ```
105    /// use willow_data_model::prelude::*;
106    ///
107    /// assert!(WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &6));
108    /// assert!(!WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &4));
109    /// assert!(!WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &8));
110    /// assert!(!WillowRange::<u8>::from(4..9).does_intersection_include_value(&(5..7), &99));
111    /// ```
112    pub fn does_intersection_include_value<R: RangeBounds<T>>(&self, other: &R, value: &T) -> bool {
113        finite_range::is_in_greatest_lower_bound(value, self, other)
114    }
115}
116
117impl<T> WillowRange<T>
118where
119    T: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
120{
121    /// Converts any value which implements [`RangeBounds<T>`](core::ops::RangeBounds) into a [`WillowRange<T>`](WillowRange) containing the same values.
122    ///
123    /// ```
124    /// use willow_data_model::prelude::*;
125    ///
126    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..)), (..).into());
127    /// assert_eq!(WillowRange::<u8>::from_bounds(&(0..)), (0..).into());
128    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..254)), (..254).into());
129    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..255)), (..255).into());
130    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..=254)), (..=254).into());
131    /// assert_eq!(WillowRange::<u8>::from_bounds(&(..=255)), (..=255).into());
132    /// assert_eq!(WillowRange::<u8>::from_bounds(&(4..8)), (4..8).into());
133    /// assert_eq!(WillowRange::<u8>::from_bounds(&(4..=8)), (4..=8).into());
134    /// ```
135    pub fn from_bounds<R>(bounds: &R) -> Self
136    where
137        R: RangeBounds<T>,
138    {
139        let start = match bounds.start_bound() {
140            Bound::Unbounded => T::least(),
141            Bound::Included(t) => t.clone(),
142            Bound::Excluded(t) => t.try_predecessor().unwrap_or_else(|| T::least()),
143        };
144
145        match bounds.end_bound() {
146            Bound::Unbounded => return Self::Open(start..),
147            Bound::Included(t) => match t.try_successor() {
148                Some(succ) => return Self::Closed(start..succ),
149                None => return Self::Open(start..),
150            },
151            Bound::Excluded(t) => return Self::Closed(start..t.clone()),
152        }
153    }
154
155    /// Returns the [intersection](https://willowprotocol.org/specs/grouping-entries/index.html#range_intersection) of `self` and `other`, i.e., the [`WillowRange`] which [includes](core::ops::RangeBounds::contains) exactly those values [included](core::ops::RangeBounds::contains) in both `self` and `other`.
156    ///
157    /// If you want to check whether some value is [included](core::ops::RangeBounds::contains) in the intersecion of two ranges, prefer [`WillowRange::does_intersection_include_value`] over explicitly constructing the intersection.
158    ///
159    /// ```
160    /// use willow_data_model::prelude::*;
161    ///
162    /// assert_eq!(WillowRange::<u8>::from(4..9).intersection(&(5..7)), (5..7).into());
163    /// assert_eq!(WillowRange::<u8>::from(4..9).intersection(&(5..11)), (5..9).into());
164    /// assert_eq!(WillowRange::<u8>::from(4..9).intersection(&(2..7)), (4..7).into());
165    /// assert!(WillowRange::<u8>::from(4..9).intersection(&(11..14)).is_empty());
166    /// assert!(WillowRange::<u8>::from(4..9).intersection(&(6..6)).is_empty());
167    /// ```
168    #[doc(alias("intersect", "greatest_lower_bound", "glb", "meet"))]
169    pub fn intersection<R: RangeBounds<T>>(&self, other: &R) -> Self {
170        Self::from_bounds(&finite_range::greatest_lower_bound(self, other))
171    }
172}
173
174impl<T> From<Range<T>> for WillowRange<T> {
175    fn from(value: Range<T>) -> Self {
176        Self::Closed(value)
177    }
178}
179
180impl<T> From<RangeFrom<T>> for WillowRange<T> {
181    fn from(value: RangeFrom<T>) -> Self {
182        Self::Open(value)
183    }
184}
185
186impl<T> From<RangeFull> for WillowRange<T>
187where
188    T: LeastElement,
189{
190    fn from(_value: RangeFull) -> Self {
191        Self::Open(T::least()..)
192    }
193}
194
195impl<T> From<RangeInclusive<T>> for WillowRange<T>
196where
197    T: SuccessorExceptForGreatest,
198{
199    fn from(value: RangeInclusive<T>) -> Self {
200        let (start, end) = value.into_inner();
201        match end.try_successor() {
202            None => Self::Open(start..),
203            Some(succ) => Self::Closed(start..succ),
204        }
205    }
206}
207
208impl<T> From<RangeTo<T>> for WillowRange<T>
209where
210    T: LeastElement,
211{
212    fn from(value: RangeTo<T>) -> Self {
213        Self::Closed(T::least()..value.end)
214    }
215}
216
217impl<T> From<RangeToInclusive<T>> for WillowRange<T>
218where
219    T: LeastElement + SuccessorExceptForGreatest,
220{
221    fn from(value: RangeToInclusive<T>) -> Self {
222        match value.end.try_successor() {
223            None => Self::Open(T::least()..),
224            Some(succ) => Self::Closed(T::least()..succ),
225        }
226    }
227}
228
229impl<T: Debug> Debug for WillowRange<T> {
230    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
231        match self {
232            Self::Closed(r) => r.fmt(f),
233            Self::Open(r) => r.fmt(f),
234        }
235    }
236}
237
238/// Two [`WillowRanges`](WillowRange) are equal iff they contain the same values.
239impl<T> PartialEq<WillowRange<T>> for WillowRange<T>
240where
241    T: Ord + SuccessorExceptForGreatest + PredecessorExceptForLeast,
242{
243    fn eq(&self, other: &WillowRange<T>) -> bool {
244        finite_range::eq(self, other)
245    }
246
247    #[allow(clippy::partialeq_ne_impl)]
248    fn ne(&self, other: &WillowRange<T>) -> bool {
249        finite_range::ne(self, other)
250    }
251}
252
253impl<T: Eq> Eq for WillowRange<T> where
254    T: Ord + SuccessorExceptForGreatest + PredecessorExceptForLeast
255{
256}
257
258/// A range is less than another iff all values contained in the first are also contained in the other.
259impl<T> PartialOrd<WillowRange<T>> for WillowRange<T>
260where
261    T: Ord + SuccessorExceptForGreatest + PredecessorExceptForLeast,
262{
263    fn partial_cmp(&self, other: &WillowRange<T>) -> Option<Ordering> {
264        finite_range::partial_cmp(self, other)
265    }
266}
267
268// Have to implement this manually beause Range and RangeFrom are not Clone.
269#[cfg(feature = "dev")]
270impl<'a, T: Arbitrary<'a>> Arbitrary<'a> for WillowRange<T> {
271    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
272        if bool::arbitrary(u)? {
273            Ok(Self::Closed(T::arbitrary(u)?..T::arbitrary(u)?))
274        } else {
275            Ok(Self::Open(T::arbitrary(u)?..))
276        }
277    }
278
279    fn try_size_hint(
280        depth: usize,
281    ) -> arbitrary::Result<(usize, Option<usize>), arbitrary::MaxRecursionReached> {
282        Ok(size_hint::or(
283            size_hint::and_all(&[
284                bool::try_size_hint(depth)?,
285                T::try_size_hint(depth)?,
286                T::try_size_hint(depth)?,
287            ]),
288            size_hint::and(bool::try_size_hint(depth)?, T::try_size_hint(depth)?),
289        ))
290    }
291}
292
293impl<T> WillowRange<T> {
294    /// Returns whether `self` is a [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range).
295    ///
296    /// ```
297    /// use willow_data_model::prelude::*;
298    ///
299    /// assert_eq!(WillowRange::<u8>::from(3..8).is_closed(), true);
300    /// assert_eq!(WillowRange::<u8>::from(3..255).is_closed(), true);
301    /// assert_eq!(WillowRange::<u8>::from(3..=255).is_closed(), false);
302    /// assert_eq!(WillowRange::<u8>::from(3..).is_closed(), false);
303    /// ```
304    pub fn is_closed(&self) -> bool {
305        matches!(self, Self::Closed(_))
306    }
307
308    /// Returns whether `self` is an [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range).
309    ///
310    /// ```
311    /// use willow_data_model::prelude::*;
312    ///
313    /// assert_eq!(WillowRange::<u8>::from(3..8).is_open(), false);
314    /// assert_eq!(WillowRange::<u8>::from(3..255).is_open(), false);
315    /// assert_eq!(WillowRange::<u8>::from(3..=255).is_open(), true);
316    /// assert_eq!(WillowRange::<u8>::from(3..).is_open(), true);
317    /// ```
318    pub fn is_open(&self) -> bool {
319        matches!(self, Self::Open(_))
320    }
321
322    /// Returns a reference to the [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) of `self`.
323    ///
324    /// ```
325    /// use willow_data_model::prelude::*;
326    ///
327    /// assert_eq!(WillowRange::<u8>::from(3..8).start(), &3);
328    /// assert_eq!(WillowRange::<u8>::from(..8).start(), &0);
329    /// ```
330    pub fn start(&self) -> &T {
331        match self {
332            Self::Closed(Range { start, .. }) => start,
333            Self::Open(RangeFrom { start }) => start,
334        }
335    }
336
337    /// Returns a mutable reference to the [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) of `self`.
338    ///
339    /// ```
340    /// use willow_data_model::prelude::*;
341    ///
342    /// assert_eq!(WillowRange::<u8>::from(3..8).start_mut(), &mut 3);
343    /// assert_eq!(WillowRange::<u8>::from(..8).start_mut(), &mut 0);
344    /// ```
345    pub fn start_mut(&mut self) -> &mut T {
346        match self {
347            Self::Closed(Range { start, .. }) => start,
348            Self::Open(RangeFrom { start }) => start,
349        }
350    }
351
352    /// Returns a reference to the [end value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value) of `self`, or `None` if the range [is open](WillowRange::is_open).
353    ///
354    /// ```
355    /// use willow_data_model::prelude::*;
356    ///
357    /// assert_eq!(WillowRange::<u8>::from(3..8).end(), Some(&8));
358    /// assert_eq!(WillowRange::<u8>::from(3..=8).end(), Some(&9));
359    /// assert_eq!(WillowRange::<u8>::from(3..).end(), None);
360    /// ```
361    pub fn end(&self) -> Option<&T> {
362        match self {
363            Self::Closed(Range { end, .. }) => Some(end),
364            Self::Open(_) => None,
365        }
366    }
367
368    /// Returns a mutable reference to the [end value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value) of `self`, or `None` if the range [is open](WillowRange::is_open).
369    ///
370    /// ```
371    /// use willow_data_model::prelude::*;
372    ///
373    /// assert_eq!(WillowRange::<u8>::from(3..8).end_mut(), Some(&mut 8));
374    /// assert_eq!(WillowRange::<u8>::from(3..=8).end_mut(), Some(&mut 9));
375    /// assert_eq!(WillowRange::<u8>::from(3..).end_mut(), None);
376    /// ```
377    pub fn end_mut(&mut self) -> Option<&mut T> {
378        match self {
379            Self::Closed(Range { end, .. }) => Some(end),
380            Self::Open(_) => None,
381        }
382    }
383
384    /// Converts this range into a different range by applying a function to all endpoints.
385    ///
386    /// ```
387    /// use willow_data_model::prelude::*;
388    ///
389    /// assert_eq!(
390    ///     WillowRange::<u8>::from(3..8).map(|x| (x + 1) as u16),
391    ///     WillowRange::<u16>::from(4..9),
392    /// );
393    /// ```
394    pub fn map<U, F>(self, mut f: F) -> WillowRange<U>
395    where
396        F: FnMut(T) -> U,
397    {
398        match self {
399            Self::Closed(Range { start, end }) => (f(start)..f(end)).into(),
400            Self::Open(RangeFrom { start }) => (f(start)..).into(),
401        }
402    }
403
404    /// Unsafely reinterprets a reference to a range as a reference to a range of a different type of boundaries.
405    ///
406    /// # Safety
407    ///
408    /// This is safe only if `&T` and `&U` have an identical layout in memory.
409    pub unsafe fn cast<U>(&self) -> &WillowRange<U> {
410        unsafe { &*(self as *const Self as *const WillowRange<U>) }
411    }
412}
413
414impl<T> WillowRange<T>
415where
416    T: Ord,
417{
418    /// Returns whether `self` is [empty](https://willowprotocol.org/specs/grouping-entries/index.html#range_empty), i.e., whether it [includes](core::ops::RangeBounds::contains) no values.
419    ///
420    /// ```
421    /// use willow_data_model::prelude::*;
422    ///
423    /// assert_eq!(WillowRange::<u8>::from(4..5).is_empty(), false);
424    /// assert_eq!(WillowRange::<u8>::from(255..).is_empty(), false);
425    /// assert_eq!(WillowRange::<u8>::from(4..4).is_empty(), true);
426    /// assert_eq!(WillowRange::<u8>::from(4..3).is_empty(), true);
427    /// ```
428    pub fn is_empty(&self) -> bool {
429        match self {
430            Self::Closed(r) => r.start >= r.end,
431            Self::Open(_) => false,
432        }
433    }
434}
435
436impl<T> WillowRange<T>
437where
438    T: SuccessorExceptForGreatest,
439{
440    /// Returns the [`WillowRange`] which [includes](core::ops::RangeBounds::contains) `t` but no other value.
441    ///
442    /// ```
443    /// use willow_data_model::prelude::*;
444    ///
445    /// assert_eq!(WillowRange::<u8>::singleton(5), (5..6).into());
446    /// assert_eq!(WillowRange::<u8>::singleton(255), (255..).into());
447    /// ```
448    pub fn singleton(t: T) -> Self {
449        match t.try_successor() {
450            Some(succ) => Self::Closed(t..succ),
451            None => Self::Open(t..),
452        }
453    }
454}
455
456impl<T> WillowRange<T>
457where
458    T: LeastElement,
459{
460    /// Returns the `WillowRange` which [includes](core::ops::RangeBounds::contains) every value of type `T`.
461    ///
462    /// ```
463    /// use willow_data_model::prelude::*;
464    ///
465    /// assert_eq!(WillowRange::<u8>::full(), (..).into());
466    /// ```
467    pub fn full() -> Self {
468        (T::least()..).into()
469    }
470
471    /// Returns whether `self` is the full range, i.e., the range which [includes](core::ops::RangeBounds::contains) every value of type `T`.
472    ///
473    /// ```
474    /// use willow_data_model::prelude::*;
475    ///
476    /// assert_eq!(WillowRange::<u8>::full().is_full(), true);
477    /// assert_eq!(WillowRange::<u8>::from(1..).is_full(), false);
478    /// assert_eq!(WillowRange::<u8>::from(0..255).is_full(), false);
479    /// ```
480    pub fn is_full(&self) -> bool {
481        match self {
482            Self::Closed(_) => false,
483            Self::Open(RangeFrom { start }) => start.is_least(),
484        }
485    }
486}
487
488impl<T> LeastElement for WillowRange<T>
489where
490    T: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
491{
492    fn least() -> Self {
493        (T::least()..T::least()).into()
494    }
495}
496
497impl<T> GreatestElement for WillowRange<T>
498where
499    T: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
500{
501    fn greatest() -> Self {
502        (..).into()
503    }
504}
505
506impl<T> LowerSemilattice for WillowRange<T>
507where
508    T: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
509{
510    fn greatest_lower_bound(&self, other: &Self) -> Self {
511        Self::from_bounds(&finite_range::greatest_lower_bound(self, other))
512    }
513}
514
515impl<T> UpperSemilattice for WillowRange<T>
516where
517    T: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
518{
519    fn least_upper_bound(&self, other: &Self) -> Self {
520        Self::from_bounds(&finite_range::least_upper_bound(self, other))
521    }
522}
523
524impl<T> Hash for WillowRange<T>
525where
526    T: Hash + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
527{
528    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
529        if self.is_least() {
530            255u8.hash(state);
531        } else if self.is_greatest() {
532            254u8.hash(state);
533        } else {
534            match self {
535                Self::Closed(inner) => {
536                    253u8.hash(state);
537                    inner.hash(state)
538                }
539                Self::Open(inner) => {
540                    253u8.hash(state);
541                    inner.hash(state)
542                }
543            }
544        }
545    }
546}
willow_data_model/groupings/willow_range.rs

willow_data_model/groupings/
willow_range.rs
