Struct range_set::RangeSet

pub struct RangeSet<A>
where
    A: Array + Eq + Debug,
    A::Item: Clone + Eq + Debug,
{ /* private fields */ }

A set of primitive integers represented as a sorted list of disjoint, inclusive ranges.

The generic parameter specifies the type of on-stack array to be used in the backing SmallVec storage.

let mut s = RangeSet::<[RangeInclusive <u32>; 1]>::from (0..=2);
println!("s: {:?}", s);
assert!(!s.spilled());

assert!(s.insert_range (8..=10).is_none());
println!("s: {:?}", s);
assert!(s.spilled());
let v : Vec <u32> = s.iter().collect();
assert_eq!(v, vec![0,1,2,8,9,10]);

assert_eq!(s.insert_range (3..=12), Some (RangeSet::from (8..=10)));
println!("s: {:?}", s);
assert!(s.spilled());  // once spilled, stays spilled
let v : Vec <u32> = s.iter().collect();
assert_eq!(v, vec![0,1,2,3,4,5,6,7,8,9,10,11,12]);
s.shrink_to_fit();  // manually un-spill
assert!(!s.spilled());

Implementations

impl<A, T> RangeSet<A>

where A: Array<Item = RangeInclusive<T>> + Eq + Debug, T: PrimInt + Debug,

pub fn new() -> Self

New empty range set

pub fn with_capacity(capacity: usize) -> Self

New empty range set with the internal smallvec initialized with the given initial capacity

pub fn from_smallvec(ranges: SmallVec<A>) -> Option<Self>

Returns a new range set if the given smallvec is valid and sorted (valid_range_slice)

pub unsafe fn from_raw_parts(ranges: SmallVec<A>) -> Self

Unchecked create from smallvec

pub fn from_valid_ranges<V: AsRef<[RangeInclusive<T>]>>( ranges: V ) -> Option<Self>

Returns a new range set if the given slice of ranges is valid and sorted (valid_range_slice)

pub fn from_ranges<V: AsRef<[RangeInclusive<T>]>>(ranges: V) -> Self

Constructs a new range set from an array or vector of inclusive ranges.

This method has been specially optimized for non-overlapping, non- adjacent ranges in ascending order.

pub fn from_elements<V: AsRef<[T]>>(elements: V) -> Self

Constructs a new range set from a slice of numbers.

This method has been specially optimized for deduplicated arrays, sorted in ascending order. Construction time is O(n) for these arrays.

let reference = range_set![1..=4, 6, 8..=10, (u32::MAX); 4];

// Optimal ordering. Special O(n) applies.
let good = RangeSet::<[RangeInclusive<u32>; 4]>::from_elements([1, 2, 3, 4, 6, 8, 9, 10, u32::MAX]);

// Random ordering. Very expensive.
let bad = RangeSet::<[RangeInclusive<u32>; 4]>::from_elements([2, 9, 6, 8, 1, u32::MAX, 4, 10, 3, 4, 8]);

assert_eq!(good, reference);
assert_eq!(bad, reference);

pub fn is_empty(&self) -> bool

Check if range set is empty

pub fn clear(&mut self)

Clears the range set

pub fn into_smallvec(self) -> SmallVec<A>

Converts into the internal smallvec

pub fn contains(&self, element: T) -> bool

Returns true if the element is contained in this set.

let mut set = RangeSet::<[RangeInclusive <u32>; 4]>::new();
set.insert_range(2..=5);
set.insert_range(10..=70);
set.insert(72);
set.insert_range(74..=80);

assert!(set.contains(2));
assert!(set.contains(3));
assert!(set.contains(33));
assert!(set.contains(72));
assert!(set.contains(80));

assert!(!set.contains(0));
assert!(!set.contains(6));
assert!(!set.contains(71));
assert!(!set.contains(122));

pub fn contains_range(&self, range: A::Item) -> bool

Returns true if all the elements of range are contained in this set.

let mut set = RangeSet::<[RangeInclusive <u32>; 4]>::new();
set.insert_range(2..=5);
set.insert_range(10..=70);
set.insert(72);
set.insert_range(74..=80);

assert!(set.contains_range(2..=4));
assert!(set.contains_range(3..=5));
assert!(set.contains_range(33..=50));
assert!(set.contains_range(75..=80));

assert!(!set.contains_range(0..=6));
assert!(!set.contains_range(3..=6));
assert!(!set.contains_range(10..=72));
assert!(!set.contains_range(50..=75));
assert!(!set.contains_range(71..=72));
assert!(!set.contains_range(122..=200));

pub fn is_superset(&self, other: &Self) -> bool

Returns true if the set is a superset of another, i.e., self contains at least all the elements in other.

let main = RangeSet::<[RangeInclusive<u32>; 1]>::from(3..=15);
let mut superset = RangeSet::from(0..=15);

assert!(superset.is_superset(&main));
superset.remove(8);
assert!(!superset.is_superset(&main));

pub fn is_subset(&self, other: &Self) -> bool

