Struct iset::IntervalMap

pub struct IntervalMap<T: PartialOrd + Copy, V, Ix: IndexType = DefaultIx> { /* fields omitted */ }

Map with interval keys (ranges x..y).

Range bounds should implement PartialOrd and Copy, for example any integer or float types. However, you cannot use values that cannot be used in comparison (such as NAN). There are no restrictions on values.

let mut map = iset::IntervalMap::new();
map.insert(20..30, "a");
map.insert(15..25, "b");
map.insert(10..20, "c");

let a: Vec<_> = map.iter(..).collect();
assert_eq!(a, &[(10..20, &"c"), (15..25, &"b"), (20..30, &"a")]);

// Iterate over intervals that overlap query (..20 here). Output is sorted.
let b: Vec<_> = map.intervals(..20).collect();
assert_eq!(b, &[10..20, 15..25]);

// Iterate over values that overlap query (20.. here). Output is sorted by intervals.
let c: Vec<_> = map.values(20..).collect();
assert_eq!(c, &[&"b", &"a"]);

Insertion takes O(log N) and search takes O(log N + K) where K is the size of the output.

You can use insert only intervals of type x..y but you can search using any query that implements RangeBounds, for example (x..y, x..=y, x.., ..=y and so on). Functions overlap, intervals_overlap and values_overlap allow to search for intervals/values that overlap a single point (same as x..=x).

Additionally, you can use mutable iterators iter_mut, values_mut as well as overlap_mut and values_overlap_mut.

You can get a value that corresponds to the smallest or largest interval in O(log N).

You can construct IntervalMap using collect():

let map: iset::IntervalMap<_, _> = vec![(10..20, "a"), (0..20, "b")]
                                       .into_iter().collect();

You can also construct IntervalMap using interval_map macro:

#[macro_use] extern crate iset;

let map = interval_map!{ 0..10 => "a", 5..15 => "b", -5..20 => "c" };
let a: Vec<_> = map.iter(..).collect();
assert_eq!(a, &[(-5..20, &"c"), (0..10, &"a"), (5..15, &"b")]);

Index types:

You can specify index type (for example u32 and u64) used in the inner representation of IntervalMap.

Method new, macro interval_map or function collect() create IntervalMap with index type u32. If you wish to use another index type you can use methods default or with_capacity. For example:

let mut map: iset::IntervalMap<_, _, u64> = iset::IntervalMap::default();
map.insert(10..20, "a");

See IndexType for details.

Implementations

impl<T: PartialOrd + Copy, V> IntervalMap<T, V>

pub fn new() -> Self

Creates an empty IntervalMap.

impl<T: PartialOrd + Copy, V, Ix: IndexType> IntervalMap<T, V, Ix>

pub fn with_capacity(capacity: usize) -> Self

Creates an empty IntervalMap with capacity.

pub fn shrink_to_fit(&mut self)

Shrinks inner contents.

pub fn insert(&mut self, interval: Range<T>, value: V)

Inserts an interval x..y and its value. Takes O(log N).

Panics if interval is empty (start >= end) or contains a value that cannot be compared (such as NAN).

pub fn iter<'a, R: RangeBounds<T>>(&'a self, query: R) -> Iter<'a, T, V, R, Ix>

Iterates over pairs (x..y, &value) that overlap the query. Takes O(log N + K) where K is the size of the output. Output is sorted by intervals, but not by values.

Panics if interval is empty or contains a value that cannot be compared (such as NAN).

pub fn intervals<'a, R: RangeBounds<T>>(
    &'a self,
    query: R
) -> Intervals<'a, T, V, R, Ix>

Iterates over intervals x..y that overlap the query. See iter for more details.

pub fn values<'a, R: RangeBounds<T>>(
    &'a self,
    query: R
) -> Values<'a, T, V, R, Ix>

Iterates over values that overlap the query. See iter for more details.

pub fn iter_mut<'a, R: RangeBounds<T>>(
    &'a mut self,
    query: R
) -> IterMut<'a, T, V, R, Ix>

