sort.h

Go to the documentation of this file.

/* *****************************************************************************
 * kblib is a general utility library for C++14 and C++17, intended to provide
 * performant high-level abstractions and more expressive ways to do simple
 * things.
 *
 * Copyright (c) 2021 killerbee
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 * ****************************************************************************/
 
#ifndef SORT_H
#define SORT_H
 
#include "algorithm.h"
#include "bits.h"
#include "fakestd.h"
#include "simple.h"
 
#include <bitset>
#include <numeric>
 
namespace kblib {
 
template <typename RandomAccessIt, typename Compare = std::less<>>
constexpr auto insertion_sort(
    const RandomAccessIt begin, const RandomAccessIt end,
    Compare&& compare
    = {}) noexcept(noexcept(swap(*begin, *begin)) and noexcept(compare(*begin,
                                                                       *begin)))
    -> void {
   // Trivial inputs are trivially already sorted.
   if (end - begin <= 1) {
      return;
   }
   for (auto pos = begin + 1; pos != end; ++pos) {
      // This search is linear, not binary, because insertion_sort is meant
      // to never be used for arrays large enough for binary search.
      auto index = kblib::find_if(begin, pos, [&compare, pos](const auto& a) {
         return compare(*pos, a);
      });
      kblib::rotate(index, pos, pos + 1);
   }
   return;
}
 
template <typename RandomAccessIt, typename RandomAccessIt2,
          typename Compare = std::less<>>
constexpr auto insertion_sort_copy(
    const RandomAccessIt begin, const RandomAccessIt end,
    const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end,
    Compare&& compare
    = {}) noexcept(noexcept(detail_algorithm::
                                shift_backward(d_begin, d_begin,
                                               d_end)) and noexcept(*d_begin
                                                                    = *begin))
    -> void {
   const auto dist = end - begin;
   assert(end - begin == d_end - d_begin);
   if (dist == 0) {
      return;
   } else if (dist == 1) {
      // ranges of 1 are trivial to sort
      *d_begin = *begin;
      return;
   } else if (dist == 2) {
      // Special case distance=2 to perform no swaps, and because the loop
      // for the general case assumes 3 or more elements.
      if (compare(*begin, *(begin + 1))) {
         *d_begin = *begin;
         *(d_begin + 1) = *(begin + 1);
         return;
      } else {
         *d_begin = *(begin + 1);
         *(d_begin + 1) = *begin;
      }
   } else {
      // This loop writes in reverse because shifting backwards can be done
      // in a forward pass, making it simpler than a forward shift, and is
      // sufficient for the algorithm, and reads in reverse to avoid worst-
      // case complexity for sorted inputs, given that it writes in reverse.
      auto read = std::prev(end);
      auto write = std::prev(d_end);
      // push first element to get the loop invariant
      *write = *read;
      do {
         --read, --write;
         // This search is linear, not binary, because insertion_sort_copy
         // is meant to never be used for arrays large enough for binary
         // search.
#if 1
         auto index = kblib::find_if(
             write + 1, d_end,
             [&compare, read](const auto& a) { return not compare(a, *read); });
#else
         auto index = kblib::find_if(write + 1, d_end,
                                     [&compare, read](const auto& a) {
                                        if (stable) {
                                           // find first element greater than
                                           // *read
                                           return compare(*read, a);
                                        } else {
                                           // find first element greater than
                                           // or equal to *read
                                           return ! compare(a, *read);
                                        }
                                     });
#endif
         detail_algorithm::shift_backward(write, write + 1, index);
         *(index - 1) = *read;
      } while (write != d_begin);
      return;
   }
}
 
template <typename RandomAccessIt, typename RandomAccessIt2,
          typename Compare = std::less<>>
constexpr auto adaptive_insertion_sort_copy(
    const RandomAccessIt begin, const RandomAccessIt end,
    const RandomAccessIt2 d_begin, const RandomAccessIt2 d_end,
    Compare&& compare
    = {}) noexcept(noexcept(detail_algorithm::
                                shift_backward(d_begin, d_begin,
                                               d_end)) and noexcept(*d_begin
                                                                    = *begin))
    -> void {
   const auto dist = end - begin;
   // For trivial inputs, don't bother doing anything
   if (dist < 3) {
      insertion_sort_copy(begin, end, d_begin, d_end,
                          std::forward<Compare>(compare));
   }
   // A very rudimentary way of estimating the sortedness of the input, by
   // counting the relative number of ascending and descending adjacent pairs
   // within the first sqrt(n) elements.
   const auto scan_end
       = begin
         + static_cast<std::ptrdiff_t>(std::sqrt(static_cast<float>(dist)));
   std::ptrdiff_t dir{};
   for (auto pos = begin; pos != scan_end - 1; ++pos) {
      if (compare(*pos, *(pos + 1))) {
         ++dir;
      } else if (compare(*(pos + 1), *pos)) {
         --dir;
      }
   }
   if (dir >= 0) {
      insertion_sort_copy(begin, end, d_begin, d_end,
                          std::forward<Compare>(compare));
   } else {
      // If the input is predominantly in reverse order, sort it in reverse
      // IMPORTANT: the reverse iterators go end, begin
      insertion_sort_copy(std::make_reverse_iterator(end),
                          std::make_reverse_iterator(begin), d_begin, d_end,
                          std::forward<Compare>(compare));
   }
}
 
template <typename T, typename = void>
struct is_radix_sortable : std::false_type {};
 
template <typename T>
struct is_radix_sortable<T, void_if_t<std::is_integral<T>::value>>
    : std::true_type {};
 
template <typename T>
struct is_radix_sortable<T, void_if_t<std::is_enum<T>::value>>
    : std::true_type {};
 
template <std::size_t B>
struct is_radix_sortable<std::bitset<B>, void> : std::true_type {};
 
template <typename T>
struct is_radix_sortable<
    T, void_if_t<is_linear_container_v<
                     T> and std::is_integral<typename T::value_type>::value>>
    : std::true_type {};
 
template <typename T>
constexpr bool is_radix_sortable_v = is_radix_sortable<T>::value;
 
#if __cpp_lib_byte
template <typename T>
constexpr bool is_byte_v
    = std::is_same<typename std::remove_cv<T>::type, std::byte>::value;
#else
template <typename T>
constexpr bool is_byte_v = false;
#endif
 
template <typename T>
KBLIB_NODISCARD constexpr auto byte_count(T) noexcept
    -> enable_if_t<std::is_integral<T>::value, std::size_t> {
   auto res
       = kblib::div(kblib::bits_of<T> + std::is_signed<T>::value, CHAR_BIT);
   return to_unsigned(res.quot + (res.rem != 0));
}
template <typename T>
KBLIB_NODISCARD constexpr auto byte_count(T) noexcept
    -> enable_if_t<std::is_enum<T>::value, std::size_t> {
   using U = typename std::underlying_type<T>::type;
   auto res
       = kblib::div(kblib::bits_of<U> + std::is_signed<U>::value, CHAR_BIT);
   return to_unsigned(res.quot + (res.rem != 0));
}
template <typename T>
KBLIB_NODISCARD constexpr auto byte_count(T*) noexcept -> std::size_t {
   return byte_count(std::uintptr_t{});
}
template <typename T>
KBLIB_NODISCARD constexpr auto byte_count(const std::unique_ptr<T>&) noexcept
    -> std::size_t {
   return byte_count(std::uintptr_t{});
}
template <typename T>
KBLIB_NODISCARD constexpr auto byte_count(const T& x) noexcept -> enable_if_t<
    is_linear_container_v<
        T> and (std::is_integral<typename T::value_type>::value or is_byte_v<T>)
        and sizeof(typename T::value_type) == 1,
    std::size_t> {
   return fakestd::size(x);
}
template <typename T>
constexpr auto byte_count(const T& x) noexcept -> enable_if_t<
    is_linear_container_v<T> and std::is_integral<typename T::value_type>::value
        and (sizeof(typename T::value_type) > 1),
    std::size_t> {
   using value_type = typename T::value_type;
   return fakestd::size(x) * byte_count(value_type{});
}
 
// Can be used to detect unsupported types with overload resolution.
 
// cert-dcl50-cpp: An exception to the rule for defining as deleted is not
// implemented by clang-tidy. This definition does not pose a security risk.
constexpr auto byte_count(...) -> void = delete;
 
template <typename T>
KBLIB_NODISCARD constexpr auto get_byte_index(T x, std::size_t idx) noexcept
    -> enable_if_t<std::is_integral<T>::value, unsigned char> {
   return static_cast<unsigned char>(x >> (idx * CHAR_BIT));
}
template <typename T>
KBLIB_NODISCARD constexpr auto get_byte_index(const T& x,
                                              std::size_t idx) noexcept
    -> enable_if_t<std::is_enum<T>::value, unsigned char> {
   return static_cast<unsigned char>(etoi(x) >> (idx * CHAR_BIT));
}
// Note that the ordering created by casting to std::uintptr_t may not agree
// with the ordering imposed by std::less<T*>.
template <typename T>
KBLIB_NODISCARD auto get_byte_index(T* x, std::size_t idx) noexcept
    -> unsigned char {
   return get_byte_index(byte_cast<std::uintptr_t>(x), idx);
}
template <typename T>
KBLIB_NODISCARD auto get_byte_index(const std::unique_ptr<T>& x,
                                    std::size_t idx) noexcept -> unsigned char {
   return get_byte_index(byte_cast<std::uintptr_t>(x.get()), idx);
}
template <typename T>
KBLIB_NODISCARD constexpr auto
get_byte_index(const T& x, std::size_t idx) noexcept -> enable_if_t<
    is_linear_container_v<
        T> and (std::is_integral<typename T::value_type>::value or is_byte_v<T>)
        and sizeof(typename T::value_type) == 1,
    unsigned char> {
   return static_cast<unsigned char>(x[idx]);
}
template <typename T>
KBLIB_NODISCARD constexpr auto get_byte_index(const T& x,
                                              std::size_t idx) noexcept
    -> enable_if_t<is_linear_container_v<
                       T> and std::is_integral<typename T::value_type>::value
                       and (sizeof(typename T::value_type) > 1),
                   unsigned char> {
   using value_type = typename T::value_type;
   auto bytes_per = byte_count(value_type{});
   return static_cast<unsigned char>(to_unsigned(x[idx / bytes_per])
                                     >> (idx % bytes_per * CHAR_BIT));
}
template <typename T>
KBLIB_NODISCARD constexpr auto get_byte_index(const T& x,
                                              std::size_t idx) noexcept
    -> enable_if_t<is_linear_container_v<
                       T> and std::is_enum<typename T::value_type>::value,
                   unsigned char> {
   using U = typename std::underlying_type<typename T::U>::type;
   auto bytes_per = byte_count(U{});
   return static_cast<unsigned char>(to_unsigned(etoi(x[idx / bytes_per]))
                                     >> (idx % bytes_per * CHAR_BIT));
}
 
template <typename T>
struct is_trivial_transformation
    : bool_constant<std::is_member_object_pointer<T>::value> {};
 
template <>
struct is_trivial_transformation<identity> : std::true_type {};
 
namespace detail_sort {
 
