SHARE
TWEET

https://habr.com/ru/post/484798/

a guest Jan 21st, 2020 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <ctime>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <chrono>
  7. #include <cstdlib>
  8. #include <functional>
  9. #include <string>
  10.  
  11. /*
  12.  * C++ implementation of timsort
  13.  *
  14.  * ported from Python's and OpenJDK's:
  15.  * - http://svn.python.org/projects/python/trunk/Objects/listobject.c
  16.  * - http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
  17.  *
  18.  * Copyright (c) 2011 Fuji, Goro (gfx) <gfuji@cpan.org>.
  19.  * Copyright (c) 2019 Morwenn.
  20.  *
  21.  * Permission is hereby granted, free of charge, to any person obtaining a copy
  22.  * of this software and associated documentation files (the "Software"), to
  23.  * deal in the Software without restriction, including without limitation the
  24.  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  25.  * sell copies of the Software, and to permit persons to whom the Software is
  26.  * furnished to do so, subject to the following conditions:
  27.  *
  28.  * The above copyright notice and this permission notice shall be included in
  29.  * all copies or substantial portions of the Software.
  30.  *
  31.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  32.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  33.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  34.  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  35.  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  36.  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  37.  * IN THE SOFTWARE.
  38.  */
  39.  
  40. #ifndef GFX_TIMSORT_HPP
  41. #define GFX_TIMSORT_HPP
  42.  
  43. #include <algorithm>
  44. #include <functional>
  45. #include <iterator>
  46. #include <utility>
  47. #include <vector>
  48.  
  49. // Semantic versioning macros
  50.  
  51. #define GFX_TIMSORT_VERSION_MAJOR 2
  52. #define GFX_TIMSORT_VERSION_MINOR 0
  53. #define GFX_TIMSORT_VERSION_PATCH 0
  54.  
  55. // Diagnostic selection macros
  56.  
  57. #ifdef GFX_TIMSORT_ENABLE_ASSERT
  58. #   include <cassert>
  59. #   define GFX_TIMSORT_ASSERT(expr) assert(expr)
  60. #else
  61. #   define GFX_TIMSORT_ASSERT(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>
  83.     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 {
  92.     projection_compare(Compare comp, Projection proj) : compare(comp), projection(proj) {
  93.     }
  94.  
  95.     template <typename T, typename U>
  96.     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.  
  120.     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.  
  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.  
  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.  
  180.     static diff_t minRunLength(diff_t n) {
  181.         GFX_TIMSORT_ASSERT(n >= 0);
  182.  
  183.         diff_t r = 0;
  184.         while (n >= MIN_MERGE) {
  185.             r |= (n & 1);
  186.             n >>= 1;
  187.         }
  188.         return n + r;
  189.     }
  190.  
  191.     TimSort() : minGallop_(MIN_GALLOP) {
  192.     }
  193.  
  194.     // Silence GCC -Winline warning
  195.     ~TimSort() {}
  196.  
  197.     void pushRun(iter_t const runBase, diff_t const runLen) {
  198.         pending_.push_back(run<iter_t>(runBase, runLen));
  199.     }
  200.  
  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.  
  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.  
  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.         GFX_TIMSORT_ASSERT(len1 > 0);
  242.         GFX_TIMSORT_ASSERT(len2 > 0);
  243.         GFX_TIMSORT_ASSERT(base1 + len1 == base2);
  244.  
  245.         pending_[i].len = len1 + len2;
  246.  
  247.         if (i == stackSize - 3) {
  248.             pending_[i + 1] = pending_[i + 2];
  249.         }
  250.  
  251.         pending_.pop_back();
  252.  
  253.         diff_t const k = gallopRight(*base2, base1, len1, 0, compare);
  254.         GFX_TIMSORT_ASSERT(k >= 0);
  255.  
  256.         base1 += k;
  257.         len1 -= k;
  258.  
  259.         if (len1 == 0) {
  260.             return;
  261.         }
  262.  
  263.         len2 = gallopLeft(*(base1 + (len1 - 1)), base2, len2, len2 - 1, compare);
  264.         GFX_TIMSORT_ASSERT(len2 >= 0);
  265.         if (len2 == 0) {
  266.             return;
  267.         }
  268.  
  269.         if (len1 <= len2) {
  270.             mergeLo(base1, len1, base2, len2, compare);
  271.         } else {
  272.             mergeHi(base1, len1, base2, len2, compare);
  273.         }
  274.     }
  275.  
  276.     template <typename Iter>
  277.     diff_t gallopLeft(ref_t key, Iter const base, diff_t const len, diff_t const hint, Compare compare) {
  278.         GFX_TIMSORT_ASSERT(len > 0);
  279.         GFX_TIMSORT_ASSERT(hint >= 0);
  280.         GFX_TIMSORT_ASSERT(hint < len);
  281.  
  282.         diff_t lastOfs = 0;
  283.         diff_t ofs = 1;
  284.  
  285.         if (compare(*(base + hint), key)) {
  286.             diff_t const maxOfs = len - hint;
  287.             while (ofs < maxOfs && compare(*(base + (hint + ofs)), key)) {
  288.                 lastOfs = ofs;
  289.                 ofs = (ofs << 1) + 1;
  290.  
  291.                 if (ofs <= 0) { // int overflow
  292.                     ofs = maxOfs;
  293.                 }
  294.             }
  295.             if (ofs > maxOfs) {
  296.                 ofs = maxOfs;
  297.             }
  298.  
  299.             lastOfs += hint;
  300.             ofs += hint;
  301.         } else {
  302.             diff_t const maxOfs = hint + 1;
  303.             while (ofs < maxOfs && !compare(*(base + (hint - ofs)), key)) {
  304.                 lastOfs = ofs;
  305.                 ofs = (ofs << 1) + 1;
  306.  
  307.                 if (ofs <= 0) {
  308.                     ofs = maxOfs;
  309.                 }
  310.             }
  311.             if (ofs > maxOfs) {
  312.                 ofs = maxOfs;
  313.             }
  314.  
  315.             diff_t const tmp = lastOfs;
  316.             lastOfs = hint - ofs;
  317.             ofs = hint - tmp;
  318.         }
  319.         GFX_TIMSORT_ASSERT(-1 <= lastOfs);
  320.         GFX_TIMSORT_ASSERT(lastOfs < ofs);
  321.         GFX_TIMSORT_ASSERT(ofs <= len);
  322.  
  323.         return std::lower_bound(base + (lastOfs + 1), base + ofs, key, compare) - base;
  324.     }
  325.  
  326.     template <typename Iter>
  327.     diff_t gallopRight(ref_t key, Iter const base, diff_t const len, diff_t const hint, Compare compare) {
  328.         GFX_TIMSORT_ASSERT(len > 0);
  329.         GFX_TIMSORT_ASSERT(hint >= 0);
  330.         GFX_TIMSORT_ASSERT(hint < len);
  331.  
  332.         diff_t ofs = 1;
  333.         diff_t lastOfs = 0;
  334.  
  335.         if (compare(key, *(base + hint))) {
  336.             diff_t const maxOfs = hint + 1;
  337.             while (ofs < maxOfs && compare(key, *(base + (hint - ofs)))) {
  338.                 lastOfs = ofs;
  339.                 ofs = (ofs << 1) + 1;
  340.  
  341.                 if (ofs <= 0) {
  342.                     ofs = maxOfs;
  343.                 }
  344.             }
  345.             if (ofs > maxOfs) {
  346.                 ofs = maxOfs;
  347.             }
  348.  
  349.             diff_t const tmp = lastOfs;
  350.             lastOfs = hint - ofs;
  351.             ofs = hint - tmp;
  352.         } else {
  353.             diff_t const maxOfs = len - hint;
  354.             while (ofs < maxOfs && !compare(key, *(base + (hint + ofs)))) {
  355.                 lastOfs = ofs;
  356.                 ofs = (ofs << 1) + 1;
  357.  
  358.                 if (ofs <= 0) { // int overflow
  359.                     ofs = maxOfs;
  360.                 }
  361.             }
  362.             if (ofs > maxOfs) {
  363.                 ofs = maxOfs;
  364.             }
  365.  
  366.             lastOfs += hint;
  367.             ofs += hint;
  368.         }
  369.         GFX_TIMSORT_ASSERT(-1 <= lastOfs);
  370.         GFX_TIMSORT_ASSERT(lastOfs < ofs);
  371.         GFX_TIMSORT_ASSERT(ofs <= len);
  372.  
  373.         return std::upper_bound(base + (lastOfs + 1), base + ofs, key, compare) - base;
  374.     }
  375.  
  376.     static void rotateLeft(iter_t first, iter_t last)
  377.     {
  378.         value_t tmp = std::move(*first);
  379.         iter_t last_1 = std::move(first + 1, last, first);
  380.         *last_1 = std::move(tmp);
  381.     }
  382.  
  383.     static void rotateRight(iter_t first, iter_t last)
  384.     {
  385.         iter_t last_1 = last - 1;
  386.         value_t tmp = std::move(*last_1);
  387.         std::move_backward(first, last_1, last);
  388.         *first = std::move(tmp);
  389.     }
  390.  
  391.  
  392.     void mergeLo(iter_t const base1, diff_t len1, iter_t const base2, diff_t len2, Compare compare) {
  393.         GFX_TIMSORT_ASSERT(len1 > 0);
  394.         GFX_TIMSORT_ASSERT(len2 > 0);
  395.         GFX_TIMSORT_ASSERT(base1 + len1 == base2);
  396.  
  397.         if (len1 == 1) {
  398.             return rotateLeft(base1, base2 + len2);
  399.         }
  400.         if (len2 == 1) {
  401.             return rotateRight(base1, base2 + len2);
  402.         }
  403.  
  404.         copy_to_tmp(base1, len1);
  405.  
  406.         tmp_iter_t cursor1 = tmp_.begin();
  407.         iter_t cursor2 = base2;
  408.         iter_t dest = base1;
  409.  
  410.         *dest = std::move(*cursor2);
  411.         ++cursor2;
  412.         ++dest;
  413.         --len2;
  414.  
  415.         int minGallop(minGallop_);
  416.  
  417.         // outer:
  418.         while (true) {
  419.             diff_t count1 = 0;
  420.             diff_t count2 = 0;
  421.  
  422.             do {
  423.                 GFX_TIMSORT_ASSERT(len1 > 1);
  424.                 GFX_TIMSORT_ASSERT(len2 > 0);
  425.  
  426.                 if (compare(*cursor2, *cursor1)) {
  427.                     *dest = std::move(*cursor2);
  428.                     ++cursor2;
  429.                     ++dest;
  430.                     ++count2;
  431.                     count1 = 0;
  432.                     if (--len2 == 0) {
  433.                         goto epilogue;
  434.                     }
  435.                 } else {
  436.                     *dest = std::move(*cursor1);
  437.                     ++cursor1;
  438.                     ++dest;
  439.                     ++count1;
  440.                     count2 = 0;
  441.                     if (--len1 == 1) {
  442.                         goto epilogue;
  443.                     }
  444.                 }
  445.             } while ((count1 | count2) < minGallop);
  446.  
  447.             do {
  448.                 GFX_TIMSORT_ASSERT(len1 > 1);
  449.                 GFX_TIMSORT_ASSERT(len2 > 0);
  450.  
  451.                 count1 = gallopRight(*cursor2, cursor1, len1, 0, compare);
  452.                 if (count1 != 0) {
  453.                     std::move_backward(cursor1, cursor1 + count1, dest + count1);
  454.                     dest += count1;
  455.                     cursor1 += count1;
  456.                     len1 -= count1;
  457.  
  458.                     if (len1 <= 1) {
  459.                         goto epilogue;
  460.                     }
  461.                 }
  462.                 *dest = std::move(*cursor2);
  463.                 ++cursor2;
  464.                 ++dest;
  465.                 if (--len2 == 0) {
  466.                     goto epilogue;
  467.                 }
  468.  
  469.                 count2 = gallopLeft(*cursor1, cursor2, len2, 0, compare);
  470.                 if (count2 != 0) {
  471.                     std::move(cursor2, cursor2 + count2, dest);
  472.                     dest += count2;
  473.                     cursor2 += count2;
  474.                     len2 -= count2;
  475.                     if (len2 == 0) {
  476.                         goto epilogue;
  477.                     }
  478.                 }
  479.                 *dest = std::move(*cursor1);
  480.                 ++cursor1;
  481.                 ++dest;
  482.                 if (--len1 == 1) {
  483.                     goto epilogue;
  484.                 }
  485.  
  486.                 --minGallop;
  487.             } while ((count1 >= MIN_GALLOP) | (count2 >= MIN_GALLOP));
  488.  
  489.             if (minGallop < 0) {
  490.                 minGallop = 0;
  491.             }
  492.             minGallop += 2;
  493.         } // end of "outer" loop
  494.  
  495.         epilogue: // merge what is left from either cursor1 or cursor2
  496.  
  497.         minGallop_ = (std::min)(minGallop, 1);
  498.  
  499.         if (len1 == 1) {
  500.             GFX_TIMSORT_ASSERT(len2 > 0);
  501.             std::move(cursor2, cursor2 + len2, dest);
  502.             *(dest + len2) = std::move(*cursor1);
  503.         } else {
  504.             GFX_TIMSORT_ASSERT(len1 != 0 && "Comparison function violates its general contract");
  505.             GFX_TIMSORT_ASSERT(len2 == 0);
  506.             GFX_TIMSORT_ASSERT(len1 > 1);
  507.             std::move(cursor1, cursor1 + len1, dest);
  508.         }
  509.     }
  510.  
  511.     void mergeHi(iter_t const base1, diff_t len1, iter_t const base2, diff_t len2, Compare compare) {
  512.         GFX_TIMSORT_ASSERT(len1 > 0);
  513.         GFX_TIMSORT_ASSERT(len2 > 0);
  514.         GFX_TIMSORT_ASSERT(base1 + len1 == base2);
  515.  
  516.         if (len1 == 1) {
  517.             return rotateLeft(base1, base2 + len2);
  518.         }
  519.         if (len2 == 1) {
  520.             return rotateRight(base1, base2 + len2);
  521.         }
  522.  
  523.         copy_to_tmp(base2, len2);
  524.  
  525.         iter_t cursor1 = base1 + len1;
  526.         tmp_iter_t cursor2 = tmp_.begin() + (len2 - 1);
  527.         iter_t dest = base2 + (len2 - 1);
  528.  
  529.         *dest = std::move(*(--cursor1));
  530.         --dest;
  531.         --len1;
  532.  
  533.         int minGallop(minGallop_);
  534.  
  535.         // outer:
  536.         while (true) {
  537.             diff_t count1 = 0;
  538.             diff_t count2 = 0;
  539.  
  540.             // The next loop is a hot path of the algorithm, so we decrement
  541.             // eagerly the cursor so that it always points directly to the value
  542.             // to compare, but we have to implement some trickier logic to make
  543.             // sure that it points to the next value again by the end of said loop
  544.             --cursor1;
  545.  
  546.             do {
  547.                 GFX_TIMSORT_ASSERT(len1 > 0);
  548.                 GFX_TIMSORT_ASSERT(len2 > 1);
  549.  
  550.                 if (compare(*cursor2, *cursor1)) {
  551.                     *dest = std::move(*cursor1);
  552.                     --dest;
  553.                     ++count1;
  554.                     count2 = 0;
  555.                     if (--len1 == 0) {
  556.                         goto epilogue;
  557.                     }
  558.                     --cursor1;
  559.                 } else {
  560.                     *dest = std::move(*cursor2);
  561.                     --cursor2;
  562.                     --dest;
  563.                     ++count2;
  564.                     count1 = 0;
  565.                     if (--len2 == 1) {
  566.                         ++cursor1; // See comment before the loop
  567.                         goto epilogue;
  568.                     }
  569.                 }
  570.             } while ((count1 | count2) < minGallop);
  571.             ++cursor1; // See comment before the loop
  572.  
  573.             do {
  574.                 GFX_TIMSORT_ASSERT(len1 > 0);
  575.                 GFX_TIMSORT_ASSERT(len2 > 1);
  576.  
  577.                 count1 = len1 - gallopRight(*cursor2, base1, len1, len1 - 1, compare);
  578.                 if (count1 != 0) {
  579.                     dest -= count1;
  580.                     cursor1 -= count1;
  581.                     len1 -= count1;
  582.                     std::move_backward(cursor1, cursor1 + count1, dest + (1 + count1));
  583.  
  584.                     if (len1 == 0) {
  585.                         goto epilogue;
  586.                     }
  587.                 }
  588.                 *dest = std::move(*cursor2);
  589.                 --cursor2;
  590.                 --dest;
  591.                 if (--len2 == 1) {
  592.                     goto epilogue;
  593.                 }
  594.  
  595.                 count2 = len2 - gallopLeft(*(cursor1 - 1), tmp_.begin(), len2, len2 - 1, compare);
  596.                 if (count2 != 0) {
  597.                     dest -= count2;
  598.                     cursor2 -= count2;
  599.                     len2 -= count2;
  600.                     std::move(cursor2 + 1, cursor2 + (1 + count2), dest + 1);
  601.                     if (len2 <= 1) {
  602.                         goto epilogue;
  603.                     }
  604.                 }
  605.                 *dest = std::move(*(--cursor1));
  606.                 --dest;
  607.                 if (--len1 == 0) {
  608.                     goto epilogue;
  609.                 }
  610.  
  611.                 --minGallop;
  612.             } while ((count1 >= MIN_GALLOP) | (count2 >= MIN_GALLOP));
  613.  
  614.             if (minGallop < 0) {
  615.                 minGallop = 0;
  616.             }
  617.             minGallop += 2;
  618.         } // end of "outer" loop
  619.  
  620.         epilogue: // merge what is left from either cursor1 or cursor2
  621.  
  622.         minGallop_ = (std::min)(minGallop, 1);
  623.  
  624.         if (len2 == 1) {
  625.             GFX_TIMSORT_ASSERT(len1 > 0);
  626.             dest -= len1;
  627.             std::move_backward(cursor1 - len1, cursor1, dest + (1 + len1));
  628.             *dest = std::move(*cursor2);
  629.         } else {
  630.             GFX_TIMSORT_ASSERT(len2 != 0 && "Comparison function violates its general contract");
  631.             GFX_TIMSORT_ASSERT(len1 == 0);
  632.             GFX_TIMSORT_ASSERT(len2 > 1);
  633.             std::move(tmp_.begin(), tmp_.begin() + len2, dest - (len2 - 1));
  634.         }
  635.     }
  636.  
  637.     void copy_to_tmp(iter_t const begin, diff_t len) {
  638.         tmp_.assign(std::make_move_iterator(begin),
  639.                     std::make_move_iterator(begin + len));
  640.     }
  641.  
  642. public:
  643.  
  644.     static void sort(iter_t const lo, iter_t const hi, Compare compare) {
  645.         GFX_TIMSORT_ASSERT(lo <= hi);
  646.  
  647.         diff_t nRemaining = (hi - lo);
  648.         if (nRemaining < 2) {
  649.             return; // nothing to do
  650.         }
  651.  
  652.         if (nRemaining < MIN_MERGE) {
  653.             diff_t const initRunLen = countRunAndMakeAscending(lo, hi, compare);
  654.             GFX_TIMSORT_LOG("initRunLen: " << initRunLen);
  655.             binarySort(lo, hi, lo + initRunLen, compare);
  656.             return;
  657.         }
  658.  
  659.         TimSort ts;
  660.         diff_t const minRun = minRunLength(nRemaining);
  661.         iter_t cur = lo;
  662.         do {
  663.             diff_t runLen = countRunAndMakeAscending(cur, hi, compare);
  664.  
  665.             if (runLen < minRun) {
  666.                 diff_t const force = (std::min)(nRemaining, minRun);
  667.                 binarySort(cur, cur + force, cur + runLen, compare);
  668.                 runLen = force;
  669.             }
  670.  
  671.             ts.pushRun(cur, runLen);
  672.             ts.mergeCollapse(compare);
  673.  
  674.             cur += runLen;
  675.             nRemaining -= runLen;
  676.         } while (nRemaining != 0);
  677.  
  678.         GFX_TIMSORT_ASSERT(cur == hi);
  679.         ts.mergeForceCollapse(compare);
  680.         GFX_TIMSORT_ASSERT(ts.pending_.size() == 1);
  681.  
  682.         GFX_TIMSORT_LOG("size: " << (hi - lo) << " tmp_.size(): " << ts.tmp_.size()
  683.                                  << " pending_.size(): " << ts.pending_.size());
  684.     }
  685. };
  686.  
  687. } // namespace detail
  688.  
  689.  
  690. // ---------------------------------------
  691. // Public interface implementation
  692. // ---------------------------------------
  693.  
  694. /**
  695.  * Stably sorts a range with a comparison function and a projection function.
  696.  */
  697. template <typename RandomAccessIterator, typename Compare, typename Projection>
  698. void timsort(RandomAccessIterator const first, RandomAccessIterator const last,
  699.              Compare compare, Projection projection) {
  700.     typedef detail::projection_compare<Compare, Projection> compare_t;
  701.     compare_t comp(std::move(compare), std::move(projection));
  702.     detail::TimSort<RandomAccessIterator, compare_t>::sort(first, last, std::move(comp));
  703. }
  704.  
  705. /**
  706.  * Same as std::stable_sort(first, last, compare).
  707.  */
  708. template <typename RandomAccessIterator, typename Compare>
  709. void timsort(RandomAccessIterator const first, RandomAccessIterator const last, Compare compare) {
  710.     gfx::timsort(first, last, compare, detail::identity());
  711. }
  712.  
  713. /**
  714.  * Same as std::stable_sort(first, last).
  715.  */
  716. template <typename RandomAccessIterator>
  717. void timsort(RandomAccessIterator const first, RandomAccessIterator const last) {
  718.     typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
  719.     gfx::timsort(first, last, std::less<value_type>(), detail::identity());
  720. }
  721.  
  722. /**
  723.  * Stably sorts a range with a comparison function and a projection function.
  724.  */
  725. template <typename RandomAccessRange, typename Compare, typename Projection>
  726. void timsort(RandomAccessRange &range, Compare compare, Projection projection) {
  727.     gfx::timsort(std::begin(range), std::end(range), compare, projection);
  728. }
  729.  
  730. /**
  731.  * Same as std::stable_sort(std::begin(range), std::end(range), compare).
  732.  */
  733. template <typename RandomAccessRange, typename Compare>
  734. void timsort(RandomAccessRange &range, Compare compare) {
  735.     gfx::timsort(std::begin(range), std::end(range), compare);
  736. }
  737.  
  738. /**
  739.  * Same as std::stable_sort(std::begin(range), std::end(range)).
  740.  */
  741. template <typename RandomAccessRange>
  742. void timsort(RandomAccessRange &range) {
  743.     gfx::timsort(std::begin(range), std::end(range));
  744. }
  745.  
  746. } // namespace gfx
  747.  
  748. #undef GFX_TIMSORT_ENABLE_ASSERT
  749. #undef GFX_TIMSORT_ASSERT
  750. #undef GFX_TIMSORT_ENABLE_LOG
  751. #undef GFX_TIMSORT_LOG
  752.  
  753. #endif // GFX_TIMSORT_HPP
  754.  
  755. using namespace std;
  756.  
  757. int compare (const void * a, const void * b)
  758. {
  759.   return ( *(int*)a - *(int*)b );
  760. }
  761.  
  762. int* glue(int* a, int lenA, int* b, int lenB) {
  763.     int lenC = lenA + lenB;
  764.     int* c = new int[lenC]; // результирующий массив
  765.     int indx_a = 0;
  766.     int indx_b = 0;
  767.     int i = 0;
  768.  
  769.     for (; i < lenC; ++i) {
  770.         if (indx_a < lenA) {
  771.             if (indx_b < lenB) { // Оба массива содержат элементы
  772.                 c[i] = (a[indx_a] < b[indx_b]) ?
  773.                     a[indx_a++] :
  774.                     b[indx_b++];
  775.                 continue;
  776.             } // Элементы есть только в первом
  777.             while (indx_a < lenA)
  778.                 c[i++] = a[indx_a++];
  779.         }
  780.         else // Элементы есть только во втором
  781.             while (indx_b < lenB)
  782.                 c[i++] = b[indx_b++];
  783.         break;
  784.     }
  785.  
  786.     return c;
  787. }
  788.  
  789. void glueDelete(int*& arr, int*& a, int lenA, int*& b, int lenB) {
  790.     if (lenA == 0) { // если первый пустой
  791.         delete[] a; // высвобождаем от него память
  792.         arr = b; // результирующий будет вторым массивом
  793.         return;
  794.     }
  795.     if (lenB == 0) { // если второй пустой
  796.         delete[] b; // высвобождаем от него память
  797.         arr = a; // результирующий будет вторым массивом
  798.         return;
  799.     }
  800.  
  801.     int *copy = glue(a, lenA, b, lenB); // сливаем
  802.     delete[]a; // удаляемо ненужные массивы
  803.     delete[]b; // удаляемо ненужные массивы
  804.     arr = copy;  // изменяем указатель
  805. }
  806.  
  807. void insertionSort(int*& arr, int lo, int hi) {
  808.     for (int i = lo + 1; i <= hi; ++i)
  809.         for (int j = i; j > 0 && arr[j - 1] > arr[j]; --j)
  810.             swap(arr[j - 1], arr[j]);
  811. }
  812.  
  813. const int catchUp = 8;
  814.  
  815. /// works only if arr is pointer assigned by new keyword
  816. void newGenerationSort(int*& arr, int len) {
  817.     int localCatchUp = min(catchUp, len); // потому что мы не можем пытаться вставлять элемент за границами массива
  818.     insertionSort(arr, 0, localCatchUp - 1); // для начала сортируем первые localCatchUp элементов
  819.  
  820.     if (len <= localCatchUp) // на случай если это массив на n <= catchUp элементов
  821.         return; // а также это база рекурсии
  822.  
  823.     int* selection = new int[len << 1]; // то же что и new int[len * 2]
  824.     int left = len - 1; // индекс для хранения новых минимальных элементов
  825.     int right = len;  // индекс для хранения новых максимальных элементов
  826.  
  827.     selection[left--] = arr[0];
  828.     for (int i = 1; i < localCatchUp; ++i) {
  829.         selection[right++] = arr[i];
  830.     }
  831.  
  832.     int restLen = len >> 1;
  833.     int* restFirst = new int[restLen];
  834.     int* restSecond = new int[restLen];
  835.  
  836.     int restFirstLen = 0;
  837.     int restSecondLen = 0;
  838.  
  839.     for (int i = localCatchUp; i < len; ++i) {
  840.  
  841.         if (selection[right - localCatchUp] <= arr[i])
  842.         {
  843.             selection[right] = arr[i];
  844.  
  845.             for (int j = right; selection[j - 1] > selection[j]; --j)
  846.                 swap(selection[j - 1], selection[j]);
  847.  
  848.             ++right;
  849.             continue;
  850.         }
  851.  
  852.         if (selection[left + localCatchUp] >= arr[i])
  853.         {
  854.             selection[left] = arr[i];
  855.  
  856.             for (int j = left; selection[j] >= selection[j + 1]; ++j)
  857.                 swap(selection[j], selection[j + 1]);
  858.  
  859.             --left;
  860.             continue;
  861.         }
  862.  
  863.         if (i & 1) { // i - непарное
  864.             restFirst[restFirstLen++] = arr[i];
  865.         }
  866.         else {
  867.             restSecond[restSecondLen++] = arr[i];
  868.         }
  869.     }
  870.     delete[] arr;
  871.  
  872.     int selectionLen = right - left - 1; // просто длина нашей выборки
  873.     int* copy = glue(selection + left + 1, selectionLen, nullptr, 0); // копируем все элементы выборки в новый массив
  874.  
  875.     delete[] selection; // удаляем массив размером 2 * len элементов и
  876.     selection = copy; // вместо него используем ровно столько памяти, сколько нужно
  877.  
  878.     newGenerationSort(restFirst, restFirstLen);
  879.     newGenerationSort(restSecond, restSecondLen);
  880.  
  881.     int* part2;
  882.     int part2Len;
  883.     if (selectionLen < restFirstLen) {
  884.         glueDelete(selection, restFirst, restFirstLen, selection, selectionLen); // selection += restFirst
  885.         selectionLen += restFirstLen;
  886.  
  887.         part2 = restSecond;
  888.         part2Len = restSecondLen;
  889.     }
  890.     else {
  891.         glueDelete(part2, restFirst, restFirstLen, restSecond, restSecondLen); // part2 = restFirst + restSecond
  892.         part2Len = restFirstLen + restSecondLen;
  893.     }
  894.  
  895.     glueDelete(arr, selection, selectionLen, part2, part2Len);
  896. }
  897.  
  898. void printArr(int* arr, int len) {
  899.     for (int i = 0; i < len; ++i) {
  900.         cout << arr[i] << " ";
  901.     }
  902.     cout << endl;
  903. }
  904.  
  905. bool arraysEqual(int* arr1, int* arr2, int len) {
  906.     for (int i = 0; i < len; ++i) {
  907.         if (arr1[i] != arr2[i]) {
  908.             return false;
  909.         }
  910.     }
  911.     return true;
  912. }
  913.  
  914. int* createArray(int length, function<int ()> fGen) {
  915.     int* a1 = new int[length];
  916.     generate(a1, a1+length, fGen);
  917.     return a1;
  918. }
  919.  
  920. int* array_copy(int* arr, int length) {
  921.     int* a2 = new int[length];
  922.     for (int i = 0; i < length; i++) {
  923.         a2[i] = arr[i];
  924.     }
  925.  
  926.     return a2;
  927. }
  928.  
  929. double tester(int tests, int length, function<void (int *&, size_t)> fSort, function<int ()> fGen) {
  930.     int** arrays1 = new int* [tests];
  931.  
  932.     for (int t = 0; t < tests; ++t) { // просто заполнение массивов
  933.         int* arr1 = createArray(length, fGen);
  934.         arrays1[t] = arr1;
  935.     }
  936.  
  937.     auto t1 = chrono::high_resolution_clock::now();
  938.     for (int t = 0; t < tests; ++t) {
  939.         fSort(arrays1[t], length);
  940.     }
  941.  
  942.     chrono::duration<double, milli> diff = chrono::high_resolution_clock::now() - t1;
  943.  
  944.     return diff.count() / tests;
  945. }
  946.  
  947. int main() {
  948.     srand(time(nullptr));
  949.  
  950.     int length = 1000000;
  951.  
  952.     cout << "size: " << length << endl;
  953.  
  954.     int t = 100;
  955.     cout << "tests: " << t << endl;
  956.  
  957.     vector<pair<string, function<void (int *&, size_t)>>> sorts = {
  958.             make_pair("qsort", [](int *&arr, size_t len) { qsort (arr, len, sizeof(int), compare); }),
  959.             make_pair("std::sort", [](int *&arr, size_t len) { sort(arr, arr + len); }),
  960.             make_pair("timsort", [](int *&arr, size_t len) { gfx::timsort(arr, arr + len); }),
  961.             make_pair("newSort", [](int *&arr, size_t len) { newGenerationSort(arr, len); })};
  962.  
  963.     vector<pair<string, function<int ()>>> gens = {
  964.             make_pair("random", []() { return rand(); }),
  965.             make_pair("sorted", [n = 0] () mutable { return n++; }),
  966.             make_pair("part-sorted", [n = 0] () mutable { return rand() < RAND_MAX * 0.2 ? rand() : n++; }),
  967.             make_pair("chunk-sorted", [n = 0, length] () mutable { return n++ % (length / 4); }),
  968.             make_pair("rsorted", [n = 0] () mutable { return n--; }),
  969.             make_pair("part-rsorted", [n = 0] () mutable { return rand() < RAND_MAX * 0.2 ? rand() : n--; }),
  970.             make_pair("chunk-rsorted", [n = 0, length] () mutable { return n-- % (length / 4); })};
  971.  
  972.     cout << setw(12) << " ";
  973.  
  974.     for (auto s : sorts) {
  975.         cout << " " << setw(10) << s.first;
  976.     }
  977.  
  978.     cout << endl;
  979.  
  980.     for (auto gen : gens) {
  981.         cout << setw(12) << gen.first;
  982.         for (auto sort : sorts) {
  983.             cout << " " << setw(10) << tester(t, length, sort.second, gen.second);
  984.         }
  985.         cout << endl;
  986.     }
  987.  
  988.     return 0;
  989. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top