View source code
Display the source code in std/algorithm/setops.d from which this
page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a
Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
local clone.
Module std.algorithm.setops
This is a submodule of std
.
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.
Function Name | Description |
---|---|
cartesianProduct | Computes Cartesian product of two ranges. |
largestPartialIntersection | Copies out the values that occur most frequently in a range of ranges. |
largestPartialIntersectionWeighted | Copies out the values that occur most frequently (multiplied by per-value weights) in a range of ranges. |
multiwayMerge | Merges a range of sorted ranges. |
multiwayUnion | Computes the union of a range of sorted ranges. |
setDifference | Lazily computes the set difference of two or more sorted ranges. |
setIntersection | Lazily computes the intersection of two or more sorted ranges. |
setSymmetricDifference | Lazily computes the symmetric set difference of two or more sorted ranges. |
Functions
Name | Description |
---|---|
cartesianProduct(range1, range2)
|
Lazily computes the Cartesian product of two or more ranges. The product is a range of tuples of elements from each respective range. |
largestPartialIntersection(ror, tgt, sorted)
|
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 elements are returned.
|
largestPartialIntersectionWeighted(ror, tgt, weights, sorted)
|
Similar to largestPartialIntersection , but associates a weight
with each distinct element in the intersection.
|
multiwayMerge(ror)
|
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 ). 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 ), i.e., log(ror times worse than just spanning all ranges in
turn. The output comes sorted (unstably) by less .
|
multiwayUnion(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.
multiwayUnion(ror) is functionally equivalent to multiwayMerge(ror) .
|
setDifference(r1, 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.
|
setIntersection(ranges)
|
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.
|
setSymmetricDifference(r1, 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.
|
Structs
Name | Description |
---|---|
MultiwayMerge
|
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 ). 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 ), i.e., log(ror times worse than just spanning all ranges in
turn. The output comes sorted (unstably) by less .
|
SetDifference
|
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.
|
SetIntersection
|
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.
|
SetSymmetricDifference
|
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.
|
Authors
License
Copyright © 1999-2022 by the D Language Foundation | Page generated by ddox.