   template <typename RandomAccessIt, typename Compare>
   constexpr auto sort(RandomAccessIt, const RandomAccessIt, Compare) -> void {}
   template <typename RandomAccessIt, typename Compare>
   constexpr auto stable_sort(RandomAccessIt, const RandomAccessIt, Compare)
       -> void {}
 
   template <typename RandomAccessIt, typename Compare, std::size_t small_size>
   constexpr auto merge_sort(RandomAccessIt begin, const RandomAccessIt end,
                             Compare cmp) -> void {
      if (end - begin <= small_size) {
         insertion_sort(begin, end, cmp);
         return;
      } else {
         auto middle = begin + (end - begin) / 2;
         merge_sort(begin, middle, cmp);
         merge_sort(middle, end, cmp);
         std::inplace_merge(begin, middle, end, cmp);
         return;
      }
   }
 
   template <typename RandomAccessIt, typename Compare, std::size_t small_size>
   constexpr auto heap_sort(RandomAccessIt begin, const RandomAccessIt end,
                            Compare cmp) -> void {
      std::make_heap(begin, end, cmp);
      while (begin != end) {
         std::pop_heap(begin, end--, cmp);
      }
      return;
   }
 
   enum class sort_direction { ascending, descending };
 
   template <sort_direction dir, typename RandomAccessIt, typename Projection>
   constexpr auto radix_sort_i(RandomAccessIt begin, const RandomAccessIt end,
                               Projection proj) -> void {
      using E = decay_t<decltype(proj(*begin))>;
      const auto max_bytes = byte_count(E{});
      for (const auto byte : range(max_bytes)) {
         for (auto it = begin; it != end; ++it) {
         }
      }
   }
   template <sort_direction dir, typename RandomAccessIt, typename Projection>
   constexpr auto radix_sort_s(RandomAccessIt begin, const RandomAccessIt end,
                               Projection proj) -> void {
      if (begin != end) {
         const auto max_bytes = kblib::accumulate(
             begin, end, std::size_t{}, [&](auto m, const auto& el) {
                return max(m, byte_count(proj(*el)));
             });
      }
      const auto max_bytes = [&] {
         std::size_t max_bytes{};
         for (const auto v : indirect(begin, end)) {
            max_bytes = max(max_bytes, byte_count(v));
         }
         return max_bytes;
      }();
   }
 
