Struct RangeList 

pub struct RangeList<E>
where
    E: PartialOrd,
{ /* private fields */ }

A sorted collection of inclusive ranges that can be used to represent non-continuous sets of values.

Warning

Although RangeList can be constructed for elements that do not implement std::cmp::Ord, but do implement std::cmp::PartialOrd, constructor methods, such as the FromIterator implementation, will panic if the used boundary values cannot be sorted. This requirement allows the usage of types like f64, as long as the user can guarantee that values that cannot be ordered, like NaN, will not appear.

Implementations

impl<E> RangeList<E>

where E: PartialOrd,

pub fn first_position_bound(&self, bound: &Bound<E>) -> Option<usize>

where E: Clone + DiscreteElement,

Returns the Self::position pointing at the smallest element greater than (or equal to) the given bound.

Passing Bound::Included(x) will return the position of the smallest element greater than or equal to x, or None if all elements are smaller than x.

Passing Bound::Excluded(x) will return the position of the smallest element greater than x, or None if all elements are smaller than or equal to x.

Passing Bound::Unbounded will return None.

Examples

let rl = RangeList::from_iter([1..=4, 6..=8]);
assert_eq!(rl.first_position_bound(&Bound::Included(-1)), Some(0));
assert_eq!(rl.first_position_bound(&Bound::Included(1)), Some(0));
assert_eq!(rl.first_position_bound(&Bound::Excluded(1)), Some(1));
assert_eq!(rl.first_position_bound(&Bound::Included(4)), Some(3));
assert_eq!(rl.first_position_bound(&Bound::Excluded(4)), Some(4));
assert_eq!(rl.first_position_bound(&Bound::Included(8)), Some(6));

assert_eq!(rl.first_position_bound(&Bound::Included(9)), None);

pub fn from_sorted_elements<T>(iter: T) -> RangeList<E>

where T: IntoIterator<Item = E>, E: DiscreteElement + Clone,

Construct a RangeList from an iterator of elements that are known to be yielded in sorted (increasing) order, but where duplicates might still exist.

Warning

This function will panic if the iterator yields a larger element than one yielded previously.

pub fn from_sorted_ranges<T>(iter: T) -> RangeList<E>

where T: IntoIterator<Item = RangeInclusive<E>>, E: Any + Clone,

Construct a RangeList from an iterator of inclusive ranges that are known to be yielded in sorted (increasing) order, but where ranges might still need to be merged.

Warning

This function will panic if the iterator yields a strictly larger range than the previous one.

pub fn is_empty(&self) -> bool

Returns true if the range list contains no items.

Examples

assert!(!RangeList::from_iter([3..=4]).is_empty());
assert!(RangeList::<i64>::default().is_empty());
assert!(RangeList::from_iter([3..=2]).is_empty());

pub fn iter<'a>( &'a self, ) -> Map<<&'a RangeList<E> as IntoIterator>::IntoIter, fn(RangeInclusive<&'a E>) -> RangeInclusive<E>>

where E: Copy,

Returns an Copying iterator for the ranges in the set.

pub fn last_position_bound(&self, bound: &Bound<E>) -> Option<usize>

where E: Clone + DiscreteElement,

Returns the Self::position pointing at the largest element smaller than (or equal to) the given bound.

Passing Bound::Included(x) will return the position of the largest element smaller than or equal to x, or None if all elements are larger x.

Passing Bound::Excluded(x) will return the position of the largest element smaller than x, or None if all elements are larger than or equal to x.

Passing Bound::Unbounded will return None.

Examples

let rl = RangeList::from_iter([1..=4, 6..=8]);
assert_eq!(rl.last_position_bound(&Bound::Included(1)), Some(0));
assert_eq!(rl.last_position_bound(&Bound::Included(4)), Some(3));
assert_eq!(rl.last_position_bound(&Bound::Excluded(4)), Some(2));
assert_eq!(rl.last_position_bound(&Bound::Included(9)), Some(7));
assert_eq!(rl.last_position_bound(&Bound::Excluded(9)), Some(7));

assert_eq!(rl.last_position_bound(&Bound::Included(-1)), None);
assert_eq!(rl.last_position_bound(&Bound::Excluded(1)), None);

pub fn lower_bound(&self) -> Option<&E>

Returns the lower bound of the range list, or None if the range list is empty.

Examples

assert_eq!(RangeList::from_iter([1..=4]).lower_bound(), Some(&1));
assert_eq!(RangeList::from_iter([1..=4, 6..=7, -5..=-3]).lower_bound(), Some(&-5));

assert_eq!(RangeList::<i64>::default().lower_bound(), None);

pub fn position(&self, elem: &E) -> Option<usize>

where E: DiscreteElement,

Returns how many elements precede the given element in the RangeList, or None if the element does not occur in the RangeList.

Examples

let rl = RangeList::from_iter([1..=4, 6..=8]);
assert_eq!(rl.position(&1), Some(0));
assert_eq!(rl.position(&4), Some(3));
assert_eq!(rl.position(&6), Some(4));
assert_eq!(rl.position(&7), Some(5));
assert_eq!(rl.position(&-4), None);

pub fn set_lower_bound(&mut self, lower_bound: E)

where E: Debug,

Tightens the lower bound of the range list, removing any (partial) ranges that are below the new lower bound.

Note that no action is taken if the new lower bound is less than or equal to the current lower bound.

