willow_data_model/groupings/
mod.rs

1//! [Groupings](https://willowprotocol.org/specs/grouping-entries/) of entries in 3d space.
2//!
3//! This module implements the [groupings](https://willowprotocol.org/specs/grouping-entries/) used by the Willow specifications:
4//!
5//! - [ranges](https://willowprotocol.org/specs/grouping-entries/#ranges) ([`WillowRange`]),
6//! - [3d ranges](https://willowprotocol.org/specs/grouping-entries/#D3Range) ([`Range3d`]),
7//! - [areas](https://willowprotocol.org/specs/grouping-entries/#areas) ([`Area`]), and
8//! - [areas of interest](https://willowprotocol.org/specs/grouping-entries/#aois) ([`AreaOfInterest`]).
9//!
10//! Our implementations center around two traits: [`Coordinatelike`] describes values which fall into some position in three-dimensional Willow space, and [`Grouping`] describes groupings of values based on their position in three-dimensional Willow space. The [`CoordinatelikeExt`] trait then provides convenient methods for checking which values are included in which groupings.
11//!
12//! ```
13//! use willow_data_model::prelude::*;
14//!
15//! let entry = Entry::builder()
16//!     .namespace_id("family")
17//!     .subspace_id([5; 32])
18//!     .path(Path::<4, 4, 4>::new())
19//!     .timestamp(12345)
20//!     .payload_digest("some_hash")
21//!     .payload_length(17)
22//!     .build().unwrap();
23//!
24//! assert!(entry.wdm_is_in(&Range3d::full()));
25//! assert!(!entry.wdm_is_in(&Area::wdm_empty()));
26//! ```
27
28use crate::prelude::*;
29
30mod willow_range;
31use order_theory::BoundedLowerSemilattice;
32pub use willow_range::*;
33
34mod range_3d;
35pub use range_3d::*;
36
37mod area;
38pub use area::*;
39
40mod area_of_interest;
41pub use area_of_interest::*;
42
43mod keylike;
44pub use keylike::*;
45
46mod coordinatelike;
47pub use coordinatelike::*;
48
49/// A [`WillowRange`] of [SubspaceIds](https://willowprotocol.org/specs/data-model/index.html#SubspaceId).
50///
51/// [TODO example]
52///
53/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#SubspaceRange)
54pub type SubspaceRange<S> = WillowRange<S>;
55
56/// A [`WillowRange`] of [Paths](https://willowprotocol.org/specs/data-model/index.html#Path).
57///
58/// [TODO example]
59///
60/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#PathRange)
61pub type PathRange<const MCL: usize, const MCC: usize, const MPL: usize> =
62    WillowRange<Path<MCL, MCC, MPL>>;
63
64/// A [`WillowRange`] of [Timestamps](https://willowprotocol.org/specs/data-model/index.html#Timestamp).
65///
66/// [TODO example]
67///
68/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#TimeRange)
69pub type TimeRange = WillowRange<Timestamp>;
70
71/// A grouping of entries.
72///
73/// A grouping describes a set of [`Coordinatelike`] values, with [`Grouping::wdm_includes`] providing the membership test. Groupings must form a [`BoundedLowerSemilattice`], with the least element including no values at all, and the partial order corresponding to the subset relation of included values.
74pub trait Grouping<const MCL: usize, const MCC: usize, const MPL: usize, S>:
75    BoundedLowerSemilattice
76{
77    /// Returns `true` iff the given [`Coordinatelike`] value is included in this grouping.
78    fn wdm_includes<Coord>(&self, coord: &Coord) -> bool
79    where
80        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized;
81
82    /// Returns `true` iff every value [included](Grouping::wdm_includes) in `other` is also [included](Grouping::wdm_includes) in `self`.
83    fn wdm_includes_grouping(&self, other: &Self) -> bool {
84        self >= other
85    }
86
87    /// Returns `true` iff every value [included](Grouping::wdm_includes) in `other` is also [included](Grouping::wdm_includes) in `self` *and* `self` and `other` are not equal.
88    fn wdm_strictly_includes_grouping(&self, other: &Self) -> bool {
89        self > other
90    }
91
92    /// Returns `true` iff the given [`Coordinatelike`] value is [included](Grouping::wdm_includes) in the [intersection](Grouping::wdm_intersection) of `self` and `other`.
93    fn wdm_includes_in_intersection<Coord>(&self, other: &Self, coord: &Coord) -> bool
94    where
95        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized,
96    {
97        self.wdm_includes(coord) && other.wdm_includes(coord)
98    }
99
100    /// Returns `true` iff `self` [includes](Grouping::wdm_includes) no values.
101    fn wdm_is_empty(&self) -> bool {
102        self.is_least()
103    }
104
105    /// Returns a grouping which [includes](Grouping::wdm_includes) no values.
106    fn wdm_empty() -> Self {
107        Self::least()
108    }
109
110    /// Returns a grouping which [includes](Grouping::wdm_includes) exactly those values [included](Grouping::wdm_includes) by both `self` and `other`.
111    fn wdm_intersection(&self, other: &Self) -> Self {
112        self.greatest_lower_bound(other)
113    }
114}
willow_data_model/groupings/mod.rs

willow_data_model/groupings/
mod.rs
