// Written in the D programming language./**This is a submodule of $(MREF std, algorithm).It contains generic _sorting algorithms. $(SCRIPT inhibitQuickIndex = 1;)$(BOOKTABLE Cheat Sheet,$(TR $(TH Function Name) $(TH Description))$(T2 completeSort,        If $(D a = [10, 20, 30]) and $(D b = [40, 6, 15]), then        $(D completeSort(a, b)) leaves $(D a = [6, 10, 15]) and $(D b = [20,        30, 40]).        The range $(D a) must be sorted prior to the call, and as a result the        combination $(D $(REF chain, std,range)(a, b)) is sorted.)$(T2 isPartitioned,        $(D isPartitioned!"a < 0"([-1, -2, 1, 0, 2])) returns $(D true) because        the predicate is $(D true) for a portion of the range and $(D false)        afterwards.)$(T2 isSorted,        $(D isSorted([1, 1, 2, 3])) returns $(D true).)$(T2 isStrictlyMonotonic,        $(D isStrictlyMonotonic([1, 1, 2, 3])) returns $(D false).)$(T2 ordered,        $(D ordered(1, 1, 2, 3)) returns $(D true).)$(T2 strictlyOrdered,        $(D strictlyOrdered(1, 1, 2, 3)) returns $(D false).)$(T2 makeIndex,        Creates a separate index for a range.)$(T2 merge,        Lazily merges two or more sorted ranges.)$(T2 multiSort,        Sorts by multiple keys.)$(T2 nextEvenPermutation,        Computes the next lexicographically greater even permutation of a range        in-place.)$(T2 nextPermutation,        Computes the next lexicographically greater permutation of a range        in-place.)$(T2 partialSort,        If $(D a = [5, 4, 3, 2, 1]), then $(D partialSort(a, 3)) leaves        $(D a[0 .. 3] = [1, 2, 3]).        The other elements of $(D a) are left in an unspecified order.)$(T2 partition,        Partitions a range according to a unary predicate.)$(T2 partition3,        Partitions a range according to a binary predicate in three parts (less        than, equal, greater than the given pivot). Pivot is not given as an        index, but instead as an element independent from the range's content.)$(T2 pivotPartition,        Partitions a range according to a binary predicate in two parts: less        than or equal, and greater than or equal to the given pivot, passed as        an index in the range.)$(T2 schwartzSort,        Sorts with the help of the $(LINK2 https://en.wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform).)$(T2 sort,        Sorts.)$(T2 topN,        Separates the top elements in a range.)$(T2 topNCopy,        Copies out the top elements of a range.)$(T2 topNIndex,        Builds an index of the top elements of a range.)) 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/_sorting.d) Macros:T2=$(TR $(TDNW $(LREF $1)) $(TD $+)) */module std.algorithm.sorting; import std.algorithm.mutation : SwapStrategy;import std.functional; // : unaryFun, binaryFun;import std.range.primitives;import std.typecons : Flag;// FIXMEimport std.meta; // : allSatisfy;import std.range; // : SortedRange;import std.traits; /**Specifies whether the output of certain algorithm is desired in sortedformat. If set to $(D SortOutput.no), the output should not be sorted. Otherwise if set to $(D SortOutput.yes), the output should be sorted. */alias SortOutput = Flag!"sortOutput"; // completeSort/**Sorts the random-access range $(D chain(lhs, rhs)) according topredicate $(D less). The left-hand side of the range $(D lhs) isassumed to be already sorted; $(D rhs) is assumed to be unsorted. Theexact strategy chosen depends on the relative sizes of $(D lhs) and$(D rhs).  Performs $(BIGOH lhs.length + rhs.length * log(rhs.length))(best case) to $(BIGOH (lhs.length + rhs.length) * log(lhs.length +rhs.length)) (worst-case) evaluations of $(D swap). Params:    less = The predicate to sort by.    ss = The swapping strategy to use.    lhs = The sorted, left-hand side of the random access range to be sorted.    rhs = The unsorted, right-hand side of the random access range to be        sorted.*/void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,        RandomAccessRange1, RandomAccessRange2)(SortedRange!(RandomAccessRange1, less) lhs, RandomAccessRange2 rhs)if (hasLength!(RandomAccessRange2) && hasSlicing!(RandomAccessRange2)){    import std.algorithm.mutation : bringToFront;    import std.range : chain, assumeSorted;    // Probably this algorithm can be optimized by using in-place    // merge    auto lhsOriginal = lhs.release();    foreach (i; 0 .. rhs.length)    {        auto sortedSoFar = chain(lhsOriginal, rhs[0 .. i]);        auto ub = assumeSorted!less(sortedSoFar).upperBound(rhs[i]);        if (!ub.length) continue;        bringToFront(ub.release(), rhs[i .. i + 1]);    }} ///@safe unittest{    import std.range : assumeSorted;    int[] a = [ 1, 2, 3 ];    int[] b = [ 4, 0, 6, 5 ];    completeSort(assumeSorted(a), b);    assert(a == [ 0, 1, 2 ]);    assert(b == [ 3, 4, 5, 6 ]);} // isSorted/**Checks whether a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)is sorted according to the comparison operation $(D less). Performs $(BIGOH r.length)evaluations of $(D less). Unlike `isSorted`, `isStrictlyMonotonic` does not allow for equal values,i.e. values for which both `less(a, b)` and `less(b, a)` are false. With either function, the predicate must be a strict ordering just like with`isSorted`. For example, using `"a <= b"` instead of `"a < b"` isincorrect and will cause failed assertions. Params:    less = Predicate the range should be sorted by.    r = Forward range to check for sortedness. Returns:    `true` if the range is sorted, false otherwise. `isSorted` allows    duplicates, `isStrictlyMonotonic` not.*/bool isSorted(alias less = "a < b", Range)(Range r)if (isForwardRange!(Range)){    if (r.empty) return true;     static if (isRandomAccessRange!Range && hasLength!Range)    {        immutable limit = r.length - 1;        foreach (i; 0 .. limit)        {            if (!binaryFun!less(r[i + 1], r[i])) continue;            assert(                !binaryFun!less(r[i], r[i + 1]),                "Predicate for isSorted is not antisymmetric. Both" ~                        " pred(a, b) and pred(b, a) are true for certain values.");            return false;        }    }    else    {        auto ahead = r.save;        ahead.popFront();        size_t i;         for (; !ahead.empty; ahead.popFront(), r.popFront(), ++i)        {            if (!binaryFun!less(ahead.front, r.front)) continue;            // Check for antisymmetric predicate            assert(                !binaryFun!less(r.front, ahead.front),                "Predicate for isSorted is not antisymmetric. Both" ~                        " pred(a, b) and pred(b, a) are true for certain values.");            return false;        }    }    return true;} ///@safe unittest{    assert([1, 1, 2].isSorted);    // strictly monotonic doesn't allow duplicates    assert(![1, 1, 2].isStrictlyMonotonic);     int[] arr = [4, 3, 2, 1];    assert(!isSorted(arr));    assert(!isStrictlyMonotonic(arr));     assert(isSorted!"a > b"(arr));    assert(isStrictlyMonotonic!"a > b"(arr));     sort(arr);    assert(isSorted(arr));    assert(isStrictlyMonotonic(arr));} @safe unittest{    import std.conv : to;     // Issue 9457    auto x = "abcd";    assert(isSorted(x));    auto y = "acbd";    assert(!isSorted(y));     int[] a = [1, 2, 3];    assert(isSorted(a));    int[] b = [1, 3, 2];    assert(!isSorted(b));     // ignores duplicates    int[] c = [1, 1, 2];    assert(isSorted(c));     dchar[] ds = "コーヒーが好きです"d.dup;    sort(ds);    string s = to!string(ds);    assert(isSorted(ds));  // random-access    assert(isSorted(s));   // bidirectional} @nogc @safe nothrow pure unittest{    static immutable a = [1, 2, 3];    assert(a.isSorted);} /// dittobool isStrictlyMonotonic(alias less = "a < b", Range)(Range r)if (isForwardRange!Range){    import std.algorithm.searching : findAdjacent;    return findAdjacent!((a,b) => !binaryFun!less(a,b))(r).empty;} @safe unittest{    import std.conv : to;     assert("abcd".isStrictlyMonotonic);    assert(!"aacd".isStrictlyMonotonic);    assert(!"acb".isStrictlyMonotonic);     assert([1, 2, 3].isStrictlyMonotonic);    assert(![1, 3, 2].isStrictlyMonotonic);    assert(![1, 1, 2].isStrictlyMonotonic);     // ー occurs twice -> can't be strict    dchar[] ds = "コーヒーが好きです"d.dup;    sort(ds);    string s = to!string(ds);    assert(!isStrictlyMonotonic(ds));  // random-access    assert(!isStrictlyMonotonic(s));   // bidirectional     dchar[] ds2 = "コーヒが好きです"d.dup;    sort(ds2);    string s2 = to!string(ds2);    assert(isStrictlyMonotonic(ds2));  // random-access    assert(isStrictlyMonotonic(s2));   // bidirectional} @nogc @safe nothrow pure unittest{    static immutable a = [1, 2, 3];    assert(a.isStrictlyMonotonic);} /**Like $(D isSorted), returns $(D true) if the given $(D values) are orderedaccording to the comparison operation $(D less). Unlike $(D isSorted), takes valuesdirectly instead of structured in a range. $(D ordered) allows repeated values, e.g. $(D ordered(1, 1, 2)) is $(D true). To verifythat the values are ordered strictly monotonically, use $(D strictlyOrdered);$(D strictlyOrdered(1, 1, 2)) is $(D false). With either function, the predicate must be a strict ordering. For example,using $(D "a <= b") instead of $(D "a < b") is incorrect and will cause failedassertions. Params:    values = The tested value    less = The comparison predicate Returns:    $(D true) if the values are ordered; $(D ordered) allows for duplicates,    $(D strictlyOrdered) does not.*/ bool ordered(alias less = "a < b", T...)(T values)if ((T.length == 2 && is(typeof(binaryFun!less(values[1], values[0])) : bool))    ||    (T.length > 2 && is(typeof(ordered!less(values[0 .. 1 + $ / 2])))        && is(typeof(ordered!less(values[$ / 2 .. $]))))    ){    foreach (i, _; T[0 .. $ - 1])    {        if (binaryFun!less(values[i + 1], values[i]))        {            assert(!binaryFun!less(values[i], values[i + 1]),                __FUNCTION__ ~ ": incorrect non-strict predicate.");            return false;        }    }    return true;} /// dittobool strictlyOrdered(alias less = "a < b", T...)(T values)if (is(typeof(ordered!less(values)))){    foreach (i, _; T[0 .. $ - 1])    {        if (!binaryFun!less(values[i], values[i + 1]))        {            return false;        }        assert(!binaryFun!less(values[i + 1], values[i]),            __FUNCTION__ ~ ": incorrect non-strict predicate.");    }    return true;} ///@safe unittest{    assert(ordered(42, 42, 43));    assert(!strictlyOrdered(43, 42, 45));    assert(ordered(42, 42, 43));    assert(!strictlyOrdered(42, 42, 43));    assert(!ordered(43, 42, 45));    // Ordered lexicographically    assert(ordered("Jane", "Jim", "Joe"));    assert(strictlyOrdered("Jane", "Jim", "Joe"));    // Incidentally also ordered by length decreasing    assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));    // ... but not strictly so: "Jim" and "Joe" have the same length    assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));} // partition/**Partitions a range in two using the given $(D predicate).Specifically, reorders the range $(D r = [left, right$(RPAREN)) using $(D swap)such that all elements $(D i) for which $(D predicate(i)) is $(D true) comebefore all elements $(D j) for which $(D predicate(j)) returns $(D false). Performs $(BIGOH r.length) (if unstable or semistable) or $(BIGOHr.length * log(r.length)) (if stable) evaluations of $(D less) and $(Dswap). The unstable version computes the minimum possible evaluationsof $(D swap) (roughly half of those performed by the semistableversion). Params:    predicate = The predicate to partition by.    ss = The swapping strategy to employ.    r = The random-access range to partition. Returns: The right part of $(D r) after partitioning. If $(D ss == SwapStrategy.stable), $(D partition) preserves the relativeordering of all elements $(D a), $(D b) in $(D r) for which $(D predicate(a) ==predicate(b)). If $(D ss == SwapStrategy.semistable), $(D partition) preservesthe relative ordering of all elements $(D a), $(D b) in the left part of $(D r)for which $(D predicate(a) == predicate(b)). See_Also:    STL's $(HTTP sgi.com/tech/stl/_partition.html, _partition)$(BR)    STL's $(HTTP sgi.com/tech/stl/stable_partition.html, stable_partition)*/Range partition(alias predicate, SwapStrategy ss, Range)(Range r)if (ss == SwapStrategy.stable && isRandomAccessRange!(Range) && hasLength!Range && hasSlicing!Range){    import std.algorithm.mutation : bringToFront;     alias pred = unaryFun!(predicate);    if (r.empty) return r;     if (r.length == 1)    {        if (pred(r.front)) r.popFront();        return r;    }    const middle = r.length / 2;    alias recurse = .partition!(pred, ss, Range);    auto lower = recurse(r[0 .. middle]);    auto upper = recurse(r[middle .. r.length]);    bringToFront(lower, r[middle .. r.length - upper.length]);    return r[r.length - lower.length - upper.length .. r.length];} ///dittoRange partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range){    import std.algorithm.mutation : swap;    alias pred = unaryFun!(predicate);     static if (ss == SwapStrategy.semistable)    {        if (r.empty) return r;         for (; !r.empty; r.popFront())        {            // skip the initial portion of "correct" elements            if (pred(r.front)) continue;            // hit the first "bad" element            auto result = r;            for (r.popFront(); !r.empty; r.popFront())            {                if (!pred(r.front)) continue;                swap(result.front, r.front);                result.popFront();            }            return result;        }         return r;    }    else    {        // Inspired from www.stepanovpapers.com/PAM3-partition_notes.pdf,        // section "Bidirectional Partition Algorithm (Hoare)"        static if (isDynamicArray!Range)        {            import std.algorithm.mutation : swapAt;            // For dynamic arrays prefer index-based manipulation            if (!r.length) return r;            size_t lo = 0, hi = r.length - 1;            for (;;)            {                for (;;)                {                    if (lo > hi) return r[lo .. r.length];                    if (!pred(r[lo])) break;                    ++lo;                }                // found the left bound                assert(lo <= hi);                for (;;)                {                    if (lo == hi) return r[lo .. r.length];                    if (pred(r[hi])) break;                    --hi;                }                // found the right bound, swap & make progress                r.swapAt(lo++, hi--);            }        }        else        {            import std.algorithm.mutation : swap;            auto result = r;            for (;;)            {                for (;;)                {                    if (r.empty) return result;                    if (!pred(r.front)) break;                    r.popFront();                    result.popFront();                }                // found the left bound                assert(!r.empty);                for (;;)                {                    if (pred(r.back)) break;                    r.popBack();                    if (r.empty) return result;                }                // found the right bound, swap & make progress                static if (is(typeof(swap(r.front, r.back))))

Lines 1–500 of 4468. Load more