Examples

let mut r = RangeList::from_iter([-5..=-3, 1..=4, 6..=7]);
r.set_lower_bound(2);
assert_eq!(r.lower_bound(), Some(&2));
assert_eq!(r.iter().collect::<Vec<_>>(), vec![2..=4, 6..=7]);

pub fn set_upper_bound(&mut self, upper_bound: E)

Tightens the upper bound of the range list, removing any (partial) ranges that are above the new upper bound.

Note that no action is taken if the new upper bound is greater than or equal to the current upper bound.

Examples

let mut r = RangeList::from_iter([-5..=-3, 1..=4, 6..=7]);
r.set_upper_bound(3);
assert_eq!(r.upper_bound(), Some(&3));
assert_eq!(r.iter().collect::<Vec<_>>(), vec![-5..=-3, 1..=3]);

pub fn upper_bound(&self) -> Option<&E>

Returns the upper bound of the range list, or None if the range list is empty

Examples

assert_eq!(RangeList::from_iter([1..=4]).upper_bound(), Some(&4));
assert_eq!(RangeList::from_iter([1..=4, 6..=7, -5..=-3]).upper_bound(), Some(&7));

assert_eq!(RangeList::<i64>::default().upper_bound(), None);

Trait Implementations

impl<E> Clone for RangeList<E>

where E: Clone + PartialOrd,

fn clone(&self) -> RangeList<E>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<E> Debug for RangeList<E>

where E: Debug + PartialOrd,

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

Formats the value using the given formatter.

impl<E> Default for RangeList<E>

where E: PartialOrd,

fn default() -> RangeList<E>

Returns the “default value” for a type.

impl<E> Display for RangeList<E>

where E: Debug + PartialOrd,

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

Formats the value using the given formatter.

impl<E> From<&RangeInclusive<E>> for RangeList<E>

where E: Clone + PartialOrd,

fn from(value: &RangeInclusive<E>) -> RangeList<E>

Converts to this type from the input type.

impl<E> From<RangeInclusive<E>> for RangeList<E>

where E: Clone + PartialOrd,

fn from(value: RangeInclusive<E>) -> RangeList<E>

Converts to this type from the input type.

impl<E, R> FromIterator<R> for RangeList<E>

where E: Any + Clone + PartialOrd, R: Into<RangeInclusive<E>>,

fn from_iter<T>(iter: T) -> RangeList<E>

where T: IntoIterator<Item = R>,

Creates a value from an iterator.

impl<E> Hash for RangeList<E>

where E: Hash + PartialOrd,

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<E> IntervalIterator<E> for RangeList<E>

where E: PartialOrd + Clone,

type IntervalIter = <RangeList<E> as IntoIterator>::IntoIter

The type of the interval iterator.

fn intervals(&self) -> <RangeList<E> as IntervalIterator<E>>::IntervalIter

Returns an iterator over the ordered intervals.

fn card(&self) -> Option<usize>

where E: DiscreteElement,

Returns the number of elements contained within the RangeList.

fn contains(&self, elem: &E) -> bool

Returns true if elem is contained in the range list.

fn diff<O, R>(&self, other: &O) -> R

where E: Clone + DiscreteElement, O: IntervalIterator<E>, R: FromIterator<RangeInclusive<E>>,

Compute RangeList without any of the elements in the ranges of other.

fn disjoint<O>(&self, other: &O) -> bool

where O: IntervalIterator<E> + ?Sized,

Returns whether self and other are disjoint sets

fn intersect<O, R>(&self, other: &O) -> R

where E: Clone, O: IntervalIterator<E>, R: FromIterator<RangeInclusive<E>>,

Return the set intersection of two interval iterators.

fn subset<O>(&self, other: &O) -> bool

where O: IntervalIterator<E> + ?Sized,

Returns whether self is a subset of other

fn superset<O>(&self, other: &O) -> bool

where O: IntervalIterator<E> + ?Sized,

Returns whether self is a superset of other

fn union<O, R>(&self, other: &O) -> R

where E: Clone, O: IntervalIterator<E>, R: FromIterator<RangeInclusive<E>>,

Return the set union of two interval iterators.

impl<'a, E> IntoIterator for &'a RangeList<E>

where E: PartialOrd,

type IntoIter = Map<Iter<'a, (E, E)>, fn(&'a (E, E)) -> RangeInclusive<&'a E>>

Which kind of iterator are we turning this into?

type Item = RangeInclusive<&'a E>

The type of the elements being iterated over.

fn into_iter(self) -> <&'a RangeList<E> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<E> IntoIterator for RangeList<E>

where E: PartialOrd + Clone,

type IntoIter = Map<IntoIter<(E, E)>, fn((E, E)) -> RangeInclusive<E>>

Which kind of iterator are we turning this into?

type Item = RangeInclusive<E>

The type of the elements being iterated over.

fn into_iter(self) -> <RangeList<E> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<E> PartialEq for RangeList<E>

where E: PartialEq + PartialOrd,

fn eq(&self, other: &RangeList<E>) -> 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<E> PartialOrd for RangeList<E>

where E: PartialOrd,

fn partial_cmp(&self, other: &RangeList<E>) -> 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<E> Eq for RangeList<E>

where E: Eq + PartialOrd,

impl<E> StructuralPartialEq for RangeList<E>

where E: PartialOrd,