Struct iset::IntervalSet

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

Set with interval keys (ranges x..y). Newtype over IntervalMap<T, ()>.

See IntervalMap for more information.

let mut set = iset::IntervalSet::new();
set.insert(0.4..1.5);
set.insert(0.1..0.5);
set.insert(-1.0..0.2);

// Iterate over intervals that overlap `0.2..0.8`.
let a: Vec<_> = set.iter(0.2..0.8).collect();
assert_eq!(a, &[0.1..0.5, 0.4..1.5]);

// Iterate over intervals that overlap a point 0.5.
let b: Vec<_> = set.overlap(0.5).collect();
assert_eq!(b, &[0.4..1.5]);

// Will panic:
// set.insert(0.0..core::f32::NAN);
// set.overlap(core::f32::NAN);

// It is still possible to use infinity.
let inf = core::f32::INFINITY;
set.insert(0.0..inf);
let c: Vec<_> = set.overlap(0.5).collect();
assert_eq!(c, &[0.0..inf, 0.4..1.5]);

println!("{:?}", set);
// {-1.0..0.2, 0.0..inf, 0.1..0.5, 0.4..1.5}

There are no mutable iterators over IntervalSet as keys should be immutable.

You can get smallest and largest intervals in O(log N).

You can construct IntervalSet using collect():

let set: iset::IntervalSet<_> = vec![10..20, 0..20].into_iter().collect();

You can also construct IntervalSet using interval_set macro:

#[macro_use] extern crate iset;

let set = interval_set!{ 100..210, 50..150 };
let a: Vec<_> = set.iter(..).collect();
assert_eq!(a, &[50..150, 100..210]);

Index types:

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

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

let mut set: iset::IntervalSet<_, u64> = iset::IntervalSet::default();
set.insert(10..20);

See IndexType for details.

Implementations

impl<T: PartialOrd + Copy> IntervalSet<T>

pub fn new() -> Self

Creates an empty IntervalSet.

impl<T: PartialOrd + Copy, Ix: IndexType> IntervalSet<T, Ix>

pub fn with_capacity(capacity: usize) -> Self

Creates an empty IntervalSet with capacity.

pub fn shrink_to_fit(&mut self)

Shrinks inner contents.

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

Inserts an interval x..y. 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
) -> Intervals<'a, T, (), R, Ix>

Iterates over intervals x..y that overlap the query. Takes O(log N + K) where K is the size of the output. Output is sorted by intervals.

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

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

Iterates over intervals x..y that overlap the point. Same as iter(point..=point). See iter for more details.

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

Returns the smallest interval in the set (intervals are sorted lexicographically). Takes O(log N). Returns None if the set is empty.

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

Returns the largest interval in the set (intervals are sorted lexicographically). Takes O(log N). Returns None if the set is empty.

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

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

Write dot file to writer. T should implement Display.

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<T: PartialOrd + Copy> FromIterator<Range<T>> for IntervalSet<T>

Construct IntervalSet from ranges x..y.

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

Creates a value from an iterator.

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

type IntoIter = IntoIterSet<T, Ix>

Which kind of iterator are we turning this into?

type Item = Range<T>

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.