1 // Written in the D programming language.
2 /**
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic _sorting algorithms.
5
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
9 $(T2 completeSort,
10 If $(D a = [10, 20, 30]) and $(D b = [40, 6, 15]), then
11 $(D completeSort(a, b)) leaves $(D a = [6, 10, 15]) and $(D b = [20,
12 30, 40]).
13 The range $(D a) must be sorted prior to the call, and as a result the
14 combination $(D $(REF chain, std,range)(a, b)) is sorted.)
15 $(T2 isPartitioned,
16 $(D isPartitioned!"a < 0"([-1, -2, 1, 0, 2])) returns $(D true) because
17 the predicate is $(D true) for a portion of the range and $(D false)
18 afterwards.)
19 $(T2 isSorted,
20 $(D isSorted([1, 1, 2, 3])) returns $(D true).)
21 $(T2 isStrictlyMonotonic,
22 $(D isStrictlyMonotonic([1, 1, 2, 3])) returns $(D false).)
23 $(T2 ordered,
24 $(D ordered(1, 1, 2, 3)) returns $(D true).)
25 $(T2 strictlyOrdered,
26 $(D strictlyOrdered(1, 1, 2, 3)) returns $(D false).)
27 $(T2 makeIndex,
28 Creates a separate index for a range.)
29 $(T2 merge,
30 Lazily merges two or more sorted ranges.)
31 $(T2 multiSort,
32 Sorts by multiple keys.)
33 $(T2 nextEvenPermutation,
34 Computes the next lexicographically greater even permutation of a range
35 in-place.)
36 $(T2 nextPermutation,
37 Computes the next lexicographically greater permutation of a range
38 in-place.)
39 $(T2 partialSort,
40 If $(D a = [5, 4, 3, 2, 1]), then $(D partialSort(a, 3)) leaves
41 $(D a[0 .. 3] = [1, 2, 3]).
42 The other elements of $(D a) are left in an unspecified order.)
43 $(T2 partition,
44 Partitions a range according to a unary predicate.)
45 $(T2 partition3,
46 Partitions a range according to a binary predicate in three parts (less
47 than, equal, greater than the given pivot). Pivot is not given as an
48 index, but instead as an element independent from the range's content.)
49 $(T2 pivotPartition,
50 Partitions a range according to a binary predicate in two parts: less
51 than or equal, and greater than or equal to the given pivot, passed as
52 an index in the range.)
53 $(T2 schwartzSort,
54 Sorts with the help of the $(LINK2 https://en.wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform).)
55 $(T2 sort,
56 Sorts.)
57 $(T2 topN,
58 Separates the top elements in a range.)
59 $(T2 topNCopy,
60 Copies out the top elements of a range.)
61 $(T2 topNIndex,
62 Builds an index of the top elements of a range.)
63 )
64
65 Copyright: Andrei Alexandrescu 2008-.
66
67 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
68
69 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
70
71 Source: $(PHOBOSSRC std/algorithm/_sorting.d)
72
73 Macros:
74 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
75 */
76 module std.algorithm.sorting;
77
78 import std.algorithm.mutation : SwapStrategy;
79 import std.functional; // : unaryFun, binaryFun;
80 import std.range.primitives;
81 import std.typecons : Flag;
82 // FIXME
83 import std.meta; // : allSatisfy;
84 import std.range; // : SortedRange;
85 import std.traits;
86
87 /**
88 Specifies whether the output of certain algorithm is desired in sorted
89 format.
90
91 If set to $(D SortOutput.no), the output should not be sorted.
92
93 Otherwise if set to $(D SortOutput.yes), the output should be sorted.
94 */
95 alias SortOutput = Flag!"sortOutput";
96
97 // completeSort
98 /**
99 Sorts the random-access range $(D chain(lhs, rhs)) according to
100 predicate $(D less). The left-hand side of the range $(D lhs) is
101 assumed to be already sorted; $(D rhs) is assumed to be unsorted. The
102 exact strategy chosen depends on the relative sizes of $(D lhs) and
103 $(D rhs). Performs $(BIGOH lhs.length + rhs.length * log(rhs.length))
104 (best case) to $(BIGOH (lhs.length + rhs.length) * log(lhs.length +
105 rhs.length)) (worst-case) evaluations of $(D swap).
106
107 Params:
108 less = The predicate to sort by.
109 ss = The swapping strategy to use.
110 lhs = The sorted, left-hand side of the random access range to be sorted.
111 rhs = The unsorted, right-hand side of the random access range to be
112 sorted.
113 */
114 void completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
115 RandomAccessRange1, RandomAccessRange2)(SortedRange!(RandomAccessRange1, less) lhs, RandomAccessRange2 rhs)
116 if (hasLength!(RandomAccessRange2) && hasSlicing!(RandomAccessRange2))
117 {
118 import std.algorithm.mutation : bringToFront;
119 import std.range : chain, assumeSorted;
120 // Probably this algorithm can be optimized by using in-place
121 // merge
122 auto lhsOriginal = lhs.release();
123 foreach (i; 0 .. rhs.length)
124 {
125 auto sortedSoFar = chain(lhsOriginal, rhs[0 .. i]);
126 auto ub = assumeSorted!less(sortedSoFar).upperBound(rhs[i]);
127 if (!ub.length) continue;
128 bringToFront(ub.release(), rhs[i .. i + 1]);
129 }
130 }
131
132 ///
133 @safe unittest
134 {
135 import std.range : assumeSorted;
136 int[] a = [ 1, 2, 3 ];
137 int[] b = [ 4, 0, 6, 5 ];
138 completeSort(assumeSorted(a), b);
139 assert(a == [ 0, 1, 2 ]);
140 assert(b == [ 3, 4, 5, 6 ]);
141 }
142
143 // isSorted
144 /**
145 Checks whether a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
146 is sorted according to the comparison operation $(D less). Performs $(BIGOH r.length)
147 evaluations of $(D less).
148
149 Unlike `isSorted`, `isStrictlyMonotonic` does not allow for equal values,
150 i.e. values for which both `less(a, b)` and `less(b, a)` are false.
151
152 With either function, the predicate must be a strict ordering just like with
153 `isSorted`. For example, using `"a <= b"` instead of `"a < b"` is
154 incorrect and will cause failed assertions.
155
156 Params:
157 less = Predicate the range should be sorted by.
158 r = Forward range to check for sortedness.
159
160 Returns:
161 `true` if the range is sorted, false otherwise. `isSorted` allows
162 duplicates, `isStrictlyMonotonic` not.
163 */
164 bool isSorted(alias less = "a < b", Range)(Range r)
165 if (isForwardRange!(Range))
166 {
167 if (r.empty) return true;
168
169 static if (isRandomAccessRange!Range && hasLength!Range)
170 {
171 immutable limit = r.length - 1;
172 foreach (i; 0 .. limit)
173 {
174 if (!binaryFun!less(r[i + 1], r[i])) continue;
175 assert(
176 !binaryFun!less(r[i], r[i + 1]),
177 "Predicate for isSorted is not antisymmetric. Both" ~
178 " pred(a, b) and pred(b, a) are true for certain values.");
179 return false;
180 }
181 }
182 else
183 {
184 auto ahead = r.save;
185 ahead.popFront();
186 size_t i;
187
188 for (; !ahead.empty; ahead.popFront(), r.popFront(), ++i)
189 {
190 if (!binaryFun!less(ahead.front, r.front)) continue;
191 // Check for antisymmetric predicate
192 assert(
193 !binaryFun!less(r.front, ahead.front),
194 "Predicate for isSorted is not antisymmetric. Both" ~
195 " pred(a, b) and pred(b, a) are true for certain values.");
196 return false;
197 }
198 }
199 return true;
200 }
201
202 ///
203 @safe unittest
204 {
205 assert([1, 1, 2].isSorted);
206 // strictly monotonic doesn't allow duplicates
207 assert(![1, 1, 2].isStrictlyMonotonic);
208
209 int[] arr = [4, 3, 2, 1];
210 assert(!isSorted(arr));
211 assert(!isStrictlyMonotonic(arr));
212
213 assert(isSorted!"a > b"(arr));
214 assert(isStrictlyMonotonic!"a > b"(arr));
215
216 sort(arr);
217 assert(isSorted(arr));
218 assert(isStrictlyMonotonic(arr));
219 }
220
221 @safe unittest
222 {
223 import std.conv : to;
224
225 // Issue 9457
226 auto x = "abcd";
227 assert(isSorted(x));
228 auto y = "acbd";
229 assert(!isSorted(y));
230
231 int[] a = [1, 2, 3];
232 assert(isSorted(a));
233 int[] b = [1, 3, 2];
234 assert(!isSorted(b));
235
236 // ignores duplicates
237 int[] c = [1, 1, 2];
238 assert(isSorted(c));
239
240 dchar[] ds = "コーヒーが好きです"d.dup;
241 sort(ds);
242 string s = to!string(ds);
243 assert(isSorted(ds)); // random-access
244 assert(isSorted(s)); // bidirectional
245 }
246
247 @nogc @safe nothrow pure unittest
248 {
249 static immutable a = [1, 2, 3];
250 assert(a.isSorted);
251 }
252
253 /// ditto
254 bool isStrictlyMonotonic(alias less = "a < b", Range)(Range r)
255 if (isForwardRange!Range)
256 {
257 import std.algorithm.searching : findAdjacent;
258 return findAdjacent!((a,b) => !binaryFun!less(a,b))(r).empty;
259 }
260
261 @safe unittest
262 {
263 import std.conv : to;
264
265 assert("abcd".isStrictlyMonotonic);
266 assert(!"aacd".isStrictlyMonotonic);
267 assert(!"acb".isStrictlyMonotonic);
268
269 assert([1, 2, 3].isStrictlyMonotonic);
270 assert(![1, 3, 2].isStrictlyMonotonic);
271 assert(![1, 1, 2].isStrictlyMonotonic);
272
273 // ー occurs twice -> can't be strict
274 dchar[] ds = "コーヒーが好きです"d.dup;
275 sort(ds);
276 string s = to!string(ds);
277 assert(!isStrictlyMonotonic(ds)); // random-access
278 assert(!isStrictlyMonotonic(s)); // bidirectional
279
280 dchar[] ds2 = "コーヒが好きです"d.dup;
281 sort(ds2);
282 string s2 = to!string(ds2);
283 assert(isStrictlyMonotonic(ds2)); // random-access
284 assert(isStrictlyMonotonic(s2)); // bidirectional
285 }
286
287 @nogc @safe nothrow pure unittest
288 {
289 static immutable a = [1, 2, 3];
290 assert(a.isStrictlyMonotonic);
291 }
292
293 /**
294 Like $(D isSorted), returns $(D true) if the given $(D values) are ordered
295 according to the comparison operation $(D less). Unlike $(D isSorted), takes values
296 directly instead of structured in a range.
297
298 $(D ordered) allows repeated values, e.g. $(D ordered(1, 1, 2)) is $(D true). To verify
299 that the values are ordered strictly monotonically, use $(D strictlyOrdered);
300 $(D strictlyOrdered(1, 1, 2)) is $(D false).
301
302 With either function, the predicate must be a strict ordering. For example,
303 using $(D "a <= b") instead of $(D "a < b") is incorrect and will cause failed
304 assertions.
305
306 Params:
307 values = The tested value
308 less = The comparison predicate
309
310 Returns:
311 $(D true) if the values are ordered; $(D ordered) allows for duplicates,
312 $(D strictlyOrdered) does not.
313 */
314
315 bool ordered(alias less = "a < b", T...)(T values)
316 if ((T.length == 2 && is(typeof(binaryFun!less(values[1], values[0])) : bool))
317 ||
318 (T.length > 2 && is(typeof(ordered!less(values[0 .. 1 + $ / 2])))
319 && is(typeof(ordered!less(values[$ / 2 .. $]))))
320 )
321 {
foreach(i,_;T[0..$-1])322 foreach (i, _; T[0 .. $ - 1])
323 {
324 if (binaryFun!less(values[i + 1], values[i]))
325 {
326 assert(!binaryFun!less(values[i], values[i + 1]),
327 __FUNCTION__ ~ ": incorrect non-strict predicate.");
328 return false;
329 }
330 }
331 return true;
332 }
333
334 /// ditto
335 bool strictlyOrdered(alias less = "a < b", T...)(T values)
336 if (is(typeof(ordered!less(values))))
337 {
foreach(i,_;T[0..$-1])338 foreach (i, _; T[0 .. $ - 1])
339 {
340 if (!binaryFun!less(values[i], values[i + 1]))
341 {
342 return false;
343 }
344 assert(!binaryFun!less(values[i + 1], values[i]),
345 __FUNCTION__ ~ ": incorrect non-strict predicate.");
346 }
347 return true;
348 }
349
350 ///
351 @safe unittest
352 {
353 assert(ordered(42, 42, 43));
354 assert(!strictlyOrdered(43, 42, 45));
355 assert(ordered(42, 42, 43));
356 assert(!strictlyOrdered(42, 42, 43));
357 assert(!ordered(43, 42, 45));
358 // Ordered lexicographically
359 assert(ordered("Jane", "Jim", "Joe"));
360 assert(strictlyOrdered("Jane", "Jim", "Joe"));
361 // Incidentally also ordered by length decreasing
362 assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
363 // ... but not strictly so: "Jim" and "Joe" have the same length
364 assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
365 }
366
367 // partition
368 /**
369 Partitions a range in two using the given $(D predicate).
370 Specifically, reorders the range $(D r = [left, right$(RPAREN)) using $(D swap)
371 such that all elements $(D i) for which $(D predicate(i)) is $(D true) come
372 before all elements $(D j) for which $(D predicate(j)) returns $(D false).
373
374 Performs $(BIGOH r.length) (if unstable or semistable) or $(BIGOH
375 r.length * log(r.length)) (if stable) evaluations of $(D less) and $(D
376 swap). The unstable version computes the minimum possible evaluations
377 of $(D swap) (roughly half of those performed by the semistable
378 version).
379
380 Params:
381 predicate = The predicate to partition by.
382 ss = The swapping strategy to employ.
383 r = The random-access range to partition.
384
385 Returns:
386
387 The right part of $(D r) after partitioning.
388
389 If $(D ss == SwapStrategy.stable), $(D partition) preserves the relative
390 ordering of all elements $(D a), $(D b) in $(D r) for which $(D predicate(a) ==
391 predicate(b)). If $(D ss == SwapStrategy.semistable), $(D partition) preserves
392 the relative ordering of all elements $(D a), $(D b) in the left part of $(D r)
393 for which $(D predicate(a) == predicate(b)).
394
395 See_Also:
396 STL's $(HTTP sgi.com/tech/stl/_partition.html, _partition)$(BR)
397 STL's $(HTTP sgi.com/tech/stl/stable_partition.html, stable_partition)
398 */
399 Range partition(alias predicate, SwapStrategy ss, Range)(Range r)
400 if (ss == SwapStrategy.stable && isRandomAccessRange!(Range) && hasLength!Range && hasSlicing!Range)
401 {
402 import std.algorithm.mutation : bringToFront;
403
404 alias pred = unaryFun!(predicate);
405 if (r.empty) return r;
406
407 if (r.length == 1)
408 {
409 if (pred(r.front)) r.popFront();
410 return r;
411 }
412 const middle = r.length / 2;
413 alias recurse = .partition!(pred, ss, Range);
414 auto lower = recurse(r[0 .. middle]);
415 auto upper = recurse(r[middle .. r.length]);
416 bringToFront(lower, r[middle .. r.length - upper.length]);
417 return r[r.length - lower.length - upper.length .. r.length];
418 }
419
420 ///ditto
421 Range partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range r)
422 if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range)
423 {
424 import std.algorithm.mutation : swap;
425 alias pred = unaryFun!(predicate);
426
427 static if (ss == SwapStrategy.semistable)
428 {
429 if (r.empty) return r;
430
431 for (; !r.empty; r.popFront())
432 {
433 // skip the initial portion of "correct" elements
434 if (pred(r.front)) continue;
435 // hit the first "bad" element
436 auto result = r;
437 for (r.popFront(); !r.empty; r.popFront())
438 {
439 if (!pred(r.front)) continue;
440 swap(result.front, r.front);
441 result.popFront();
442 }
443 return result;
444 }
445
446 return r;
447 }
448 else
449 {
450 // Inspired from www.stepanovpapers.com/PAM3-partition_notes.pdf,
451 // section "Bidirectional Partition Algorithm (Hoare)"
452 static if (isDynamicArray!Range)
453 {
454 import std.algorithm.mutation : swapAt;
455 // For dynamic arrays prefer index-based manipulation
456 if (!r.length) return r;
457 size_t lo = 0, hi = r.length - 1;
458 for (;;)
459 {
460 for (;;)
461 {
462 if (lo > hi) return r[lo .. r.length];
463 if (!pred(r[lo])) break;
464 ++lo;
465 }
466 // found the left bound
467 assert(lo <= hi);
468 for (;;)
469 {
470 if (lo == hi) return r[lo .. r.length];
471 if (pred(r[hi])) break;
472 --hi;
473 }
474 // found the right bound, swap & make progress
475 r.swapAt(lo++, hi--);
476 }
477 }
478 else
479 {
480 import std.algorithm.mutation : swap;
481 auto result = r;
482 for (;;)
483 {
484 for (;;)
485 {
486 if (r.empty) return result;
487 if (!pred(r.front)) break;
488 r.popFront();
489 result.popFront();
490 }
491 // found the left bound
492 assert(!r.empty);
493 for (;;)
494 {
495 if (pred(r.back)) break;
496 r.popBack();
497 if (r.empty) return result;
498 }
499 // found the right bound, swap & make progress
500 static if (is(typeof(swap(r.front, r.back))))
501 {
502 swap(r.front, r.back);
503 }
504 else
505 {
506 auto t1 = r.moveFront(), t2 = r.moveBack();
507 r.front = t2;
508 r.back = t1;
509 }
510 r.popFront();
511 result.popFront();
512 r.popBack();
513 }
514 }
515 }
516 }
517
518 ///
519 @safe unittest
520 {
521 import std.algorithm.mutation : SwapStrategy;
522 import std.algorithm.searching : count, find;
523 import std.conv : text;
524 import std.range.primitives : empty;
525
526 auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
527 auto arr = Arr.dup;
even(int a)528 static bool even(int a) { return (a & 1) == 0; }
529 // Partition arr such that even numbers come first
530 auto r = partition!(even)(arr);
531 // Now arr is separated in evens and odds.
532 // Numbers may have become shuffled due to instability
533 assert(r == arr[5 .. $]);
534 assert(count!(even)(arr[0 .. 5]) == 5);
535 assert(find!(even)(r).empty);
536
537 // Can also specify the predicate as a string.
538 // Use 'a' as the predicate argument name
539 arr[] = Arr[];
540 r = partition!(q{(a & 1) == 0})(arr);
541 assert(r == arr[5 .. $]);
542
543 // Now for a stable partition:
544 arr[] = Arr[];
545 r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
546 // Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1
547 assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);
548
549 // In case the predicate needs to hold its own state, use a delegate:
550 arr[] = Arr[];
551 int x = 3;
552 // Put stuff greater than 3 on the left
fun(int a)553 bool fun(int a) { return a > x; }
554 r = partition!(fun, SwapStrategy.semistable)(arr);
555 // Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2
556 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
557 }
558
559 @safe unittest
560 {
561 import std.algorithm.internal : rndstuff;
even(int a)562 static bool even(int a) { return (a & 1) == 0; }
563
564 // test with random data
565 auto a = rndstuff!int();
566 partition!even(a);
567 assert(isPartitioned!even(a));
568 auto b = rndstuff!string();
569 partition!`a.length < 5`(b);
570 assert(isPartitioned!`a.length < 5`(b));
571 }
572
573 // pivotPartition
574 /**
575
576 Partitions `r` around `pivot` using comparison function `less`, algorithm akin
577 to $(LINK2 https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme,
578 Hoare partition). Specifically, permutes elements of `r` and returns
579 an index $(D k < r.length) such that:
580
581 $(UL
582
583 $(LI `r[pivot]` is swapped to `r[k]`)
584
585 $(LI All elements `e` in subrange $(D r[0 .. k]) satisfy $(D !less(r[k], e))
586 (i.e. `r[k]` is greater than or equal to each element to its left according to
587 predicate `less`))
588
589 $(LI All elements `e` in subrange $(D r[0 .. k]) satisfy $(D !less(e,
590 r[k])) (i.e. `r[k]` is less than or equal to each element to its right
591 according to predicate `less`)))
592
593 If `r` contains equivalent elements, multiple permutations of `r` satisfy these
594 constraints. In such cases, `pivotPartition` attempts to distribute equivalent
595 elements fairly to the left and right of `k` such that `k` stays close to $(D
596 r.length / 2).
597
598 Params:
599 less = The predicate used for comparison, modeled as a
600 $(LINK2 https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings,
601 strict weak ordering) (irreflexive, antisymmetric, transitive, and implying a transitive
602 equivalence)
603 r = The range being partitioned
604 pivot = The index of the pivot for partitioning, must be less than `r.length` or
605 `0` is `r.length` is `0`
606
607 Returns:
608 The new position of the pivot
609
610 See_Also:
611 $(HTTP jgrcs.info/index.php/jgrcs/article/view/142, Engineering of a Quicksort
612 Partitioning Algorithm), D. Abhyankar, Journal of Global Research in Computer
613 Science, February 2011. $(HTTPS youtube.com/watch?v=AxnotgLql0k, ACCU 2016
614 Keynote), Andrei Alexandrescu.
615 */
616 size_t pivotPartition(alias less = "a < b", Range)
617 (Range r, size_t pivot)
618 if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range)
619 {
620 assert(pivot < r.length || r.length == 0 && pivot == 0);
621 if (r.length <= 1) return 0;
622 import std.algorithm.mutation : swapAt, move;
623 alias lt = binaryFun!less;
624
625 // Pivot at the front
626 r.swapAt(pivot, 0);
627
628 // Fork implementation depending on nothrow copy, assignment, and
629 // comparison. If all of these are nothrow, use the specialized
630 // implementation discussed at https://youtube.com/watch?v=AxnotgLql0k.
631 static if (is(typeof(
632 () nothrow { auto x = r.front; x = r.front; return lt(x, x); }
633 )))
634 {
635 auto p = r[0];
636 // Plant the pivot in the end as well as a sentinel
637 size_t lo = 0, hi = r.length - 1;
638 auto save = move(r[hi]);
639 r[hi] = p; // Vacancy is in r[$ - 1] now
640 // Start process
641 for (;;)
642 {
643 // Loop invariant
version(unittest)644 version (unittest)
645 {
646 import std.algorithm.searching : all;
647 assert(r[0 .. lo].all!(x => !lt(p, x)));
648 assert(r[hi + 1 .. r.length].all!(x => !lt(x, p)));
649 }
650 do ++lo; while (lt(r[lo], p));
651 r[hi] = r[lo];
652 // Vacancy is now in r[lo]
653 do --hi; while (lt(p, r[hi]));
654 if (lo >= hi) break;
655 r[lo] = r[hi];
656 // Vacancy is not in r[hi]
657 }
658 // Fixup
659 assert(lo - hi <= 2);
660 assert(!lt(p, r[hi]));
661 if (lo == hi + 2)
662 {
663 assert(!lt(r[hi + 1], p));
664 r[lo] = r[hi + 1];
665 --lo;
666 }
667 r[lo] = save;
668 if (lt(p, save)) --lo;
669 assert(!lt(p, r[lo]));
670 }
671 else
672 {
673 size_t lo = 1, hi = r.length - 1;
674 loop: for (;; lo++, hi--)
675 {
676 for (;; ++lo)
677 {
678 if (lo > hi) break loop;
679 if (!lt(r[lo], r[0])) break;
680 }
681 // found the left bound: r[lo] >= r[0]
682 assert(lo <= hi);
683 for (;; --hi)
684 {
685 if (lo >= hi) break loop;
686 if (!lt(r[0], r[hi])) break;
687 }
688 // found the right bound: r[hi] <= r[0], swap & make progress
689 assert(!lt(r[lo], r[hi]));
690 r.swapAt(lo, hi);
691 }
692 --lo;
693 }
694 r.swapAt(lo, 0);
695 return lo;
696 }
697
698 ///
699 @safe nothrow unittest
700 {
701 int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
702 size_t pivot = pivotPartition(a, a.length / 2);
703 import std.algorithm.searching : all;
704 assert(a[0 .. pivot].all!(x => x <= a[pivot]));
705 assert(a[pivot .. $].all!(x => x >= a[pivot]));
706 }
707
708 @safe unittest
709 {
test(alias less)710 void test(alias less)()
711 {
712 int[] a;
713 size_t pivot;
714
715 a = [-9, -4, -2, -2, 9];
716 pivot = pivotPartition!less(a, a.length / 2);
717 import std.algorithm.searching : all;
718 assert(a[0 .. pivot].all!(x => x <= a[pivot]));
719 assert(a[pivot .. $].all!(x => x >= a[pivot]));
720
721 a = [9, 2, 8, -5, 5, 4, -8, -4, 9];
722 pivot = pivotPartition!less(a, a.length / 2);
723 assert(a[0 .. pivot].all!(x => x <= a[pivot]));
724 assert(a[pivot .. $].all!(x => x >= a[pivot]));
725
726 a = [ 42 ];
727 pivot = pivotPartition!less(a, a.length / 2);
728 assert(pivot == 0);
729 assert(a == [ 42 ]);
730
731 a = [ 43, 42 ];
732 pivot = pivotPartition!less(a, 0);
733 assert(pivot == 1);
734 assert(a == [ 42, 43 ]);
735
736 a = [ 43, 42 ];
737 pivot = pivotPartition!less(a, 1);
738 assert(pivot == 0);
739 assert(a == [ 42, 43 ]);
740
741 a = [ 42, 42 ];
742 pivot = pivotPartition!less(a, 0);
743 assert(pivot == 0 || pivot == 1);
744 assert(a == [ 42, 42 ]);
745 pivot = pivotPartition!less(a, 1);
746 assert(pivot == 0 || pivot == 1);
747 assert(a == [ 42, 42 ]);
748
749 import std.algorithm.iteration : map;
750 import std.random;
751 import std.stdio;
752 auto s = unpredictableSeed;
753 auto g = Random(s);
754 a = iota(0, uniform(1, 1000, g))
755 .map!(_ => uniform(-1000, 1000, g))
756 .array;
757 scope(failure) writeln("RNG seed was ", s);
758 pivot = pivotPartition!less(a, a.length / 2);
759 assert(a[0 .. pivot].all!(x => x <= a[pivot]));
760 assert(a[pivot .. $].all!(x => x >= a[pivot]));
761 }
762 test!"a < b";
myLess(int a,int b)763 static bool myLess(int a, int b)
764 {
765 static bool bogus;
766 if (bogus) throw new Exception(""); // just to make it no-nothrow
767 return a < b;
768 }
769 test!myLess;
770 }
771
772 /**
773 Params:
774 pred = The predicate that the range should be partitioned by.
775 r = The range to check.
776 Returns: $(D true) if $(D r) is partitioned according to predicate $(D pred).
777 */
778 bool isPartitioned(alias pred, Range)(Range r)
779 if (isForwardRange!(Range))
780 {
781 for (; !r.empty; r.popFront())
782 {
783 if (unaryFun!(pred)(r.front)) continue;
784 for (r.popFront(); !r.empty; r.popFront())
785 {
786 if (unaryFun!(pred)(r.front)) return false;
787 }
788 break;
789 }
790 return true;
791 }
792
793 ///
794 @safe unittest
795 {
796 int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
797 assert(isPartitioned!"a & 1"(r));
798 }
799
800 // partition3
801 /**
802 Rearranges elements in $(D r) in three adjacent ranges and returns
803 them. The first and leftmost range only contains elements in $(D r)
804 less than $(D pivot). The second and middle range only contains
805 elements in $(D r) that are equal to $(D pivot). Finally, the third
806 and rightmost range only contains elements in $(D r) that are greater
807 than $(D pivot). The less-than test is defined by the binary function
808 $(D less).
809
810 Params:
811 less = The predicate to use for the rearrangement.
812 ss = The swapping strategy to use.
813 r = The random-access range to rearrange.
814 pivot = The pivot element.
815
816 Returns:
817 A $(REF Tuple, std,typecons) of the three resulting ranges. These ranges are
818 slices of the original range.
819
820 BUGS: stable $(D partition3) has not been implemented yet.
821 */
822 auto partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)
823 (Range r, E pivot)
824 if (ss == SwapStrategy.unstable && isRandomAccessRange!Range
825 && hasSwappableElements!Range && hasLength!Range && hasSlicing!Range
826 && is(typeof(binaryFun!less(r.front, pivot)) == bool)
827 && is(typeof(binaryFun!less(pivot, r.front)) == bool)
828 && is(typeof(binaryFun!less(r.front, r.front)) == bool))
829 {
830 // The algorithm is described in "Engineering a sort function" by
831 // Jon Bentley et al, pp 1257.
832
833 import std.algorithm.comparison : min;
834 import std.algorithm.mutation : swap, swapAt, swapRanges;
835 import std.typecons : tuple;
836
837 alias lessFun = binaryFun!less;
838 size_t i, j, k = r.length, l = k;
839
840 bigloop:
841 for (;;)
842 {
843 for (;; ++j)
844 {
845 if (j == k) break bigloop;
846 assert(j < r.length);
847 if (lessFun(r[j], pivot)) continue;
848 if (lessFun(pivot, r[j])) break;
849 r.swapAt(i++, j);
850 }
851 assert(j < k);
852 for (;;)
853 {
854 assert(k > 0);
855 if (!lessFun(pivot, r[--k]))
856 {
857 if (lessFun(r[k], pivot)) break;
858 r.swapAt(k, --l);
859 }
860 if (j == k) break bigloop;
861 }
862 // Here we know r[j] > pivot && r[k] < pivot
863 r.swapAt(j++, k);
864 }
865
866 // Swap the equal ranges from the extremes into the middle
867 auto strictlyLess = j - i, strictlyGreater = l - k;
868 auto swapLen = min(i, strictlyLess);
869 swapRanges(r[0 .. swapLen], r[j - swapLen .. j]);
870 swapLen = min(r.length - l, strictlyGreater);
871 swapRanges(r[k .. k + swapLen], r[r.length - swapLen .. r.length]);
872 return tuple(r[0 .. strictlyLess],
873 r[strictlyLess .. r.length - strictlyGreater],
874 r[r.length - strictlyGreater .. r.length]);
875 }
876
877 ///
878 @safe unittest
879 {
880 auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
881 auto pieces = partition3(a, 4);
882 assert(pieces[0] == [ 1, 3 ]);
883 assert(pieces[1] == [ 4, 4, 4 ]);
884 assert(pieces[2] == [ 8, 7 ]);
885 }
886
887 @safe unittest
888 {
889 import std.random : Random, uniform, unpredictableSeed;
890
891 immutable uint[] seeds = [3923355730, 1927035882, unpredictableSeed];
foreach(s;seeds)892 foreach (s; seeds)
893 {
894 auto r = Random(s);
895 auto a = new int[](uniform(0, 100, r));
896 foreach (ref e; a)
897 {
898 e = uniform(0, 50, r);
899 }
900 auto pieces = partition3(a, 25);
901 assert(pieces[0].length + pieces[1].length + pieces[2].length == a.length);
902 foreach (e; pieces[0])
903 {
904 assert(e < 25);
905 }
906 foreach (e; pieces[1])
907 {
908 assert(e == 25);
909 }
910 foreach (e; pieces[2])
911 {
912 assert(e > 25);
913 }
914 }
915 }
916
917 // makeIndex
918 /**
919 Computes an index for $(D r) based on the comparison $(D less). The
920 index is a sorted array of pointers or indices into the original
921 range. This technique is similar to sorting, but it is more flexible
922 because (1) it allows "sorting" of immutable collections, (2) allows
923 binary search even if the original collection does not offer random
924 access, (3) allows multiple indexes, each on a different predicate,
925 and (4) may be faster when dealing with large objects. However, using
926 an index may also be slower under certain circumstances due to the
927 extra indirection, and is always larger than a sorting-based solution
928 because it needs space for the index in addition to the original
929 collection. The complexity is the same as $(D sort)'s.
930
931 The first overload of $(D makeIndex) writes to a range containing
932 pointers, and the second writes to a range containing offsets. The
933 first overload requires $(D Range) to be a
934 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives), and the
935 latter requires it to be a random-access range.
936
937 $(D makeIndex) overwrites its second argument with the result, but
938 never reallocates it.
939
940 Params:
941 less = The comparison to use.
942 ss = The swapping strategy.
943 r = The range to index.
944 index = The resulting index.
945
946 Returns: The pointer-based version returns a $(D SortedRange) wrapper
947 over index, of type $(D SortedRange!(RangeIndex, (a, b) =>
948 binaryFun!less(*a, *b))) thus reflecting the ordering of the
949 index. The index-based version returns $(D void) because the ordering
950 relation involves not only $(D index) but also $(D r).
951
952 Throws: If the second argument's length is less than that of the range
953 indexed, an exception is thrown.
954 */
955 SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))
956 makeIndex(
957 alias less = "a < b",
958 SwapStrategy ss = SwapStrategy.unstable,
959 Range,
960 RangeIndex)
961 (Range r, RangeIndex index)
962 if (isForwardRange!(Range) && isRandomAccessRange!(RangeIndex)
963 && is(ElementType!(RangeIndex) : ElementType!(Range)*))
964 {
965 import std.algorithm.internal : addressOf;
966 import std.exception : enforce;
967
968 // assume collection already ordered
969 size_t i;
970 for (; !r.empty; r.popFront(), ++i)
971 index[i] = addressOf(r.front);
972 enforce(index.length == i);
973 // sort the index
974 sort!((a, b) => binaryFun!less(*a, *b), ss)(index);
975 return typeof(return)(index);
976 }
977
978 /// Ditto
979 void makeIndex(
980 alias less = "a < b",
981 SwapStrategy ss = SwapStrategy.unstable,
982 Range,
983 RangeIndex)
984 (Range r, RangeIndex index)
985 if (isRandomAccessRange!Range && !isInfinite!Range &&
986 isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex &&
987 isIntegral!(ElementType!RangeIndex))
988 {
989 import std.conv : to;
990 import std.exception : enforce;
991
992 alias IndexType = Unqual!(ElementType!RangeIndex);
993 enforce(r.length == index.length,
994 "r and index must be same length for makeIndex.");
995 static if (IndexType.sizeof < size_t.sizeof)
996 {
997 enforce(r.length <= size_t(1) + IndexType.max, "Cannot create an index with " ~
998 "element type " ~ IndexType.stringof ~ " with length " ~
999 to!string(r.length) ~ ".");
1000 }
1001
1002 // Use size_t as loop index to avoid overflow on ++i,
1003 // e.g. when squeezing 256 elements into a ubyte index.
1004 foreach (size_t i; 0 .. r.length)
1005 index[i] = cast(IndexType) i;
1006
1007 // sort the index
1008 sort!((a, b) => binaryFun!less(r[cast(size_t) a], r[cast(size_t) b]), ss)
1009 (index);
1010 }
1011
1012 ///
1013 @system unittest
1014 {
1015 immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
1016 // index using pointers
1017 auto index1 = new immutable(int)*[arr.length];
1018 makeIndex!("a < b")(arr, index1);
1019 assert(isSorted!("*a < *b")(index1));
1020 // index using offsets
1021 auto index2 = new size_t[arr.length];
1022 makeIndex!("a < b")(arr, index2);
1023 assert(isSorted!
1024 ((size_t a, size_t b){ return arr[a] < arr[b];})
1025 (index2));
1026 }
1027
1028 @system unittest
1029 {
1030 immutable(int)[] arr = [ 2, 3, 1, 5, 0 ];
1031 // index using pointers
1032 auto index1 = new immutable(int)*[arr.length];
1033 alias ImmRange = typeof(arr);
1034 alias ImmIndex = typeof(index1);
1035 static assert(isForwardRange!(ImmRange));
1036 static assert(isRandomAccessRange!(ImmIndex));
1037 static assert(!isIntegral!(ElementType!(ImmIndex)));
1038 static assert(is(ElementType!(ImmIndex) : ElementType!(ImmRange)*));
1039 makeIndex!("a < b")(arr, index1);
1040 assert(isSorted!("*a < *b")(index1));
1041
1042 // index using offsets
1043 auto index2 = new long[arr.length];
1044 makeIndex(arr, index2);
1045 assert(isSorted!
1046 ((long a, long b){
1047 return arr[cast(size_t) a] < arr[cast(size_t) b];
1048 })(index2));
1049
1050 // index strings using offsets
1051 string[] arr1 = ["I", "have", "no", "chocolate"];
1052 auto index3 = new byte[arr1.length];
1053 makeIndex(arr1, index3);
1054 assert(isSorted!
1055 ((byte a, byte b){ return arr1[a] < arr1[b];})
1056 (index3));
1057 }
1058
1059 @safe unittest
1060 {
1061 import std.algorithm.comparison : equal;
1062
1063 ubyte[256] index = void;
1064 iota(256).makeIndex(index[]);
1065 assert(index[].equal(iota(256)));
1066 byte[128] sindex = void;
1067 iota(128).makeIndex(sindex[]);
1068 assert(sindex[].equal(iota(128)));
1069
1070 auto index2 = new uint[10];
1071 10.iota.makeIndex(index2);
1072 assert(index2.equal(10.iota));
1073 }
1074
1075 struct Merge(alias less = "a < b", Rs...)
1076 if (Rs.length >= 2 &&
1077 allSatisfy!(isInputRange, Rs) &&
1078 !is(CommonType!(staticMap!(ElementType, Rs)) == void))
1079 {
1080 public Rs source;
1081 private size_t _lastFrontIndex = size_t.max;
1082 static if (isBidirectional)
1083 {
1084 private size_t _lastBackIndex = size_t.max; // `size_t.max` means uninitialized,
1085 }
1086
1087 import std.functional : binaryFun;
1088 import std.traits : isCopyable;
1089 import std.typetuple : anySatisfy;
1090
1091 private alias comp = binaryFun!less;
1092 private alias ElementType = CommonType!(staticMap!(.ElementType, Rs));
1093 private enum isBidirectional = allSatisfy!(isBidirectionalRange, staticMap!(Unqual, Rs));
1094
1095 debug private enum canCheckSortedness = isCopyable!ElementType && !hasAliasing!ElementType;
1096
thisMerge1097 this(Rs source)
1098 {
1099 this.source = source;
1100 this._lastFrontIndex = frontIndex;
1101 }
1102
1103 static if (anySatisfy!(isInfinite, Rs))
1104 {
1105 enum bool empty = false; // propagate infiniteness
1106 }
1107 else
1108 {
emptyMerge1109 @property bool empty()
1110 {
1111 return _lastFrontIndex == size_t.max;
1112 }
1113 }
1114
frontMerge1115 @property auto ref front()
1116 {
1117 final switch (_lastFrontIndex)
1118 {
1119 foreach (i, _; Rs)
1120 {
1121 case i:
1122 assert(!source[i].empty);
1123 return source[i].front;
1124 }
1125 }
1126 }
1127
frontIndexMerge1128 private size_t frontIndex()
1129 {
1130 size_t bestIndex = size_t.max; // indicate undefined
1131 Unqual!ElementType bestElement;
1132 foreach (i, _; Rs)
1133 {
1134 if (source[i].empty) continue;
1135 if (bestIndex == size_t.max || // either this is the first or
1136 comp(source[i].front, bestElement))
1137 {
1138 bestIndex = i;
1139 bestElement = source[i].front;
1140 }
1141 }
1142 return bestIndex;
1143 }
1144
popFrontMerge1145 void popFront()
1146 {
1147 sw: final switch (_lastFrontIndex)
1148 {
1149 foreach (i, R; Rs)
1150 {
1151 case i:
1152 debug static if (canCheckSortedness)
1153 {
1154 ElementType previousFront = source[i].front();
1155 }
1156 source[i].popFront();
1157 debug static if (canCheckSortedness)
1158 {
1159 if (!source[i].empty)
1160 {
1161 assert(previousFront == source[i].front ||
1162 comp(previousFront, source[i].front),
1163 "Input " ~ i.stringof ~ " is unsorted"); // @nogc
1164 }
1165 }
1166 break sw;
1167 }
1168 }
1169 _lastFrontIndex = frontIndex;
1170 }
1171
1172 static if (isBidirectional)
1173 {
backMerge1174 @property auto ref back()
1175 {
1176 if (_lastBackIndex == size_t.max)
1177 {
1178 this._lastBackIndex = backIndex; // lazy initialization
1179 }
1180 final switch (_lastBackIndex)
1181 {
1182 foreach (i, _; Rs)
1183 {
1184 case i:
1185 assert(!source[i].empty);
1186 return source[i].back;
1187 }
1188 }
1189 }
1190
backIndexMerge1191 private size_t backIndex()
1192 {
1193 size_t bestIndex = size_t.max; // indicate undefined
1194 Unqual!ElementType bestElement;
1195 foreach (i, _; Rs)
1196 {
1197 if (source[i].empty) continue;
1198 if (bestIndex == size_t.max || // either this is the first or
1199 comp(bestElement, source[i].back))
1200 {
1201 bestIndex = i;
1202 bestElement = source[i].back;
1203 }
1204 }
1205 return bestIndex;
1206 }
1207
popBackMerge1208 void popBack()
1209 {
1210 if (_lastBackIndex == size_t.max)
1211 {
1212 this._lastBackIndex = backIndex; // lazy initialization
1213 }
1214 sw: final switch (_lastBackIndex)
1215 {
1216 foreach (i, R; Rs)
1217 {
1218 case i:
1219 debug static if (canCheckSortedness)
1220 {
1221 ElementType previousBack = source[i].back();
1222 }
1223 source[i].popBack();
1224 debug static if (canCheckSortedness)
1225 {
1226 if (!source[i].empty)
1227 {
1228 assert(previousBack == source[i].back ||
1229 comp(source[i].back, previousBack),
1230 "Input " ~ i.stringof ~ " is unsorted"); // @nogc
1231 }
1232 }
1233 break sw;
1234 }
1235 }
1236 _lastBackIndex = backIndex;
1237 if (_lastBackIndex == size_t.max) // if emptied
1238 {
1239 _lastFrontIndex = size_t.max;
1240 }
1241 }
1242 }
1243
1244 static if (allSatisfy!(isForwardRange, staticMap!(Unqual, Rs)))
1245 {
saveMerge1246 @property auto save()
1247 {
1248 auto result = this;
1249 foreach (i, _; Rs)
1250 {
1251 result.source[i] = result.source[i].save;
1252 }
1253 return result;
1254 }
1255 }
1256
1257 static if (allSatisfy!(hasLength, Rs))
1258 {
lengthMerge1259 @property size_t length()
1260 {
1261 size_t result;
1262 foreach (i, _; Rs)
1263 {
1264 result += source[i].length;
1265 }
1266 return result;
1267 }
1268
1269 alias opDollar = length;
1270 }
1271 }
1272
1273 /**
1274 Merge multiple sorted ranges `rs` with less-than predicate function `pred`
1275 into one single sorted output range containing the sorted union of the
1276 elements of inputs. Duplicates are not eliminated, meaning that the total
1277 number of elements in the output is the sum of all elements in the ranges
1278 passed to it; the `length` member is offered if all inputs also have
1279 `length`. The element types of all the inputs must have a common type
1280 `CommonType`.
1281
1282 Params:
1283 less = Predicate the given ranges are sorted by.
1284 rs = The ranges to compute the union for.
1285
1286 Returns:
1287 A range containing the union of the given ranges.
1288
1289 Details:
1290
1291 All of its inputs are assumed to be sorted. This can mean that inputs are
1292 instances of $(REF SortedRange, std,range). Use the result of $(REF sort,
1293 std,algorithm,sorting), or $(REF assumeSorted, std,range) to merge ranges
1294 known to be sorted (show in the example below). Note that there is currently
1295 no way of ensuring that two or more instances of $(REF SortedRange,
1296 std,range) are sorted using a specific comparison function `pred`. Therefore
1297 no checking is done here to assure that all inputs `rs` are instances of
1298 $(REF SortedRange, std,range).
1299
1300 This algorithm is lazy, doing work progressively as elements are pulled off
1301 the result.
1302
1303 Time complexity is proportional to the sum of element counts over all inputs.
1304
1305 If all inputs have the same element type and offer it by `ref`, output
1306 becomes a range with mutable `front` (and `back` where appropriate) that
1307 reflects in the original inputs.
1308
1309 If any of the inputs `rs` is infinite so is the result (`empty` being always
1310 `false`).
1311 */
1312 Merge!(less, Rs) merge(alias less = "a < b", Rs...)(Rs rs)
1313 if (Rs.length >= 2 &&
1314 allSatisfy!(isInputRange, Rs) &&
1315 !is(CommonType!(staticMap!(ElementType, Rs)) == void))
1316 {
1317 return typeof(return)(rs);
1318 }
1319
1320 ///
1321 @safe pure nothrow unittest
1322 {
1323 import std.algorithm.comparison : equal;
1324 import std.range : retro;
1325
1326 int[] a = [1, 3, 5];
1327 int[] b = [2, 3, 4];
1328
1329 assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
1330 assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));
1331 }
1332
1333 @safe pure nothrow unittest
1334 {
1335 import std.algorithm.comparison : equal;
1336
1337 int[] a = [ 1, 2, 4, 5, 7, 9 ];
1338 int[] b = [ 0, 1, 2, 4, 7, 8 ];
1339 double[] c = [ 10.5 ];
1340
1341 assert(merge(a, b).length == a.length + b.length);
1342 assert(equal(merge(a, b), [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
1343 assert(equal(merge(a, c, b),
1344 [0, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9, 10.5][]));
1345 auto u = merge(a, b);
1346 u.front--;
1347 assert(equal(u, [-1, 1, 1, 2, 2, 4, 4, 5, 7, 7, 8, 9][]));
1348 }
1349
1350 @safe pure nothrow unittest
1351 {
1352 // save
1353 import std.range : dropOne;
1354 int[] a = [1, 2];
1355 int[] b = [0, 3];
1356 auto arr = a.merge(b);
1357 assert(arr.front == 0);
1358 assert(arr.save.dropOne.front == 1);
1359 assert(arr.front == 0);
1360 }
1361
1362 @safe pure nothrow unittest
1363 {
1364 import std.algorithm.comparison : equal;
1365 import std.internal.test.dummyrange;
1366
1367 auto dummyResult1 = [1, 1, 1.5, 2, 3, 4, 5, 5.5, 6, 7, 8, 9, 10];
1368 auto dummyResult2 = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5,
1369 6, 6, 7, 7, 8, 8, 9, 9, 10, 10];
foreach(DummyType;AllDummyRanges)1370 foreach (DummyType; AllDummyRanges)
1371 {
1372 DummyType d;
1373 assert(d.merge([1, 1.5, 5.5]).equal(dummyResult1));
1374 assert(d.merge(d).equal(dummyResult2));
1375 }
1376 }
1377
1378 @nogc @safe pure nothrow unittest
1379 {
1380 import std.algorithm.comparison : equal;
1381
1382 static immutable a = [1, 3, 5];
1383 static immutable b = [2, 3, 4];
1384 static immutable r = [1, 2, 3, 3, 4, 5];
1385 assert(a.merge(b).equal(r));
1386 }
1387
1388 /// test bi-directional access and common type
1389 @safe pure nothrow unittest
1390 {
1391 import std.algorithm.comparison : equal;
1392 import std.range : retro;
1393 import std.traits : CommonType;
1394
1395 alias S = short;
1396 alias I = int;
1397 alias D = double;
1398
1399 S[] a = [1, 2, 3];
1400 I[] b = [50, 60];
1401 D[] c = [10, 20, 30, 40];
1402
1403 auto m = merge(a, b, c);
1404
1405 static assert(is(typeof(m.front) == CommonType!(S, I, D)));
1406
1407 assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60]));
1408 assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1]));
1409
1410 m.popFront();
1411 assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60]));
1412 m.popBack();
1413 assert(equal(m, [2, 3, 10, 20, 30, 40, 50]));
1414 m.popFront();
1415 assert(equal(m, [3, 10, 20, 30, 40, 50]));
1416 m.popBack();
1417 assert(equal(m, [3, 10, 20, 30, 40]));
1418 m.popFront();
1419 assert(equal(m, [10, 20, 30, 40]));
1420 m.popBack();
1421 assert(equal(m, [10, 20, 30]));
1422 m.popFront();
1423 assert(equal(m, [20, 30]));
1424 m.popBack();
1425 assert(equal(m, [20]));
1426 m.popFront();
1427 assert(m.empty);
1428 }
1429
validPredicates(E,less...)1430 private template validPredicates(E, less...)
1431 {
1432 static if (less.length == 0)
1433 enum validPredicates = true;
1434 else static if (less.length == 1 && is(typeof(less[0]) == SwapStrategy))
1435 enum validPredicates = true;
1436 else
1437 enum validPredicates =
1438 is(typeof((E a, E b){ bool r = binaryFun!(less[0])(a, b); }))
1439 && validPredicates!(E, less[1 .. $]);
1440 }
1441
1442 /**
1443 $(D auto multiSort(Range)(Range r)
1444 if (validPredicates!(ElementType!Range, less));)
1445
1446 Sorts a range by multiple keys. The call $(D multiSort!("a.id < b.id",
1447 "a.date > b.date")(r)) sorts the range $(D r) by $(D id) ascending,
1448 and sorts elements that have the same $(D id) by $(D date)
1449 descending. Such a call is equivalent to $(D sort!"a.id != b.id ? a.id
1450 < b.id : a.date > b.date"(r)), but $(D multiSort) is faster because it
1451 does fewer comparisons (in addition to being more convenient).
1452
1453 Returns:
1454 The initial range wrapped as a $(D SortedRange) with its predicates
1455 converted to an equivalent single predicate.
1456 */
multiSort(less...)1457 template multiSort(less...) //if (less.length > 1)
1458 {
1459 auto multiSort(Range)(Range r)
1460 if (validPredicates!(ElementType!Range, less))
1461 {
1462 import std.meta : AliasSeq;
1463 import std.range : assumeSorted;
1464 static if (is(typeof(less[$ - 1]) == SwapStrategy))
1465 {
1466 enum ss = less[$ - 1];
1467 alias funs = less[0 .. $ - 1];
1468 }
1469 else
1470 {
1471 enum ss = SwapStrategy.unstable;
1472 alias funs = less;
1473 }
1474
1475 static if (funs.length == 0)
1476 static assert(false, "No sorting predicate provided for multiSort");
1477 else
1478 static if (funs.length == 1)
1479 return sort!(funs[0], ss, Range)(r);
1480 else
1481 {
1482 multiSortImpl!(Range, ss, funs)(r);
1483 return assumeSorted!(multiSortPredFun!(Range, funs))(r);
1484 }
1485 }
1486 }
1487
multiSortPredFun(Range,funs...)1488 private bool multiSortPredFun(Range, funs...)(ElementType!Range a, ElementType!Range b)
1489 {
1490 foreach (f; funs)
1491 {
1492 alias lessFun = binaryFun!(f);
1493 if (lessFun(a, b)) return true;
1494 if (lessFun(b, a)) return false;
1495 }
1496 return false;
1497 }
1498
multiSortImpl(Range,SwapStrategy ss,funs...)1499 private void multiSortImpl(Range, SwapStrategy ss, funs...)(Range r)
1500 {
1501 alias lessFun = binaryFun!(funs[0]);
1502
1503 static if (funs.length > 1)
1504 {
1505 while (r.length > 1)
1506 {
1507 auto p = getPivot!lessFun(r);
1508 auto t = partition3!(funs[0], ss)(r, r[p]);
1509 if (t[0].length <= t[2].length)
1510 {
1511 multiSortImpl!(Range, ss, funs)(t[0]);
1512 multiSortImpl!(Range, ss, funs[1 .. $])(t[1]);
1513 r = t[2];
1514 }
1515 else
1516 {
1517 multiSortImpl!(Range, ss, funs[1 .. $])(t[1]);
1518 multiSortImpl!(Range, ss, funs)(t[2]);
1519 r = t[0];
1520 }
1521 }
1522 }
1523 else
1524 {
1525 sort!(lessFun, ss)(r);
1526 }
1527 }
1528
1529 ///
1530 @safe unittest
1531 {
1532 import std.algorithm.mutation : SwapStrategy;
1533 static struct Point { int x, y; }
1534 auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ];
1535 auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ];
1536 multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
1537 assert(pts1 == pts2);
1538 }
1539
1540 @safe unittest
1541 {
1542 import std.algorithm.comparison : equal;
1543 import std.range;
1544
1545 static struct Point { int x, y; }
1546 auto pts1 = [ Point(5, 6), Point(1, 0), Point(5, 7), Point(1, 1), Point(1, 2), Point(0, 1) ];
1547 auto pts2 = [ Point(0, 1), Point(1, 0), Point(1, 1), Point(1, 2), Point(5, 6), Point(5, 7) ];
1548 static assert(validPredicates!(Point, "a.x < b.x", "a.y < b.y"));
1549 multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1);
1550 assert(pts1 == pts2);
1551
1552 auto pts3 = indexed(pts1, iota(pts1.length));
1553 assert(pts3.multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable).release.equal(pts2));
1554
1555 auto pts4 = iota(10).array;
1556 assert(pts4.multiSort!("a > b").release.equal(iota(10).retro));
1557 }
1558
1559 @safe unittest //issue 9160 (L-value only comparators)
1560 {
1561 static struct A
1562 {
1563 int x;
1564 int y;
1565 }
1566
byX(const ref A lhs,const ref A rhs)1567 static bool byX(const ref A lhs, const ref A rhs)
1568 {
1569 return lhs.x < rhs.x;
1570 }
1571
byY(const ref A lhs,const ref A rhs)1572 static bool byY(const ref A lhs, const ref A rhs)
1573 {
1574 return lhs.y < rhs.y;
1575 }
1576
1577 auto points = [ A(4, 1), A(2, 4)];
1578 multiSort!(byX, byY)(points);
1579 assert(points[0] == A(2, 4));
1580 assert(points[1] == A(4, 1));
1581 }
1582
1583 @safe unittest // issue 16179 (cannot access frame of function)
1584 {
1585 auto arr = [[1, 2], [2, 0], [1, 0], [1, 1]];
1586 int c = 3;
1587
1588 arr.multiSort!(
1589 (a, b) => a[0] < b[0],
1590 (a, b) => c*a[1] < c*b[1]
1591 );
1592 assert(arr == [[1, 0], [1, 1], [1, 2], [2, 0]]);
1593 }
1594
1595 @safe unittest //Issue 16413 - @system comparison function
1596 {
lt(int a,int b)1597 bool lt(int a, int b) { return a < b; } static @system
1598 auto a = [2, 1];
1599 a.multiSort!(lt, lt);
1600 assert(a == [1, 2]);
1601 }
1602
getPivot(alias less,Range)1603 private size_t getPivot(alias less, Range)(Range r)
1604 {
1605 auto mid = r.length / 2;
1606 if (r.length < 512)
1607 {
1608 if (r.length >= 32)
1609 medianOf!less(r, size_t(0), mid, r.length - 1);
1610 return mid;
1611 }
1612
1613 // The plan here is to take the median of five by taking five elements in
1614 // the array, segregate around their median, and return the position of the
1615 // third. We choose first, mid, last, and two more in between those.
1616
1617 auto quarter = r.length / 4;
1618 medianOf!less(r,
1619 size_t(0), mid - quarter, mid, mid + quarter, r.length - 1);
1620 return mid;
1621 }
1622
1623 /*
1624 Sorting routine that is optimized for short ranges. Note: uses insertion sort
1625 going downward. Benchmarked a similar routine that goes upward, for some reason
1626 it's slower.
1627 */
shortSort(alias less,Range)1628 private void shortSort(alias less, Range)(Range r)
1629 {
1630 import std.algorithm.mutation : swapAt;
1631 alias pred = binaryFun!(less);
1632
1633 switch (r.length)
1634 {
1635 case 0: case 1:
1636 return;
1637 case 2:
1638 if (pred(r[1], r[0])) r.swapAt(0, 1);
1639 return;
1640 case 3:
1641 if (pred(r[2], r[0]))
1642 {
1643 if (pred(r[0], r[1]))
1644 {
1645 r.swapAt(0, 1);
1646 r.swapAt(0, 2);
1647 }
1648 else
1649 {
1650 r.swapAt(0, 2);
1651 if (pred(r[1], r[0])) r.swapAt(0, 1);
1652 }
1653 }
1654 else
1655 {
1656 if (pred(r[1], r[0]))
1657 {
1658 r.swapAt(0, 1);
1659 }
1660 else
1661 {
1662 if (pred(r[2], r[1])) r.swapAt(1, 2);
1663 }
1664 }
1665 return;
1666 case 4:
1667 if (pred(r[1], r[0])) r.swapAt(0, 1);
1668 if (pred(r[3], r[2])) r.swapAt(2, 3);
1669 if (pred(r[2], r[0])) r.swapAt(0, 2);
1670 if (pred(r[3], r[1])) r.swapAt(1, 3);
1671 if (pred(r[2], r[1])) r.swapAt(1, 2);
1672 return;
1673 default:
1674 sort5!pred(r[r.length - 5 .. r.length]);
1675 if (r.length == 5) return;
1676 break;
1677 }
1678
1679 assert(r.length >= 6);
1680 /* The last 5 elements of the range are sorted. Proceed with expanding the
1681 sorted portion downward. */
1682 immutable maxJ = r.length - 2;
1683 for (size_t i = r.length - 6; ; --i)
1684 {
1685 static if (is(typeof(() nothrow
1686 {
1687 auto t = r[0]; if (pred(t, r[0])) r[0] = r[0];
1688 }))) // Can we afford to temporarily invalidate the array?
1689 {
1690 size_t j = i + 1;
1691 auto temp = r[i];
1692 if (pred(r[j], temp))
1693 {
1694 do
1695 {
1696 r[j - 1] = r[j];
1697 ++j;
1698 }
1699 while (j < r.length && pred(r[j], temp));
1700 r[j - 1] = temp;
1701 }
1702 }
1703 else
1704 {
1705 size_t j = i;
1706 while (pred(r[j + 1], r[j]))
1707 {
1708 r.swapAt(j, j + 1);
1709 if (j == maxJ) break;
1710 ++j;
1711 }
1712 }
1713 if (i == 0) break;
1714 }
1715 }
1716
1717 @safe unittest
1718 {
1719 import std.random : Random, uniform;
1720
1721 auto rnd = Random(1);
1722 auto a = new int[uniform(100, 200, rnd)];
foreach(ref e;a)1723 foreach (ref e; a)
1724 {
1725 e = uniform(-100, 100, rnd);
1726 }
1727
1728 shortSort!(binaryFun!("a < b"), int[])(a);
1729 assert(isSorted(a));
1730 }
1731
1732 /*
1733 Sorts the first 5 elements exactly of range r.
1734 */
sort5(alias lt,Range)1735 private void sort5(alias lt, Range)(Range r)
1736 {
1737 assert(r.length >= 5);
1738
1739 import std.algorithm.mutation : swapAt;
1740
1741 // 1. Sort first two pairs
1742 if (lt(r[1], r[0])) r.swapAt(0, 1);
1743 if (lt(r[3], r[2])) r.swapAt(2, 3);
1744
1745 // 2. Arrange first two pairs by the largest element
1746 if (lt(r[3], r[1]))
1747 {
1748 r.swapAt(0, 2);
1749 r.swapAt(1, 3);
1750 }
1751 assert(!lt(r[1], r[0]) && !lt(r[3], r[1]) && !lt(r[3], r[2]));
1752
1753 // 3. Insert 4 into [0, 1, 3]
1754 if (lt(r[4], r[1]))
1755 {
1756 r.swapAt(3, 4);
1757 r.swapAt(1, 3);
1758 if (lt(r[1], r[0]))
1759 {
1760 r.swapAt(0, 1);
1761 }
1762 }
1763 else if (lt(r[4], r[3]))
1764 {
1765 r.swapAt(3, 4);
1766 }
1767 assert(!lt(r[1], r[0]) && !lt(r[3], r[1]) && !lt(r[4], r[3]));
1768
1769 // 4. Insert 2 into [0, 1, 3, 4] (note: we already know the last is greater)
1770 assert(!lt(r[4], r[2]));
1771 if (lt(r[2], r[1]))
1772 {
1773 r.swapAt(1, 2);
1774 if (lt(r[1], r[0]))
1775 {
1776 r.swapAt(0, 1);
1777 }
1778 }
1779 else if (lt(r[3], r[2]))
1780 {
1781 r.swapAt(2, 3);
1782 }
1783 // 7 comparisons, 0-9 swaps
1784 }
1785
1786 @safe unittest
1787 {
1788 import std.algorithm.iteration : permutations;
1789 import std.algorithm.mutation : copy;
1790
1791 int[5] buf;
1792 foreach (per; iota(5).permutations)
1793 {
1794 per.copy(buf[]);
1795 sort5!((a, b) => a < b)(buf[]);
1796 assert(buf[].isSorted);
1797 }
1798 }
1799
1800 // sort
1801 /**
1802 Sorts a random-access range according to the predicate $(D less). Performs
1803 $(BIGOH r.length * log(r.length)) evaluations of $(D less). If `less` involves
1804 expensive computations on the _sort key, it may be worthwhile to use
1805 $(LREF schwartzSort) instead.
1806
1807 Stable sorting requires $(D hasAssignableElements!Range) to be true.
1808
1809 $(D sort) returns a $(REF SortedRange, std,range) over the original range,
1810 allowing functions that can take advantage of sorted data to know that the
1811 range is sorted and adjust accordingly. The $(REF SortedRange, std,range) is a
1812 wrapper around the original range, so both it and the original range are sorted.
1813 Other functions can't know that the original range has been sorted, but
1814 they $(I can) know that $(REF SortedRange, std,range) has been sorted.
1815
1816 Preconditions:
1817
1818 The predicate is expected to satisfy certain rules in order for $(D sort) to
1819 behave as expected - otherwise, the program may fail on certain inputs (but not
1820 others) when not compiled in release mode, due to the cursory $(D assumeSorted)
1821 check. Specifically, $(D sort) expects $(D less(a,b) && less(b,c)) to imply
1822 $(D less(a,c)) (transitivity), and, conversely, $(D !less(a,b) && !less(b,c)) to
1823 imply $(D !less(a,c)). Note that the default predicate ($(D "a < b")) does not
1824 always satisfy these conditions for floating point types, because the expression
1825 will always be $(D false) when either $(D a) or $(D b) is NaN.
1826 Use $(REF cmp, std,math) instead.
1827
1828 Params:
1829 less = The predicate to sort by.
1830 ss = The swapping strategy to use.
1831 r = The range to sort.
1832
1833 Returns: The initial range wrapped as a $(D SortedRange) with the predicate
1834 $(D binaryFun!less).
1835
1836 Algorithms: $(HTTP en.wikipedia.org/wiki/Introsort, Introsort) is used for unstable sorting and
1837 $(HTTP en.wikipedia.org/wiki/Timsort, Timsort) is used for stable sorting.
1838 Each algorithm has benefits beyond stability. Introsort is generally faster but
1839 Timsort may achieve greater speeds on data with low entropy or if predicate calls
1840 are expensive. Introsort performs no allocations whereas Timsort will perform one
1841 or more allocations per call. Both algorithms have $(BIGOH n log n) worst-case
1842 time complexity.
1843
1844 See_Also:
1845 $(REF assumeSorted, std,range)$(BR)
1846 $(REF SortedRange, std,range)$(BR)
1847 $(REF SwapStrategy, std,algorithm,mutation)$(BR)
1848 $(REF binaryFun, std,functional)
1849 */
1850 SortedRange!(Range, less)
1851 sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
1852 Range)(Range r)
1853 if (((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
1854 hasAssignableElements!Range)) ||
1855 (ss != SwapStrategy.unstable && hasAssignableElements!Range)) &&
1856 isRandomAccessRange!Range &&
1857 hasSlicing!Range &&
1858 hasLength!Range)
1859 /+ Unstable sorting uses the quicksort algorithm, which uses swapAt,
1860 which either uses swap(...), requiring swappable elements, or just
1861 swaps using assignment.
1862 Stable sorting uses TimSort, which needs to copy elements into a buffer,
1863 requiring assignable elements. +/
1864 {
1865 import std.range : assumeSorted;
1866 alias lessFun = binaryFun!(less);
1867 alias LessRet = typeof(lessFun(r.front, r.front)); // instantiate lessFun
1868 static if (is(LessRet == bool))
1869 {
1870 static if (ss == SwapStrategy.unstable)
1871 quickSortImpl!(lessFun)(r, r.length);
1872 else //use Tim Sort for semistable & stable
1873 TimSortImpl!(lessFun, Range).sort(r, null);
1874
1875 assert(isSorted!lessFun(r), "Failed to sort range of type " ~ Range.stringof);
1876 }
1877 else
1878 {
1879 static assert(false, "Invalid predicate passed to sort: " ~ less.stringof);
1880 }
1881 return assumeSorted!less(r);
1882 }
1883
1884 ///
1885 @safe pure nothrow unittest
1886 {
1887 int[] array = [ 1, 2, 3, 4 ];
1888
1889 // sort in descending order
1890 array.sort!("a > b");
1891 assert(array == [ 4, 3, 2, 1 ]);
1892
1893 // sort in ascending order
1894 array.sort();
1895 assert(array == [ 1, 2, 3, 4 ]);
1896
1897 // sort with reusable comparator and chain
1898 alias myComp = (x, y) => x > y;
1899 assert(array.sort!(myComp).release == [ 4, 3, 2, 1 ]);
1900 }
1901
1902 ///
1903 @safe unittest
1904 {
1905 // Showcase stable sorting
1906 import std.algorithm.mutation : SwapStrategy;
1907 string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
1908 sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
1909 assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
1910 }
1911
1912 ///
1913 @safe unittest
1914 {
1915 // Sorting floating-point numbers in presence of NaN
1916 double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];
1917
1918 import std.algorithm.comparison : equal;
1919 import std.math : cmp, isIdentical;
1920
1921 sort!((a, b) => cmp(a, b) < 0)(numbers);
1922
1923 double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
1924 assert(numbers.equal!isIdentical(sorted));
1925 }
1926
1927 @safe unittest
1928 {
1929 // Simple regression benchmark
1930 import std.algorithm.iteration, std.algorithm.mutation, std.random;
1931 Random rng;
1932 int[] a = iota(20148).map!(_ => uniform(-1000, 1000, rng)).array;
1933 static uint comps;
less(int a,int b)1934 static bool less(int a, int b) { ++comps; return a < b; }
1935 sort!less(a); // random numbers
1936 sort!less(a); // sorted ascending
1937 a.reverse();
1938 sort!less(a); // sorted descending
1939 a[] = 0;
1940 sort!less(a); // all equal
1941
1942 // This should get smaller with time. On occasion it may go larger, but only
1943 // if there's thorough justification.
1944 debug enum uint watermark = 1676280;
1945 else enum uint watermark = 1676220;
1946
1947 import std.conv;
1948 assert(comps <= watermark, text("You seem to have pessimized sort! ",
1949 watermark, " < ", comps));
1950 assert(comps >= watermark, text("You seem to have improved sort!",
1951 " Please update watermark from ", watermark, " to ", comps));
1952 }
1953
1954 @safe unittest
1955 {
1956 import std.algorithm.internal : rndstuff;
1957 import std.algorithm.mutation : swapRanges;
1958 import std.random : Random, unpredictableSeed, uniform;
1959 import std.uni : toUpper;
1960
1961 // sort using delegate
1962 auto a = new int[100];
1963 auto rnd = Random(unpredictableSeed);
foreach(ref e;a)1964 foreach (ref e; a)
1965 {
1966 e = uniform(-100, 100, rnd);
1967 }
1968
1969 int i = 0;
greater2(int a,int b)1970 bool greater2(int a, int b) @safe { return a + i > b + i; }
1971 auto greater = &greater2;
1972 sort!(greater)(a);
1973 assert(isSorted!(greater)(a));
1974
1975 // sort using string
1976 sort!("a < b")(a);
1977 assert(isSorted!("a < b")(a));
1978
1979 // sort using function; all elements equal
foreach(ref e;a)1980 foreach (ref e; a)
1981 {
1982 e = 5;
1983 }
less(int a,int b)1984 static bool less(int a, int b) { return a < b; }
1985 sort!(less)(a);
1986 assert(isSorted!(less)(a));
1987
1988 string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
lessi(string a,string b)1989 bool lessi(string a, string b) { return toUpper(a) < toUpper(b); }
1990 sort!(lessi, SwapStrategy.stable)(words);
1991 assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
1992
1993 // sort using ternary predicate
1994 //sort!("b - a")(a);
1995 //assert(isSorted!(less)(a));
1996
1997 a = rndstuff!(int)();
1998 sort(a);
1999 assert(isSorted(a));
2000 auto b = rndstuff!(string)();
2001 sort!("toLower(a) < toLower(b)")(b);
2002 assert(isSorted!("toUpper(a) < toUpper(b)")(b));
2003
2004 {
2005 // Issue 10317
2006 enum E_10317 { a, b }
2007 auto a_10317 = new E_10317[10];
2008 sort(a_10317);
2009 }
2010
2011 {
2012 // Issue 7767
2013 // Unstable sort should complete without an excessive number of predicate calls
2014 // This would suggest it's running in quadratic time
2015
2016 // Compilation error if predicate is not static, i.e. a nested function
2017 static uint comp;
pred(size_t a,size_t b)2018 static bool pred(size_t a, size_t b)
2019 {
2020 ++comp;
2021 return a < b;
2022 }
2023
2024 size_t[] arr;
2025 arr.length = 1024;
2026
2027 foreach (k; 0 .. arr.length) arr[k] = k;
2028 swapRanges(arr[0..$/2], arr[$/2..$]);
2029
2030 sort!(pred, SwapStrategy.unstable)(arr);
2031 assert(comp < 25_000);
2032 }
2033
2034 {
2035 import std.algorithm.mutation : swap;
2036
2037 bool proxySwapCalled;
2038 struct S
2039 {
2040 int i;
2041 alias i this;
proxySwapS2042 void proxySwap(ref S other) { swap(i, other.i); proxySwapCalled = true; }
2043 @disable void opAssign(S value);
2044 }
2045
2046 alias R = S[];
2047 R r = [S(3), S(2), S(1)];
2048 static assert(hasSwappableElements!R);
2049 static assert(!hasAssignableElements!R);
2050 r.sort();
2051 assert(proxySwapCalled);
2052 }
2053 }
2054
quickSortImpl(alias less,Range)2055 private void quickSortImpl(alias less, Range)(Range r, size_t depth)
2056 {
2057 import std.algorithm.comparison : min, max;
2058 import std.algorithm.mutation : swap, swapAt;
2059
2060 alias Elem = ElementType!(Range);
2061 enum size_t shortSortGetsBetter = max(32, 1024 / Elem.sizeof);
2062 static assert(shortSortGetsBetter >= 1);
2063
2064 // partition
2065 while (r.length > shortSortGetsBetter)
2066 {
2067 if (depth == 0)
2068 {
2069 HeapOps!(less, Range).heapSort(r);
2070 return;
2071 }
2072 depth = depth >= depth.max / 2 ? (depth / 3) * 2 : (depth * 2) / 3;
2073
2074 const pivotIdx = getPivot!(less)(r);
2075 auto pivot = r[pivotIdx];
2076
2077 // partition
2078 r.swapAt(pivotIdx, r.length - 1);
2079 size_t lessI = size_t.max, greaterI = r.length - 1;
2080
2081 outer: for (;;)
2082 {
2083 alias pred = binaryFun!less;
2084 while (pred(r[++lessI], pivot)) {}
2085 assert(lessI <= greaterI, "sort: invalid comparison function.");
2086 for (;;)
2087 {
2088 if (greaterI == lessI) break outer;
2089 if (!pred(pivot, r[--greaterI])) break;
2090 }
2091 assert(lessI <= greaterI, "sort: invalid comparison function.");
2092 if (lessI == greaterI) break;
2093 r.swapAt(lessI, greaterI);
2094 }
2095
2096 r.swapAt(r.length - 1, lessI);
2097 auto left = r[0 .. lessI], right = r[lessI + 1 .. r.length];
2098 if (right.length > left.length)
2099 {
2100 swap(left, right);
2101 }
2102 .quickSortImpl!(less, Range)(right, depth);
2103 r = left;
2104 }
2105 // residual sort
2106 static if (shortSortGetsBetter > 1)
2107 {
2108 shortSort!(less, Range)(r);
2109 }
2110 }
2111
2112 // Heap operations for random-access ranges
package(std)2113 package(std) template HeapOps(alias less, Range)
2114 {
2115 import std.algorithm.mutation : swapAt;
2116
2117 static assert(isRandomAccessRange!Range);
2118 static assert(hasLength!Range);
2119 static assert(hasSwappableElements!Range || hasAssignableElements!Range);
2120
2121 alias lessFun = binaryFun!less;
2122
2123 //template because of @@@12410@@@
2124 void heapSort()(Range r)
2125 {
2126 // If true, there is nothing to do
2127 if (r.length < 2) return;
2128 // Build Heap
2129 buildHeap(r);
2130 // Sort
2131 for (size_t i = r.length - 1; i > 0; --i)
2132 {
2133 r.swapAt(0, i);
2134 percolate(r, 0, i);
2135 }
2136 }
2137
2138 //template because of @@@12410@@@
2139 void buildHeap()(Range r)
2140 {
2141 immutable n = r.length;
2142 for (size_t i = n / 2; i-- > 0; )
2143 {
2144 siftDown(r, i, n);
2145 }
2146 assert(isHeap(r));
2147 }
2148
2149 bool isHeap()(Range r)
2150 {
2151 size_t parent = 0;
2152 foreach (child; 1 .. r.length)
2153 {
2154 if (lessFun(r[parent], r[child])) return false;
2155 // Increment parent every other pass
2156 parent += !(child & 1);
2157 }
2158 return true;
2159 }
2160
2161 // Sifts down r[parent] (which is initially assumed to be messed up) so the
2162 // heap property is restored for r[parent .. end].
2163 // template because of @@@12410@@@
2164 void siftDown()(Range r, size_t parent, immutable size_t end)
2165 {
2166 for (;;)
2167 {
2168 auto child = (parent + 1) * 2;
2169 if (child >= end)
2170 {
2171 // Leftover left child?
2172 if (child == end && lessFun(r[parent], r[--child]))
2173 r.swapAt(parent, child);
2174 break;
2175 }
2176 auto leftChild = child - 1;
2177 if (lessFun(r[child], r[leftChild])) child = leftChild;
2178 if (!lessFun(r[parent], r[child])) break;
2179 r.swapAt(parent, child);
2180 parent = child;
2181 }
2182 }
2183
2184 // Alternate version of siftDown that performs fewer comparisons, see
2185 // https://en.wikipedia.org/wiki/Heapsort#Bottom-up_heapsort. The percolate
2186 // process first sifts the parent all the way down (without comparing it
2187 // against the leaves), and then a bit up until the heap property is
2188 // restored. So there are more swaps but fewer comparisons. Gains are made
2189 // when the final position is likely to end toward the bottom of the heap,
2190 // so not a lot of sifts back are performed.
2191 //template because of @@@12410@@@
2192 void percolate()(Range r, size_t parent, immutable size_t end)
2193 {
2194 immutable root = parent;
2195
2196 // Sift down
2197 for (;;)
2198 {
2199 auto child = (parent + 1) * 2;
2200
2201 if (child >= end)
2202 {
2203 if (child == end)
2204 {
2205 // Leftover left node.
2206 --child;
2207 r.swapAt(parent, child);
2208 parent = child;
2209 }
2210 break;
2211 }
2212
2213 auto leftChild = child - 1;
2214 if (lessFun(r[child], r[leftChild])) child = leftChild;
2215 r.swapAt(parent, child);
2216 parent = child;
2217 }
2218
2219 // Sift up
2220 for (auto child = parent; child > root; child = parent)
2221 {
2222 parent = (child - 1) / 2;
2223 if (!lessFun(r[parent], r[child])) break;
2224 r.swapAt(parent, child);
2225 }
2226 }
2227 }
2228
2229 // Tim Sort implementation
TimSortImpl(alias pred,R)2230 private template TimSortImpl(alias pred, R)
2231 {
2232 import core.bitop : bsr;
2233 import std.array : uninitializedArray;
2234
2235 static assert(isRandomAccessRange!R);
2236 static assert(hasLength!R);
2237 static assert(hasSlicing!R);
2238 static assert(hasAssignableElements!R);
2239
2240 alias T = ElementType!R;
2241
2242 alias less = binaryFun!pred;
2243 alias greater = (a, b) => less(b, a);
2244 alias greaterEqual = (a, b) => !less(a, b);
2245 alias lessEqual = (a, b) => !less(b, a);
2246
2247 enum minimalMerge = 128;
2248 enum minimalGallop = 7;
2249 enum minimalStorage = 256;
2250 enum stackSize = 40;
2251
2252 struct Slice{ size_t base, length; }
2253
2254 // Entry point for tim sort
2255 void sort()(R range, T[] temp)
2256 {
2257 import std.algorithm.comparison : min;
2258
2259 // Do insertion sort on small range
2260 if (range.length <= minimalMerge)
2261 {
2262 binaryInsertionSort(range);
2263 return;
2264 }
2265
2266 immutable minRun = minRunLength(range.length);
2267 immutable minTemp = min(range.length / 2, minimalStorage);
2268 size_t minGallop = minimalGallop;
2269 Slice[stackSize] stack = void;
2270 size_t stackLen = 0;
2271
2272 // Allocate temporary memory if not provided by user
2273 if (temp.length < minTemp) temp = () @trusted { return uninitializedArray!(T[])(minTemp); }();
2274
2275 for (size_t i = 0; i < range.length; )
2276 {
2277 // Find length of first run in list
2278 size_t runLen = firstRun(range[i .. range.length]);
2279
2280 // If run has less than minRun elements, extend using insertion sort
2281 if (runLen < minRun)
2282 {
2283 // Do not run farther than the length of the range
2284 immutable force = range.length - i > minRun ? minRun : range.length - i;
2285 binaryInsertionSort(range[i .. i + force], runLen);
2286 runLen = force;
2287 }
2288
2289 // Push run onto stack
2290 stack[stackLen++] = Slice(i, runLen);
2291 i += runLen;
2292
2293 // Collapse stack so that (e1 > e2 + e3 && e2 > e3)
2294 // STACK is | ... e1 e2 e3 >
2295 while (stackLen > 1)
2296 {
2297 immutable run4 = stackLen - 1;
2298 immutable run3 = stackLen - 2;
2299 immutable run2 = stackLen - 3;
2300 immutable run1 = stackLen - 4;
2301
2302 if ( (stackLen > 2 && stack[run2].length <= stack[run3].length + stack[run4].length) ||
2303 (stackLen > 3 && stack[run1].length <= stack[run3].length + stack[run2].length) )
2304 {
2305 immutable at = stack[run2].length < stack[run4].length ? run2 : run3;
2306 mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
2307 }
2308 else if (stack[run3].length > stack[run4].length) break;
2309 else mergeAt(range, stack[0 .. stackLen], run3, minGallop, temp);
2310
2311 stackLen -= 1;
2312 }
2313
2314 // Assert that the code above established the invariant correctly
2315 version (assert)
2316 {
2317 if (stackLen == 2) assert(stack[0].length > stack[1].length);
2318 else if (stackLen > 2)
2319 {
2320 foreach (k; 2 .. stackLen)
2321 {
2322 assert(stack[k - 2].length > stack[k - 1].length + stack[k].length);
2323 assert(stack[k - 1].length > stack[k].length);
2324 }
2325 }
2326 }
2327 }
2328
2329 // Force collapse stack until there is only one run left
2330 while (stackLen > 1)
2331 {
2332 immutable run3 = stackLen - 1;
2333 immutable run2 = stackLen - 2;
2334 immutable run1 = stackLen - 3;
2335 immutable at = stackLen >= 3 && stack[run1].length <= stack[run3].length
2336 ? run1 : run2;
2337 mergeAt(range, stack[0 .. stackLen], at, minGallop, temp);
2338 --stackLen;
2339 }
2340 }
2341
2342 // Calculates optimal value for minRun:
2343 // take first 6 bits of n and add 1 if any lower bits are set
2344 size_t minRunLength()(size_t n)
2345 {
2346 immutable shift = bsr(n)-5;
2347 auto result = (n >> shift) + !!(n & ~((1 << shift)-1));
2348 return result;
2349 }
2350
2351 // Returns length of first run in range
2352 size_t firstRun()(R range)
2353 out(ret)
2354 {
2355 assert(ret <= range.length);
2356 }
2357 body
2358 {
2359 import std.algorithm.mutation : reverse;
2360
2361 if (range.length < 2) return range.length;
2362
2363 size_t i = 2;
2364 if (lessEqual(range[0], range[1]))
2365 {
2366 while (i < range.length && lessEqual(range[i-1], range[i])) ++i;
2367 }
2368 else
2369 {
2370 while (i < range.length && greater(range[i-1], range[i])) ++i;
2371 reverse(range[0 .. i]);
2372 }
2373 return i;
2374 }
2375
2376 // A binary insertion sort for building runs up to minRun length
2377 void binaryInsertionSort()(R range, size_t sortedLen = 1)
2378 out
2379 {
2380 if (!__ctfe) assert(isSorted!pred(range));
2381 }
2382 body
2383 {
2384 import std.algorithm.mutation : move;
2385
2386 for (; sortedLen < range.length; ++sortedLen)
2387 {
2388 T item = range.moveAt(sortedLen);
2389 size_t lower = 0;
2390 size_t upper = sortedLen;
2391 while (upper != lower)
2392 {
2393 size_t center = (lower + upper) / 2;
2394 if (less(item, range[center])) upper = center;
2395 else lower = center + 1;
2396 }
2397 //Currently (DMD 2.061) moveAll+retro is slightly less
2398 //efficient then stright 'for' loop
2399 //11 instructions vs 7 in the innermost loop [checked on Win32]
2400 //moveAll(retro(range[lower .. sortedLen]),
2401 // retro(range[lower+1 .. sortedLen+1]));
2402 for (upper=sortedLen; upper > lower; upper--)
2403 range[upper] = range.moveAt(upper - 1);
2404 range[lower] = move(item);
2405 }
2406 }
2407
2408 // Merge two runs in stack (at, at + 1)
2409 void mergeAt()(R range, Slice[] stack, immutable size_t at, ref size_t minGallop, ref T[] temp)
2410 in
2411 {
2412 assert(stack.length >= 2);
2413 assert(stack.length - at == 2 || stack.length - at == 3);
2414 }
2415 body
2416 {
2417 immutable base = stack[at].base;
2418 immutable mid = stack[at].length;
2419 immutable len = stack[at + 1].length + mid;
2420
2421 // Pop run from stack
2422 stack[at] = Slice(base, len);
2423 if (stack.length - at == 3) stack[$ - 2] = stack[$ - 1];
2424
2425 // Merge runs (at, at + 1)
2426 return merge(range[base .. base + len], mid, minGallop, temp);
2427 }
2428
2429 // Merge two runs in a range. Mid is the starting index of the second run.
2430 // minGallop and temp are references; The calling function must receive the updated values.
2431 void merge()(R range, size_t mid, ref size_t minGallop, ref T[] temp)
2432 in
2433 {
2434 if (!__ctfe)
2435 {
2436 assert(isSorted!pred(range[0 .. mid]));
2437 assert(isSorted!pred(range[mid .. range.length]));
2438 }
2439 }
2440 body
2441 {
2442 assert(mid < range.length);
2443
2444 // Reduce range of elements
2445 immutable firstElement = gallopForwardUpper(range[0 .. mid], range[mid]);
2446 immutable lastElement = gallopReverseLower(range[mid .. range.length], range[mid - 1]) + mid;
2447 range = range[firstElement .. lastElement];
2448 mid -= firstElement;
2449
2450 if (mid == 0 || mid == range.length) return;
2451
2452 // Call function which will copy smaller run into temporary memory
2453 if (mid <= range.length / 2)
2454 {
2455 temp = ensureCapacity(mid, temp);
2456 minGallop = mergeLo(range, mid, minGallop, temp);
2457 }
2458 else
2459 {
2460 temp = ensureCapacity(range.length - mid, temp);
2461 minGallop = mergeHi(range, mid, minGallop, temp);
2462 }
2463 }
2464
2465 // Enlarge size of temporary memory if needed
2466 T[] ensureCapacity()(size_t minCapacity, T[] temp)
2467 out(ret)
2468 {
2469 assert(ret.length >= minCapacity);
2470 }
2471 body
2472 {
2473 if (temp.length < minCapacity)
2474 {
2475 size_t newSize = 1<<(bsr(minCapacity)+1);
2476 //Test for overflow
2477 if (newSize < minCapacity) newSize = minCapacity;
2478
2479 if (__ctfe) temp.length = newSize;
2480 else temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
2481 }
2482 return temp;
2483 }
2484
2485 // Merge front to back. Returns new value of minGallop.
2486 // temp must be large enough to store range[0 .. mid]
2487 size_t mergeLo()(R range, immutable size_t mid, size_t minGallop, T[] temp)
2488 out
2489 {
2490 if (!__ctfe) assert(isSorted!pred(range));
2491 }
2492 body
2493 {
2494 import std.algorithm.mutation : copy;
2495
2496 assert(mid <= range.length);
2497 assert(temp.length >= mid);
2498
2499 // Copy run into temporary memory
2500 temp = temp[0 .. mid];
2501 copy(range[0 .. mid], temp);
2502
2503 // Move first element into place
2504 range[0] = range[mid];
2505
2506 size_t i = 1, lef = 0, rig = mid + 1;
2507 size_t count_lef, count_rig;
2508 immutable lef_end = temp.length - 1;
2509
2510 if (lef < lef_end && rig < range.length)
2511 outer: while (true)
2512 {
2513 count_lef = 0;
2514 count_rig = 0;
2515
2516 // Linear merge
2517 while ((count_lef | count_rig) < minGallop)
2518 {
2519 if (lessEqual(temp[lef], range[rig]))
2520 {
2521 range[i++] = temp[lef++];
2522 if (lef >= lef_end) break outer;
2523 ++count_lef;
2524 count_rig = 0;
2525 }
2526 else
2527 {
2528 range[i++] = range[rig++];
2529 if (rig >= range.length) break outer;
2530 count_lef = 0;
2531 ++count_rig;
2532 }
2533 }
2534
2535 // Gallop merge
2536 do
2537 {
2538 count_lef = gallopForwardUpper(temp[lef .. $], range[rig]);
2539 foreach (j; 0 .. count_lef) range[i++] = temp[lef++];
2540 if (lef >= temp.length) break outer;
2541
2542 count_rig = gallopForwardLower(range[rig .. range.length], temp[lef]);
2543 foreach (j; 0 .. count_rig) range[i++] = range[rig++];
2544 if (rig >= range.length) while (true)
2545 {
2546 range[i++] = temp[lef++];
2547 if (lef >= temp.length) break outer;
2548 }
2549
2550 if (minGallop > 0) --minGallop;
2551 }
2552 while (count_lef >= minimalGallop || count_rig >= minimalGallop);
2553
2554 minGallop += 2;
2555 }
2556
2557 // Move remaining elements from right
2558 while (rig < range.length)
2559 range[i++] = range[rig++];
2560
2561 // Move remaining elements from left
2562 while (lef < temp.length)
2563 range[i++] = temp[lef++];
2564
2565 return minGallop > 0 ? minGallop : 1;
2566 }
2567
2568 // Merge back to front. Returns new value of minGallop.
2569 // temp must be large enough to store range[mid .. range.length]
2570 size_t mergeHi()(R range, immutable size_t mid, size_t minGallop, T[] temp)
2571 out
2572 {
2573 if (!__ctfe) assert(isSorted!pred(range));
2574 }
2575 body
2576 {
2577 import std.algorithm.mutation : copy;
2578
2579 assert(mid <= range.length);
2580 assert(temp.length >= range.length - mid);
2581
2582 // Copy run into temporary memory
2583 temp = temp[0 .. range.length - mid];
2584 copy(range[mid .. range.length], temp);
2585
2586 // Move first element into place
2587 range[range.length - 1] = range[mid - 1];
2588
2589 size_t i = range.length - 2, lef = mid - 2, rig = temp.length - 1;
2590 size_t count_lef, count_rig;
2591
2592 outer:
2593 while (true)
2594 {
2595 count_lef = 0;
2596 count_rig = 0;
2597
2598 // Linear merge
2599 while ((count_lef | count_rig) < minGallop)
2600 {
2601 if (greaterEqual(temp[rig], range[lef]))
2602 {
2603 range[i--] = temp[rig];
2604 if (rig == 1)
2605 {
2606 // Move remaining elements from left
2607 while (true)
2608 {
2609 range[i--] = range[lef];
2610 if (lef == 0) break;
2611 --lef;
2612 }
2613
2614 // Move last element into place
2615 range[i] = temp[0];
2616
2617 break outer;
2618 }
2619 --rig;
2620 count_lef = 0;
2621 ++count_rig;
2622 }
2623 else
2624 {
2625 range[i--] = range[lef];
2626 if (lef == 0) while (true)
2627 {
2628 range[i--] = temp[rig];
2629 if (rig == 0) break outer;
2630 --rig;
2631 }
2632 --lef;
2633 ++count_lef;
2634 count_rig = 0;
2635 }
2636 }
2637
2638 // Gallop merge
2639 do
2640 {
2641 count_rig = rig - gallopReverseLower(temp[0 .. rig], range[lef]);
2642 foreach (j; 0 .. count_rig)
2643 {
2644 range[i--] = temp[rig];
2645 if (rig == 0) break outer;
2646 --rig;
2647 }
2648
2649 count_lef = lef - gallopReverseUpper(range[0 .. lef], temp[rig]);
2650 foreach (j; 0 .. count_lef)
2651 {
2652 range[i--] = range[lef];
2653 if (lef == 0) while (true)
2654 {
2655 range[i--] = temp[rig];
2656 if (rig == 0) break outer;
2657 --rig;
2658 }
2659 --lef;
2660 }
2661
2662 if (minGallop > 0) --minGallop;
2663 }
2664 while (count_lef >= minimalGallop || count_rig >= minimalGallop);
2665
2666 minGallop += 2;
2667 }
2668
2669 return minGallop > 0 ? minGallop : 1;
2670 }
2671
2672 // false = forward / lower, true = reverse / upper
2673 template gallopSearch(bool forwardReverse, bool lowerUpper)
2674 {
2675 // Gallop search on range according to attributes forwardReverse and lowerUpper
2676 size_t gallopSearch(R)(R range, T value)
2677 out(ret)
2678 {
2679 assert(ret <= range.length);
2680 }
2681 body
2682 {
2683 size_t lower = 0, center = 1, upper = range.length;
2684 alias gap = center;
2685
2686 static if (forwardReverse)
2687 {
2688 static if (!lowerUpper) alias comp = lessEqual; // reverse lower
2689 static if (lowerUpper) alias comp = less; // reverse upper
2690
2691 // Gallop Search Reverse
2692 while (gap <= upper)
2693 {
2694 if (comp(value, range[upper - gap]))
2695 {
2696 upper -= gap;
2697 gap *= 2;
2698 }
2699 else
2700 {
2701 lower = upper - gap;
2702 break;
2703 }
2704 }
2705
2706 // Binary Search Reverse
2707 while (upper != lower)
2708 {
2709 center = lower + (upper - lower) / 2;
2710 if (comp(value, range[center])) upper = center;
2711 else lower = center + 1;
2712 }
2713 }
2714 else
2715 {
2716 static if (!lowerUpper) alias comp = greater; // forward lower
2717 static if (lowerUpper) alias comp = greaterEqual; // forward upper
2718
2719 // Gallop Search Forward
2720 while (lower + gap < upper)
2721 {
2722 if (comp(value, range[lower + gap]))
2723 {
2724 lower += gap;
2725 gap *= 2;
2726 }
2727 else
2728 {
2729 upper = lower + gap;
2730 break;
2731 }
2732 }
2733
2734 // Binary Search Forward
2735 while (lower != upper)
2736 {
2737 center = lower + (upper - lower) / 2;
2738 if (comp(value, range[center])) lower = center + 1;
2739 else upper = center;
2740 }
2741 }
2742
2743 return lower;
2744 }
2745 }
2746
2747 alias gallopForwardLower = gallopSearch!(false, false);
2748 alias gallopForwardUpper = gallopSearch!(false, true);
2749 alias gallopReverseLower = gallopSearch!( true, false);
2750 alias gallopReverseUpper = gallopSearch!( true, true);
2751 }
2752
2753 @safe unittest
2754 {
2755 import std.random : Random, uniform, randomShuffle;
2756
2757 // Element type with two fields
2758 static struct E
2759 {
2760 size_t value, index;
2761 }
2762
2763 // Generates data especially for testing sorting with Timsort
genSampleData(uint seed)2764 static E[] genSampleData(uint seed) @safe
2765 {
2766 import std.algorithm.mutation : swap, swapRanges;
2767
2768 auto rnd = Random(seed);
2769
2770 E[] arr;
2771 arr.length = 64 * 64;
2772
2773 // We want duplicate values for testing stability
2774 foreach (i, ref v; arr) v.value = i / 64;
2775
2776 // Swap ranges at random middle point (test large merge operation)
2777 immutable mid = uniform(arr.length / 4, arr.length / 4 * 3, rnd);
2778 swapRanges(arr[0 .. mid], arr[mid .. $]);
2779
2780 // Shuffle last 1/8 of the array (test insertion sort and linear merge)
2781 randomShuffle(arr[$ / 8 * 7 .. $], rnd);
2782
2783 // Swap few random elements (test galloping mode)
2784 foreach (i; 0 .. arr.length / 64)
2785 {
2786 immutable a = uniform(0, arr.length, rnd), b = uniform(0, arr.length, rnd);
2787 swap(arr[a], arr[b]);
2788 }
2789
2790 // Now that our test array is prepped, store original index value
2791 // This will allow us to confirm the array was sorted stably
2792 foreach (i, ref v; arr) v.index = i;
2793
2794 return arr;
2795 }
2796
2797 // Tests the Timsort function for correctness and stability
testSort(uint seed)2798 static bool testSort(uint seed)
2799 {
2800 auto arr = genSampleData(seed);
2801
2802 // Now sort the array!
2803 static bool comp(E a, E b)
2804 {
2805 return a.value < b.value;
2806 }
2807
2808 sort!(comp, SwapStrategy.stable)(arr);
2809
2810 // Test that the array was sorted correctly
2811 assert(isSorted!comp(arr));
2812
2813 // Test that the array was sorted stably
2814 foreach (i; 0 .. arr.length - 1)
2815 {
2816 if (arr[i].value == arr[i + 1].value) assert(arr[i].index < arr[i + 1].index);
2817 }
2818
2819 return true;
2820 }
2821
2822 enum seed = 310614065;
2823 testSort(seed);
2824
2825 enum result = testSort(seed);
2826 assert(result == true);
2827 }
2828
2829 @safe unittest
2830 {//bugzilla 4584
2831 assert(isSorted!"a < b"(sort!("a < b", SwapStrategy.stable)(
2832 [83, 42, 85, 86, 87, 22, 89, 30, 91, 46, 93, 94, 95, 6,
2833 97, 14, 33, 10, 101, 102, 103, 26, 105, 106, 107, 6]
2834 )));
2835
2836 }
2837
2838 @safe unittest
2839 {
2840 //test stable sort + zip
2841 import std.range;
2842 auto x = [10, 50, 60, 60, 20];
2843 dchar[] y = "abcde"d.dup;
2844
2845 sort!("a[0] < b[0]", SwapStrategy.stable)(zip(x, y));
2846 assert(x == [10, 20, 50, 60, 60]);
2847 assert(y == "aebcd"d);
2848 }
2849
2850 @safe unittest
2851 {
2852 // Issue 14223
2853 import std.array, std.range;
2854 auto arr = chain(iota(0, 384), iota(0, 256), iota(0, 80), iota(0, 64), iota(0, 96)).array;
2855 sort!("a < b", SwapStrategy.stable)(arr);
2856 }
2857
2858 // schwartzSort
2859 /**
2860 Alternative sorting method that should be used when comparing keys involves an
2861 expensive computation. Instead of using `less(a, b)` for comparing elements,
2862 `schwartzSort` uses `less(transform(a), transform(b))`. The values of the
2863 `transform` function are precomputed in a temporary array, thus saving on
2864 repeatedly computing it. Conversely, if the cost of `transform` is small
2865 compared to the cost of allocating and filling the precomputed array, `sort`
2866 may be faster and therefore preferable.
2867
2868 This approach to sorting is akin to the $(HTTP
2869 wikipedia.org/wiki/Schwartzian_transform, Schwartzian transform), also known as
2870 the decorate-sort-undecorate pattern in Python and Lisp. The complexity is the
2871 same as that of the corresponding `sort`, but `schwartzSort` evaluates
2872 `transform` only `r.length` times (less than half when compared to regular
2873 sorting). The usage can be best illustrated with an example.
2874
2875 Example:
2876 ----
2877 uint hashFun(string) { ... expensive computation ... }
2878 string[] array = ...;
2879 // Sort strings by hash, slow
2880 sort!((a, b) => hashFun(a) < hashFun(b))(array);
2881 // Sort strings by hash, fast (only computes arr.length hashes):
2882 schwartzSort!(hashFun, "a < b")(array);
2883 ----
2884
2885 The $(D schwartzSort) function might require less temporary data and
2886 be faster than the Perl idiom or the decorate-sort-undecorate idiom
2887 present in Python and Lisp. This is because sorting is done in-place
2888 and only minimal extra data (one array of transformed elements) is
2889 created.
2890
2891 To check whether an array was sorted and benefit of the speedup of
2892 Schwartz sorting, a function $(D schwartzIsSorted) is not provided
2893 because the effect can be achieved by calling $(D
2894 isSorted!less(map!transform(r))).
2895
2896 Params:
2897 transform = The transformation to apply.
2898 less = The predicate to sort by.
2899 ss = The swapping strategy to use.
2900 r = The range to sort.
2901
2902 Returns: The initial range wrapped as a $(D SortedRange) with the
2903 predicate $(D (a, b) => binaryFun!less(transform(a),
2904 transform(b))).
2905 */
2906 SortedRange!(R, ((a, b) => binaryFun!less(unaryFun!transform(a),
2907 unaryFun!transform(b))))
2908 schwartzSort(alias transform, alias less = "a < b",
2909 SwapStrategy ss = SwapStrategy.unstable, R)(R r)
2910 if (isRandomAccessRange!R && hasLength!R)
2911 {
2912 import std.conv : emplace;
2913 import std.range : zip, SortedRange;
2914 import std.string : representation;
2915
2916 alias T = typeof(unaryFun!transform(r.front));
trustedMalloc(size_t len)2917 static trustedMalloc(size_t len) @trusted
2918 {
2919 import core.checkedint : mulu;
2920 import core.stdc.stdlib : malloc;
2921 bool overflow;
2922 const nbytes = mulu(len, T.sizeof, overflow);
2923 if (overflow) assert(0);
2924 return (cast(T*) malloc(nbytes))[0 .. len];
2925 }
2926 auto xform1 = trustedMalloc(r.length);
2927
2928 size_t length;
scope(exit)2929 scope(exit)
2930 {
2931 static if (hasElaborateDestructor!T)
2932 {
2933 foreach (i; 0 .. length) collectException(destroy(xform1[i]));
2934 }
2935 static void trustedFree(T[] p) @trusted
2936 {
2937 import core.stdc.stdlib : free;
2938 free(p.ptr);
2939 }
2940 trustedFree(xform1);
2941 }
2942 for (; length != r.length; ++length)
2943 {
2944 emplace(&xform1[length], unaryFun!transform(r[length]));
2945 }
2946 // Make sure we use ubyte[] and ushort[], not char[] and wchar[]
2947 // for the intermediate array, lest zip gets confused.
2948 static if (isNarrowString!(typeof(xform1)))
2949 {
2950 auto xform = xform1.representation();
2951 }
2952 else
2953 {
2954 alias xform = xform1;
2955 }
2956 zip(xform, r).sort!((a, b) => binaryFun!less(a[0], b[0]), ss)();
2957 return typeof(return)(r);
2958 }
2959
2960 ///
2961 @safe unittest
2962 {
2963 import std.algorithm.iteration : map;
2964 import std.numeric : entropy;
2965
2966 auto lowEnt = [ 1.0, 0, 0 ],
2967 midEnt = [ 0.1, 0.1, 0.8 ],
2968 highEnt = [ 0.31, 0.29, 0.4 ];
2969 auto arr = new double[][3];
2970 arr[0] = midEnt;
2971 arr[1] = lowEnt;
2972 arr[2] = highEnt;
2973
2974 schwartzSort!(entropy, "a > b")(arr);
2975
2976 assert(arr[0] == highEnt);
2977 assert(arr[1] == midEnt);
2978 assert(arr[2] == lowEnt);
2979 assert(isSorted!("a > b")(map!(entropy)(arr)));
2980 }
2981
2982 @safe unittest
2983 {
2984 import std.algorithm.iteration : map;
2985 import std.numeric : entropy;
2986
2987 auto lowEnt = [ 1.0, 0, 0 ],
2988 midEnt = [ 0.1, 0.1, 0.8 ],
2989 highEnt = [ 0.31, 0.29, 0.4 ];
2990 auto arr = new double[][3];
2991 arr[0] = midEnt;
2992 arr[1] = lowEnt;
2993 arr[2] = highEnt;
2994
2995 schwartzSort!(entropy, "a < b")(arr);
2996
2997 assert(arr[0] == lowEnt);
2998 assert(arr[1] == midEnt);
2999 assert(arr[2] == highEnt);
3000 assert(isSorted!("a < b")(map!(entropy)(arr)));
3001 }
3002
3003 @safe unittest
3004 {
3005 // issue 4909
3006 import std.typecons : Tuple;
3007 Tuple!(char)[] chars;
3008 schwartzSort!"a[0]"(chars);
3009 }
3010
3011 @safe unittest
3012 {
3013 // issue 5924
3014 import std.typecons : Tuple;
3015 Tuple!(char)[] chars;
3016 schwartzSort!((Tuple!(char) c){ return c[0]; })(chars);
3017 }
3018
3019 // partialSort
3020 /**
3021 Reorders the random-access range $(D r) such that the range $(D r[0
3022 .. mid]) is the same as if the entire $(D r) were sorted, and leaves
3023 the range $(D r[mid .. r.length]) in no particular order. Performs
3024 $(BIGOH r.length * log(mid)) evaluations of $(D pred). The
3025 implementation simply calls $(D topN!(less, ss)(r, n)) and then $(D
3026 sort!(less, ss)(r[0 .. n])).
3027
3028 Params:
3029 less = The predicate to sort by.
3030 ss = The swapping strategy to use.
3031 r = The random-access range to reorder.
3032 n = The length of the initial segment of `r` to sort.
3033 */
3034 void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
3035 Range)(Range r, size_t n)
3036 if (isRandomAccessRange!(Range) && hasLength!(Range) && hasSlicing!(Range))
3037 {
3038 partialSort!(less, ss)(r[0 .. n], r[n .. $]);
3039 }
3040
3041 ///
3042 @system unittest
3043 {
3044 int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ];
3045 partialSort(a, 5);
3046 assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);
3047 }
3048
3049 /**
3050 Stores the smallest elements of the two ranges in the left-hand range in sorted order.
3051
3052 Params:
3053 less = The predicate to sort by.
3054 ss = The swapping strategy to use.
3055 r1 = The first range.
3056 r2 = The second range.
3057 */
3058
3059 void partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
3060 Range1, Range2)(Range1 r1, Range2 r2)
3061 if (isRandomAccessRange!(Range1) && hasLength!Range1 &&
3062 isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) &&
3063 hasLvalueElements!Range1 && hasLvalueElements!Range2)
3064 {
3065 topN!(less, ss)(r1, r2);
3066 sort!(less, ss)(r1);
3067 }
3068 ///
3069 @system unittest
3070 {
3071 int[] a = [5, 7, 2, 6, 7];
3072 int[] b = [2, 1, 5, 6, 7, 3, 0];
3073
3074 partialSort(a, b);
3075 assert(a == [0, 1, 2, 2, 3]);
3076 }
3077
3078 // topN
3079 /**
3080 Reorders the range $(D r) using $(D swap) such that $(D r[nth]) refers
3081 to the element that would fall there if the range were fully
3082 sorted. In addition, it also partitions $(D r) such that all elements
3083 $(D e1) from $(D r[0]) to $(D r[nth]) satisfy $(D !less(r[nth], e1)),
3084 and all elements $(D e2) from $(D r[nth]) to $(D r[r.length]) satisfy
3085 $(D !less(e2, r[nth])). Effectively, it finds the nth smallest
3086 (according to $(D less)) elements in $(D r). Performs an expected
3087 $(BIGOH r.length) (if unstable) or $(BIGOH r.length * log(r.length))
3088 (if stable) evaluations of $(D less) and $(D swap).
3089
3090 If $(D n >= r.length), the algorithm has no effect and returns
3091 `r[0 .. r.length]`.
3092
3093 Params:
3094 less = The predicate to sort by.
3095 ss = The swapping strategy to use.
3096 r = The random-access range to reorder.
3097 nth = The index of the element that should be in sorted position after the
3098 function is done.
3099
3100 See_Also:
3101 $(LREF topNIndex),
3102 $(HTTP sgi.com/tech/stl/nth_element.html, STL's nth_element)
3103
3104 BUGS:
3105
3106 Stable topN has not been implemented yet.
3107 */
3108 auto topN(alias less = "a < b",
3109 SwapStrategy ss = SwapStrategy.unstable,
3110 Range)(Range r, size_t nth)
3111 if (isRandomAccessRange!(Range) && hasLength!Range && hasSlicing!Range)
3112 {
3113 static assert(ss == SwapStrategy.unstable,
3114 "Stable topN not yet implemented");
3115 if (nth >= r.length) return r[0 .. r.length];
3116 auto ret = r[0 .. nth];
3117 if (false)
3118 {
3119 // Workaround for https://issues.dlang.org/show_bug.cgi?id=16528
3120 // Safety checks: enumerate all potentially unsafe generic primitives
3121 // then use a @trusted implementation.
3122 binaryFun!less(r[0], r[r.length - 1]);
3123 import std.algorithm.mutation : swapAt;
3124 r.swapAt(size_t(0), size_t(0));
3125 static assert(is(typeof(r.length) == size_t));
3126 pivotPartition!less(r, 0);
3127 }
3128 bool useSampling = true;
3129 topNImpl!(binaryFun!less)(r, nth, useSampling);
3130 return ret;
3131 }
3132
3133 private @trusted
topNImpl(alias less,R)3134 void topNImpl(alias less, R)(R r, size_t n, ref bool useSampling)
3135 {
3136 for (;;)
3137 {
3138 import std.algorithm.mutation : swapAt;
3139 assert(n < r.length);
3140 size_t pivot = void;
3141
3142 // Decide strategy for partitioning
3143 if (n == 0)
3144 {
3145 pivot = 0;
3146 foreach (i; 1 .. r.length)
3147 if (less(r[i], r[pivot])) pivot = i;
3148 r.swapAt(n, pivot);
3149 return;
3150 }
3151 if (n + 1 == r.length)
3152 {
3153 pivot = 0;
3154 foreach (i; 1 .. r.length)
3155 if (less(r[pivot], r[i])) pivot = i;
3156 r.swapAt(n, pivot);
3157 return;
3158 }
3159 if (r.length <= 12)
3160 {
3161 pivot = pivotPartition!less(r, r.length / 2);
3162 }
3163 else if (n * 16 <= (r.length - 1) * 7)
3164 {
3165 pivot = topNPartitionOffMedian!(less, No.leanRight)
3166 (r, n, useSampling);
3167 // Quality check
3168 if (useSampling)
3169 {
3170 if (pivot < n)
3171 {
3172 if (pivot * 4 < r.length)
3173 {
3174 useSampling = false;
3175 }
3176 }
3177 else if ((r.length - pivot) * 8 < r.length * 3)
3178 {
3179 useSampling = false;
3180 }
3181 }
3182 }
3183 else if (n * 16 >= (r.length - 1) * 9)
3184 {
3185 pivot = topNPartitionOffMedian!(less, Yes.leanRight)
3186 (r, n, useSampling);
3187 // Quality check
3188 if (useSampling)
3189 {
3190 if (pivot < n)
3191 {
3192 if (pivot * 8 < r.length * 3)
3193 {
3194 useSampling = false;
3195 }
3196 }
3197 else if ((r.length - pivot) * 4 < r.length)
3198 {
3199 useSampling = false;
3200 }
3201 }
3202 }
3203 else
3204 {
3205 pivot = topNPartition!less(r, n, useSampling);
3206 // Quality check
3207 if (useSampling &&
3208 (pivot * 9 < r.length * 2 || pivot * 9 > r.length * 7))
3209 {
3210 // Failed - abort sampling going forward
3211 useSampling = false;
3212 }
3213 }
3214
3215 assert(pivot != size_t.max);
3216 // See how the pivot fares
3217 if (pivot == n)
3218 {
3219 return;
3220 }
3221 if (pivot > n)
3222 {
3223 r = r[0 .. pivot];
3224 }
3225 else
3226 {
3227 n -= pivot + 1;
3228 r = r[pivot + 1 .. r.length];
3229 }
3230 }
3231 }
3232
3233 ///
3234 @safe unittest
3235 {
3236 int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
3237 topN!"a < b"(v, 100);
3238 assert(v == [ 25, 7, 9, 2, 0, 5, 21 ]);
3239 auto n = 4;
3240 topN!"a < b"(v, n);
3241 assert(v[n] == 9);
3242 }
3243
topNPartition(alias lp,R)3244 private size_t topNPartition(alias lp, R)(R r, size_t n, bool useSampling)
3245 {
3246 assert(r.length >= 9 && n < r.length);
3247 immutable ninth = r.length / 9;
3248 auto pivot = ninth / 2;
3249 // Position subrange r[lo .. hi] to have length equal to ninth and its upper
3250 // median r[lo .. hi][$ / 2] in exactly the same place as the upper median
3251 // of the entire range r[$ / 2]. This is to improve behavior for searching
3252 // the median in already sorted ranges.
3253 immutable lo = r.length / 2 - pivot, hi = lo + ninth;
3254 // We have either one straggler on the left, one on the right, or none.
3255 assert(lo - (r.length - hi) <= 1 || (r.length - hi) - lo <= 1);
3256 assert(lo >= ninth * 4);
3257 assert(r.length - hi >= ninth * 4);
3258
3259 // Partition in groups of 3, and the mid tertile again in groups of 3
3260 if (!useSampling)
3261 p3!lp(r, lo - ninth, hi + ninth);
3262 p3!lp(r, lo, hi);
3263
3264 // Get the median of medians of medians
3265 // Map the full interval of n to the full interval of the ninth
3266 pivot = (n * (ninth - 1)) / (r.length - 1);
3267 topNImpl!lp(r[lo .. hi], pivot, useSampling);
3268 return expandPartition!lp(r, lo, pivot + lo, hi);
3269 }
3270
p3(alias less,Range)3271 private void p3(alias less, Range)(Range r, size_t lo, immutable size_t hi)
3272 {
3273 assert(lo <= hi && hi < r.length);
3274 immutable ln = hi - lo;
3275 for (; lo < hi; ++lo)
3276 {
3277 assert(lo >= ln);
3278 assert(lo + ln < r.length);
3279 medianOf!less(r, lo - ln, lo, lo + ln);
3280 }
3281 }
3282
3283 private void p4(alias less, Flag!"leanRight" f, Range)
3284 (Range r, size_t lo, immutable size_t hi)
3285 {
3286 assert(lo <= hi && hi < r.length);
3287 immutable ln = hi - lo, _2ln = ln * 2;
3288 for (; lo < hi; ++lo)
3289 {
3290 assert(lo >= ln);
3291 assert(lo + ln < r.length);
3292 static if (f == Yes.leanRight)
3293 medianOf!(less, f)(r, lo - _2ln, lo - ln, lo, lo + ln);
3294 else
3295 medianOf!(less, f)(r, lo - ln, lo, lo + ln, lo + _2ln);
3296 }
3297 }
3298
3299 private size_t topNPartitionOffMedian(alias lp, Flag!"leanRight" f, R)
3300 (R r, size_t n, bool useSampling)
3301 {
3302 assert(r.length >= 12);
3303 assert(n < r.length);
3304 immutable _4 = r.length / 4;
3305 static if (f == Yes.leanRight)
3306 immutable leftLimit = 2 * _4;
3307 else
3308 immutable leftLimit = _4;
3309 // Partition in groups of 4, and the left quartile again in groups of 3
3310 if (!useSampling)
3311 {
3312 p4!(lp, f)(r, leftLimit, leftLimit + _4);
3313 }
3314 immutable _12 = _4 / 3;
3315 immutable lo = leftLimit + _12, hi = lo + _12;
3316 p3!lp(r, lo, hi);
3317
3318 // Get the median of medians of medians
3319 // Map the full interval of n to the full interval of the ninth
3320 immutable pivot = (n * (_12 - 1)) / (r.length - 1);
3321 topNImpl!lp(r[lo .. hi], pivot, useSampling);
3322 return expandPartition!lp(r, lo, pivot + lo, hi);
3323 }
3324
3325 /*
3326 Params:
3327 less = predicate
3328 r = range to partition
3329 pivot = pivot to partition around
3330 lo = value such that r[lo .. pivot] already less than r[pivot]
3331 hi = value such that r[pivot .. hi] already greater than r[pivot]
3332
3333 Returns: new position of pivot
3334 */
3335 private
expandPartition(alias lp,R)3336 size_t expandPartition(alias lp, R)(R r, size_t lo, size_t pivot, size_t hi)
3337 in
3338 {
3339 import std.algorithm.searching : all;
3340 assert(lo <= pivot);
3341 assert(pivot < hi);
3342 assert(hi <= r.length);
3343 assert(r[lo .. pivot + 1].all!(x => !lp(r[pivot], x)));
3344 assert(r[pivot + 1 .. hi].all!(x => !lp(x, r[pivot])));
3345 }
3346 out
3347 {
3348 import std.algorithm.searching : all;
3349 assert(r[0 .. pivot + 1].all!(x => !lp(r[pivot], x)));
3350 assert(r[pivot + 1 .. r.length].all!(x => !lp(x, r[pivot])));
3351 }
3352 body
3353 {
3354 import std.algorithm.mutation : swapAt;
3355 import std.algorithm.searching : all;
3356 // We work with closed intervals!
3357 --hi;
3358
3359 size_t left = 0, rite = r.length - 1;
3360 loop: for (;; ++left, --rite)
3361 {
3362 for (;; ++left)
3363 {
3364 if (left == lo) break loop;
3365 if (!lp(r[left], r[pivot])) break;
3366 }
3367 for (;; --rite)
3368 {
3369 if (rite == hi) break loop;
3370 if (!lp(r[pivot], r[rite])) break;
3371 }
3372 r.swapAt(left, rite);
3373 }
3374
3375 assert(r[lo .. pivot + 1].all!(x => !lp(r[pivot], x)));
3376 assert(r[pivot + 1 .. hi + 1].all!(x => !lp(x, r[pivot])));
3377 assert(r[0 .. left].all!(x => !lp(r[pivot], x)));
3378 assert(r[rite + 1 .. r.length].all!(x => !lp(x, r[pivot])));
3379
3380 immutable oldPivot = pivot;
3381
3382 if (left < lo)
3383 {
3384 // First loop: spend r[lo .. pivot]
3385 for (; lo < pivot; ++left)
3386 {
3387 if (left == lo) goto done;
3388 if (!lp(r[oldPivot], r[left])) continue;
3389 --pivot;
3390 assert(!lp(r[oldPivot], r[pivot]));
3391 r.swapAt(left, pivot);
3392 }
3393 // Second loop: make left and pivot meet
3394 for (;; ++left)
3395 {
3396 if (left == pivot) goto done;
3397 if (!lp(r[oldPivot], r[left])) continue;
3398 for (;;)
3399 {
3400 if (left == pivot) goto done;
3401 --pivot;
3402 if (lp(r[pivot], r[oldPivot]))
3403 {
3404 r.swapAt(left, pivot);
3405 break;
3406 }
3407 }
3408 }
3409 }
3410
3411 // First loop: spend r[lo .. pivot]
3412 for (; hi != pivot; --rite)
3413 {
3414 if (rite == hi) goto done;
3415 if (!lp(r[rite], r[oldPivot])) continue;
3416 ++pivot;
3417 assert(!lp(r[pivot], r[oldPivot]));
3418 r.swapAt(rite, pivot);
3419 }
3420 // Second loop: make left and pivot meet
3421 for (; rite > pivot; --rite)
3422 {
3423 if (!lp(r[rite], r[oldPivot])) continue;
3424 while (rite > pivot)
3425 {
3426 ++pivot;
3427 if (lp(r[oldPivot], r[pivot]))
3428 {
3429 r.swapAt(rite, pivot);
3430 break;
3431 }
3432 }
3433 }
3434
3435 done:
3436 r.swapAt(oldPivot, pivot);
3437 return pivot;
3438 }
3439
3440 @safe unittest
3441 {
3442 auto a = [ 10, 5, 3, 4, 8, 11, 13, 3, 9, 4, 10 ];
3443 assert(expandPartition!((a, b) => a < b)(a, 4, 5, 6) == 9);
3444 a = randomArray;
3445 if (a.length == 0) return;
3446 expandPartition!((a, b) => a < b)(a, a.length / 2, a.length / 2,
3447 a.length / 2 + 1);
3448 }
3449
version(unittest)3450 version (unittest)
3451 private T[] randomArray(Flag!"exactSize" flag = No.exactSize, T = int)(
3452 size_t maxSize = 1000,
3453 T minValue = 0, T maxValue = 255)
3454 {
3455 import std.algorithm.iteration : map;
3456 import std.random : unpredictableSeed, Random, uniform;
3457 auto size = flag == Yes.exactSize ? maxSize : uniform(1, maxSize);
3458 return iota(0, size).map!(_ => uniform(minValue, maxValue)).array;
3459 }
3460
3461 @safe unittest
3462 {
3463 import std.algorithm.comparison : max, min;
3464 import std.algorithm.iteration : reduce;
3465
3466 int[] v = [ 7, 6, 5, 4, 3, 2, 1, 0 ];
3467 ptrdiff_t n = 3;
3468 topN!("a < b")(v, n);
3469 assert(reduce!max(v[0 .. n]) <= v[n]);
3470 assert(reduce!min(v[n + 1 .. $]) >= v[n]);
3471 //
3472 v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3473 n = 3;
3474 topN(v, n);
3475 assert(reduce!max(v[0 .. n]) <= v[n]);
3476 assert(reduce!min(v[n + 1 .. $]) >= v[n]);
3477 //
3478 v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3479 n = 1;
3480 topN(v, n);
3481 assert(reduce!max(v[0 .. n]) <= v[n]);
3482 assert(reduce!min(v[n + 1 .. $]) >= v[n]);
3483 //
3484 v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3485 n = v.length - 1;
3486 topN(v, n);
3487 assert(v[n] == 7);
3488 //
3489 v = [3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5];
3490 n = 0;
3491 topN(v, n);
3492 assert(v[n] == 1);
3493
3494 double[][] v1 = [[-10, -5], [-10, -3], [-10, -5], [-10, -4],
3495 [-10, -5], [-9, -5], [-9, -3], [-9, -5],];
3496
3497 // double[][] v1 = [ [-10, -5], [-10, -4], [-9, -5], [-9, -5],
3498 // [-10, -5], [-10, -3], [-10, -5], [-9, -3],];
3499 double[]*[] idx = [ &v1[0], &v1[1], &v1[2], &v1[3], &v1[4], &v1[5], &v1[6],
3500 &v1[7], ];
3501
3502 auto mid = v1.length / 2;
3503 topN!((a, b){ return (*a)[1] < (*b)[1]; })(idx, mid);
3504 foreach (e; idx[0 .. mid]) assert((*e)[1] <= (*idx[mid])[1]);
3505 foreach (e; idx[mid .. $]) assert((*e)[1] >= (*idx[mid])[1]);
3506 }
3507
3508 @safe unittest
3509 {
3510 import std.algorithm.comparison : max, min;
3511 import std.algorithm.iteration : reduce;
3512 import std.random : Random, uniform, unpredictableSeed;
3513
3514 immutable uint[] seeds = [90027751, 2709791795, 1374631933, 995751648, 3541495258, 984840953, unpredictableSeed];
foreach(s;seeds)3515 foreach (s; seeds)
3516 {
3517 auto r = Random(s);
3518
3519 int[] a = new int[uniform(1, 10000, r)];
3520 foreach (ref e; a) e = uniform(-1000, 1000, r);
3521
3522 auto k = uniform(0, a.length, r);
3523 topN(a, k);
3524 if (k > 0)
3525 {
3526 auto left = reduce!max(a[0 .. k]);
3527 assert(left <= a[k]);
3528 }
3529 if (k + 1 < a.length)
3530 {
3531 auto right = reduce!min(a[k + 1 .. $]);
3532 assert(right >= a[k]);
3533 }
3534 }
3535 }
3536
3537 // bug 12987
3538 @safe unittest
3539 {
3540 int[] a = [ 25, 7, 9, 2, 0, 5, 21 ];
3541 auto n = 4;
3542 auto t = topN(a, n);
3543 sort(t);
3544 assert(t == [0, 2, 5, 7]);
3545 }
3546
3547 /**
3548 Stores the smallest elements of the two ranges in the left-hand range.
3549
3550 Params:
3551 less = The predicate to sort by.
3552 ss = The swapping strategy to use.
3553 r1 = The first range.
3554 r2 = The second range.
3555 */
3556 auto topN(alias less = "a < b",
3557 SwapStrategy ss = SwapStrategy.unstable,
3558 Range1, Range2)(Range1 r1, Range2 r2)
3559 if (isRandomAccessRange!(Range1) && hasLength!Range1 &&
3560 isInputRange!Range2 && is(ElementType!Range1 == ElementType!Range2) &&
3561 hasLvalueElements!Range1 && hasLvalueElements!Range2)
3562 {
3563 import std.container : BinaryHeap;
3564
3565 static assert(ss == SwapStrategy.unstable,
3566 "Stable topN not yet implemented");
3567
3568 auto heap = BinaryHeap!(Range1, less)(r1);
foreach(ref e;r2)3569 foreach (ref e; r2)
3570 {
3571 heap.conditionalSwap(e);
3572 }
3573
3574 return r1;
3575 }
3576
3577 ///
3578 @system unittest
3579 {
3580 int[] a = [ 5, 7, 2, 6, 7 ];
3581 int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
3582 topN(a, b);
3583 sort(a);
3584 assert(a == [0, 1, 2, 2, 3]);
3585 }
3586
3587 // bug 15421
3588 @system unittest
3589 {
3590 import std.algorithm.comparison : equal;
3591 import std.internal.test.dummyrange;
3592 import std.meta : AliasSeq;
3593
3594 alias RandomRanges = AliasSeq!(
3595 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random)
3596 );
3597
3598 alias ReferenceRanges = AliasSeq!(
3599 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Forward),
3600 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Bidirectional),
3601 DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random),
3602 DummyRange!(ReturnBy.Reference, Length.No, RangeType.Forward),
3603 DummyRange!(ReturnBy.Reference, Length.No, RangeType.Bidirectional));
3604
foreach(T1;RandomRanges)3605 foreach (T1; RandomRanges)
3606 {
3607 foreach (T2; ReferenceRanges)
3608 {
3609 import std.array;
3610
3611 T1 A;
3612 T2 B;
3613
3614 A.reinit();
3615 B.reinit();
3616
3617 topN(A, B);
3618
3619 // BUG(?): sort doesn't accept DummyRanges (needs Slicing and Length)
3620 auto a = array(A);
3621 auto b = array(B);
3622 sort(a);
3623 sort(b);
3624
3625 assert(equal(a, [ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 ]));
3626 assert(equal(b, [ 6, 6, 7, 7, 8, 8, 9, 9, 10, 10 ]));
3627 }
3628 }
3629 }
3630
3631 // bug 15421
3632 @system unittest
3633 {
3634 auto a = [ 9, 8, 0, 3, 5, 25, 43, 4, 2, 0, 7 ];
3635 auto b = [ 9, 8, 0, 3, 5, 25, 43, 4, 2, 0, 7 ];
3636
3637 topN(a, 4);
3638 topN(b[0 .. 4], b[4 .. $]);
3639
3640 sort(a[0 .. 4]);
3641 sort(a[4 .. $]);
3642 sort(b[0 .. 4]);
3643 sort(b[4 .. $]);
3644
3645 assert(a[0 .. 4] == b[0 .. 4]);
3646 assert(a[4 .. $] == b[4 .. $]);
3647 assert(a == b);
3648 }
3649
3650 // bug 12987
3651 @system unittest
3652 {
3653 int[] a = [ 5, 7, 2, 6, 7 ];
3654 int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
3655 auto t = topN(a, b);
3656 sort(t);
3657 assert(t == [ 0, 1, 2, 2, 3 ]);
3658 }
3659
3660 // bug 15420
3661 @system unittest
3662 {
3663 int[] a = [ 5, 7, 2, 6, 7 ];
3664 int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
3665 topN!"a > b"(a, b);
3666 sort!"a > b"(a);
3667 assert(a == [ 7, 7, 7, 6, 6 ]);
3668 }
3669
3670 /**
3671 Copies the top $(D n) elements of the
3672 $(REF_ALTTEXT input range, isInputRange, std,range,primitives) $(D source) into the
3673 random-access range $(D target), where $(D n =
3674 target.length). Elements of $(D source) are not touched. If $(D
3675 sorted) is $(D true), the target is sorted. Otherwise, the target
3676 respects the $(HTTP en.wikipedia.org/wiki/Binary_heap, heap property).
3677
3678 Params:
3679 less = The predicate to sort by.
3680 source = The source range.
3681 target = The target range.
3682 sorted = Whether to sort the elements copied into `target`.
3683
3684 Returns: The slice of `target` containing the copied elements.
3685 */
3686 TRange topNCopy(alias less = "a < b", SRange, TRange)
3687 (SRange source, TRange target, SortOutput sorted = No.sortOutput)
3688 if (isInputRange!(SRange) && isRandomAccessRange!(TRange)
3689 && hasLength!(TRange) && hasSlicing!(TRange))
3690 {
3691 import std.container : BinaryHeap;
3692
3693 if (target.empty) return target;
3694 auto heap = BinaryHeap!(TRange, less)(target, 0);
3695 foreach (e; source) heap.conditionalInsert(e);
3696 auto result = target[0 .. heap.length];
3697 if (sorted == Yes.sortOutput)
3698 {
3699 while (!heap.empty) heap.removeFront();
3700 }
3701 return result;
3702 }
3703
3704 ///
3705 @system unittest
3706 {
3707 import std.typecons : Yes;
3708
3709 int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
3710 int[] b = new int[3];
3711 topNCopy(a, b, Yes.sortOutput);
3712 assert(b == [ 0, 1, 2 ]);
3713 }
3714
3715 @system unittest
3716 {
3717 import std.random : Random, unpredictableSeed, uniform, randomShuffle;
3718 import std.typecons : Yes;
3719
3720 auto r = Random(unpredictableSeed);
3721 ptrdiff_t[] a = new ptrdiff_t[uniform(1, 1000, r)];
3722 foreach (i, ref e; a) e = i;
3723 randomShuffle(a, r);
3724 auto n = uniform(0, a.length, r);
3725 ptrdiff_t[] b = new ptrdiff_t[n];
3726 topNCopy!(binaryFun!("a < b"))(a, b, Yes.sortOutput);
3727 assert(isSorted!(binaryFun!("a < b"))(b));
3728 }
3729
3730 /**
3731 Given a range of elements, constructs an index of its top $(I n) elements
3732 (i.e., the first $(I n) elements if the range were sorted).
3733
3734 Similar to $(LREF topN), except that the range is not modified.
3735
3736 Params:
3737 less = A binary predicate that defines the ordering of range elements.
3738 Defaults to $(D a < b).
3739 ss = $(RED (Not implemented yet.)) Specify the swapping strategy.
3740 r = A
3741 $(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives)
3742 of elements to make an index for.
3743 index = A
3744 $(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives)
3745 with assignable elements to build the index in. The length of this range
3746 determines how many top elements to index in $(D r).
3747
3748 This index range can either have integral elements, in which case the
3749 constructed index will consist of zero-based numerical indices into
3750 $(D r); or it can have pointers to the element type of $(D r), in which
3751 case the constructed index will be pointers to the top elements in
3752 $(D r).
3753 sorted = Determines whether to sort the index by the elements they refer
3754 to.
3755
3756 See_also: $(LREF topN), $(LREF topNCopy).
3757
3758 BUGS:
3759 The swapping strategy parameter is not implemented yet; currently it is
3760 ignored.
3761 */
3762 void topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
3763 Range, RangeIndex)
3764 (Range r, RangeIndex index, SortOutput sorted = No.sortOutput)
3765 if (isRandomAccessRange!Range &&
3766 isRandomAccessRange!RangeIndex &&
3767 hasAssignableElements!RangeIndex)
3768 {
3769 static assert(ss == SwapStrategy.unstable,
3770 "Stable swap strategy not implemented yet.");
3771
3772 import std.container.binaryheap : BinaryHeap;
3773 if (index.empty) return;
3774
3775 static if (isIntegral!(ElementType!(RangeIndex)))
3776 {
3777 import std.exception : enforce;
3778
3779 enforce(ElementType!(RangeIndex).max >= index.length,
3780 "Index type too small");
3781 bool indirectLess(ElementType!(RangeIndex) a, ElementType!(RangeIndex) b)
3782 {
3783 return binaryFun!(less)(r[a], r[b]);
3784 }
3785 auto heap = BinaryHeap!(RangeIndex, indirectLess)(index, 0);
3786 foreach (i; 0 .. r.length)
3787 {
3788 heap.conditionalInsert(cast(ElementType!RangeIndex) i);
3789 }
3790
3791 }
3792 else static if (is(ElementType!(RangeIndex) == ElementType!(Range)*))
3793 {
3794 static bool indirectLess(const ElementType!(RangeIndex) a,
3795 const ElementType!(RangeIndex) b)
3796 {
3797 return binaryFun!less(*a, *b);
3798 }
3799 auto heap = BinaryHeap!(RangeIndex, indirectLess)(index, 0);
3800 foreach (i; 0 .. r.length)
3801 {
3802 heap.conditionalInsert(&r[i]);
3803 }
3804 }
3805 else static assert(0, "Invalid ElementType");
3806
3807 if (sorted == Yes.sortOutput)
3808 {
3809 while (!heap.empty) heap.removeFront();
3810 }
3811 }
3812
3813 ///
3814 @system unittest
3815 {
3816 import std.typecons : Yes;
3817
3818 // Construct index to top 3 elements using numerical indices:
3819 int[] a = [ 10, 2, 7, 5, 8, 1 ];
3820 int[] index = new int[3];
3821 topNIndex(a, index, Yes.sortOutput);
3822 assert(index == [5, 1, 3]); // because a[5]==1, a[1]==2, a[3]==5
3823
3824 // Construct index to top 3 elements using pointer indices:
3825 int*[] ptrIndex = new int*[3];
3826 topNIndex(a, ptrIndex, Yes.sortOutput);
3827 assert(ptrIndex == [ &a[5], &a[1], &a[3] ]);
3828 }
3829
3830 @system unittest
3831 {
3832 import std.conv : text;
3833
3834 {
3835 int[] a = [ 10, 8, 9, 2, 4, 6, 7, 1, 3, 5 ];
3836 int*[] b = new int*[5];
3837 topNIndex!("a > b")(a, b, Yes.sortOutput);
3838 assert(b == [ &a[0], &a[2], &a[1], &a[6], &a[5]]);
3839 }
3840 {
3841 int[] a = [ 10, 8, 9, 2, 4, 6, 7, 1, 3, 5 ];
3842 auto b = new ubyte[5];
3843 topNIndex!("a > b")(a, b, Yes.sortOutput);
3844 assert(b == [ cast(ubyte) 0, cast(ubyte) 2, cast(ubyte) 1, cast(ubyte) 6, cast(ubyte) 5], text(b));
3845 }
3846 }
3847
3848 // medianOf
3849 /*
3850 Private for the time being.
3851
3852 Computes the median of 2 to 5 arbitrary indexes in random-access range `r`
3853 using hand-written specialized algorithms. The indexes must be distinct (if not,
3854 behavior is implementation-defined). The function also partitions the elements
3855 involved around the median, e.g. $(D medianOf(r, a, b, c)) not only fills `r[b]`
3856 with the median of `r[a]`, `r[b]`, and `r[c]`, but also puts the minimum in
3857 `r[a]` and the maximum in `r[c]`.
3858
3859 Params:
3860 less = The comparison predicate used, modeled as a
3861 $(LINK2 https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings, strict weak ordering)
3862 (irreflexive, antisymmetric, transitive, and implying a transitive equivalence).
3863 flag = Used only for even values of `T.length`. If `No.leanRight`, the median
3864 "leans left", meaning $(D medianOf(r, a, b, c, d)) puts the lower median of the
3865 four in `r[b]`, the minimum in `r[a]`, and the two others in `r[c]` and `r[d]`.
3866 Conversely, $(D median!("a < b", Yes.leanRight)(r, a, b, c, d)) puts the upper
3867 median of the four in `r[c]`, the maximum in `r[d]`, and the two others in
3868 `r[a]` and `r[b]`.
3869 r = The range containing the indexes.
3870 i = Two to five indexes inside `r`.
3871 */
3872 private void medianOf(
3873 alias less = "a < b",
3874 Flag!"leanRight" flag = No.leanRight,
3875 Range,
3876 Indexes...)
3877 (Range r, Indexes i)
3878 if (isRandomAccessRange!Range && hasLength!Range &&
3879 Indexes.length >= 2 && Indexes.length <= 5 &&
3880 allSatisfy!(isUnsigned, Indexes))
3881 {
3882 assert(r.length >= Indexes.length);
3883 import std.functional : binaryFun;
3884 alias lt = binaryFun!less;
3885 enum k = Indexes.length;
3886 import std.algorithm.mutation : swapAt;
3887
3888 alias a = i[0];
3889 static assert(is(typeof(a) == size_t));
3890 static if (k >= 2)
3891 {
3892 alias b = i[1];
3893 static assert(is(typeof(b) == size_t));
3894 assert(a != b);
3895 }
3896 static if (k >= 3)
3897 {
3898 alias c = i[2];
3899 static assert(is(typeof(c) == size_t));
3900 assert(a != c && b != c);
3901 }
3902 static if (k >= 4)
3903 {
3904 alias d = i[3];
3905 static assert(is(typeof(d) == size_t));
3906 assert(a != d && b != d && c != d);
3907 }
3908 static if (k >= 5)
3909 {
3910 alias e = i[4];
3911 static assert(is(typeof(e) == size_t));
3912 assert(a != e && b != e && c != e && d != e);
3913 }
3914
3915 static if (k == 2)
3916 {
3917 if (lt(r[b], r[a])) r.swapAt(a, b);
3918 }
3919 else static if (k == 3)
3920 {
3921 if (lt(r[c], r[a])) // c < a
3922 {
3923 if (lt(r[a], r[b])) // c < a < b
3924 {
3925 r.swapAt(a, b);
3926 r.swapAt(a, c);
3927 }
3928 else // c < a, b <= a
3929 {
3930 r.swapAt(a, c);
3931 if (lt(r[b], r[a])) r.swapAt(a, b);
3932 }
3933 }
3934 else // a <= c
3935 {
3936 if (lt(r[b], r[a])) // b < a <= c
3937 {
3938 r.swapAt(a, b);
3939 }
3940 else // a <= c, a <= b
3941 {
3942 if (lt(r[c], r[b])) r.swapAt(b, c);
3943 }
3944 }
3945 assert(!lt(r[b], r[a]));
3946 assert(!lt(r[c], r[b]));
3947 }
3948 else static if (k == 4)
3949 {
3950 static if (flag == No.leanRight)
3951 {
3952 // Eliminate the rightmost from the competition
3953 if (lt(r[d], r[c])) r.swapAt(c, d); // c <= d
3954 if (lt(r[d], r[b])) r.swapAt(b, d); // b <= d
3955 medianOf!lt(r, a, b, c);
3956 }
3957 else
3958 {
3959 // Eliminate the leftmost from the competition
3960 if (lt(r[b], r[a])) r.swapAt(a, b); // a <= b
3961 if (lt(r[c], r[a])) r.swapAt(a, c); // a <= c
3962 medianOf!lt(r, b, c, d);
3963 }
3964 }
3965 else static if (k == 5)
3966 {
3967 // Credit: Teppo Niinimäki
scope(success)3968 version (unittest) scope(success)
3969 {
3970 assert(!lt(r[c], r[a]));
3971 assert(!lt(r[c], r[b]));
3972 assert(!lt(r[d], r[c]));
3973 assert(!lt(r[e], r[c]));
3974 }
3975
3976 if (lt(r[c], r[a])) r.swapAt(a, c);
3977 if (lt(r[d], r[b])) r.swapAt(b, d);
3978 if (lt(r[d], r[c]))
3979 {
3980 r.swapAt(c, d);
3981 r.swapAt(a, b);
3982 }
3983 if (lt(r[e], r[b])) r.swapAt(b, e);
3984 if (lt(r[e], r[c]))
3985 {
3986 r.swapAt(c, e);
3987 if (lt(r[c], r[a])) r.swapAt(a, c);
3988 }
3989 else
3990 {
3991 if (lt(r[c], r[b])) r.swapAt(b, c);
3992 }
3993 }
3994 }
3995
3996 @safe unittest
3997 {
3998 // Verify medianOf for all permutations of [1, 2, 2, 3, 4].
3999 int[5] data = [1, 2, 2, 3, 4];
4000 do
4001 {
4002 int[5] a = data;
4003 medianOf(a[], size_t(0), size_t(1));
4004 assert(a[0] <= a[1]);
4005
4006 a[] = data[];
4007 medianOf(a[], size_t(0), size_t(1), size_t(2));
4008 assert(ordered(a[0], a[1], a[2]));
4009
4010 a[] = data[];
4011 medianOf(a[], size_t(0), size_t(1), size_t(2), size_t(3));
4012 assert(a[0] <= a[1] && a[1] <= a[2] && a[1] <= a[3]);
4013
4014 a[] = data[];
4015 medianOf!("a < b", Yes.leanRight)(a[], size_t(0), size_t(1),
4016 size_t(2), size_t(3));
4017 assert(a[0] <= a[2] && a[1] <= a[2] && a[2] <= a[3]);
4018
4019 a[] = data[];
4020 medianOf(a[], size_t(0), size_t(1), size_t(2), size_t(3), size_t(4));
4021 assert(a[0] <= a[2] && a[1] <= a[2] && a[2] <= a[3] && a[2] <= a[4]);
4022 }
4023 while (nextPermutation(data[]));
4024 }
4025
4026 // nextPermutation
4027 /**
4028 * Permutes $(D range) in-place to the next lexicographically greater
4029 * permutation.
4030 *
4031 * The predicate $(D less) defines the lexicographical ordering to be used on
4032 * the range.
4033 *
4034 * If the range is currently the lexicographically greatest permutation, it is
4035 * permuted back to the least permutation and false is returned. Otherwise,
4036 * true is returned. One can thus generate all permutations of a range by
4037 * sorting it according to $(D less), which produces the lexicographically
4038 * least permutation, and then calling nextPermutation until it returns false.
4039 * This is guaranteed to generate all distinct permutations of the range
4040 * exactly once. If there are $(I N) elements in the range and all of them are
4041 * unique, then $(I N)! permutations will be generated. Otherwise, if there are
4042 * some duplicated elements, fewer permutations will be produced.
4043 ----
4044 // Enumerate all permutations
4045 int[] a = [1,2,3,4,5];
4046 do
4047 {
4048 // use the current permutation and
4049 // proceed to the next permutation of the array.
4050 } while (nextPermutation(a));
4051 ----
4052 * Params:
4053 * less = The ordering to be used to determine lexicographical ordering of the
4054 * permutations.
4055 * range = The range to permute.
4056 *
4057 * Returns: false if the range was lexicographically the greatest, in which
4058 * case the range is reversed back to the lexicographically smallest
4059 * permutation; otherwise returns true.
4060 * See_Also:
4061 * $(REF permutations, std,algorithm,iteration).
4062 */
4063 bool nextPermutation(alias less="a < b", BidirectionalRange)
4064 (BidirectionalRange range)
4065 if (isBidirectionalRange!BidirectionalRange &&
4066 hasSwappableElements!BidirectionalRange)
4067 {
4068 import std.algorithm.mutation : reverse, swap;
4069 import std.algorithm.searching : find;
4070 import std.range : retro, takeExactly;
4071 // Ranges of 0 or 1 element have no distinct permutations.
4072 if (range.empty) return false;
4073
4074 auto i = retro(range);
4075 auto last = i.save;
4076
4077 // Find last occurring increasing pair of elements
4078 size_t n = 1;
4079 for (i.popFront(); !i.empty; i.popFront(), last.popFront(), n++)
4080 {
4081 if (binaryFun!less(i.front, last.front))
4082 break;
4083 }
4084
4085 if (i.empty)
4086 {
4087 // Entire range is decreasing: it's lexicographically the greatest. So
4088 // wrap it around.
4089 range.reverse();
4090 return false;
4091 }
4092
4093 // Find last element greater than i.front.
4094 auto j = find!((a) => binaryFun!less(i.front, a))(
4095 takeExactly(retro(range), n));
4096
4097 assert(!j.empty); // shouldn't happen since i.front < last.front
4098 swap(i.front, j.front);
4099 reverse(takeExactly(retro(range), n));
4100
4101 return true;
4102 }
4103
4104 ///
4105 @safe unittest
4106 {
4107 // Step through all permutations of a sorted array in lexicographic order
4108 int[] a = [1,2,3];
4109 assert(nextPermutation(a) == true);
4110 assert(a == [1,3,2]);
4111 assert(nextPermutation(a) == true);
4112 assert(a == [2,1,3]);
4113 assert(nextPermutation(a) == true);
4114 assert(a == [2,3,1]);
4115 assert(nextPermutation(a) == true);
4116 assert(a == [3,1,2]);
4117 assert(nextPermutation(a) == true);
4118 assert(a == [3,2,1]);
4119 assert(nextPermutation(a) == false);
4120 assert(a == [1,2,3]);
4121 }
4122
4123 ///
4124 @safe unittest
4125 {
4126 // Step through permutations of an array containing duplicate elements:
4127 int[] a = [1,1,2];
4128 assert(nextPermutation(a) == true);
4129 assert(a == [1,2,1]);
4130 assert(nextPermutation(a) == true);
4131 assert(a == [2,1,1]);
4132 assert(nextPermutation(a) == false);
4133 assert(a == [1,1,2]);
4134 }
4135
4136 @safe unittest
4137 {
4138 // Boundary cases: arrays of 0 or 1 element.
4139 int[] a1 = [];
4140 assert(!nextPermutation(a1));
4141 assert(a1 == []);
4142
4143 int[] a2 = [1];
4144 assert(!nextPermutation(a2));
4145 assert(a2 == [1]);
4146 }
4147
4148 @safe unittest
4149 {
4150 import std.algorithm.comparison : equal;
4151
4152 auto a1 = [1, 2, 3, 4];
4153
4154 assert(nextPermutation(a1));
4155 assert(equal(a1, [1, 2, 4, 3]));
4156
4157 assert(nextPermutation(a1));
4158 assert(equal(a1, [1, 3, 2, 4]));
4159
4160 assert(nextPermutation(a1));
4161 assert(equal(a1, [1, 3, 4, 2]));
4162
4163 assert(nextPermutation(a1));
4164 assert(equal(a1, [1, 4, 2, 3]));
4165
4166 assert(nextPermutation(a1));
4167 assert(equal(a1, [1, 4, 3, 2]));
4168
4169 assert(nextPermutation(a1));
4170 assert(equal(a1, [2, 1, 3, 4]));
4171
4172 assert(nextPermutation(a1));
4173 assert(equal(a1, [2, 1, 4, 3]));
4174
4175 assert(nextPermutation(a1));
4176 assert(equal(a1, [2, 3, 1, 4]));
4177
4178 assert(nextPermutation(a1));
4179 assert(equal(a1, [2, 3, 4, 1]));
4180
4181 assert(nextPermutation(a1));
4182 assert(equal(a1, [2, 4, 1, 3]));
4183
4184 assert(nextPermutation(a1));
4185 assert(equal(a1, [2, 4, 3, 1]));
4186
4187 assert(nextPermutation(a1));
4188 assert(equal(a1, [3, 1, 2, 4]));
4189
4190 assert(nextPermutation(a1));
4191 assert(equal(a1, [3, 1, 4, 2]));
4192
4193 assert(nextPermutation(a1));
4194 assert(equal(a1, [3, 2, 1, 4]));
4195
4196 assert(nextPermutation(a1));
4197 assert(equal(a1, [3, 2, 4, 1]));
4198
4199 assert(nextPermutation(a1));
4200 assert(equal(a1, [3, 4, 1, 2]));
4201
4202 assert(nextPermutation(a1));
4203 assert(equal(a1, [3, 4, 2, 1]));
4204
4205 assert(nextPermutation(a1));
4206 assert(equal(a1, [4, 1, 2, 3]));
4207
4208 assert(nextPermutation(a1));
4209 assert(equal(a1, [4, 1, 3, 2]));
4210
4211 assert(nextPermutation(a1));
4212 assert(equal(a1, [4, 2, 1, 3]));
4213
4214 assert(nextPermutation(a1));
4215 assert(equal(a1, [4, 2, 3, 1]));
4216
4217 assert(nextPermutation(a1));
4218 assert(equal(a1, [4, 3, 1, 2]));
4219
4220 assert(nextPermutation(a1));
4221 assert(equal(a1, [4, 3, 2, 1]));
4222
4223 assert(!nextPermutation(a1));
4224 assert(equal(a1, [1, 2, 3, 4]));
4225 }
4226
4227 @safe unittest
4228 {
4229 // Test with non-default sorting order
4230 int[] a = [3,2,1];
4231 assert(nextPermutation!"a > b"(a) == true);
4232 assert(a == [3,1,2]);
4233 assert(nextPermutation!"a > b"(a) == true);
4234 assert(a == [2,3,1]);
4235 assert(nextPermutation!"a > b"(a) == true);
4236 assert(a == [2,1,3]);
4237 assert(nextPermutation!"a > b"(a) == true);
4238 assert(a == [1,3,2]);
4239 assert(nextPermutation!"a > b"(a) == true);
4240 assert(a == [1,2,3]);
4241 assert(nextPermutation!"a > b"(a) == false);
4242 assert(a == [3,2,1]);
4243 }
4244
4245 // Issue 13594
4246 @safe unittest
4247 {
4248 int[3] a = [1,2,3];
4249 assert(nextPermutation(a[]));
4250 assert(a == [1,3,2]);
4251 }
4252
4253 // nextEvenPermutation
4254 /**
4255 * Permutes $(D range) in-place to the next lexicographically greater $(I even)
4256 * permutation.
4257 *
4258 * The predicate $(D less) defines the lexicographical ordering to be used on
4259 * the range.
4260 *
4261 * An even permutation is one which is produced by swapping an even number of
4262 * pairs of elements in the original range. The set of $(I even) permutations
4263 * is distinct from the set of $(I all) permutations only when there are no
4264 * duplicate elements in the range. If the range has $(I N) unique elements,
4265 * then there are exactly $(I N)!/2 even permutations.
4266 *
4267 * If the range is already the lexicographically greatest even permutation, it
4268 * is permuted back to the least even permutation and false is returned.
4269 * Otherwise, true is returned, and the range is modified in-place to be the
4270 * lexicographically next even permutation.
4271 *
4272 * One can thus generate the even permutations of a range with unique elements
4273 * by starting with the lexicographically smallest permutation, and repeatedly
4274 * calling nextEvenPermutation until it returns false.
4275 ----
4276 // Enumerate even permutations
4277 int[] a = [1,2,3,4,5];
4278 do
4279 {
4280 // use the current permutation and
4281 // proceed to the next even permutation of the array.
4282 } while (nextEvenPermutation(a));
4283 ----
4284 * One can also generate the $(I odd) permutations of a range by noting that
4285 * permutations obey the rule that even + even = even, and odd + even = odd.
4286 * Thus, by swapping the last two elements of a lexicographically least range,
4287 * it is turned into the first odd permutation. Then calling
4288 * nextEvenPermutation on this first odd permutation will generate the next
4289 * even permutation relative to this odd permutation, which is actually the
4290 * next odd permutation of the original range. Thus, by repeatedly calling
4291 * nextEvenPermutation until it returns false, one enumerates the odd
4292 * permutations of the original range.
4293 ----
4294 // Enumerate odd permutations
4295 int[] a = [1,2,3,4,5];
4296 swap(a[$-2], a[$-1]); // a is now the first odd permutation of [1,2,3,4,5]
4297 do
4298 {
4299 // use the current permutation and
4300 // proceed to the next odd permutation of the original array
4301 // (which is an even permutation of the first odd permutation).
4302 } while (nextEvenPermutation(a));
4303 ----
4304 *
4305 * Warning: Since even permutations are only distinct from all permutations
4306 * when the range elements are unique, this function assumes that there are no
4307 * duplicate elements under the specified ordering. If this is not _true, some
4308 * permutations may fail to be generated. When the range has non-unique
4309 * elements, you should use $(MYREF nextPermutation) instead.
4310 *
4311 * Params:
4312 * less = The ordering to be used to determine lexicographical ordering of the
4313 * permutations.
4314 * range = The range to permute.
4315 *
4316 * Returns: false if the range was lexicographically the greatest, in which
4317 * case the range is reversed back to the lexicographically smallest
4318 * permutation; otherwise returns true.
4319 */
4320 bool nextEvenPermutation(alias less="a < b", BidirectionalRange)
4321 (BidirectionalRange range)
4322 if (isBidirectionalRange!BidirectionalRange &&
4323 hasSwappableElements!BidirectionalRange)
4324 {
4325 import std.algorithm.mutation : reverse, swap;
4326 import std.algorithm.searching : find;
4327 import std.range : retro, takeExactly;
4328 // Ranges of 0 or 1 element have no distinct permutations.
4329 if (range.empty) return false;
4330
4331 bool oddParity = false;
4332 bool ret = true;
4333 do
4334 {
4335 auto i = retro(range);
4336 auto last = i.save;
4337
4338 // Find last occurring increasing pair of elements
4339 size_t n = 1;
4340 for (i.popFront(); !i.empty;
4341 i.popFront(), last.popFront(), n++)
4342 {
4343 if (binaryFun!less(i.front, last.front))
4344 break;
4345 }
4346
4347 if (!i.empty)
4348 {
4349 // Find last element greater than i.front.
4350 auto j = find!((a) => binaryFun!less(i.front, a))(
4351 takeExactly(retro(range), n));
4352
4353 // shouldn't happen since i.front < last.front
4354 assert(!j.empty);
4355
4356 swap(i.front, j.front);
4357 oddParity = !oddParity;
4358 }
4359 else
4360 {
4361 // Entire range is decreasing: it's lexicographically
4362 // the greatest.
4363 ret = false;
4364 }
4365
4366 reverse(takeExactly(retro(range), n));
4367 if ((n / 2) % 2 == 1)
4368 oddParity = !oddParity;
4369 } while (oddParity);
4370
4371 return ret;
4372 }
4373
4374 ///
4375 @safe unittest
4376 {
4377 // Step through even permutations of a sorted array in lexicographic order
4378 int[] a = [1,2,3];
4379 assert(nextEvenPermutation(a) == true);
4380 assert(a == [2,3,1]);
4381 assert(nextEvenPermutation(a) == true);
4382 assert(a == [3,1,2]);
4383 assert(nextEvenPermutation(a) == false);
4384 assert(a == [1,2,3]);
4385 }
4386
4387 @safe unittest
4388 {
4389 auto a3 = [ 1, 2, 3, 4 ];
4390 int count = 1;
4391 while (nextEvenPermutation(a3)) count++;
4392 assert(count == 12);
4393 }
4394
4395 @safe unittest
4396 {
4397 // Test with non-default sorting order
4398 auto a = [ 3, 2, 1 ];
4399
4400 assert(nextEvenPermutation!"a > b"(a) == true);
4401 assert(a == [ 2, 1, 3 ]);
4402 assert(nextEvenPermutation!"a > b"(a) == true);
4403 assert(a == [ 1, 3, 2 ]);
4404 assert(nextEvenPermutation!"a > b"(a) == false);
4405 assert(a == [ 3, 2, 1 ]);
4406 }
4407
4408 @safe unittest
4409 {
4410 // Test various cases of rollover
4411 auto a = [ 3, 1, 2 ];
4412 assert(nextEvenPermutation(a) == false);
4413 assert(a == [ 1, 2, 3 ]);
4414
4415 auto b = [ 3, 2, 1 ];
4416 assert(nextEvenPermutation(b) == false);
4417 assert(b == [ 1, 3, 2 ]);
4418 }
4419
4420 @safe unittest
4421 {
4422 // Issue 13594
4423 int[3] a = [1,2,3];
4424 assert(nextEvenPermutation(a[]));
4425 assert(a == [2,3,1]);
4426 }
4427
4428 /**
4429 Even permutations are useful for generating coordinates of certain geometric
4430 shapes. Here's a non-trivial example:
4431 */
4432 @safe unittest
4433 {
4434 import std.math : sqrt;
4435
4436 // Print the 60 vertices of a uniform truncated icosahedron (soccer ball)
4437 enum real Phi = (1.0 + sqrt(5.0)) / 2.0; // Golden ratio
4438 real[][] seeds = [
4439 [0.0, 1.0, 3.0*Phi],
4440 [1.0, 2.0+Phi, 2.0*Phi],
4441 [Phi, 2.0, Phi^^3]
4442 ];
4443 size_t n;
foreach(seed;seeds)4444 foreach (seed; seeds)
4445 {
4446 // Loop over even permutations of each seed
4447 do
4448 {
4449 // Loop over all sign changes of each permutation
4450 size_t i;
4451 do
4452 {
4453 // Generate all possible sign changes
4454 for (i=0; i < seed.length; i++)
4455 {
4456 if (seed[i] != 0.0)
4457 {
4458 seed[i] = -seed[i];
4459 if (seed[i] < 0.0)
4460 break;
4461 }
4462 }
4463 n++;
4464 } while (i < seed.length);
4465 } while (nextEvenPermutation(seed));
4466 }
4467 assert(n == 60);
4468 }
4469