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//! # #[cfg(feature = "dev")] {
16//! let entry = Entry::builder()
17//!     .namespace_id(Family)
18//!     .subspace_id(Betty)
19//!     .path(Path::<4, 4, 4>::new())
20//!     .timestamp(12345)
21//!     .payload_digest("some_hash")
22//!     .payload_length(17)
23//!     .build().unwrap();
24//!
25//! assert!(entry.wdm_is_in(&Range3d::full()));
26//! # }
27//! ```
28
29use core::fmt;
30
31#[cfg(feature = "dev")]
32use arbitrary::Arbitrary;
33
34use crate::prelude::*;
35
36mod willow_range;
37pub use willow_range::*;
38
39mod range_3d;
40pub use range_3d::*;
41
42mod area;
43pub use area::*;
44
45mod area_of_interest;
46pub use area_of_interest::*;
47
48mod keylike;
49pub use keylike::*;
50
51mod coordinatelike;
52pub use coordinatelike::*;
53
54mod namespaced;
55pub use namespaced::*;
56
57/// A [`WillowRange`] of [SubspaceIds](https://willowprotocol.org/specs/data-model/index.html#SubspaceId).
58///
59/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#SubspaceRange)
60pub type SubspaceRange<S> = WillowRange<S>;
61
62/// A [`WillowRange`] of [Paths](https://willowprotocol.org/specs/data-model/index.html#Path).
63///
64/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#PathRange)
65pub type PathRange<const MCL: usize, const MCC: usize, const MPL: usize> =
66    WillowRange<Path<MCL, MCC, MPL>>;
67
68/// A [`WillowRange`] of [Timestamps](https://willowprotocol.org/specs/data-model/index.html#Timestamp).
69///
70/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#TimeRange)
71pub type TimeRange = WillowRange<Timestamp>;
72
73/// An error returned whenever an operation would result in an empty grouping.
74#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
75#[cfg_attr(feature = "dev", derive(Arbitrary))]
76pub struct EmptyGrouping;
77
78impl fmt::Display for EmptyGrouping {
79    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80        write!(
81            f,
82            "An operation would have resulted in an empty grouping of Willow entries."
83        )
84    }
85}
86
87impl core::error::Error for EmptyGrouping {}
88
89/// A grouping of entries.
90///
91/// A grouping describes a non-empty set of [`Coordinatelike`] values, with [`Grouping::wdm_includes`] providing the membership test. Groupings must implement [`PartialOrd`] as the subset relation.
92pub trait Grouping<const MCL: usize, const MCC: usize, const MPL: usize, S>:
93    PartialOrd + Sized
94{
95    /// Returns `true` iff the given [`Coordinatelike`] value is included in this grouping.
96    fn wdm_includes<Coord>(&self, coord: &Coord) -> bool
97    where
98        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized;
99
100    /// Returns `true` iff every value [included](Grouping::wdm_includes) in `other` is also [included](Grouping::wdm_includes) in `self`.
101    fn wdm_includes_grouping(&self, other: &Self) -> bool {
102        self >= other
103    }
104
105    /// 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.
106    fn wdm_strictly_includes_grouping(&self, other: &Self) -> bool {
107        self > other
108    }
109
110    /// Returns a grouping which [includes](Grouping::wdm_includes) exactly those values [included](Grouping::wdm_includes) by both `self` and `other`. If that set would be empty, returns an [`EmptyGrouping`] error instead.
111    fn wdm_intersection(&self, other: &Self) -> Result<Self, EmptyGrouping>
112    where
113        S: Clone;
114
115    /// Returns `true` iff the given [`Coordinatelike`] value is [included](Grouping::wdm_includes) in both `self` and `other`.
116    fn wdm_includes_in_intersection<Coord>(&self, other: &Self, coord: &Coord) -> bool
117    where
118        Coord: Coordinatelike<MCL, MCC, MPL, S> + ?Sized,
119    {
120        self.wdm_includes(coord) && other.wdm_includes(coord)
121    }
122}
willow_data_model/groupings/mod.rs

willow_data_model/groupings/
mod.rs
