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 const 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            && *value <= end
129        {
130            return Some((start, end));
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    /// O((M + 1) log N), where N is the number of ranges in the map and M is the number of ranges
151    /// overlapping the removal range. Each overlapping range costs one removal, plus at most two
152    /// insertions in total for the pieces that stick out.
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        // Every range that overlaps or follows `start`, cut off past `end`.
175        let overlapping: Vec<(u64, u64)> = self
176            .iter_from(start)
177            .take_while(|&(&r_start, _)| r_start <= end)
178            .map(|(&r_start, &r_end)| (r_start, r_end))
179            .collect();
180
181        // Remove each overlapping range and re-add whatever sticks out on either side.
182        for (r_start, r_end) in overlapping {
183            self.ranges.remove(&r_start);
184            if r_start < start {
185                self.ranges.insert(r_start, start - 1);
186            }
187            if r_end > end {
188                self.ranges.insert(end + 1, r_end);
189            }
190        }
191    }
192
193    /// Returns an iterator over the ranges `(start, end)` in the [RMap].
194    ///
195    /// The ranges are yielded in ascending order of their start points.
196    /// Each tuple represents an inclusive range `[start, end]`.
197    ///
198    /// # Example
199    ///
200    /// ```
201    /// use commonware_storage::rmap::RMap;
202    ///
203    /// let mut map = RMap::new();
204    /// map.insert(0); map.insert(1); // Map: [0, 1]
205    /// map.insert(3); map.insert(4); // Map: [0, 1], [3, 4]
206    ///
207    /// let mut iter = map.iter();
208    /// assert_eq!(iter.next(), Some((&0, &1)));
209    /// assert_eq!(iter.next(), Some((&3, &4)));
210    /// assert_eq!(iter.next(), None);
211    /// ```
212    pub fn iter(&self) -> impl Iterator<Item = (&u64, &u64)> {
213        self.ranges.iter()
214    }
215
216    /// Returns an iterator over ranges `(start, end)` that overlap or follow `from`.
217    ///
218    /// A range overlaps `from` if its end >= `from`. Ranges are yielded in
219    /// ascending order of their start points.
220    ///
221    /// # Example
222    ///
223    /// ```
224    /// use commonware_storage::rmap::RMap;
225    ///
226    /// let mut map = RMap::new();
227    /// map.insert(0); map.insert(1); // Map: [0, 1]
228    /// map.insert(3); map.insert(4); // Map: [0, 1], [3, 4]
229    /// map.insert(7); // Map: [0, 1], [3, 4], [7, 7]
230    ///
231    /// let v: Vec<_> = map.iter_from(2).collect();
232    /// assert_eq!(v, vec![(&3, &4), (&7, &7)]);
233    ///
234    /// let v: Vec<_> = map.iter_from(1).collect();
235    /// assert_eq!(v, vec![(&0, &1), (&3, &4), (&7, &7)]);
236    ///
237    /// let v: Vec<_> = map.iter_from(4).collect();
238    /// assert_eq!(v, vec![(&3, &4), (&7, &7)]);
239    /// ```
240    pub fn iter_from(&self, from: u64) -> impl Iterator<Item = (&u64, &u64)> {
241        // The last range whose start <= `from` might contain `from` (if its end >= `from`).
242        let candidate = self
243            .ranges
244            .range(..=from)
245            .next_back()
246            .filter(|&(_, &end)| end >= from);
247
248        // All ranges starting after `from` are guaranteed to follow.
249        let tail = match from {
250            u64::MAX => None,
251            _ => Some(self.ranges.range(from + 1..)),
252        };
253        candidate.into_iter().chain(tail.into_iter().flatten())
254    }
255
256    /// Retrieve the first index in the [RMap].
257    ///
258    /// # Example
259    ///
260    /// ```
261    /// use commonware_storage::rmap::RMap;
262    ///
263    /// let mut map = RMap::new();
264    /// assert_eq!(map.first_index(), None);
265    /// map.insert(3); map.insert(4); // Map: [3, 4]
266    /// assert_eq!(map.first_index(), Some(3));
267    /// map.insert(1); // Map: [1, 1], [3, 4]
268    /// assert_eq!(map.first_index(), Some(1));
269    /// ```
270    pub fn first_index(&self) -> Option<u64> {
271        self.ranges.first_key_value().map(|(&start, _)| start)
272    }
273
274    /// Retrieve the last index in the [RMap].
275    ///
276    /// # Example
277    ///
278    /// ```
279    /// use commonware_storage::rmap::RMap;
280    ///
281    /// let mut map = RMap::new();
282    /// assert_eq!(map.last_index(), None);
283    /// map.insert(1); map.insert(2); // Map: [1, 2]
284    /// assert_eq!(map.last_index(), Some(2));
285    /// map.insert(5); // Map: [1, 2], [5, 5]
286    /// assert_eq!(map.last_index(), Some(5));
287    /// ```
288    pub fn last_index(&self) -> Option<u64> {
289        self.ranges.last_key_value().map(|(_, &end)| end)
290    }
291
292    /// Finds the end of the range containing `value` and the start of the
293    /// range succeeding `value`. This method is useful for identifying gaps around a given point.
294    ///
295    /// # Behavior
296    ///
297    /// - If `value` falls within an existing range `[r_start, r_end]`, `current_range_end` will be `Some(r_end)`.
298    /// - If `value` falls in a gap between two ranges `[..., prev_end]` and `[next_start, ...]`,
299    ///   `current_range_end` will be `None` and `next_range_start` will be `Some(next_start)`.
300    /// - If `value` is before all ranges in the map, `current_range_end` will be `None`.
301    /// - If `value` is after all ranges in the map (or within the last range), `next_range_start` will be `None`.
302    /// - If the map is empty, both will be `None`.
303    ///
304    /// # Arguments
305    ///
306    /// * `value`: The `u64` value to query around.
307    ///
308    /// # Returns
309    ///
310    /// A tuple `(Option<u64>, Option<u64>)` where:
311    /// - 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.
312    /// - 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.
313    ///
314    /// # Complexity
315    ///
316    /// O(log N) where N is the number of ranges in [RMap].
317    ///
318    /// # Example
319    ///
320    /// ```
321    /// use commonware_storage::rmap::RMap;
322    ///
323    /// let mut map = RMap::new();
324    /// map.insert(1); map.insert(2); // Map: [1, 2]
325    /// map.insert(5); map.insert(6); // Map: [1, 2], [5, 6]
326    ///
327    /// assert_eq!(map.next_gap(0), (None, Some(1)));        // Before all ranges
328    /// assert_eq!(map.next_gap(1), (Some(2), Some(5)));     // Value is at the start of a range
329    /// assert_eq!(map.next_gap(2), (Some(2), Some(5)));     // Value is at the end of a range
330    /// assert_eq!(map.next_gap(3), (None, Some(5)));     // Value is in a gap
331    /// assert_eq!(map.next_gap(5), (Some(6), None));        // Value is at the start of the last range
332    /// assert_eq!(map.next_gap(6), (Some(6), None));        // Value is at the end of the last range
333    /// assert_eq!(map.next_gap(7), (None, None));        // After all ranges
334    /// ```
335    pub fn next_gap(&self, value: u64) -> (Option<u64>, Option<u64>) {
336        let current_range_end = match self.ranges.range(..=value).next_back().map(|(_, &end)| end) {
337            Some(end) if end >= value => Some(end),
338            _ => None,
339        };
340
341        let next_range_start = match value {
342            u64::MAX => None,
343            _ => self
344                .ranges
345                .range(value + 1..)
346                .next()
347                .map(|(&start, _)| start),
348        };
349
350        (current_range_end, next_range_start)
351    }
352
353    /// Returns up to `max` missing items starting from `start`.
354    ///
355    /// This method iterates through gaps between existing ranges, collecting missing indices
356    /// until either `max` items are found or there are no more gaps to fill.
357    ///
358    /// # Arguments
359    ///
360    /// * `start`: The index to start searching from (inclusive).
361    /// * `max`: The maximum number of missing items to return.
362    ///
363    /// # Returns
364    ///
365    /// A vector containing up to `max` missing indices from gaps between ranges.
366    /// The vector may contain fewer than `max` items if there aren't enough gaps.
367    /// If there are no more ranges after the current position, no items are returned.
368    ///
369    /// # Complexity
370    ///
371    /// O(log N + M) where N is the number of ranges in [RMap] and M is the number of missing items
372    /// returned (at most `max`).
373    ///
374    /// # Example
375    ///
376    /// ```
377    /// use commonware_storage::rmap::RMap;
378    ///
379    /// let mut map = RMap::new();
380    /// map.insert(1); map.insert(2); // Map: [1, 2]
381    /// map.insert(5); map.insert(6); // Map: [1, 2], [5, 6]
382    /// map.insert(10);                // Map: [1, 2], [5, 6], [10, 10]
383    ///
384    /// // Starting from 0, find up to 5 missing items
385    /// assert_eq!(map.missing_items(0, 5), vec![0, 3, 4, 7, 8]);
386    ///
387    /// // Starting from 3, find up to 3 missing items
388    /// assert_eq!(map.missing_items(3, 3), vec![3, 4, 7]);
389    ///
390    /// // Starting from 7, find up to 10 missing items (only gaps are returned)
391    /// assert_eq!(map.missing_items(7, 10), vec![7, 8, 9]);
392    ///
393    /// // Starting from 11, there are no more ranges, so no gaps
394    /// assert_eq!(map.missing_items(11, 5), Vec::<u64>::new());
395    /// ```
396    pub fn missing_items(&self, start: u64, max: usize) -> Vec<u64> {
397        // Ensure input is valid
398        assert!(max > 0, "max must be greater than 0");
399        let mut missing = Vec::with_capacity(max);
400
401        // Each range closes the gap before it. The scan then resumes past it.
402        let mut current = start;
403        for (&r_start, &r_end) in self.iter_from(start) {
404            missing.extend((current..r_start).take(max - missing.len()));
405            if missing.len() == max {
406                break;
407            }
408            let Some(next) = r_end.checked_add(1) else {
409                break;
410            };
411            current = next;
412        }
413        missing
414    }
415}
416
417#[cfg(test)]
418mod tests {
419    use super::*;
420
421    #[test]
422    fn test_new() {
423        let map = RMap::new();
424        assert_eq!(map.iter().count(), 0);
425    }
426
427    #[test]
428    fn test_insert_empty() {
429        let mut map = RMap::new();
430        map.insert(5);
431        assert_eq!(map.get(&5), Some((5, 5)));
432        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &5)]);
433    }
434
435    #[test]
436    fn test_insert_isolated() {
437        let mut map = RMap::new();
438        map.insert(5);
439        map.insert(10);
440        assert_eq!(map.get(&5), Some((5, 5)));
441        assert_eq!(map.get(&10), Some((10, 10)));
442        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &5), (&10, &10)]);
443    }
444
445    #[test]
446    fn test_insert_covered() {
447        let mut map = RMap::new();
448        map.insert(1);
449        map.insert(2);
450        map.insert(3); // Range is 1-3
451        map.insert(2); // Insert value already covered
452        assert_eq!(map.get(&1), Some((1, 3)));
453        assert_eq!(map.get(&2), Some((1, 3)));
454        assert_eq!(map.get(&3), Some((1, 3)));
455        assert_eq!(map.iter().count(), 1);
456        assert_eq!(map.iter().next(), Some((&1, &3)));
457    }
458
459    #[test]
460    fn test_insert_adjacent_end() {
461        let mut map = RMap::new();
462        map.insert(1);
463        map.insert(2); // Range is 1-2
464        map.insert(3); // Adjacent to end
465        assert_eq!(map.get(&1), Some((1, 3)));
466        assert_eq!(map.get(&3), Some((1, 3)));
467        assert_eq!(map.iter().next(), Some((&1, &3)));
468    }
469
470    #[test]
471    fn test_insert_adjacent_start() {
472        let mut map = RMap::new();
473        map.insert(2);
474        map.insert(3); // Range is 2-3
475        map.insert(1); // Adjacent to start
476        assert_eq!(map.get(&1), Some((1, 3)));
477        assert_eq!(map.get(&3), Some((1, 3)));
478        assert_eq!(map.iter().next(), Some((&1, &3)));
479    }
480
481    #[test]
482    fn test_insert_bridge_ranges() {
483        let mut map = RMap::new();
484        map.insert(1);
485        map.insert(2);
486        assert_eq!(map.get(&1), Some((1, 2)));
487        map.insert(5);
488        map.insert(6);
489        assert_eq!(map.get(&5), Some((5, 6)));
490        // Current: (1,2), (5,6)
491        map.insert(3); // Insert 3, should become (1,3), (5,6)
492        assert_eq!(map.get(&1), Some((1, 3)));
493        assert_eq!(map.get(&2), Some((1, 3)));
494        assert_eq!(map.get(&3), Some((1, 3)));
495        assert_eq!(map.get(&5), Some((5, 6)));
496        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&1, &3), (&5, &6)]);
497
498        map.insert(4); // Insert 4, should bridge to (1,6)
499        assert_eq!(map.get(&1), Some((1, 6)));
500        assert_eq!(map.get(&3), Some((1, 6)));
501        assert_eq!(map.get(&4), Some((1, 6)));
502        assert_eq!(map.get(&6), Some((1, 6)));
503        assert_eq!(map.iter().count(), 1);
504        assert_eq!(map.iter().next(), Some((&1, &6)));
505    }
506
507    #[test]
508    fn test_insert_complex_merging_and_ordering() {
509        let mut map = RMap::new();
510        map.insert(10); // (10,10)
511        map.insert(12); // (10,10), (12,12)
512        map.insert(11); // (10,12)
513        assert_eq!(map.get(&10), Some((10, 12)));
514        assert_eq!(map.get(&11), Some((10, 12)));
515        assert_eq!(map.get(&12), Some((10, 12)));
516
517        map.insert(15); // (10,12), (15,15)
518        map.insert(13); // (10,13), (15,15)
519        assert_eq!(map.get(&13), Some((10, 13)));
520        assert_eq!(map.get(&12), Some((10, 13)));
521        assert_eq!(map.get(&15), Some((15, 15)));
522
523        map.insert(14); // (10,15)
524        assert_eq!(map.get(&10), Some((10, 15)));
525        assert_eq!(map.get(&14), Some((10, 15)));
526        assert_eq!(map.get(&15), Some((10, 15)));
527        assert_eq!(map.iter().count(), 1);
528        assert_eq!(map.iter().next(), Some((&10, &15)));
529
530        map.insert(5); // (5,5), (10,15)
531        map.insert(7); // (5,5), (7,7), (10,15)
532        map.insert(6); // (5,7), (10,15)
533        assert_eq!(map.get(&5), Some((5, 7)));
534        assert_eq!(map.get(&6), Some((5, 7)));
535        assert_eq!(map.get(&7), Some((5, 7)));
536        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &7), (&10, &15)]);
537
538        map.insert(9); // (5,7), (9,9), (10,15) -> should become (5,7), (9,15)
539        assert_eq!(map.get(&9), Some((9, 15)));
540        assert_eq!(map.get(&10), Some((9, 15)));
541        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&5, &7), (&9, &15)]);
542
543        map.insert(8); // (5,15)
544        assert_eq!(map.get(&5), Some((5, 15)));
545        assert_eq!(map.get(&8), Some((5, 15)));
546        assert_eq!(map.get(&15), Some((5, 15)));
547        assert_eq!(map.iter().next(), Some((&5, &15)));
548    }
549
550    #[test]
551    fn test_insert_max_value() {
552        let mut map = RMap::new();
553        map.insert(u64::MAX);
554        assert_eq!(map.get(&u64::MAX), Some((u64::MAX, u64::MAX)));
555        map.insert(u64::MAX - 1);
556        assert_eq!(map.get(&(u64::MAX - 1)), Some((u64::MAX - 1, u64::MAX)));
557        assert_eq!(map.get(&u64::MAX), Some((u64::MAX - 1, u64::MAX)));
558    }
559
560    #[test]
561    fn test_get() {
562        let mut map = RMap::new();
563        map.insert(1);
564        map.insert(2);
565        map.insert(3); // Range 1-3
566        map.insert(5);
567        map.insert(6); // Range 5-6
568
569        assert_eq!(map.get(&1), Some((1, 3)));
570        assert_eq!(map.get(&2), Some((1, 3)));
571        assert_eq!(map.get(&3), Some((1, 3)));
572        assert_eq!(map.get(&4), None);
573        assert_eq!(map.get(&5), Some((5, 6)));
574        assert_eq!(map.get(&6), Some((5, 6)));
575        assert_eq!(map.get(&0), None);
576        assert_eq!(map.get(&7), None);
577    }
578
579    #[test]
580    fn test_remove_empty() {
581        let mut map = RMap::new();
582        map.remove(1, 5);
583        assert_eq!(map.iter().count(), 0);
584    }
585
586    #[test]
587    fn test_remove_invalid_range() {
588        let mut map = RMap::new();
589        map.insert(1);
590        map.insert(2); // 1-2
591        map.remove(5, 1); // start > end, should do nothing
592        assert_eq!(map.iter().next(), Some((&1, &2)));
593    }
594
595    #[test]
596    fn test_remove_non_existent() {
597        let mut map = RMap::new();
598        map.insert(5);
599        map.insert(6); // 5-6
600        map.remove(1, 3); // Before existing
601        assert_eq!(map.iter().next(), Some((&5, &6)));
602        map.remove(8, 10); // After existing
603        assert_eq!(map.iter().next(), Some((&5, &6)));
604        map.remove(1, 10); // Covers existing
605        assert_eq!(map.iter().count(), 0);
606    }
607
608    #[test]
609    fn test_remove_exact_match() {
610        let mut map = RMap::new();
611        map.insert(1);
612        map.insert(2);
613        map.insert(3); // 1-3
614        map.insert(5);
615        map.insert(6); // 5-6
616        map.remove(1, 3);
617        assert_eq!(map.get(&2), None);
618        assert_eq!(map.iter().next(), Some((&5, &6)));
619        map.remove(5, 6);
620        assert_eq!(map.iter().count(), 0);
621    }
622
623    #[test]
624    fn test_remove_subset_split() {
625        let mut map = RMap::new();
626        map.insert(1);
627        map.insert(2);
628        map.insert(3);
629        map.insert(4);
630        map.insert(5); // 1-5
631        map.remove(3, 3); // Remove 3 from 1-5 -> (1,2), (4,5)
632        assert_eq!(map.get(&2), Some((1, 2)));
633        assert_eq!(map.get(&3), None);
634        assert_eq!(map.get(&4), Some((4, 5)));
635        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&1, &2), (&4, &5)]);
636
637        // Reset and test another split
638        let mut map2 = RMap::new();
639        map2.insert(1);
640        map2.insert(2);
641        map2.insert(3);
642        map2.insert(4);
643        map2.insert(5); // 1-5
644        map2.remove(2, 4); // Remove 2-4 from 1-5 -> (1,1), (5,5)
645        assert_eq!(map2.get(&1), Some((1, 1)));
646        assert_eq!(map2.get(&2), None);
647        assert_eq!(map2.get(&3), None);
648        assert_eq!(map2.get(&4), None);
649        assert_eq!(map2.get(&5), Some((5, 5)));
650        assert_eq!(map2.iter().collect::<Vec<_>>(), vec![(&1, &1), (&5, &5)]);
651    }
652
653    #[test]
654    fn test_remove_overlap_start() {
655        let mut map = RMap::new();
656        map.insert(1);
657        map.insert(2);
658        map.insert(3);
659        map.insert(4);
660        map.insert(5); // 1-5
661        map.remove(0, 2); // Remove 0-2 from 1-5 -> (3,5)
662        assert_eq!(map.get(&1), None);
663        assert_eq!(map.get(&2), None);
664        assert_eq!(map.get(&3), Some((3, 5)));
665        assert_eq!(map.iter().next(), Some((&3, &5)));
666    }
667
668    #[test]
669    fn test_remove_overlap_end() {
670        let mut map = RMap::new();
671        map.insert(1);
672        map.insert(2);
673        map.insert(3);
674        map.insert(4);
675        map.insert(5); // 1-5
676        map.remove(4, 6); // Remove 4-6 from 1-5 -> (1,3)
677        assert_eq!(map.get(&3), Some((1, 3)));
678        assert_eq!(map.get(&4), None);
679        assert_eq!(map.get(&5), None);
680        assert_eq!(map.iter().next(), Some((&1, &3)));
681    }
682
683    #[test]
684    fn test_remove_cover_multiple_ranges() {
685        let mut map = RMap::new();
686        map.insert(1);
687        map.insert(2); // 1-2
688        map.insert(4);
689        map.insert(5); // 4-5
690        map.insert(7);
691        map.insert(8); // 7-8
692
693        map.remove(3, 6); // Removes 4-5, no truncation as 3 and 6 are in gaps. (1,2), (7,8)
694        assert_eq!(map.get(&2), Some((1, 2)));
695        assert_eq!(map.get(&4), None);
696        assert_eq!(map.get(&5), None);
697        assert_eq!(map.get(&7), Some((7, 8)));
698        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&1, &2), (&7, &8)]);
699
700        map.remove(0, 10); // Removes all remaining ranges
701        assert_eq!(map.iter().count(), 0);
702    }
703
704    #[test]
705    fn test_remove_partial_overlap_multiple_ranges() {
706        let mut map = RMap::new();
707        map.insert(1);
708        map.insert(2);
709        map.insert(3); // 1-3
710        map.insert(5);
711        map.insert(6);
712        map.insert(7); // 5-7
713        map.insert(9);
714        map.insert(10);
715        map.insert(11); // 9-11
716
717        map.remove(2, 6); // Affects 1-3 (becomes 1-1) and 5-7 (becomes 7-7)
718        assert_eq!(map.get(&1), Some((1, 1)));
719        assert_eq!(map.get(&2), None);
720        assert_eq!(map.get(&3), None);
721        assert_eq!(map.get(&5), None);
722        assert_eq!(map.get(&6), None);
723        assert_eq!(map.get(&7), Some((7, 7)));
724        assert_eq!(map.get(&9), Some((9, 11)));
725        assert_eq!(
726            map.iter().collect::<Vec<_>>(),
727            vec![(&1, &1), (&7, &7), (&9, &11)]
728        );
729
730        // Reset and test removing all
731        let mut map2 = RMap::new();
732        map2.insert(1);
733        map2.insert(2);
734        map2.insert(3);
735        map2.insert(5);
736        map2.insert(6);
737        map2.insert(7);
738        map2.insert(9);
739        map2.insert(10);
740        map2.insert(11);
741        map2.remove(0, 20); // remove all
742        assert_eq!(map2.iter().count(), 0);
743    }
744
745    #[test]
746    fn test_remove_touching_boundaries_no_merge() {
747        let mut map = RMap::new();
748        map.insert(0);
749        map.insert(1);
750        map.insert(2); // 0-2
751        map.insert(4);
752        map.insert(5); // 4-5
753
754        // Remove range that is exactly between two existing ranges
755        map.remove(3, 3);
756        assert_eq!(map.iter().collect::<Vec<_>>(), vec![(&0, &2), (&4, &5)]);
757    }
758
759    #[test]
760    fn test_remove_max_value_ranges() {
761        let mut map = RMap::new();
762        map.insert(u64::MAX - 2);
763        map.insert(u64::MAX - 1);
764        map.insert(u64::MAX); // MAX-2 to MAX
765
766        map.remove(u64::MAX, u64::MAX); // Remove MAX -> (MAX-2, MAX-1)
767        assert_eq!(map.get(&(u64::MAX - 2)), Some((u64::MAX - 2, u64::MAX - 1)));
768        assert_eq!(map.get(&u64::MAX), None);
769
770        map.remove(u64::MAX - 2, u64::MAX - 2); // Remove MAX-2 -> (MAX-1, MAX-1)
771        assert_eq!(map.get(&(u64::MAX - 2)), None);
772        assert_eq!(map.get(&(u64::MAX - 1)), Some((u64::MAX - 1, u64::MAX - 1)));
773
774        map.remove(u64::MAX - 1, u64::MAX - 1); // Remove MAX-1 -> empty
775        assert_eq!(map.iter().count(), 0);
776
777        map.insert(u64::MAX - 1);
778        map.insert(u64::MAX); // MAX-1 to MAX
779        map.remove(u64::MIN, u64::MAX); // Remove all
780        assert_eq!(map.iter().count(), 0);
781    }
782
783    #[test]
784    fn test_iter() {
785        let mut map = RMap::new();
786        assert_eq!(map.iter().next(), None);
787        map.insert(5);
788        map.insert(6); // 5-6
789        map.insert(1);
790        map.insert(2); // 1-2
791        let mut iter = map.iter();
792        assert_eq!(iter.next(), Some((&1, &2)));
793        assert_eq!(iter.next(), Some((&5, &6)));
794        assert_eq!(iter.next(), None);
795    }
796
797    #[test]
798    fn test_first_index() {
799        let mut map = RMap::new();
800        assert_eq!(map.first_index(), None);
801
802        map.insert(5);
803        map.insert(6); // [5, 6]
804        assert_eq!(map.first_index(), Some(5));
805
806        map.insert(1); // [1, 1], [5, 6]
807        assert_eq!(map.first_index(), Some(1));
808
809        map.remove(0, 4); // [5, 6]
810        assert_eq!(map.first_index(), Some(5));
811
812        map.remove(5, 6); // empty
813        assert_eq!(map.first_index(), None);
814    }
815
816    #[test]
817    fn test_last_index() {
818        let mut map = RMap::new();
819        assert_eq!(map.last_index(), None);
820
821        map.insert(1);
822        map.insert(2); // [1, 2]
823        assert_eq!(map.last_index(), Some(2));
824
825        map.insert(5); // [1, 2], [5, 5]
826        assert_eq!(map.last_index(), Some(5));
827
828        map.insert(6); // [1, 2], [5, 6]
829        assert_eq!(map.last_index(), Some(6));
830
831        map.remove(5, 10); // [1, 2]
832        assert_eq!(map.last_index(), Some(2));
833
834        map.remove(0, 2); // empty
835        assert_eq!(map.last_index(), None);
836    }
837
838    #[test]
839    fn test_next_gap_empty() {
840        let map = RMap::new();
841        assert_eq!(map.next_gap(5), (None, None));
842    }
843
844    #[test]
845    fn test_next_gap_single_range() {
846        let mut map = RMap::new();
847        map.insert(5);
848        map.insert(6);
849        map.insert(7); // 5-7
850        assert_eq!(map.next_gap(4), (None, Some(5))); // Before range
851        assert_eq!(map.next_gap(5), (Some(7), None)); // Start of range
852        assert_eq!(map.next_gap(6), (Some(7), None)); // Middle of range
853        assert_eq!(map.next_gap(7), (Some(7), None)); // End of range
854        assert_eq!(map.next_gap(8), (None, None)); // After range
855    }
856
857    #[test]
858    fn test_next_gap_multiple_ranges() {
859        let mut map = RMap::new();
860        map.insert(1);
861        map.insert(2); // 1-2
862        map.insert(5);
863        map.insert(6); // 5-6
864        map.insert(10); // 10-10
865
866        assert_eq!(map.next_gap(0), (None, Some(1))); // Before all
867        assert_eq!(map.next_gap(1), (Some(2), Some(5))); // Start of first range
868        assert_eq!(map.next_gap(2), (Some(2), Some(5))); // End of first range
869        assert_eq!(map.next_gap(3), (None, Some(5))); // Gap between 1st and 2nd
870        assert_eq!(map.next_gap(4), (None, Some(5))); // Gap, closer to 2nd
871        assert_eq!(map.next_gap(5), (Some(6), Some(10))); // Start of 2nd range
872        assert_eq!(map.next_gap(6), (Some(6), Some(10))); // End of 2nd range
873        assert_eq!(map.next_gap(7), (None, Some(10))); // Gap between 2nd and 3rd
874        assert_eq!(map.next_gap(8), (None, Some(10))); // Gap
875        assert_eq!(map.next_gap(9), (None, Some(10))); // Gap, closer to 3rd
876        assert_eq!(map.next_gap(10), (Some(10), None)); // Start/End of 3rd range
877        assert_eq!(map.next_gap(11), (None, None)); // After all
878    }
879
880    #[test]
881    fn test_next_gap_value_is_max() {
882        let mut map = RMap::new();
883        map.insert(u64::MAX - 5);
884        map.insert(u64::MAX - 4); // MAX-5 to MAX-4
885        map.insert(u64::MAX - 1);
886        map.insert(u64::MAX); // MAX-1 to MAX
887
888        assert_eq!(map.next_gap(u64::MAX - 6), (None, Some(u64::MAX - 5)));
889        assert_eq!(
890            map.next_gap(u64::MAX - 5),
891            (Some(u64::MAX - 4), Some(u64::MAX - 1))
892        );
893        assert_eq!(
894            map.next_gap(u64::MAX - 4),
895            (Some(u64::MAX - 4), Some(u64::MAX - 1))
896        );
897        assert_eq!(map.next_gap(u64::MAX - 3), (None, Some(u64::MAX - 1))); // In gap
898        assert_eq!(map.next_gap(u64::MAX - 2), (None, Some(u64::MAX - 1))); // In gap
899        assert_eq!(map.next_gap(u64::MAX - 1), (Some(u64::MAX), None));
900        assert_eq!(map.next_gap(u64::MAX), (Some(u64::MAX), None));
901    }
902
903    #[test]
904    fn test_odd_ranges() {
905        // Insert values
906        let mut map = RMap::new();
907        map.insert(1);
908        map.insert(10);
909        map.insert(11);
910        map.insert(14);
911
912        // Sanity check next_gap
913        assert_eq!(map.next_gap(0), (None, Some(1)));
914        assert_eq!(map.next_gap(1), (Some(1), Some(10)));
915        assert_eq!(map.next_gap(10), (Some(11), Some(14)));
916        assert_eq!(map.next_gap(11), (Some(11), Some(14)));
917        assert_eq!(map.next_gap(12), (None, Some(14)));
918        assert_eq!(map.next_gap(14), (Some(14), None));
919    }
920
921    #[test]
922    fn test_missing_items_empty_map() {
923        let map = RMap::new();
924        assert_eq!(map.missing_items(0, 5), Vec::<u64>::new());
925        assert_eq!(map.missing_items(100, 10), Vec::<u64>::new());
926    }
927
928    #[test]
929    fn test_missing_items_single_gap() {
930        let mut map = RMap::new();
931        map.insert(1);
932        map.insert(2); // [1, 2]
933        map.insert(5);
934        map.insert(6); // [1, 2], [5, 6]
935
936        // Gap between ranges: 3, 4
937        assert_eq!(map.missing_items(3, 5), vec![3, 4]);
938        assert_eq!(map.missing_items(3, 2), vec![3, 4]);
939        assert_eq!(map.missing_items(3, 1), vec![3]);
940        assert_eq!(map.missing_items(4, 1), vec![4]);
941    }
942
943    #[test]
944    fn test_missing_items_multiple_gaps() {
945        let mut map = RMap::new();
946        map.insert(1);
947        map.insert(2); // [1, 2]
948        map.insert(5);
949        map.insert(6); // [1, 2], [5, 6]
950        map.insert(10); // [1, 2], [5, 6], [10, 10]
951
952        // Starting from 0 (before first range)
953        assert_eq!(map.missing_items(0, 5), vec![0, 3, 4, 7, 8]);
954        assert_eq!(map.missing_items(0, 6), vec![0, 3, 4, 7, 8, 9]);
955        assert_eq!(map.missing_items(0, 7), vec![0, 3, 4, 7, 8, 9]);
956
957        // Starting from within first gap
958        assert_eq!(map.missing_items(3, 3), vec![3, 4, 7]);
959        assert_eq!(map.missing_items(4, 2), vec![4, 7]);
960
961        // Starting from within second gap
962        assert_eq!(map.missing_items(7, 10), vec![7, 8, 9]);
963        assert_eq!(map.missing_items(8, 2), vec![8, 9]);
964
965        // Starting after last range (no more gaps)
966        assert_eq!(map.missing_items(11, 5), Vec::<u64>::new());
967        assert_eq!(map.missing_items(100, 10), Vec::<u64>::new());
968    }
969
970    #[test]
971    fn test_missing_items_starting_in_range() {
972        let mut map = RMap::new();
973        map.insert(1);
974        map.insert(2);
975        map.insert(3); // [1, 3]
976        map.insert(7);
977        map.insert(8);
978        map.insert(9); // [1, 3], [7, 9]
979
980        // Starting within first range
981        assert_eq!(map.missing_items(1, 3), vec![4, 5, 6]);
982        assert_eq!(map.missing_items(2, 4), vec![4, 5, 6]);
983        assert_eq!(map.missing_items(3, 2), vec![4, 5]);
984
985        // Starting within second range
986        assert_eq!(map.missing_items(7, 5), Vec::<u64>::new());
987        assert_eq!(map.missing_items(8, 3), Vec::<u64>::new());
988        assert_eq!(map.missing_items(9, 1), Vec::<u64>::new());
989    }
990
991    #[test]
992    #[should_panic]
993    fn test_missing_items_zero_n() {
994        let mut map = RMap::new();
995        map.insert(1);
996        map.insert(5);
997
998        map.missing_items(1, 0);
999    }
1000
1001    #[test]
1002    fn test_missing_items_large_gap() {
1003        let mut map = RMap::new();
1004        map.insert(1);
1005        map.insert(1000);
1006
1007        // Large gap between 1 and 1000
1008        assert_eq!(map.missing_items(2, 5), vec![2, 3, 4, 5, 6]);
1009        assert_eq!(map.missing_items(995, 5), vec![995, 996, 997, 998, 999]);
1010
1011        // Request more items than exist in gap
1012        let items = map.missing_items(2, 998);
1013        assert_eq!(items.len(), 998);
1014        assert_eq!(items[0], 2);
1015        assert_eq!(items[997], 999);
1016    }
1017
1018    #[test]
1019    fn test_missing_items_at_boundaries() {
1020        let mut map = RMap::new();
1021        map.insert(5);
1022        map.insert(6); // [5, 6]
1023        map.insert(10); // [5, 6], [10, 10]
1024
1025        // Starting at exact boundary of range start
1026        assert_eq!(map.missing_items(5, 3), vec![7, 8, 9]);
1027
1028        // Starting at exact boundary of range end
1029        assert_eq!(map.missing_items(6, 3), vec![7, 8, 9]);
1030
1031        // Starting at isolated range
1032        assert_eq!(map.missing_items(10, 5), Vec::<u64>::new());
1033    }
1034
1035    #[test]
1036    fn test_missing_items_near_max() {
1037        let mut map = RMap::new();
1038        map.insert(u64::MAX - 5);
1039        map.insert(u64::MAX - 3);
1040        map.insert(u64::MAX);
1041
1042        // Gap: MAX-4, MAX-2, MAX-1
1043        assert_eq!(
1044            map.missing_items(u64::MAX - 6, 5),
1045            vec![u64::MAX - 6, u64::MAX - 4, u64::MAX - 2, u64::MAX - 1]
1046        );
1047        assert_eq!(
1048            map.missing_items(u64::MAX - 4, 3),
1049            vec![u64::MAX - 4, u64::MAX - 2, u64::MAX - 1]
1050        );
1051
1052        // Starting at MAX (no gaps possible)
1053        assert_eq!(map.missing_items(u64::MAX, 5), Vec::<u64>::new());
1054    }
1055
1056    #[test]
1057    fn test_missing_items_range_ending_at_max() {
1058        let mut map = RMap::new();
1059        map.insert(u64::MAX - 2);
1060        map.insert(u64::MAX - 1);
1061        map.insert(u64::MAX); // [MAX-2, MAX]
1062
1063        assert_eq!(map.missing_items(u64::MAX - 2, 3), Vec::<u64>::new());
1064        assert_eq!(map.missing_items(u64::MAX - 1, 3), Vec::<u64>::new());
1065        assert_eq!(map.missing_items(u64::MAX, 3), Vec::<u64>::new());
1066    }
1067
1068    #[test]
1069    fn test_missing_items_contiguous_ranges() {
1070        let mut map = RMap::new();
1071        map.insert(1);
1072        map.insert(2);
1073        map.insert(3); // [1, 3]
1074        map.insert(4);
1075        map.insert(5);
1076        map.insert(6); // [1, 6] (merged)
1077
1078        // No gaps in contiguous range
1079        assert_eq!(map.missing_items(0, 3), vec![0]);
1080        assert_eq!(map.missing_items(7, 5), Vec::<u64>::new());
1081    }
1082}
commonware_storage/rmap/mod.rs

commonware_storage/rmap/
mod.rs
