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 crypto_helper::{MKMapKey, MKTreeNode},
12 entities::BlockNumber,
13 StdResult,
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 cfg_test_tools! {
31 pub fn new(start: u64, end: u64) -> Self {
33 Self {
34 inner_range: BlockNumber(start)..BlockNumber(end),
35 }
36 }
37
38 pub fn try_add(&self, other: &BlockRange) -> StdResult<BlockRange> {
40 if self.inner_range.end.max(other.inner_range.end)
41 < self.inner_range.start.min(other.inner_range.start)
42 {
43 return Err(anyhow!(
44 "BlockRange cannot be added as they don't strictly overlap"
45 ));
46 }
47
48 Ok(Self {
49 inner_range: Range {
50 start: self.inner_range.start.min(other.inner_range.start),
51 end: self.inner_range.end.max(other.inner_range.end),
52 },
53 })
54 }
55 }
56
57 pub fn start(number: BlockNumber) -> BlockNumber {
59 Self::start_with_length(number, Self::LENGTH)
60 }
61
62 pub fn all_block_ranges_in(interval: RangeInclusive<BlockNumber>) -> BlockRangesSequence {
64 BlockRangesSequence::new(interval)
65 }
66
67 pub fn from_block_number(number: BlockNumber) -> Self {
69 Self::from_block_number_and_length(number, Self::LENGTH).unwrap()
71 }
72
73 pub(crate) fn from_block_number_and_length(
75 number: BlockNumber,
76 length: BlockRangeLength,
77 ) -> StdResult<Self> {
78 if length == 0 {
79 return Err(anyhow!(
80 "BlockRange cannot be be computed with a length of 0"
81 ));
82 }
83 let block_range_start = Self::start_with_length(number, length);
84 let block_range_end = block_range_start + length;
85 Ok(Self::from(*block_range_start..*block_range_end))
86 }
87
88 fn start_with_length(number: BlockNumber, length: BlockRangeLength) -> BlockNumber {
90 (number / length) * length
93 }
94}
95
96impl Display for BlockRange {
97 fn fmt(&self, f: &mut Formatter) -> Result {
98 write!(f, "[{},{}[", self.inner_range.start, self.inner_range.end)
99 }
100}
101
102impl Deref for BlockRange {
103 type Target = Range<BlockNumber>;
104
105 fn deref(&self) -> &Self::Target {
106 &self.inner_range
107 }
108}
109
110impl PartialOrd for BlockRange {
111 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
112 Some(std::cmp::Ord::cmp(self, other))
113 }
114}
115
116impl Ord for BlockRange {
117 fn cmp(&self, other: &Self) -> Ordering {
118 match self.inner_range.start.cmp(&other.inner_range.start) {
120 Ordering::Equal => self.inner_range.end.cmp(&other.inner_range.end),
121 order => order,
122 }
123 }
124}
125
126impl From<Range<u64>> for BlockRange {
127 fn from(other: Range<u64>) -> Self {
128 BlockRange {
129 inner_range: BlockNumber(other.start)..BlockNumber(other.end),
130 }
131 }
132}
133
134impl From<BlockRange> for MKTreeNode {
135 fn from(other: BlockRange) -> Self {
136 let start = other.start.to_string();
137 let end = other.end.to_string();
138 let mut bytes = vec![];
139 bytes.extend_from_slice(start.as_bytes());
140 bytes.extend_from_slice("-".as_bytes());
141 bytes.extend_from_slice(end.as_bytes());
142 MKTreeNode::new(bytes)
143 }
144}
145
146impl MKMapKey for BlockRange {}
147
148#[derive(Debug, Clone, Eq, PartialEq)]
153pub struct BlockRangesSequence {
154 start: BlockNumber,
155 end: BlockNumber,
156}
157
158impl BlockRangesSequence {
159 pub fn new(interval: RangeInclusive<BlockNumber>) -> Self {
163 let start = if (*interval.start() % BlockRange::LENGTH) == 0 {
164 *interval.start()
165 } else {
166 BlockRange::start(*interval.start()) + BlockRange::LENGTH
167 };
168 let end = BlockRange::start(*interval.end() + 1);
170
171 if start >= end {
172 Self {
173 start: BlockNumber(0),
174 end: BlockNumber(0),
175 }
176 } else {
177 Self { start, end }
178 }
179 }
180
181 pub fn start(&self) -> BlockNumber {
183 self.start
184 }
185
186 pub fn end(&self) -> BlockNumber {
188 self.end
189 }
190
191 pub fn contains(&self, range: &Range<BlockNumber>) -> bool {
193 self.start <= range.start && range.end <= self.end
194 }
195
196 pub fn is_empty(&self) -> bool {
198 self.start >= self.end
199 }
200
201 pub fn into_vec(self) -> Vec<BlockRange> {
203 self.into_iter().collect()
204 }
205}
206
207impl Iterator for BlockRangesSequence {
208 type Item = BlockRange;
209
210 fn next(&mut self) -> Option<Self::Item> {
211 if BlockRangesSequence::is_empty(self) {
212 return None;
213 }
214
215 let block_range = BlockRange::from_block_number(self.start);
216 self.start = block_range.end;
217 Some(block_range)
218 }
219
220 fn size_hint(&self) -> (usize, Option<usize>) {
221 (*self.start as usize, Some(*self.end as usize))
222 }
223}
224
225impl ExactSizeIterator for BlockRangesSequence {
226 fn len(&self) -> usize {
227 *((self.end - self.start) / BlockRange::LENGTH) as usize
228 }
229}
230
231#[cfg(test)]
232mod tests {
233 use std::ops::Not;
234
235 use super::*;
236
237 #[test]
238 fn test_block_range_contains() {
239 let block_range = BlockRange::new(1, 10);
240
241 assert!(block_range.contains(&BlockNumber(1)));
242 assert!(block_range.contains(&BlockNumber(6)));
243 assert!(block_range.contains(&BlockNumber(9)));
244
245 assert!(block_range.contains(&BlockNumber(0)).not());
246 assert!(block_range.contains(&BlockNumber(10)).not());
248 }
249
250 #[test]
251 fn test_block_range_cmp() {
252 assert_eq!(BlockRange::new(1, 10), BlockRange::new(1, 10));
253 assert_ne!(BlockRange::new(1, 10), BlockRange::new(1, 11));
254 assert_ne!(BlockRange::new(1, 10), BlockRange::new(2, 10));
255 assert_ne!(BlockRange::new(1, 11), BlockRange::new(2, 10));
256
257 assert!(BlockRange::new(1, 10) < BlockRange::new(1, 11));
258 assert!(BlockRange::new(1, 10) < BlockRange::new(2, 10));
259 assert!(BlockRange::new(1, 11) < BlockRange::new(2, 10));
260 }
261
262 #[test]
263 fn test_block_range_try_add() {
264 assert_eq!(
265 BlockRange::new(1, 10)
266 .try_add(&BlockRange::new(1, 10))
267 .unwrap(),
268 BlockRange::new(1, 10)
269 );
270 assert_eq!(
271 BlockRange::new(1, 10)
272 .try_add(&BlockRange::new(1, 11))
273 .unwrap(),
274 BlockRange::new(1, 11)
275 );
276 assert_eq!(
277 BlockRange::new(1, 10)
278 .try_add(&BlockRange::new(2, 10))
279 .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}