willow_data_model/groupings/
area.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 [`Area`](https://willowprotocol.org/specs/grouping-entries/#Area) is a box in three-dimensional willow space, consisting of all entries matching either a single subspace id or entries of arbitrary subspace ids, prefixed by some [`Path`], and a [`TimeRange`](super::TimeRange).
16///
17/// Areas are the default way by which application developers should aggregate entries. See [the specification](https://willowprotocol.org/specs/grouping-entries/#areas) for more details.
18///
19/// ```
20/// use willow_data_model::prelude::*;
21///
22/// let a1 = Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17));
23///
24/// assert!(a1.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
25/// assert_eq!(a1.subspace(), None);
26///
27/// let a2 = Area::<2, 2, 2, u8>::new(Some(42), Path::new(), Timestamp::from(15)..);
28/// assert_eq!(
29///     a1.wdm_intersection(&a2),
30///     Area::<2, 2, 2, u8>::new(
31///         Some(42),
32///         Path::new(),
33///         Timestamp::from(15)..Timestamp::from(17),
34///     ),
35/// );
36/// ```
37///
38/// [Specification](https://willowprotocol.org/specs/grouping-entries/#Area)
39#[derive(Clone, Debug)]
40#[cfg_attr(feature = "dev", derive(Arbitrary))]
41pub struct Area<const MCL: usize, const MCC: usize, const MPL: usize, S> {
42    subspace: Option<S>,
43    path: Path<MCL, MCC, MPL>,
44    times: TimeRange,
45}
46
47impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S> {
48    /// Creates a new `Area` from its constituent optional subspace id, [`Path`], and [`TimeRange`](super::TimeRange).
49    ///
50    /// ```
51    /// use willow_data_model::prelude::*;
52    ///
53    /// let a = Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17));
54    ///
55    /// assert!(a.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
56    /// assert_eq!(a.subspace(), None);
57    /// ```
58    pub fn new<TR>(subspace: Option<S>, path: Path<MCL, MCC, MPL>, times: TR) -> Self
59    where
60        TR: Into<TimeRange>,
61    {
62        Self {
63            subspace,
64            path,
65            times: times.into(),
66        }
67    }
68
69    /// Returns a reference to the inner subspace id, if any.
70    ///
71    /// ```
72    /// use willow_data_model::prelude::*;
73    ///
74    /// let a1 = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
75    /// assert_eq!(a1.subspace(), Some(&17));
76    ///
77    /// let a2 = Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17));
78    /// assert_eq!(a2.subspace(), None);
79    /// ```
80    ///
81    /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaSubspace).
82    pub fn subspace(&self) -> Option<&S> {
83        self.subspace.as_ref()
84    }
85
86    /// Returns a reference to the inner [`Path`].
87    ///
88    /// ```
89    /// use willow_data_model::prelude::*;
90    ///
91    /// let a = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
92    /// assert_eq!(a.path(), &Path::new());
93    /// ```
94    ///
95    /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaPath).
96    pub fn path(&self) -> &Path<MCL, MCC, MPL> {
97        &self.path
98    }
99
100    /// Returns a reference to the inner [`TimeRange`](super::TimeRange).
101    ///
102    /// ```
103    /// use willow_data_model::prelude::*;
104    ///
105    /// let a = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
106    /// assert_eq!(a.times(), &WillowRange::from(..Timestamp::from(17)));
107    /// ```
108    ///
109    /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaTime).
110    pub fn times(&self) -> &TimeRange {
111        &self.times
112    }
113
114    /// Sets the inner subspace id.
115    pub fn set_subspace(&mut self, new_subspace: Option<S>) {
116        self.subspace = new_subspace;
117    }
118
119    /// Sets the inner [`Path`].
120    pub fn set_path(&mut self, new_path: Path<MCL, MCC, MPL>) {
121        self.path = new_path;
122    }
123
124    /// Sets the inner [`TimeRange`].
125    pub fn set_times<TR>(&mut self, new_range: TR)
126    where
127        TR: Into<TimeRange>,
128    {
129        self.times = new_range.into();
130    }
131
132    /// Returns the [subspace area](https://willowprotocol.org/specs/grouping-entries/#subspace_area) for the given subspace id, i.e., the area which includes exactly the entries of the given subspace id.
133    ///
134    /// ```
135    /// use willow_data_model::prelude::*;
136    ///
137    /// let a = Area::<2, 2, 2, u8>::new_subspace(17);
138    ///
139    /// assert!(a.wdm_includes(&(17, Path::new(), Timestamp::from(9))));
140    /// assert!(!a.wdm_includes(&(18, Path::new(), Timestamp::from(9))));
141    /// assert_eq!(a.subspace(), Some(&17));
142    /// ```
143    pub fn new_subspace(subspace_id: S) -> Self {
144        Self::new(Some(subspace_id), Path::new(), ..)
145    }
146}
147
148impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Grouping<MCL, MCC, MPL, S>
149    for Area<MCL, MCC, MPL, S>
150where
151    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
152{
153    fn wdm_includes<Coord>(&self, coord: &Coord) -> bool
154    where
155        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized,
156    {
157        self.times().contains(&coord.wdm_timestamp())
158            && self
159                .subspace()
160                .map(|subspace_id| subspace_id == coord.wdm_subspace_id())
161                .unwrap_or(true)
162            && coord.wdm_path().is_prefixed_by(self.path())
163    }
164}
165
166/// An area is equal to another iff both include exactly the same values.
167///
168/// This implementation assumes that `S` is inhabited by more than one value.
169impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialEq<Self>
170    for Area<MCL, MCC, MPL, S>
171where
172    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
173{
174    fn eq(&self, other: &Self) -> bool {
175        match (self.wdm_is_empty(), other.wdm_is_empty()) {
176            (true, true) => true,
177            (true, false) | (false, true) => false,
178            (false, false) => {
179                self.subspace() == other.subspace()
180                    && self.path() == other.path()
181                    && self.times() == other.times()
182            }
183        }
184    }
185}
186
187impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Eq for Area<MCL, MCC, MPL, S> where
188    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest
189{
190}
191
192/// An area is less than another iff all values included in the first are also included in the other.
193///
194/// This implementation assumes that `S` is inhabited by more than one value.
195impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialOrd<Self>
196    for Area<MCL, MCC, MPL, S>
197where
198    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
199{
200    /// An area is less than another iff all values included in the first are also included in the other.
201    ///
202    /// This implementation assumes that `S` is inhabited by more than one value.
203    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
204        match (self.wdm_is_empty(), other.wdm_is_empty()) {
205            (true, true) => Some(Ordering::Equal),
206            (true, false) => Some(Ordering::Less),
207            (false, true) => Some(Ordering::Greater),
208            (false, false) => {
209                match (
210                    cmp_subspace(self.subspace(), other.subspace())?,
211                    other.path().prefix_cmp(self.path())?,
212                    self.times().partial_cmp(other.times())?,
213                ) {
214                    (Ordering::Equal, Ordering::Equal, Ordering::Equal) => Some(Ordering::Equal),
215                    (subspaces_cmp, paths_cmp, times_cmp) => {
216                        if subspaces_cmp.is_le() && paths_cmp.is_le() && times_cmp.is_le() {
217                            Some(Ordering::Less)
218                        } else if subspaces_cmp.is_ge() && paths_cmp.is_ge() && times_cmp.is_ge() {
219                            Some(Ordering::Greater)
220                        } else {
221                            None
222                        }
223                    }
224                }
225            }
226        }
227    }
228}
229
230fn cmp_subspace<S: PartialEq>(s1: Option<&S>, s2: Option<&S>) -> Option<Ordering> {
231    match (s1, s2) {
232        (None, None) => Some(Ordering::Equal),
233        (Some(_), None) => Some(Ordering::Less),
234        (None, Some(_)) => Some(Ordering::Greater),
235        (Some(s1), Some(s2)) => {
236            if s1 == s2 {
237                Some(Ordering::Equal)
238            } else {
239                None
240            }
241        }
242    }
243}
244
245impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LeastElement
246    for Area<MCL, MCC, MPL, S>
247where
248    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
249{
250    fn least() -> Self {
251        Self::new(None, Path::new(), TimeRange::least())
252    }
253
254    fn is_least(&self) -> bool {
255        self.times().is_empty()
256    }
257}
258
259impl<const MCL: usize, const MCC: usize, const MPL: usize, S> GreatestElement
260    for Area<MCL, MCC, MPL, S>
261where
262    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
263{
264    fn greatest() -> Self {
265        Self::new(None, Path::new(), TimeRange::full())
266    }
267
268    fn is_greatest(&self) -> bool {
269        self.subspace().is_none() && self.times().is_full() && self.path().is_empty()
270    }
271}
272
273impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LowerSemilattice
274    for Area<MCL, MCC, MPL, S>
275where
276    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
277{
278    fn greatest_lower_bound(&self, other: &Self) -> Self {
279        let subspace = match (self.subspace(), other.subspace()) {
280            (None, None) => None,
281            (Some(s), None) | (None, Some(s)) => Some(s.clone()),
282            (Some(s1), Some(s2)) => {
283                if s1 == s2 {
284                    Some(s1.clone())
285                } else {
286                    return Self::least();
287                }
288            }
289        };
290
291        let path = match self.path().prefix_cmp(other.path()) {
292            Some(Ordering::Greater) | Some(Ordering::Equal) => self.path().clone(),
293            Some(Ordering::Less) => other.path().clone(),
294            None => return Self::least(),
295        };
296
297        Self::new(
298            subspace,
299            path,
300            self.times().greatest_lower_bound(other.times()),
301        )
302    }
303}
304
305impl<const MCL: usize, const MCC: usize, const MPL: usize, S> UpperSemilattice
306    for Area<MCL, MCC, MPL, S>
307where
308    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
309{
310    fn least_upper_bound(&self, other: &Self) -> Self {
311        if self.wdm_is_empty() {
312            other.clone()
313        } else if other.wdm_is_empty() {
314            self.clone()
315        } else {
316            let subspace = match (self.subspace(), other.subspace()) {
317                (None, None) => None,
318                (Some(_), None) | (None, Some(_)) => None,
319                (Some(s1), Some(s2)) => {
320                    if s1 == s2 {
321                        Some(s1.clone())
322                    } else {
323                        None
324                    }
325                }
326            };
327
328            let path = self.path().longest_common_prefix(other.path());
329
330            Self::new(
331                subspace,
332                path,
333                self.times().least_upper_bound(other.times()),
334            )
335        }
336    }
337}
338
339impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S>
340where
341    S: Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
342{
343    /// Returns whether an [`Entry`] of the given [coordinate](Coordinatelike) could possibly cause [prefix pruning](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) in this area.
344    ///
345    /// ```
346    /// use willow_data_model::prelude::*;
347    ///
348    /// let a = Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17));
349    ///
350    /// assert!(a.admits_pruning_by(&(17, Path::new(), Timestamp::from(9))));
351    /// assert!(!a.admits_pruning_by(&(18, Path::new(), Timestamp::from(9))));
352    /// ```
353    pub fn admits_pruning_by<Coord>(&self, coord: &Coord) -> bool
354    where
355        Coord: Coordinatelike<MCL, MCC, MPL, S>,
356    {
357        if let Some(s) = self.subspace() {
358            if s != coord.wdm_subspace_id() {
359                return false;
360            }
361        }
362
363        if coord.wdm_timestamp() < *self.times().start() {
364            return false;
365        }
366
367        coord.wdm_path().is_related_to(self.path())
368    }
369}
370
371impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Area<MCL, MCC, MPL, S>
372where
373    S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
374{
375    /// Returns the [`Area`] which [includes](Grouping::wdm_includes) every [coordinate](Coordinatelike).
376    ///
377    /// ```
378    /// use willow_data_model::prelude::*;
379    ///
380    /// let a = Area::<2, 2, 2, u8>::full();
381    ///
382    /// assert!(a.wdm_includes(&(6, Path::new(), Timestamp::from(9))));
383    /// assert!(a.wdm_includes(&(16, Path::new(), Timestamp::from(9))));
384    /// ```
385    pub fn full() -> Self {
386        Self::greatest()
387    }
388
389    /// Returns whether `self` is the full area, i.e., the area which [includes](Grouping::wdm_includes) every [coordinate](Coordinatelike).
390    ///
391    /// ```
392    /// use willow_data_model::prelude::*;
393    ///
394    /// assert!(Area::<2, 2, 2, u8>::full().is_full());
395    /// assert!(!Area::<2, 2, 2, u8>::new(Some(17), Path::new(), ..Timestamp::from(17)).is_full());
396    /// ```
397    pub fn is_full(&self) -> bool {
398        self.is_greatest()
399    }
400}
401
402impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Hash for Area<MCL, MCC, MPL, S>
403where
404    S: Hash + Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
405{
406    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
407        if self.is_least() {
408            255u8.hash(state);
409        } else if self.is_greatest() {
410            254u8.hash(state);
411        } else {
412            253u8.hash(state);
413            self.subspace.hash(state);
414            self.path.hash(state);
415            self.times.hash(state);
416        }
417    }
418}
willow_data_model/groupings/area.rs

willow_data_model/groupings/
area.rs
