willow_data_model/groupings/
range_3d.rs

1use core::fmt::Debug;
2use core::hash::Hash;
3use core::{cmp::Ordering, ops::RangeBounds};
4
5#[cfg(feature = "dev")]
6use arbitrary::Arbitrary;
7
8use order_theory::{
9    GreatestElement, LeastElement, LowerSemilattice, PredecessorExceptForLeast,
10    SuccessorExceptForGreatest, UpperSemilattice,
11};
12
13use crate::prelude::*;
14
15/// An arbitrary box in three-dimensional willow space, consisting of a [`SubspaceRange`](super::SubspaceRange), a [`PathRange`](super::PathRange), and a [`TimeRange`](super::TimeRange).
16///
17/// As an application developer, you probably do not need to interact with 3d ranges, you should prefer [`Areas`](super::Area) — the latter work well with encrypted data, whereas 3d ranges do not define human-meaningful subsets of data when working with encryption.
18///
19/// ```
20/// use willow_data_model::prelude::*;
21///
22/// let r = Range3d::<2, 2, 2, u8>::new(5..=8, .., ..Timestamp::from(17));
23///
24/// assert!(r.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
25/// assert_eq!(r.subspaces(), &WillowRange::from(5u8..9));
26///
27/// let r2 = Range3d::<2, 2, 2, u8>::new(7..8, .., Timestamp::from(15)..);
28/// assert_eq!(
29///     r.wdm_intersection(&r2),
30///     Range3d::<2, 2, 2, u8>::new(7..8, .., Timestamp::from(15)..Timestamp::from(17)),
31/// );
32/// ```
33///
34/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#D3Range)
35#[derive(Clone, Debug)]
36#[cfg_attr(feature = "dev", derive(Arbitrary))]
37pub struct Range3d<const MCL: usize, const MCC: usize, const MPL: usize, S> {
38    subspaces: SubspaceRange<S>,
39    paths: PathRange<MCL, MCC, MPL>,
40    times: TimeRange,
41}
42
43impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S> {
44    /// Creates a new `Range3d` from its constituent [`SubspaceRange`](super::SubspaceRange), [`PathRange`](super::PathRange), and [`TimeRange`](super::TimeRange).
45    ///
46    /// ```
47    /// use willow_data_model::prelude::*;
48    ///
49    /// let r = Range3d::<2, 2, 2, u8>::new(5..=8, .., ..Timestamp::from(17));
50    ///
51    /// assert!(r.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
52    /// assert_eq!(r.subspaces(), &WillowRange::from(5u8..9));
53    /// ```
54    pub fn new<SR, PR, TR>(subspaces: SR, paths: PR, times: TR) -> Self
55    where
56        SR: Into<SubspaceRange<S>>,
57        PR: Into<PathRange<MCL, MCC, MPL>>,
58        TR: Into<TimeRange>,
59    {
60        Self {
61            subspaces: subspaces.into(),
62            paths: paths.into(),
63            times: times.into(),
64        }
65    }
66
67    /// Returns a reference to the inner [`SubspaceRange`](super::SubspaceRange).
68    ///
69    /// ```
70    /// use willow_data_model::prelude::*;
71    ///
72    /// let r = Range3d::<2, 2, 2, u8>::new(5..=8, .., ..Timestamp::from(17));
73    /// assert_eq!(r.subspaces(), &SubspaceRange::from(5u8..9));
74    /// ```
75    ///
76    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3RangeSubspace).
77    pub fn subspaces(&self) -> &SubspaceRange<S> {
78        &self.subspaces
79    }
80
81    /// Returns a reference to the inner [`PathRange`](super::PathRange).
82    ///
83    /// ```
84    /// use willow_data_model::prelude::*;
85    ///
86    /// let r = Range3d::<2, 2, 2, u8>::new(5..=8, .., ..Timestamp::from(17));
87    /// assert_eq!(r.paths(), &WillowRange::full());
88    /// ```
89    ///
90    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3RangePath).
91    pub fn paths(&self) -> &PathRange<MCL, MCC, MPL> {
92        &self.paths
93    }
94
95    /// Returns a reference to the inner [`TimeRange`](super::TimeRange).
96    ///
97    /// ```
98    /// use willow_data_model::prelude::*;
99    ///
100    /// let r = Range3d::<2, 2, 2, u8>::new(5..=8, .., ..Timestamp::from(17));
101    /// assert_eq!(r.times(), &WillowRange::from(..Timestamp::from(17)));
102    /// ```
103    ///
104    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3RangeTime).
105    pub fn times(&self) -> &TimeRange {
106        &self.times
107    }
108
109    /// Sets the inner [`SubspaceRange`](super::SubspaceRange).
110    pub fn set_subspaces<SR>(&mut self, new_range: SR)
111    where
112        SR: Into<SubspaceRange<S>>,
113    {
114        self.subspaces = new_range.into();
115    }
116
117    /// Sets the inner [`PathRange`](super::PathRange).
118    pub fn set_paths<PR>(&mut self, new_range: PR)
119    where
120        PR: Into<PathRange<MCL, MCC, MPL>>,
121    {
122        self.paths = new_range.into();
123    }
124
125    /// Sets the inner [`TimeRange`](super::TimeRange).
126    pub fn set_times<TR>(&mut self, new_range: TR)
127    where
128        TR: Into<TimeRange>,
129    {
130        self.times = new_range.into();
131    }
132}
133
134impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Grouping<MCL, MCC, MPL, S>
135    for Range3d<MCL, MCC, MPL, S>
136where
137    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
138{
139    fn wdm_includes<Coord>(&self, coord: &Coord) -> bool
140    where
141        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized,
142    {
143        self.times().contains(&coord.wdm_timestamp())
144            && self.subspaces().contains(coord.wdm_subspace_id())
145            && self.paths().contains(coord.wdm_path())
146    }
147}
148
149/// A 3d-range is equal to another iff both include exactly the same values.
150impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialEq<Self>
151    for Range3d<MCL, MCC, MPL, S>
152where
153    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
154{
155    fn eq(&self, other: &Self) -> bool {
156        match (self.wdm_is_empty(), other.wdm_is_empty()) {
157            (true, true) => true,
158            (true, false) | (false, true) => false,
159            (false, false) => {
160                self.subspaces == other.subspaces
161                    && self.paths == other.paths
162                    && self.times == other.times
163            }
164        }
165    }
166}
167
168impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Eq for Range3d<MCL, MCC, MPL, S> where
169    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest
170{
171}
172
173/// A 3d-range is less than another iff all values included in the first are also included in the other.
174impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialOrd<Self>
175    for Range3d<MCL, MCC, MPL, S>
176where
177    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
178{
179    /// A 3d-range is less than another iff all values included in the first are also included in the other.
180    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
181        match (self.wdm_is_empty(), other.wdm_is_empty()) {
182            (true, true) => Some(Ordering::Equal),
183            (true, false) => Some(Ordering::Less),
184            (false, true) => Some(Ordering::Greater),
185            (false, false) => {
186                match (
187                    self.subspaces().partial_cmp(other.subspaces())?,
188                    self.paths().partial_cmp(other.paths())?,
189                    self.times().partial_cmp(other.times())?,
190                ) {
191                    (Ordering::Equal, Ordering::Equal, Ordering::Equal) => Some(Ordering::Equal),
192                    (subspaces_cmp, paths_cmp, times_cmp) => {
193                        if subspaces_cmp.is_le() && paths_cmp.is_le() && times_cmp.is_le() {
194                            Some(Ordering::Less)
195                        } else if subspaces_cmp.is_ge() && paths_cmp.is_ge() && times_cmp.is_ge() {
196                            Some(Ordering::Greater)
197                        } else {
198                            None
199                        }
200                    }
201                }
202            }
203        }
204    }
205}
206
207impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LeastElement
208    for Range3d<MCL, MCC, MPL, S>
209where
210    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
211{
212    fn least() -> Self {
213        Self::new(
214            SubspaceRange::least(),
215            PathRange::least(),
216            TimeRange::least(),
217        )
218    }
219
220    fn is_least(&self) -> bool {
221        self.subspaces().is_empty() || self.paths().is_empty() || self.times().is_empty()
222    }
223}
224
225impl<const MCL: usize, const MCC: usize, const MPL: usize, S> GreatestElement
226    for Range3d<MCL, MCC, MPL, S>
227where
228    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
229{
230    fn greatest() -> Self {
231        Self::new(SubspaceRange::full(), PathRange::full(), TimeRange::full())
232    }
233
234    fn is_greatest(&self) -> bool {
235        self.times().is_full() && self.subspaces().is_full() && self.paths().is_full()
236    }
237}
238
239impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LowerSemilattice
240    for Range3d<MCL, MCC, MPL, S>
241where
242    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
243{
244    fn greatest_lower_bound(&self, other: &Self) -> Self {
245        Self::new(
246            self.subspaces().greatest_lower_bound(other.subspaces()),
247            self.paths().greatest_lower_bound(other.paths()),
248            self.times().greatest_lower_bound(other.times()),
249        )
250    }
251}
252
253impl<const MCL: usize, const MCC: usize, const MPL: usize, S> UpperSemilattice
254    for Range3d<MCL, MCC, MPL, S>
255where
256    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
257{
258    fn least_upper_bound(&self, other: &Self) -> Self {
259        if self.wdm_is_empty() {
260            other.clone()
261        } else if other.wdm_is_empty() {
262            self.clone()
263        } else {
264            Self::new(
265                self.subspaces().least_upper_bound(other.subspaces()),
266                self.paths().least_upper_bound(other.paths()),
267                self.times().least_upper_bound(other.times()),
268            )
269        }
270    }
271}
272
273impl<const MCL: usize, const MCC: usize, const MPL: usize, S> From<Area<MCL, MCC, MPL, S>>
274    for Range3d<MCL, MCC, MPL, S>
275where
276    S: Clone + SuccessorExceptForGreatest + LeastElement,
277{
278    fn from(value: Area<MCL, MCC, MPL, S>) -> Self {
279        let subspaces = match value.subspace() {
280            None => WillowRange::full(),
281            Some(s) => WillowRange::singleton(s.clone()),
282        };
283
284        let paths = match value.path().greater_but_not_prefixed() {
285            Some(succ) => WillowRange::from(value.path().clone()..succ),
286            None => WillowRange::from(value.path().clone()..),
287        };
288
289        Self::new(subspaces, paths, value.times().clone())
290    }
291}
292
293impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S>
294where
295    S: Clone + SuccessorExceptForGreatest,
296{
297    /// Returns the [`Range3d`] which [includes](Grouping::wdm_includes) `coord` but no other value.
298    ///
299    /// ```
300    /// use willow_data_model::prelude::*;
301    ///
302    /// let r = Range3d::<2, 2, 2, u8>::singleton(&(6, Path::new(), Timestamp::from(9)));
303    ///
304    /// assert!(r.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
305    /// assert!(!r.wdm_includes(&(16, Path::new(), Timestamp::from(9))));
306    /// ```
307    pub fn singleton<Coord>(coord: &Coord) -> Self
308    where
309        Coord: Coordinatelike<MCL, MCC, MPL, S>,
310    {
311        Self::new(
312            SubspaceRange::singleton(coord.wdm_subspace_id().clone()),
313            PathRange::singleton(coord.wdm_path().clone()),
314            TimeRange::singleton(coord.wdm_timestamp()),
315        )
316    }
317}
318
319impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S>
320where
321    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
322{
323    /// Returns the `Range3d` which [includes](Grouping::wdm_includes) every [coordinate](Coordinatelike).
324    ///
325    /// ```
326    /// use willow_data_model::prelude::*;
327    ///
328    /// let r = Range3d::<2, 2, 2, u8>::full();
329    ///
330    /// assert!(r.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
331    /// assert!(r.wdm_includes(&(16, Path::new(), Timestamp::from(9))));
332    /// ```
333    pub fn full() -> Self {
334        Self::greatest()
335    }
336
337    /// Returns whether `self` is the full 3d range, i.e., the 3d range which [includes](Grouping::wdm_includes) every [coordinate](Coordinatelike).
338    ///
339    /// ```
340    /// use willow_data_model::prelude::*;
341    ///
342    /// assert!(Range3d::<2, 2, 2, u8>::full().is_full());
343    /// assert!(!Range3d::<2, 2, 2, u8>::new(5..=8, .., ..Timestamp::from(17)).is_full());
344    /// ```
345    pub fn is_full(&self) -> bool {
346        self.is_greatest()
347    }
348}
349
350impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Hash for Range3d<MCL, MCC, MPL, S>
351where
352    S: Hash + Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
353{
354    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
355        if self.is_least() {
356            255u8.hash(state);
357        } else if self.is_greatest() {
358            254u8.hash(state);
359        } else {
360            253u8.hash(state);
361            self.subspaces.hash(state);
362            self.paths.hash(state);
363            self.times.hash(state);
364        }
365    }
366}
willow_data_model/groupings/range_3d.rs

willow_data_model/groupings/
range_3d.rs
