Struct SegmentMap

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

SegmentMap

A map of non-overlapping ranges to values. Inserted ranges will be merged with adjacent ranges if they have the same value.

Internally, SegmentMap is represented by a BTreeMap in which the keys are represented by a concrete [Range] type, sorted by their start values.

Examples

TODO

Entry API

TODO

Implementations

impl<K, V> SegmentMap<K, V>

pub fn len(&self) -> usize

Returns the number of ranges in the map.

Examples

Basic usage:

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map contains no ranges.

Examples

Basic usage:

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

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

Converts the map into a Vec by chaining [into_iter] and [collect]

pub fn iter(&self) -> Iter<'_, K, V>

Gets an iterator over the sorted ranges in the map.

Examples

Basic usage:

let mut map = SegmentMap::new();
map.insert(0..1, "a");
map.insert(1..2, "b");
map.insert(2..3, "c");

let (first_range, first_value) = map.iter().next().unwrap();
assert_eq!((*first_range, *first_value), (Segment::from(0..1), "a"));

pub fn iter_in<R>(&self, range: R) -> IterIn<'_, K, V>

where R: RangeBounds<K>, K: Clone + Ord,

Gets an iterator over a subset of the sorted ranges in the map, bounded by range.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Gets an iterator over the sorted ranges in the map, with mutable values

Ranges are used as keys and therefore cannot be mutable. To manipulate the bounds of stored ranges, they must be removed and re-inserted to ensure bound integrity.

Examples

Basic usage:

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);

// add 10 to the value if the key isn't "a"
for (key, value) in map.iter_mut() {
    if key != &"a" {
        *value += 10;
    }
}

pub fn ranges(&self) -> Ranges<'_, K, V>

Gets an iterator over the range keys of the map (similar to BTreeMap::keys())

Examples

Basic usage:

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(2, "b");
a.insert(1, "a");

let keys: Vec<_> = a.keys().cloned().collect();
assert_eq!(keys, [1, 2]);

pub fn values(&self) -> Values<'_, K, V>

Gets an iterator over the values of the map, in order by their range.

Examples

Basic usage:

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "hello");
a.insert(2, "goodbye");

let values: Vec<&str> = a.values().cloned().collect();
assert_eq!(values, ["hello", "goodbye"]);

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

Gets a mutable iterator over the values of the map, in order by their range.

Examples

Basic usage:

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, String::from("hello"));
a.insert(2, String::from("goodbye"));

for value in a.values_mut() {
    value.push_str("!");
}

let values: Vec<String> = a.values().cloned().collect();
assert_eq!(values, [String::from("hello!"),
                    String::from("goodbye!")]);

pub fn iter_subset<R>(&self, range: R) -> IterSubset<'_, K, V>

where R: RangeBounds<K>, K: Clone + Ord,

pub fn subset<R>(&self, range: R) -> SegmentMap<K, &V>

where R: RangeBounds<K>, K: Clone + Ord,

Create a SegmentMap referencing a subset range in self

pub fn iter_complement(&self) -> IterComplement<'_, K, V>

pub fn complement(&self) -> SegmentSet<&K>

where K: Ord,

pub fn iter_gaps(&self) -> Gaps<'_, K, V>

Gets an iterator over all maximally-sized gaps between ranges in the map

NOTE: Empty regions before and after those stored in this map (i.e. before the first range and after the last range) will not be included in this iterator

pub fn gaps(&self) -> SegmentSet<&K>

where K: Ord,

impl<K, V> SegmentMap<K, V>

pub fn new() -> SegmentMap<K, V>

where K: Ord,

Makes a new, empty SegmentMap.

Does not allocate anything on its own.

Examples

Basic usage:

let mut map = SegmentMap::new();

// entries can now be inserted into the empty map
map.insert(0..1, "a");

pub fn with_value(value: V) -> SegmentMap<K, V>

where K: Ord,

Makes a new, empty SegmentMap with a value for the full range.

Examples

Basic usage:

let mut map = SegmentMap::with_value(true);

// All values will return something
assert_eq!(map[&0], true);
assert_eq!(map[&10], true);
assert_eq!(map[&12345678], true);

pub fn clear(&mut self)

Clears the map, removing all elements.

This also resets the capacity of the internal store.

Examples

Basic usage:

let mut a = SegmentMap::new();
a.insert(0..1, "a");
a.clear();
assert!(a.is_empty());

pub fn shrink_to_fit(&mut self)

Resets the capacity of store

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

where K: Clone + Ord,

Returns a reference to the value corresponding to the given point, if the point is covered by any range in the map.

Examples

Basic usage:

let mut map = SegmentMap::new();
map.insert(0..1, "a");
assert_eq!(map.get(&0), Some(&"a"));
assert_eq!(map.get(&2), None);

