willow_data_model/grouping/
range.rs

1use core::cmp;
2use core::cmp::Ordering;
3
4#[cfg(feature = "dev")]
5use arbitrary::{Arbitrary, Error as ArbitraryError};
6
7use crate::path::Path;
8
9#[derive(Debug, Hash, PartialEq, Eq, Clone, Copy)]
10#[cfg_attr(feature = "dev", derive(Arbitrary))]
11/// Determines whether a [`Range`] is _closed_ or _open_.
12pub enum RangeEnd<T> {
13    /// A [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) consists of a [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) and an [end_value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value).
14    Closed(T),
15    /// An [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) consists only of a [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value).
16    Open,
17}
18
19impl<T: PartialOrd> RangeEnd<T> {
20    /// Return if the [`RangeEnd`] is greater than the given value.
21    pub fn gt_val(&self, val: &T) -> bool {
22        match self {
23            RangeEnd::Open => true,
24            RangeEnd::Closed(end_val) => end_val > val,
25        }
26    }
27}
28
29impl From<&RangeEnd<u64>> for u64 {
30    fn from(value: &RangeEnd<u64>) -> Self {
31        match value {
32            RangeEnd::Closed(val) => *val,
33            RangeEnd::Open => u64::MAX,
34        }
35    }
36}
37
38impl<T: Ord> Ord for RangeEnd<T> {
39    fn cmp(&self, other: &Self) -> Ordering {
40        match self {
41            RangeEnd::Closed(end_value) => match other {
42                RangeEnd::Closed(other_end_value) => end_value.cmp(other_end_value),
43                RangeEnd::Open => Ordering::Less,
44            },
45            RangeEnd::Open => match other {
46                RangeEnd::Closed(_) => Ordering::Greater,
47                RangeEnd::Open => Ordering::Equal,
48            },
49        }
50    }
51}
52
53impl<T: PartialOrd> PartialOrd for RangeEnd<T> {
54    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
55        match self {
56            RangeEnd::Closed(end_value) => match other {
57                RangeEnd::Closed(other_end_value) => end_value.partial_cmp(other_end_value),
58                RangeEnd::Open => Some(Ordering::Less),
59            },
60            RangeEnd::Open => match other {
61                RangeEnd::Closed(_) => Some(Ordering::Greater),
62                RangeEnd::Open => Some(Ordering::Equal),
63            },
64        }
65    }
66}
67
68impl<T> PartialEq<T> for RangeEnd<T>
69where
70    T: PartialEq,
71{
72    fn eq(&self, other: &T) -> bool {
73        match self {
74            RangeEnd::Closed(val) => val.eq(other),
75            RangeEnd::Open => false,
76        }
77    }
78}
79
80impl<T> PartialOrd<T> for RangeEnd<T>
81where
82    T: PartialOrd,
83{
84    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
85        match self {
86            RangeEnd::Closed(val) => val.partial_cmp(other),
87            RangeEnd::Open => Some(Ordering::Greater),
88        }
89    }
90}
91
92impl PartialEq<RangeEnd<u64>> for u64 {
93    fn eq(&self, other: &RangeEnd<u64>) -> bool {
94        match other {
95            RangeEnd::Closed(other_val) => self.eq(other_val),
96            RangeEnd::Open => false,
97        }
98    }
99}
100
101impl PartialOrd<RangeEnd<u64>> for u64 {
102    fn partial_cmp(&self, other: &RangeEnd<u64>) -> Option<Ordering> {
103        match other {
104            RangeEnd::Closed(other_val) => self.partial_cmp(other_val),
105            RangeEnd::Open => Some(Ordering::Less),
106        }
107    }
108}
109
110impl<const MCL: usize, const MCC: usize, const MPL: usize> PartialEq<RangeEnd<Path<MCL, MCC, MPL>>>
111    for Path<MCL, MCC, MPL>
112{
113    fn eq(&self, other: &RangeEnd<Path<MCL, MCC, MPL>>) -> bool {
114        match other {
115            RangeEnd::Closed(other_path) => self.eq(other_path),
116            RangeEnd::Open => false,
117        }
118    }
119}
120
121impl<const MCL: usize, const MCC: usize, const MPL: usize> PartialOrd<RangeEnd<Path<MCL, MCC, MPL>>>
122    for Path<MCL, MCC, MPL>
123{
124    fn partial_cmp(&self, other: &RangeEnd<Path<MCL, MCC, MPL>>) -> Option<Ordering> {
125        match other {
126            RangeEnd::Closed(other_path) => self.partial_cmp(other_path),
127            RangeEnd::Open => Some(Ordering::Less),
128        }
129    }
130}
131
132/// One-dimensional grouping over a type of value.
133///
134/// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#range)
135#[derive(Debug, Hash, PartialEq, Eq, Clone, Copy)]
136pub struct Range<T> {
137    /// A range [includes](https://willowprotocol.org/specs/grouping-entries/index.html#range_include) all values greater than or equal to its [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) **and** less than its [end_value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value)
138    pub start: T,
139    /// A range [includes](https://willowprotocol.org/specs/grouping-entries/index.html#range_include) all values strictly less than its end value (if it is not open) **and** greater than or equal to its [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value).
140    pub end: RangeEnd<T>,
141}
142
143impl<T> Range<T> {
144    /// Returns a new [`Range`].
145    pub fn new(start: T, end: RangeEnd<T>) -> Self {
146        Self { start, end }
147    }
148
149    /// Returns a new [open range](https://willowprotocol.org/specs/grouping-entries/index.html#open_range) from a [start value](https://willowprotocol.org/specs/grouping-entries/index.html#start_value).
150    pub fn new_open(start: T) -> Self {
151        Self {
152            start,
153            end: RangeEnd::Open,
154        }
155    }
156}
157
158impl<T> Range<T>
159where
160    T: PartialOrd,
161{
162    /// Returns a new [closed range](https://willowprotocol.org/specs/grouping-entries/index.html#closed_range) from a [start](https://willowprotocol.org/specs/grouping-entries/index.html#start_value) and [end_value](https://willowprotocol.org/specs/grouping-entries/index.html#end_value), or [`None`] if the resulting range would never [include](https://willowprotocol.org/specs/grouping-entries/index.html#range_include) any values.
163    pub fn new_closed(start: T, end: T) -> Option<Self> {
164        if start < end {
165            return Some(Self {
166                start,
167                end: RangeEnd::Closed(end),
168            });
169        }
170
171        None
172    }
173
174    /// Returns whether a given value is [included](https://willowprotocol.org/specs/grouping-entries/index.html#range_include) by the [`Range`] or not.
175    pub fn includes(&self, value: &T) -> bool {
176        &self.start <= value && self.end.gt_val(value)
177    }
178
179    /// Returns `true` if `other` range is fully [included](https://willowprotocol.org/specs/grouping-entries/index.html#range_include) in this [`Range`].
180    pub fn includes_range(&self, other: &Range<T>) -> bool {
181        self.start <= other.start && self.end >= other.end
182    }
183}
184impl<T> Range<T>
185where
186    T: Ord + Clone,
187{
188    /// Creates the [intersection](https://willowprotocol.org/specs/grouping-entries/index.html#range_intersection) between this [`Range`] and another `Range`, if any.
189    pub fn intersection(&self, other: &Self) -> Option<Self> {
190        let start = cmp::max(&self.start, &other.start);
191        let end = match (&self.end, &other.end) {
192            (RangeEnd::Open, RangeEnd::Closed(b)) => RangeEnd::Closed(b),
193            (RangeEnd::Closed(a), RangeEnd::Closed(b)) => RangeEnd::Closed(a.min(b)),
194            (RangeEnd::Closed(a), RangeEnd::Open) => RangeEnd::Closed(a),
195            (RangeEnd::Open, RangeEnd::Open) => RangeEnd::Open,
196        };
197        match end {
198            RangeEnd::Open => Some(Self::new_open(start.clone())),
199            RangeEnd::Closed(t) if t >= start => {
200                Some(Self::new_closed(start.clone(), t.clone()).unwrap())
201            }
202            RangeEnd::Closed(_) => None,
203        }
204    }
205}
206
207impl<T: Default> Range<T> {
208    /// Creates a new range which [includes](https://willowprotocol.org/specs/grouping-entries/index.html#range_include) everything. This requires `Default::default()` to return the minimal value of type `T` in order to be correct.
209    pub fn full() -> Self {
210        Self::new_open(T::default())
211    }
212}
213
214impl<T: Default> Default for Range<T> {
215    fn default() -> Self {
216        Self::full()
217    }
218}
219
220impl<T: Ord> Ord for Range<T> {
221    fn cmp(&self, other: &Self) -> Ordering {
222        match self.start.cmp(&other.start) {
223            Ordering::Less => Ordering::Less,
224            Ordering::Equal => Ordering::Equal,
225            Ordering::Greater => self.end.cmp(&other.end),
226        }
227    }
228}
229
230impl<T: PartialOrd> PartialOrd for Range<T> {
231    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
232        match self.start.partial_cmp(&other.start) {
233            None => None,
234            Some(Ordering::Less) => Some(Ordering::Less),
235            Some(Ordering::Equal) => Some(Ordering::Equal),
236            Some(Ordering::Greater) => self.end.partial_cmp(&other.end),
237        }
238    }
239}
240
241#[cfg(feature = "dev")]
242impl<'a, T> Arbitrary<'a> for Range<T>
243where
244    T: Arbitrary<'a> + PartialOrd,
245{
246    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
247        let start: T = Arbitrary::arbitrary(u)?;
248        let end: RangeEnd<T> = Arbitrary::arbitrary(u)?;
249
250        if !end.gt_val(&start) {
251            return Err(ArbitraryError::IncorrectFormat);
252        }
253
254        Ok(Self { start, end })
255    }
256}
257
258#[cfg(test)]
259mod tests {
260    use super::*;
261
262    // Range end
263
264    #[test]
265    fn range_end_ord() {
266        assert!(RangeEnd::Closed(0) == RangeEnd::Closed(0));
267        assert!(RangeEnd::Closed(1) < RangeEnd::Closed(2));
268        assert!(RangeEnd::Closed(100) < RangeEnd::Open);
269        assert!(RangeEnd::<usize>::Open == RangeEnd::Open);
270    }
271
272    // Range
273
274    #[test]
275    fn range_new_closed() {
276        assert!(Range::new_closed(0, 0).is_none());
277        assert!(Range::new_closed(2, 1).is_none());
278        assert!(Range::new_closed(5, 10).is_some());
279    }
280
281    #[test]
282    fn range_includes() {
283        let open_range = Range::new_open(20);
284
285        assert!(open_range.includes(&20));
286        assert!(open_range.includes(&30));
287        assert!(!open_range.includes(&10));
288
289        let closed_range = Range::new_closed(5, 10).unwrap();
290
291        assert!(closed_range.includes(&5));
292        assert!(closed_range.includes(&8));
293        assert!(!closed_range.includes(&1));
294    }
295
296    #[test]
297    fn range_includes_range() {
298        let open_range = Range::new_open(0);
299        let open_range_2 = Range::new_open(2);
300
301        assert!(open_range.includes_range(&open_range_2));
302        assert!(!open_range_2.includes_range(&open_range));
303
304        let closed_range = Range::new_closed(0, 10).unwrap();
305        let closed_range_2 = Range::new_closed(5, 10).unwrap();
306        let closed_range_3 = Range::new_closed(5, 15).unwrap();
307
308        assert!(closed_range.includes_range(&closed_range_2));
309        assert!(!closed_range_2.includes_range(&closed_range));
310        assert!(!closed_range.includes_range(&closed_range_3));
311
312        assert!(open_range.includes_range(&closed_range));
313        assert!(!closed_range.includes_range(&open_range_2));
314    }
315
316    #[test]
317    fn range_intersection() {
318        let closed_1 = Range::new_closed(0, 10).unwrap();
319        let closed_2 = Range::new_closed(5, 15).unwrap();
320
321        let intersection_1 = closed_1.intersection(&closed_2);
322
323        assert!(intersection_1.is_some());
324        assert_eq!(intersection_1.unwrap(), Range::new_closed(5, 10).unwrap());
325
326        let open_1 = Range::new_open(5);
327
328        let intersection_2 = open_1.intersection(&closed_1);
329
330        assert!(intersection_2.is_some());
331        assert_eq!(intersection_2.unwrap(), Range::new_closed(5, 10).unwrap());
332
333        let closed_3 = Range::new_closed(20, 25).unwrap();
334
335        let intersection_3 = closed_3.intersection(&closed_1);
336
337        assert!(intersection_3.is_none());
338
339        let open_2 = Range::new_open(50);
340
341        let intersection_4 = closed_3.intersection(&open_2);
342
343        assert!(intersection_4.is_none())
344    }
345}
willow_data_model/grouping/range.rs

willow_data_model/grouping/
range.rs
