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