pub fn get_range_value(&self, at: &K) -> Option<(&Segment<K>, &V)>

where K: Clone + Ord,

Returns the range-value pair (as a pair of references) corresponding to the given point, if the point is covered by any range in the map.

Examples

let mut map = SegmentMap::new();
map.insert(0..1, "a");
assert_eq!(map.get_range_value(&0), Some((&Segment::from(0..1), &"a")));
assert_eq!(map.get_range_value(&2), None);

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

where K: Clone + Ord,

Returns true if any range in the map covers the specified point.

Examples

Basic usage:

let mut map = SegmentMap::new();
map.insert(0..1, "a");
assert_eq!(map.contains(&0), true);
assert_eq!(map.contains(&2), false);

pub fn bounds(&self) -> Option<Segment<&K>>

Get the widest bounds covered by the ranges in this map

NOTE: This is not necessarily (or likely) a contiguous range!

Examples

let mut map = SegmentMap::new();
map.insert(0..9, "a");
map.insert(15..30, "b");
map.insert(35..90, "c");

assert_eq!(map.bounds(), Some(Segment::from(0..90).as_ref()));

pub fn lower_bound(&self) -> Option<&Bound<K>>

Get the lowest bound covered by the ranges in this map

Examples

let mut map = SegmentMap::new();
map.insert(0..9, "a");
map.insert(15..30, "b");
map.insert(35..90, "c");

assert_eq!(map.lower_bound(), Some(&Bound::Included(0)));

pub fn upper_bound(&self) -> Option<&Bound<K>>

Get the highest bound covered by the ranges in this map

Examples

let mut map = SegmentMap::new();
map.insert(0..9, "a");
map.insert(15..30, "b");
map.insert(35..90, "c");

assert_eq!(map.upper_bound(), Some(&Bound::Excluded(90)));

pub fn retain<F>(&mut self, f: F)

where K: Ord, F: FnMut(&Segment<K>, &mut V) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all pairs (k, v) such that f(&k, &mut v) returns false.

Examples

let mut map = SegmentMap::new();
map.set(0..5, true);
map.set(5..10, false);
map.set(10..15, true);
map.set(15..20, false);
map.set(20..25, true);

// Keep only the ranges with even numbered starts
map.retain(|k, _| k.start_value().unwrap() % 2 == 0);

assert!(map[&0] == true);
assert!(map[&10] == true);
assert!(map[&12] == true);
assert!(map[&20] == true);
assert!(map[&24] == true);

assert!(map.get(&15).is_none());

pub fn insert<R>(&mut self, range: R, value: V) -> Option<SegmentMap<K, V>>

where R: RangeBounds<K>, K: Clone + Ord, V: Clone + Eq,

Insert a value for the specified range

If the inserted range completely overlaps any existing range in the map, the existing range (or ranges) will be replaced by the inserted range.

If the inserted range partially overlaps any existing range in the map, the existing ranges will be truncated to non-overlapping regions.

If the inserted range overlaps or is touching an existing range that maps to the same value, the ranges will be merged into one contiguous range

Returns

Much like other maps (BTreeMap::insert or [HashMap::insert]), insert returns the overwritten values (if any existed). Because multiple ranges might be overwritten, another map will be constructed with those values.

Note: This will allocate a new underlying SegmentMap, though, so an option is used in case no ranges were overwritten. If you don’t care about the overwritten values, use [SegmentMap::set_range] instead.

Examples

Basic Usage

let mut map = SegmentMap::new();
map.insert(0..4, "a");
assert_eq!(map.is_empty(), false);

map.insert(2..6, "b");
assert_eq!(map[&1], "a");
assert_eq!(map[&3], "b");

Overwriting

let mut map = SegmentMap::new();
map.insert(0..10, "a");
let out = map.insert(3..6, "b").unwrap();

assert_eq!(map[&2], "a");
assert_eq!(map[&4], "b");
assert_eq!(map[&7], "a");
assert!(out.into_iter().eq(vec![(Segment::from(3..6), "a")]));

Coalescing

let mut map = SegmentMap::new();
map.insert(0..10, "a");
map.insert(10..20, "a");

assert!(map.into_iter().eq(vec![(Segment::from(0..20), "a")]));

See Also

• SegmentMap::set if you don’t want to return the values overwritten
• SegmentMap::insert_if_empty if you only want to insert the value if no overlaps occur
• SegmentMap::insert_in_gaps if you only want to insert the value for the empty parts of the range, not overwriting any values.

pub fn set<R>(&mut self, range: R, value: V)

where R: RangeBounds<K>, K: Clone + Ord, V: Clone + Eq,

