commonware_storage/rmap/
mod.rs

1//! A collection that manages disjoint, inclusive ranges `[start, end]`.
2//!
3//! # Design
4//!
5//! - Ranges are stored in ascending order of their start points.
6//! - Ranges are disjoint; there are no overlapping ranges.
7//! - Adjacent ranges are merged (e.g., inserting `5` into `[0,4]` and then inserting `4` results in `[0,5]`).
8//! - Each key in the [BTreeMap] represents the inclusive start of a range, and its
9//!   corresponding value represents the inclusive end of that range.
10
11use std::collections::BTreeMap;
12
13/// A collection that manages disjoint, inclusive ranges `[start, end]`.
14#[derive(Debug, Default, PartialEq)]
15pub struct RMap {
16    ranges: BTreeMap<u64, u64>,
17}
18
19impl RMap {
20    /// Creates a new, empty [RMap].
21    pub fn new() -> Self {
22        Self {
23            ranges: BTreeMap::new(),
24        }
25    }
26
27    /// Inserts a value into the [RMap].
28    ///
29    /// # Behavior
30    ///
31    /// - Create a new range `[value, value]` if `value` is isolated.
32    /// - Extend an existing range if `value` is adjacent to it (e.g., inserting `5` into `[1, 4]` results in `[1, 5]`).
33    /// - Merge two ranges if `value` bridges them (e.g., inserting `3` into a map with `[1, 2]` and `[4, 5]` results in `[1, 5]`).
34    /// - Do nothing if `value` is already covered by an existing range.
35    ///
36    /// # Complexity
37    ///
38    /// The time complexity is typically O(log N) due to `BTreeMap` lookups and insertions,
39    /// where N is the number of disjoint ranges in the map. In scenarios involving merges,
40    /// a few extra map operations (removals, insertions) might occur, but the overall
41    /// complexity remains logarithmic.
42    ///
43    /// # Example
44    ///
45    /// ```
46    /// use commonware_storage::rmap::RMap;
47    ///
48    /// let mut map = RMap::new();
49    /// map.insert(1); // Map: [1, 1]
50    /// assert_eq!(map.next_gap(0), (None, Some(1)));
51    /// map.insert(3); // Map: [1, 1], [3, 3]
52    /// assert_eq!(map.next_gap(1), (Some(1), Some(3)));
53    /// map.insert(2); // Map: [1, 3]
54    /// map.insert(0); // Map: [0, 3]
55    /// map.insert(5); // Map: [0, 3], [5, 5]
56    /// map.insert(4); // Map: [0, 5]
57    /// assert_eq!(map.get(&3), Some((0, 5)));
58    /// ```
59    pub fn insert(&mut self, value: u64) {
60        let prev_opt = self
61            .ranges
62            .range(..=value)
63            .next_back()
64            .map(|(&s, &e)| (s, e));
65        let next_opt = match value {
66            u64::MAX => None,
67            _ => self.ranges.range(value + 1..).next().map(|(&s, &e)| (s, e)),
68        };
69
70        match (prev_opt, next_opt) {
71            (Some((p_start, p_end)), Some((n_start, n_end))) => {
72                if value <= p_end {
73                    // Value is within prev range
74                    return;
75                }
76                if value == p_end + 1 && value + 1 == n_start {
77                    // Value bridges prev and next
78                    self.ranges.remove(&p_start);
79                    self.ranges.remove(&n_start);
80                    self.ranges.insert(p_start, n_end);
81                } else if value == p_end + 1 {
82                    // Value is adjacent to prev's end
83                    self.ranges.remove(&p_start);
84                    self.ranges.insert(p_start, value);
85                } else if value + 1 == n_start {
86                    // Value is adjacent to next's start
87                    self.ranges.remove(&n_start);
88                    self.ranges.insert(value, n_end);
89                } else {
90                    // New isolated range
91                    self.ranges.insert(value, value);
92                }
93            }
94            (Some((p_start, p_end)), None) => {
95                if value <= p_end {
96                    // Value is within prev range
97                    return;
98                }
99                if value == p_end + 1 {
100                    // Value is adjacent to prev's end
101                    self.ranges.remove(&p_start);
102                    self.ranges.insert(p_start, value);
103                } else {
104                    // New isolated range
105                    self.ranges.insert(value, value);
106                }
107            }
108            (None, Some((n_start, n_end))) => {
109                if value + 1 == n_start {
110                    // Value is adjacent to next's start
111                    self.ranges.remove(&n_start);
112                    self.ranges.insert(value, n_end);
113                } else {
114                    // New isolated range
115                    self.ranges.insert(value, value);
116                }
117            }
118            (None, None) => {
119                // Map is empty or value is isolated
120                self.ranges.insert(value, value);
121            }
122        }
123    }
124
125    /// Returns the range that contains the given value.
126    pub fn get(&self, value: &u64) -> Option<(u64, u64)> {
127        if let Some((&start, &end)) = self.ranges.range(..=value).next_back() {
128            if *value <= end {
129                return Some((start, end));
130            }
131        }
132        None
133    }
134
135    /// Removes a range `[start, end]` (inclusive) from the [RMap].
136    ///
137    /// # Behavior
138    ///
139    /// - If the removal range completely covers an existing range, the existing range is removed.
140    /// - If the removal range is a sub-range of an existing range, the existing range may be split
141    ///   into two (e.g., removing `[3, 4]` from `[1, 6]` results in `[1, 2]` and `[5, 6]`).
142    /// - If the removal range overlaps with the start or end of an existing range, the existing
143    ///   range is truncated (e.g., removing `[1, 2]` from `[1, 5]` results in `[3, 5]`).
144    /// - If the removal range covers multiple existing ranges, all such ranges are affected or removed.
145    /// - If `start > end`, the method does nothing.
146    /// - If the removal range does not overlap with any existing range, the map remains unchanged.
147    ///
148    /// # Complexity
149    ///
150    /// The time complexity is O(M + K log N), where N is the total number of ranges in the map,
151    /// M is the number of ranges that overlap with the removal range (iterate part), and K is the number of
152    /// new ranges created or ranges removed (at most 2 additions and M removals).
153    ///
154    /// # Example
155    ///
156    /// ```
157    /// use commonware_storage::rmap::RMap;
158    ///
159    /// let mut map = RMap::new();
160    /// map.insert(1); map.insert(2); map.insert(3); // Map: [1, 3]
161    /// map.insert(5); map.insert(6); map.insert(7); // Map: [1, 3], [5, 7]
162    ///
163    /// map.remove(2, 6); // Results in [1, 1], [7, 7]
164    /// assert_eq!(map.get(&1), Some((1, 1)));
165    /// assert_eq!(map.get(&2), None);
166    /// assert_eq!(map.get(&6), None);
167    /// assert_eq!(map.get(&7), Some((7, 7)));
168    /// ```
169    pub fn remove(&mut self, start: u64, end: u64) {
170        if start > end {
171            return;
172        }
173
174        // Iterate over ranges that could possibly overlap with the removal range `[start, end]`.
175        // A range (r_start, r_end) overlaps if r_start <= end AND r_end >= start.
176        //
177        // We optimize the BTreeMap iteration by only looking at ranges whose start (r_start)
178        // is less than or equal to the `end` of the removal range. If r_start > end,
179        // then (r_start, r_end) cannot overlap with [start, end].
180        let mut to_add = Vec::new();
181        let mut to_remove = Vec::new();
182
183        for (&r_start, &r_end) in self.ranges.iter() {
184            // Case 1: No overlap
185            if r_end < start || r_start > end {
186                continue;
187            }
188
189            // Case 2: Removal range completely covers current range
190            if start <= r_start && end >= r_end {
191                to_remove.push(r_start);
192                continue;
193            }
194
195            // Case 3: Current range completely covers removal range (split)
196            if r_start < start && r_end > end {
197                to_remove.push(r_start);
198                to_add.push((r_start, start - 1));
199                to_add.push((end + 1, r_end));
200                continue;
201            }
202
203            // Case 4: Removal range overlaps start of current range
204            if start <= r_start && end < r_end {
205                // and end >= r_start implied by not Case 1
206                to_remove.push(r_start);
207                to_add.push((end + 1, r_end));
208                continue;
209            }
210
211            // Case 5: Removal range overlaps end of current range
212            if start > r_start && end >= r_end {
213                // and start <= r_end implied by not Case 1
214                to_remove.push(r_start);
215                to_add.push((r_start, start - 1));
216                continue;
217            }
218        }
219
220        // Remove anything no longer needed.
221        for r_start in to_remove {
222            self.ranges.remove(&r_start);
223        }
224
225        // Add anything that is now needed.
226        for (a_start, a_end) in to_add {
227            if a_start <= a_end {
228                // Ensure valid range before adding
229                self.ranges.insert(a_start, a_end);
230            }
231        }
232    }
233
234    /// Returns an iterator over the ranges `(start, end)` in the [RMap].
235    ///
236    /// The ranges are yielded in ascending order of their start points.
237    /// Each tuple represents an inclusive range `[start, end]`.
238    ///
239    /// # Example
240    ///
241    /// ```
242    /// use commonware_storage::rmap::RMap;
243    ///
244    /// let mut map = RMap::new();
245    /// map.insert(0); map.insert(1); // Map: [0, 1]
246    /// map.insert(3); map.insert(4); // Map: [0, 1], [3, 4]
247    ///
248    /// let mut iter = map.iter();
249    /// assert_eq!(iter.next(), Some((&0, &1)));
250    /// assert_eq!(iter.next(), Some((&3, &4)));
251    /// assert_eq!(iter.next(), None);
252    /// ```
253    pub fn iter(&self) -> impl Iterator<Item = (&u64, &u64)> {
254        self.ranges.iter()
255    }
256
257    /// Finds the end of the range containing `value` and the start of the
258    /// range succeeding `value`. This method is useful for identifying gaps around a given point.
259    ///
260    /// # Behavior
261    ///
262    /// - If `value` falls within an existing range `[r_start, r_end]`, `current_range_end` will be `Some(r_end)`.
263    /// - If `value` falls in a gap between two ranges `[..., prev_end]` and `[next_start, ...]`,
264    ///   `current_range_end` will be `None` and `next_range_start` will be `Some(next_start)`.
265    /// - If `value` is before all ranges in the map, `current_range_end` will be `None`.
266    /// - If `value` is after all ranges in the map (or within the last range), `next_range_start` will be `None`.
267    /// - If the map is empty, both will be `None`.
268    ///
269    /// # Arguments
270    ///
271    /// * `value`: The `u64` value to query around.
272    ///
273    /// # Returns
274    ///
275    /// A tuple `(Option<u64>, Option<u64>)` where:
276    /// - The first element (`current_range_end`) is `Some(end)` of the range that contains `value`. It's `None` if `value` is before all ranges, the map is empty, or `value` is not in any range.
277    /// - The second element (`next_range_start`) is `Some(start)` of the first range that begins strictly after `value`. It's `None` if no range starts after `value` or the map is empty.
278    ///
279    /// # Complexity
280    ///
281    /// O(log N) where N is the number of ranges in [RMap].
282    ///
283    /// # Example
284    ///
285    /// ```
286    /// use commonware_storage::rmap::RMap;
287    ///
288    /// let mut map = RMap::new();
289    /// map.insert(1); map.insert(2); // Map: [1, 2]
290    /// map.insert(5); map.insert(6); // Map: [1, 2], [5, 6]
291    ///
292    /// assert_eq!(map.next_gap(0), (None, Some(1)));        // Before all ranges
293    /// assert_eq!(map.next_gap(1), (Some(2), Some(5)));     // Value is at the start of a range
294    /// assert_eq!(map.next_gap(2), (Some(2), Some(5)));     // Value is at the end of a range
295    /// assert_eq!(map.next_gap(3), (None, Some(5)));     // Value is in a gap
296    /// assert_eq!(map.next_gap(5), (Some(6), None));        // Value is at the start of the last range
297    /// assert_eq!(map.next_gap(6), (Some(6), None));        // Value is at the end of the last range
298    /// assert_eq!(map.next_gap(7), (None, None));        // After all ranges
299    /// ```
300    pub fn next_gap(&self, value: u64) -> (Option<u64>, Option<u64>) {
301        let current_range_end = match self.ranges.range(..=value).next_back().map(|(_, &end)| end) {
302            Some(end) if end >= value => Some(end),
303            _ => None,
304        };
305
306        let next_range_start = match value {
307            u64::MAX => None,
308            _ => self
309                .ranges
310                .range(value + 1..)
311                .next()
312                .map(|(&start, _)| start),
313        };
314
315        (current_range_end, next_range_start)
316    }
317
318    /// Returns up to `max` missing items starting from `start`.
319    ///
320    /// This method iterates through gaps between existing ranges, collecting missing indices
321    /// until either `max` items are found or there are no more gaps to fill.
322    ///
323    /// # Arguments
324    ///
325    /// * `start`: The index to start searching from (inclusive).
326    /// * `max`: The maximum number of missing items to return.
327    ///
328    /// # Returns
329    ///
330    /// A vector containing up to `max` missing indices from gaps between ranges.
331    /// The vector may contain fewer than `max` items if there aren't enough gaps.
332    /// If there are no more ranges after the current position, no items are returned.
333    ///
334    /// # Complexity
335    ///
336    /// O(G log N + M) where N is the number of ranges in [RMap], G is the number of gaps
337    /// visited (at most N), and M is the number of missing items returned (at most `max`).
338    /// Each gap requires a `next_gap` call (O(log N)) and collecting items (O(items in gap)).
339    ///
340    /// # Example
341    ///
342    /// ```
343    /// use commonware_storage::rmap::RMap;
344    ///
345    /// let mut map = RMap::new();
346    /// map.insert(1); map.insert(2); // Map: [1, 2]
347    /// map.insert(5); map.insert(6); // Map: [1, 2], [5, 6]
348    /// map.insert(10);                // Map: [1, 2], [5, 6], [10, 10]
349    ///
350    /// // Starting from 0, find up to 5 missing items
351    /// assert_eq!(map.missing_items(0, 5), vec![0, 3, 4, 7, 8]);
352    ///
353    /// // Starting from 3, find up to 3 missing items
354    /// assert_eq!(map.missing_items(3, 3), vec![3, 4, 7]);
355    ///
356    /// // Starting from 7, find up to 10 missing items (only gaps are returned)
357    /// assert_eq!(map.missing_items(7, 10), vec![7, 8, 9]);
358    ///
359    /// // Starting from 11, there are no more ranges, so no gaps
360    /// assert_eq!(map.missing_items(11, 5), Vec::<u64>::new());
361    /// ```
362    pub fn missing_items(&self, start: u64, max: usize) -> Vec<u64> {
363        // Ensure input is valid
364        assert!(max > 0, "max must be greater than 0");
365        let mut current = start;
366
367        // Collect missing items
368        let mut missing = Vec::with_capacity(max);
369        loop {
370            // If we're inside a range, skip to just after it
371            let (current_range_end, next_range_start) = self.next_gap(current);
372            if let Some(end) = current_range_end {
373                // Check if we can move past this range
374                if end == u64::MAX {
375                    break missing; // No gaps possible after u64::MAX
376                }
377                current = end + 1;
378                continue;
379            }
380
381            // We're in a gap - check if there's a next range
382            let Some(next_start) = next_range_start else {
383                break missing; // No more ranges, so no more gaps to fill
384            };
385
386            // Collect items from this gap until we hit the next range or have enough
387            let gap_end = next_start - 1; // next_start must be greater than or equal to 1
388            let items_needed = max - missing.len(); // there must be at least one item to collect
389            let gap_end = gap_end.min(current.saturating_add(items_needed as u64 - 1));
390            for index in current..=gap_end {
391                missing.push(index);
392            }
393
394            // If we have enough items, break
395            if missing.len() >= max {
396                break missing;
397            }
398
399            // Move to the start of the next range to check for more gaps
400            current = next_start;
401        }
402    }
403}
404
405#[cfg(test)]
406mod tests {
407    use super::*;
408
409    #[test]
410    fn test_new() {
411        let map = RMap::new();
412        assert_eq!(map.iter().count(), 0);
413    }
414
415    #[test]
416    fn test_insert_empty() {
417        let mut map = RMap::new();
418        map.insert(5);
419        assert_eq!(map.get(&5), Some((5, 5)));
420        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &5)]);
421    }
422
423    #[test]
424    fn test_insert_isolated() {
425        let mut map = RMap::new();
426        map.insert(5);
427        map.insert(10);
428        assert_eq!(map.get(&5), Some((5, 5)));
429        assert_eq!(map.get(&10), Some((10, 10)));
430        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &5), (&10, &10)]);
431    }
432
433    #[test]
434    fn test_insert_covered() {
435        let mut map = RMap::new();
436        map.insert(1);
437        map.insert(2);
438        map.insert(3); // Range is 1-3
439        map.insert(2); // Insert value already covered
440        assert_eq!(map.get(&1), Some((1, 3)));
441        assert_eq!(map.get(&2), Some((1, 3)));
442        assert_eq!(map.get(&3), Some((1, 3)));
443        assert_eq!(map.iter().count(), 1);
444        assert_eq!(map.iter().next(), Some((&1, &3)));
445    }
446
447    #[test]
448    fn test_insert_adjacent_end() {
449        let mut map = RMap::new();
450        map.insert(1);
451        map.insert(2); // Range is 1-2
452        map.insert(3); // Adjacent to end
453        assert_eq!(map.get(&1), Some((1, 3)));
454        assert_eq!(map.get(&3), Some((1, 3)));
455        assert_eq!(map.iter().next(), Some((&1, &3)));
456    }
457
458    #[test]
459    fn test_insert_adjacent_start() {
460        let mut map = RMap::new();
461        map.insert(2);
462        map.insert(3); // Range is 2-3
463        map.insert(1); // Adjacent to start
464        assert_eq!(map.get(&1), Some((1, 3)));
465        assert_eq!(map.get(&3), Some((1, 3)));
466        assert_eq!(map.iter().next(), Some((&1, &3)));
467    }
468
469    #[test]
470    fn test_insert_bridge_ranges() {
471        let mut map = RMap::new();
472        map.insert(1);
473        map.insert(2);
474        assert_eq!(map.get(&1), Some((1, 2)));
475        map.insert(5);
476        map.insert(6);
477        assert_eq!(map.get(&5), Some((5, 6)));
478        // Current: (1,2), (5,6)
479        map.insert(3); // Insert 3, should become (1,3), (5,6)
480        assert_eq!(map.get(&1), Some((1, 3)));
481        assert_eq!(map.get(&2), Some((1, 3)));
482        assert_eq!(map.get(&3), Some((1, 3)));
483        assert_eq!(map.get(&5), Some((5, 6)));
484        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&1, &3), (&5, &6)]);
485
486        map.insert(4); // Insert 4, should bridge to (1,6)
487        assert_eq!(map.get(&1), Some((1, 6)));
488        assert_eq!(map.get(&3), Some((1, 6)));
489        assert_eq!(map.get(&4), Some((1, 6)));
490        assert_eq!(map.get(&6), Some((1, 6)));
491        assert_eq!(map.iter().count(), 1);
492        assert_eq!(map.iter().next(), Some((&1, &6)));
493    }
494
495    #[test]
496    fn test_insert_complex_merging_and_ordering() {
497        let mut map = RMap::new();
498        map.insert(10); // (10,10)
499        map.insert(12); // (10,10), (12,12)
500        map.insert(11); // (10,12)
501        assert_eq!(map.get(&10), Some((10, 12)));
502        assert_eq!(map.get(&11), Some((10, 12)));
503        assert_eq!(map.get(&12), Some((10, 12)));
504
505        map.insert(15); // (10,12), (15,15)
506        map.insert(13); // (10,13), (15,15)
507        assert_eq!(map.get(&13), Some((10, 13)));
508        assert_eq!(map.get(&12), Some((10, 13)));
509        assert_eq!(map.get(&15), Some((15, 15)));
510
511        map.insert(14); // (10,15)
512        assert_eq!(map.get(&10), Some((10, 15)));
513        assert_eq!(map.get(&14), Some((10, 15)));
514        assert_eq!(map.get(&15), Some((10, 15)));
515        assert_eq!(map.iter().count(), 1);
516        assert_eq!(map.iter().next(), Some((&10, &15)));
517
518        map.insert(5); // (5,5), (10,15)
519        map.insert(7); // (5,5), (7,7), (10,15)
520        map.insert(6); // (5,7), (10,15)
521        assert_eq!(map.get(&5), Some((5, 7)));
522        assert_eq!(map.get(&6), Some((5, 7)));
523        assert_eq!(map.get(&7), Some((5, 7)));
524        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &7), (&10, &15)]);
525
526        map.insert(9); // (5,7), (9,9), (10,15) -> should become (5,7), (9,15)
527        assert_eq!(map.get(&9), Some((9, 15)));
528        assert_eq!(map.get(&10), Some((9, 15)));
529        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &7), (&9, &15)]);
530
531        map.insert(8); // (5,15)
532        assert_eq!(map.get(&5), Some((5, 15)));
533        assert_eq!(map.get(&8), Some((5, 15)));
534        assert_eq!(map.get(&15), Some((5, 15)));
535        assert_eq!(map.iter().next(), Some((&5, &15)));
536    }
537
538    #[test]
539    fn test_insert_max_value() {
540        let mut map = RMap::new();
541        map.insert(u64::MAX);
542        assert_eq!(map.get(&u64::MAX), Some((u64::MAX, u64::MAX)));
543        map.insert(u64::MAX - 1);
544        assert_eq!(map.get(&(u64::MAX - 1)), Some((u64::MAX - 1, u64::MAX)));
545        assert_eq!(map.get(&u64::MAX), Some((u64::MAX - 1, u64::MAX)));
546    }
547
548    #[test]
549    fn test_get() {
550        let mut map = RMap::new();
551        map.insert(1);
552        map.insert(2);
553        map.insert(3); // Range 1-3
554        map.insert(5);
555        map.insert(6); // Range 5-6
556
557        assert_eq!(map.get(&1), Some((1, 3)));
558        assert_eq!(map.get(&2), Some((1, 3)));
559        assert_eq!(map.get(&3), Some((1, 3)));
560        assert_eq!(map.get(&4), None);
561        assert_eq!(map.get(&5), Some((5, 6)));
562        assert_eq!(map.get(&6), Some((5, 6)));
563        assert_eq!(map.get(&0), None);
564        assert_eq!(map.get(&7), None);
565    }
566
567    #[test]
568    fn test_remove_empty() {
569        let mut map = RMap::new();
570        map.remove(1, 5);
571        assert_eq!(map.iter().count(), 0);
572    }
573
574    #[test]
575    fn test_remove_invalid_range() {
576        let mut map = RMap::new();
577        map.insert(1);
578        map.insert(2); // 1-2
579        map.remove(5, 1); // start > end, should do nothing
580        assert_eq!(map.iter().next(), Some((&1, &2)));
581    }
582
583    #[test]
584    fn test_remove_non_existent() {
585        let mut map = RMap::new();
586        map.insert(5);
587        map.insert(6); // 5-6
588        map.remove(1, 3); // Before existing
589        assert_eq!(map.iter().next(), Some((&5, &6)));
590        map.remove(8, 10); // After existing
591        assert_eq!(map.iter().next(), Some((&5, &6)));
592        map.remove(1, 10); // Covers existing
593        assert_eq!(map.iter().count(), 0);
594    }
595
596    #[test]
597    fn test_remove_exact_match() {
598        let mut map = RMap::new();
599        map.insert(1);
600        map.insert(2);
601        map.insert(3); // 1-3
602        map.insert(5);
603        map.insert(6); // 5-6
604        map.remove(1, 3);
605        assert_eq!(map.get(&2), None);
606        assert_eq!(map.iter().next(), Some((&5, &6)));
607        map.remove(5, 6);
608        assert_eq!(map.iter().count(), 0);
609    }
610
611    #[test]
612    fn test_remove_subset_split() {
613        let mut map = RMap::new();
614        map.insert(1);
615        map.insert(2);
616        map.insert(3);
617        map.insert(4);
618        map.insert(5); // 1-5
619        map.remove(3, 3); // Remove 3 from 1-5 -> (1,2), (4,5)
620        assert_eq!(map.get(&2), Some((1, 2)));
621        assert_eq!(map.get(&3), None);
622        assert_eq!(map.get(&4), Some((4, 5)));
623        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&1, &2), (&4, &5)]);
624
625        // Reset and test another split
626        let mut map2 = RMap::new();
627        map2.insert(1);
628        map2.insert(2);
629        map2.insert(3);
630        map2.insert(4);
631        map2.insert(5); // 1-5
632        map2.remove(2, 4); // Remove 2-4 from 1-5 -> (1,1), (5,5)
633        assert_eq!(map2.get(&1), Some((1, 1)));
634        assert_eq!(map2.get(&2), None);
635        assert_eq!(map2.get(&3), None);
636        assert_eq!(map2.get(&4), None);
637        assert_eq!(map2.get(&5), Some((5, 5)));
638        assert_eq!(map2.iter().collect::<Vec<_>>(), vec![(&1, &1), (&5, &5)]);
639    }
640
641    #[test]
642    fn test_remove_overlap_start() {
643        let mut map = RMap::new();
644        map.insert(1);
645        map.insert(2);
646        map.insert(3);
647        map.insert(4);
648        map.insert(5); // 1-5
649        map.remove(0, 2); // Remove 0-2 from 1-5 -> (3,5)
650        assert_eq!(map.get(&1), None);
651        assert_eq!(map.get(&2), None);
652        assert_eq!(map.get(&3), Some((3, 5)));
653        assert_eq!(map.iter().next(), Some((&3, &5)));
654    }
655
656    #[test]
657    fn test_remove_overlap_end() {
658        let mut map = RMap::new();
659        map.insert(1);
660        map.insert(2);
661        map.insert(3);
662        map.insert(4);
663        map.insert(5); // 1-5
664        map.remove(4, 6); // Remove 4-6 from 1-5 -> (1,3)
665        assert_eq!(map.get(&3), Some((1, 3)));
666        assert_eq!(map.get(&4), None);
667        assert_eq!(map.get(&5), None);
668        assert_eq!(map.iter().next(), Some((&1, &3)));
669    }
670
671    #[test]
672    fn test_remove_cover_multiple_ranges() {
673        let mut map = RMap::new();
674        map.insert(1);
675        map.insert(2); // 1-2
676        map.insert(4);
677        map.insert(5); // 4-5
678        map.insert(7);
679        map.insert(8); // 7-8
680
681        map.remove(3, 6); // Removes 4-5, no truncation as 3 and 6 are in gaps. (1,2), (7,8)
682        assert_eq!(map.get(&2), Some((1, 2)));
683        assert_eq!(map.get(&4), None);
684        assert_eq!(map.get(&5), None);
685        assert_eq!(map.get(&7), Some((7, 8)));
686        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&1, &2), (&7, &8)]);
687
688        map.remove(0, 10); // Removes all remaining ranges
689        assert_eq!(map.iter().count(), 0);
690    }
691
692    #[test]
693    fn test_remove_partial_overlap_multiple_ranges() {
694        let mut map = RMap::new();
695        map.insert(1);
696        map.insert(2);
697        map.insert(3); // 1-3
698        map.insert(5);
699        map.insert(6);
700        map.insert(7); // 5-7
701        map.insert(9);
702        map.insert(10);
703        map.insert(11); // 9-11
704
705        map.remove(2, 6); // Affects 1-3 (becomes 1-1) and 5-7 (becomes 7-7)
706        assert_eq!(map.get(&1), Some((1, 1)));
707        assert_eq!(map.get(&2), None);
708        assert_eq!(map.get(&3), None);
709        assert_eq!(map.get(&5), None);
710        assert_eq!(map.get(&6), None);
711        assert_eq!(map.get(&7), Some((7, 7)));
712        assert_eq!(map.get(&9), Some((9, 11)));
713        assert_eq!(
714            map.iter().collect::<Vec<_>>(),
715            vec![(&1, &1), (&7, &7), (&9, &11)]
716        );
717
718        // Reset and test removing all
719        let mut map2 = RMap::new();
720        map2.insert(1);
721        map2.insert(2);
722        map2.insert(3);
723        map2.insert(5);
724        map2.insert(6);
725        map2.insert(7);
726        map2.insert(9);
727        map2.insert(10);
728        map2.insert(11);
729        map2.remove(0, 20); // remove all
730        assert_eq!(map2.iter().count(), 0);
731    }
732
733    #[test]
734    fn test_remove_touching_boundaries_no_merge() {
735        let mut map = RMap::new();
736        map.insert(0);
737        map.insert(1);
738        map.insert(2); // 0-2
739        map.insert(4);
740        map.insert(5); // 4-5
741
742        // Remove range that is exactly between two existing ranges
743        map.remove(3, 3);
744        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&0, &2), (&4, &5)]);
745    }
746
747    #[test]
748    fn test_remove_max_value_ranges() {
749        let mut map = RMap::new();
750        map.insert(u64::MAX - 2);
751        map.insert(u64::MAX - 1);
752        map.insert(u64::MAX); // MAX-2 to MAX
753
754        map.remove(u64::MAX, u64::MAX); // Remove MAX -> (MAX-2, MAX-1)
755        assert_eq!(map.get(&(u64::MAX - 2)), Some((u64::MAX - 2, u64::MAX - 1)));
756        assert_eq!(map.get(&u64::MAX), None);
757
758        map.remove(u64::MAX - 2, u64::MAX - 2); // Remove MAX-2 -> (MAX-1, MAX-1)
759        assert_eq!(map.get(&(u64::MAX - 2)), None);
760        assert_eq!(map.get(&(u64::MAX - 1)), Some((u64::MAX - 1, u64::MAX - 1)));
761
762        map.remove(u64::MAX - 1, u64::MAX - 1); // Remove MAX-1 -> empty
763        assert_eq!(map.iter().count(), 0);
764
765        map.insert(u64::MAX - 1);
766        map.insert(u64::MAX); // MAX-1 to MAX
767        map.remove(u64::MIN, u64::MAX); // Remove all
768        assert_eq!(map.iter().count(), 0);
769    }
770
771    #[test]
772    fn test_iter() {
773        let mut map = RMap::new();
774        assert_eq!(map.iter().next(), None);
775        map.insert(5);
776        map.insert(6); // 5-6
777        map.insert(1);
778        map.insert(2); // 1-2
779        let mut iter = map.iter();
780        assert_eq!(iter.next(), Some((&1, &2)));
781        assert_eq!(iter.next(), Some((&5, &6)));
782        assert_eq!(iter.next(), None);
783    }
784
785    #[test]
786    fn test_next_gap_empty() {
787        let map = RMap::new();
788        assert_eq!(map.next_gap(5), (None, None));
789    }
790
791    #[test]
792    fn test_next_gap_single_range() {
793        let mut map = RMap::new();
794        map.insert(5);
795        map.insert(6);
796        map.insert(7); // 5-7
797        assert_eq!(map.next_gap(4), (None, Some(5))); // Before range
798        assert_eq!(map.next_gap(5), (Some(7), None)); // Start of range
799        assert_eq!(map.next_gap(6), (Some(7), None)); // Middle of range
800        assert_eq!(map.next_gap(7), (Some(7), None)); // End of range
801        assert_eq!(map.next_gap(8), (None, None)); // After range
802    }
803
804    #[test]
805    fn test_next_gap_multiple_ranges() {
806        let mut map = RMap::new();
807        map.insert(1);
808        map.insert(2); // 1-2
809        map.insert(5);
810        map.insert(6); // 5-6
811        map.insert(10); // 10-10
812
813        assert_eq!(map.next_gap(0), (None, Some(1))); // Before all
814        assert_eq!(map.next_gap(1), (Some(2), Some(5))); // Start of first range
815        assert_eq!(map.next_gap(2), (Some(2), Some(5))); // End of first range
816        assert_eq!(map.next_gap(3), (None, Some(5))); // Gap between 1st and 2nd
817        assert_eq!(map.next_gap(4), (None, Some(5))); // Gap, closer to 2nd
818        assert_eq!(map.next_gap(5), (Some(6), Some(10))); // Start of 2nd range
819        assert_eq!(map.next_gap(6), (Some(6), Some(10))); // End of 2nd range
820        assert_eq!(map.next_gap(7), (None, Some(10))); // Gap between 2nd and 3rd
821        assert_eq!(map.next_gap(8), (None, Some(10))); // Gap
822        assert_eq!(map.next_gap(9), (None, Some(10))); // Gap, closer to 3rd
823        assert_eq!(map.next_gap(10), (Some(10), None)); // Start/End of 3rd range
824        assert_eq!(map.next_gap(11), (None, None)); // After all
825    }
826
827    #[test]
828    fn test_next_gap_value_is_max() {
829        let mut map = RMap::new();
830        map.insert(u64::MAX - 5);
831        map.insert(u64::MAX - 4); // MAX-5 to MAX-4
832        map.insert(u64::MAX - 1);
833        map.insert(u64::MAX); // MAX-1 to MAX
834
835        assert_eq!(map.next_gap(u64::MAX - 6), (None, Some(u64::MAX - 5)));
836        assert_eq!(
837            map.next_gap(u64::MAX - 5),
838            (Some(u64::MAX - 4), Some(u64::MAX - 1))
839        );
840        assert_eq!(
841            map.next_gap(u64::MAX - 4),
842            (Some(u64::MAX - 4), Some(u64::MAX - 1))
843        );
844        assert_eq!(map.next_gap(u64::MAX - 3), (None, Some(u64::MAX - 1))); // In gap
845        assert_eq!(map.next_gap(u64::MAX - 2), (None, Some(u64::MAX - 1))); // In gap
846        assert_eq!(map.next_gap(u64::MAX - 1), (Some(u64::MAX), None));
847        assert_eq!(map.next_gap(u64::MAX), (Some(u64::MAX), None));
848    }
849
850    #[test]
851    fn test_odd_ranges() {
852        // Insert values
853        let mut map = RMap::new();
854        map.insert(1);
855        map.insert(10);
856        map.insert(11);
857        map.insert(14);
858
859        // Sanity check next_gap
860        assert_eq!(map.next_gap(0), (None, Some(1)));
861        assert_eq!(map.next_gap(1), (Some(1), Some(10)));
862        assert_eq!(map.next_gap(10), (Some(11), Some(14)));
863        assert_eq!(map.next_gap(11), (Some(11), Some(14)));
864        assert_eq!(map.next_gap(12), (None, Some(14)));
865        assert_eq!(map.next_gap(14), (Some(14), None));
866    }
867
868    #[test]
869    fn test_missing_items_empty_map() {
870        let map = RMap::new();
871        assert_eq!(map.missing_items(0, 5), Vec::<u64>::new());
872        assert_eq!(map.missing_items(100, 10), Vec::<u64>::new());
873    }
874
875    #[test]
876    fn test_missing_items_single_gap() {
877        let mut map = RMap::new();
878        map.insert(1);
879        map.insert(2); // [1, 2]
880        map.insert(5);
881        map.insert(6); // [1, 2], [5, 6]
882
883        // Gap between ranges: 3, 4
884        assert_eq!(map.missing_items(3, 5), vec![3, 4]);
885        assert_eq!(map.missing_items(3, 2), vec![3, 4]);
886        assert_eq!(map.missing_items(3, 1), vec![3]);
887        assert_eq!(map.missing_items(4, 1), vec![4]);
888    }
889
890    #[test]
891    fn test_missing_items_multiple_gaps() {
892        let mut map = RMap::new();
893        map.insert(1);
894        map.insert(2); // [1, 2]
895        map.insert(5);
896        map.insert(6); // [1, 2], [5, 6]
897        map.insert(10); // [1, 2], [5, 6], [10, 10]
898
899        // Starting from 0 (before first range)
900        assert_eq!(map.missing_items(0, 5), vec![0, 3, 4, 7, 8]);
901        assert_eq!(map.missing_items(0, 6), vec![0, 3, 4, 7, 8, 9]);
902        assert_eq!(map.missing_items(0, 7), vec![0, 3, 4, 7, 8, 9]);
903
904        // Starting from within first gap
905        assert_eq!(map.missing_items(3, 3), vec![3, 4, 7]);
906        assert_eq!(map.missing_items(4, 2), vec![4, 7]);
907
908        // Starting from within second gap
909        assert_eq!(map.missing_items(7, 10), vec![7, 8, 9]);
910        assert_eq!(map.missing_items(8, 2), vec![8, 9]);
911
912        // Starting after last range (no more gaps)
913        assert_eq!(map.missing_items(11, 5), Vec::<u64>::new());
914        assert_eq!(map.missing_items(100, 10), Vec::<u64>::new());
915    }
916
917    #[test]
918    fn test_missing_items_starting_in_range() {
919        let mut map = RMap::new();
920        map.insert(1);
921        map.insert(2);
922        map.insert(3); // [1, 3]
923        map.insert(7);
924        map.insert(8);
925        map.insert(9); // [1, 3], [7, 9]
926
927        // Starting within first range
928        assert_eq!(map.missing_items(1, 3), vec![4, 5, 6]);
929        assert_eq!(map.missing_items(2, 4), vec![4, 5, 6]);
930        assert_eq!(map.missing_items(3, 2), vec![4, 5]);
931
932        // Starting within second range
933        assert_eq!(map.missing_items(7, 5), Vec::<u64>::new());
934        assert_eq!(map.missing_items(8, 3), Vec::<u64>::new());
935        assert_eq!(map.missing_items(9, 1), Vec::<u64>::new());
936    }
937
938    #[test]
939    #[should_panic]
940    fn test_missing_items_zero_n() {
941        let mut map = RMap::new();
942        map.insert(1);
943        map.insert(5);
944
945        map.missing_items(1, 0);
946    }
947
948    #[test]
949    fn test_missing_items_large_gap() {
950        let mut map = RMap::new();
951        map.insert(1);
952        map.insert(1000);
953
954        // Large gap between 1 and 1000
955        assert_eq!(map.missing_items(2, 5), vec![2, 3, 4, 5, 6]);
956        assert_eq!(map.missing_items(995, 5), vec![995, 996, 997, 998, 999]);
957
958        // Request more items than exist in gap
959        let items = map.missing_items(2, 998);
960        assert_eq!(items.len(), 998);
961        assert_eq!(items[0], 2);
962        assert_eq!(items[997], 999);
963    }
964
965    #[test]
966    fn test_missing_items_at_boundaries() {
967        let mut map = RMap::new();
968        map.insert(5);
969        map.insert(6); // [5, 6]
970        map.insert(10); // [5, 6], [10, 10]
971
972        // Starting at exact boundary of range start
973        assert_eq!(map.missing_items(5, 3), vec![7, 8, 9]);
974
975        // Starting at exact boundary of range end
976        assert_eq!(map.missing_items(6, 3), vec![7, 8, 9]);
977
978        // Starting at isolated range
979        assert_eq!(map.missing_items(10, 5), Vec::<u64>::new());
980    }
981
982    #[test]
983    fn test_missing_items_near_max() {
984        let mut map = RMap::new();
985        map.insert(u64::MAX - 5);
986        map.insert(u64::MAX - 3);
987        map.insert(u64::MAX);
988
989        // Gap: MAX-4, MAX-2, MAX-1
990        assert_eq!(
991            map.missing_items(u64::MAX - 6, 5),
992            vec![u64::MAX - 6, u64::MAX - 4, u64::MAX - 2, u64::MAX - 1]
993        );
994        assert_eq!(
995            map.missing_items(u64::MAX - 4, 3),
996            vec![u64::MAX - 4, u64::MAX - 2, u64::MAX - 1]
997        );
998
999        // Starting at MAX (no gaps possible)
1000        assert_eq!(map.missing_items(u64::MAX, 5), Vec::<u64>::new());
1001    }
1002
1003    #[test]
1004    fn test_missing_items_contiguous_ranges() {
1005        let mut map = RMap::new();
1006        map.insert(1);
1007        map.insert(2);
1008        map.insert(3); // [1, 3]
1009        map.insert(4);
1010        map.insert(5);
1011        map.insert(6); // [1, 6] (merged)
1012
1013        // No gaps in contiguous range
1014        assert_eq!(map.missing_items(0, 3), vec![0]);
1015        assert_eq!(map.missing_items(7, 5), Vec::<u64>::new());
1016    }
1017}
commonware_storage/rmap/mod.rs

commonware_storage/rmap/
mod.rs
