willow_data_model/groupings/area_of_interest.rs
1use core::cmp::Ordering;
2use core::fmt::Debug;
3use core::hash::Hash;
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 [`AreaOfInterest`](https://willowprotocol.org/specs/grouping-entries/#Area) is an [`Area`] together with a maximum number of entries it may include, and a maximum sum of total [payload_lengths](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) for the included entries.
16///
17/// A [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of [`u64::MAX`] indicates that there is no limit on the number of entries. A [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size) of [`u64::MAX`] indicates that there is no limit on the total [payload_lengths](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of the entries.
18///
19/// ```
20/// use willow_data_model::prelude::*;
21///
22/// let aoi = AreaOfInterest::new(
23/// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
24/// 5,
25/// 400,
26/// );
27///
28/// assert_eq!(aoi.area(), &Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)));
29/// assert_eq!(aoi.max_count(), 5);
30/// assert_eq!(aoi.max_size(), 400);
31/// ```
32///
33/// [Specification](https://willowprotocol.org/specs/grouping-entries/#aois)
34#[derive(Clone, Debug)]
35#[cfg_attr(feature = "dev", derive(Arbitrary))]
36pub struct AreaOfInterest<const MCL: usize, const MCC: usize, const MPL: usize, S> {
37 area: Area<MCL, MCC, MPL, S>,
38 max_count: u64,
39 max_size: u64,
40}
41
42impl<const MCL: usize, const MCC: usize, const MPL: usize, S> AreaOfInterest<MCL, MCC, MPL, S> {
43 /// Creates a new [`AreaOfInterest`] from its constituent [`Area`], [max_count](https://willowprotocol.org/specs/grouping-entries/#aoi_count), and [max_size](https://willowprotocol.org/specs/grouping-entries/#aoi_size).
44 ///
45 /// A [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of [`u64::MAX`] indicates that there is no limit on the number of entries. A [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size) of [`u64::MAX`] indicates that there is no limit on the total [payload_lengths](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of the entries.
46 ///
47 /// ```
48 /// use willow_data_model::prelude::*;
49 ///
50 /// let aoi = AreaOfInterest::new(
51 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
52 /// 5,
53 /// 400,
54 /// );
55 ///
56 /// assert_eq!(
57 /// aoi.area(),
58 /// &Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
59 /// );
60 /// assert_eq!(aoi.max_count(), 5);
61 /// assert_eq!(aoi.max_size(), 400);
62 /// ```
63 pub fn new(area: Area<MCL, MCC, MPL, S>, max_count: u64, max_size: u64) -> Self {
64 Self {
65 area,
66 max_count,
67 max_size,
68 }
69 }
70
71 /// Returns a reference to the inner [`Area`].
72 ///
73 /// ```
74 /// use willow_data_model::prelude::*;
75 ///
76 /// let aoi = AreaOfInterest::new(
77 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
78 /// 5,
79 /// 400,
80 /// );
81 /// assert_eq!(aoi.area(), &Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)));
82 /// ```
83 ///
84 /// [Definition](https://willowprotocol.org/specs/grouping-entries/#aoi_area).
85 pub fn area(&self) -> &Area<MCL, MCC, MPL, S> {
86 &self.area
87 }
88
89 /// Returns the [max_count](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of entries.
90 ///
91 /// A [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of [`u64::MAX`] indicates that there is no limit on the number of entries in this area of interest.
92 ///
93 /// ```
94 /// use willow_data_model::prelude::*;
95 ///
96 /// let aoi = AreaOfInterest::new(
97 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
98 /// 5,
99 /// 400,
100 /// );
101 /// assert_eq!(aoi.max_count(), 5);
102 /// ```
103 ///
104 /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaPath).
105 pub fn max_count(&self) -> u64 {
106 self.max_count
107 }
108
109 /// Returns the [max_count](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of entries.
110 ///
111 /// A [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size) of [`u64::MAX`] indicates that there is no limit on the total [payload_lengths](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of the entries in this area of interest.
112 ///
113 /// ```
114 /// use willow_data_model::prelude::*;
115 ///
116 /// let aoi = AreaOfInterest::new(
117 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
118 /// 5,
119 /// 400,
120 /// );
121 /// assert_eq!(aoi.max_size(), 400);
122 /// ```
123 ///
124 /// [Definition](https://willowprotocol.org/specs/grouping-entries/#AreaPath).
125 pub fn max_size(&self) -> u64 {
126 self.max_size
127 }
128
129 /// Sets the inner area.
130 pub fn set_area(&mut self, new_area: Area<MCL, MCC, MPL, S>) {
131 self.area = new_area;
132 }
133
134 /// Sets the [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count).
135 ///
136 /// A [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of [`u64::MAX`] indicates that there is no limit on the number of entries in this area of interest.
137 pub fn set_max_count(&mut self, new_max_count: u64) {
138 self.max_count = new_max_count;
139 }
140
141 /// Sets the [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size).
142 ///
143 /// A [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size) of [`u64::MAX`] indicates that there is no limit on the total [payload_lengths](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of the entries in this area of interest.
144 pub fn set_max_size(&mut self, new_max_size: u64) {
145 self.max_size = new_max_size;
146 }
147}
148
149impl<const MCL: usize, const MCC: usize, const MPL: usize, S> AreaOfInterest<MCL, MCC, MPL, S>
150where
151 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
152{
153 /// Returns `true` iff this area of interest cannot possibly contain any entries.
154 ///
155 /// ```
156 /// use willow_data_model::prelude::*;
157 ///
158 /// assert!(
159 /// !AreaOfInterest::new(
160 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
161 /// 5,
162 /// 400,
163 /// ).is_empty(),
164 /// );
165 /// assert!(
166 /// !AreaOfInterest::new(
167 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
168 /// 5,
169 /// 0, // Could still possibly contain entries with a payload_length of zero.
170 /// ).is_empty(),
171 /// );
172 ///
173 /// assert!(
174 /// AreaOfInterest::new(
175 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
176 /// 0,
177 /// 400,
178 /// ).is_empty(),
179 /// );
180 /// assert!(
181 /// AreaOfInterest::new(
182 /// Area::<2, 2, 2, u8>::wdm_empty(),
183 /// 5,
184 /// 400,
185 /// ).is_empty(),
186 /// );
187 /// ```
188 pub fn is_empty(&self) -> bool {
189 self.is_least()
190 }
191
192 /// Returns the [intersection](https://willowprotocol.org/specs/grouping-entries/#aoi_intersection) of `self` and `other`.
193 ///
194 /// ```
195 /// use willow_data_model::prelude::*;
196 ///
197 /// let aoi1 = AreaOfInterest::new(
198 /// Area::<2, 2, 2, u8>::new(None, Path::new(), ..Timestamp::from(17)),
199 /// 5,
200 /// 400,
201 /// );
202 /// let aoi2 = AreaOfInterest::new(
203 /// Area::<2, 2, 2, u8>::new(None, Path::new(), Timestamp::from(14)..),
204 /// 12,
205 /// 32,
206 /// );
207 ///
208 /// assert_eq!(
209 /// aoi1.intersection(&aoi2),
210 /// AreaOfInterest::new(
211 /// Area::<2, 2, 2, u8>::new(
212 /// None,
213 /// Path::new(),
214 /// Timestamp::from(14)..Timestamp::from(17),
215 /// ),
216 /// 5,
217 /// 32,
218 /// ),
219 /// );
220 /// ```
221 pub fn intersection(&self, other: &Self) -> Self {
222 self.greatest_lower_bound(other)
223 }
224}
225
226/// An area is equal to another iff both are empty, or both have equal constituent values.
227///
228/// This implementation assumes that `S` is inhabited by more than one value.
229impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialEq<Self>
230 for AreaOfInterest<MCL, MCC, MPL, S>
231where
232 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
233{
234 fn eq(&self, other: &Self) -> bool {
235 match (self.is_least(), other.is_least()) {
236 (true, true) => true,
237 (true, false) | (false, true) => false,
238 (false, false) => {
239 self.area() == other.area()
240 && self.max_count() == other.max_count()
241 && self.max_size() == other.max_size()
242 }
243 }
244 }
245}
246
247impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Eq
248 for AreaOfInterest<MCL, MCC, MPL, S>
249where
250 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
251{
252}
253
254/// An area is less than another iff is is empty but the other is not, or if its area is less than the other's area and its [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) and [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size) are not strictly greater than those of the other.
255///
256/// This implementation assumes that `S` is inhabited by more than one value.
257impl<const MCL: usize, const MCC: usize, const MPL: usize, S> PartialOrd<Self>
258 for AreaOfInterest<MCL, MCC, MPL, S>
259where
260 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
261{
262 /// An area is less than another iff it has a [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) of zero (and the other doesn't), or if its area is less than the other's area and its [`max_count`](https://willowprotocol.org/specs/grouping-entries/#aoi_count) and [`max_size`](https://willowprotocol.org/specs/grouping-entries/#aoi_size) are not strictly greater than those of the other.
263 ///
264 /// This implementation assumes that `S` is inhabited by more than one value.
265 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
266 match (self.is_least(), other.is_least()) {
267 (true, true) => Some(Ordering::Equal),
268 (true, false) => Some(Ordering::Less),
269 (false, true) => Some(Ordering::Greater),
270 (false, false) => match (
271 self.area().partial_cmp(other.area())?,
272 self.max_count().cmp(&other.max_count()),
273 self.max_size().cmp(&other.max_size()),
274 ) {
275 (Ordering::Equal, Ordering::Equal, Ordering::Equal) => Some(Ordering::Equal),
276 (area_cmp, count_cmp, size_cmp) => {
277 if area_cmp.is_le() && count_cmp.is_le() && size_cmp.is_le() {
278 Some(Ordering::Less)
279 } else if area_cmp.is_ge() && count_cmp.is_ge() && size_cmp.is_ge() {
280 Some(Ordering::Greater)
281 } else {
282 None
283 }
284 }
285 },
286 }
287 }
288}
289
290impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LeastElement
291 for AreaOfInterest<MCL, MCC, MPL, S>
292where
293 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
294{
295 fn least() -> Self {
296 Self::new(Area::least(), 0, 0)
297 }
298
299 fn is_least(&self) -> bool {
300 self.max_count() == 0 || self.area().is_least()
301 }
302}
303
304impl<const MCL: usize, const MCC: usize, const MPL: usize, S> GreatestElement
305 for AreaOfInterest<MCL, MCC, MPL, S>
306where
307 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
308{
309 fn greatest() -> Self {
310 Self::new(Area::greatest(), u64::MAX, u64::MAX)
311 }
312
313 fn is_greatest(&self) -> bool {
314 self.area().is_greatest() && self.max_count() == u64::MAX && self.max_size() == u64::MAX
315 }
316}
317
318impl<const MCL: usize, const MCC: usize, const MPL: usize, S> LowerSemilattice
319 for AreaOfInterest<MCL, MCC, MPL, S>
320where
321 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
322{
323 fn greatest_lower_bound(&self, other: &Self) -> Self {
324 Self::new(
325 self.area().greatest_lower_bound(other.area()),
326 self.max_count().greatest_lower_bound(&other.max_count()),
327 self.max_size().greatest_lower_bound(&other.max_size()),
328 )
329 }
330}
331
332impl<const MCL: usize, const MCC: usize, const MPL: usize, S> UpperSemilattice
333 for AreaOfInterest<MCL, MCC, MPL, S>
334where
335 S: Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
336{
337 fn least_upper_bound(&self, other: &Self) -> Self {
338 if self.is_least() {
339 other.clone()
340 } else if other.is_least() {
341 self.clone()
342 } else {
343 Self::new(
344 self.area().least_upper_bound(other.area()),
345 self.max_count().least_upper_bound(&other.max_count()),
346 self.max_size().least_upper_bound(&other.max_size()),
347 )
348 }
349 }
350}
351
352impl<const MCL: usize, const MCC: usize, const MPL: usize, S> Hash
353 for AreaOfInterest<MCL, MCC, MPL, S>
354where
355 S: Hash + Clone + Ord + PredecessorExceptForLeast + SuccessorExceptForGreatest,
356{
357 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
358 if self.is_least() {
359 255u8.hash(state);
360 } else if self.is_greatest() {
361 254u8.hash(state);
362 } else {
363 253u8.hash(state);
364 self.area.hash(state);
365 self.max_count.hash(state);
366 self.max_size.hash(state);
367 }
368 }
369}