Google Git
Sign in
gnu / gcc / refs/tags/releases/gcc-11.2.0 / . / libphobos / src / std / algorithm / sorting.d
blob: 2400bca8bf7932dec91e988473f9901a3a684f08 [file] [log] [blame]
// 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;
// FIXME
import std.meta; // : allSatisfy;
import std.range; // : SortedRange;
import std.traits;
/**
Specifies whether the output of certain algorithm is desired in sorted
format.
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 to
predicate $(D less). The left-hand side of the range $(D lhs) is
assumed to be already sorted; $(D rhs) is assumed to be unsorted. The
exact 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"` is
incorrect 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);
}
/// ditto
bool 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 ordered
according to the comparison operation $(D less). Unlike $(D isSorted), takes values
directly instead of structured in a range.
$(D ordered) allows repeated values, e.g. $(D ordered(1, 1, 2)) is $(D true). To verify
that 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 failed
assertions.
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;
}
/// ditto
bool 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) come
before all elements $(D j) for which $(D predicate(j)) returns $(D false).
Performs $(BIGOH r.length) (if unstable or semistable) or $(BIGOH
r.length * log(r.length)) (if stable) evaluations of $(D less) and $(D
swap). The unstable version computes the minimum possible evaluations
of $(D swap) (roughly half of those performed by the semistable
version).
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 relative
ordering of all elements $(D a), $(D b) in $(D r) for which $(D predicate(a) ==
predicate(b)). If $(D ss == SwapStrategy.semistable), $(D partition) preserves
the 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];
}
///ditto
Range 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))))
{
swap(r.front, r.back);
}
else
{
auto t1 = r.moveFront(), t2 = r.moveBack();
r.front = t2;
r.back = t1;
}
r.popFront();
result.popFront();
r.popBack();
}
}
}
}
///
@safe unittest
{
import std.algorithm.mutation : SwapStrategy;
import std.algorithm.searching : count, find;
import std.conv : text;
import std.range.primitives : empty;
auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
// Partition arr such that even numbers come first
auto r = partition!(even)(arr);
// Now arr is separated in evens and odds.
// Numbers may have become shuffled due to instability
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);
// Can also specify the predicate as a string.
// Use 'a' as the predicate argument name
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);
// Now for a stable partition:
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
// Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);
// In case the predicate needs to hold its own state, use a delegate:
arr[] = Arr[];
int x = 3;
// Put stuff greater than 3 on the left
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
// Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
}
@safe unittest
{
import std.algorithm.internal : rndstuff;
static bool even(int a) { return (a & 1) == 0; }
// test with random data
auto a = rndstuff!int();
partition!even(a);
assert(isPartitioned!even(a));
auto b = rndstuff!string();
partition!`a.length < 5`(b);
assert(isPartitioned!`a.length < 5`(b));
}
// pivotPartition
/**
Partitions `r` around `pivot` using comparison function `less`, algorithm akin
to $(LINK2 https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme,
Hoare partition). Specifically, permutes elements of `r` and returns
an index $(D k < r.length) such that:
$(UL
$(LI `r[pivot]` is swapped to `r[k]`)
$(LI All elements `e` in subrange $(D r[0 .. k]) satisfy $(D !less(r[k], e))
(i.e. `r[k]` is greater than or equal to each element to its left according to
predicate `less`))
$(LI All elements `e` in subrange $(D r[0 .. k]) satisfy $(D !less(e,
r[k])) (i.e. `r[k]` is less than or equal to each element to its right
according to predicate `less`)))
If `r` contains equivalent elements, multiple permutations of `r` satisfy these
constraints. In such cases, `pivotPartition` attempts to distribute equivalent
elements fairly to the left and right of `k` such that `k` stays close to $(D
r.length / 2).
Params:
less = The predicate used for comparison, modeled as a
$(LINK2 https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings,
strict weak ordering) (irreflexive, antisymmetric, transitive, and implying a transitive
equivalence)
r = The range being partitioned
pivot = The index of the pivot for partitioning, must be less than `r.length` or
`0` is `r.length` is `0`
Returns:
The new position of the pivot
See_Also:
$(HTTP jgrcs.info/index.php/jgrcs/article/view/142, Engineering of a Quicksort
Partitioning Algorithm), D. Abhyankar, Journal of Global Research in Computer
Science, February 2011. $(HTTPS youtube.com/watch?v=AxnotgLql0k, ACCU 2016
Keynote), Andrei Alexandrescu.
*/
size_t pivotPartition(alias less = "a < b", Range)
(Range r, size_t pivot)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range)
{
assert(pivot < r.length || r.length == 0 && pivot == 0);
if (r.length <= 1) return 0;
import std.algorithm.mutation : swapAt, move;
alias lt = binaryFun!less;
// Pivot at the front
r.swapAt(pivot, 0);
// Fork implementation depending on nothrow copy, assignment, and
// comparison. If all of these are nothrow, use the specialized
// implementation discussed at https://youtube.com/watch?v=AxnotgLql0k.
static if (is(typeof(
() nothrow { auto x = r.front; x = r.front; return lt(x, x); }
)))
{
auto p = r[0];
// Plant the pivot in the end as well as a sentinel
size_t lo = 0, hi = r.length - 1;
auto save = move(r[hi]);
r[hi] = p; // Vacancy is in r[$ - 1] now
// Start process
for (;;)
{
// Loop invariant
version (unittest)
{
import std.algorithm.searching : all;
assert(r[0 .. lo].all!(x => !lt(p, x)));
assert(r[hi + 1 .. r.length].all!(x => !lt(x, p)));
}
do ++lo; while (lt(r[lo], p));
r[hi] = r[lo];
// Vacancy is now in r[lo]
do --hi; while (lt(p, r[hi]));
if (lo >= hi) break;
r[lo] = r[hi];
// Vacancy is not in r[hi]
}
// Fixup
assert(lo - hi <= 2);
assert(!lt(p, r[hi]));
if (lo == hi + 2)
{
assert(!lt(r[hi + 1], p));
r[lo] = r[hi + 1];
--lo;
}
r[lo] = save;
if (lt(p, save)) --lo;
assert(!lt(p, r[lo]));
}
else
{
size_t lo = 1, hi = r.length - 1;
loop: for (;; lo++, hi--)
{
for (;; ++lo)
{
if (lo > hi) break loop;
if (!lt(r[lo], r[0])) break;
}
// found the left bound: r[lo] >= r[0]
assert(lo <= hi);
for (;; --hi)
{
if (lo >= hi) break loop;
if (!lt(r[0], r[hi])) break;
}
// found the right bound: r[hi] <= r[0], swap & make progress
assert(!lt(r[lo], r[hi]));
r.swapAt(lo, hi);
}
--lo;
}
r.swapAt(lo, 0);
return lo;
}
///
@safe nothrow unittest
{
int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
size_t pivot = pivotPartition(a, a.length / 2);
import std.algorithm.searching : all;
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));
}
@safe unittest
{
void test(alias less)()
{
int[] a;
size_t pivot;
a = [-9, -4, -2, -2, 9];
pivot = pivotPartition!less(a, a.length / 2);
import std.algorithm.searching : all;
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));
a = [9, 2, 8, -5, 5, 4, -8, -4, 9];
pivot = pivotPartition!less(a, a.length / 2);
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));
a = [ 42 ];
pivot = pivotPartition!less(a, a.length / 2);
assert(pivot == 0);
assert(a == [ 42 ]);
a = [ 43, 42 ];
pivot = pivotPartition!less(a, 0);
assert(pivot == 1);
assert(a == [ 42, 43 ]);
a = [ 43, 42 ];
pivot = pivotPartition!less(a, 1);
assert(pivot == 0);
assert(a == [ 42, 43 ]);
a = [ 42, 42 ];
pivot = pivotPartition!less(a, 0);
assert(pivot == 0 || pivot == 1);
assert(a == [ 42, 42 ]);
pivot = pivotPartition!less(a, 1);
assert(pivot == 0 || pivot == 1);
assert(a == [ 42, 42 ]);
import std.algorithm.iteration : map;
import std.random;
import std.stdio;
auto s = unpredictableSeed;
auto g = Random(s);
a = iota(0, uniform(1, 1000, g))
.map!(_ => uniform(-1000, 1000, g))
.array;
scope(failure) writeln("RNG seed was ", s);
pivot = pivotPartition!less(a, a.length / 2);
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));
}
test!"a < b";
static bool myLess(int a, int b)
{
static bool bogus;
if (bogus) throw new Exception(""); // just to make it no-nothrow
return a < b;
}
test!myLess;
}
/**
Params:
pred = The predicate that the range should be partitioned by.
r = The range to check.
Returns: $(D true) if $(D r) is partitioned according to predicate $(D pred).
*/
bool isPartitioned(alias pred, Range)(Range r)
if (isForwardRange!(Range))
{
for (; !r.empty; r.popFront())
{
if (unaryFun!(pred)(r.front)) continue;
for (r.popFront(); !r.empty; r.popFront())
{
if (unaryFun!(pred)(r.front)) return false;
}
break;
}
return true;
}
///
@safe unittest
{
int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
assert(isPartitioned!"a & 1"(r));
}
// partition3
/**
Rearranges elements in $(D r) in three adjacent ranges and returns
them. The first and leftmost range only contains elements in $(D r)
less than $(D pivot). The second and middle range only contains
elements in $(D r) that are equal to $(D pivot). Finally, the third
and rightmost range only contains elements in $(D r) that are greater
than $(D pivot). The less-than test is defined by the binary function
$(D less).
Params:
less = The predicate to use for the rearrangement.
ss = The swapping strategy to use.
r = The random-access range to rearrange.
pivot = The pivot element.
Returns:
A $(REF Tuple, std,typecons) of the three resulting ranges. These ranges are
slices of the original range.
BUGS: stable $(D partition3) has not been implemented yet.
*/
auto partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)
(Range r, E pivot)
if (ss == SwapStrategy.unstable && isRandomAccessRange!Range
&& hasSwappableElements!Range && hasLength!Range && hasSlicing!Range
&& is(typeof(binaryFun!less(r.front, pivot)) == bool)
&& is(typeof(binaryFun!less(pivot, r.front)) == bool)
&& is(typeof(binaryFun!less(r.front, r.front)) == bool))
{
// The algorithm is described in "Engineering a sort function" by
// Jon Bentley et al, pp 1257.
import std.algorithm.comparison : min;
import std.algorithm.mutation : swap, swapAt, swapRanges;
import std.typecons : tuple;
alias lessFun = binaryFun!less;
size_t i, j, k = r.length, l = k;
bigloop:
for (;;)
{
for (;; ++j)
{
if (j == k) break bigloop;
assert(j < r.length);
if (lessFun(r[j], pivot)) continue;
if (lessFun(pivot, r[j])) break;
r.swapAt(i++, j);
}
assert(j < k);
for (;;)
{
assert(k > 0);
if (!lessFun(pivot, r[--k]))
{
if (lessFun(r[k], pivot)) break;
r.swapAt(k, --l);
}
if (j == k) break bigloop;
}
// Here we know r[j] > pivot && r[k] < pivot
r.swapAt(j++, k);
}
// Swap the equal ranges from the extremes into the middle
auto strictlyLess = j - i, strictlyGreater = l - k;
auto swapLen = min(i, strictlyLess);
swapRanges(r[0 .. swapLen], r[j - swapLen .. j]);
swapLen = min(r.length - l, strictlyGreater);
swapRanges(r[k .. k + swapLen], r[r.length - swapLen .. r.length]);
return tuple(r[0 .. strictlyLess],
r[strictlyLess .. r.length - strictlyGreater],
r[r.length - strictlyGreater .. r.length]);
}
///
@safe unittest
{
auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
auto pieces = partition3(a, 4);
assert(pieces[0] == [ 1, 3 ]);
assert(pieces[1] == [ 4, 4, 4 ]);
assert(pieces[2] == [ 8, 7 ]);
}
@safe unittest
{
import std.random : Random, uniform, unpredictableSeed;
immutable uint[] seeds = [3923355730, 1927035882, unpredictableSeed];
foreach (s; seeds)
{
auto r = Random(s);
auto a = new int[](uniform(0, 100, r));
foreach (ref e; a)
{
e = uniform(0, 50, r);
}
auto pieces = partition3(a, 25);
assert(pieces[0].length + pieces[1].length + pieces[2].length == a.length);
foreach (e; pieces[0])
{
assert(e < 25);
}
foreach (e; pieces[1])
{
assert(e == 25);
}
foreach (e; pieces[2])
{
assert(e > 25);
}
}
}
// makeIndex
/**
Computes an index for $(D r) based on the comparison $(D less). The
index is a sorted array of pointers or indices into the original
range. This technique is similar to sorting, but it is more flexible
because (1) it allows "sorting" of immutable collections, (2) allows
binary search even if the original collection does not offer random
access, (3) allows multiple indexes, each on a different predicate,
and (4) may be faster when dealing with large objects. However, using
an index may also be slower under certain circumstances due to the
extra indirection, and is always larger than a sorting-based solution
because it needs space for the index in addition to the original
collection. The complexity is the same as $(D sort)'s.
The first overload of $(D makeIndex) writes to a range containing
pointers, and the second writes to a range containing offsets. The
first overload requires $(D Range) to be a
$(REF_ALTTEXT forward range, isForwardRange, std,range,primitives), and the
latter requires it to be a random-access range.
$(D makeIndex) overwrites its second argument with the result, but
never reallocates it.
Params:
less = The comparison to use.
ss = The swapping strategy.
r = The range to index.
index = The resulting index.
Returns: The pointer-based version returns a $(D SortedRange) wrapper
over index, of type $(D SortedRange!(RangeIndex, (a, b) =>
binaryFun!less(*a, *b))) thus reflecting the ordering of the
index. The index-based version returns $(D void) because the ordering
relation involves not only $(D index) but also $(D r).
Throws: If the second argument's length is less than that of the range
indexed, an exception is thrown.
*/
SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))
makeIndex(
alias less = "a < b",
SwapStrategy ss = SwapStrategy.unstable,
Range,
RangeIndex)
(Range r, RangeIndex index)
if (isForwardRange!(Range) && isRandomAccessRange!(RangeIndex)
&& is(ElementType!(RangeIndex) : ElementType!(Range)*))
{
import std.algorithm.internal : addressOf;
import std.exception : enforce;
// assume collection already ordered
size_t i;
for (; !r.empty; r.popFront(), ++i)
index[i] = addressOf(r.front);
enforce(index.length == i);
// sort the index
sort!((a, b) => binaryFun!less(*a, *b), ss)(index);
return typeof(return)(index);
}
/// Ditto
void makeIndex(
alias less = "a < b",
SwapStrategy ss = SwapStrategy.unstable,
Range,
RangeIndex)
(Range r, RangeIndex index)
if (isRandomAccessRange!Range && !isInfinite!Range &&
isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex &&
isIntegral!(ElementType!RangeIndex))
{
import std.conv : to;
import std.exception : enforce;
alias IndexType = Unqual!(ElementType!RangeIndex);
enforce(r.length == index.length,
"r and index must be same length for makeIndex.");
static if (IndexType.sizeof < size_t.sizeof)
{
enforce(r.length <= size_t(1) + IndexType.max, "Cannot create an index with " ~
"element type " ~ IndexType.stringof ~ " with length " ~
to!string(r.length) ~ ".");
}
// Use size_t as loop index to avoid overflow on ++i,
// e.g. when squeezing 256 elements into a ubyte index.
foreach (size_t i; 0 .. r.length)
index[i] = cast(IndexType) i;
// sort the index
sort!((a, b) => binaryFun!less(r[cast(size_t) a], r[cast(size_t) b]), ss)
(index);
}
///
@system unittest
{
immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
// index using pointers
auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// index using offsets
auto index2 = new size_t[arr.length];
makeIndex!("a < b")(arr, index2);
assert(isSorted!
((size_t a, size_t b){ return arr[a] < arr[b];})
(index2));
}
@system unittest
{
immutable(int)[] arr = [ 2, 3, 1, 5, 0 ];
// index using pointers
auto index1 = new immutable(int)*[arr.length];
alias ImmRange = typeof(arr);
alias ImmIndex = typeof(index1);
static assert(isForwardRange!(ImmRange));
static assert(isRandomAccessRange!(ImmIndex));
static assert(!isIntegral!(ElementType!(ImmIndex)));
static assert(is(ElementType!(ImmIndex) : ElementType!(ImmRange)*));
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
// index using offsets
auto index2 = new long[arr.length];
makeIndex(arr, index2);
assert(isSorted!
((long a, long b){
return arr[cast(size_t) a] < arr[cast(size_t) b];
})(index2));
// index strings using offsets
string[] arr1 = ["I", "have", "no", "chocolate"];
auto index3 = new byte[arr1.length];
makeIndex(arr1, index3);
assert(isSorted!
((byte a, byte b){ return arr1[a] < arr1[b];})
(index3));
}
@safe unittest
{
import std.algorithm.comparison : equal;
ubyte[256] index = void;
iota(256).makeIndex(index[]);
assert(index[].equal(iota(256)));
byte[128] sindex = void;
iota(128).makeIndex(sindex[]);
assert(sindex[].equal(iota(128)));
auto index2 = new uint[10];
10.iota.makeIndex(index2);
assert(index2.equal(10.iota));
}
struct Merge(alias less = "a < b", Rs...)
if (Rs.length >= 2 &&
allSatisfy!(isInputRange, Rs) &&
!is(CommonType!(staticMap!(ElementType, Rs)) == void))
{
public Rs source;
private size_t _lastFrontIndex = size_t.max;
static if (isBidirectional)
{
private size_t _lastBackIndex = size_t.max; // `size_t.max` means uninitialized,
}
import std.functional : binaryFun;
import std.traits : isCopyable;
import std.typetuple : anySatisfy;
private alias comp = binaryFun!less;
private alias ElementType = CommonType!(staticMap!(.ElementType, Rs));
private enum isBidirectional = allSatisfy!(isBidirectionalRange, staticMap!(Unqual, Rs));
debug private enum canCheckSortedness = isCopyable!ElementType && !hasAliasing!ElementType;
this(Rs source)
{
this.source = source;
this._lastFrontIndex = frontIndex;
}
static if (anySatisfy!(isInfinite, Rs))
{
enum bool empty = false; // propagate infiniteness
}
else
{
@property bool empty()
{
return _lastFrontIndex == size_t.max;
}
}
@property auto ref front()
{
final switch (_lastFrontIndex)
{
foreach (i, _; Rs)
{
case i:
assert(!source[i].empty);
return source[i].front;
}
}
}
private size_t frontIndex()
{
size_t bestIndex = size_t.max; // indicate undefined
Unqual!ElementType bestElement;
foreach (i, _; Rs)
{
if (source[i].empty) continue;
if (bestIndex == size_t.max || // either this is the first or
comp(source[i].front, bestElement))
{
bestIndex = i;
bestElement = source[i].front;
}
}
return bestIndex;
}
void popFront()
{
sw: final switch (_lastFrontIndex)
{
foreach (i, R; Rs)
{
case i:
debug static if (canCheckSortedness)
{
ElementType previousFront = source[i].front();
}
source[i].popFront();
debug static if (canCheckSortedness)
{
if (!source[i].empty)
{
assert(previousFront == source[i].front ||
comp(previousFront, source[i].front),
"Input " ~ i.stringof ~ " is unsorted"); // @nogc
}
}
break sw;
}
}
_lastFrontIndex = frontIndex;
}
static if (isBidirectional)
{
@property auto ref back()
{
if (_lastBackIndex == size_t.max)
{
this._lastBackIndex = backIndex; // lazy initialization
}
final switch (_lastBackIndex)
{
foreach (i, _; Rs)
{
case i:
assert(!source[i].empty);
return source[i].back;
}
}
}
private size_t backIndex()
{
size_t bestIndex = size_t.max; // indicate undefined
Unqual!ElementType bestElement;
foreach (i, _; Rs)
{
if (source[i].empty) continue;
if (bestIndex == size_t.max || // either this is the first or
comp(bestElement, source[i].back))
{
bestIndex = i;
bestElement = source[i].back;
}
}
return bestIndex;
}
void popBack()
{
if (_lastBackIndex == size_t.max)
{
this._lastBackIndex = backIndex; // lazy initialization
}
sw: final switch (_lastBackIndex)
{
foreach (i, R; Rs)
{
case i:
debug static if (canCheckSortedness)
{
ElementType previousBack = source[i].back();
}
source[i].popBack();
debug static if (canCheckSortedness)
{
if (!source[i].empty)
{
assert(previousBack == source[i].back ||
comp(source[i].back, previousBack),
"Input " ~ i.stringof ~ " is unsorted"); // @nogc
}
}
break sw;
}
}
_lastBackIndex = backIndex;
if (_lastBackIndex == size_t.max) // if emptied
{
_lastFrontIndex = size_t.max;
}
}
}
static if (allSatisfy!(isForwardRange, staticMap!(Unqual, Rs)))
{
@property auto save()
{
auto result = this;
foreach (i, _; Rs)
{
result.source[i] = result.source[i].save;
}
return result;
}
}
static if (allSatisfy!(hasLength, Rs))
{
@property size_t length()
{
size_t result;
foreach (i, _; Rs)
{
result += source[i].length;
}
return result;
}
alias opDollar = length;
}
}
/**
Merge multiple sorted ranges `rs` with less-than predicate function `pred`
into one single sorted output range containing the sorted union of the
elements of inputs. Duplicates are not eliminated, meaning that the total
number of elements in the output is the sum of all elements in the ranges
passed to it; the `length` member is offered if all inputs also have
`length`. The element types of all the inputs must have a common type
`CommonType`.
Params:
less = Predicate the given ranges are sorted by.
rs = The ranges to compute the union for.
Returns:
A range containing the union of the given ranges.
Details:
All of its inputs are assumed to be sorted. This can mean that inputs are
instances of $(REF SortedRange, std,range). Use the result of $(REF sort,
std,algorithm,sorting), or $(REF assumeSorted, std,range) to merge ranges
known to be sorted (show in the example below). Note that there is currently
no way of ensuring that two or more instances of $(REF SortedRange,
std,range) are sorted using a specific comparison function `pred`. Therefore
no checking is done here to assure that all inputs `rs` are instances of
$(REF SortedRange, std,range).
This algorithm is lazy, doing work progressively as elements are pulled off
the result.
Time complexity is proportional to the sum of element counts over all inputs.
If all inputs have the same element type and offer it by `ref`, output
becomes a range with mutable `front` (and `back` where appropriate) that
reflects in the original inputs.
If any of the inputs `rs` is infinite so is the result (`empty` being always
`false`).
*/
Merge!(less, Rs) merge(alias less = "a < b", Rs...)(Rs rs)
if (Rs.length >= 2 &&
allSatisfy!(isInputRange, Rs) &&
!is(CommonType!(staticMap!(ElementType, Rs)) == void))
{
return typeof(return)(rs);
}
///
@safe pure nothrow unittest
{
import std.algorithm.comparison : equal;
import std.range : retro;
int[] a = [1, 3, 5];
int[] b = [2, 3, 4];
assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));
}
@safe pure nothrow unittest
{
import std.algorithm.comparison : equal;
int[] a = [ 1, 2, 4, 5, 7, 9 ];
int[] b = [ 0, 1, 2, 4, 7, 8 ];
double[] c = [ 10.5 ];
assert(merge(a, b).length == a.length + b.length);
assert(equal(merge(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
assert(equal(merge(a, c, b),
[0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10.5][]));
auto u = merge(a, b);
u.front--;
assert(equal(u, [-1, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
}
@safe pure nothrow unittest
{
// save
import std.range : dropOne;
int[] a = [1, 2];
int[] b = [0, 3];
auto arr = a.merge(b);
assert(arr.front == 0);
assert(arr.save.dropOne.front == 1);
assert(arr.front == 0);
}
@safe pure nothrow unittest
{
import std.algorithm.comparison : equal;
import std.internal.test.dummyrange;
auto dummyResult1 = [1, 1, 1.5, 2, 3, 4, 5, 5.5, 6, 7, 8, 9, 10];
auto dummyResult2 = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5,
6, 6, 7, 7, 8, 8, 9, 9, 10, 10];
foreach (DummyType; AllDummyRanges)
{
DummyType d;
assert(d.merge([1, 1.5, 5.5]).equal(dummyResult1));
assert(d.merge(d).equal(dummyResult2));
}
}
@nogc @safe pure nothrow unittest
{
import std.algorithm.comparison : equal;
static immutable a = [1, 3, 5];
static immutable b = [2, 3, 4];
static immutable r = [1, 2, 3, 3, 4, 5];
assert(a.merge(b).equal(r));
}
/// test bi-directional access and common type
@safe pure nothrow unittest
{
import std.algorithm.comparison : equal;
import std.range : retro;
import std.traits : CommonType;
alias S = short;
alias I = int;
alias D = double;
S[] a = [1, 2, 3];
I[] b = [50, 60];
D[] c = [10, 20, 30, 40];
auto m = merge(a, b, c);
static assert(is(typeof(m.front) == CommonType!(S, I, D)));
assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60]));
assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1]));
m.popFront();
assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60]));
m.popBack();
assert(equal(m, [2, 3, 10, 20, 30, 40, 50]));
m.popFront();
assert(equal(m, [3, 10, 20, 30, 40, 50]));
m.popBack();
assert(equal(m, [3, 10, 20, 30, 40]));
m.popFront();
assert(equal(m, [10, 20, 30, 40]));
m.popBack();
assert(equal(m, [10, 20, 30]));
m.popFront();
assert(equal(m, [20, 30]));
m.popBack();
assert(equal(m, [20]));
m.popFront();
assert(m.empty);
}
private template validPredicates(E, less...)
{
static if (less.length == 0)
enum validPredicates = true;
else static if (less.length == 1 && is(typeof(less[0]) == SwapStrategy))
enum validPredicates = true;
else
enum validPredicates =
is(typeof((E a, E b){ bool r = binaryFun!(less[0])(a, b); }))
&& validPredicates!(E, less[1 .. $]);
}
/**
$(D auto multiSort(Range)(Range r)
if (validPredicates!(ElementType!Range, less));)
Sorts a range by multiple keys. The call $(D multiSort!("a.id < b.id",
"a.date > b.date")(r)) sorts the range $(D r) by $(D id) ascending,
and sorts elements that have the same $(D id) by $(D date)
descending. Such a call is equivalent to $(D sort!"a.id != b.id ? a.id
< b.id : a.date > b.date"(r)), but $(D multiSort) is faster because it
does fewer comparisons (in addition to being more convenient).
Returns:
The initial range wrapped as a $(D SortedRange) with its predicates
converted to an equivalent single predicate.
*/
template multiSort(less...) //if (less.length > 1)
{
auto multiSort(Range)(Range r)
if (validPredicates!(ElementType!Range, less))
{
import std.meta : AliasSeq;
import std.range : assumeSorted;
static if (is(typeof(less[$ - 1]) == SwapStrategy))
{
enum ss = less[$ - 1];
alias funs = less[0 .. $ - 1];
}
else
{
enum ss = SwapStrategy.unstable;
alias funs = less;
}
static if (funs.length == 0)
static assert(false, "No sorting predicate provided for multiSort");
else
static if (funs.length == 1)
return sort!(funs[0], ss, Range)(r);
else
{
multiSortImpl!(Range, ss, funs)(r);
return assumeSorted!(multiSortPredFun!(Range, funs))(r);
}
}
}
private bool multiSortPredFun(Range, funs...)(ElementType!Range a, ElementType!Range b)
{
foreach (f; funs)
{
alias lessFun = binaryFun!(f);
if (lessFun(a, b)) return true;
if (lessFun(b, a)) return false;
}
return false;
}
private void multiSortImpl(Range, SwapStrategy ss, funs...)(Range r)
{
alias lessFun = binaryFun!(funs[0]);
static if (funs.length > 1)
{
while (r.length > 1)
{
auto p = getPivot!lessFun(r);
auto t = partition3!(funs[0], ss)(r, r[p]);
if (t[0].length <= t[2].length)
{
multiSortImpl!(Range, ss, funs)(t[0]);
multiSortImpl!(Range, ss, funs[1 .. $])(t[1]);
r = t[2];
}
else
{
multiSortImpl!(Range, ss, funs[1 .. $])(t[1]);
multiSortImpl!(Range, ss, funs)(t[2]);
r = t[0];
}
}
}
else
{
sort!(lessFun, ss)(r);
}
}
///
@safe unittest
{
import std.algorithm.mutation : SwapStrategy;
static struct Point { int x, y; }
auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ];
auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ];
multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
assert(pts1 == pts2);
}
@safe unittest
{
import std.algorithm.comparison : equal;
import std.range;
static struct Point { int x, y; }
auto pts1 = [ Point(5, 6), Point(1, 0), Point(5, 7), Point(1, 1), Point(1, 2), Point(0, 1) ];
auto pts2 = [ Point(0, 1), Point(1, 0), Point(1, 1), Point(1, 2), Point(5, 6), Point(5, 7) ];
static assert(validPredicates!(Point, "a.x < b.x", "a.y < b.y"));
multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
assert(pts1 == pts2);
auto pts3 = indexed(pts1, iota(pts1.length));
assert(pts3.multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable).release.equal(pts2));
auto pts4 = iota(10).array;
assert(pts4.multiSort!("a > b").release.equal(iota(10).retro));
}
@safe unittest //issue 9160 (L-value only comparators)
{
static struct A
{
int x;
int y;
}
static bool byX(const ref A lhs, const ref A rhs)
{
return lhs.x < rhs.x;
}
static bool byY(const ref A lhs, const ref A rhs)
{
return lhs.y < rhs.y;
}
auto points = [ A(4, 1), A(2, 4)];
multiSort!(byX, byY)(points);
assert(points[0] == A(2, 4));
assert(points[1] == A(4, 1));
}
@safe unittest // issue 16179 (cannot access frame of function)
{
auto arr = [[1, 2], [2, 0], [1, 0], [1, 1]];
int c = 3;
arr.multiSort!(
(a, b) => a[0] < b[0],
(a, b) => c*a[1] < c*b[1]
);
assert(arr == [[1, 0], [1, 1], [1, 2], [2, 0]]);
}
@safe unittest //Issue 16413 - @system comparison function
{
bool lt(int a, int b) { return a < b; } static @system
auto a = [2, 1];
a.multiSort!(lt, lt);
assert(a == [1, 2]);
}
private size_t getPivot(alias less, Range)(Range r)
{
auto mid = r.length / 2;
if (r.length < 512)
{
if (r.length >= 32)
medianOf!less(r, size_t(0), mid, r.length - 1);
return mid;
}
// The plan here is to take the median of five by taking five elements in
// the array, segregate around their median, and return the position of the
// third. We choose first, mid, last, and two more in between those.
auto quarter = r.length / 4;
medianOf!less(r,
size_t(0), mid - quarter, mid, mid + quarter, r.length - 1);
return mid;
}
/*
Sorting routine that is optimized for short ranges. Note: uses insertion sort
going downward. Benchmarked a similar routine that goes upward, for some reason
it's slower.
*/
private void shortSort(alias less, Range)(Range r)
{
import std.algorithm.mutation : swapAt;
alias pred = binaryFun!(less);
switch (r.length)
{
case 0: case 1:
return;
case 2:
if (pred(r[1], r[0])) r.swapAt(0, 1);
return;
case 3:
if (pred(r[2], r[0]))
{
if (pred(r[0], r[1]))
{
r.swapAt(0, 1);
r.swapAt(0, 2);
}
else
{
r.swapAt(0, 2);
if (pred(r[1], r[0])) r.swapAt(0, 1);
}
}
else
{
if (pred(r[1], r[0]))
{
r.swapAt(0, 1);
}
else
{
if (pred(r[2], r[1])) r.swapAt(1, 2);
}
}
return;
case 4:
if (pred(r[1], r[0])) r.swapAt(0, 1);
if (pred(r[3], r[2])) r.swapAt(2, 3);
if (pred(r[2], r[0])) r.swapAt(0, 2);
if (pred(r[3], r[1])) r.swapAt(1, 3);
if (pred(r[2], r[1])) r.swapAt(1, 2);
return;
default:
sort5!pred(r[r.length - 5 .. r.length]);
if (r.length == 5) return;
break;
}
assert(r.length >= 6);
/* The last 5 elements of the range are sorted. Proceed with expanding the
sorted portion downward. */
immutable maxJ = r.length - 2;
for (size_t i = r.length - 6; ; --i)
{
static if (is(typeof(() nothrow
{
auto t = r[0]; if (pred(t, r[0])) r[0] = r[0];
}))) // Can we afford to temporarily invalidate the array?
{
size_t j = i + 1;
auto temp = r[i];
if (pred(r[j], temp))
{
do
{
r[j - 1] = r[j];
++j;
}
while (j < r.length && pred(r[j], temp));
r[j - 1] = temp;
}
}
else
{
size_t j = i;
while (pred(r[j + 1], r[j]))
{
r.swapAt(j, j + 1);
if (j == maxJ) break;
++j;
}
}
if (i == 0) break;
}
}
@safe unittest
{
import std.random : Random, uniform;
auto rnd = Random(1);
auto a = new int[uniform(100, 200, rnd)];
foreach (ref e; a)
{
e = uniform(-100, 100, rnd);
}
shortSort!(binaryFun!("a < b"), int[])(a);
assert(isSorted(a));
}
/*
Sorts the first 5 elements exactly of range r.
*/
private void sort5(alias lt, Range)(Range r)
{
assert(r.length >= 5);
import std.algorithm.mutation : swapAt;
// 1. Sort first two pairs
if (lt(r[1], r[0])) r.swapAt(0, 1);
if (lt(r[3], r[2])) r.swapAt(2, 3);
// 2. Arrange first two pairs by the largest element
if (lt(r[3], r[1]))
{
r.swapAt(0, 2);
r.swapAt(1, 3);
}
assert(!lt(r[1], r[0]) && !lt(r[3], r[1]) && !lt(r[3], r[2]));
// 3. Insert 4 into [0, 1, 3]
if (lt(r[4], r[1]))
{
r.swapAt(3, 4);
r.swapAt(1, 3);
if (lt(r[1], r[0]))
{
r.swapAt(0, 1);
}
}
else if (lt(r[4], r[3]))
{
r.swapAt(3, 4);
}
assert(!lt(r[1], r[0]) && !lt(r[3], r[1]) && !lt(r[4], r[3]));
// 4. Insert 2 into [0, 1, 3, 4] (note: we already know the last is greater)
assert(!lt(r[4], r[2]));
if (lt(r[2], r[1]))
{
r.swapAt(1, 2);
if (lt(r[1], r[0]))
{
r.swapAt(0, 1);
}
}
else if (lt(r[3], r[2]))
{
r.swapAt(2, 3);
}
// 7 comparisons, 0-9 swaps
}
@safe unittest
{
import std.algorithm.iteration : permutations;
import std.algorithm.mutation : copy;
int[5] buf;
foreach (per; iota(5).permutations)
{
per.copy(buf[]);
sort5!((a, b) => a < b)(buf[]);
assert(buf[].isSorted);
}
}
// sort
/**
Sorts a random-access range according to the predicate $(D less). Performs
$(BIGOH r.length * log(r.length)) evaluations of $(D less). If `less` involves
expensive computations on the _sort key, it may be worthwhile to use
$(LREF schwartzSort) instead.
Stable sorting requires $(D hasAssignableElements!Range) to be true.
$(D sort) returns a $(REF SortedRange, std,range) over the original range,
allowing functions that can take advantage of sorted data to know that the
range is sorted and adjust accordingly. The $(REF SortedRange, std,range) is a
wrapper around the original range, so both it and the original range are sorted.
Other functions can't know that the original range has been sorted, but
they $(I can) know that $(REF SortedRange, std,range) has been sorted.
Preconditions:
The predicate is expected to satisfy certain rules in order for $(D sort) to
behave as expected - otherwise, the program may fail on certain inputs (but not
others) when not compiled in release mode, due to the cursory $(D assumeSorted)
check. Specifically, $(D sort) expects $(D less(a,b) && less(b,c)) to imply
$(D less(a,c)) (transitivity), and, conversely, $(D !less(a,b) && !less(b,c)) to
imply $(D !less(a,c)). Note that the default predicate ($(D "a < b")) does not
always satisfy these conditions for floating point types, because the expression
will always be $(D false) when either $(D a) or $(D b) is NaN.
Use $(REF cmp, std,math) instead.
Params:
less = The predicate to sort by.
ss = The swapping strategy to use.
r = The range to sort.
Returns: The initial range wrapped as a $(D SortedRange) with the predicate
$(D binaryFun!less).
Algorithms: $(HTTP en.wikipedia.org/wiki/Introsort, Introsort) is used for unstable sorting and
$(HTTP en.wikipedia.org/wiki/Timsort, Timsort) is used for stable sorting.
Each algorithm has benefits beyond stability. Introsort is generally faster but
Timsort may achieve greater speeds on data with low entropy or if predicate calls
are expensive. Introsort performs no allocations whereas Timsort will perform one
or more allocations per call. Both algorithms have $(BIGOH n log n) worst-case
time complexity.
See_Also:
$(REF assumeSorted, std,range)$(BR)
$(REF SortedRange, std,range)$(BR)
$(REF SwapStrategy, std,algorithm,mutation)$(BR)
$(REF binaryFun, std,functional)
*/
SortedRange!(Range, less)
sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
Range)(Range r)
if (((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
hasAssignableElements!Range)) ||
(ss != SwapStrategy.unstable && hasAssignableElements!Range)) &&
isRandomAccessRange!Range &&
hasSlicing!Range &&
hasLength!Range)
/+ Unstable sorting uses the quicksort algorithm, which uses swapAt,
which either uses swap(...), requiring swappable elements, or just
swaps using assignment.
Stable sorting uses TimSort, which needs to copy elements into a buffer,
requiring assignable elements. +/
{
import std.range : assumeSorted;
alias lessFun = binaryFun!(less);
alias LessRet = typeof(lessFun(r.front, r.front)); // instantiate lessFun
static if (is(LessRet == bool))
{
static if (ss == SwapStrategy.unstable)
quickSortImpl!(lessFun)(r, r.length);
else //use Tim Sort for semistable & stable
TimSortImpl!(lessFun, Range).sort(r, null);
assert(isSorted!lessFun(r), "Failed to sort range of type " ~ Range.stringof);
}
else
{
static assert(false, "Invalid predicate passed to sort: " ~ less.stringof);
}
return assumeSorted!less(r);
}
///
@safe pure nothrow unittest
{
int[] array = [ 1, 2, 3, 4 ];
// sort in descending order
array.sort!("a > b");
assert(array == [ 4, 3, 2, 1 ]);
// sort in ascending order
array.sort();
assert(array == [ 1, 2, 3, 4 ]);
// sort with reusable comparator and chain
alias myComp = (x, y) => x > y;
assert(array.sort!(myComp).release == [ 4, 3, 2, 1 ]);
}
///
@safe unittest
{
// Showcase stable sorting
import std.algorithm.mutation : SwapStrategy;
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
}
///
@safe unittest
{
// Sorting floating-point numbers in presence of NaN
double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];
import std.algorithm.comparison : equal;
import std.math : cmp, isIdentical;
sort!((a, b) => cmp(a, b) < 0)(numbers);
double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
assert(numbers.equal!isIdentical(sorted));
}
@safe unittest
{
// Simple regression benchmark
import std.algorithm.iteration, std.algorithm.mutation, std.random;
Random rng;
int[] a = iota(20148).map!(_ => uniform(-1000, 1000, rng)).array;
static uint comps;
static bool less(int a, int b) { ++comps; return a < b; }
sort!less(a); // random numbers
sort!less(a); // sorted ascending
a.reverse();
sort!less(a); // sorted descending
a[] = 0;
sort!less(a); // all equal
// This should get smaller with time. On occasion it may go larger, but only
// if there's thorough justification.
debug enum uint watermark = 1676280;
else enum uint watermark = 1676220;
import std.conv;
assert(comps <= watermark, text("You seem to have pessimized sort! ",
watermark, " < ", comps));
assert(comps >= watermark, text("You seem to have improved sort!",
" Please update watermark from ", watermark, " to ", comps));
}
@safe unittest
{
import std.algorithm.internal : rndstuff;
import std.algorithm.mutation : swapRanges;
import std.random : Random, unpredictableSeed, uniform;
import std.uni : toUpper;
// sort using delegate
auto a = new int[100];
auto rnd = Random(unpredictableSeed);
foreach (ref e; a)
{
e = uniform(-100, 100, rnd);
}
int i = 0;
bool greater2(int a, int b) @safe { return a + i > b + i; }
auto greater = &greater2;
sort!(greater)(a);
assert(isSorted!(greater)(a));
// sort using string
sort!("a < b")(a);
assert(isSorted!("a < b")(a));
// sort using function; all elements equal
foreach (ref e; a)
{
e = 5;
}
static bool less(int a, int b) { return a < b; }
sort!(less)(a);
assert(isSorted!(less)(a));
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
bool lessi(string a, string b) { return toUpper(a) < toUpper(b); }
sort!(lessi, SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
// sort using ternary predicate
//sort!("b - a")(a);
//assert(isSorted!(less)(a));
a = rndstuff!(int)();
sort(a);
assert(isSorted(a));
auto b = rndstuff!(string)();
sort!("toLower(a) < toLower(b)")(b);
assert(isSorted!("toUpper(a) < toUpper(b)")(b));
{
// Issue 10317
enum E_10317 { a, b }
auto a_10317 = new E_10317[10];
sort(a_10317);
}
{
// Issue 7767
// Unstable sort should complete without an excessive number of predicate calls
// This would suggest it's running in quadratic time
// Compilation error if predicate is not static, i.e. a nested function
static uint comp;
static bool pred(size_t a, size_t b)
{
++comp;
return a < b;
}
size_t[] arr;
arr.length = 1024;
foreach (k; 0 .. arr.length) arr[k] = k;
swapRanges(arr[0..$/2], arr[$/2..$]);
sort!(pred, SwapStrategy.unstable)(arr);
assert(comp < 25_000);
}
{
import std.algorithm.mutation : swap;
bool proxySwapCalled;
struct S
{
int i;
alias i this;
void proxySwap(ref S other) { swap(i, other.i); proxySwapCalled = true; }
@disable void opAssign(S value);
}
alias R = S[];
R r = [S(3), S(2), S(1)];
static assert(hasSwappableElements!R);
static assert(!hasAssignableElements!R);
r.sort();
assert(proxySwapCalled);
}
}
private void quickSortImpl(alias less, Range)(Range r, size_t depth)
{
import std.algorithm.comparison : min, max;
import std.algorithm.mutation : swap, swapAt;
alias Elem = ElementType!(Range);
enum size_t shortSortGetsBetter = max(32, 1024 / Elem.sizeof);
static assert(shortSortGetsBetter >= 1);
// partition
while (r.length > shortSortGetsBetter)
{
if (depth == 0)
{
HeapOps!(less, Range).heapSort(r);
return;
}
depth = depth >= depth.max / 2 ? (depth / 3) * 2 : (depth * 2) / 3;
const pivotIdx = getPivot!(less)(r);
auto pivot = r[pivotIdx];
// partition
r.swapAt(pivotIdx, r.length - 1);
size_t lessI = size_t.max, greaterI = r.length - 1;
outer: for (;;)
{
alias pred = binaryFun!less;
while (pred(r[++lessI], pivot)) {}
assert(lessI <= greaterI, "sort: invalid comparison function.");
for (;;)
{
if (greaterI == lessI) break outer;
if (!pred(pivot, r[--greaterI])) break;
}
assert(lessI <= greaterI, "sort: invalid comparison function.");
if (lessI == greaterI) break;
r.swapAt(lessI, greaterI);
}
r.swapAt(r.length - 1, lessI);
auto left = r[0 .. lessI], right = r[lessI + 1 .. r.length];
if (right.length > left.length)
{
swap(left, right);
}
.quickSortImpl!(less, Range)(right, depth);
r = left;
}
// residual sort
static if (shortSortGetsBetter > 1)
{
shortSort!(less, Range)(r);
}
}
// Heap operations for random-access ranges
package(std) template HeapOps(alias less, Range)
{
import std.algorithm.mutation : swapAt;
static assert(isRandomAccessRange!Range);
static assert(hasLength!Range);
static assert(hasSwappableElements!Range || hasAssignableElements!Range);
alias lessFun = binaryFun!less;
//template because of @@@12410@@@
void heapSort()(Range r)
{
// If true, there is nothing to do
if (r.length < 2) return;
// Build Heap
buildHeap(r);
// Sort
for (size_t i = r.length - 1; i > 0; --i)
{
r.swapAt(0, i);
percolate(r, 0, i);
}
}
//template because of @@@12410@@@
void buildHeap()(Range r)
{
immutable n = r.length;
for (size_t i = n / 2; i-- > 0; )
{
siftDown(r, i, n);
}
assert(isHeap(r));
}
bool isHeap()(Range r)
{
size_t parent = 0;
foreach (child; 1 .. r.length)
{
if (lessFun(r[parent], r[child])) return false;
// Increment parent every other pass
parent += !(child & 1);
}
return true;
}
// Sifts down r[parent] (which is initially assumed to be messed up) so the
// heap property is restored for r[parent .. end].
// template because of @@@12410@@@
void siftDown()(Range r, size_t parent, immutable size_t end)
{
for (;;)
{
auto child = (parent + 1) * 2;
if (child >= end)
{
// Leftover left child?
if (child == end && lessFun(r[parent], r[--child]))
r.swapAt(parent, child);
break;
}
auto leftChild = child - 1;
if (lessFun(r[child], r[leftChild])) child = leftChild;
if (!lessFun(r[parent], r[child])) break;
r.swapAt(parent, child);
parent = child;
}
}
// Alternate version of siftDown that performs fewer comparisons, see
// https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort. The percolate
// process first sifts the parent all the way down (without comparing it
// against the leaves), and then a bit up until the heap property is
// restored. So there are more swaps but fewer comparisons. Gains are made
// when the final position is likely to end toward the bottom of the heap,
// so not a lot of sifts back are performed.
//template because of @@@12410@@@
void percolate()(Range r, size_t parent, immutable size_t end)
{
immutable root = parent;
// Sift down
for (;;)
{
auto child = (parent + 1) * 2;
if (child >= end)
{
if (child == end)
{
// Leftover left node.
--child;
r.swapAt(parent, child);
parent = child;
}
break;
}
auto leftChild = child - 1;
if (lessFun(r[child], r[leftChild])) child = leftChild;
r.swapAt(parent, child);
parent = child;
}
// Sift up
for (auto child = parent; child > root; child = parent)
{
parent = (child - 1) / 2;
if (!lessFun(r[parent], r[child])) break;
r.swapAt(parent, child);
}
}
}
// Tim Sort implementation
private template TimSortImpl(alias pred, R)
{
import core.bitop : bsr;
import std.array : uninitializedArray;
static assert(isRandomAccessRange!R);
static assert(hasLength!R);
static assert(hasSlicing!R);
static assert(hasAssignableElements!R);
alias T = ElementType!R;
alias less = binaryFun!pred;
alias greater = (a, b) => less(b, a);
alias greaterEqual = (a, b) => !less(a, b);
alias lessEqual = (a, b) => !less(b, a);
enum minimalMerge = 128;
enum minimalGallop = 7;
enum minimalStorage = 256;
enum stackSize = 40;
struct Slice{ size_t base, length; }
// Entry point for tim sort
void sort()(R range, T[] temp)
{
import std.algorithm.comparison : min;
// Do insertion sort on small range
if (range.length <= minimalMerge)
{
binaryInsertionSort(range);
return;
}
immutable minRun = minRunLength(range.length);
immutable minTemp = min(range.length / 2, minimalStorage);
size_t minGallop = minimalGallop;
Slice[stackSize] stack = void;
size_t stackLen = 0;
// Allocate temporary memory if not provided by user
if (temp.length < minTemp) temp = () @trusted { return uninitializedArray!(T[])(minTemp); }();
for (size_t i = 0; i < range.length; )
{
// Find length of first run in list
size_t runLen = firstRun(range[i .. range.length]);
// If run has less than minRun elements, extend using insertion sort
if (runLen < minRun)
{
// Do not run farther than the length of the range
immutable force = range.length - i > minRun ? minRun : range.length - i;
binaryInsertionSort(range[i .. i + force], runLen);
runLen = force;
}
// Push run onto stack
stack[stackLen++] = Slice(i, runLen);
i += runLen;
// Collapse stack so that (e1 > e2 + e3 && e2 > e3)
// STACK is | ... e1 e2 e3 >
while (stackLen > 1)
{
immutable run4 = stackLen - 1;
immutable run3 = stackLen - 2;
immutable run2 = stackLen - 3;
immutable run1 = stackLen - 4;
if ( (stackLen > 2 && stack[run2].length <= stack[run3].length + stack[run4].length) ||
(stackLen > 3 && stack[run1].length <= stack[run3].length + stack[run2].length) )
{
immutable at = stack[run2].length < stack[run4].length ? run2 : run3;
mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
}
else if (stack[run3].length > stack[run4].length) break;
else mergeAt(range, stack[0 .. stackLen], run3, minGallop, temp);
stackLen -= 1;
}
// Assert that the code above established the invariant correctly
version (assert)
{
if (stackLen == 2) assert(stack[0].length > stack[1].length);
else if (stackLen > 2)
{
foreach (k; 2 .. stackLen)
{
assert(stack[k - 2].length > stack[k - 1].length + stack[k].length);
assert(stack[k - 1].length > stack[k].length);
}
}
}
}
// Force collapse stack until there is only one run left
while (stackLen > 1)
{
immutable run3 = stackLen - 1;
immutable run2 = stackLen - 2;
immutable run1 = stackLen - 3;
immutable at = stackLen >= 3 && stack[run1].length <= stack[run3].length
? run1 : run2;
mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
--stackLen;
}
}
// Calculates optimal value for minRun:
// take first 6 bits of n and add 1 if any lower bits are set
size_t minRunLength()(size_t n)
{
immutable shift = bsr(n)-5;
auto result = (n >> shift) + !!(n & ~((1 << shift)-1));
return result;
}
// Returns length of first run in range
size_t firstRun()(R range)
out(ret)
{
assert(ret <= range.length);
}
body
{
import std.algorithm.mutation : reverse;
if (range.length < 2) return range.length;
size_t i = 2;
if (lessEqual(range[0], range[1]))
{
while (i < range.length && lessEqual(range[i-1], range[i])) ++i;
}
else
{
while (i < range.length && greater(range[i-1], range[i])) ++i;
reverse(range[0 .. i]);
}
return i;
}
// A binary insertion sort for building runs up to minRun length
void binaryInsertionSort()(R range, size_t sortedLen = 1)
out
{
if (!__ctfe) assert(isSorted!pred(range));
}
body
{
import std.algorithm.mutation : move;
for (; sortedLen < range.length; ++sortedLen)
{
T item = range.moveAt(sortedLen);
size_t lower = 0;
size_t upper = sortedLen;
while (upper != lower)
{
size_t center = (lower + upper) / 2;
if (less(item, range[center])) upper = center;
else lower = center + 1;
}
//Currently (DMD 2.061) moveAll+retro is slightly less
//efficient then stright 'for' loop
//11 instructions vs 7 in the innermost loop [checked on Win32]
//moveAll(retro(range[lower .. sortedLen]),
// retro(range[lower+1 .. sortedLen+1]));
for (upper=sortedLen; upper > lower; upper--)
range[upper] = range.moveAt(upper - 1);
range[lower] = move(item);
}
}
// Merge two runs in stack (at, at + 1)
void mergeAt()(R range, Slice[] stack, immutable size_t at, ref size_t minGallop, ref T[] temp)
in
{
assert(stack.length >= 2);
assert(stack.length - at == 2 || stack.length - at == 3);
}
body
{
immutable base = stack[at].base;
immutable mid = stack[at].length;
immutable len = stack[at + 1].length + mid;
// Pop run from stack
stack[at] = Slice(base, len);
if (stack.length - at == 3) stack[$ - 2] = stack[$ - 1];
// Merge runs (at, at + 1)
return merge(range[base .. base + len], mid, minGallop, temp);
}
// Merge two runs in a range. Mid is the starting index of the second run.
// minGallop and temp are references; The calling function must receive the updated values.
void merge()(R range, size_t mid, ref size_t minGallop, ref T[] temp)
in
{
if (!__ctfe)
{
assert(isSorted!pred(range[0 .. mid]));
assert(isSorted!pred(range[mid .. range.length]));
}
}
body
{
assert(mid < range.length);
// Reduce range of elements
immutable firstElement = gallopForwardUpper(range[0 .. mid], range[mid]);
immutable lastElement = gallopReverseLower(range[mid .. range.length], range[mid - 1]) + mid;
range = range[firstElement .. lastElement];
mid -= firstElement;
if (mid == 0 || mid == range.length) return;
// Call function which will copy smaller run into temporary memory
if (mid <= range.length / 2)
{
temp = ensureCapacity(mid, temp);
minGallop = mergeLo(range, mid, minGallop, temp);
}
else
{
temp = ensureCapacity(range.length - mid, temp);
minGallop = mergeHi(range, mid, minGallop, temp);
}
}
// Enlarge size of temporary memory if needed
T[] ensureCapacity()(size_t minCapacity, T[] temp)
out(ret)
{
assert(ret.length >= minCapacity);
}
body
{
if (temp.length < minCapacity)
{
size_t newSize = 1<<(bsr(minCapacity)+1);
//Test for overflow
if (newSize < minCapacity) newSize = minCapacity;
if (__ctfe) temp.length = newSize;
else temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
}
return temp;
}
// Merge front to back. Returns new value of minGallop.
// temp must be large enough to store range[0 .. mid]
size_t mergeLo()(R range, immutable size_t mid, size_t minGallop, T[] temp)
out
{
if (!__ctfe) assert(isSorted!pred(range));
}
body
{
import std.algorithm.mutation : copy;
assert(mid <= range.length);
assert(temp.length >= mid);
// Copy run into temporary memory
temp = temp[0 .. mid];
copy(range[0 .. mid], temp);
// Move first element into place
range[0] = range[mid];
size_t i = 1, lef = 0, rig = mid + 1;
size_t count_lef, count_rig;
immutable lef_end = temp.length - 1;
if (lef < lef_end && rig < range.length)
outer: while (true)
{
count_lef = 0;
count_rig = 0;
// Linear merge
while ((count_lef | count_rig) < minGallop)
{
if (lessEqual(temp[lef], range[rig]))
{
range[i++] = temp[lef++];
if (lef >= lef_end) break outer;
++count_lef;
count_rig = 0;
}
else
{
range[i++] = range[rig++];
if (rig >= range.length) break outer;
count_lef = 0;
++count_rig;
}
}
// Gallop merge
do
{
count_lef = gallopForwardUpper(temp[lef .. $], range[rig]);
foreach (j; 0 .. count_lef) range[i++] = temp[lef++];
if (lef >= temp.length) break outer;
count_rig = gallopForwardLower(range[rig .. range.length], temp[lef]);
foreach (j; 0 .. count_rig) range[i++] = range[rig++];
if (rig >= range.length) while (true)
{
range[i++] = temp[lef++];
if (lef >= temp.length) break outer;
}
if (minGallop > 0) --minGallop;
}
while (count_lef >= minimalGallop || count_rig >= minimalGallop);
minGallop += 2;
}
// Move remaining elements from right
while (rig < range.length)
range[i++] = range[rig++];
// Move remaining elements from left
while (lef < temp.length)
range[i++] = temp[lef++];
return minGallop > 0 ? minGallop : 1;
}
// Merge back to front. Returns new value of minGallop.
// temp must be large enough to store range[mid .. range.length]
size_t mergeHi()(R range, immutable size_t mid, size_t minGallop, T[] temp)
out
{
if (!__ctfe) assert(isSorted!pred(range));
}
body
{
import std.algorithm.mutation : copy;
assert(mid <= range.length);
assert(temp.length >= range.length - mid);
// Copy run into temporary memory
temp = temp[0 .. range.length - mid];
copy(range[mid .. range.length], temp);
// Move first element into place
range[range.length - 1] = range[mid - 1];
size_t i = range.length - 2, lef = mid - 2, rig = temp.length - 1;
size_t count_lef, count_rig;
outer:
while (true)
{
count_lef = 0;
count_rig = 0;
// Linear merge
while ((count_lef | count_rig) < minGallop)
{
if (greaterEqual(temp[rig], range[lef]))
{
range[i--] = temp[rig];
if (rig == 1)
{
// Move remaining elements from left
while (true)
{
range[i--] = range[lef];
if (lef == 0) break;
--lef;
}
// Move last element into place
range[i] = temp[0];
break outer;
}
--rig;
count_lef = 0;
++count_rig;
}
else
{
range[i--] = range[lef];
if (lef == 0) while (true)
{
range[i--] = temp[rig];
if (rig == 0) break outer;
--rig;
}
--lef;
++count_lef;
count_rig = 0;
}
}
// Gallop merge
do
{
count_rig = rig - gallopReverseLower(temp[0 .. rig], range[lef]);
foreach (j; 0 .. count_rig)
{
range[i--] = temp[rig];
if (rig == 0) break outer;
--rig;
}
count_lef = lef - gallopReverseUpper(range[0 .. lef], temp[rig]);
foreach (j; 0 .. count_lef)
{
range[i--] = range[lef];
if (lef == 0) while (true)
{
range[i--] = temp[rig];
if (rig == 0) break outer;
--rig;
}
--lef;
}
if (minGallop > 0) --minGallop;
}
while (count_lef >= minimalGallop || count_rig >= minimalGallop);
minGallop += 2;
}
return minGallop > 0 ? minGallop : 1;
}
// false = forward / lower, true = reverse / upper
template gallopSearch(bool forwardReverse, bool lowerUpper)
{
// Gallop search on range according to attributes forwardReverse and lowerUpper
size_t gallopSearch(R)(R range, T value)
out(ret)
{
assert(ret <= range.length);
}
body
{
size_t lower = 0, center = 1, upper = range.length;
alias gap = center;
static if (forwardReverse)
{
static if (!lowerUpper) alias comp = lessEqual; // reverse lower
static if (lowerUpper) alias comp = less; // reverse upper
// Gallop Search Reverse
while (gap <= upper)
{
if (comp(value, range[upper - gap]))
{
upper -= gap;
gap *= 2;
}
else
{
lower = upper - gap;
break;
}
}
// Binary Search Reverse
while (upper != lower)
{
center = lower + (upper - lower) / 2;
if (comp(value, range[center])) upper = center;
else lower = center + 1;
}
}
else
{
static if (!lowerUpper) alias comp = greater; // forward lower
static if (lowerUpper) alias comp = greaterEqual; // forward upper
// Gallop Search Forward
while (lower + gap < upper)
{
if (comp(value, range[lower + gap]))
{
lower += gap;
gap *= 2;
}
else
{
upper = lower + gap;
break;
}
}
// Binary Search Forward
while (lower != upper)
{
center = lower + (upper - lower) / 2;
if (comp(value, range[center])) lower = center + 1;
else upper = center;
}
}
return lower;
}
}
alias gallopForwardLower = gallopSearch!(false, false);
alias gallopForwardUpper = gallopSearch!(false, true);
alias gallopReverseLower = gallopSearch!( true, false);
alias gallopReverseUpper = gallopSearch!( true, true);
}
@safe unittest
{
import std.random : Random, uniform, randomShuffle;
// Element type with two fields
static struct E
{
size_t value, index;
}
// Generates data especially for testing sorting with Timsort
static E[] genSampleData(uint seed) @safe
{
import std.algorithm.mutation : swap, swapRanges;
auto rnd = Random(seed);
E[] arr;
arr.length = 64 * 64;
// We want duplicate values for testing stability
foreach (i, ref v; arr) v.value = i / 64;
// Swap ranges at random middle point (test large merge operation)
immutable mid = uniform(arr.length / 4, arr.length / 4 * 3, rnd);
swapRanges(arr[0 .. mid], arr[mid .. $]);
// Shuffle last 1/8 of the array (test insertion sort and linear merge)
randomShuffle(arr[$ / 8 * 7 .. $], rnd);
// Swap few random elements (test galloping mode)
foreach (i; 0 .. arr.length / 64)
{
immutable a = uniform(0, arr.length, rnd), b = uniform(0, arr.length, rnd);
swap(arr[a], arr[b]);
}
// Now that our test array is prepped, store original index value
// This will allow us to confirm the array was sorted stably
foreach (i, ref v; arr) v.index = i;
return arr;
}
// Tests the Timsort function for correctness and stability
static bool testSort(uint seed)
{
auto arr = genSampleData(seed);
// Now sort the array!
static bool comp(E a, E b)
{
return a.value < b.value;
}
sort!(comp, SwapStrategy.stable)(arr);
// Test that the array was sorted correctly
assert(isSorted!comp(arr));
// Test that the array was sorted stably
foreach (i; 0 .. arr.length - 1)
{
if (arr[i].value =