| 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. |
Sourcestd/algorithm/setops.d
cartesianProduct(R1, R2)(R1range1, R2range2)cartesianProduct(RR...)(RRranges)ranges.length >= 2 && allSatisfy!(isForwardRange, RR) && !anySatisfy!(isInfinite, RR));cartesianProduct(R1, R2, RR...)(R1range1, R2range2, RRotherRanges)R1range1 | The first range |
R2range2 | The second range |
RRranges | Two or more non-infinite forward ranges |
RRotherRanges | Zero or more non-infinite forward ranges |
import std.algorithm.searching : canFind;import std.range;import std.typecons : tuple;auto N = sequence!"n"(0);// the range of natural numbersauto 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)));
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])));}
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")]));
largestPartialIntersection(alias less = "a < b", RangeOfRanges, Range)(RangeOfRangesror, Rangetgt, SortOutputsorted = No.sortOutput);ror, copies totgt the elements that are common to most ranges, along with their numberof occurrences. All ranges inror are assumed to be sorted byless. Only the most frequenttgt.length elements are returned.| less | The predicate the ranges are sorted by. |
RangeOfRangesror | A range of forward ranges sorted byless. |
Rangetgt | The target range to copy common elements to. |
SortOutputsorted | Whether the elements copied should be in sorted order.The functionlargestPartialIntersection is useful fore.g. searching aninverted index for the documents mostlikely to contain some terms of interest. The complexity of the searchisΟ(n * log(tgt.length)), wheren is the sum of lengths ofall input ranges. This approach is faster than keeping an associativearray of the occurrences and then selecting its top items, and alsorequires less memory (largestPartialIntersection builds itsresult directly intgt and requires no extra memory).If at least one of the ranges is a multiset, then all occurencesof a duplicate element are taken into account. The result isequivalent to merging all ranges and picking the most frequenttgt.length elements. |
WarningBecauselargestPartialIntersection does not allocateextra memory, it will leaveror modified. Namely,largestPartialIntersection assumes ownership ofror anddiscretionarily swaps and advances elements of it. If you wantror to preserve its contents after the call, you may want to pass aduplicate tolargestPartialIntersection (and perhaps cache theduplicate in between calls).
import std.typecons : tuple, Tuple;// 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];// it will modify the input range, hence we need to create a duplicatelargestPartialIntersection(a.dup, b);// First member is the item, second is the occurrence countwriteln(b[0]);// tuple(7.0, 4u)// 7.0 occurs in 4 out of 5 inputs, more than any other number// If more of the top-frequent numbers are needed, just create a larger// tgt rangeauto c =new Tuple!(double,uint)[2];largestPartialIntersection(a, c);writeln(c[0]);// tuple(1.0, 3u)// 1.0 occurs in 3 inputs// multisetdouble[][] x =[ [1, 1, 1, 1, 4, 7, 8], [1, 7], [1, 7, 8], [4, 7], [7]];auto y =new Tuple!(double,uint)[2];largestPartialIntersection(x.dup, y);// 7.0 occurs 5 timeswriteln(y[0]);// tuple(7.0, 5u)// 1.0 occurs 6 timeswriteln(y[1]);// tuple(1.0, 6u)
largestPartialIntersectionWeighted(alias less = "a < b", RangeOfRanges, Range, WeightsAA)(RangeOfRangesror, Rangetgt, WeightsAAweights, SortOutputsorted = No.sortOutput);tgt.length, weight-based ranking elements.| less | The predicate the ranges are sorted by. |
RangeOfRangesror | A range offorward ranges sorted byless. |
Rangetgt | The target range to copy common elements to. |
WeightsAAweights | An associative array mapping elements to weights. |
SortOutputsorted | Whether the elements copied should be in sorted order. |
import std.typecons : tuple, Tuple;// Figure which number can be found in most arrays of the set of// arrays below, with specific per-element weightsdouble[][] 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 countwriteln(b[0]);// tuple(4.0, 2u)// 4.0 occurs 2 times -> 4.6 (2 * 2.3)// 7.0 occurs 3 times -> 4.4 (3 * 1.1)// multisetdouble[][] x =[ [ 1, 1, 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ],];auto y =new Tuple!(double,uint)[1];largestPartialIntersectionWeighted(x, y,weights);writeln(y[0]);// tuple(1.0, 5u)// 1.0 occurs 5 times -> 1.2 * 5 = 6
MultiwayMerge(alias less, RangeOfRanges);multiwayMerge(alias less = "a < b", RangeOfRanges)(RangeOfRangesror);ror decreases as rangesin it are exhausted, so the complexity of a full pass throughMultiwayMerge is dependent on the distribution of the lengths of rangescontained withinror. If all ranges have the same lengthn(worst case scenario), the complexity of a full pass throughMultiwayMerge isΟ(n * ror.length * log(ror.length)), i.e.,log(ror.length) times worse than just spanning all ranges inturn. The output comes sorted (unstably) byless.multiwayMerge is available underthe namenWayUnion andMultiwayMerge under the name ofNWayUnion .Future code should usemultiwayMerge andMultiwayMerge asnWayUnionandNWayUnion will be deprecated.| less | Predicate the given ranges are sorted by. |
RangeOfRangesror | A range of ranges sorted byless to compute the union for. |
ror.WarningBecauseMultiwayMerge does not allocate extra memory, itwill leaveror modified. Namely,MultiwayMerge assumes ownershipofror and discretionarily swaps and advances elements of it. Ifyou wantror to preserve its contents after the call, you maywant to pass a duplicate toMultiwayMerge (and perhaps cache theduplicate in between calls).
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(multiwayMerge(a), witness));double[][] b =[// range with duplicates [ 1, 1, 4, 7, 8 ], [ 7 ], [ 1, 7, 8], [ 4 ], [ 7 ],];// duplicates are propagated to the resulting rangeassert(equal(multiwayMerge(b), witness));
compFront(.ElementType!RangeOfRangesa, .ElementType!RangeOfRangesb);ror);empty();front();popFront();multiwayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRangesror);multiwayUnion(ror) is functionally equivalent tomultiwayMerge(ror).uniq.| less | Predicate the given ranges are sorted by. |
RangeOfRangesror | A range of ranges sorted byless to compute the intersection for. |
ror.See also:multiwayMergeimport std.algorithm.comparison : equal;// setsdouble[][] a =[ [ 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 8], [ 4 ], [ 7 ],];auto witness = [1, 4, 7, 8];assert(equal(multiwayUnion(a), witness));// multisetsdouble[][] b =[ [ 1, 1, 1, 4, 7, 8 ], [ 1, 7 ], [ 1, 7, 7, 8], [ 4 ], [ 7 ],];assert(equal(multiwayUnion(b), witness));double[][] c =[ [9, 8, 8, 8, 7, 6], [9, 8, 6], [9, 8, 5]];auto witness2 = [9, 8, 7, 6, 5];assert(equal(multiwayUnion!"a > b"(c), witness2));
SetDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);setDifference(alias less = "a < b", R1, R2)(R1r1, R2r2);r1 andr2. The two rangesare assumed to be sorted byless. The element types of the tworanges must have a common type.r1 andy times andr2, the number of occurencesofa in the resulting range is going to bex-y if x > y or 0 otherwise.| less | Predicate the given ranges are sorted by. |
R1r1 | The first range. |
R2r2 | The range to subtract fromr1. |
r1 andr2.import std.algorithm.comparison : equal;import std.range.primitives : isForwardRange;//setsint[] a = [ 1, 2, 4, 5, 7, 9 ];int[] b = [ 0, 1, 2, 4, 7, 8 ];assert(equal(setDifference(a, b), [5, 9]));staticassert(isForwardRange!(typeof(setDifference(a, b))));// multisetsint[] x = [1, 1, 1, 2, 3];int[] y = [1, 1, 2, 4, 5];auto r =setDifference(x, y);assert(equal(r, [1, 3]));assert(setDifference(r, x).empty);
r1, R2r2);popFront();front();save();empty();SetIntersection(alias less = "a < b", Rs...) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void));setIntersection(alias less = "a < b", Rs...)(Rsranges)ranges. The ranges are assumed to be sorted byless. The elementtypes of the ranges must have a common type.| less | Predicate the given ranges are sorted by. |
Rsranges | The ranges to compute the intersection for. |
import std.algorithm.comparison : equal;// setsint[] 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]));// multisetsint[] d = [ 1, 1, 2, 2, 7, 7 ];int[] e = [ 1, 1, 1, 7];assert(equal(setIntersection(a, d), [1, 2, 7]));assert(equal(setIntersection(d, e), [1, 1, 7]));
input);empty();popFront();front();save();SetSymmetricDifference(alias less = "a < b", R1, R2) if (isInputRange!R1 && isInputRange!R2);setSymmetricDifference(alias less = "a < b", R1, R2)(R1r1, R2r2);r1 andr2,i.e. the elements that are present in exactly one ofr1 andr2. The two ranges are assumed to be sorted byless, and theoutput is also sorted byless. The element types of the tworanges must have a common type.r1,b is the number ofoccurences ofx inr2, andabs is the absolute value.If both arguments are ranges of L-values of the same type thenSetSymmetricDifference will also be a range of L-values ofthat type.| less | Predicate the given ranges are sorted by. |
R1r1 | The first range. |
R2r2 | The second range. |
r1 andr2.import std.algorithm.comparison : equal;import std.range.primitives : isForwardRange;// setsint[] a = [ 1, 2, 4, 5, 7, 9 ];int[] b = [ 0, 1, 2, 4, 7, 8 ];assert(equal(setSymmetricDifference(a, b), [0, 5, 8, 9][]));staticassert(isForwardRange!(typeof(setSymmetricDifference(a, b))));//mutisetsint[] c = [1, 1, 1, 1, 2, 2, 2, 4, 5, 6];int[] d = [1, 1, 2, 2, 2, 2, 4, 7, 9];assert(equal(setSymmetricDifference(c, d),setSymmetricDifference(d, c)));assert(equal(setSymmetricDifference(c, d), [1, 1, 2, 5, 6, 7, 9]));
r1, R2r2);popFront();front();save();opSlice();empty();