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