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

willow_data_model/grouping/
range_3d.rs