Iterator over pairs (x..y, &mut value) that overlap the query. See iter for more details.

pub fn values_mut<'a, R: RangeBounds<T>>(
    &'a mut self,
    query: R
) -> ValuesMut<'a, T, V, R, Ix>

Iterator over mutable values that overlap the query. See iter for more details.

pub fn into_iter<R: RangeBounds<T>>(self, query: R) -> IntoIter<T, V, R, Ix>

Consumes IntervalMap and iterates over pairs (x..y, value) that overlap the query. See iter for more details.

pub fn overlap<'a>(&'a self, point: T) -> Iter<'a, T, V, RangeInclusive<T>, Ix>

Iterates over pairs (x..y, &value) that overlap the point. See iter for more details.

pub fn intervals_overlap<'a>(
    &'a self,
    point: T
) -> Intervals<'a, T, V, RangeInclusive<T>, Ix>

Iterates over intervals x..y that overlap the point. See iter for more details.

pub fn values_overlap<'a>(
    &'a self,
    point: T
) -> Values<'a, T, V, RangeInclusive<T>, Ix>

Iterates over values that overlap the point. See iter for more details.

pub fn overlap_mut<'a>(
    &'a mut self,
    point: T
) -> IterMut<'a, T, V, RangeInclusive<T>, Ix>

Iterator over pairs (x..y, &mut value) that overlap the point. See iter for more details.

pub fn values_overlap_mut<'a>(
    &'a mut self,
    point: T
) -> ValuesMut<'a, T, V, RangeInclusive<T>, Ix>

Iterates over mutable values that overlap the point. See iter for more details.

pub fn smallest(&self) -> Option<(Range<T>, &V)>

Returns the pair (x..y, &value) with the smallest x..y (intervals are sorted lexicographically). Takes O(log N). Returns None if the map is empty.

pub fn smallest_mut(&mut self) -> Option<(Range<T>, &mut V)>

Returns the pair (x..y, &mut value) with the smallest x..y (intervals are sorted lexicographically). Takes O(log N). Returns None if the map is empty.

pub fn largest(&self) -> Option<(Range<T>, &V)>

Returns the pair (x..y, &value) with the largest x..y (intervals are sorted lexicographically). Takes O(log N). Returns None if the map is empty.

pub fn largest_mut(&mut self) -> Option<(Range<T>, &mut V)>

Returns the pair (x..y, &mut value) with the largest x..y (intervals are sorted lexicographically). Takes O(log N). Returns None if the map is empty.

impl<T: PartialOrd + Copy + Display, V: Display, Ix: IndexType> IntervalMap<T, V, Ix>

pub fn write_dot<W: Write>(&self, writer: W) -> Result<()>

Write dot file to writer. T and V should implement Display.

impl<T: PartialOrd + Copy + Display, V, Ix: IndexType> IntervalMap<T, V, Ix>

pub fn write_dot_without_values<W: Write>(&self, writer: W) -> Result<()>

Write dot file to writer without values. T should implement Display.

Trait Implementations

impl<T: Clone + PartialOrd + Copy, V: Clone, Ix: Clone + IndexType> Clone for IntervalMap<T, V, Ix>

fn clone(&self) -> IntervalMap<T, V, Ix>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: PartialOrd + Copy + Debug, V: Debug, Ix: IndexType> Debug for IntervalMap<T, V, Ix>

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

Formats the value using the given formatter.

impl<T: PartialOrd + Copy, V, Ix: IndexType> Default for IntervalMap<T, V, Ix>

fn default() -> Self

Returns the “default value” for a type.

impl<T: PartialOrd + Copy, V> FromIterator<(Range<T>, V)> for IntervalMap<T, V>

Construct IntervalMap from pairs (x..y, value).

fn from_iter<I: IntoIterator<Item = (Range<T>, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<T: PartialOrd + Copy, V, Ix: IndexType> IntoIterator for IntervalMap<T, V, Ix>

type IntoIter = IntoIter<T, V, RangeFull, Ix>

Which kind of iterator are we turning this into?

type Item = (Range<T>, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.