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