Struct range_collections::range_set::RangeSet

pub struct RangeSet<A: Array>(_);

A set of non-overlapping ranges

let mut a: RangeSet2<i32> = RangeSet::from(10..);
let b: RangeSet2<i32> = RangeSet::from(1..5);

a |= b;
let r = !a;

A data structure to represent a set of non-overlapping ranges of element type T: RangeSetEntry. It uses a SmallVec<T> of sorted boundaries internally.

It can represent not just finite ranges but also ranges with unbounded end. Because it can represent infinite ranges, it can also represent the set of all elements, and therefore all boolean operations including negation.

Adjacent ranges will be merged.

It provides very fast operations for set operations (&, |, ^) as well as for intersection tests (is_disjoint, is_subset).

In addition to the fast set operations that produce a new range set, it also supports the equivalent in-place operations.

Complexity

Complexity is given separately for the number of comparisons and the number of copies, since sometimes you have a comparison operation that is basically free (any of the primitive types), whereas sometimes you have a comparison operation that is many orders of magnitude more expensive than a copy (long strings, arbitrary precision integers, …)

Number of comparisons

operation	best	worst	remark
negation	1	O(N)
union	O(log(N))	O(N)	binary merge
intersection	O(log(N))	O(N)	binary merge
difference	O(log(N))	O(N)	binary merge
xor	O(log(N))	O(N)	binary merge
membership	O(log(N))	O(log(N))	binary search
is_disjoint	O(log(N))	O(N)	binary merge with cutoff
is_subset	O(log(N))	O(N)	binary merge with cutoff

Number of copies

For creating new sets, obviously there needs to be at least one copy for each element of the result set, so the complexity is always O(N). For in-place operations it gets more interesting. In case the number of elements of the result being identical to the number of existing elements, there will be no copies and no allocations.

E.g. if the result just has some of the ranges of the left hand side extended or truncated, but the same number of boundaries, there will be no allocations and no copies except for the changed boundaries themselves.

If the result has fewer boundaries than then lhs, there will be some copying but no allocations. Only if the result is larger than the capacity of the underlying vector of the lhs will there be allocations.

operation	best	worst
negation	1	1
union	1	O(N)
intersection	1	O(N)
difference	1	O(N)
xor	1	O(N)

Testing

Testing is done by some simple smoke tests as well as quickcheck tests of the algebraic properties of the boolean operations.

Implementations

impl<T, A: Array<Item = T>> RangeSet<A>

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

iterate over all ranges in this range set

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

get the boundaries in this range set as a SmallVec

impl<T: RangeSetEntry, A: Array<Item = T>> RangeSet<A>

pub fn empty() -> Self

the empty range set

pub fn all() -> Self

a range set containing all values

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> RangeSet<A>

pub fn intersection_with(&mut self, that: &impl AbstractRangeSet<T>)

intersection in place

pub fn union_with(&mut self, that: &impl AbstractRangeSet<T>)

union in place

pub fn difference_with(&mut self, that: &impl AbstractRangeSet<T>)

difference in place

pub fn symmetric_difference_with(&mut self, that: &impl AbstractRangeSet<T>)

symmetric difference in place (xor)

Trait Implementations

impl<A: Array> AbstractRangeSet<<A as Array>::Item> for RangeSet<A> where
    A::Item: RangeSetEntry, 

fn boundaries(&self) -> &[A::Item]

the boundaries as a reference - must be strictly sorted

fn to_range_set<A: Array<Item = T>>(&self) -> RangeSet<A> where
    T: Clone, 

convert to a normal range set

fn contains(&self, value: &T) -> bool where
    T: Ord, 

true if the value is contained in the range set

fn is_empty(&self) -> bool

true if the range set is empty

fn is_all(&self) -> bool where
    T: RangeSetEntry, 

true if the range set contains all values

fn is_disjoint(&self, that: &impl AbstractRangeSet<T>) -> bool where
    T: RangeSetEntry, 

true if this range set is disjoint from another range set

fn is_subset(&self, that: impl AbstractRangeSet<T>) -> bool where
    T: Ord, 

true if this range set is a superset of another range set

fn is_superset(&self, that: impl AbstractRangeSet<T>) -> bool where
    T: Ord, 

true if this range set is a subset of another range set

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

iterate over all ranges in this range set

fn intersection<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

intersection

fn union<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

union

fn difference<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

difference

fn symmetric_difference<A>(
    &self,
    that: &impl AbstractRangeSet<T>
) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

symmetric difference (xor)

impl<A: Array> AbstractRangeSet<<A as Array>::Item> for &RangeSet<A> where
    A::Item: RangeSetEntry, 

fn boundaries(&self) -> &[A::Item]

the boundaries as a reference - must be strictly sorted

fn to_range_set<A: Array<Item = T>>(&self) -> RangeSet<A> where
    T: Clone, 

