lumina_node/
block_ranges.rs

1//! Ranges utilities
2
3use std::borrow::Borrow;
4use std::fmt::{Debug, Display};
5use std::ops::{
6    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, Not, RangeInclusive, Sub, SubAssign,
7};
8
9use serde::Serialize;
10use smallvec::SmallVec;
11
12/// Type alias of [`RangeInclusive<u64>`].
13///
14/// [`RangeInclusive<u64>`]: std::ops::RangeInclusive
15pub type BlockRange = RangeInclusive<u64>;
16
17/// Errors that can be produced by [`BlockRanges`].
18#[derive(Debug, thiserror::Error, PartialEq, Eq)]
19pub enum BlockRangesError {
20    /// Block ranges must be sorted.
21    #[error("Block ranges are not sorted")]
22    UnsortedBlockRanges,
23
24    /// Not a valid block range.
25    #[error("Invalid block range: {}", .0.display())]
26    InvalidBlockRange(BlockRange),
27
28    /// Provided range overlaps with another one.
29    #[error("Insertion constrain not satisfied: Provided range ({}) overlaps with {}", .0.display(), .1.display())]
30    BlockRangeOverlap(BlockRange, BlockRange),
31
32    /// Provided range do not have any adjacent neightbors.
33    #[error(
34        "Insertion constrain not satified: Provided range ({}) do not have any adjacent neighbors", .0.display()
35    )]
36    NoAdjacentNeighbors(BlockRange),
37}
38
39type Result<T, E = BlockRangesError> = std::result::Result<T, E>;
40
41pub(crate) trait BlockRangeExt {
42    fn display(&self) -> BlockRangeDisplay<'_>;
43    fn validate(&self) -> Result<()>;
44    fn len(&self) -> u64;
45    fn is_adjacent(&self, other: &BlockRange) -> bool;
46    fn is_overlapping(&self, other: &BlockRange) -> bool;
47    fn is_left_of(&self, other: &BlockRange) -> bool;
48    fn is_right_of(&self, other: &BlockRange) -> bool;
49    fn headn(&self, limit: u64) -> Self;
50    fn tailn(&self, limit: u64) -> Self;
51}
52
53pub(crate) struct BlockRangeDisplay<'a>(&'a RangeInclusive<u64>);
54
55impl Display for BlockRangeDisplay<'_> {
56    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
57        write!(f, "{}-{}", self.0.start(), self.0.end())
58    }
59}
60
61impl BlockRangeExt for BlockRange {
62    fn display(&self) -> BlockRangeDisplay<'_> {
63        BlockRangeDisplay(self)
64    }
65
66    fn validate(&self) -> Result<()> {
67        if *self.start() > 0 && self.start() <= self.end() {
68            Ok(())
69        } else {
70            Err(BlockRangesError::InvalidBlockRange(self.to_owned()))
71        }
72    }
73
74    fn len(&self) -> u64 {
75        match self.end().checked_sub(*self.start()) {
76            Some(difference) => difference + 1,
77            None => 0,
78        }
79    }
80
81    fn is_adjacent(&self, other: &BlockRange) -> bool {
82        debug_assert!(self.validate().is_ok());
83        debug_assert!(other.validate().is_ok());
84
85        // End of `self` touches start of `other`
86        //
87        // self:  |------|
88        // other:         |------|
89        if *self.end() == other.start().saturating_sub(1) {
90            return true;
91        }
92
93        // Start of `self` touches end of `other`
94        //
95        // self:          |------|
96        // other: |------|
97        if self.start().saturating_sub(1) == *other.end() {
98            return true;
99        }
100
101        false
102    }
103
104    fn is_overlapping(&self, other: &BlockRange) -> bool {
105        debug_assert!(self.validate().is_ok());
106        debug_assert!(other.validate().is_ok());
107
108        // `self` overlaps with start of `other`
109        //
110        // self:  |------|
111        // other:     |------|
112        if self.start() < other.start() && other.contains(self.end()) {
113            return true;
114        }
115
116        // `self` overlaps with end of `other`
117        //
118        // self:      |------|
119        // other: |------|
120        if self.end() > other.end() && other.contains(self.start()) {
121            return true;
122        }
123
124        // `self` is subset of `other`
125        //
126        // self:    |--|
127        // other: |------|
128        if self.start() >= other.start() && self.end() <= other.end() {
129            return true;
130        }
131
132        // `self` is superset of `other`
133        //
134        // self:  |------|
135        // other:   |--|
136        if self.start() <= other.start() && self.end() >= other.end() {
137            return true;
138        }
139
140        false
141    }
142
143    /// Returns `true` if the whole range of `self` is on the left of `other`.
144    fn is_left_of(&self, other: &BlockRange) -> bool {
145        debug_assert!(self.validate().is_ok());
146        debug_assert!(other.validate().is_ok());
147        self.end() < other.start()
148    }
149
150    /// Returns `true` if the whole range of `self` is on the right of `other`.
151    fn is_right_of(&self, other: &BlockRange) -> bool {
152        debug_assert!(self.validate().is_ok());
153        debug_assert!(other.validate().is_ok());
154        other.end() < self.start()
155    }
156
157    /// Truncate the range so that it contains at most `limit` elements, removing from the tail
158    fn headn(&self, limit: u64) -> Self {
159        if self.is_empty() {
160            return RangeInclusive::new(1, 0);
161        }
162        let start = *self.start();
163        let end = *self.end();
164
165        let Some(adjusted_start) = end.saturating_sub(limit).checked_add(1) else {
166            // overflow can happen only if limit == 0, which is an empty range anyway
167            return RangeInclusive::new(1, 0);
168        };
169
170        u64::max(start, adjusted_start)..=end
171    }
172
173    /// Truncate the range so that it contains at most `limit` elements, removing from the head
174    fn tailn(&self, limit: u64) -> Self {
175        if self.is_empty() {
176            return RangeInclusive::new(1, 0);
177        }
178        let start = *self.start();
179        let end = *self.end();
180
181        let Some(adjusted_end) = start.saturating_add(limit).checked_sub(1) else {
182            return RangeInclusive::new(1, 0);
183        };
184
185        start..=u64::min(end, adjusted_end)
186    }
187}
188
189/// Represents possibly multiple non-overlapping, sorted ranges of header heights
190#[derive(Debug, Clone, PartialEq, Default, Serialize)]
191#[serde(transparent)]
192pub struct BlockRanges(SmallVec<[BlockRange; 2]>);
193
194/// Custom `Deserialize` that validates `BlockRanges`.
195impl<'de> serde::Deserialize<'de> for BlockRanges {
196    fn deserialize<D>(deserializer: D) -> Result<BlockRanges, D::Error>
197    where
198        D: serde::de::Deserializer<'de>,
199    {
200        let raw_ranges = SmallVec::<[RangeInclusive<u64>; 2]>::deserialize(deserializer)?;
201        let ranges = BlockRanges::from_vec(raw_ranges)
202            .map_err(|e| serde::de::Error::custom(e.to_string()))?;
203        Ok(ranges)
204    }
205}
206
207impl BlockRanges {
208    /// Create a new, empty `BlockRanges`.
209    pub fn new() -> BlockRanges {
210        BlockRanges(SmallVec::new())
211    }
212
213    /// Create a `BlockRanges` from a [`SmallVec`].
214    pub fn from_vec(ranges: SmallVec<[BlockRange; 2]>) -> Result<Self> {
215        let mut prev: Option<&RangeInclusive<u64>> = None;
216
217        for range in &ranges {
218            range.validate()?;
219
220            if prev.is_some_and(|prev| range.start() <= prev.end()) {
221                return Err(BlockRangesError::UnsortedBlockRanges);
222            }
223
224            prev = Some(range);
225        }
226
227        Ok(BlockRanges(ranges))
228    }
229
230    /// Returns internal representation.
231    pub fn into_inner(self) -> SmallVec<[BlockRange; 2]> {
232        self.0
233    }
234
235    /// Return whether `BlockRanges` contains provided height.
236    pub fn contains(&self, height: u64) -> bool {
237        self.0.iter().any(|r| r.contains(&height))
238    }
239
240    /// Return how many blocks exist in `BlockRanges`.
241    pub fn len(&self) -> u64 {
242        self.0.iter().map(|r| r.len()).sum()
243    }
244
245    /// Return whether range is empty.
246    pub fn is_empty(&self) -> bool {
247        self.0.iter().all(|r| r.is_empty())
248    }
249
250    /// Return highest height in the range.
251    pub fn head(&self) -> Option<u64> {
252        self.0.last().map(|r| *r.end())
253    }
254
255    pub(crate) fn headn(&self, limit: u64) -> BlockRanges {
256        let mut truncated = BlockRanges::new();
257        let mut len = 0;
258
259        for range in self.0.iter().rev() {
260            if len == limit {
261                break;
262            }
263
264            let r = range.headn(limit - len);
265
266            len += r.len();
267            truncated
268                .insert_relaxed(r)
269                .expect("BlockRanges always holds valid ranges");
270
271            debug_assert_eq!(truncated.len(), len);
272            debug_assert!(len <= limit);
273        }
274
275        truncated
276    }
277
278    /// Return lowest height in the range.
279    pub fn tail(&self) -> Option<u64> {
280        self.0.first().map(|r| *r.start())
281    }
282
283    #[allow(unused)]
284    pub(crate) fn tailn(&self, limit: u64) -> BlockRanges {
285        let mut truncated = BlockRanges::new();
286        let mut len = 0;
287
288        for range in self.0.iter() {
289            if len == limit {
290                break;
291            }
292
293            let r = range.tailn(limit - len);
294
295            len += r.len();
296            truncated
297                .insert_relaxed(r)
298                .expect("BlockRanges always holds valid ranges");
299
300            debug_assert_eq!(truncated.len(), len);
301            debug_assert!(len <= limit);
302        }
303
304        truncated
305    }
306
307    /// Returns first and last index of ranges overlapping or touching provided `range`.
308    fn find_affected_ranges(&self, range: impl Borrow<BlockRange>) -> Option<(usize, usize)> {
309        let range = range.borrow();
310        debug_assert!(range.validate().is_ok());
311
312        let mut start_idx = None;
313        let mut end_idx = None;
314
315        for (i, r) in self.0.iter().enumerate() {
316            if r.is_overlapping(range) || r.is_adjacent(range) {
317                if start_idx.is_none() {
318                    start_idx = Some(i);
319                }
320
321                end_idx = Some(i);
322            } else if end_idx.is_some() {
323                // Ranges are sorted, we can skip checking the rest.
324                break;
325            }
326        }
327
328        Some((start_idx?, end_idx?))
329    }
330
331    /// Checks if `to_insert` is valid range to be inserted into the header store.
332    ///
333    /// This *must* be used when implementing [`Store::insert`].
334    ///
335    /// The constraints are as follows:
336    ///
337    /// * Insertion range must be valid.
338    /// * Insertion range must not overlap with any of the existing ranges.
339    /// * Insertion range must be appended to the left or to the right of an existing range.
340    /// * Insertion is always allowed on empty `BlockRanges`.
341    /// * New HEAD range can be created at the front if it doesn't overlap with existing one.
342    ///
343    /// Returns:
344    ///
345    /// * `Err(_)` if constraints are not met.
346    /// * `Ok(true, false)` if `to_insert` range is going to be merged with its left neighbor.
347    /// * `Ok(false, true)` if `to_insert` range is going to be merged with the right neighbor.
348    /// * `Ok(true, true)` if `to_insert` range is going to be merged with both neighbors.
349    /// * `Ok(false, false)` if `to_insert` range is going to be inserted as a new HEAD range (without merging).
350    ///
351    /// [`Store::insert`]: crate::store::Store::insert
352    pub fn check_insertion_constraints(
353        &self,
354        to_insert: impl Borrow<BlockRange>,
355    ) -> Result<(bool, bool)> {
356        let to_insert = to_insert.borrow();
357        to_insert.validate()?;
358
359        let Some(head_range) = self.0.last() else {
360            // Allow insersion on empty store.
361            return Ok((false, false));
362        };
363
364        if head_range.is_left_of(to_insert) {
365            // Allow adding a new HEAD
366            let prev_exists = head_range.is_adjacent(to_insert);
367            return Ok((prev_exists, false));
368        }
369
370        let Some((first_idx, last_idx)) = self.find_affected_ranges(to_insert) else {
371            return Err(BlockRangesError::NoAdjacentNeighbors(to_insert.to_owned()));
372        };
373
374        let first = &self.0[first_idx];
375        let last = &self.0[last_idx];
376        let num_of_ranges = last_idx - first_idx + 1;
377
378        match num_of_ranges {
379            0 => unreachable!(),
380            1 => {
381                if first.is_overlapping(to_insert) {
382                    Err(BlockRangesError::BlockRangeOverlap(
383                        to_insert.to_owned(),
384                        calc_overlap(to_insert, first, last),
385                    ))
386                } else if first.is_left_of(to_insert) {
387                    Ok((true, false))
388                } else {
389                    Ok((false, true))
390                }
391            }
392            2 => {
393                if first.is_adjacent(to_insert) && last.is_adjacent(to_insert) {
394                    Ok((true, true))
395                } else {
396                    Err(BlockRangesError::BlockRangeOverlap(
397                        to_insert.to_owned(),
398                        calc_overlap(to_insert, first, last),
399                    ))
400                }
401            }
402            _ => Err(BlockRangesError::BlockRangeOverlap(
403                to_insert.to_owned(),
404                calc_overlap(to_insert, first, last),
405            )),
406        }
407    }
408
409    /// Returns the head height and removes it from the ranges.
410    pub fn pop_head(&mut self) -> Option<u64> {
411        let last = self.0.last_mut()?;
412        let head = *last.end();
413
414        if last.len() == 1 {
415            self.0.remove(self.0.len() - 1);
416        } else {
417            *last = *last.start()..=*last.end() - 1;
418        }
419
420        Some(head)
421    }
422
423    /// Returns the tail (lowest) height and removes it from the ranges.
424    pub fn pop_tail(&mut self) -> Option<u64> {
425        let first = self.0.first_mut()?;
426        let tail = *first.start();
427
428        if first.len() == 1 {
429            self.0.remove(0);
430        } else {
431            *first = *first.start() + 1..=*first.end();
432        }
433
434        Some(tail)
435    }
436
437    /// Insert a new range.
438    ///
439    /// This fails only if `range` is not valid. It allows inserting an overlapping range.
440    pub fn insert_relaxed(&mut self, range: impl Borrow<BlockRange>) -> Result<()> {
441        let range = range.borrow();
442        range.validate()?;
443
444        match self.find_affected_ranges(range) {
445            // `range` must be merged with other ranges
446            Some((start_idx, end_idx)) => {
447                let start = *self.0[start_idx].start().min(range.start());
448                let end = *self.0[end_idx].end().max(range.end());
449
450                self.0.drain(start_idx..=end_idx);
451                self.0.insert(start_idx, start..=end);
452            }
453            // `range` can not be merged with other ranges
454            None => {
455                for (i, r) in self.0.iter().enumerate() {
456                    if range.end() < r.start() {
457                        self.0.insert(i, range.to_owned());
458                        return Ok(());
459                    }
460                }
461
462                self.0.push(range.to_owned());
463            }
464        }
465
466        Ok(())
467    }
468
469    /// Remove a range.
470    ///
471    /// This fails only if `range` is not valid. It allows removing non-existing range.
472    pub fn remove_relaxed(&mut self, range: impl Borrow<BlockRange>) -> Result<()> {
473        let range = range.borrow();
474        range.validate()?;
475
476        let Some((start_idx, end_idx)) = self.find_affected_ranges(range) else {
477            // Nothing to remove
478            return Ok(());
479        };
480
481        // Remove old ranges
482        let old_ranges = self
483            .0
484            .drain(start_idx..=end_idx)
485            .collect::<SmallVec<[_; 2]>>();
486
487        // ranges:       |-----|  |----|  |----|
488        // remove:           |--------------|
489        // after remove: |---|              |--|
490        let first_range = old_ranges.first().expect("non empty");
491        let last_range = old_ranges.last().expect("non empty");
492
493        if range.end() < last_range.end() {
494            // Add the right range
495            self.0
496                .insert(start_idx, *range.end() + 1..=*last_range.end());
497        }
498
499        if first_range.start() < range.start() {
500            // Add the left range
501            self.0
502                .insert(start_idx, *first_range.start()..=*range.start() - 1);
503        }
504
505        Ok(())
506    }
507
508    pub(crate) fn edges(&self) -> BlockRanges {
509        let mut edges = BlockRanges::new();
510
511        for range in self.0.iter() {
512            let start = *range.start();
513            let end = *range.end();
514
515            edges
516                .insert_relaxed(start..=start)
517                .expect("BlockRanges always holds valid ranges");
518            edges
519                .insert_relaxed(end..=end)
520                .expect("BlockRanges always holds valid ranges");
521        }
522
523        edges
524    }
525
526    /// Returns `([left], middle, [right])` that can be used for binary search.
527    pub(crate) fn partitions(&self) -> Option<(BlockRanges, u64, BlockRanges)> {
528        let len = self.len();
529
530        if len == 0 {
531            return None;
532        }
533
534        let mut left = BlockRanges::new();
535        let mut right = BlockRanges::new();
536
537        let middle = len / 2;
538        let mut left_len = 0;
539
540        for range in self.0.iter() {
541            let range_len = range.len();
542
543            if left_len + range_len <= middle {
544                // If the whole `range` is up to the `middle`
545                left.insert_relaxed(range.to_owned())
546                    .expect("BlockRanges always holds valid ranges");
547                left_len += range_len;
548            } else if left_len < middle {
549                // If `range` overlaps with `middle`
550                let start = *range.start();
551                let end = *range.end();
552
553                let left_end = start + middle - left_len;
554                let left_range = start..=left_end;
555
556                left_len += left_range.len();
557                left.insert_relaxed(left_range)
558                    .expect("BlockRanges always holds valid ranges");
559
560                if left_end < end {
561                    right
562                        .insert_relaxed(left_end + 1..=end)
563                        .expect("BlockRanges always holds valid ranges");
564                }
565            } else {
566                // If the whole `range` is after the `middle`
567                right
568                    .insert_relaxed(range.to_owned())
569                    .expect("BlockRanges always holds valid ranges");
570            }
571        }
572
573        let middle_height = if left_len < right.len() {
574            right.pop_tail()?
575        } else {
576            left.pop_head()?
577        };
578
579        Some((left, middle_height, right))
580    }
581
582    /// Returns the height that is on the left of `height` parameter.
583    pub(crate) fn left_of(&self, height: u64) -> Option<u64> {
584        for r in self.0.iter().rev() {
585            if r.is_left_of(&(height..=height)) {
586                return Some(*r.end());
587            } else if r.contains(&height) && *r.start() != height {
588                return Some(height - 1);
589            }
590        }
591
592        None
593    }
594
595    /// Returns the height that is on the left of `height` parameter.
596    pub(crate) fn right_of(&self, height: u64) -> Option<u64> {
597        for r in self.0.iter() {
598            if r.is_right_of(&(height..=height)) {
599                return Some(*r.start());
600            } else if r.contains(&height) && *r.end() != height {
601                return Some(height + 1);
602            }
603        }
604
605        None
606    }
607}
608
609impl TryFrom<RangeInclusive<u64>> for BlockRanges {
610    type Error = BlockRangesError;
611
612    fn try_from(value: RangeInclusive<u64>) -> Result<Self, Self::Error> {
613        let mut ranges = BlockRanges::new();
614        ranges.insert_relaxed(value)?;
615        Ok(ranges)
616    }
617}
618
619impl<const N: usize> TryFrom<[RangeInclusive<u64>; N]> for BlockRanges {
620    type Error = BlockRangesError;
621
622    fn try_from(value: [RangeInclusive<u64>; N]) -> Result<Self, Self::Error> {
623        BlockRanges::from_vec(value.into_iter().collect())
624    }
625}
626
627impl TryFrom<&[RangeInclusive<u64>]> for BlockRanges {
628    type Error = BlockRangesError;
629
630    fn try_from(value: &[RangeInclusive<u64>]) -> Result<Self, Self::Error> {
631        BlockRanges::from_vec(value.iter().cloned().collect())
632    }
633}
634
635impl AsRef<[RangeInclusive<u64>]> for BlockRanges {
636    fn as_ref(&self) -> &[RangeInclusive<u64>] {
637        &self.0
638    }
639}
640
641impl AddAssign for BlockRanges {
642    fn add_assign(&mut self, rhs: BlockRanges) {
643        self.add_assign(&rhs);
644    }
645}
646
647impl AddAssign<&BlockRanges> for BlockRanges {
648    fn add_assign(&mut self, rhs: &BlockRanges) {
649        for range in rhs.0.iter() {
650            self.insert_relaxed(range)
651                .expect("BlockRanges always holds valid ranges");
652        }
653    }
654}
655
656impl Add for BlockRanges {
657    type Output = Self;
658
659    fn add(mut self, rhs: BlockRanges) -> Self::Output {
660        self.add_assign(&rhs);
661        self
662    }
663}
664
665impl Add<&BlockRanges> for BlockRanges {
666    type Output = Self;
667
668    fn add(mut self, rhs: &BlockRanges) -> Self::Output {
669        self.add_assign(rhs);
670        self
671    }
672}
673
674impl SubAssign for BlockRanges {
675    fn sub_assign(&mut self, rhs: BlockRanges) {
676        self.sub_assign(&rhs);
677    }
678}
679
680impl SubAssign<&BlockRanges> for BlockRanges {
681    fn sub_assign(&mut self, rhs: &BlockRanges) {
682        for range in rhs.0.iter() {
683            self.remove_relaxed(range)
684                .expect("BlockRanges always holds valid ranges");
685        }
686    }
687}
688
689impl Sub for BlockRanges {
690    type Output = Self;
691
692    fn sub(mut self, rhs: BlockRanges) -> Self::Output {
693        self.sub_assign(&rhs);
694        self
695    }
696}
697
698impl Sub<&BlockRanges> for BlockRanges {
699    type Output = Self;
700
701    fn sub(mut self, rhs: &BlockRanges) -> Self::Output {
702        self.sub_assign(rhs);
703        self
704    }
705}
706
707impl Not for BlockRanges {
708    type Output = Self;
709
710    fn not(self) -> Self::Output {
711        let mut inverse = BlockRanges::new();
712
713        // Start with full range
714        inverse.insert_relaxed(1..=u64::MAX).expect("valid ranges");
715
716        // And remove whatever we have
717        for range in self.0.iter() {
718            inverse
719                .remove_relaxed(range)
720                .expect("BlockRanges always holds valid ranges");
721        }
722
723        inverse
724    }
725}
726
727impl BitOrAssign for BlockRanges {
728    fn bitor_assign(&mut self, rhs: BlockRanges) {
729        self.add_assign(&rhs);
730    }
731}
732
733impl BitOrAssign<&BlockRanges> for BlockRanges {
734    fn bitor_assign(&mut self, rhs: &BlockRanges) {
735        self.add_assign(rhs);
736    }
737}
738
739impl BitOr for BlockRanges {
740    type Output = Self;
741
742    fn bitor(mut self, rhs: BlockRanges) -> Self::Output {
743        self.add_assign(&rhs);
744        self
745    }
746}
747
748impl BitOr<&BlockRanges> for BlockRanges {
749    type Output = Self;
750
751    fn bitor(mut self, rhs: &BlockRanges) -> Self::Output {
752        self.add_assign(rhs);
753        self
754    }
755}
756
757impl BitAndAssign for BlockRanges {
758    fn bitand_assign(&mut self, rhs: BlockRanges) {
759        self.bitand_assign(&rhs);
760    }
761}
762
763impl BitAndAssign<&BlockRanges> for BlockRanges {
764    fn bitand_assign(&mut self, rhs: &BlockRanges) {
765        // !(!A | !B) == (A & B)
766        *self = !(!self.clone() | !rhs.clone());
767    }
768}
769
770impl BitAnd for BlockRanges {
771    type Output = Self;
772
773    fn bitand(mut self, rhs: BlockRanges) -> Self::Output {
774        self.bitand_assign(&rhs);
775        self
776    }
777}
778
779impl BitAnd<&BlockRanges> for BlockRanges {
780    type Output = Self;
781
782    fn bitand(mut self, rhs: &BlockRanges) -> Self::Output {
783        self.bitand_assign(rhs);
784        self
785    }
786}
787
788impl Iterator for BlockRanges {
789    type Item = u64;
790
791    fn next(&mut self) -> Option<Self::Item> {
792        self.pop_tail()
793    }
794}
795
796impl DoubleEndedIterator for BlockRanges {
797    fn next_back(&mut self) -> Option<Self::Item> {
798        self.pop_head()
799    }
800}
801
802impl Display for BlockRanges {
803    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
804        write!(f, "[")?;
805        for (idx, range) in self.0.iter().enumerate() {
806            if idx == 0 {
807                write!(f, "{}", range.display())?;
808            } else {
809                write!(f, ", {}", range.display())?;
810            }
811        }
812        write!(f, "]")
813    }
814}
815
816fn calc_overlap(
817    to_insert: &BlockRange,
818    first_range: &BlockRange,
819    last_range: &BlockRange,
820) -> BlockRange {
821    let start = first_range.start().max(to_insert.start());
822    let end = last_range.end().min(to_insert.end());
823    *start..=*end
824}
825
826#[cfg(test)]
827mod tests {
828    use super::*;
829
830    use crate::test_utils::new_block_ranges;
831
832    #[test]
833    fn range_len() {
834        assert_eq!((0u64..=0).len(), 1);
835        assert_eq!((0u64..=5).len(), 6);
836        assert_eq!((1u64..=2).len(), 2);
837        assert_eq!(RangeInclusive::new(2u64, 1).len(), 0);
838        assert_eq!((10001u64..=20000).len(), 10000);
839    }
840
841    #[test]
842    fn block_ranges_empty() {
843        assert!(new_block_ranges([]).is_empty());
844        assert!(!new_block_ranges([1..=3]).is_empty());
845    }
846
847    #[test]
848    fn block_ranges_head() {
849        assert_eq!(new_block_ranges([]).head(), None);
850        assert_eq!(new_block_ranges([1..=3]).head(), Some(3));
851        assert_eq!(new_block_ranges([1..=3, 6..=9]).head(), Some(9));
852        assert_eq!(new_block_ranges([1..=3, 5..=5, 8..=9]).head(), Some(9));
853    }
854
855    #[test]
856    fn block_ranges_tail() {
857        assert_eq!(new_block_ranges([]).tail(), None);
858        assert_eq!(new_block_ranges([1..=3]).tail(), Some(1));
859        assert_eq!(new_block_ranges([1..=3, 6..=9]).tail(), Some(1));
860        assert_eq!(new_block_ranges([1..=3, 5..=5, 8..=9]).tail(), Some(1));
861    }
862
863    #[test]
864    fn check_range_insert_append() {
865        let (prev_exists, next_exists) = new_block_ranges([])
866            .check_insertion_constraints(1..=5)
867            .unwrap();
868        assert!(!prev_exists);
869        assert!(!next_exists);
870
871        let (prev_exists, next_exists) = new_block_ranges([1..=4])
872            .check_insertion_constraints(5..=5)
873            .unwrap();
874        assert!(prev_exists);
875        assert!(!next_exists);
876
877        let (prev_exists, next_exists) = new_block_ranges([1..=5])
878            .check_insertion_constraints(6..=9)
879            .unwrap();
880        assert!(prev_exists);
881        assert!(!next_exists);
882
883        let (prev_exists, next_exists) = new_block_ranges([6..=8])
884            .check_insertion_constraints(2..=5)
885            .unwrap();
886        assert!(!prev_exists);
887        assert!(next_exists);
888
889        // Allow inserting a new HEAD range
890        let (prev_exists, next_exists) = new_block_ranges([1..=5])
891            .check_insertion_constraints(7..=9)
892            .unwrap();
893        assert!(!prev_exists);
894        assert!(!next_exists);
895    }
896
897    #[test]
898    fn check_range_insert_with_consolidation() {
899        let (prev_exists, next_exists) = new_block_ranges([1..=3, 6..=9])
900            .check_insertion_constraints(4..=5)
901            .unwrap();
902        assert!(prev_exists);
903        assert!(next_exists);
904
905        let (prev_exists, next_exists) = new_block_ranges([1..=2, 5..=5, 8..=9])
906            .check_insertion_constraints(3..=4)
907            .unwrap();
908        assert!(prev_exists);
909        assert!(next_exists);
910
911        let (prev_exists, next_exists) = new_block_ranges([1..=2, 4..=4, 8..=9])
912            .check_insertion_constraints(5..=7)
913            .unwrap();
914        assert!(prev_exists);
915        assert!(next_exists);
916    }
917
918    #[test]
919    fn check_range_insert_overlapping() {
920        let result = new_block_ranges([1..=2])
921            .check_insertion_constraints(1..=1)
922            .unwrap_err();
923        assert_eq!(result, BlockRangesError::BlockRangeOverlap(1..=1, 1..=1));
924
925        let result = new_block_ranges([1..=2])
926            .check_insertion_constraints(2..=2)
927            .unwrap_err();
928        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=2, 2..=2));
929
930        let result = new_block_ranges([1..=4])
931            .check_insertion_constraints(2..=8)
932            .unwrap_err();
933        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=8, 2..=4));
934
935        let result = new_block_ranges([1..=4])
936            .check_insertion_constraints(2..=3)
937            .unwrap_err();
938        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=3, 2..=3));
939
940        let result = new_block_ranges([5..=9])
941            .check_insertion_constraints(1..=5)
942            .unwrap_err();
943        assert_eq!(result, BlockRangesError::BlockRangeOverlap(1..=5, 5..=5));
944
945        let result = new_block_ranges([5..=8])
946            .check_insertion_constraints(2..=8)
947            .unwrap_err();
948        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=8, 5..=8));
949
950        let result = new_block_ranges([1..=3, 6..=9])
951            .check_insertion_constraints(3..=6)
952            .unwrap_err();
953        assert_eq!(result, BlockRangesError::BlockRangeOverlap(3..=6, 3..=6));
954
955        let result = new_block_ranges([1..=3, 5..=6])
956            .check_insertion_constraints(3..=9)
957            .unwrap_err();
958        assert_eq!(result, BlockRangesError::BlockRangeOverlap(3..=9, 3..=6));
959
960        let result = new_block_ranges([2..=3, 5..=6])
961            .check_insertion_constraints(1..=5)
962            .unwrap_err();
963        assert_eq!(result, BlockRangesError::BlockRangeOverlap(1..=5, 2..=5));
964    }
965
966    #[test]
967    fn check_range_insert_invalid_placement() {
968        let result = new_block_ranges([1..=2, 7..=9])
969            .check_insertion_constraints(4..=4)
970            .unwrap_err();
971        assert_eq!(result, BlockRangesError::NoAdjacentNeighbors(4..=4));
972
973        let result = new_block_ranges([1..=2, 8..=9])
974            .check_insertion_constraints(4..=6)
975            .unwrap_err();
976        assert_eq!(result, BlockRangesError::NoAdjacentNeighbors(4..=6));
977
978        let result = new_block_ranges([4..=5, 7..=8])
979            .check_insertion_constraints(1..=2)
980            .unwrap_err();
981        assert_eq!(result, BlockRangesError::NoAdjacentNeighbors(1..=2));
982    }
983
984    #[test]
985    fn test_header_range_creation_ok() {
986        new_block_ranges([1..=3, 5..=8]);
987        new_block_ranges([]);
988        new_block_ranges([1..=1, 1000000..=2000000]);
989    }
990
991    #[test]
992    #[should_panic]
993    fn test_header_range_creation_overlap() {
994        new_block_ranges([1..=3, 2..=5]);
995    }
996
997    #[test]
998    #[should_panic]
999    fn test_header_range_creation_inverse() {
1000        new_block_ranges([1..=3, RangeInclusive::new(9, 5)]);
1001    }
1002
1003    #[test]
1004    #[should_panic]
1005    fn test_header_range_creation_wrong_order() {
1006        new_block_ranges([10..=15, 1..=5]);
1007    }
1008
1009    #[test]
1010    fn pop_head() {
1011        let mut ranges = new_block_ranges([]);
1012        assert_eq!(ranges.pop_head(), None);
1013
1014        let mut ranges = new_block_ranges([1..=4, 6..=8, 10..=10]);
1015        assert_eq!(ranges.pop_head(), Some(10));
1016        assert_eq!(ranges.pop_head(), Some(8));
1017        assert_eq!(ranges.pop_head(), Some(7));
1018        assert_eq!(ranges.pop_head(), Some(6));
1019        assert_eq!(ranges.pop_head(), Some(4));
1020        assert_eq!(ranges.pop_head(), Some(3));
1021        assert_eq!(ranges.pop_head(), Some(2));
1022        assert_eq!(ranges.pop_head(), Some(1));
1023        assert_eq!(ranges.pop_head(), None);
1024    }
1025
1026    #[test]
1027    fn pop_tail() {
1028        let mut ranges = new_block_ranges([]);
1029        assert_eq!(ranges.pop_tail(), None);
1030
1031        let mut ranges = new_block_ranges([1..=4, 6..=8, 10..=10]);
1032        assert_eq!(ranges.pop_tail(), Some(1));
1033        assert_eq!(ranges.pop_tail(), Some(2));
1034        assert_eq!(ranges.pop_tail(), Some(3));
1035        assert_eq!(ranges.pop_tail(), Some(4));
1036        assert_eq!(ranges.pop_tail(), Some(6));
1037        assert_eq!(ranges.pop_tail(), Some(7));
1038        assert_eq!(ranges.pop_tail(), Some(8));
1039        assert_eq!(ranges.pop_tail(), Some(10));
1040        assert_eq!(ranges.pop_tail(), None);
1041    }
1042
1043    #[test]
1044    fn block_ranges_iterator() {
1045        let ranges = new_block_ranges([1..=5, 10..=15]);
1046        let heights: Vec<_> = ranges.collect();
1047        assert_eq!(heights, vec![1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15]);
1048
1049        let empty_heights: Vec<u64> = new_block_ranges([]).collect();
1050        assert_eq!(empty_heights, Vec::<u64>::new())
1051    }
1052
1053    #[test]
1054    fn block_ranges_double_ended_iterator() {
1055        let ranges = new_block_ranges([1..=5, 10..=15]);
1056        let heights: Vec<_> = ranges.rev().collect();
1057        assert_eq!(heights, vec![15, 14, 13, 12, 11, 10, 5, 4, 3, 2, 1]);
1058
1059        let empty_heights: Vec<u64> = new_block_ranges([]).collect();
1060        assert_eq!(empty_heights, Vec::<u64>::new())
1061    }
1062
1063    #[test]
1064    fn validate_check() {
1065        (1..=1).validate().unwrap();
1066        (1..=2).validate().unwrap();
1067        (0..=0).validate().unwrap_err();
1068        (0..=1).validate().unwrap_err();
1069        #[allow(clippy::reversed_empty_ranges)]
1070        (2..=1).validate().unwrap_err();
1071    }
1072
1073    #[test]
1074    fn adjacent_check() {
1075        assert!((3..=5).is_adjacent(&(1..=2)));
1076        assert!((3..=5).is_adjacent(&(6..=8)));
1077
1078        assert!(!(3..=5).is_adjacent(&(1..=1)));
1079        assert!(!(3..=5).is_adjacent(&(7..=8)));
1080    }
1081
1082    #[test]
1083    fn overlapping_check() {
1084        // equal
1085        assert!((3..=5).is_overlapping(&(3..=5)));
1086
1087        // partial set
1088        assert!((3..=5).is_overlapping(&(1..=4)));
1089        assert!((3..=5).is_overlapping(&(1..=3)));
1090        assert!((3..=5).is_overlapping(&(4..=8)));
1091        assert!((3..=5).is_overlapping(&(5..=8)));
1092
1093        // subset
1094        assert!((3..=5).is_overlapping(&(4..=4)));
1095        assert!((3..=5).is_overlapping(&(3..=4)));
1096        assert!((3..=5).is_overlapping(&(4..=5)));
1097
1098        // superset
1099        assert!((3..=5).is_overlapping(&(1..=5)));
1100        assert!((3..=5).is_overlapping(&(1..=6)));
1101        assert!((3..=5).is_overlapping(&(3..=6)));
1102        assert!((3..=5).is_overlapping(&(4..=6)));
1103
1104        // not overlapping
1105        assert!(!(3..=5).is_overlapping(&(1..=1)));
1106        assert!(!(3..=5).is_overlapping(&(7..=8)));
1107    }
1108
1109    #[test]
1110    fn is_left_of_check() {
1111        // range is on the left of
1112        assert!((1..=2).is_left_of(&(3..=4)));
1113        assert!((1..=1).is_left_of(&(3..=4)));
1114
1115        // range is on the right of
1116        assert!(!(3..=4).is_left_of(&(1..=2)));
1117        assert!(!(3..=4).is_left_of(&(1..=1)));
1118
1119        // overlapping is not accepted
1120        assert!(!(1..=3).is_left_of(&(3..=4)));
1121        assert!(!(1..=5).is_left_of(&(3..=4)));
1122        assert!(!(3..=4).is_left_of(&(1..=3)));
1123    }
1124
1125    #[test]
1126    fn left_of() {
1127        let r = new_block_ranges([10..=20, 30..=30, 40..=50]);
1128
1129        assert_eq!(r.left_of(60), Some(50));
1130        assert_eq!(r.left_of(50), Some(49));
1131        assert_eq!(r.left_of(45), Some(44));
1132        assert_eq!(r.left_of(40), Some(30));
1133        assert_eq!(r.left_of(39), Some(30));
1134        assert_eq!(r.left_of(30), Some(20));
1135        assert_eq!(r.left_of(29), Some(20));
1136        assert_eq!(r.left_of(20), Some(19));
1137        assert_eq!(r.left_of(15), Some(14));
1138        assert_eq!(r.left_of(10), None);
1139        assert_eq!(r.left_of(9), None);
1140    }
1141
1142    #[test]
1143    fn is_right_of_check() {
1144        // range is on the right of
1145        assert!((3..=4).is_right_of(&(1..=2)));
1146        assert!((3..=4).is_right_of(&(1..=1)));
1147
1148        // range is on the left of
1149        assert!(!(1..=2).is_right_of(&(3..=4)));
1150        assert!(!(1..=1).is_right_of(&(3..=4)));
1151
1152        // overlapping is not accepted
1153        assert!(!(1..=3).is_right_of(&(3..=4)));
1154        assert!(!(1..=5).is_right_of(&(3..=4)));
1155        assert!(!(3..=4).is_right_of(&(1..=3)));
1156    }
1157
1158    #[test]
1159    fn right_of() {
1160        let r = new_block_ranges([10..=20, 30..=30, 40..=50]);
1161
1162        assert_eq!(r.right_of(1), Some(10));
1163        assert_eq!(r.right_of(9), Some(10));
1164        assert_eq!(r.right_of(10), Some(11));
1165        assert_eq!(r.right_of(15), Some(16));
1166        assert_eq!(r.right_of(19), Some(20));
1167        assert_eq!(r.right_of(20), Some(30));
1168        assert_eq!(r.right_of(29), Some(30));
1169        assert_eq!(r.right_of(30), Some(40));
1170        assert_eq!(r.right_of(39), Some(40));
1171        assert_eq!(r.right_of(40), Some(41));
1172        assert_eq!(r.right_of(45), Some(46));
1173        assert_eq!(r.right_of(49), Some(50));
1174        assert_eq!(r.right_of(50), None);
1175        assert_eq!(r.right_of(60), None);
1176    }
1177
1178    #[test]
1179    fn headn() {
1180        assert_eq!((1..=10).headn(u64::MAX), 1..=10);
1181        assert_eq!((1..=10).headn(20), 1..=10);
1182        assert_eq!((1..=10).headn(10), 1..=10);
1183        assert_eq!((1..=10).headn(5), 6..=10);
1184        assert_eq!((1..=10).headn(1), 10..=10);
1185        assert!((1..=10).headn(0).is_empty());
1186
1187        assert_eq!((0..=u64::MAX).headn(u64::MAX), 1..=u64::MAX);
1188        assert_eq!((0..=u64::MAX).headn(1), u64::MAX..=u64::MAX);
1189        assert!((0..=u64::MAX).headn(0).is_empty());
1190
1191        assert_eq!(
1192            new_block_ranges([1..=10]).headn(u64::MAX),
1193            new_block_ranges([1..=10])
1194        );
1195        assert_eq!(
1196            new_block_ranges([1..=10]).headn(20),
1197            new_block_ranges([1..=10])
1198        );
1199        assert_eq!(
1200            new_block_ranges([1..=10]).headn(10),
1201            new_block_ranges([1..=10])
1202        );
1203        assert_eq!(
1204            new_block_ranges([1..=10]).headn(5),
1205            new_block_ranges([6..=10])
1206        );
1207        assert_eq!(
1208            new_block_ranges([1..=10]).headn(1),
1209            new_block_ranges([10..=10])
1210        );
1211        assert!(new_block_ranges([1..=10]).headn(0).is_empty());
1212
1213        assert_eq!(
1214            new_block_ranges([1..=5, 10..=14]).headn(u64::MAX),
1215            new_block_ranges([1..=5, 10..=14])
1216        );
1217        assert_eq!(
1218            new_block_ranges([1..=5, 10..=14]).headn(20),
1219            new_block_ranges([1..=5, 10..=14])
1220        );
1221        assert_eq!(
1222            new_block_ranges([1..=5, 10..=14]).headn(10),
1223            new_block_ranges([1..=5, 10..=14])
1224        );
1225        assert_eq!(
1226            new_block_ranges([1..=5, 10..=14]).headn(4),
1227            new_block_ranges([11..=14])
1228        );
1229        assert_eq!(
1230            new_block_ranges([1..=5, 10..=14]).headn(5),
1231            new_block_ranges([10..=14])
1232        );
1233        assert_eq!(
1234            new_block_ranges([1..=5, 10..=14]).headn(6),
1235            new_block_ranges([5..=5, 10..=14])
1236        );
1237        assert_eq!(
1238            new_block_ranges([1..=5, 10..=14]).headn(7),
1239            new_block_ranges([4..=5, 10..=14])
1240        );
1241        assert_eq!(
1242            new_block_ranges([1..=5, 10..=14]).headn(1),
1243            new_block_ranges([14..=14])
1244        );
1245        assert!(new_block_ranges([1..=5, 10..=14]).headn(0).is_empty());
1246    }
1247
1248    #[test]
1249    fn tailn() {
1250        assert_eq!((1..=10).tailn(20), 1..=10);
1251        assert_eq!((1..=10).tailn(10), 1..=10);
1252        assert_eq!((1..=10).tailn(5), 1..=5);
1253        assert_eq!((1..=10).tailn(1), 1..=1);
1254        assert!((1..=10).tailn(0).is_empty());
1255
1256        assert_eq!((0..=u64::MAX).tailn(u64::MAX), 0..=(u64::MAX - 1));
1257        assert_eq!((0..=u64::MAX).tailn(1), 0..=0);
1258        assert!((0..=u64::MAX).tailn(0).is_empty());
1259
1260        assert_eq!(
1261            new_block_ranges([1..=10]).tailn(u64::MAX),
1262            new_block_ranges([1..=10])
1263        );
1264        assert_eq!(
1265            new_block_ranges([1..=10]).tailn(20),
1266            new_block_ranges([1..=10])
1267        );
1268        assert_eq!(
1269            new_block_ranges([1..=10]).tailn(10),
1270            new_block_ranges([1..=10])
1271        );
1272        assert_eq!(
1273            new_block_ranges([1..=10]).tailn(5),
1274            new_block_ranges([1..=5])
1275        );
1276        assert_eq!(
1277            new_block_ranges([1..=10]).tailn(1),
1278            new_block_ranges([1..=1])
1279        );
1280        assert!(new_block_ranges([1..=10]).tailn(0).is_empty());
1281
1282        assert_eq!(
1283            new_block_ranges([1..=5, 10..=14]).tailn(u64::MAX),
1284            new_block_ranges([1..=5, 10..=14])
1285        );
1286        assert_eq!(
1287            new_block_ranges([1..=5, 10..=14]).tailn(20),
1288            new_block_ranges([1..=5, 10..=14])
1289        );
1290        assert_eq!(
1291            new_block_ranges([1..=5, 10..=14]).tailn(10),
1292            new_block_ranges([1..=5, 10..=14])
1293        );
1294        assert_eq!(
1295            new_block_ranges([1..=5, 10..=14]).tailn(4),
1296            new_block_ranges([1..=4])
1297        );
1298        assert_eq!(
1299            new_block_ranges([1..=5, 10..=14]).tailn(5),
1300            new_block_ranges([1..=5])
1301        );
1302        assert_eq!(
1303            new_block_ranges([1..=5, 10..=14]).tailn(6),
1304            new_block_ranges([1..=5, 10..=10])
1305        );
1306        assert_eq!(
1307            new_block_ranges([1..=5, 10..=14]).tailn(7),
1308            new_block_ranges([1..=5, 10..=11])
1309        );
1310        assert_eq!(
1311            new_block_ranges([1..=5, 10..=14]).tailn(1),
1312            new_block_ranges([1..=1])
1313        );
1314        assert!(new_block_ranges([1..=5, 10..=14]).tailn(0).is_empty());
1315    }
1316
1317    #[test]
1318    fn find_affected_ranges() {
1319        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
1320
1321        assert_eq!(ranges.find_affected_ranges(28..=28), None);
1322        assert_eq!(ranges.find_affected_ranges(1..=15), None);
1323        assert_eq!(ranges.find_affected_ranges(1..=28), None);
1324        assert_eq!(ranges.find_affected_ranges(3..=28), None);
1325        assert_eq!(ranges.find_affected_ranges(1..=29), Some((0, 0)));
1326        assert_eq!(ranges.find_affected_ranges(1..=30), Some((0, 0)));
1327        assert_eq!(ranges.find_affected_ranges(1..=49), Some((0, 0)));
1328        assert_eq!(ranges.find_affected_ranges(1..=50), Some((0, 0)));
1329        assert_eq!(ranges.find_affected_ranges(1..=51), Some((0, 0)));
1330
1331        assert_eq!(ranges.find_affected_ranges(40..=51), Some((0, 0)));
1332        assert_eq!(ranges.find_affected_ranges(50..=51), Some((0, 0)));
1333        assert_eq!(ranges.find_affected_ranges(51..=51), Some((0, 0)));
1334
1335        assert_eq!(ranges.find_affected_ranges(40..=79), Some((0, 1)));
1336        assert_eq!(ranges.find_affected_ranges(50..=79), Some((0, 1)));
1337        assert_eq!(ranges.find_affected_ranges(51..=79), Some((0, 1)));
1338        assert_eq!(ranges.find_affected_ranges(50..=80), Some((0, 1)));
1339
1340        assert_eq!(ranges.find_affected_ranges(52..=52), None);
1341        assert_eq!(ranges.find_affected_ranges(52..=78), None);
1342        assert_eq!(ranges.find_affected_ranges(52..=79), Some((1, 1)));
1343        assert_eq!(ranges.find_affected_ranges(52..=80), Some((1, 1)));
1344        assert_eq!(ranges.find_affected_ranges(52..=129), Some((1, 2)));
1345        assert_eq!(ranges.find_affected_ranges(99..=129), Some((1, 2)));
1346        assert_eq!(ranges.find_affected_ranges(100..=129), Some((1, 2)));
1347        assert_eq!(ranges.find_affected_ranges(101..=129), Some((1, 2)));
1348        assert_eq!(ranges.find_affected_ranges(101..=128), Some((1, 1)));
1349        assert_eq!(ranges.find_affected_ranges(51..=129), Some((0, 2)));
1350
1351        assert_eq!(ranges.find_affected_ranges(102..=128), None);
1352        assert_eq!(ranges.find_affected_ranges(102..=120), None);
1353        assert_eq!(ranges.find_affected_ranges(120..=128), None);
1354
1355        assert_eq!(ranges.find_affected_ranges(40..=129), Some((0, 2)));
1356        assert_eq!(ranges.find_affected_ranges(40..=140), Some((0, 2)));
1357        assert_eq!(ranges.find_affected_ranges(20..=140), Some((0, 2)));
1358        assert_eq!(ranges.find_affected_ranges(20..=150), Some((0, 2)));
1359        assert_eq!(ranges.find_affected_ranges(20..=151), Some((0, 2)));
1360        assert_eq!(ranges.find_affected_ranges(20..=160), Some((0, 2)));
1361
1362        assert_eq!(ranges.find_affected_ranges(120..=129), Some((2, 2)));
1363        assert_eq!(ranges.find_affected_ranges(120..=128), None);
1364        assert_eq!(ranges.find_affected_ranges(120..=130), Some((2, 2)));
1365        assert_eq!(ranges.find_affected_ranges(120..=131), Some((2, 2)));
1366        assert_eq!(ranges.find_affected_ranges(140..=145), Some((2, 2)));
1367        assert_eq!(ranges.find_affected_ranges(140..=150), Some((2, 2)));
1368        assert_eq!(ranges.find_affected_ranges(140..=155), Some((2, 2)));
1369        assert_eq!(ranges.find_affected_ranges(152..=155), None);
1370        assert_eq!(ranges.find_affected_ranges(152..=178), None);
1371        assert_eq!(ranges.find_affected_ranges(152..=152), None);
1372
1373        assert_eq!(new_block_ranges([]).find_affected_ranges(1..=1), None);
1374
1375        assert_eq!(new_block_ranges([1..=2]).find_affected_ranges(6..=9), None);
1376        assert_eq!(new_block_ranges([4..=8]).find_affected_ranges(1..=2), None);
1377        assert_eq!(
1378            new_block_ranges([4..=8, 20..=30]).find_affected_ranges(1..=2),
1379            None
1380        );
1381        assert_eq!(
1382            new_block_ranges([4..=8, 20..=30]).find_affected_ranges(10..=12),
1383            None
1384        );
1385        assert_eq!(
1386            new_block_ranges([4..=8, 20..=30]).find_affected_ranges(32..=32),
1387            None
1388        );
1389    }
1390
1391    #[test]
1392    fn insert_relaxed_disjoined() {
1393        let mut r = BlockRanges::default();
1394        r.insert_relaxed(10..=10).unwrap();
1395        assert_eq!(&r.0[..], &[10..=10][..]);
1396
1397        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
1398
1399        let mut r = ranges.clone();
1400        r.insert_relaxed(1..=1).unwrap();
1401        assert_eq!(&r.0[..], &[1..=1, 30..=50, 80..=100, 130..=150][..]);
1402
1403        let mut r = ranges.clone();
1404        r.insert_relaxed(1..=28).unwrap();
1405        assert_eq!(&r.0[..], &[1..=28, 30..=50, 80..=100, 130..=150][..]);
1406
1407        let mut r = ranges.clone();
1408        r.insert_relaxed(10..=28).unwrap();
1409        assert_eq!(&r.0[..], &[10..=28, 30..=50, 80..=100, 130..=150][..]);
1410
1411        let mut r = ranges.clone();
1412        r.insert_relaxed(52..=78).unwrap();
1413        assert_eq!(&r.0[..], &[30..=50, 52..=78, 80..=100, 130..=150][..]);
1414
1415        let mut r = ranges.clone();
1416        r.insert_relaxed(102..=128).unwrap();
1417        assert_eq!(&r.0[..], &[30..=50, 80..=100, 102..=128, 130..=150][..]);
1418
1419        let mut r = ranges.clone();
1420        r.insert_relaxed(152..=152).unwrap();
1421        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150, 152..=152][..]);
1422
1423        let mut r = ranges.clone();
1424        r.insert_relaxed(152..=170).unwrap();
1425        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150, 152..=170][..]);
1426
1427        let mut r = ranges.clone();
1428        r.insert_relaxed(160..=170).unwrap();
1429        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150, 160..=170][..]);
1430    }
1431
1432    #[test]
1433    fn insert_relaxed_intersected() {
1434        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
1435
1436        let mut r = ranges.clone();
1437        r.insert_relaxed(29..=29).unwrap();
1438        assert_eq!(&r.0[..], &[29..=50, 80..=100, 130..=150][..]);
1439
1440        let mut r = ranges.clone();
1441        r.insert_relaxed(1..=29).unwrap();
1442        assert_eq!(&r.0[..], &[1..=50, 80..=100, 130..=150][..]);
1443
1444        let mut r = ranges.clone();
1445        r.insert_relaxed(29..=35).unwrap();
1446        assert_eq!(&r.0[..], &[29..=50, 80..=100, 130..=150][..]);
1447
1448        let mut r = ranges.clone();
1449        r.insert_relaxed(29..=55).unwrap();
1450        assert_eq!(&r.0[..], &[29..=55, 80..=100, 130..=150][..]);
1451
1452        let mut r = ranges.clone();
1453        r.insert_relaxed(29..=78).unwrap();
1454        assert_eq!(&r.0[..], &[29..=78, 80..=100, 130..=150][..]);
1455
1456        let mut r = ranges.clone();
1457        r.insert_relaxed(29..=79).unwrap();
1458        assert_eq!(&r.0[..], &[29..=100, 130..=150][..]);
1459
1460        let mut r = ranges.clone();
1461        r.insert_relaxed(30..=79).unwrap();
1462        assert_eq!(&r.0[..], &[30..=100, 130..=150][..]);
1463
1464        let mut r = ranges.clone();
1465        r.insert_relaxed(30..=150).unwrap();
1466        assert_eq!(&r.0[..], &[30..=150][..]);
1467
1468        let mut r = ranges.clone();
1469        r.insert_relaxed(10..=170).unwrap();
1470        assert_eq!(&r.0[..], &[10..=170][..]);
1471
1472        let mut r = ranges.clone();
1473        r.insert_relaxed(85..=129).unwrap();
1474        assert_eq!(&r.0[..], &[30..=50, 80..=150][..]);
1475
1476        let mut r = ranges.clone();
1477        r.insert_relaxed(85..=129).unwrap();
1478        assert_eq!(&r.0[..], &[30..=50, 80..=150][..]);
1479
1480        let mut r = ranges.clone();
1481        r.insert_relaxed(135..=170).unwrap();
1482        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=170][..]);
1483
1484        let mut r = ranges.clone();
1485        r.insert_relaxed(151..=170).unwrap();
1486        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=170][..]);
1487
1488        let mut r = new_block_ranges([1..=2, 4..=6, 8..=10, 15..=20, 80..=100]);
1489        r.insert_relaxed(3..=79).unwrap();
1490        assert_eq!(&r.0[..], &[1..=100][..]);
1491    }
1492
1493    #[test]
1494    fn remove_relaxed() {
1495        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
1496
1497        let mut r = ranges.clone();
1498        r.remove_relaxed(29..=29).unwrap();
1499        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150][..]);
1500
1501        let mut r = ranges.clone();
1502        r.remove_relaxed(30..=30).unwrap();
1503        assert_eq!(&r.0[..], &[31..=50, 80..=100, 130..=150][..]);
1504
1505        let mut r = ranges.clone();
1506        r.remove_relaxed(20..=40).unwrap();
1507        assert_eq!(&r.0[..], &[41..=50, 80..=100, 130..=150][..]);
1508
1509        let mut r = ranges.clone();
1510        r.remove_relaxed(35..=40).unwrap();
1511        assert_eq!(&r.0[..], &[30..=34, 41..=50, 80..=100, 130..=150][..]);
1512
1513        let mut r = ranges.clone();
1514        r.remove_relaxed(51..=129).unwrap();
1515        assert_eq!(&r.0[..], &[30..=50, 130..=150][..]);
1516
1517        let mut r = ranges.clone();
1518        r.remove_relaxed(50..=130).unwrap();
1519        assert_eq!(&r.0[..], &[30..=49, 131..=150][..]);
1520
1521        let mut r = ranges.clone();
1522        r.remove_relaxed(35..=49).unwrap();
1523        assert_eq!(&r.0[..], &[30..=34, 50..=50, 80..=100, 130..=150][..]);
1524
1525        let mut r = ranges.clone();
1526        r.remove_relaxed(35..=50).unwrap();
1527        assert_eq!(&r.0[..], &[30..=34, 80..=100, 130..=150][..]);
1528
1529        let mut r = ranges.clone();
1530        r.remove_relaxed(35..=55).unwrap();
1531        assert_eq!(&r.0[..], &[30..=34, 80..=100, 130..=150][..]);
1532
1533        let mut r = ranges.clone();
1534        r.remove_relaxed(35..=135).unwrap();
1535        assert_eq!(&r.0[..], &[30..=34, 136..=150][..]);
1536
1537        let mut r = ranges.clone();
1538        r.remove_relaxed(35..=170).unwrap();
1539        assert_eq!(&r.0[..], &[30..=34][..]);
1540
1541        let mut r = ranges.clone();
1542        r.remove_relaxed(10..=135).unwrap();
1543        assert_eq!(&r.0[..], &[136..=150][..]);
1544
1545        let mut r = ranges.clone();
1546        r.remove_relaxed(10..=170).unwrap();
1547        assert!(r.0.is_empty());
1548
1549        let mut r = new_block_ranges([1..=10, 12..=12, 14..=14]);
1550        r.remove_relaxed(12..=12).unwrap();
1551        assert_eq!(&r.0[..], &[1..=10, 14..=14][..]);
1552
1553        let mut r = new_block_ranges([1..=u64::MAX]);
1554        r.remove_relaxed(12..=12).unwrap();
1555        assert_eq!(&r.0[..], &[1..=11, 13..=u64::MAX][..]);
1556
1557        let mut r = new_block_ranges([1..=u64::MAX]);
1558        r.remove_relaxed(1..=1).unwrap();
1559        assert_eq!(&r.0[..], &[2..=u64::MAX][..]);
1560
1561        let mut r = new_block_ranges([1..=u64::MAX]);
1562        r.remove_relaxed(u64::MAX..=u64::MAX).unwrap();
1563        assert_eq!(&r.0[..], &[1..=u64::MAX - 1][..]);
1564    }
1565
1566    #[test]
1567    fn edges() {
1568        let r = BlockRanges::default();
1569        let edges = r.edges();
1570        assert!(edges.is_empty());
1571
1572        let r = new_block_ranges([6..=6, 8..=100, 200..=201, 300..=310]);
1573        let edges = r.edges();
1574        assert_eq!(
1575            &edges.0[..],
1576            &[6..=6, 8..=8, 100..=100, 200..=201, 300..=300, 310..=310][..]
1577        );
1578    }
1579
1580    #[test]
1581    fn inverse() {
1582        let inverse = !BlockRanges::new();
1583        assert_eq!(&inverse.0[..], &[1..=u64::MAX][..]);
1584
1585        let inverse = !new_block_ranges([1..=u64::MAX]);
1586        assert!(inverse.is_empty());
1587
1588        let inverse = !new_block_ranges([10..=u64::MAX]);
1589        assert_eq!(&inverse.0[..], &[1..=9][..]);
1590
1591        let inverse = !new_block_ranges([1..=9]);
1592        assert_eq!(&inverse.0[..], &[10..=u64::MAX][..]);
1593
1594        let inverse = !new_block_ranges([10..=100, 200..=200, 400..=600, 700..=800, 900..=900]);
1595        assert_eq!(
1596            &inverse.0[..],
1597            &[
1598                1..=9,
1599                101..=199,
1600                201..=399,
1601                601..=699,
1602                801..=899,
1603                901..=u64::MAX
1604            ][..]
1605        );
1606        assert_eq!(
1607            &(!inverse).0[..],
1608            &[10..=100, 200..=200, 400..=600, 700..=800, 900..=900][..]
1609        );
1610
1611        let inverse = !new_block_ranges([1..=100, 200..=200, 400..=600, 700..=800, 900..=900]);
1612        assert_eq!(
1613            &inverse.0[..],
1614            &[101..=199, 201..=399, 601..=699, 801..=899, 901..=u64::MAX][..]
1615        );
1616        assert_eq!(
1617            &(!inverse).0[..],
1618            &[1..=100, 200..=200, 400..=600, 700..=800, 900..=900][..]
1619        );
1620
1621        let inverse = !new_block_ranges([2..=100, 400..=600, 700..=(u64::MAX - 1)]);
1622        assert_eq!(
1623            &inverse.0[..],
1624            &[1..=1, 101..=399, 601..=699, u64::MAX..=u64::MAX][..]
1625        );
1626        assert_eq!(
1627            &(!inverse).0[..],
1628            &[2..=100, 400..=600, 700..=(u64::MAX - 1)][..]
1629        );
1630    }
1631
1632    #[test]
1633    fn bitwise_and() {
1634        let a = new_block_ranges([10..=100, 200..=200, 400..=600, 700..=800, 900..=900]);
1635        let b = new_block_ranges([50..=50, 55..=250, 300..=750, 800..=1000]);
1636
1637        assert_eq!(
1638            a & b,
1639            new_block_ranges([
1640                50..=50,
1641                55..=100,
1642                200..=200,
1643                400..=600,
1644                700..=750,
1645                800..=800,
1646                900..=900
1647            ])
1648        );
1649    }
1650
1651    #[test]
1652    fn partition() {
1653        assert!(BlockRanges::new().partitions().is_none());
1654
1655        let ranges = new_block_ranges([1..=101]);
1656        let (left, middle, right) = ranges.partitions().unwrap();
1657        assert_eq!(left, new_block_ranges([1..=50]));
1658        assert_eq!(middle, 51);
1659        assert_eq!(right, new_block_ranges([52..=101]));
1660
1661        let ranges = new_block_ranges([10..=10]);
1662        let (left, middle, right) = ranges.partitions().unwrap();
1663        assert!(left.is_empty());
1664        assert_eq!(middle, 10);
1665        assert!(right.is_empty());
1666
1667        let ranges = new_block_ranges([10..=14, 20..=24, 100..=109]);
1668        let (left, middle, right) = ranges.partitions().unwrap();
1669        assert_eq!(left, new_block_ranges([10..=14, 20..=23]));
1670        assert_eq!(middle, 24);
1671        assert_eq!(right, new_block_ranges([100..=109]));
1672
1673        let ranges = new_block_ranges([10..=19, 90..=94, 100..=104]);
1674        let (left, middle, right) = ranges.partitions().unwrap();
1675        assert_eq!(left, new_block_ranges([10..=18]));
1676        assert_eq!(middle, 19);
1677        assert_eq!(right, new_block_ranges([90..=94, 100..=104]));
1678
1679        let ranges = new_block_ranges([10..=14, 20..=25, 100..=109]);
1680        let (left, middle, right) = ranges.partitions().unwrap();
1681        assert_eq!(left, new_block_ranges([10..=14, 20..=24]));
1682        assert_eq!(middle, 25);
1683        assert_eq!(right, new_block_ranges([100..=109]));
1684
1685        let ranges = new_block_ranges([10..=14, 20..=24, 99..=109]);
1686        let (left, middle, right) = ranges.partitions().unwrap();
1687        assert_eq!(left, new_block_ranges([10..=14, 20..=24]));
1688        assert_eq!(middle, 99);
1689        assert_eq!(right, new_block_ranges([100..=109]));
1690
1691        let ranges = new_block_ranges([10..=14, 20..=24, 30..=30, 100..=109]);
1692        let (left, middle, right) = ranges.partitions().unwrap();
1693        assert_eq!(left, new_block_ranges([10..=14, 20..=24]));
1694        assert_eq!(middle, 30);
1695        assert_eq!(right, new_block_ranges([100..=109]));
1696
1697        let ranges = new_block_ranges([10..=19, 30..=30, 90..=94, 100..=104]);
1698        let (left, middle, right) = ranges.partitions().unwrap();
1699        assert_eq!(left, new_block_ranges([10..=19]));
1700        assert_eq!(middle, 30);
1701        assert_eq!(right, new_block_ranges([90..=94, 100..=104]));
1702
1703        let ranges = new_block_ranges([10..=14, 20..=24, 30..=31, 100..=109]);
1704        let (left, middle, right) = ranges.partitions().unwrap();
1705        assert_eq!(left, new_block_ranges([10..=14, 20..=24, 30..=30]));
1706        assert_eq!(middle, 31);
1707        assert_eq!(right, new_block_ranges([100..=109]));
1708
1709        let ranges = new_block_ranges([10..=19, 30..=31, 90..=94, 100..=104]);
1710        let (left, middle, right) = ranges.partitions().unwrap();
1711        assert_eq!(left, new_block_ranges([10..=19, 30..=30]));
1712        assert_eq!(middle, 31);
1713        assert_eq!(right, new_block_ranges([90..=94, 100..=104]));
1714
1715        let ranges = new_block_ranges([10..=14, 20..=24, 30..=32, 100..=109]);
1716        let (left, middle, right) = ranges.partitions().unwrap();
1717        assert_eq!(left, new_block_ranges([10..=14, 20..=24, 30..=30]));
1718        assert_eq!(middle, 31);
1719        assert_eq!(right, new_block_ranges([32..=32, 100..=109]));
1720
1721        let ranges = new_block_ranges([10..=19, 30..=32, 90..=94, 100..=104]);
1722        let (left, middle, right) = ranges.partitions().unwrap();
1723        assert_eq!(left, new_block_ranges([10..=19, 30..=30]));
1724        assert_eq!(middle, 31);
1725        assert_eq!(right, new_block_ranges([32..=32, 90..=94, 100..=104]));
1726    }
1727
1728    #[test]
1729    fn block_ranges_len() {
1730        let r = BlockRanges::default();
1731        assert!(r.is_empty());
1732        assert_eq!(r.len(), 0);
1733        assert_eq!(r.count(), 0);
1734
1735        let r = new_block_ranges([4..=4]);
1736        assert!(!r.is_empty());
1737        assert_eq!(r.len(), 1);
1738
1739        let r = new_block_ranges([4..=4, 100..=101]);
1740        assert!(!r.is_empty());
1741        assert_eq!(r.len(), 3);
1742        assert_eq!(r.count(), 3);
1743
1744        let r = new_block_ranges([250..=300]);
1745        assert!(!r.is_empty());
1746        assert_eq!(r.len(), 51);
1747        assert_eq!(r.count(), 51);
1748
1749        let r = new_block_ranges([4..=4, 100..=101, 250..=300]);
1750        assert!(!r.is_empty());
1751        assert_eq!(r.len(), 54);
1752        assert_eq!(r.count(), 54);
1753
1754        let r = new_block_ranges([4..=10, 100..=101, 250..=300]);
1755        assert!(!r.is_empty());
1756        assert_eq!(r.len(), 60);
1757        assert_eq!(r.count(), 60);
1758
1759        let r = new_block_ranges([4..=4, 100..=101, 250..=300, 500..=500]);
1760        assert!(!r.is_empty());
1761        assert_eq!(r.len(), 55);
1762        assert_eq!(r.count(), 55);
1763    }
1764}
lumina_node/block_ranges.rs

lumina_node/
block_ranges.rs
