// Written in the D programming language./**This is a submodule of $(MREF std, algorithm).It contains generic mutation algorithms. $(SCRIPT inhibitQuickIndex = 1;)$(BOOKTABLE Cheat Sheet,$(TR $(TH Function Name) $(TH Description))$(T2 bringToFront,        If `a = [1, 2, 3]` and `b = [4, 5, 6, 7]`,        `bringToFront(a, b)` leaves `a = [4, 5, 6]` and        `b = [7, 1, 2, 3]`.)$(T2 copy,        Copies a range to another. If        `a = [1, 2, 3]` and `b = new int[5]`, then `copy(a, b)`        leaves `b = [1, 2, 3, 0, 0]` and returns `b[3 .. $]`.)$(T2 fill,        Fills a range with a pattern,        e.g., if `a = new int[3]`, then `fill(a, 4)`        leaves `a = [4, 4, 4]` and `fill(a, [3, 4])` leaves        `a = [3, 4, 3]`.)$(T2 initializeAll,        If `a = [1.2, 3.4]`, then `initializeAll(a)` leaves        `a = [double.init, double.init]`.)$(T2 move,        `move(a, b)` moves `a` into `b`. `move(a)` reads `a`        destructively when necessary.)$(T2 moveEmplace,        Similar to `move` but assumes `target` is uninitialized.)$(T2 moveAll,        Moves all elements from one range to another.)$(T2 moveEmplaceAll,        Similar to `moveAll` but assumes all elements in `target` are uninitialized.)$(T2 moveSome,        Moves as many elements as possible from one range to another.)$(T2 moveEmplaceSome,        Similar to `moveSome` but assumes all elements in `target` are uninitialized.)$(T2 remove,        Removes elements from a range in-place, and returns the shortened        range.)$(T2 reverse,        If `a = [1, 2, 3]`, `reverse(a)` changes it to `[3, 2, 1]`.)$(T2 strip,        Strips all leading and trailing elements equal to a value, or that        satisfy a predicate.        If `a = [1, 1, 0, 1, 1]`, then `strip(a, 1)` and        `strip!(e => e == 1)(a)` returns `[0]`.)$(T2 stripLeft,        Strips all leading elements equal to a value, or that satisfy a        predicate.  If `a = [1, 1, 0, 1, 1]`, then `stripLeft(a, 1)` and        `stripLeft!(e => e == 1)(a)` returns `[0, 1, 1]`.)$(T2 stripRight,        Strips all trailing elements equal to a value, or that satisfy a        predicate.        If `a = [1, 1, 0, 1, 1]`, then `stripRight(a, 1)` and        `stripRight!(e => e == 1)(a)` returns `[1, 1, 0]`.)$(T2 swap,        Swaps two values.)$(T2 swapAt,        Swaps two values by indices.)$(T2 swapRanges,        Swaps all elements of two ranges.)$(T2 uninitializedFill,        Fills a range (assumed uninitialized) with a value.)) 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/mutation.d) Macros:T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) */module std.algorithm.mutation; import std.range.primitives;import std.traits : isArray, isAssignable, isBlitAssignable, isNarrowString,       Unqual, isSomeChar, isMutable;import std.meta : allSatisfy;import std.typecons : tuple, Tuple; // bringToFront/**`bringToFront` takes two ranges `front` and `back`, which maybe of different types. Considering the concatenation of `front` and`back` one unified range, `bringToFront` rotates that unifiedrange such that all elements in `back` are brought to the beginningof the unified range. The relative ordering of elements in `front`and `back`, respectively, remains unchanged. The `bringToFront` function treats strings at the code unitlevel and it is not concerned with Unicode character integrity.`bringToFront` is designed as a function for moving elementsin ranges, not as a string function. Performs $(BIGOH max(front.length, back.length)) evaluations of $(Dswap). The `bringToFront` function can rotate elements in one buffer left or right, swapbuffers of equal length, and even move elements across disjointbuffers of different types and different lengths. Preconditions: Either `front` and `back` are disjoint, or `back` isreachable from `front` and `front` is not reachable from $(Dback). Params:    front = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)    back = a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) Returns:    The number of elements brought to the front, i.e., the length of `back`. See_Also:    $(LINK2 http://en.cppreference.com/w/cpp/algorithm/rotate, STL's `rotate`)*/size_t bringToFront(InputRange, ForwardRange)(InputRange front, ForwardRange back)if (isInputRange!InputRange && isForwardRange!ForwardRange){    import std.string : representation;     static if (isNarrowString!InputRange)    {        auto frontW = representation(front);    }    else    {        alias frontW = front;    }    static if (isNarrowString!ForwardRange)    {        auto backW = representation(back);    }    else    {        alias backW = back;    }     return bringToFrontImpl(frontW, backW);} /**The simplest use of `bringToFront` is for rotating elements in abuffer. For example:*/@safe unittest{    auto arr = [4, 5, 6, 7, 1, 2, 3];    auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);    assert(p == arr.length - 4);    assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);} /**The `front` range may actually "step over" the `back`range. This is very useful with forward ranges that cannot computecomfortably right-bounded subranges like `arr[0 .. 4]` above. Inthe example below, `r2` is a right subrange of `r1`.*/@safe unittest{    import std.algorithm.comparison : equal;    import std.container : SList;    import std.range.primitives : popFrontN;     auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);    auto r1 = list[];    auto r2 = list[]; popFrontN(r2, 4);    assert(equal(r2, [ 1, 2, 3 ]));    bringToFront(r1, r2);    assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));} /**Elements can be swapped across ranges of different types:*/@safe unittest{    import std.algorithm.comparison : equal;    import std.container : SList;     auto list = SList!(int)(4, 5, 6, 7);    auto vec = [ 1, 2, 3 ];    bringToFront(list[], vec);    assert(equal(list[], [ 1, 2, 3, 4 ]));    assert(equal(vec, [ 5, 6, 7 ]));} /**Unicode integrity is not preserved:*/@safe unittest{    import std.string : representation;    auto ar = representation("a".dup);    auto br = representation("ç".dup);     bringToFront(ar, br);     auto a = cast(char[]) ar;    auto b = cast(char[]) br;     // Illegal UTF-8    assert(a == "\303");    // Illegal UTF-8    assert(b == "\247a");} private size_t bringToFrontImpl(InputRange, ForwardRange)(InputRange front, ForwardRange back)if (isInputRange!InputRange && isForwardRange!ForwardRange){    import std.array : sameHead;    import std.range : take, Take;    enum bool sameHeadExists = is(typeof(front.sameHead(back)));    size_t result;     for (bool semidone; !front.empty && !back.empty; )    {        static if (sameHeadExists)        {            if (front.sameHead(back)) break; // shortcut        }        // Swap elements until front and/or back ends.        auto back0 = back.save;        size_t nswaps;        do        {            static if (sameHeadExists)            {                // Detect the stepping-over condition.                if (front.sameHead(back0)) back0 = back.save;            }            swapFront(front, back);            ++nswaps;            front.popFront();            back.popFront();        }        while (!front.empty && !back.empty);         if (!semidone) result += nswaps;         // Now deal with the remaining elements.        if (back.empty)        {            if (front.empty) break;            // Right side was shorter, which means that we've brought            // all the back elements to the front.            semidone = true;            // Next pass: bringToFront(front, back0) to adjust the rest.            back = back0;        }        else        {            assert(front.empty, "Expected front to be empty");            // Left side was shorter. Let's step into the back.            static if (is(InputRange == Take!ForwardRange))            {                front = take(back0, nswaps);            }            else            {                immutable subresult = bringToFront(take(back0, nswaps),                                                   back);                if (!semidone) result += subresult;                break; // done            }        }    }    return result;} @safe unittest{    import std.algorithm.comparison : equal;    import std.conv : text;    import std.random : Random = Xorshift, uniform;     // a more elaborate test    {        auto rnd = Random(123_456_789);        int[] a = new int[uniform(100, 200, rnd)];        int[] b = new int[uniform(100, 200, rnd)];        foreach (ref e; a) e = uniform(-100, 100, rnd);        foreach (ref e; b) e = uniform(-100, 100, rnd);        int[] c = a ~ b;        // writeln("a= ", a);        // writeln("b= ", b);        auto n = bringToFront(c[0 .. a.length], c[a.length .. $]);        //writeln("c= ", c);        assert(n == b.length);        assert(c == b ~ a, text(c, "\n", a, "\n", b));    }    // different types, moveFront, no sameHead    {        static struct R(T)        {            T[] data;            size_t i;            @property            {                R save() { return this; }                bool empty() { return i >= data.length; }                T front() { return data[i]; }                T front(real e) { return data[i] = cast(T) e; }            }            void popFront() { ++i; }        }        auto a = R!int([1, 2, 3, 4, 5]);        auto b = R!real([6, 7, 8, 9]);        auto n = bringToFront(a, b);        assert(n == 4);        assert(a.data == [6, 7, 8, 9, 1]);        assert(b.data == [2, 3, 4, 5]);    }    // front steps over back    {        int[] arr, r1, r2;         // back is shorter        arr = [4, 5, 6, 7, 1, 2, 3];        r1 = arr;        r2 = arr[4 .. $];        bringToFront(r1, r2) == 3 || assert(0);        assert(equal(arr, [1, 2, 3, 4, 5, 6, 7]));         // front is shorter        arr = [5, 6, 7, 1, 2, 3, 4];        r1 = arr;        r2 = arr[3 .. $];        bringToFront(r1, r2) == 4 || assert(0);        assert(equal(arr, [1, 2, 3, 4, 5, 6, 7]));    }     // https://issues.dlang.org/show_bug.cgi?id=16959    auto arr = ['4', '5', '6', '7', '1', '2', '3'];    auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);     assert(p == arr.length - 4);    assert(arr == ['1', '2', '3', '4', '5', '6', '7']);} // Tests if types are arrays and support slice assign.private enum bool areCopyCompatibleArrays(T1, T2) =    isArray!T1 && isArray!T2 && is(typeof(T2.init[] = T1.init[])); // copy/**Copies the content of `source` into `target` and returns theremaining (unfilled) part of `target`. Preconditions: `target` shall have enough room to accommodatethe entirety of `source`. Params:    source = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)    target = an output range Returns:    The unfilled part of target */TargetRange copy(SourceRange, TargetRange)(SourceRange source, TargetRange target)if (isInputRange!SourceRange && isOutputRange!(TargetRange, ElementType!SourceRange)){    static if (areCopyCompatibleArrays!(SourceRange, TargetRange))    {        const tlen = target.length;        const slen = source.length;        assert(tlen >= slen,                "Cannot copy a source range into a smaller target range.");         immutable overlaps = () @trusted {            return source.ptr < target.ptr + tlen &&                target.ptr < source.ptr + slen; }();         if (overlaps)        {            if (source.ptr < target.ptr)            {                foreach_reverse (idx; 0 .. slen)                    target[idx] = source[idx];            }            else            {                foreach (idx; 0 .. slen)                    target[idx] = source[idx];            }            return target[slen .. tlen];        }        else        {            // Array specialization.  This uses optimized memory copying            // routines under the hood and is about 10-20x faster than the            // generic implementation.            target[0 .. slen] = source[];            return target[slen .. $];        }    }    else    {        // Specialize for 2 random access ranges.        // Typically 2 random access ranges are faster iterated by common        // index than by x.popFront(), y.popFront() pair        static if (isRandomAccessRange!SourceRange &&                hasLength!SourceRange &&                hasSlicing!TargetRange &&                isRandomAccessRange!TargetRange &&                hasLength!TargetRange)        {            auto len = source.length;            foreach (idx; 0 .. len)                target[idx] = source[idx];            return target[len .. target.length];        }        else        {            foreach (element; source)                put(target, element);            return target;        }    }} ///@safe unittest{    int[] a = [ 1, 5 ];    int[] b = [ 9, 8 ];    int[] buf = new int[](a.length + b.length + 10);    auto rem = a.copy(buf);    // copy a into buf    rem = b.copy(rem);         // copy b into remainder of buf    assert(buf[0 .. a.length + b.length] == [1, 5, 9, 8]);    assert(rem.length == 10);   // unused slots in buf} /**As long as the target range elements support assignment from sourcerange elements, different types of ranges are accepted:*/@safe unittest{    float[] src = [ 1.0f, 5 ];    double[] dest = new double[src.length];    src.copy(dest);} /**To _copy at most `n` elements from a range, you may want to use$(REF take, std,range):*/@safe unittest{    import std.range;    int[] src = [ 1, 5, 8, 9, 10 ];    auto dest = new int[](3);    src.take(dest.length).copy(dest);    assert(dest == [ 1, 5, 8 ]);} /**To _copy just those elements from a range that satisfy a predicate,use $(LREF filter):*/@safe unittest{    import std.algorithm.iteration : filter;    int[] src = [ 1, 5, 8, 9, 10, 1, 2, 0 ];    auto dest = new int[src.length];    auto rem = src        .filter!(a => (a & 1) == 1)        .copy(dest);    assert(dest[0 .. $ - rem.length] == [ 1, 5, 9, 1 ]);} /**$(REF retro, std,range) can be used to achieve behavior similar to$(LINK2 http://en.cppreference.com/w/cpp/algorithm/copy_backward, STL's `copy_backward`'):*/@safe unittest{    import std.algorithm, std.range;    int[] src = [1, 2, 4];    int[] dest = [0, 0, 0, 0, 0];    src.retro.copy(dest.retro);    assert(dest == [0, 0, 1, 2, 4]);} // Test CTFE copy.@safe unittest{    enum c = copy([1,2,3], [4,5,6,7]);    assert(c == [7]);}  

Lines 1–500 of 3367. Load more