willow_data_model/grouping/
range_3d.rs

1#[cfg(feature = "dev")]
2use arbitrary::Arbitrary;
3
4use crate::{
5    entry::{Entry, Timestamp},
6    grouping::{area::Area, range::Range},
7    parameters::SubspaceId,
8    path::Path,
9};
10
11/// A three-dimensional range that includes every Entry included in all three of its ranges.
12///
13/// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3Range).
14#[derive(Debug, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
15pub struct Range3d<const MCL: usize, const MCC: usize, const MPL: usize, S> {
16    /// A range of [`SubspaceId`]s.
17    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#SubspaceRange).
18    subspaces: Range<S>,
19    /// A range of [`Path`]s.
20    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#PathRange).
21    paths: Range<Path<MCL, MCC, MPL>>,
22    /// A range of [`Timestamp`]s.
23    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#TimeRange).
24    times: Range<Timestamp>,
25}
26
27impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S> {
28    /// Creates a new [`Range3d`].
29    pub fn new(
30        subspaces: Range<S>,
31        paths: Range<Path<MCL, MCC, MPL>>,
32        times: Range<Timestamp>,
33    ) -> Self {
34        Range3d {
35            subspaces,
36            paths,
37            times,
38        }
39    }
40
41    /// Returns a reference to the range of [`SubspaceId`]s.
42    ///
43    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#SubspaceRange).
44    pub fn subspaces(&self) -> &Range<S> {
45        &self.subspaces
46    }
47
48    /// Returns a reference to the range of [`Path`]s.
49    ///
50    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#PathRange).
51    pub fn paths(&self) -> &Range<Path<MCL, MCC, MPL>> {
52        &self.paths
53    }
54
55    /// Returns a reference to the range of [`Timestamp`]s.
56    ///
57    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#TimeRange).
58    pub fn times(&self) -> &Range<Timestamp> {
59        &self.times
60    }
61}
62
63impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S>
64where
65    S: Default,
66{
67    /// Creates a new [`Range3d`] that covers everything. Requires `S::default()` to be the least `S` to be correct.
68    pub fn new_full() -> Self {
69        Self::new(
70            Default::default(),
71            Range::new_open(Path::new_empty()),
72            Default::default(),
73        )
74    }
75}
76
77impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S>
78where
79    S: PartialOrd,
80{
81    /// Returns whether an [`Entry`] is [included](https://willowprotocol.org/specs/grouping-entries/index.html#d3_range_include) by this 3d range.
82    pub fn includes_entry<N, PD>(&self, entry: &Entry<MCL, MCC, MPL, N, S, PD>) -> bool {
83        self.subspaces.includes(entry.subspace_id())
84            && self.paths.includes(entry.path())
85            && self.times.includes(&entry.timestamp())
86    }
87}
88
89impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Range3d<MCL, MCC, MPL, S>
90where
91    S: Ord + Clone,
92{
93    /// Returns the intersection between this [`Range3d`] and another.
94    pub fn intersection(&self, other: &Range3d<MCL, MCC, MPL, S>) -> Option<Self> {
95        let paths = self.paths.intersection(&other.paths)?;
96        let times = self.times.intersection(&other.times)?;
97        let subspaces = self.subspaces.intersection(&other.subspaces)?;
98        Some(Self {
99            paths,
100            times,
101            subspaces,
102        })
103    }
104}
105
106impl<const MCL: usize, const MCC: usize, const MPL: usize, S: Default> Default
107    for Range3d<MCL, MCC, MPL, S>
108{
109    /// The default 3dRange, assuming that `S::default()` yields the default SubspaceId.
110    ///
111    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#default_3d_range)
112    fn default() -> Self {
113        Self {
114            subspaces: Range::<S>::default(),
115            paths: Range::new_open(Path::new_empty()),
116            times: Range::new_open(0),
117        }
118    }
119}
120
121impl<const MCL: usize, const MCC: usize, const MPL: usize, S: SubspaceId>
122    From<Area<MCL, MCC, MPL, S>> for Range3d<MCL, MCC, MPL, S>
123{
124    fn from(value: Area<MCL, MCC, MPL, S>) -> Self {
125        let subspaces = match value.subspace() {
126            super::AreaSubspace::Any => Range::new_open(S::default()),
127            super::AreaSubspace::Id(id) => match id.successor() {
128                Some(successor) => {
129                    super::Range::new(id.clone(), super::RangeEnd::Closed(successor))
130                }
131                None => super::Range::new_open(id.clone()),
132            },
133        };
134
135        let paths = match value.path().successor() {
136            Some(succesor) => {
137                super::Range::new(value.path().clone(), super::RangeEnd::Closed(succesor))
138            }
139            None => super::Range::new_open(value.path().clone()),
140        };
141
142        Self {
143            subspaces,
144            paths,
145            times: *value.times(),
146        }
147    }
148}
149
150#[cfg(feature = "dev")]
151impl<'a, const MCL: usize, const MCC: usize, const MPL: usize, S> Arbitrary<'a>
152    for Range3d<MCL, MCC, MPL, S>
153where
154    S: PartialOrd + Arbitrary<'a>,
155{
156    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
157        Ok(Self {
158            subspaces: Arbitrary::arbitrary(u)?,
159            paths: Arbitrary::arbitrary(u)?,
160            times: Arbitrary::arbitrary(u)?,
161        })
162    }
163}
164
165#[cfg(test)]
166mod tests {
167    use crate::path::Component;
168
169    use super::*;
170
171    const MCL: usize = 8;
172    const MCC: usize = 4;
173    const MPL: usize = 16;
174
175    #[test]
176    fn includes_entry() {
177        let entry = Entry::new(
178            0,
179            10,
180            Path::<MCL, MCC, MPL>::new_from_slice(&[Component::new(b"a").unwrap()]).unwrap(),
181            500,
182            10,
183            0,
184        );
185
186        let range_including = Range3d {
187            subspaces: Range::<u64>::new_closed(9, 11).unwrap(),
188            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
189                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
190                Path::new_from_slice(&[Component::new(b"b").unwrap()]).unwrap(),
191            )
192            .unwrap(),
193            times: Range::<Timestamp>::new_closed(400, 600).unwrap(),
194        };
195
196        assert!(range_including.includes_entry(&entry));
197
198        let range_subspaces_excluding = Range3d {
199            subspaces: Range::<u64>::new_closed(11, 13).unwrap(),
200            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
201                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
202                Path::new_from_slice(&[Component::new(b"b").unwrap()]).unwrap(),
203            )
204            .unwrap(),
205            times: Range::<Timestamp>::new_closed(400, 600).unwrap(),
206        };
207
208        assert!(!range_subspaces_excluding.includes_entry(&entry));
209
210        let range_paths_excluding = Range3d {
211            subspaces: Range::<u64>::new_closed(9, 11).unwrap(),
212            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
213                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
214                Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
215            )
216            .unwrap(),
217            times: Range::<Timestamp>::new_closed(400, 600).unwrap(),
218        };
219
220        assert!(!range_paths_excluding.includes_entry(&entry));
221
222        let range_times_excluding = Range3d {
223            subspaces: Range::<u64>::new_closed(9, 11).unwrap(),
224            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
225                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
226                Path::new_from_slice(&[Component::new(b"b").unwrap()]).unwrap(),
227            )
228            .unwrap(),
229            times: Range::<Timestamp>::new_closed(100, 200).unwrap(),
230        };
231
232        assert!(!range_times_excluding.includes_entry(&entry));
233    }
234
235    #[test]
236    fn intersection() {
237        let empty_intersection_subspace = Range3d {
238            subspaces: Range::<u64>::new_closed(11, 13).unwrap(),
239            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
240                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
241                Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
242            )
243            .unwrap(),
244            times: Range::<Timestamp>::new_closed(0, 100).unwrap(),
245        }
246        .intersection(&Range3d {
247            subspaces: Range::<u64>::new_closed(0, 3).unwrap(),
248            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
249                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
250                Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
251            )
252            .unwrap(),
253            times: Range::<Timestamp>::new_closed(0, 100).unwrap(),
254        });
255
256        assert!(empty_intersection_subspace.is_none());
257
258        let empty_intersection_path = Range3d {
259            subspaces: Range::<u64>::new_closed(0, 3).unwrap(),
260            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
261                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
262                Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
263            )
264            .unwrap(),
265            times: Range::<Timestamp>::new_closed(0, 100).unwrap(),
266        }
267        .intersection(&Range3d {
268            subspaces: Range::<u64>::new_closed(0, 3).unwrap(),
269            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
270                Path::new_from_slice(&[Component::new(b"4").unwrap()]).unwrap(),
271                Path::new_from_slice(&[Component::new(b"6").unwrap()]).unwrap(),
272            )
273            .unwrap(),
274            times: Range::<Timestamp>::new_closed(0, 100).unwrap(),
275        });
276
277        assert!(empty_intersection_path.is_none());
278
279        let empty_intersection_time = Range3d {
280            subspaces: Range::<u64>::new_closed(0, 3).unwrap(),
281            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
282                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
283                Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
284            )
285            .unwrap(),
286            times: Range::<Timestamp>::new_closed(0, 100).unwrap(),
287        }
288        .intersection(&Range3d {
289            subspaces: Range::<u64>::new_closed(0, 3).unwrap(),
290            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
291                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
292                Path::new_from_slice(&[Component::new(b"1").unwrap()]).unwrap(),
293            )
294            .unwrap(),
295            times: Range::<Timestamp>::new_closed(200, 300).unwrap(),
296        });
297
298        assert!(empty_intersection_time.is_none());
299
300        let intersection = Range3d {
301            subspaces: Range::<u64>::new_closed(0, 3).unwrap(),
302            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
303                Path::new_from_slice(&[Component::new(b"0").unwrap()]).unwrap(),
304                Path::new_from_slice(&[Component::new(b"6").unwrap()]).unwrap(),
305            )
306            .unwrap(),
307            times: Range::<Timestamp>::new_closed(0, 100).unwrap(),
308        }
309        .intersection(&Range3d {
310            subspaces: Range::<u64>::new_closed(2, 4).unwrap(),
311            paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
312                Path::new_from_slice(&[Component::new(b"3").unwrap()]).unwrap(),
313                Path::new_from_slice(&[Component::new(b"9").unwrap()]).unwrap(),
314            )
315            .unwrap(),
316            times: Range::<Timestamp>::new_closed(50, 150).unwrap(),
317        });
318
319        assert!(intersection.is_some());
320
321        assert_eq!(
322            intersection.unwrap(),
323            Range3d {
324                subspaces: Range::<u64>::new_closed(2, 3).unwrap(),
325                paths: Range::<Path<MCL, MCC, MPL>>::new_closed(
326                    Path::new_from_slice(&[Component::new(b"3").unwrap()]).unwrap(),
327                    Path::new_from_slice(&[Component::new(b"6").unwrap()]).unwrap(),
328                )
329                .unwrap(),
330                times: Range::<Timestamp>::new_closed(50, 100).unwrap(),
331            }
332        )
333    }
334}
willow_data_model/grouping/range_3d.rs

willow_data_model/grouping/
range_3d.rs