   template <std::size_t size>
   constexpr auto make_array_for(std::false_type)
       -> kblib::containing_ptr<std::array<std::size_t, size>> {
      return {};
   }
   template <std::size_t size>
   auto make_array_for(std::true_type)
       -> kblib::heap_value<std::array<std::size_t, size + 1>> {
      return {in_place_agg};
   }
 
   template <sort_direction dir, typename RandomAccessIt1,
             typename RandomAccessIt2, typename Projection>
   constexpr auto counting_sort(RandomAccessIt1 begin,
                                const RandomAccessIt1 end,
                                RandomAccessIt2 d_begin, Projection proj)
       -> void {
      using E = decay_t<decltype(proj(*begin))>;
      constexpr auto size = std::numeric_limits<std::make_unsigned_t<E>>::max();
      auto count = make_array_for<size>(bool_constant<(size > 256)>{});
 
      for (auto cur = begin; cur != end; ++cur) {
         ++count->at(proj(*cur));
      }
      kblib::transform_exclusive_scan(begin(*count), end(*count), begin(*count),
                                      std::size_t{}, std::plus<>{}, proj);
 
      for (auto cur = end; cur != begin; --cur) {
         auto el = std::prev(cur);
         d_begin[--count->at(proj(*el))] = *el;
      }
 
      return;
   }
 
