Struct range_map_vec::RangeMap

source ·

pub struct RangeMap<K, V> { /* private fields */ }

Expand description

A range map that supports lookups for a value V, based on a key type K. Ranges are defined as a RangeInclusive. The map does not allow overlapping ranges.

This implementation is done by using a sorted vec and using binary search for insertion and removal.

Implementations§

source §

impl<K, V> RangeMap<K, V>
where K: PartialOrd + Clone,

source

pub fn new() -> Self

Create a new empty RangeMap.

source

pub fn entry(&mut self, range: RangeInclusive<K>) -> Entry<'_, K, V>

Returns an entry for the given range. If the range overlaps an existing region, returns an Entry::Overlapping; otherwise, returns Entry::Vacant.

Note that there could be multiple ranges in the map that overlap the given range but only one overlap will be returned by this function.

This function panics if range.is_empty() is true.

source

pub fn insert(&mut self, range: RangeInclusive<K>, value: V) -> bool

Insert a new range into the map.

Returns true if the map did not contain an overlapping range. Returns false if the map contained an overlapping range.

This function panics if range.is_empty() is true.

Note that two entries with adjacent ranges that contain the same value are not merged. Adjacent entries can be merged using RangeMap::merge_adjacent.

§Examples

use range_map_vec::RangeMap;

let mut map: RangeMap<u64, u64> = RangeMap::new();
assert_eq!(map.insert(0..=5, 0), true);
assert_eq!(map.insert(1..=20, 1), false);
assert_eq!(map.get_entry(&3).unwrap(), &(0, 5, 0));

source

pub fn remove(&mut self, value: &K) -> Option<(K, K, V)>

Remove a given range from the map given a value covered by the range. Returns the value removed from the map, (start, end, value), if any.

source

pub fn remove_range(&mut self, range: RangeInclusive<K>) -> Vec<(K, K, V)>

Removes any entries that overlaps the specified range. Returns a sorted vector representing ranges removed.

source

pub fn into_vec(self) -> Vec<(K, K, V)>

Remove all ranges in the map and return them as a Vec, with (start, end, value).

source

pub fn contains(&self, value: &K) -> bool

Returns true if the map contains an range that covers the value.

source

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

Returns a reference to the value covered by a range in the map, if any.

use range_map_vec::RangeMap;

let mut map: RangeMap<u64, u64> = RangeMap::new();
assert_eq!(map.insert(0..=3, 0), true);
assert_eq!(map.insert(5..=10, 1), true);
assert_eq!(map.get(&3).unwrap(), &0);
assert!(map.get(&4).is_none());

source

pub fn get_range(&self, range: RangeInclusive<K>) -> Option<&V>

Returns a reference to the value that overlaps the given range, if any.

Note that there could be multiple ranges in the map that overlap the given range but only one overlap will be returned by this function.

This function panics if range.is_empty() is true.

source

pub fn get_entry(&self, value: &K) -> Option<&(K, K, V)>

Returns a reference to the entry that covers value, if any.

source

pub fn get_range_entry(&self, range: RangeInclusive<K>) -> Option<&(K, K, V)>

Returns a reference to the entry overlapping the specified range, if any.

Note that there could be multiple ranges in the map that overlap the given range but only one overlap will be returned by this function.

source

pub fn iter( &self ) -> impl Clone + DoubleEndedIterator<Item = (RangeInclusive<K>, &V)>

Provides an iterator to iterate through the whole map.

source

pub fn merge_adjacent<F>(&mut self, is_adjacent: F)
where F: Fn(RangeInclusive<K>, RangeInclusive<K>) -> bool, V: Eq,

Merge adjacent ranges that hold the same value using the provided closure to determine if a range is adjacent to another.

The closure accepts two arguments, with the first argument being smaller than the second.

§Examples

use range_map_vec::RangeMap;

let mut map: RangeMap<u64, u64> = RangeMap::new();
assert_eq!(map.insert(0..=2, 0), true);
assert_eq!(map.insert(3..=5, 0), true);
assert_eq!(map.insert(7..=10, 0), true);

map.merge_adjacent(|smaller, larger| {
    let next = *smaller.end() + 1;
    next == *larger.start()
});

assert_eq!(map.get_entry(&3).unwrap(), &(0, 5, 0));
assert_eq!(map.get_entry(&8).unwrap(), &(7, 10, 0));