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

lumina_node/
block_ranges.rs
