If you spot a problem with this page, click here to create a Bugzilla issue.

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 a local clone.

std.algorithm.setops

This is a submodule of std.algorithm. It contains generic algorithms that implement set operations.

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

License:

Boost License 1.0.

Authors:

Andrei Alexandrescu

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.

Parameters:

R1 range1	The first range
R2 range2	The second range
RR ranges	Two or more non-infinite forward ranges
RR otherRanges	Zero or more non-infinite forward ranges

Returns:

A forward range of std.typecons.Tuple representing elements of the cartesian product of the given 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.

Parameters:

less	The predicate the ranges are sorted by.
RangeOfRanges ror	A range of forward ranges sorted by less.
Range tgt	The target range to copy common elements to.
SortOutput sorted	Whether the elements copied should be in sorted order. 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).

Examples:

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 duplicate
largestPartialIntersection(a.dup, b);
// First member is the item, second is the occurrence count
assert(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 range
auto c = new Tuple!(double, uint)[2];
largestPartialIntersection(a, c);
assert(c[0] == tuple(1.0, 3u));
// 1.0 occurs in 3 inputs

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.

Parameters:

less	The predicate the ranges are sorted by.
RangeOfRanges ror	A range of forward ranges sorted by less.
Range tgt	The target range to copy common elements to.
WeightsAA weights	An associative array mapping elements to weights.
SortOutput sorted	Whether the elements copied should be in sorted order.

Examples:

import std.typecons : tuple, Tuple;

// 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));
// 4.0 occurs 2 times -> 4.6 (2 * 2.3)
// 7.0 occurs 3 times -> 4.4 (3 * 1.1)

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.

Parameters:

less	Predicate the given ranges are sorted by.
RangeOfRanges 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 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.

Parameters:

less	Predicate the given ranges are sorted by.
R1 r1	The first range.
R2 r2	The range to subtract from r1.

Returns:

A range of the difference of r1 and r2.

less	Predicate the given ranges are sorted by.
Rs ranges	The ranges to compute the intersection for.

less	Predicate the given ranges are sorted by.
Rs rs	The ranges to compute the union for.

Library Reference

std.algorithm.setops