// Written in the D programming language./**This is a submodule of $(MREF std, algorithm).It contains generic algorithms that implement set operations. The functions $(LREF multiwayMerge), $(LREF multiwayUnion), $(LREF setDifference),$(LREF setIntersection), $(LREF setSymmetricDifference) expect a range of sortedranges as input. All algorithms are generalized to accept as input not only sets but also$(LINK2 https://en.wikipedia.org/wiki/Multiset, multisets). Each algorithmdocuments behaviour in the presence of duplicated inputs. $(SCRIPT inhibitQuickIndex = 1;)$(BOOKTABLE Cheat Sheet,$(TR $(TH Function Name) $(TH Description))$(T2 cartesianProduct,        Computes Cartesian product of two ranges.)$(T2 largestPartialIntersection,        Copies out the values that occur most frequently in a range of ranges.)$(T2 largestPartialIntersectionWeighted,        Copies out the values that occur most frequently (multiplied by        per-value weights) in a range of ranges.)$(T2 multiwayMerge,        Merges a range of sorted ranges.)$(T2 multiwayUnion,        Computes the union of a range of sorted ranges.)$(T2 setDifference,        Lazily computes the set difference of two sorted ranges.)$(T2 setIntersection,        Lazily computes the intersection of two or more sorted ranges.)$(T2 setSymmetricDifference,        Lazily computes the symmetric set difference of two sorted ranges.)) Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). Authors: $(HTTP erdani.com, Andrei Alexandrescu) Source: $(PHOBOSSRC std/algorithm/setops.d) Macros:T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) */module std.algorithm.setops; import std.range.primitives; import std.functional : unaryFun, binaryFun;import std.traits;import std.meta : AliasSeq, staticMap, allSatisfy, anySatisfy; import std.algorithm.sorting : Merge;import std.typecons : No; // cartesianProduct/**Lazily computes the Cartesian product of two or more ranges. The product is arange 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$(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and theother an $(REF_ALTTEXT input range, isInputRange, std,range,primitives). If one range is infinite and the other finite, then the finite range mustbe 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 eachadjacent pair of ranges. Params:    range1 = The first range    range2 = The second range    ranges = Two or more non-infinite forward ranges    otherRanges = Zero or more non-infinite forward ranges Returns:    A forward range of $(REF Tuple, std,typecons) representing elements of the    cartesian product of the given ranges.*/auto cartesianProduct(R1, R2)(R1 range1, R2 range2)if (!allSatisfy!(isForwardRange, R1, R2) ||    anySatisfy!(isInfinite, R1, R2)){    import std.algorithm.iteration : map, joiner;     static if (isInfinite!R1 && isInfinite!R2)    {        static if (isForwardRange!R1 && isForwardRange!R2)        {            import std.range : zip, repeat, take, chain, sequence;             // This algorithm traverses the cartesian product by alternately            // covering the right and bottom edges of an increasing square area            // over the infinite table of combinations. This schedule allows us            // to require only forward ranges.            return zip(sequence!"n"(cast(size_t) 0), range1.save, range2.save,                       repeat(range1), repeat(range2))                .map!(function(a) => chain(                    zip(repeat(a[1]), take(a[4].save, a[0])),                    zip(take(a[3].save, a[0]+1), repeat(a[2]))                ))()                .joiner();        }        else static assert(0, "cartesianProduct of infinite ranges requires "~                              "forward ranges");    }    else static if (isInputRange!R1 && isForwardRange!R2 && !isInfinite!R2)    {        import std.range : zip, repeat;        return joiner(map!((ElementType!R1 a) => zip(repeat(a), range2.save))                          (range1));    }    else static if (isInputRange!R2 && isForwardRange!R1 && !isInfinite!R1)    {        import std.range : zip, repeat;        return joiner(map!((ElementType!R2 a) => zip(range1.save, repeat(a)))                          (range2));    }    else static assert(0, "cartesianProduct involving finite ranges must "~                          "have at least one finite forward range");} ///@safe unittest{    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)));} ///@safe unittest{    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])));    }} @safe unittest{    // Test cartesian product of two infinite ranges    import std.algorithm.searching : canFind;    import std.range;    import std.typecons : tuple;     auto Even = sequence!"2*n"(0);    auto Odd = sequence!"2*n+1"(0);    auto EvenOdd = cartesianProduct(Even, Odd);     foreach (pair; [[0, 1], [2, 1], [0, 3], [2, 3], [4, 1], [4, 3], [0, 5],                    [2, 5], [4, 5], [6, 1], [6, 3], [6, 5]])    {        assert(canFind(EvenOdd, tuple(pair[0], pair[1])));    }     // This should terminate in finite time    assert(canFind(EvenOdd, tuple(124, 73)));    assert(canFind(EvenOdd, tuple(0, 97)));    assert(canFind(EvenOdd, tuple(42, 1)));} @safe unittest{    // Test cartesian product of an infinite input range and a finite forward    // range.    import std.algorithm.searching : canFind;    import std.range;    import std.typecons : tuple;     auto N = sequence!"n"(0);    auto M = [100, 200, 300];    auto NM = cartesianProduct(N,M);     foreach (pair; [[0, 100], [0, 200], [0, 300], [1, 100], [1, 200], [1, 300],                    [2, 100], [2, 200], [2, 300], [3, 100], [3, 200],                    [3, 300]])    {        assert(canFind(NM, tuple(pair[0], pair[1])));    }     // We can't solve the halting problem, so we can only check a finite    // initial segment here.    assert(!canFind(NM.take(100), tuple(100, 0)));    assert(!canFind(NM.take(100), tuple(1, 1)));    assert(!canFind(NM.take(100), tuple(100, 200)));     auto MN = cartesianProduct(M,N);    foreach (pair; [[100, 0], [200, 0], [300, 0], [100, 1], [200, 1], [300, 1],                    [100, 2], [200, 2], [300, 2], [100, 3], [200, 3],                    [300, 3]])    {        assert(canFind(MN, tuple(pair[0], pair[1])));    }     // We can't solve the halting problem, so we can only check a finite    // initial segment here.    assert(!canFind(MN.take(100), tuple(0, 100)));    assert(!canFind(MN.take(100), tuple(0, 1)));    assert(!canFind(MN.take(100), tuple(100, 200)));} @safe unittest{    import std.algorithm.searching : canFind;    import std.typecons : tuple;     // Test cartesian product of two finite ranges.    auto X = [1, 2, 3];    auto Y = [4, 5, 6];    auto XY = cartesianProduct(X, Y);    auto Expected = [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4],                     [3, 5], [3, 6]];     // Verify Expected ⊆ XY    foreach (pair; Expected)    {        assert(canFind(XY, tuple(pair[0], pair[1])));    }     // Verify XY ⊆ Expected    foreach (pair; XY)    {        assert(canFind(Expected, [pair[0], pair[1]]));    }     // And therefore, by set comprehension, XY == Expected} @safe unittest{    import std.algorithm.comparison : equal;    import std.algorithm.iteration : map;    import std.algorithm.searching : canFind;    import std.typecons : tuple;     import std.range;    auto N = sequence!"n"(0);     // To force the template to fall to the second case, we wrap N in a struct    // that doesn't allow bidirectional access.    struct FwdRangeWrapper(R)    {        R impl;         // Input range API        @property auto front() { return impl.front; }        void popFront() { impl.popFront(); }        static if (isInfinite!R)            enum empty = false;        else            @property bool empty() { return impl.empty; }         // Forward range API        @property auto save() { return typeof(this)(impl.save); }    }    auto fwdWrap(R)(R range) { return FwdRangeWrapper!R(range); }     // General test: two infinite bidirectional ranges    auto N2 = cartesianProduct(N, N);     assert(canFind(N2, tuple(0, 0)));    assert(canFind(N2, tuple(123, 321)));    assert(canFind(N2, tuple(11, 35)));    assert(canFind(N2, tuple(279, 172)));     // Test first case: forward range with bidirectional range    auto fwdN = fwdWrap(N);    auto N2_a = cartesianProduct(fwdN, N);     assert(canFind(N2_a, tuple(0, 0)));    assert(canFind(N2_a, tuple(123, 321)));    assert(canFind(N2_a, tuple(11, 35)));    assert(canFind(N2_a, tuple(279, 172)));     // Test second case: bidirectional range with forward range    auto N2_b = cartesianProduct(N, fwdN);     assert(canFind(N2_b, tuple(0, 0)));    assert(canFind(N2_b, tuple(123, 321)));    assert(canFind(N2_b, tuple(11, 35)));    assert(canFind(N2_b, tuple(279, 172)));     // Test third case: finite forward range with (infinite) input range    static struct InpRangeWrapper(R)    {        R impl;         // Input range API        @property auto front() { return impl.front; }        void popFront() { impl.popFront(); }        static if (isInfinite!R)            enum empty = false;        else            @property bool empty() { return impl.empty; }    }    auto inpWrap(R)(R r) { return InpRangeWrapper!R(r); }     auto inpN = inpWrap(N);    auto B = [ 1, 2, 3 ];    auto fwdB = fwdWrap(B);    auto BN = cartesianProduct(fwdB, inpN);     assert(equal(map!"[a[0],a[1]]"(BN.take(10)), [[1, 0], [2, 0], [3, 0],                 [1, 1], [2, 1], [3, 1], [1, 2], [2, 2], [3, 2], [1, 3]]));     // Test fourth case: (infinite) input range with finite forward range    auto NB = cartesianProduct(inpN, fwdB);     assert(equal(map!"[a[0],a[1]]"(NB.take(10)), [[0, 1], [0, 2], [0, 3],                 [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1]]));     // General finite range case    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])));    }} // https://issues.dlang.org/show_bug.cgi?id=13091pure nothrow @safe @nogc unittest{    int[1] a = [1];    foreach (t; cartesianProduct(a[], a[])) {}} /// dittoauto cartesianProduct(RR...)(RR ranges)if (ranges.length >= 2 &&    allSatisfy!(isForwardRange, RR) &&    !anySatisfy!(isInfinite, RR)){    // This overload uses a much less template-heavy implementation when    // all ranges are finite forward ranges, which is the most common use    // case, so that we don't run out of resources too quickly.    //    // For infinite ranges or non-forward ranges, we fall back to the old    // implementation which expands an exponential number of templates.    import std.typecons : tuple;    import std.meta : allSatisfy;    import std.range.primitives : hasLength;     static struct Result    {        RR ranges;        RR current;        bool empty = true;         this(RR _ranges)        {            ranges = _ranges;            empty = false;            foreach (i, r; ranges)            {                current[i] = r.save;                if (current[i].empty)                    empty = true;            }        }        @property auto front()        {            import std.algorithm.internal : algoFormat;            import std.range : iota;            return mixin(algoFormat("tuple(%(current[%d].front%|,%))",                                    iota(0, current.length)));        }        void popFront() scope        {            foreach_reverse (i, ref r; current)            {                r.popFront();                if (!r.empty) break;                 static if (i == 0)                    empty = true;                else                    r = ranges[i].save; // rollover            }        }        @property Result save() return scope        {            Result copy = this;            foreach (i, r; ranges)            {                copy.ranges[i] = ranges[i].save;                copy.current[i] = current[i].save;            }            return copy;        }        static if (allSatisfy!(hasLength, RR))        {            @property size_t length()            {                size_t result = 1;                foreach (r; ranges)                {                    result *= r.length;                }                return result;            }        }    }    static assert(isForwardRange!Result, Result.stringof ~ " must be a forward"            ~ " range");     return Result(ranges);}@safe unittest{    import std.algorithm.setops : cartesianProduct;     // 2 ranges    assert(cartesianProduct([1, 2], [3, 4]).length == 4);     // different sizes    assert(cartesianProduct([1, 2, 3], [4, 5]).length == 6);     // 3 ranges    assert(cartesianProduct([1, 2], [3, 4], [5]).length == 4);}// cartesian product of empty ranges should be empty// https://issues.dlang.org/show_bug.cgi?id=10693@safe unittest{    int[] a, b, c, d, e;    auto cprod = cartesianProduct(a,b,c,d,e);    assert(cprod.empty);    foreach (_; cprod) {} // should not crash     // Test case where only one of the ranges is empty: the result should still    // be empty.    int[] p=[1], q=[];    auto cprod2 = cartesianProduct(p,p,p,q,p);    assert(cprod2.empty);    foreach (_; cprod2) {} // should not crash} @safe unittest{    // .init value of cartesianProduct should be empty    auto cprod = cartesianProduct([0,0], [1,1], [2,2]);    assert(!cprod.empty);    assert(cprod.init.empty);} // https://issues.dlang.org/show_bug.cgi?id=13393@safe unittest{    assert(!cartesianProduct([0],[0],[0]).save.empty);} /// dittoauto cartesianProduct(R1, R2, RR...)(R1 range1, R2 range2, RR otherRanges)if (!allSatisfy!(isForwardRange, R1, R2, RR) ||    anySatisfy!(isInfinite, R1, R2, RR)){    /* We implement the n-ary cartesian product by recursively invoking the     * binary cartesian product. To make the resulting range nicer, we denest     * one level of tuples so that a ternary cartesian product, for example,     * returns 3-element tuples instead of nested 2-element tuples.     */    import std.algorithm.internal : algoFormat;    import std.algorithm.iteration : map;    import std.range : iota;     enum string denest = algoFormat("tuple(a[0], %(a[1][%d]%|,%))",                                iota(0, otherRanges.length+1));    return map!denest(        cartesianProduct(range1, cartesianProduct(range2, otherRanges))    );} 

Lines 1–500 of 1602. Load more