1use std::{
2 cmp::Ordering,
3 fmt::{Display, Formatter, Result},
4 ops::{Deref, Range, RangeInclusive},
5};
6
7use anyhow::anyhow;
8use serde::{Deserialize, Serialize};
9
10use crate::{
11 StdResult,
12 crypto_helper::{MKMapKey, MKTreeNode},
13 entities::BlockNumber,
14};
15
16pub type BlockRangeLength = BlockNumber;
18
19#[derive(Serialize, Deserialize, Clone, Eq, PartialEq, Debug, Hash)]
21pub struct BlockRange {
22 inner_range: Range<BlockNumber>,
23}
24
25impl BlockRange {
26 pub const LENGTH: BlockRangeLength = BlockNumber(15);
29
30 pub fn start(number: BlockNumber) -> BlockNumber {
32 Self::start_with_length(number, Self::LENGTH)
33 }
34
35 pub fn all_block_ranges_in(interval: RangeInclusive<BlockNumber>) -> BlockRangesSequence {
37 BlockRangesSequence::new(interval)
38 }
39
40 pub fn from_block_number(number: BlockNumber) -> Self {
42 Self::from_block_number_and_length(number, Self::LENGTH).unwrap()
44 }
45
46 pub(crate) fn from_block_number_and_length(
48 number: BlockNumber,
49 length: BlockRangeLength,
50 ) -> StdResult<Self> {
51 if length == 0 {
52 return Err(anyhow!(
53 "BlockRange cannot be be computed with a length of 0"
54 ));
55 }
56 let block_range_start = Self::start_with_length(number, length);
57 let block_range_end = block_range_start + length;
58 Ok(Self::from(*block_range_start..*block_range_end))
59 }
60
61 fn start_with_length(number: BlockNumber, length: BlockRangeLength) -> BlockNumber {
63 (number / length) * length
66 }
67}
68
69impl Display for BlockRange {
70 fn fmt(&self, f: &mut Formatter) -> Result {
71 write!(f, "[{},{}[", self.inner_range.start, self.inner_range.end)
72 }
73}
74
75impl Deref for BlockRange {
76 type Target = Range<BlockNumber>;
77
78 fn deref(&self) -> &Self::Target {
79 &self.inner_range
80 }
81}
82
83impl PartialOrd for BlockRange {
84 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
85 Some(std::cmp::Ord::cmp(self, other))
86 }
87}
88
89impl Ord for BlockRange {
90 fn cmp(&self, other: &Self) -> Ordering {
91 match self.inner_range.start.cmp(&other.inner_range.start) {
93 Ordering::Equal => self.inner_range.end.cmp(&other.inner_range.end),
94 order => order,
95 }
96 }
97}
98
99impl From<Range<u64>> for BlockRange {
100 fn from(other: Range<u64>) -> Self {
101 BlockRange {
102 inner_range: BlockNumber(other.start)..BlockNumber(other.end),
103 }
104 }
105}
106
107impl From<BlockRange> for MKTreeNode {
108 fn from(other: BlockRange) -> Self {
109 let start = other.start.to_string();
110 let end = other.end.to_string();
111 let mut bytes = vec![];
112 bytes.extend_from_slice(start.as_bytes());
113 bytes.extend_from_slice("-".as_bytes());
114 bytes.extend_from_slice(end.as_bytes());
115 MKTreeNode::new(bytes)
116 }
117}
118
119impl MKMapKey for BlockRange {}
120
121#[derive(Debug, Clone, Eq, PartialEq)]
126pub struct BlockRangesSequence {
127 start: BlockNumber,
128 end: BlockNumber,
129}
130
131impl BlockRangesSequence {
132 pub fn new(interval: RangeInclusive<BlockNumber>) -> Self {
136 let start = if (*interval.start() % BlockRange::LENGTH) == 0 {
137 *interval.start()
138 } else {
139 BlockRange::start(*interval.start()) + BlockRange::LENGTH
140 };
141 let end = BlockRange::start(*interval.end() + 1);
143
144 if start >= end {
145 Self {
146 start: BlockNumber(0),
147 end: BlockNumber(0),
148 }
149 } else {
150 Self { start, end }
151 }
152 }
153
154 pub fn start(&self) -> BlockNumber {
156 self.start
157 }
158
159 pub fn end(&self) -> BlockNumber {
161 self.end
162 }
163
164 pub fn contains(&self, range: &Range<BlockNumber>) -> bool {
166 self.start <= range.start && range.end <= self.end
167 }
168
169 pub fn is_empty(&self) -> bool {
171 self.start >= self.end
172 }
173
174 pub fn into_vec(self) -> Vec<BlockRange> {
176 self.into_iter().collect()
177 }
178}
179
180impl Iterator for BlockRangesSequence {
181 type Item = BlockRange;
182
183 fn next(&mut self) -> Option<Self::Item> {
184 if BlockRangesSequence::is_empty(self) {
185 return None;
186 }
187
188 let block_range = BlockRange::from_block_number(self.start);
189 self.start = block_range.end;
190 Some(block_range)
191 }
192
193 fn size_hint(&self) -> (usize, Option<usize>) {
194 (*self.start as usize, Some(*self.end as usize))
195 }
196}
197
198impl ExactSizeIterator for BlockRangesSequence {
199 fn len(&self) -> usize {
200 *((self.end - self.start) / BlockRange::LENGTH) as usize
201 }
202}
203
204mod test_extensions {
205 use crate::test::entities_extensions::BlockRangeTestExtension;
206
207 use super::*;
208
209 impl BlockRangeTestExtension for BlockRange {
210 fn new(start: u64, end: u64) -> Self {
211 Self {
212 inner_range: BlockNumber(start)..BlockNumber(end),
213 }
214 }
215
216 fn try_add(&self, other: &BlockRange) -> StdResult<BlockRange> {
217 if self.inner_range.end.max(other.inner_range.end)
218 < self.inner_range.start.min(other.inner_range.start)
219 {
220 return Err(anyhow!(
221 "BlockRange cannot be added as they don't strictly overlap"
222 ));
223 }
224
225 Ok(Self {
226 inner_range: Range {
227 start: self.inner_range.start.min(other.inner_range.start),
228 end: self.inner_range.end.max(other.inner_range.end),
229 },
230 })
231 }
232 }
233}
234
235#[cfg(test)]
236mod tests {
237 use std::ops::Not;
238
239 use crate::test::entities_extensions::BlockRangeTestExtension;
240
241 use super::*;
242
243 #[test]
244 fn test_block_range_contains() {
245 let block_range = BlockRange::new(1, 10);
246
247 assert!(block_range.contains(&BlockNumber(1)));
248 assert!(block_range.contains(&BlockNumber(6)));
249 assert!(block_range.contains(&BlockNumber(9)));
250
251 assert!(block_range.contains(&BlockNumber(0)).not());
252 assert!(block_range.contains(&BlockNumber(10)).not());
254 }
255
256 #[test]
257 fn test_block_range_cmp() {
258 assert_eq!(BlockRange::new(1, 10), BlockRange::new(1, 10));
259 assert_ne!(BlockRange::new(1, 10), BlockRange::new(1, 11));
260 assert_ne!(BlockRange::new(1, 10), BlockRange::new(2, 10));
261 assert_ne!(BlockRange::new(1, 11), BlockRange::new(2, 10));
262
263 assert!(BlockRange::new(1, 10) < BlockRange::new(1, 11));
264 assert!(BlockRange::new(1, 10) < BlockRange::new(2, 10));
265 assert!(BlockRange::new(1, 11) < BlockRange::new(2, 10));
266 }
267
268 #[test]
269 fn test_block_range_try_add() {
270 assert_eq!(
271 BlockRange::new(1, 10).try_add(&BlockRange::new(1, 10)).unwrap(),
272 BlockRange::new(1, 10)
273 );
274 assert_eq!(
275 BlockRange::new(1, 10).try_add(&BlockRange::new(1, 11)).unwrap(),
276 BlockRange::new(1, 11)
277 );
278 assert_eq!(
279 BlockRange::new(1, 10).try_add(&BlockRange::new(2, 10)).unwrap(),
280 BlockRange::new(1, 10)
281 );
282 }
283
284 #[test]
285 fn test_block_range_start() {
286 assert_eq!(BlockRange::start(BlockNumber(0)), 0);
287 assert_eq!(BlockRange::start(BlockNumber(1)), 0);
288 assert_eq!(BlockRange::start(BlockNumber(14)), 0);
289 assert_eq!(BlockRange::start(BlockNumber(15)), 15);
290 assert_eq!(BlockRange::start(BlockNumber(16)), 15);
291 assert_eq!(BlockRange::start(BlockNumber(29)), 15);
292 }
293
294 #[test]
295 fn test_block_range_all_block_ranges_in() {
296 assert_eq!(
297 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(0)).into_vec(),
298 vec![]
299 );
300 assert_eq!(
301 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(1)).into_vec(),
302 vec![]
303 );
304 assert_eq!(
305 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(13)).into_vec(),
306 vec![]
307 );
308 assert_eq!(
309 BlockRange::all_block_ranges_in(BlockNumber(1)..=BlockNumber(14)).into_vec(),
310 vec![]
311 );
312 assert_eq!(
313 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(14)).into_vec(),
314 vec![BlockRange::new(0, 15)]
315 );
316 assert_eq!(
317 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(15)).into_vec(),
318 vec![BlockRange::new(0, 15)]
319 );
320 assert_eq!(
321 BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(29)).into_vec(),
322 vec![BlockRange::new(15, 30)]
323 );
324 assert_eq!(
325 BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(30)).into_vec(),
326 vec![BlockRange::new(15, 30)]
327 );
328 assert_eq!(
329 BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(60)).into_vec(),
330 vec![
331 BlockRange::new(15, 30),
332 BlockRange::new(30, 45),
333 BlockRange::new(45, 60)
334 ]
335 );
336 }
337
338 #[test]
339 fn test_block_ranges_sequence_is_empty() {
340 assert!(BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(0)).is_empty());
341 assert!(BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(1)).is_empty());
342 assert!(BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(13)).is_empty());
343 assert!(BlockRange::all_block_ranges_in(BlockNumber(1)..=BlockNumber(14)).is_empty());
344 assert!(
345 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(14))
346 .is_empty()
347 .not()
348 );
349 assert!(
350 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(15))
351 .is_empty()
352 .not()
353 );
354 assert!(
355 BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(29))
356 .is_empty()
357 .not()
358 );
359 assert!(
360 BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(30))
361 .is_empty()
362 .not()
363 );
364 assert!(
365 BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(60))
366 .is_empty()
367 .not()
368 );
369 }
370
371 #[test]
372 fn test_block_ranges_sequence_len() {
373 assert_eq!(
374 BlockRange::all_block_ranges_in(BlockNumber(0)..=(BlockRange::LENGTH - 2)).len(),
375 0
376 );
377 assert_eq!(
378 BlockRange::all_block_ranges_in(BlockNumber(0)..=(BlockRange::LENGTH - 1)).len(),
379 1
380 );
381 assert_eq!(
382 BlockRange::all_block_ranges_in(BlockNumber(0)..=(BlockRange::LENGTH * 15)).len(),
383 15
384 );
385 }
386
387 #[test]
388 fn test_block_ranges_sequence_contains() {
389 let block_range = BlockRange::new(15, 30);
390 assert!(
391 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(14))
392 .contains(&block_range)
393 .not()
394 );
395 assert!(
396 BlockRange::all_block_ranges_in(BlockNumber(30)..=BlockNumber(59))
397 .contains(&block_range)
398 .not()
399 );
400 assert!(
401 BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(29))
402 .contains(&block_range)
403 );
404 assert!(
405 BlockRange::all_block_ranges_in(BlockNumber(15)..=BlockNumber(29))
406 .contains(&block_range)
407 );
408 assert!(
409 BlockRange::all_block_ranges_in(BlockNumber(15)..=BlockNumber(44))
410 .contains(&block_range)
411 );
412 }
413
414 #[test]
415 fn test_block_range_from_number() {
416 assert_eq!(
417 BlockRange::from_block_number(BlockNumber(0)),
418 BlockRange::new(0, 15)
419 );
420 assert_eq!(
421 BlockRange::from_block_number(BlockNumber(1)),
422 BlockRange::new(0, 15)
423 );
424 assert_eq!(
425 BlockRange::from_block_number(BlockNumber(14)),
426 BlockRange::new(0, 15)
427 );
428 assert_eq!(
429 BlockRange::from_block_number(BlockNumber(15)),
430 BlockRange::new(15, 30)
431 );
432 assert_eq!(
433 BlockRange::from_block_number(BlockNumber(16)),
434 BlockRange::new(15, 30)
435 );
436 assert_eq!(
437 BlockRange::from_block_number(BlockNumber(29)),
438 BlockRange::new(15, 30)
439 );
440 }
441
442 #[test]
443 fn test_block_range_from_number_and_length_with_valid_input() {
444 assert_eq!(
445 BlockRange::from_block_number_and_length(BlockNumber(0), BlockNumber(10)).unwrap(),
446 BlockRange::new(0, 10)
447 );
448 assert_eq!(
449 BlockRange::from_block_number_and_length(BlockNumber(1), BlockNumber(10)).unwrap(),
450 BlockRange::new(0, 10)
451 );
452 assert_eq!(
453 BlockRange::from_block_number_and_length(BlockNumber(9), BlockNumber(10)).unwrap(),
454 BlockRange::new(0, 10)
455 );
456 assert_eq!(
457 BlockRange::from_block_number_and_length(BlockNumber(10), BlockNumber(10)).unwrap(),
458 BlockRange::new(10, 20)
459 );
460 assert_eq!(
461 BlockRange::from_block_number_and_length(BlockNumber(11), BlockNumber(10)).unwrap(),
462 BlockRange::new(10, 20)
463 );
464 assert_eq!(
465 BlockRange::from_block_number_and_length(BlockNumber(19), BlockNumber(10)).unwrap(),
466 BlockRange::new(10, 20)
467 );
468 }
469
470 #[test]
471 fn test_block_range_from_number_and_length_with_invalid_input() {
472 BlockRange::from_block_number_and_length(BlockNumber(10), BlockNumber(0))
473 .expect_err("BlockRange should not be computed with a length of 0");
474 }
475
476 #[test]
477 #[allow(clippy::reversed_empty_ranges)]
479 fn test_building_sequence_with_start_greater_than_end_yield_empty_iterator() {
480 let sequence = BlockRange::all_block_ranges_in(BlockNumber(30)..=BlockNumber(15));
481 assert_eq!(sequence.clone().into_vec(), vec![]);
482 assert!(sequence.is_empty());
483 }
484}