Struct range_collections::range_set::RangeSet [−][src]
pub struct RangeSet<A: Array>(_);
Expand description
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
intersection in place
union in place
difference in place
symmetric difference in place (xor)
Trait Implementations
impl<A: Array> AbstractRangeSet<<A as Array>::Item> for RangeSet<A> where
A::Item: RangeSetEntry,
impl<A: Array> AbstractRangeSet<<A as Array>::Item> for RangeSet<A> where
A::Item: RangeSetEntry,
the boundaries as a reference - must be strictly sorted
convert to a normal range set
true if the value is contained in the range set
true if the range set contains all values
true if this range set is disjoint from another range set
true if this range set is a superset of another range set Read more
true if this range set is a subset of another range set Read more
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,
fn intersection<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
A: Array<Item = T>,
T: Ord + Clone,
intersection
union
fn difference<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
A: Array<Item = T>,
T: Ord + Clone,
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,
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,
impl<A: Array> AbstractRangeSet<<A as Array>::Item> for &RangeSet<A> where
A::Item: RangeSetEntry,
the boundaries as a reference - must be strictly sorted
convert to a normal range set
true if the value is contained in the range set
true if the range set contains all values
true if this range set is disjoint from another range set
true if this range set is a superset of another range set Read more
true if this range set is a subset of another range set Read more
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,
fn intersection<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
A: Array<Item = T>,
T: Ord + Clone,
intersection
union
fn difference<A>(&self, that: &impl AbstractRangeSet<T>) -> RangeSet<A> where
A: Array<Item = T>,
T: Ord + Clone,
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,
fn symmetric_difference<A>(
&self,
that: &impl AbstractRangeSet<T>
) -> RangeSet<A> where
A: Array<Item = T>,
T: Ord + Clone,
symmetric difference (xor)
compute the intersection of this range set with another, producing a new range set
∀ t ∈ T, r(t) = a(t) & b(t)
Performs the &=
operation. Read more
compute the union of this range set with another, producing a new range set
∀ t ∈ T, r(t) = a(t) | b(t)
Performs the |=
operation. Read more
compute the exclusive or of this range set with another, producing a new range set
∀ t ∈ T, r(t) = a(t) ^ b(t)
Performs the ^=
operation. Read more
compute the negation of this range set
∀ t ∈ T, r(t) = !a(t)
compute the negation of this range set
∀ t ∈ T, r(t) = !a(t)
impl<A: Array, R: AbstractRangeSet<A::Item>> PartialEq<R> for RangeSet<A> where
A::Item: RangeSetEntry,
impl<A: Array, R: AbstractRangeSet<A::Item>> PartialEq<R> for RangeSet<A> where
A::Item: RangeSetEntry,
compute the difference of this range set with another, producing a new range set
∀ t ∈ T, r(t) = a(t) & !b(t)
Performs the -=
operation. Read more
Auto Trait Implementations
impl<A> RefUnwindSafe for RangeSet<A> where
A: RefUnwindSafe,
<A as Array>::Item: RefUnwindSafe,
impl<A> UnwindSafe for RangeSet<A> where
A: UnwindSafe,
<A as Array>::Item: RefUnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more