Struct RMap 

pub struct RMap { /* private fields */ }

A collection that manages disjoint, inclusive ranges [start, end].

Implementations

impl RMap

pub fn new() -> Self

Creates a new, empty RMap.

pub fn insert(&mut self, value: u64)

Inserts a value into the RMap.

Behavior

• Create a new range [value, value] if value is isolated.
• Extend an existing range if value is adjacent to it (e.g., inserting 5 into [1, 4] results in [1, 5]).
• Merge two ranges if value bridges them (e.g., inserting 3 into a map with [1, 2] and [4, 5] results in [1, 5]).
• Do nothing if value is already covered by an existing range.

Complexity

The time complexity is typically O(log N) due to BTreeMap lookups and insertions, where N is the number of disjoint ranges in the map. In scenarios involving merges, a few extra map operations (removals, insertions) might occur, but the overall complexity remains logarithmic.

Example

use commonware_storage::rmap::RMap;

let mut map = RMap::new();
map.insert(1); // Map: [1, 1]
assert_eq!(map.next_gap(0), (None, Some(1)));
map.insert(3); // Map: [1, 1], [3, 3]
assert_eq!(map.next_gap(1), (Some(1), Some(3)));
map.insert(2); // Map: [1, 3]
map.insert(0); // Map: [0, 3]
map.insert(5); // Map: [0, 3], [5, 5]
map.insert(4); // Map: [0, 5]
assert_eq!(map.get(&3), Some((0, 5)));

pub fn get(&self, value: &u64) -> Option<(u64, u64)>

Returns the range that contains the given value.

pub fn remove(&mut self, start: u64, end: u64)

Removes a range [start, end] (inclusive) from the RMap.

Behavior

• If the removal range completely covers an existing range, the existing range is removed.
• If the removal range is a sub-range of an existing range, the existing range may be split into two (e.g., removing [3, 4] from [1, 6] results in [1, 2] and [5, 6]).
• If the removal range overlaps with the start or end of an existing range, the existing range is truncated (e.g., removing [1, 2] from [1, 5] results in [3, 5]).
• If the removal range covers multiple existing ranges, all such ranges are affected or removed.
• If start > end, the method does nothing.
• If the removal range does not overlap with any existing range, the map remains unchanged.

Complexity

The time complexity is O(M + K log N), where N is the total number of ranges in the map, M is the number of ranges that overlap with the removal range (iterate part), and K is the number of new ranges created or ranges removed (at most 2 additions and M removals).

Example

use commonware_storage::rmap::RMap;

let mut map = RMap::new();
map.insert(1); map.insert(2); map.insert(3); // Map: [1, 3]
map.insert(5); map.insert(6); map.insert(7); // Map: [1, 3], [5, 7]

map.remove(2, 6); // Results in [1, 1], [7, 7]
assert_eq!(map.get(&1), Some((1, 1)));
assert_eq!(map.get(&2), None);
assert_eq!(map.get(&6), None);
assert_eq!(map.get(&7), Some((7, 7)));

pub fn iter(&self) -> impl Iterator<Item = (&u64, &u64)>

Returns an iterator over the ranges (start, end) in the RMap.

The ranges are yielded in ascending order of their start points. Each tuple represents an inclusive range [start, end].

Example

use commonware_storage::rmap::RMap;

let mut map = RMap::new();
map.insert(0); map.insert(1); // Map: [0, 1]
map.insert(3); map.insert(4); // Map: [0, 1], [3, 4]

let mut iter = map.iter();
assert_eq!(iter.next(), Some((&0, &1)));
assert_eq!(iter.next(), Some((&3, &4)));
assert_eq!(iter.next(), None);

pub fn next_gap(&self, value: u64) -> (Option<u64>, Option<u64>)

Finds the end of the range containing value and the start of the range succeeding value. This method is useful for identifying gaps around a given point.

Behavior

• If value falls within an existing range [r_start, r_end], current_range_end will be Some(r_end).
• If value falls in a gap between two ranges [..., prev_end] and [next_start, ...], current_range_end will be None and next_range_start will be Some(next_start).
• If value is before all ranges in the map, current_range_end will be None.
• If value is after all ranges in the map (or within the last range), next_range_start will be None.
• If the map is empty, both will be None.

Arguments

• value: The u64 value to query around.

Returns

A tuple (Option<u64>, Option<u64>) where:

• 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.
• 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.

Complexity

O(log N) where N is the number of ranges in RMap.

Example

use commonware_storage::rmap::RMap;

let mut map = RMap::new();
map.insert(1); map.insert(2); // Map: [1, 2]
map.insert(5); map.insert(6); // Map: [1, 2], [5, 6]

assert_eq!(map.next_gap(0), (None, Some(1)));        // Before all ranges
assert_eq!(map.next_gap(1), (Some(2), Some(5)));     // Value is at the start of a range
assert_eq!(map.next_gap(2), (Some(2), Some(5)));     // Value is at the end of a range
assert_eq!(map.next_gap(3), (None, Some(5)));     // Value is in a gap
assert_eq!(map.next_gap(5), (Some(6), None));        // Value is at the start of the last range
assert_eq!(map.next_gap(6), (Some(6), None));        // Value is at the end of the last range
assert_eq!(map.next_gap(7), (None, None));        // After all ranges

pub fn missing_items(&self, start: u64, max: usize) -> Vec<u64>

Returns up to max missing items starting from start.

This method iterates through gaps between existing ranges, collecting missing indices until either max items are found or there are no more gaps to fill.

Arguments

• start: The index to start searching from (inclusive).
• max: The maximum number of missing items to return.

Returns

A vector containing up to max missing indices from gaps between ranges. The vector may contain fewer than max items if there aren’t enough gaps. If there are no more ranges after the current position, no items are returned.

Complexity

O(G log N + M) where N is the number of ranges in RMap, G is the number of gaps visited (at most N), and M is the number of missing items returned (at most max). Each gap requires a next_gap call (O(log N)) and collecting items (O(items in gap)).

Example

use commonware_storage::rmap::RMap;

let mut map = RMap::new();
map.insert(1); map.insert(2); // Map: [1, 2]
map.insert(5); map.insert(6); // Map: [1, 2], [5, 6]
map.insert(10);                // Map: [1, 2], [5, 6], [10, 10]

// Starting from 0, find up to 5 missing items
assert_eq!(map.missing_items(0, 5), vec![0, 3, 4, 7, 8]);

// Starting from 3, find up to 3 missing items
assert_eq!(map.missing_items(3, 3), vec![3, 4, 7]);

// Starting from 7, find up to 10 missing items (only gaps are returned)
assert_eq!(map.missing_items(7, 10), vec![7, 8, 9]);

// Starting from 11, there are no more ranges, so no gaps
assert_eq!(map.missing_items(11, 5), Vec::<u64>::new());

Trait Implementations

impl Debug for RMap

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for RMap

fn default() -> RMap

Returns the “default value” for a type.

impl PartialEq for RMap

fn eq(&self, other: &RMap) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for RMap