Set a value for the specified range, overwriting any existing subset ranges. This is the same as SegmentMap::insert, but without a return value, so overlapping ranges will be truncated and adjacent ranges with the same value will be merged.

Examples

Basic Usage

let mut map = SegmentMap::new();
map.set(0..4, "a");
assert_eq!(map.is_empty(), false);

map.set(2..6, "b");
assert_eq!(map[&1], "a");
assert_eq!(map[&3], "b");

Overwriting

let mut map = SegmentMap::new();
map.set(0..10, "a");
map.set(3..6, "b");

assert_eq!(map[&2], "a");
assert_eq!(map[&4], "b");
assert_eq!(map[&7], "a");

Coalescing

let mut map = SegmentMap::new();
map.set(0..10, "a");
map.set(10..20, "a");

assert!(map.into_iter().eq(vec![(Segment::from(0..20), "a")]))

See Also

• SegmentMap::insert if you want the value overwritten
• SegmentMap::insert_if_empty if you only want to insert the value if no overlaps occur
• SegmentMap::insert_in_gaps if you only want to insert the value for the empty parts of the range, not overwriting any values.

pub fn insert_if_empty<R>(&mut self, range: R, value: V) -> Option<V>

where R: RangeBounds<K>, K: Clone + Ord, V: Clone + Eq,

Insert a value into the map, only if there are no existing overlapping ranges. Returns the given value if it wasn’t inserted.

Examples

let mut map = SegmentMap::new();
assert!(map.insert_if_empty(0..5, true).is_none());
assert!(map.insert_if_empty(5..10, true).is_none());
assert!(map.insert_if_empty(3..6, true).is_some());

See Also

• SegmentMap::insert or SegmentMap::set if you want to overwrite existing values
• SegmentMap::insert_in_gaps if you only want to insert the value for the empty parts of the range

pub fn insert_in_gaps<R>(&mut self, range: R, value: V)

where R: RangeBounds<K>, K: Clone + Ord, V: Clone + Eq,

Insert a value for empty regions (gaps) in the specified range. If values exist for ranges overlapping this range, those values will be preserved. As such, this method may add multiple ranges for the given value.

Examples

let mut map = SegmentMap::new();
map.set(5..10, "a");
map.set(15..20, "a");
map.insert_in_gaps(0..30, "b");

assert!(map.into_iter().eq(vec![
    (Segment::from(0..5), "b"),
    (Segment::from(5..10), "a"),
    (Segment::from(10..15), "b"),
    (Segment::from(15..20), "a"),
    (Segment::from(20..30), "b"),
]));

See Also

• SegmentMap::insert or SegmentMap::set if you want to overwrite existing values
• SegmentMap::insert_if_empty if you only want to insert the value if no overlaps occur
• SegmentMap::with_value if you’d instead like to construct your map with a default value for all possible ranges

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

where R: RangeBounds<K>, K: Clone + Ord, V: Clone,

Remove all values in a given range, returning the removed values. Overlapping ranges will be truncated at the bounds of this range.

Note: This will allocate another SegmentMap for returning the removed ranges, so if you don’t care about them, use SegmentMap::clear_range instead

Examples

let mut map = SegmentMap::new();
map.insert(0..=10, 5);
let removed = map.remove(2..4).unwrap();

assert_eq!(map[&0], 5);
assert!(map.get(&2).is_none());
assert!(map.get(&3).is_none());
assert_eq!(map[&4], 5);
assert_eq!(map[&10], 5);

assert_eq!(removed[&2], 5);
assert_eq!(removed[&3], 5);

See Also

• SegmentMap::clear_range if you don’t care about the removed values

pub fn clear_range<R>(&mut self, range: R)

where R: RangeBounds<K>, K: Clone + Ord, V: Clone,

Remove all values in a given range. Overlapping ranges will be truncated at the bounds of this range.

Examples

let mut map = SegmentMap::new();
map.insert(0..=10, 5);
map.clear_range(2..4);

assert_eq!(map[&0], 5);
assert!(map.get(&2).is_none());
assert!(map.get(&3).is_none());
assert_eq!(map[&4], 5);
assert_eq!(map[&10], 5);

See Also

• SegmentMap::remove if you want the removed values

pub fn append(&mut self, other: &mut SegmentMap<K, V>)

where K: Clone + Ord, V: Clone + Eq,

Moves all elements from other into Self, leaving other empty.

Note thate V must be Clone in case any ranges need to be split

Examples

let mut a = SegmentMap::new();
a.insert(0..1, "a");
a.insert(1..2, "b");
a.insert(2..3, "c");

