pub struct RangeSet<A>{ /* private fields */ }
Expand description
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§
source§impl<A, T> RangeSet<A>
impl<A, T> RangeSet<A>
sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
New empty range set with the internal smallvec initialized with the given initial capacity
sourcepub fn from_smallvec(ranges: SmallVec<A>) -> Option<Self>
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
)
sourcepub unsafe fn from_raw_parts(ranges: SmallVec<A>) -> Self
pub unsafe fn from_raw_parts(ranges: SmallVec<A>) -> Self
Unchecked create from smallvec
sourcepub fn from_valid_ranges<V: AsRef<[RangeInclusive<T>]>>(
ranges: V
) -> Option<Self>
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
)
sourcepub fn from_ranges<V: AsRef<[RangeInclusive<T>]>>(ranges: V) -> Self
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.
sourcepub fn from_elements<V: AsRef<[T]>>(elements: V) -> Self
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);
sourcepub fn into_smallvec(self) -> SmallVec<A>
pub fn into_smallvec(self) -> SmallVec<A>
Converts into the internal smallvec
sourcepub fn contains(&self, element: T) -> bool
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));
sourcepub fn contains_range(&self, range: A::Item) -> bool
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));
sourcepub fn is_superset(&self, other: &Self) -> bool
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));
sourcepub fn is_subset(&self, other: &Self) -> bool
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));
sourcepub fn max(&self) -> Option<T>
pub fn max(&self) -> Option<T>
Returns the largest element in the set, or None
if the set is empty.
sourcepub fn min(&self) -> Option<T>
pub fn min(&self) -> Option<T>
Returns the smallest element in the set, or None
if the set is empty.
sourcepub fn insert(&mut self, element: T) -> bool
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]));
sourcepub fn remove(&mut self, element: T) -> bool
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());
sourcepub fn insert_range(&mut self, range: A::Item) -> Option<Self>
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);
sourcepub fn remove_range(&mut self, range: A::Item) -> Option<Self>
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());
sourcepub fn iter(&self) -> Iter<'_, A, T> ⓘ
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.
sourcepub fn shrink_to_fit(&mut self)
pub fn shrink_to_fit(&mut self)
Calls shrink_to_fit
on the underlying smallvec
Trait Implementations§
source§impl<A, T> From<RangeInclusive<T>> for RangeSet<A>
impl<A, T> From<RangeInclusive<T>> for RangeSet<A>
source§fn from(range: RangeInclusive<T>) -> Self
fn from(range: RangeInclusive<T>) -> Self
source§impl<A, B> PartialEq<RangeSet<B>> for RangeSet<A>
impl<A, B> PartialEq<RangeSet<B>> for RangeSet<A>
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.