   template <typename RandomAccessIt, typename UnaryOperation,
             typename BinaryPredicate, typename SortKey,
             std::size_t small_size = 8,
             bool = is_trivial_transformation<UnaryOperation>::value,
             bool = std::is_fundamental<SortKey>::value,
             bool = is_radix_sortable_v<SortKey>,
             bool = std::is_integral<SortKey>::value>
   struct sort_transform_impl {
      static constexpr auto inplace(RandomAccessIt begin,
                                    const RandomAccessIt end,
                                    UnaryOperation&& transform,
                                    BinaryPredicate&& compare) -> void {
         auto comp
             = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
                  return kblib::invoke(compare, kblib::invoke(transform, *a),
                                       kblib::invoke(transform, *b));
               };
         if (end - begin < small_size) {
            insertion_sort(begin, end, comp);
            return;
         } else {
         }
      }
 
      static constexpr auto scratch(RandomAccessIt begin,
                                    const RandomAccessIt end,
                                    UnaryOperation&& transform,
                                    BinaryPredicate&& compare) -> void {
         auto comp
             = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
                  return kblib::invoke(compare, kblib::invoke(transform, *a),
                                       kblib::invoke(transform, *b));
               };
         if (end - begin < small_size) {
            insertion_sort(begin, end, comp);
            return;
         } else {
         }
      }
 
      template <typename RandomAccessIt2>
      static constexpr auto copy(RandomAccessIt begin, const RandomAccessIt end,
                                 RandomAccessIt2 d_begin, RandomAccessIt2 d_end,
                                 UnaryOperation&& transform,
                                 BinaryPredicate&& compare) -> void {
         auto comp
             = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
                  return kblib::invoke(compare, kblib::invoke(transform, *a),
                                       kblib::invoke(transform, *b));
               };
         if (end - begin < small_size) {
            insertion_sort_copy(begin, end, d_begin, d_end, comp);
            return;
         } else {
         }
      }
   };
 
