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

willow_data_model/grouping/
range.rs
