v1/__algorithm/radix_sort.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___ALGORITHM_RADIX_SORT_H
0011 #define _LIBCPP___ALGORITHM_RADIX_SORT_H
0012
0013 // This is an implementation of classic LSD radix sort algorithm, running in linear time and using `O(max(N, M))`
0014 // additional memory, where `N` is size of an input range, `M` - maximum value of
0015 // a radix of the sorted integer type. Type of the radix and its maximum value are determined at compile time
0016 // based on type returned by function `__radix`. The default radix is uint8.
0017
0018 // The algorithm is equivalent to several consecutive calls of counting sort for each
0019 // radix of the sorted numbers from low to high byte.
0020 // The algorithm uses a temporary buffer of size equal to size of the input range. Each `i`-th pass
0021 // of the algorithm sorts values by `i`-th radix and moves values to the temporary buffer (for each even `i`, counted
0022 // from zero), or moves them back to the initial range (for each odd `i`). If there is only one radix in sorted integers
0023 // (e.g. int8), the sorted values are placed to the buffer, and then moved back to the initial range.
0024
0025 // The implementation also has several optimizations:
0026 // - the counters for the counting sort are calculated in one pass for all radices;
0027 // - if all values of a radix are the same, we do not sort that radix, and just move items to the buffer;
0028 // - if two consecutive radices satisfies condition above, we do nothing for these two radices.
0029
0030 #include <__algorithm/for_each.h>
0031 #include <__algorithm/move.h>
0032 #include <__bit/bit_log2.h>
0033 #include <__bit/countl.h>
0034 #include <__config>
0035 #include <__functional/identity.h>
0036 #include <__iterator/distance.h>
0037 #include <__iterator/iterator_traits.h>
0038 #include <__iterator/move_iterator.h>
0039 #include <__iterator/next.h>
0040 #include <__iterator/reverse_iterator.h>
0041 #include <__numeric/partial_sum.h>
0042 #include <__type_traits/decay.h>
0043 #include <__type_traits/enable_if.h>
0044 #include <__type_traits/invoke.h>
0045 #include <__type_traits/is_assignable.h>
0046 #include <__type_traits/is_integral.h>
0047 #include <__type_traits/is_unsigned.h>
0048 #include <__type_traits/make_unsigned.h>
0049 #include <__utility/forward.h>
0050 #include <__utility/integer_sequence.h>
0051 #include <__utility/move.h>
0052 #include <__utility/pair.h>
0053 #include <climits>
0054 #include <cstdint>
0055 #include <initializer_list>
0056 #include <limits>
0057
0058 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0059 #  pragma GCC system_header
0060 #endif
0061
0062 _LIBCPP_PUSH_MACROS
0063 #include <__undef_macros>
0064
0065 _LIBCPP_BEGIN_NAMESPACE_STD
0066
0067 #if _LIBCPP_STD_VER >= 14
0068
0069 template <class _InputIterator, class _OutputIterator>
0070 _LIBCPP_HIDE_FROM_ABI pair<_OutputIterator, __iter_value_type<_InputIterator>>
0071 __partial_sum_max(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {
0072   if (__first == __last)
0073     return {__result, 0};
0074
0075   auto __max                              = *__first;
0076   __iter_value_type<_InputIterator> __sum = *__first;
0077   *__result                               = __sum;
0078
0079   while (++__first != __last) {
0080     if (__max < *__first) {
0081       __max = *__first;
0082     }
0083     __sum       = std::move(__sum) + *__first;
0084     *++__result = __sum;
0085   }
0086   return {++__result, __max};
0087 }
0088
0089 template <class _Value, class _Map, class _Radix>
0090 struct __radix_sort_traits {
0091   using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>;
0092   static_assert(is_unsigned<__image_type>::value);
0093
0094   using __radix_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Radix, __image_type>>;
0095   static_assert(is_integral<__radix_type>::value);
0096
0097   static constexpr auto __radix_value_range = numeric_limits<__radix_type>::max() + 1;
0098   static constexpr auto __radix_size        = std::__bit_log2<uint64_t>(__radix_value_range);
0099   static constexpr auto __radix_count       = sizeof(__image_type) * CHAR_BIT / __radix_size;
0100 };
0101
0102 template <class _Value, class _Map>
0103 struct __counting_sort_traits {
0104   using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>;
0105   static_assert(is_unsigned<__image_type>::value);
0106
0107   static constexpr const auto __value_range = numeric_limits<__image_type>::max() + 1;
0108   static constexpr auto __radix_size        = std::__bit_log2<uint64_t>(__value_range);
0109 };
0110
0111 template <class _Radix, class _Integer>
0112 _LIBCPP_HIDE_FROM_ABI auto __nth_radix(size_t __radix_number, _Radix __radix, _Integer __n) {
0113   static_assert(is_unsigned<_Integer>::value);
0114   using __traits = __counting_sort_traits<_Integer, _Radix>;
0115
0116   return __radix(static_cast<_Integer>(__n >> __traits::__radix_size * __radix_number));
0117 }
0118
0119 template <class _ForwardIterator, class _Map, class _RandomAccessIterator>
0120 _LIBCPP_HIDE_FROM_ABI void
0121 __collect(_ForwardIterator __first, _ForwardIterator __last, _Map __map, _RandomAccessIterator __counters) {
0122   using __value_type = __iter_value_type<_ForwardIterator>;
0123   using __traits     = __counting_sort_traits<__value_type, _Map>;
0124
0125   std::for_each(__first, __last, [&__counters, &__map](const auto& __preimage) { ++__counters[__map(__preimage)]; });
0126
0127   const auto __counters_end = __counters + __traits::__value_range;
0128   std::partial_sum(__counters, __counters_end, __counters);
0129 }
0130
0131 template <class _ForwardIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>
0132 _LIBCPP_HIDE_FROM_ABI void
0133 __dispose(_ForwardIterator __first,
0134           _ForwardIterator __last,
0135           _RandomAccessIterator1 __result,
0136           _Map __map,
0137           _RandomAccessIterator2 __counters) {
0138   std::for_each(__first, __last, [&__result, &__counters, &__map](auto&& __preimage) {
0139     auto __index      = __counters[__map(__preimage)]++;
0140     __result[__index] = std::move(__preimage);
0141   });
0142 }
0143
0144 template <class _ForwardIterator,
0145           class _Map,
0146           class _Radix,
0147           class _RandomAccessIterator1,
0148           class _RandomAccessIterator2,
0149           size_t... _Radices>
0150 _LIBCPP_HIDE_FROM_ABI bool __collect_impl(
0151     _ForwardIterator __first,
0152     _ForwardIterator __last,
0153     _Map __map,
0154     _Radix __radix,
0155     _RandomAccessIterator1 __counters,
0156     _RandomAccessIterator2 __maximums,
0157     index_sequence<_Radices...>) {
0158   using __value_type                 = __iter_value_type<_ForwardIterator>;
0159   constexpr auto __radix_value_range = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_value_range;
0160
0161   auto __previous  = numeric_limits<__invoke_result_t<_Map, __value_type>>::min();
0162   auto __is_sorted = true;
0163   std::for_each(__first, __last, [&__counters, &__map, &__radix, &__previous, &__is_sorted](const auto& __value) {
0164     auto __current = __map(__value);
0165     __is_sorted &= (__current >= __previous);
0166     __previous = __current;
0167
0168     (++__counters[_Radices][std::__nth_radix(_Radices, __radix, __current)], ...);
0169   });
0170
0171   ((__maximums[_Radices] =
0172         std::__partial_sum_max(__counters[_Radices], __counters[_Radices] + __radix_value_range, __counters[_Radices])
0173             .second),
0174    ...);
0175
0176   return __is_sorted;
0177 }
0178
0179 template <class _ForwardIterator, class _Map, class _Radix, class _RandomAccessIterator1, class _RandomAccessIterator2>
0180 _LIBCPP_HIDE_FROM_ABI bool
0181 __collect(_ForwardIterator __first,
0182           _ForwardIterator __last,
0183           _Map __map,
0184           _Radix __radix,
0185           _RandomAccessIterator1 __counters,
0186           _RandomAccessIterator2 __maximums) {
0187   using __value_type           = __iter_value_type<_ForwardIterator>;
0188   constexpr auto __radix_count = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_count;
0189   return std::__collect_impl(
0190       __first, __last, __map, __radix, __counters, __maximums, make_index_sequence<__radix_count>());
0191 }
0192
0193 template <class _BidirectionalIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>
0194 _LIBCPP_HIDE_FROM_ABI void __dispose_backward(
0195     _BidirectionalIterator __first,
0196     _BidirectionalIterator __last,
0197     _RandomAccessIterator1 __result,
0198     _Map __map,
0199     _RandomAccessIterator2 __counters) {
0200   std::for_each(std::make_reverse_iterator(__last),
0201                 std::make_reverse_iterator(__first),
0202                 [&__result, &__counters, &__map](auto&& __preimage) {
0203                   auto __index      = --__counters[__map(__preimage)];
0204                   __result[__index] = std::move(__preimage);
0205                 });
0206 }
0207
0208 template <class _ForwardIterator, class _RandomAccessIterator, class _Map>
0209 _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator
0210 __counting_sort_impl(_ForwardIterator __first, _ForwardIterator __last, _RandomAccessIterator __result, _Map __map) {
0211   using __value_type = __iter_value_type<_ForwardIterator>;
0212   using __traits     = __counting_sort_traits<__value_type, _Map>;
0213
0214   __iter_diff_t<_RandomAccessIterator> __counters[__traits::__value_range + 1] = {0};
0215
0216   std::__collect(__first, __last, __map, std::next(std::begin(__counters)));
0217   std::__dispose(__first, __last, __result, __map, std::begin(__counters));
0218
0219   return __result + __counters[__traits::__value_range];
0220 }
0221
0222 template <class _RandomAccessIterator1,
0223           class _RandomAccessIterator2,
0224           class _Map,
0225           class _Radix,
0226           enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count == 1,
0227                        int> = 0>
0228 _LIBCPP_HIDE_FROM_ABI void __radix_sort_impl(
0229     _RandomAccessIterator1 __first,
0230     _RandomAccessIterator1 __last,
0231     _RandomAccessIterator2 __buffer,
0232     _Map __map,
0233     _Radix __radix) {
0234   auto __buffer_end = std::__counting_sort_impl(__first, __last, __buffer, [&__map, &__radix](const auto& __value) {
0235     return __radix(__map(__value));
0236   });
0237
0238   std::move(__buffer, __buffer_end, __first);
0239 }
0240
0241 template <
0242     class _RandomAccessIterator1,
0243     class _RandomAccessIterator2,
0244     class _Map,
0245     class _Radix,
0246     enable_if_t< __radix_sort_traits<__iter_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count % 2 == 0,
0247                  int> = 0 >
0248 _LIBCPP_HIDE_FROM_ABI void __radix_sort_impl(
0249     _RandomAccessIterator1 __first,
0250     _RandomAccessIterator1 __last,
0251     _RandomAccessIterator2 __buffer_begin,
0252     _Map __map,
0253     _Radix __radix) {
0254   using __value_type = __iter_value_type<_RandomAccessIterator1>;
0255   using __traits     = __radix_sort_traits<__value_type, _Map, _Radix>;
0256
0257   __iter_diff_t<_RandomAccessIterator1> __counters[__traits::__radix_count][__traits::__radix_value_range] = {{0}};
0258   __iter_diff_t<_RandomAccessIterator1> __maximums[__traits::__radix_count]                                = {0};
0259   const auto __is_sorted = std::__collect(__first, __last, __map, __radix, __counters, __maximums);
0260   if (!__is_sorted) {
0261     const auto __range_size = std::distance(__first, __last);
0262     auto __buffer_end       = __buffer_begin + __range_size;
0263     for (size_t __radix_number = 0; __radix_number < __traits::__radix_count; __radix_number += 2) {
0264       const auto __n0th_is_single = __maximums[__radix_number] == __range_size;
0265       const auto __n1th_is_single = __maximums[__radix_number + 1] == __range_size;
0266
0267       if (__n0th_is_single && __n1th_is_single) {
0268         continue;
0269       }
0270
0271       if (__n0th_is_single) {
0272         std::move(__first, __last, __buffer_begin);
0273       } else {
0274         auto __n0th = [__radix_number, &__map, &__radix](const auto& __v) {
0275           return std::__nth_radix(__radix_number, __radix, __map(__v));
0276         };
0277         std::__dispose_backward(__first, __last, __buffer_begin, __n0th, __counters[__radix_number]);
0278       }
0279
0280       if (__n1th_is_single) {
0281         std::move(__buffer_begin, __buffer_end, __first);
0282       } else {
0283         auto __n1th = [__radix_number, &__map, &__radix](const auto& __v) {
0284           return std::__nth_radix(__radix_number + 1, __radix, __map(__v));
0285         };
0286         std::__dispose_backward(__buffer_begin, __buffer_end, __first, __n1th, __counters[__radix_number + 1]);
0287       }
0288     }
0289   }
0290 }
0291
0292 _LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(bool __b) { return __b; }
0293
0294 template <class _Ip>
0295 _LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(_Ip __n) {
0296   constexpr const auto __min_value = numeric_limits<_Ip>::min();
0297   return static_cast<make_unsigned_t<_Ip> >(__n ^ __min_value);
0298 }
0299
0300 struct __low_byte_fn {
0301   template <class _Ip>
0302   _LIBCPP_HIDE_FROM_ABI constexpr uint8_t operator()(_Ip __integer) const {
0303     static_assert(is_unsigned<_Ip>::value);
0304
0305     return static_cast<uint8_t>(__integer & 0xff);
0306   }
0307 };
0308
0309 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Map, class _Radix>
0310 _LIBCPP_HIDE_FROM_ABI void
0311 __radix_sort(_RandomAccessIterator1 __first,
0312              _RandomAccessIterator1 __last,
0313              _RandomAccessIterator2 __buffer,
0314              _Map __map,
0315              _Radix __radix) {
0316   auto __map_to_unsigned = [__map = std::move(__map)](const auto& __x) { return std::__shift_to_unsigned(__map(__x)); };
0317   std::__radix_sort_impl(__first, __last, __buffer, __map_to_unsigned, __radix);
0318 }
0319
0320 template <class _RandomAccessIterator1, class _RandomAccessIterator2>
0321 _LIBCPP_HIDE_FROM_ABI void
0322 __radix_sort(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __buffer) {
0323   std::__radix_sort(__first, __last, __buffer, __identity{}, __low_byte_fn{});
0324 }
0325
0326 #endif // _LIBCPP_STD_VER >= 14
0327
0328 _LIBCPP_END_NAMESPACE_STD
0329
0330 _LIBCPP_POP_MACROS
0331
0332 #endif // _LIBCPP___ALGORITHM_RADIX_SORT_H