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

commonware_storage/rmap/
mod.rs
