# std.algorithm.setops

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. |

nWayUnion | Computes the union of a set of sets implemented as 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. |

setUnion | Lazily computes the set union of two or more sorted ranges. |

Source: std/algorithm/setops.d

- auto cartesianProduct(R1, R2)(R1
*range1*, R2*range2*) if (!allSatisfy!(isForwardRange, R1, R2) || anySatisfy!(isInfinite, R1, R2));

auto cartesianProduct(RR...)(RR*ranges*) if (*ranges*.length >= 2 && allSatisfy!(isForwardRange, RR) && !anySatisfy!(isInfinite, RR));

auto cartesianProduct(R1, R2, RR...)(R1*range1*, R2*range2*, RR*otherRanges*) if (!allSatisfy!(isForwardRange, R1, R2, RR) || anySatisfy!(isInfinite, R1, R2, RR)); - Lazily computes the Cartesian product of two or more
*ranges*. The product is a range of tuples of elements from each respective range.The conditions for the two-range case are as follows: If both*ranges*are finite, then one must be (at least) a forward range and the other an input range. If one range is infinite and the other finite, then the finite range must be a forward range, and the infinite range can be an input range. If both*ranges*are infinite, then both must be forward*ranges*. When there are more than two*ranges*, the above conditions apply to each adjacent pair of*ranges*.Examples:import std.algorithm.searching : canFind; import std.range; import std.typecons : tuple; auto N = sequence!"n"(0); // the range of natural numbers auto N2 = cartesianProduct(N, N); // the range of all pairs of natural numbers // Various arbitrary number pairs can be found in the range in finite time. assert(canFind(N2, tuple(0, 0))); assert(canFind(N2, tuple(123, 321))); assert(canFind(N2, tuple(11, 35))); assert(canFind(N2, tuple(279, 172)));

Examples:import std.algorithm.searching : canFind; import std.typecons : tuple; auto B = [ 1, 2, 3 ]; auto C = [ 4, 5, 6 ]; auto BC = cartesianProduct(B, C); foreach (n; [[1, 4], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [1, 6], [2, 6], [3, 6]]) { assert(canFind(BC, tuple(n[0], n[1]))); }

Examples:import std.algorithm.comparison : equal; import std.typecons : tuple; auto A = [ 1, 2, 3 ]; auto B = [ 'a', 'b', 'c' ]; auto C = [ "x", "y", "z" ]; auto ABC = cartesianProduct(A, B, C); assert(ABC.equal([ tuple(1, 'a', "x"), tuple(1, 'a', "y"), tuple(1, 'a', "z"), tuple(1, 'b', "x"), tuple(1, 'b', "y"), tuple(1, 'b', "z"), tuple(1, 'c', "x"), tuple(1, 'c', "y"), tuple(1, 'c', "z"), tuple(2, 'a', "x"), tuple(2, 'a', "y"), tuple(2, 'a', "z"), tuple(2, 'b', "x"), tuple(2, 'b', "y"), tuple(2, 'b', "z"), tuple(2, 'c', "x"), tuple(2, 'c', "y"), tuple(2, 'c', "z"), tuple(3, 'a', "x"), tuple(3, 'a', "y"), tuple(3, 'a', "z"), tuple(3, 'b', "x"), tuple(3, 'b', "y"), tuple(3, 'b', "z"), tuple(3, 'c', "x"), tuple(3, 'c', "y"), tuple(3, 'c', "z") ]));

- void largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRanges
*ror*, Range*tgt*, SortOutput*sorted*= SortOutput.no); - 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.Example:

// Figure which number can be found in most arrays of the set of // arrays below. double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto b = new Tuple!(double, uint)[1]; largestPartialIntersection(a, b); // First member is the item, second is the occurrence count assert(b[0] == tuple(7.0, 4u));

