Lazily computes the Cartesian product of two or more ranges. The product is a range of tuples of elements from each respective range.
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 less. Only the most frequent tgt.length elements are returned.
Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.
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 O(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 O(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.
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. multiwayUnion(ror) is functionally equivalent to multiwayMerge(ror).uniq.
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.
Lazily computes the intersection of two or more input ranges ranges. The ranges are assumed to be sorted by less. The element types of the ranges must have a common type.
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.
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 O(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 O(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.
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.
Lazily computes the intersection of two or more input ranges ranges. The ranges are assumed to be sorted by less. The element types of the ranges must have a common type.
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.
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 sorted ranges as input.
All algorithms are generalized to accept as input not only sets but also multisets. Each algorithm documents behaviour in the presence of duplicated inputs.