let mut b = SegmentMap::new();
b.insert(2..3, "d");
b.insert(3..4, "e");
b.insert(4..5, "f");

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert_eq!(a[&0], "a");
assert_eq!(a[&1], "b");
assert_eq!(a[&2], "d");
assert_eq!(a[&3], "e");
assert_eq!(a[&4], "f");

pub fn split_off(&mut self, at: Bound<K>) -> SegmentMap<K, V>

where K: Clone + Ord, V: Clone,

Split the map into two at the given bound. Returns everything including and after that bound.

Examples

Basic Usage

let mut a = SegmentMap::new();
a.insert(0..1, "a");
a.insert(1..2, "b");
a.insert(2..3, "c");
a.insert(3..4, "d");

let b = a.split_off(Bound::Included(2));

assert!(a.into_iter().eq(vec![
    (Segment::from(0..1), "a"),
    (Segment::from(1..2), "b"),
]));
assert!(b.into_iter().eq(vec![
    (Segment::from(2..3), "c"),
    (Segment::from(3..4), "d"),
]));

Mixed Bounds

let mut a = SegmentMap::new();
a.insert(0..1, "a");
a.insert(1..2, "b");
a.insert(2..3, "c");
a.insert(3..4, "d");
a.insert(4..5, "e");
a.insert(5..6, "f");
a.insert(6..7, "g");

let c = a.split_off(Bound::Excluded(4));
let b = a.split_off(Bound::Included(2));

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);
assert_eq!(c.len(), 3);

assert_eq!(a[&0], "a");
assert_eq!(a[&1], "b");
assert!(a.get(&2).is_none());

assert!(b.get(&1).is_none());
assert_eq!(b[&2], "c");
assert_eq!(b[&3], "d");
assert_eq!(b[&4], "e");
assert!(b.get(&5).is_none());

// `c` also has a a range (4, 5), which is inaccessible with integers.
// if we were using floats, `c[4.5]` would be `"e"`.
assert!(c.get(&4).is_none());
assert_eq!(c[&5], "f");
assert_eq!(c[&6], "g");
assert!(c.get(&7).is_none());

Trait Implementations

impl<K, V> Clone for SegmentMap<K, V>

where K: Clone, V: Clone,

fn clone(&self) -> SegmentMap<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K, V> Debug for SegmentMap<K, V>

where K: Debug + Ord + Clone, V: Debug + Eq + Clone,

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

Formats the value using the given formatter.

impl<K, V> Default for SegmentMap<K, V>

where K: Ord,

fn default() -> SegmentMap<K, V>

Returns the “default value” for a type.

impl<R, K, V> Extend<(R, V)> for SegmentMap<K, V>

where R: RangeBounds<K>, K: Clone + Ord, V: Clone + Eq,

fn extend<T>(&mut self, iter: T)

where T: IntoIterator<Item = (R, V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<R, K, V> FromIterator<(R, V)> for SegmentMap<K, V>

where R: RangeBounds<K>, K: Clone + Ord, V: Clone + Eq,

fn from_iter<T>(iter: T) -> SegmentMap<K, V>

where T: IntoIterator<Item = (R, V)>,

Creates a value from an iterator.

impl<K, V> Hash for SegmentMap<K, V>

where K: Hash, V: Hash,

fn hash<H>(&self, state: &mut H)

where H: Hasher,

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<K, V> Index<&K> for SegmentMap<K, V>

where K: Clone + Ord, V: Eq + Clone,

fn index(&self, key: &K) -> &V

Returns a reference to the value corresponding to the supplied key.

Panics

Panics if the key is not present in the SegmentMap.

type Output = V

The returned type after indexing.

impl<'a, K, V> IntoIterator for &'a SegmentMap<K, V>

type Item = (&'a Segment<K>, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, K, V>

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut SegmentMap<K, V>

type Item = (&'a Segment<K>, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, K, V>

Creates an iterator from a value.

impl<K, V> IntoIterator for SegmentMap<K, V>

type Item = (Segment<K>, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <SegmentMap<K, V> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<K, V> Ord for SegmentMap<K, V>

where K: Ord, V: Ord,

fn cmp(&self, other: &SegmentMap<K, V>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<K, V> PartialEq for SegmentMap<K, V>

where K: PartialEq, V: PartialEq,

fn eq(&self, other: &SegmentMap<K, V>) -> 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<K, V> PartialOrd for SegmentMap<K, V>

where K: PartialOrd + Ord, V: PartialOrd,

fn partial_cmp(&self, other: &SegmentMap<K, V>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<V: Clone + Eq> TextMap<V> for SegmentMap<usize, V>

fn merge_only_longest<I: IntoIterator<Item = (Segment<usize>, V)>>( &mut self, other: I, )

impl<K, V> Eq for SegmentMap<K, V>

where K: Eq, V: Eq,