7.0 is the correct answer because it occurs in 4 out of the 5 inputs, more than any other number. The second member of the resulting tuple is indeed 4 (recording the number of occurrences of 7.0). If more of the top-frequent numbers are needed, just create a larger*tgt*range. In the example above, creating b with length 2 yields tuple(1.0, 3u) in the second position. The function largestPartialIntersection is useful for e.g. searching an inverted index for the documents most likely to contain some terms of interest. The complexity of the search is Ο(n * log(*tgt*.length)), where n is the sum of lengths of all input ranges. This approach is faster than keeping an associative array of the occurrences and then selecting its top items, and also requires less memory (largestPartialIntersection builds its result directly in*tgt*and requires no extra memory).Warning: Because largestPartialIntersection does not allocate extra memory, it will leave

*ror*modified. Namely, largestPartialIntersection 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 largestPartialIntersection (and perhaps cache the duplicate in between calls). - void largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRanges
*ror*, Range*tgt*, WeightsAA*weights*, SortOutput*sorted*= SortOutput.no); - Similar to largestPartialIntersection, but associates a weight with each distinct element in the intersection.
Example:

// Figure which number can be found in most arrays of the set of // arrays below, with specific per-element weights double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto b = new Tuple!(double, uint)[1]; double[double] weights = [ 1:1.2, 4:2.3, 7:1.1, 8:1.1 ]; largestPartialIntersectionWeighted(a, b, weights); // First member is the item, second is the occurrence count assert(b[0] == tuple(4.0, 2u));

The correct answer in this case is 4.0, which, although only appears two times, has a total weight 4.6 (three times its weight 2.3). The value 7 is weighted with 1.1 and occurs four times for a total weight 4.4. - struct NWayUnion(alias less, RangeOfRanges);

NWayUnion!(less, RangeOfRanges) nWayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges*ror*); - Computes the union of 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 NWayUnion 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 NWayUnion 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.Warning: Because NWayUnion does not allocate extra memory, it will leave

*ror*modified. Namely, NWayUnion 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 NWayUnion (and perhaps cache the duplicate in between calls).Examples:import std.algorithm.comparison : equal; double[][] a = [ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ], ]; auto witness = [ 1, 1, 1, 4, 4, 7, 7, 7, 7, 8, 8 ]; assert(equal(nWayUnion(a), witness));

- struct SetDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);

SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)(R1*r1*, R2*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.Examples:import std.algorithm.comparison : equal; int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; assert(equal(setDifference(a, b), [5, 9][])); static assert(isForwardRange!(typeof(setDifference(a, b))));

- struct SetIntersection(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));

SetIntersection!(less, Rs) setIntersection(alias less = "a < b", Rs...)(Rs*ranges*) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void)); - 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.Examples:import std.algorithm.comparison : equal; int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; int[] c = [ 0, 1, 4, 5, 7, 8 ]; assert(equal(setIntersection(a, a), a)); assert(equal(setIntersection(a, b), [1, 2, 4, 7])); assert(equal(setIntersection(a, b, c), [1, 4, 7]));

- struct SetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);

SetSymmetricDifference!(less, R1, R2) setSymmetricDifference(alias less = "a < b", R1, R2)(R1*r1*, R2*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 arguments are ranges of L-values of the same type then SetSymmetricDifference will also be a range of L-values of that type.Examples:import std.algorithm.comparison : equal; int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][])); static assert(isForwardRange!(typeof(setSymmetricDifference(a, b))));

- struct SetUnion(alias less = "a < b", Rs...) if (allSatisfy!(isInputRange, Rs));

SetUnion!(less, Rs) setUnion(alias less = "a < b", Rs...)(Rs*rs*); - Lazily computes the union of two or more ranges
*rs*. The ranges are assumed to be sorted by less. Elements in the output are not unique; the length of the output is the sum of the lengths of the inputs. (The length member is offered if all ranges also have length.) The element types of all ranges must have a common type.Examples:import std.algorithm.comparison : equal; int[] a = [ 1, 2, 4, 5, 7, 9 ]; int[] b = [ 0, 1, 2, 4, 7, 8 ]; double[] c = [ 10.5 ]; static assert(isForwardRange!(typeof(setUnion(a, b)))); assert(setUnion(a, b).length == a.length + b.length); assert(equal(setUnion(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][])); assert(equal(setUnion(a, c, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10.5][])); auto u = setUnion(a, b); u.front--; assert(equal(u, [-1, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));