Branch data     Line data    Source code

       1                 :            : #pragma once
       2                 :            : 
       3                 :            : 
       4                 :            : #include <mutable/util/macro.hpp>
       5                 :            : #include <algorithm>
       6                 :            : #include <cstddef>
       7                 :            : #include <type_traits>
       8                 :            : #include <utility>
       9                 :            : 
      10                 :            : 
      11                 :            : namespace m {
      12                 :            : 
      13                 :            : 
      14                 :            : /** Verifies that `mid` splits the range `begin` to `end` (exclusive) into two partitions.
      15                 :            :  *
      16                 :            :  * @return  `true` iff `mid` splits the range `begin` to `end` (exclusive) into two partitions.
      17                 :            :  */
      18                 :            : template<typename It>
      19                 :       4491 : bool verify_partition(It begin, It mid, It end)
      20                 :            : {
      21                 :            :     using T = std::remove_reference_t<decltype(*begin)>;
      22                 :       4491 :     T max_lo{std::numeric_limits<T>::lowest()};
      23                 :       4491 :     T min_hi{std::numeric_limits<T>::max()};
      24                 :       4491 :     M_insist(max_lo < min_hi);
      25         [ +  + ]:      73851 :     for (It p = begin; p != mid; ++p)
      26                 :      69360 :         max_lo = std::max(max_lo, *p);
      27         [ +  + ]:      66475 :     for (It p = mid; p != end; ++p)
      28                 :      61984 :         min_hi = std::min(min_hi, *p);
      29                 :       4491 :     return max_lo <= min_hi;
      30                 :            : }
      31                 :            : 
      32                 :            : /** Partitions the range `begin` to `end` (exclusive) into two partitions using `pivot`.
      33                 :            :  *
      34                 :            :  * @return  pointer to the beginning of the second partition
      35                 :            :  */
      36                 :            : struct partition_predicated_naive
      37                 :            : {
      38                 :            :     template<typename T, typename It>
      39                 :       4483 :     It operator()(const T pivot, It begin, It end)
      40                 :            :     {
      41                 :            : #ifndef NDEBUG
      42                 :       4483 :         const It the_end = end;
      43                 :            : #endif
      44                 :            :         using std::prev;
      45         [ +  + ]:     108969 :         while (begin < end) {
      46                 :     104486 :             const T left = *begin;
      47                 :     104486 :             const T right = *prev(end);
      48                 :     104486 :             *begin = right;
      49                 :     104486 :             *prev(end) = left;
      50                 :     104486 :             const ptrdiff_t adv_lo = right <= pivot;
      51                 :     104486 :             const ptrdiff_t adv_hi = left >= pivot;
      52                 :     104486 :             begin += adv_lo;
      53                 :     104486 :             end   -= adv_hi;
      54                 :            :         }
      55                 :            : #ifndef NDEBUG
      56         [ +  + ]:       4483 :         M_insist(begin == the_end or *begin >= pivot);
      57                 :            : #endif
      58                 :       4483 :         return begin;
      59                 :            :     }
      60                 :            : };
      61                 :            : 
      62                 :            : template<typename Partitioning, typename It>
      63                 :       2982 : void qsort(It begin, It end, Partitioning p)
      64                 :            : {
      65                 :            :     using std::swap;
      66                 :            :     using std::min, std::max;
      67                 :            :     using std::distance;
      68                 :            :     using std::prev, std::next;
      69                 :       2982 :     M_insist(begin <= end);
      70                 :            : 
      71         [ +  + ]:       7447 :     while (distance(begin, end) > 2) {
      72                 :            :         /* Compute median of three. */
      73                 :       4465 :         auto pm = begin + (end - begin) / 2;
      74                 :       4465 :         bool left_le_mid   = *begin <= *pm;
      75                 :       4465 :         bool left_le_right = *begin <= *prev(end);
      76                 :       4465 :         bool mid_le_right  = *pm <= *prev(end);
      77         [ +  + ]:       4465 :         if (left_le_mid) {
      78         [ +  + ]:       2289 :             if (left_le_right) {
      79         [ +  + ]:       1549 :                 if (mid_le_right)
      80                 :        806 :                     swap(*begin, *pm);
      81                 :            :                 else
      82                 :        743 :                     swap(*begin, *prev(end));
      83                 :       1549 :             } else {
      84                 :            :                 /* nothing to be done */
      85                 :            :             }
      86                 :       2289 :         } else {
      87         [ +  + ]:       2176 :             if (mid_le_right) {
      88         [ +  + ]:       1477 :                 if (left_le_right) {
      89                 :            :                     /* nothing to be done */
      90                 :        743 :                 } else {
      91                 :        734 :                     swap(*begin, *prev(end));
      92                 :            :                 }
      93                 :       1477 :             } else {
      94                 :        699 :                 swap(*begin, *pm);
      95                 :            :             }
      96                 :            :         }
      97                 :            : 
      98                 :       4465 :         It mid = p(*begin, next(begin), end);
      99                 :       4465 :         M_insist(mid <= end);
     100                 :       4465 :         M_insist(mid >= next(begin));
     101                 :       4465 :         M_insist(verify_partition(next(begin), mid, end));
     102                 :       4465 :         swap(*begin, *prev(mid));
     103                 :            : 
     104         [ +  + ]:       4465 :         if (distance(mid, end) >= 2) qsort(mid, end, p); // recurse to the right
     105                 :       4465 :         M_insist(std::is_sorted(mid, end));
     106                 :       4465 :         end = prev(mid);
     107                 :            :     }
     108                 :            : 
     109         [ +  + ]:       2982 :     if (distance(begin, end) == 2) {
     110         [ +  + ]:       1473 :         if (*begin > *prev(end))
     111                 :        718 :             swap(*begin, *prev(end));
     112                 :       1473 :     }
     113                 :       2982 : };
     114                 :            : 
     115                 :            : }