convert to a normal range set

fn contains(&self, value: &T) -> bool where
    T: Ord, 

true if the value is contained in the range set

fn is_empty(&self) -> bool

true if the range set is empty

fn is_all(&self) -> bool where
    T: RangeSetEntry, 

true if the range set contains all values

fn is_disjoint(&self, that: &impl AbstractRangeSet<T>) -> bool where
    T: RangeSetEntry, 

true if this range set is disjoint from another range set

fn is_subset(&self, that: impl AbstractRangeSet<T>) -> bool where
    T: Ord, 

true if this range set is a superset of another range set

fn is_superset(&self, that: impl AbstractRangeSet<T>) -> bool where
    T: Ord, 

true if this range set is a subset of another range set

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

iterate over all ranges in this range set

fn intersection<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

intersection

fn union<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

union

fn difference<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

difference

fn symmetric_difference<A>(
    &self,
    that: &impl AbstractRangeSet<T>
) -> RangeSet<A> where
    A: Array<Item = T>,
    T: Ord + Clone, 

symmetric difference (xor)

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> BitAnd<&'_ RangeSet<A>> for &RangeSet<A>

compute the intersection of this range set with another, producing a new range set

∀ t ∈ T, r(t) = a(t) & b(t)

type Output = RangeSet<A>

The resulting type after applying the & operator.

fn bitand(self, that: Self) -> Self::Output

Performs the & operation.

impl<T: Ord, A: Array<Item = T>> BitAndAssign<RangeSet<A>> for RangeSet<A>

fn bitand_assign(&mut self, that: Self)

Performs the &= operation.

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> BitOr<&'_ RangeSet<A>> for &RangeSet<A>

compute the union of this range set with another, producing a new range set

∀ t ∈ T, r(t) = a(t) | b(t)

type Output = RangeSet<A>

The resulting type after applying the | operator.

fn bitor(self, that: Self) -> Self::Output

Performs the | operation.

impl<T: Ord, A: Array<Item = T>> BitOrAssign<RangeSet<A>> for RangeSet<A>

fn bitor_assign(&mut self, that: Self)

Performs the |= operation.

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> BitXor<&'_ RangeSet<A>> for &RangeSet<A>

compute the exclusive or of this range set with another, producing a new range set

∀ t ∈ T, r(t) = a(t) ^ b(t)

type Output = RangeSet<A>

The resulting type after applying the ^ operator.

fn bitxor(self, that: Self) -> Self::Output

Performs the ^ operation.

impl<T: RangeSetEntry, A: Array<Item = T>> BitXorAssign<RangeSet<A>> for RangeSet<A>

fn bitxor_assign(&mut self, that: Self)

Performs the ^= operation.

impl<A: Array> Clone for RangeSet<A> where
    A::Item: Clone, 

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, A: Array<Item = T>> Debug for RangeSet<A>

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

Formats the value using the given formatter.

impl<T: RangeSetEntry, A: Array<Item = T>> From<Range<T>> for RangeSet<A>

fn from(value: Range<T>) -> Self

Performs the conversion.

impl<T: RangeSetEntry, A: Array<Item = T>> From<RangeFrom<T>> for RangeSet<A>

fn from(value: RangeFrom<T>) -> Self

Performs the conversion.

impl<T: RangeSetEntry, A: Array<Item = T>> From<RangeTo<T>> for RangeSet<A>

fn from(value: RangeTo<T>) -> Self

Performs the conversion.

impl<T: RangeSetEntry, A: Array<Item = T>> From<bool> for RangeSet<A>

fn from(value: bool) -> Self

Performs the conversion.

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> Not for RangeSet<A>

compute the negation of this range set

∀ t ∈ T, r(t) = !a(t)

type Output = RangeSet<A>

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> Not for &RangeSet<A>

compute the negation of this range set

∀ t ∈ T, r(t) = !a(t)

type Output = RangeSet<A>

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl<A: Array, R: AbstractRangeSet<A::Item>> PartialEq<R> for RangeSet<A> where
    A::Item: RangeSetEntry, 

fn eq(&self, that: &R) -> 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 !=.

impl<T: RangeSetEntry + Clone, A: Array<Item = T>> Sub<&'_ RangeSet<A>> for &RangeSet<A>

compute the difference of this range set with another, producing a new range set

∀ t ∈ T, r(t) = a(t) & !b(t)

type Output = RangeSet<A>

The resulting type after applying the - operator.

fn sub(self, that: Self) -> Self::Output

Performs the - operation.

impl<T: Ord, A: Array<Item = T>> SubAssign<RangeSet<A>> for RangeSet<A>

fn sub_assign(&mut self, that: Self)

Performs the -= operation.

impl<A: Array> Eq for RangeSet<A> where
    A::Item: Eq + RangeSetEntry,