#if 1
   template <typename RandomAccessIt, typename UnaryOperation,
             typename BinaryPredicate, typename SortKey, std::size_t small_size>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation, BinaryPredicate,
                              SortKey, small_size, true, false, false, false> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED BinaryPredicate&& compare)
          -> void {
         auto comp
             = [&compare, &transform](RandomAccessIt a, RandomAccessIt b) {
                  return kblib::invoke(compare, kblib::invoke(transform, *a),
                                       kblib::invoke(transform, *b));
               };
      }
   };
#endif
 
   template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
             typename SortKey, std::size_t small_size>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation, std::less<LessT>,
                              SortKey, small_size, true, true, false, false> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED std::less<LessT>&& compare)
          -> void {
      }
   };
   template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
             typename SortKey, std::size_t small_size>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation,
                              std::greater<LessT>, SortKey, small_size, true,
                              true, false, false> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED std::greater<LessT>&& compare)
          -> void {
      }
   };
 
   template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
             typename SortKey, std::size_t small_size>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation, std::less<LessT>,
                              SortKey, small_size, true, true, true, true> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED std::less<LessT>&& compare)
          -> void {
      }
   };
   template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
             typename SortKey, std::size_t small_size>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation,
                              std::greater<LessT>, SortKey, small_size, true,
                              true, true, true> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED std::greater<LessT>&& compare)
          -> void {
      }
   };
 
#if 1 // Do string radix sorting
   template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
             typename SortKey, std::size_t small_size, bool M>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation, std::less<LessT>,
                              SortKey, small_size, M, false, true, false> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED std::less<LessT>&& compare)
          -> void {
      }
   };
   template <typename RandomAccessIt, typename UnaryOperation, typename LessT,
             typename SortKey, std::size_t small_size, bool M>
   struct sort_transform_impl<RandomAccessIt, UnaryOperation,
                              std::greater<LessT>, SortKey, small_size, M,
                              false, true, false> {
      static constexpr auto inplace(KBLIB_UNUSED RandomAccessIt begin,
                                    KBLIB_UNUSED const RandomAccessIt end,
                                    KBLIB_UNUSED UnaryOperation&& transform,
                                    KBLIB_UNUSED std::greater<LessT>&& compare)
          -> void {
      }
   };
#endif
} // namespace detail_sort
 
template <typename RandomAccessIt, typename UnaryOperation,
          typename BinaryPredicate>
constexpr auto sort_transform(RandomAccessIt begin, RandomAccessIt end,
                              UnaryOperation&& transform,
                              BinaryPredicate&& compare) -> void {
   detail_sort::sort_transform_impl<
       RandomAccessIt, UnaryOperation, BinaryPredicate,
       decltype(kblib::invoke(transform, *begin))>::
       inplace(begin, end, std::forward<UnaryOperation>(transform),
               std::forward<BinaryPredicate>(compare));
}
 
template <typename RandomAccessIt, typename UnaryOperation>
constexpr auto sort_transform(RandomAccessIt begin, RandomAccessIt end,
                              UnaryOperation&& transform) -> void {
   detail_sort::sort_transform_impl<
       RandomAccessIt, UnaryOperation, std::less<>,
       decltype(kblib::invoke(transform,
                              *begin))>::inplace(begin, end,
                                                 std::forward<UnaryOperation>(
                                                     transform),
                                                 std::less<>{});
}
 
template <typename RandomAccessIt, typename BinaryPredicate>
constexpr auto sort(RandomAccessIt begin, RandomAccessIt end,
                    BinaryPredicate&& compare) -> void {
   detail_sort::sort_transform_impl<
       RandomAccessIt, identity, BinaryPredicate,
       decltype(kblib::invoke(transform,
                              *begin))>::inplace(begin, end, identity{},
                                                 std::forward<BinaryPredicate>(
                                                     compare));
}
 
template <typename RandomAccessIt>
constexpr auto sort(RandomAccessIt begin, RandomAccessIt end) -> void {
   detail_sort::sort_transform_impl<
       RandomAccessIt, identity, std::less<>,
       decltype(kblib::invoke(transform, *begin))>::inplace(begin, end,
                                                            identity{},
                                                            std::less<>{});
}
 
} // namespace kblib
 
#endif // SORT_H