Struct iset::set::IntervalSet

pub struct IntervalSet<T, Ix: IndexType = DefaultIx> { /* private fields */ }

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

use iset::interval_set;
let mut set = interval_set!{ 0.4..1.5, 0.1..0.5, 5.0..7.0 };
assert!(set.insert(-1.0..0.2));
// false because the interval is already in the set.
assert!(!set.insert(0.1..0.5));

assert!(set.contains(5.0..7.0));
assert!(set.remove(5.0..7.0));

// 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::f64::NAN);
// set.overlap(core::f64::NAN);

// It is still possible to use infinity.
const INF: f64 = core::f64::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}
assert_eq!(set.range().unwrap(), -1.0..INF);
assert_eq!(set.smallest().unwrap(), -1.0..0.2);
assert_eq!(set.largest().unwrap(), 0.4..1.5);

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

In contrast to the IntervalMap, IntervalSet does not have a force_insert, and completely forbids duplicate intervals.

Implementations

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

pub fn new() -> Self

Creates an empty IntervalSet with default index type DefaultIx.

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

pub fn with_capacity(capacity: usize) -> Self

Creates an empty IntervalSet with capacity.

pub fn from_sorted<I>(iter: I) -> Selfwhere I: Iterator<Item = Range<T>>,

Creates an interval set from a sorted iterator over intervals. Takes O(N).

Panics if the intervals are not sorted or if there are equal intervals.

pub fn len(&self) -> usize

Returns the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub fn clear(&mut self)

Clears the set, removing all values. This method has no effect on the allocated capacity.

pub fn shrink_to_fit(&mut self)

Shrinks inner contents.

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

Inserts an interval x..y to the set. If the set did not have this interval present, true is returned. Takes O(log N).

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

pub fn contains(&self, interval: Range<T>) -> bool

Check if the interval set contains interval (exact match). Takes O(log N).

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

pub fn remove(&mut self, interval: Range<T>) -> bool

Removes the interval from the set. Returns true if the interval was present in the set. Takes O(log N).

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

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

Returns a range of interval keys in the set, takes O(1). Returns None if the set is empty. out.start is the minimal start of all intervals in the set, and out.end is the maximal end of all intervals in the set.

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

Returns the smallest interval in the set (in lexicographical order). Takes O(log N). Returns None if the set is empty.

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

Removes and returns the smallest interval in the set (in lexicographical order). 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 (in lexicographical order). Takes O(log N). Returns None if the set is empty.

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

Removes and returns the largest interval in the set (in lexicographical order). Takes O(log N). Returns None if the set is empty.

pub fn has_overlap<R>(&self, query: R) -> boolwhere R: RangeBounds<T>,

Checks, if the query overlaps any intervals in the interval set. Equivalent to set.iter(query).next().is_some(), but much faster.

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

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 into_iter<R>(self, query: R) -> IntoIntervals<T, (), R, Ix> where R: RangeBounds<T>,

Consumes IntervalSet and iterates over intervals x..y that overlap the query. See iter for more details.

pub fn unsorted_iter<'a>(&'a self) -> UnsIntervals<'a, T, (), Ix>

Creates an unsorted iterator over all intervals x..y. Slightly faster than the sorted iterator, although both take O(N).

pub fn unsorted_into_iter(self) -> UnsIntoIntervals<T, (), Ix>

Consumes IntervalSet and creates an unsorted iterator over all intervals x..y.

impl<T, Ix> IntervalSet<T, Ix>where T: PartialOrd + Copy + Default + AddAssign + Sub<Output = T>, Ix: IndexType,

pub fn covered_len<R>(&self, query: R) -> Twhere R: RangeBounds<T>,

Calculates the total length of the query that is covered by intervals in the map. Takes O(log N + K) where K is the number of intervals that overlap query.

See IntervalMap::covered_len for more details.

Trait Implementations

impl<T: Clone, 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 = IntoIntervals<T, (), RangeFull, 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.