Returns true if the set is a subset of another, i.e., other contains at least all the elements in self.

let main = RangeSet::<[RangeInclusive<u32>; 1]>::from(3..=15);
let mut subset = RangeSet::from(6..=10);

assert!(subset.is_subset(&main));
subset.insert(99);
assert!(!subset.is_subset(&main));

pub fn max(&self) -> Option<T>

Returns the largest element in the set, or None if the set is empty.

pub fn min(&self) -> Option<T>

Returns the smallest element in the set, or None if the set is empty.

pub fn insert(&mut self, element: T) -> bool

Insert a single element, returning true if it was successfully inserted or else false if it was already present

type R = [RangeInclusive <u32>; 2];
let mut s = RangeSet::<R>::new();
assert!(s.insert (4));
assert_eq!(s, RangeSet::<R>::from (4..=4));
assert!(!s.insert (4));
assert_eq!(s, RangeSet::<R>::from (4..=4));
assert!(s.insert (5));
assert_eq!(s, RangeSet::<R>::from (4..=5));
assert!(s.insert (3));
assert_eq!(s, RangeSet::<R>::from (3..=5));
assert!(s.insert (10));
assert_eq!(s, RangeSet::<R>::from_ranges ([3..=5, 10..=10]));

pub fn remove(&mut self, element: T) -> bool

Remove a single element, returning true if it was successfully removed or else false if it was not present

type R = [RangeInclusive <u32>; 2];
let mut s = RangeSet::<R>::from (0..=5);
assert!(s.remove (1));
assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=5]));
assert!(!s.remove (1));
assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=5]));
assert!(s.remove (4));
assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=3, 5..=5]));
assert!(s.remove (3));
assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 2..=2, 5..=5]));
assert!(s.remove (2));
assert_eq!(s, RangeSet::<R>::from_ranges ([0..=0, 5..=5]));
assert!(s.remove (0));
assert_eq!(s, RangeSet::<R>::from (5..=5));
assert!(s.remove (5));
assert!(s.is_empty());

pub fn insert_range(&mut self, range: A::Item) -> Option<Self>

Returns the intersected values if the range is not disjoint with the curret range set.

let mut s = RangeSet::<[RangeInclusive <u32>; 2]>::from (0..=5);
assert_eq!(s.insert_range ( 3..=10), Some (RangeSet::from (3..=5)));
assert_eq!(s.insert_range (20..=30), None);

pub fn remove_range(&mut self, range: A::Item) -> Option<Self>

Removes and returns the intersected elements, if there were any.

let mut s = RangeSet::<[RangeInclusive <u32>; 2]>::from (0..=5);
assert_eq!(s.remove_range (3..=3), Some (RangeSet::from (3..=3)));
assert_eq!(s, RangeSet::<[_; 2]>::from_ranges ([0..=2, 4..=5]));
assert_eq!(s.remove_range (0..=10),
  Some (RangeSet::<[_; 2]>::from_ranges ([0..=2, 4..=5])));
assert!(s.is_empty());

pub fn iter(&self) -> Iter<'_, A, T>

Iterate over elements of the RangeSet.

To iterate over individual ranges, use range_set.as_ref().iter() instead.

pub fn spilled(&self) -> bool

Calls spilled on the underlying smallvec

pub fn shrink_to_fit(&mut self)

Calls shrink_to_fit on the underlying smallvec

Trait Implementations

impl<A, T> AsRef<SmallVec<A>> for RangeSet<A>

where A: Array<Item = RangeInclusive<T>> + Eq + Debug, T: PrimInt + Debug,

fn as_ref(&self) -> &SmallVec<A>

Converts this type into a shared reference of the (usually inferred) input type.

impl<A> Clone for RangeSet<A>

where A: Array + Eq + Debug + Clone, A::Item: Clone + Eq + Debug,

fn clone(&self) -> RangeSet<A>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A> Debug for RangeSet<A>

where A: Array + Eq + Debug + Debug, A::Item: Clone + Eq + Debug,

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

Formats the value using the given formatter.

impl<A, T> From<RangeInclusive<T>> for RangeSet<A>

where A: Array<Item = RangeInclusive<T>> + Eq + Debug, T: PrimInt + Debug,

fn from(range: RangeInclusive<T>) -> Self

Converts to this type from the input type.

impl<A, B> PartialEq<RangeSet<B>> for RangeSet<A>

where A: Array + Eq + Debug, A::Item: Clone + Eq + Debug, B: Array<Item = A::Item> + Eq + Debug,

This is a better PartialEq implementation than the derived one; it’s generic over array sizes. Smallvec’s array length should be an internal implementation detail, and shouldn’t affect whether two RangeSets are equal.

fn eq(&self, other: &RangeSet<B>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<A> Eq for RangeSet<A>

where A: Array + Eq + Debug + Eq, A::Item: Clone + Eq + Debug,

impl<A> StructuralEq for RangeSet<A>

where A: Array + Eq + Debug, A::Item: Clone + Eq + Debug,