1 /*
2 * C++ implementation of timsort
3 *
4 * ported from Python's and OpenJDK's:
5 * - http://svn.python.org/projects/python/trunk/Objects/listobject.c
6 * - http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
7 *
8 * Copyright (c) 2011 Fuji, Goro (gfx) <gfuji@cpan.org>.
9 * Copyright (c) 2019-2021 Morwenn.
10 * Copyright (c) 2021 Igor Kushnir <igorkuo@gmail.com>.
11 *
12 * Permission is hereby granted, free of charge, to any person obtaining a copy
13 * of this software and associated documentation files (the "Software"), to
14 * deal in the Software without restriction, including without limitation the
15 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
16 * sell copies of the Software, and to permit persons to whom the Software is
17 * furnished to do so, subject to the following conditions:
18 *
19 * The above copyright notice and this permission notice shall be included in
20 * all copies or substantial portions of the Software.
21 *
22 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
27 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
28 * IN THE SOFTWARE.
29 */
30
31 #ifndef GFX_TIMSORT_HPP
32 #define GFX_TIMSORT_HPP
33
34 #include <algorithm>
35 #include <functional>
36 #include <iterator>
37 #include <utility>
38 #include <vector>
39
40 // Semantic versioning macros
41
42 #define GFX_TIMSORT_VERSION_MAJOR 2
43 #define GFX_TIMSORT_VERSION_MINOR 1
44 #define GFX_TIMSORT_VERSION_PATCH 0
45
46 // Diagnostic selection macros
47
48 #if defined(GFX_TIMSORT_ENABLE_ASSERT) || defined(GFX_TIMSORT_ENABLE_AUDIT)
49 # include <cassert>
50 #endif
51
52 #ifdef GFX_TIMSORT_ENABLE_ASSERT
53 # define GFX_TIMSORT_ASSERT(expr) assert(expr)
54 #else
55 # define GFX_TIMSORT_ASSERT(expr) ((void)0)
56 #endif
57
58 #ifdef GFX_TIMSORT_ENABLE_AUDIT
59 # define GFX_TIMSORT_AUDIT(expr) assert(expr)
60 #else
61 # define GFX_TIMSORT_AUDIT(expr) ((void)0)
62 #endif
63
64 #ifdef GFX_TIMSORT_ENABLE_LOG
65 # include <iostream>
66 # define GFX_TIMSORT_LOG(expr) (std::clog << "# " << __func__ << ": " << expr << std::endl)
67 #else
68 # define GFX_TIMSORT_LOG(expr) ((void)0)
69 #endif
70
71
72 namespace gfx {
73
74 // ---------------------------------------
75 // Implementation details
76 // ---------------------------------------
77
78 namespace detail {
79
80 // Equivalent to C++20 std::identity
81 struct identity {
82 template <typename T>
operator ()gfx::detail::identity83 constexpr T&& operator()(T&& value) const noexcept
84 {
85 return std::forward<T>(value);
86 }
87 };
88
89 // Merge a predicate and a projection function
90 template <typename Compare, typename Projection>
91 struct projection_compare {
projection_comparegfx::detail::projection_compare92 projection_compare(Compare comp, Projection proj) : compare(comp), projection(proj) {
93 }
94
95 template <typename T, typename U>
operator ()gfx::detail::projection_compare96 bool operator()(T &&lhs, U &&rhs) {
97 #ifdef __cpp_lib_invoke
98 return static_cast<bool>(std::invoke(compare,
99 std::invoke(projection, std::forward<T>(lhs)),
100 std::invoke(projection, std::forward<U>(rhs))
101 ));
102 #else
103 return static_cast<bool>(compare(
104 projection(std::forward<T>(lhs)),
105 projection(std::forward<U>(rhs))
106 ));
107 #endif
108 }
109
110 Compare compare;
111 Projection projection;
112 };
113
114 template <typename Iterator> struct run {
115 typedef typename std::iterator_traits<Iterator>::difference_type diff_t;
116
117 Iterator base;
118 diff_t len;
119
rungfx::detail::run120 run(Iterator b, diff_t l) : base(b), len(l) {
121 }
122 };
123
124 template <typename RandomAccessIterator, typename Compare> class TimSort {
125 typedef RandomAccessIterator iter_t;
126 typedef typename std::iterator_traits<iter_t>::value_type value_t;
127 typedef typename std::iterator_traits<iter_t>::reference ref_t;
128 typedef typename std::iterator_traits<iter_t>::difference_type diff_t;
129
130 static const int MIN_MERGE = 32;
131 static const int MIN_GALLOP = 7;
132
133 int minGallop_; // default to MIN_GALLOP
134
135 std::vector<value_t> tmp_; // temp storage for merges
136 typedef typename std::vector<value_t>::iterator tmp_iter_t;
137
138 std::vector<run<RandomAccessIterator> > pending_;
139
binarySort(iter_t const lo,iter_t const hi,iter_t start,Compare compare)140 static void binarySort(iter_t const lo, iter_t const hi, iter_t start, Compare compare) {
141 GFX_TIMSORT_ASSERT(lo <= start);
142 GFX_TIMSORT_ASSERT(start <= hi);
143 if (start == lo) {
144 ++start;
145 }
146 for (; start < hi; ++start) {
147 GFX_TIMSORT_ASSERT(lo <= start);
148 value_t pivot = std::move(*start);
149
150 iter_t const pos = std::upper_bound(lo, start, pivot, compare);
151 for (iter_t p = start; p > pos; --p) {
152 *p = std::move(*(p - 1));
153 }
154 *pos = std::move(pivot);
155 }
156 }
157
countRunAndMakeAscending(iter_t const lo,iter_t const hi,Compare compare)158 static diff_t countRunAndMakeAscending(iter_t const lo, iter_t const hi, Compare compare) {
159 GFX_TIMSORT_ASSERT(lo < hi);
160
161 iter_t runHi = lo + 1;
162 if (runHi == hi) {
163 return 1;
164 }
165
166 if (compare(*runHi, *lo)) { // decreasing
167 do {
168 ++runHi;
169 } while (runHi < hi && compare(*runHi, *(runHi - 1)));
170 std::reverse(lo, runHi);
171 } else { // non-decreasing
172 do {
173 ++runHi;
174 } while (runHi < hi && !compare(*runHi, *(runHi - 1)));
175 }
176
177 return runHi - lo;
178 }
179
minRunLength(diff_t n)180 static diff_t minRunLength(diff_t n) {
181 GFX_TIMSORT_ASSERT(n >= 0);
182
183 diff_t r = 0;
184 while (n >= 2 * MIN_MERGE) {
185 r |= (n & 1);
186 n >>= 1;
187 }
188 return n + r;
189 }
190
TimSort()191 TimSort() : minGallop_(MIN_GALLOP) {
192 }
193
194 // Silence GCC -Winline warning
~TimSort()195 ~TimSort() {}
196
pushRun(iter_t const runBase,diff_t const runLen)197 void pushRun(iter_t const runBase, diff_t const runLen) {
198 pending_.push_back(run<iter_t>(runBase, runLen));
199 }
200
mergeCollapse(Compare compare)201 void mergeCollapse(Compare compare) {
202 while (pending_.size() > 1) {
203 diff_t n = pending_.size() - 2;
204
205 if ((n > 0 && pending_[n - 1].len <= pending_[n].len + pending_[n + 1].len) ||
206 (n > 1 && pending_[n - 2].len <= pending_[n - 1].len + pending_[n].len)) {
207 if (pending_[n - 1].len < pending_[n + 1].len) {
208 --n;
209 }
210 mergeAt(n, compare);
211 } else if (pending_[n].len <= pending_[n + 1].len) {
212 mergeAt(n, compare);
213 } else {
214 break;
215 }
216 }
217 }
218
mergeForceCollapse(Compare compare)219 void mergeForceCollapse(Compare compare) {
220 while (pending_.size() > 1) {
221 diff_t n = pending_.size() - 2;
222
223 if (n > 0 && pending_[n - 1].len < pending_[n + 1].len) {
224 --n;
225 }
226 mergeAt(n, compare);
227 }
228 }
229
mergeAt(diff_t const i,Compare compare)230 void mergeAt(diff_t const i, Compare compare) {
231 diff_t const stackSize = pending_.size();
232 GFX_TIMSORT_ASSERT(stackSize >= 2);
233 GFX_TIMSORT_ASSERT(i >= 0);
234 GFX_TIMSORT_ASSERT(i == stackSize - 2 || i == stackSize - 3);
235
236 iter_t base1 = pending_[i].base;
237 diff_t len1 = pending_[i].len;
238 iter_t base2 = pending_[i + 1].base;
239 diff_t len2 = pending_[i + 1].len;
240
241 pending_[i].len = len1 + len2;
242
243 if (i == stackSize - 3) {
244 pending_[i + 1] = pending_[i + 2];
245 }
246
247 pending_.pop_back();
248
249 mergeConsecutiveRuns(base1, len1, base2, len2, std::move(compare));
250 }
251
mergeConsecutiveRuns(iter_t base1,diff_t len1,iter_t base2,diff_t len2,Compare compare)252 void mergeConsecutiveRuns(iter_t base1, diff_t len1, iter_t base2, diff_t len2, Compare compare) {
253 GFX_TIMSORT_ASSERT(len1 > 0);
254 GFX_TIMSORT_ASSERT(len2 > 0);
255 GFX_TIMSORT_ASSERT(base1 + len1 == base2);
256
257 diff_t const k = gallopRight(*base2, base1, len1, 0, compare);
258 GFX_TIMSORT_ASSERT(k >= 0);
259
260 base1 += k;
261 len1 -= k;
262
263 if (len1 == 0) {
264 return;
265 }
266
267 len2 = gallopLeft(*(base1 + (len1 - 1)), base2, len2, len2 - 1, compare);
268 GFX_TIMSORT_ASSERT(len2 >= 0);
269 if (len2 == 0) {
270 return;
271 }
272
273 if (len1 <= len2) {
274 mergeLo(base1, len1, base2, len2, compare);
275 } else {
276 mergeHi(base1, len1, base2, len2, compare);
277 }
278 }
279
280 template <typename Iter>
gallopLeft(ref_t key,Iter const base,diff_t const len,diff_t const hint,Compare compare)281 static diff_t gallopLeft(ref_t key, Iter const base, diff_t const len,
282 diff_t const hint, Compare compare) {
283 GFX_TIMSORT_ASSERT(len > 0);
284 GFX_TIMSORT_ASSERT(hint >= 0);
285 GFX_TIMSORT_ASSERT(hint < len);
286
287 diff_t lastOfs = 0;
288 diff_t ofs = 1;
289
290 if (compare(*(base + hint), key)) {
291 diff_t const maxOfs = len - hint;
292 while (ofs < maxOfs && compare(*(base + (hint + ofs)), key)) {
293 lastOfs = ofs;
294 ofs = (ofs << 1) + 1;
295
296 if (ofs <= 0) { // int overflow
297 ofs = maxOfs;
298 }
299 }
300 if (ofs > maxOfs) {
301 ofs = maxOfs;
302 }
303
304 lastOfs += hint;
305 ofs += hint;
306 } else {
307 diff_t const maxOfs = hint + 1;
308 while (ofs < maxOfs && !compare(*(base + (hint - ofs)), key)) {
309 lastOfs = ofs;
310 ofs = (ofs << 1) + 1;
311
312 if (ofs <= 0) {
313 ofs = maxOfs;
314 }
315 }
316 if (ofs > maxOfs) {
317 ofs = maxOfs;
318 }
319
320 diff_t const tmp = lastOfs;
321 lastOfs = hint - ofs;
322 ofs = hint - tmp;
323 }
324 GFX_TIMSORT_ASSERT(-1 <= lastOfs);
325 GFX_TIMSORT_ASSERT(lastOfs < ofs);
326 GFX_TIMSORT_ASSERT(ofs <= len);
327
328 return std::lower_bound(base + (lastOfs + 1), base + ofs, key, compare) - base;
329 }
330
331 template <typename Iter>
gallopRight(ref_t key,Iter const base,diff_t const len,diff_t const hint,Compare compare)332 static diff_t gallopRight(ref_t key, Iter const base, diff_t const len,
333 diff_t const hint, Compare compare) {
334 GFX_TIMSORT_ASSERT(len > 0);
335 GFX_TIMSORT_ASSERT(hint >= 0);
336 GFX_TIMSORT_ASSERT(hint < len);
337
338 diff_t ofs = 1;
339 diff_t lastOfs = 0;
340
341 if (compare(key, *(base + hint))) {
342 diff_t const maxOfs = hint + 1;
343 while (ofs < maxOfs && compare(key, *(base + (hint - ofs)))) {
344 lastOfs = ofs;
345 ofs = (ofs << 1) + 1;
346
347 if (ofs <= 0) {
348 ofs = maxOfs;
349 }
350 }
351 if (ofs > maxOfs) {
352 ofs = maxOfs;
353 }
354
355 diff_t const tmp = lastOfs;
356 lastOfs = hint - ofs;
357 ofs = hint - tmp;
358 } else {
359 diff_t const maxOfs = len - hint;
360 while (ofs < maxOfs && !compare(key, *(base + (hint + ofs)))) {
361 lastOfs = ofs;
362 ofs = (ofs << 1) + 1;
363
364 if (ofs <= 0) { // int overflow
365 ofs = maxOfs;
366 }
367 }
368 if (ofs > maxOfs) {
369 ofs = maxOfs;
370 }
371
372 lastOfs += hint;
373 ofs += hint;
374 }
375 GFX_TIMSORT_ASSERT(-1 <= lastOfs);
376 GFX_TIMSORT_ASSERT(lastOfs < ofs);
377 GFX_TIMSORT_ASSERT(ofs <= len);
378
379 return std::upper_bound(base + (lastOfs + 1), base + ofs, key, compare) - base;
380 }
381
rotateLeft(iter_t first,iter_t last)382 static void rotateLeft(iter_t first, iter_t last)
383 {
384 value_t tmp = std::move(*first);
385 iter_t last_1 = std::move(first + 1, last, first);
386 *last_1 = std::move(tmp);
387 }
388
rotateRight(iter_t first,iter_t last)389 static void rotateRight(iter_t first, iter_t last)
390 {
391 iter_t last_1 = last - 1;
392 value_t tmp = std::move(*last_1);
393 std::move_backward(first, last_1, last);
394 *first = std::move(tmp);
395 }
396
397
mergeLo(iter_t const base1,diff_t len1,iter_t const base2,diff_t len2,Compare compare)398 void mergeLo(iter_t const base1, diff_t len1, iter_t const base2, diff_t len2, Compare compare) {
399 GFX_TIMSORT_ASSERT(len1 > 0);
400 GFX_TIMSORT_ASSERT(len2 > 0);
401 GFX_TIMSORT_ASSERT(base1 + len1 == base2);
402
403 if (len1 == 1) {
404 return rotateLeft(base1, base2 + len2);
405 }
406 if (len2 == 1) {
407 return rotateRight(base1, base2 + len2);
408 }
409
410 copy_to_tmp(base1, len1);
411
412 tmp_iter_t cursor1 = tmp_.begin();
413 iter_t cursor2 = base2;
414 iter_t dest = base1;
415
416 *dest = std::move(*cursor2);
417 ++cursor2;
418 ++dest;
419 --len2;
420
421 int minGallop(minGallop_);
422
423 // outer:
424 while (true) {
425 diff_t count1 = 0;
426 diff_t count2 = 0;
427
428 do {
429 GFX_TIMSORT_ASSERT(len1 > 1);
430 GFX_TIMSORT_ASSERT(len2 > 0);
431
432 if (compare(*cursor2, *cursor1)) {
433 *dest = std::move(*cursor2);
434 ++cursor2;
435 ++dest;
436 ++count2;
437 count1 = 0;
438 if (--len2 == 0) {
439 goto epilogue;
440 }
441 } else {
442 *dest = std::move(*cursor1);
443 ++cursor1;
444 ++dest;
445 ++count1;
446 count2 = 0;
447 if (--len1 == 1) {
448 goto epilogue;
449 }
450 }
451 } while ((count1 | count2) < minGallop);
452
453 do {
454 GFX_TIMSORT_ASSERT(len1 > 1);
455 GFX_TIMSORT_ASSERT(len2 > 0);
456
457 count1 = gallopRight(*cursor2, cursor1, len1, 0, compare);
458 if (count1 != 0) {
459 std::move_backward(cursor1, cursor1 + count1, dest + count1);
460 dest += count1;
461 cursor1 += count1;
462 len1 -= count1;
463
464 if (len1 <= 1) {
465 goto epilogue;
466 }
467 }
468 *dest = std::move(*cursor2);
469 ++cursor2;
470 ++dest;
471 if (--len2 == 0) {
472 goto epilogue;
473 }
474
475 count2 = gallopLeft(*cursor1, cursor2, len2, 0, compare);
476 if (count2 != 0) {
477 std::move(cursor2, cursor2 + count2, dest);
478 dest += count2;
479 cursor2 += count2;
480 len2 -= count2;
481 if (len2 == 0) {
482 goto epilogue;
483 }
484 }
485 *dest = std::move(*cursor1);
486 ++cursor1;
487 ++dest;
488 if (--len1 == 1) {
489 goto epilogue;
490 }
491
492 --minGallop;
493 } while ((count1 >= MIN_GALLOP) | (count2 >= MIN_GALLOP));
494
495 if (minGallop < 0) {
496 minGallop = 0;
497 }
498 minGallop += 2;
499 } // end of "outer" loop
500
501 epilogue: // merge what is left from either cursor1 or cursor2
502
503 minGallop_ = (std::min)(minGallop, 1);
504
505 if (len1 == 1) {
506 GFX_TIMSORT_ASSERT(len2 > 0);
507 std::move(cursor2, cursor2 + len2, dest);
508 *(dest + len2) = std::move(*cursor1);
509 } else {
510 GFX_TIMSORT_ASSERT(len1 != 0 && "Comparison function violates its general contract");
511 GFX_TIMSORT_ASSERT(len2 == 0);
512 GFX_TIMSORT_ASSERT(len1 > 1);
513 std::move(cursor1, cursor1 + len1, dest);
514 }
515 }
516
mergeHi(iter_t const base1,diff_t len1,iter_t const base2,diff_t len2,Compare compare)517 void mergeHi(iter_t const base1, diff_t len1, iter_t const base2, diff_t len2, Compare compare) {
518 GFX_TIMSORT_ASSERT(len1 > 0);
519 GFX_TIMSORT_ASSERT(len2 > 0);
520 GFX_TIMSORT_ASSERT(base1 + len1 == base2);
521
522 if (len1 == 1) {
523 return rotateLeft(base1, base2 + len2);
524 }
525 if (len2 == 1) {
526 return rotateRight(base1, base2 + len2);
527 }
528
529 copy_to_tmp(base2, len2);
530
531 iter_t cursor1 = base1 + len1;
532 tmp_iter_t cursor2 = tmp_.begin() + (len2 - 1);
533 iter_t dest = base2 + (len2 - 1);
534
535 *dest = std::move(*(--cursor1));
536 --dest;
537 --len1;
538
539 int minGallop(minGallop_);
540
541 // outer:
542 while (true) {
543 diff_t count1 = 0;
544 diff_t count2 = 0;
545
546 // The next loop is a hot path of the algorithm, so we decrement
547 // eagerly the cursor so that it always points directly to the value
548 // to compare, but we have to implement some trickier logic to make
549 // sure that it points to the next value again by the end of said loop
550 --cursor1;
551
552 do {
553 GFX_TIMSORT_ASSERT(len1 > 0);
554 GFX_TIMSORT_ASSERT(len2 > 1);
555
556 if (compare(*cursor2, *cursor1)) {
557 *dest = std::move(*cursor1);
558 --dest;
559 ++count1;
560 count2 = 0;
561 if (--len1 == 0) {
562 goto epilogue;
563 }
564 --cursor1;
565 } else {
566 *dest = std::move(*cursor2);
567 --cursor2;
568 --dest;
569 ++count2;
570 count1 = 0;
571 if (--len2 == 1) {
572 ++cursor1; // See comment before the loop
573 goto epilogue;
574 }
575 }
576 } while ((count1 | count2) < minGallop);
577 ++cursor1; // See comment before the loop
578
579 do {
580 GFX_TIMSORT_ASSERT(len1 > 0);
581 GFX_TIMSORT_ASSERT(len2 > 1);
582
583 count1 = len1 - gallopRight(*cursor2, base1, len1, len1 - 1, compare);
584 if (count1 != 0) {
585 dest -= count1;
586 cursor1 -= count1;
587 len1 -= count1;
588 std::move_backward(cursor1, cursor1 + count1, dest + (1 + count1));
589
590 if (len1 == 0) {
591 goto epilogue;
592 }
593 }
594 *dest = std::move(*cursor2);
595 --cursor2;
596 --dest;
597 if (--len2 == 1) {
598 goto epilogue;
599 }
600
601 count2 = len2 - gallopLeft(*(cursor1 - 1), tmp_.begin(), len2, len2 - 1, compare);
602 if (count2 != 0) {
603 dest -= count2;
604 cursor2 -= count2;
605 len2 -= count2;
606 std::move(cursor2 + 1, cursor2 + (1 + count2), dest + 1);
607 if (len2 <= 1) {
608 goto epilogue;
609 }
610 }
611 *dest = std::move(*(--cursor1));
612 --dest;
613 if (--len1 == 0) {
614 goto epilogue;
615 }
616
617 --minGallop;
618 } while ((count1 >= MIN_GALLOP) | (count2 >= MIN_GALLOP));
619
620 if (minGallop < 0) {
621 minGallop = 0;
622 }
623 minGallop += 2;
624 } // end of "outer" loop
625
626 epilogue: // merge what is left from either cursor1 or cursor2
627
628 minGallop_ = (std::min)(minGallop, 1);
629
630 if (len2 == 1) {
631 GFX_TIMSORT_ASSERT(len1 > 0);
632 dest -= len1;
633 std::move_backward(cursor1 - len1, cursor1, dest + (1 + len1));
634 *dest = std::move(*cursor2);
635 } else {
636 GFX_TIMSORT_ASSERT(len2 != 0 && "Comparison function violates its general contract");
637 GFX_TIMSORT_ASSERT(len1 == 0);
638 GFX_TIMSORT_ASSERT(len2 > 1);
639 std::move(tmp_.begin(), tmp_.begin() + len2, dest - (len2 - 1));
640 }
641 }
642
copy_to_tmp(iter_t const begin,diff_t len)643 void copy_to_tmp(iter_t const begin, diff_t len) {
644 tmp_.assign(std::make_move_iterator(begin),
645 std::make_move_iterator(begin + len));
646 }
647
648 public:
649
merge(iter_t const lo,iter_t const mid,iter_t const hi,Compare compare)650 static void merge(iter_t const lo, iter_t const mid, iter_t const hi, Compare compare) {
651 GFX_TIMSORT_ASSERT(lo <= mid);
652 GFX_TIMSORT_ASSERT(mid <= hi);
653
654 if (lo == mid || mid == hi) {
655 return; // nothing to do
656 }
657
658 TimSort ts;
659 ts.mergeConsecutiveRuns(lo, mid - lo, mid, hi - mid, std::move(compare));
660
661 GFX_TIMSORT_LOG("1st size: " << (mid - lo) << "; 2nd size: " << (hi - mid)
662 << "; tmp_.size(): " << ts.tmp_.size());
663 }
664
sort(iter_t const lo,iter_t const hi,Compare compare)665 static void sort(iter_t const lo, iter_t const hi, Compare compare) {
666 GFX_TIMSORT_ASSERT(lo <= hi);
667
668 diff_t nRemaining = (hi - lo);
669 if (nRemaining < 2) {
670 return; // nothing to do
671 }
672
673 if (nRemaining < MIN_MERGE) {
674 diff_t const initRunLen = countRunAndMakeAscending(lo, hi, compare);
675 GFX_TIMSORT_LOG("initRunLen: " << initRunLen);
676 binarySort(lo, hi, lo + initRunLen, compare);
677 return;
678 }
679
680 TimSort ts;
681 diff_t const minRun = minRunLength(nRemaining);
682 iter_t cur = lo;
683 do {
684 diff_t runLen = countRunAndMakeAscending(cur, hi, compare);
685
686 if (runLen < minRun) {
687 diff_t const force = (std::min)(nRemaining, minRun);
688 binarySort(cur, cur + force, cur + runLen, compare);
689 runLen = force;
690 }
691
692 ts.pushRun(cur, runLen);
693 ts.mergeCollapse(compare);
694
695 cur += runLen;
696 nRemaining -= runLen;
697 } while (nRemaining != 0);
698
699 GFX_TIMSORT_ASSERT(cur == hi);
700 ts.mergeForceCollapse(compare);
701 GFX_TIMSORT_ASSERT(ts.pending_.size() == 1);
702
703 GFX_TIMSORT_LOG("size: " << (hi - lo) << " tmp_.size(): " << ts.tmp_.size()
704 << " pending_.size(): " << ts.pending_.size());
705 }
706 };
707
708 } // namespace detail
709
710
711 // ---------------------------------------
712 // Public interface implementation
713 // ---------------------------------------
714
715 /**
716 * Stably merges two consecutive sorted ranges [first, middle) and [middle, last) into one
717 * sorted range [first, last) with a comparison function and a projection function.
718 */
719 template <typename RandomAccessIterator, typename Compare, typename Projection>
timmerge(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last,Compare compare,Projection projection)720 void timmerge(RandomAccessIterator first, RandomAccessIterator middle,
721 RandomAccessIterator last, Compare compare, Projection projection) {
722 typedef detail::projection_compare<Compare, Projection> compare_t;
723 compare_t comp(std::move(compare), std::move(projection));
724 GFX_TIMSORT_AUDIT(std::is_sorted(first, middle, comp) && "Precondition");
725 GFX_TIMSORT_AUDIT(std::is_sorted(middle, last, comp) && "Precondition");
726 detail::TimSort<RandomAccessIterator, compare_t>::merge(first, middle, last, comp);
727 GFX_TIMSORT_AUDIT(std::is_sorted(first, last, comp) && "Postcondition");
728 }
729
730 /**
731 * Same as std::inplace_merge(first, middle, last, compare).
732 */
733 template <typename RandomAccessIterator, typename Compare>
timmerge(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last,Compare compare)734 void timmerge(RandomAccessIterator first, RandomAccessIterator middle,
735 RandomAccessIterator last, Compare compare) {
736 gfx::timmerge(first, middle, last, compare, detail::identity());
737 }
738
739 /**
740 * Same as std::inplace_merge(first, middle, last).
741 */
742 template <typename RandomAccessIterator>
timmerge(RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last)743 void timmerge(RandomAccessIterator first, RandomAccessIterator middle,
744 RandomAccessIterator last) {
745 typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
746 gfx::timmerge(first, middle, last, std::less<value_type>(), detail::identity());
747 }
748
749 /**
750 * Stably sorts a range with a comparison function and a projection function.
751 */
752 template <typename RandomAccessIterator, typename Compare, typename Projection>
timsort(RandomAccessIterator const first,RandomAccessIterator const last,Compare compare,Projection projection)753 void timsort(RandomAccessIterator const first, RandomAccessIterator const last,
754 Compare compare, Projection projection) {
755 typedef detail::projection_compare<Compare, Projection> compare_t;
756 compare_t comp(std::move(compare), std::move(projection));
757 detail::TimSort<RandomAccessIterator, compare_t>::sort(first, last, comp);
758 GFX_TIMSORT_AUDIT(std::is_sorted(first, last, comp) && "Postcondition");
759 }
760
761 /**
762 * Same as std::stable_sort(first, last, compare).
763 */
764 template <typename RandomAccessIterator, typename Compare>
timsort(RandomAccessIterator const first,RandomAccessIterator const last,Compare compare)765 void timsort(RandomAccessIterator const first, RandomAccessIterator const last, Compare compare) {
766 gfx::timsort(first, last, compare, detail::identity());
767 }
768
769 /**
770 * Same as std::stable_sort(first, last).
771 */
772 template <typename RandomAccessIterator>
timsort(RandomAccessIterator const first,RandomAccessIterator const last)773 void timsort(RandomAccessIterator const first, RandomAccessIterator const last) {
774 typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
775 gfx::timsort(first, last, std::less<value_type>(), detail::identity());
776 }
777
778 /**
779 * Stably sorts a range with a comparison function and a projection function.
780 */
781 template <typename RandomAccessRange, typename Compare, typename Projection>
timsort(RandomAccessRange & range,Compare compare,Projection projection)782 void timsort(RandomAccessRange &range, Compare compare, Projection projection) {
783 gfx::timsort(std::begin(range), std::end(range), compare, projection);
784 }
785
786 /**
787 * Same as std::stable_sort(std::begin(range), std::end(range), compare).
788 */
789 template <typename RandomAccessRange, typename Compare>
timsort(RandomAccessRange & range,Compare compare)790 void timsort(RandomAccessRange &range, Compare compare) {
791 gfx::timsort(std::begin(range), std::end(range), compare);
792 }
793
794 /**
795 * Same as std::stable_sort(std::begin(range), std::end(range)).
796 */
797 template <typename RandomAccessRange>
timsort(RandomAccessRange & range)798 void timsort(RandomAccessRange &range) {
799 gfx::timsort(std::begin(range), std::end(range));
800 }
801
802 } // namespace gfx
803
804 #undef GFX_TIMSORT_ENABLE_ASSERT
805 #undef GFX_TIMSORT_ASSERT
806 #undef GFX_TIMSORT_ENABLE_AUDIT
807 #undef GFX_TIMSORT_AUDIT
808 #undef GFX_TIMSORT_ENABLE_LOG
809 #undef GFX_TIMSORT_LOG
810
811 #endif // GFX_TIMSORT_HPP
812