std.algorithm.setops
This is a submodule of std.algorithm. It contains generic algorithms that implement set operations.
The functions multiwayMerge, multiwayUnion, setDifference,
setIntersection, setSymmetricDifference expect a range of sortedranges as input.
All algorithms are generalized to accept as input not only sets but also
multisets. Each algorithmdocuments behaviour in the presence of duplicated inputs.
Copyright
Andrei Alexandrescu 2008-.
Types 6
structMultiwayMerge(alias less, RangeOfRanges)
Merges multiple sets. The input sets are passed as a range of ranges and each is assumed to be sorted by less. Computation is done lazily, one union element at a time. The complexity of one popFront operation is log(ror.length). However, the length of ror decreases as ranges in it are exhausted, so the complexity of a full pass through MultiwayMerge is dependent on the distribution of the lengths of ranges contained within ror. If all ranges have the same length n (worst case scenario), the complexity of a full pass through MultiwayMerge is n ror.length log(ror.length), i.e., log(ror.length) times worse than just spanning all ranges in turn. The output comes sorted (unstably) by less.
The length of the resulting range is the sum of all lengths of the ranges passed as input. This means that all elements (duplicates included) are transferred to the resulting range.
For backward compatibility, multiwayMerge is available under the name nWayUnion and MultiwayMerge under the name of NWayUnion . Future code should use multiwayMerge and MultiwayMerge as nWayUnion and NWayUnion will be deprecated.
Parameters
less | Predicate the given ranges are sorted by. |
ror | A range of ranges sorted by less to compute the union for. |
Returns
A range of the union of the ranges in
ror.
Warning: Because MultiwayMerge does not allocate extra memory, it will leave ror modified. Namely, MultiwayMerge assumes ownership of ror and discretionarily swaps and advances elements of it. If you want ror to preserve its contents after the call, you may want to pass a duplicate to MultiwayMerge (and perhaps cache the duplicate in between calls).
See Also
merge for an analogous function that
takes a static number of ranges of possibly disparate types.
Methods
bool compFront(.ElementType!RangeOfRanges a,
.ElementType!RangeOfRanges b)bool empty() @property@property auto ref front()void popFront()Constructors
this(RangeOfRanges ror)aliasnWayUnion = multiwayMerge
aliasNWayUnion = MultiwayMerge
structSetDifference(alias less = "a < b", R1, R2) if (isInputRange!(R1) && isInputRange!(R2))
Lazily computes the difference of r1 and r2. The two ranges are assumed to be sorted by less. The element types of the two ranges must have a common type.
In the case of multisets, considering that element a appears x times in r1 and y times and r2, the number of occurences of a in the resulting range is going to be x-y if x > y or 0 otherwise.
Parameters
less | Predicate the given ranges are sorted by. |
r1 | The first range. |
r2 | The range to subtract from r1. |
Returns
Fields
R1 r1R2 r2Constructors
this(R1 r1, R2 r2)structSetIntersection(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) &&
!is(CommonType!(staticMap!(ElementType, Rs)) == void))
Lazily computes the intersection of two or more
input rangesranges. The ranges are assumed to be sorted by less. The element types of the ranges must have a common type.
In the case of multisets, the range with the minimum number of occurences of a given element, propagates the number of occurences of this element to the resulting range.
Parameters
less | Predicate the given ranges are sorted by. |
ranges | The ranges to compute the intersection for. |
Returns
A range containing the intersection of the given ranges.
Fields
Rs _inputConstructors
this(Rs input)structSetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!(R1) && isInputRange!(R2))
Lazily computes the symmetric difference of r1 and r2, i.e. the elements that are present in exactly one of r1 and r2. The two ranges are assumed to be sorted by less, and the output is also sorted by less. The element types of the two ranges must have a common type.
If both ranges are sets (without duplicated elements), the resulting range is going to be a set. If at least one of the ranges is a multiset, the number of occurences of an element x in the resulting range is abs(a-b) where a is the number of occurences of x in r1, b is the number of occurences of x in r2, and abs is the absolute value.
If both arguments are ranges of L-values of the same type then SetSymmetricDifference will also be a range of L-values of that type.
Parameters
less | Predicate the given ranges are sorted by. |
r1 | The first range. |
r2 | The second range. |
Returns
Fields
R1 r1R2 r2Methods
void adjustPosition()void popFront()@property auto ref front()ref auto opSlice()bool empty() @propertyConstructors
this(R1 r1, R2 r2)Functions 10
fn
auto cartesianProduct(R1, R2)(R1 range1, R2 range2) if (!allSatisfy!(isForwardRange, R1, R2) ||
anySatisfy!(isInfinite, R1, R2))Lazily computes the Cartesian product of two or more ranges. The product is a range of tuples of elements from each respective range.fn
auto cartesianProduct(RR...)(RR ranges) if (ranges.length >= 2 &&
allSatisfy!(isForwardRange, RR) &&
!anySatisfy!(isInfinite, RR))dittofn
auto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges) if (!allSatisfy!(isForwardRange, R1, R2, RR) ||
anySatisfy!(isInfinite, R1, R2, RR))dittofn
void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges ror, Range tgt, SortOutput sorted = No.sortOutput)Given a range of sorted forward ranges `ror`, copies to `tgt` the elements that are common to most ranges, along with their number of occurrences. All ranges in `ror` are assumed to be sorted by le...fn
void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges ror, Range tgt, WeightsAA weights, SortOutput sorted = No.sortOutput)Similar to `largestPartialIntersection`, but associates a weight with each distinct element in the intersection.fn
MultiwayMerge!(less, RangeOfRanges) multiwayMerge(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror)Dittofn
auto multiwayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror)Computes the union of multiple ranges. The input ranges are passed as a range of ranges and each is assumed to be sorted by less. Computation is done lazily, one union element at a time. `multiwayU...fn
SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs ranges) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) &&
!is(CommonType!(staticMap!(ElementType, Rs)) == void))Dittofn
SetSymmetricDifference!(less, R1, R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1 r1, R2 r2)Ditto