432 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ALGORITHM_RADIX_SORT_H11#define _LIBCPP___ALGORITHM_RADIX_SORT_H12 13// This is an implementation of classic LSD radix sort algorithm, running in linear time and using `O(max(N, M))`14// additional memory, where `N` is size of an input range, `M` - maximum value of15// a radix of the sorted integer type. Type of the radix and its maximum value are determined at compile time16// based on type returned by function `__radix`. The default radix is uint8.17 18// The algorithm is equivalent to several consecutive calls of counting sort for each19// radix of the sorted numbers from low to high byte.20// The algorithm uses a temporary buffer of size equal to size of the input range. Each `i`-th pass21// of the algorithm sorts values by `i`-th radix and moves values to the temporary buffer (for each even `i`, counted22// from zero), or moves them back to the initial range (for each odd `i`). If there is only one radix in sorted integers23// (e.g. int8), the sorted values are placed to the buffer, and then moved back to the initial range.24 25// The implementation also has several optimizations:26// - the counters for the counting sort are calculated in one pass for all radices;27// - if all values of a radix are the same, we do not sort that radix, and just move items to the buffer;28// - if two consecutive radices satisfies condition above, we do nothing for these two radices.29 30#include <__algorithm/for_each.h>31#include <__algorithm/move.h>32#include <__bit/bit_cast.h>33#include <__bit/bit_log2.h>34#include <__config>35#include <__cstddef/size_t.h>36#include <__functional/identity.h>37#include <__iterator/access.h>38#include <__iterator/distance.h>39#include <__iterator/iterator_traits.h>40#include <__iterator/move_iterator.h>41#include <__iterator/next.h>42#include <__iterator/reverse_iterator.h>43#include <__numeric/partial_sum.h>44#include <__type_traits/decay.h>45#include <__type_traits/enable_if.h>46#include <__type_traits/invoke.h>47#include <__type_traits/is_assignable.h>48#include <__type_traits/is_enum.h>49#include <__type_traits/is_integral.h>50#include <__type_traits/is_unsigned.h>51#include <__type_traits/make_unsigned.h>52#include <__type_traits/void_t.h>53#include <__utility/declval.h>54#include <__utility/forward.h>55#include <__utility/integer_sequence.h>56#include <__utility/move.h>57#include <__utility/pair.h>58#include <climits>59#include <cstdint>60#include <initializer_list>61#include <limits>62 63#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)64# pragma GCC system_header65#endif66 67_LIBCPP_PUSH_MACROS68#include <__undef_macros>69 70_LIBCPP_BEGIN_NAMESPACE_STD71 72#if _LIBCPP_STD_VER >= 1473 74template <class _InputIterator, class _OutputIterator>75_LIBCPP_HIDE_FROM_ABI constexpr pair<_OutputIterator, __iterator_value_type<_InputIterator>>76__partial_sum_max(_InputIterator __first, _InputIterator __last, _OutputIterator __result) {77 if (__first == __last)78 return {__result, 0};79 80 auto __max = *__first;81 __iterator_value_type<_InputIterator> __sum = *__first;82 *__result = __sum;83 84 while (++__first != __last) {85 if (__max < *__first) {86 __max = *__first;87 }88 __sum = std::move(__sum) + *__first;89 *++__result = __sum;90 }91 return {++__result, __max};92}93 94template <class _Value, class _Map, class _Radix>95struct __radix_sort_traits {96 using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>;97 static_assert(is_unsigned<__image_type>::value);98 99 using __radix_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Radix, __image_type>>;100 static_assert(is_integral<__radix_type>::value);101 102 static constexpr auto __radix_value_range = numeric_limits<__radix_type>::max() + 1;103 static constexpr auto __radix_size = std::__bit_log2<uint64_t>(__radix_value_range);104 static constexpr auto __radix_count = sizeof(__image_type) * CHAR_BIT / __radix_size;105};106 107template <class _Value, class _Map>108struct __counting_sort_traits {109 using __image_type _LIBCPP_NODEBUG = decay_t<__invoke_result_t<_Map, _Value>>;110 static_assert(is_unsigned<__image_type>::value);111 112 static constexpr const auto __value_range = numeric_limits<__image_type>::max() + 1;113 static constexpr auto __radix_size = std::__bit_log2<uint64_t>(__value_range);114};115 116template <class _Radix, class _Integer>117_LIBCPP_HIDE_FROM_ABI constexpr auto __nth_radix(size_t __radix_number, _Radix __radix, _Integer __n) {118 static_assert(is_unsigned<_Integer>::value);119 using __traits = __counting_sort_traits<_Integer, _Radix>;120 121 return __radix(static_cast<_Integer>(__n >> __traits::__radix_size * __radix_number));122}123 124template <class _ForwardIterator, class _Map, class _RandomAccessIterator>125_LIBCPP_HIDE_FROM_ABI constexpr void126__collect(_ForwardIterator __first, _ForwardIterator __last, _Map __map, _RandomAccessIterator __counters) {127 using __value_type = __iterator_value_type<_ForwardIterator>;128 using __traits = __counting_sort_traits<__value_type, _Map>;129 130 std::for_each(__first, __last, [&__counters, &__map](const auto& __preimage) { ++__counters[__map(__preimage)]; });131 132 const auto __counters_end = __counters + __traits::__value_range;133 std::partial_sum(__counters, __counters_end, __counters);134}135 136template <class _ForwardIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>137_LIBCPP_HIDE_FROM_ABI constexpr void138__dispose(_ForwardIterator __first,139 _ForwardIterator __last,140 _RandomAccessIterator1 __result,141 _Map __map,142 _RandomAccessIterator2 __counters) {143 std::for_each(__first, __last, [&__result, &__counters, &__map](auto&& __preimage) {144 auto __index = __counters[__map(__preimage)]++;145 __result[__index] = std::move(__preimage);146 });147}148 149template <class _ForwardIterator,150 class _Map,151 class _Radix,152 class _RandomAccessIterator1,153 class _RandomAccessIterator2,154 size_t... _Radices>155_LIBCPP_HIDE_FROM_ABI constexpr bool __collect_impl(156 _ForwardIterator __first,157 _ForwardIterator __last,158 _Map __map,159 _Radix __radix,160 _RandomAccessIterator1 __counters,161 _RandomAccessIterator2 __maximums,162 index_sequence<_Radices...>) {163 using __value_type = __iterator_value_type<_ForwardIterator>;164 constexpr auto __radix_value_range = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_value_range;165 166 auto __previous = numeric_limits<__invoke_result_t<_Map, __value_type>>::min();167 auto __is_sorted = true;168 std::for_each(__first, __last, [&__counters, &__map, &__radix, &__previous, &__is_sorted](const auto& __value) {169 auto __current = __map(__value);170 __is_sorted &= (__current >= __previous);171 __previous = __current;172 173 (++__counters[_Radices][std::__nth_radix(_Radices, __radix, __current)], ...);174 });175 176 ((__maximums[_Radices] =177 std::__partial_sum_max(__counters[_Radices], __counters[_Radices] + __radix_value_range, __counters[_Radices])178 .second),179 ...);180 181 return __is_sorted;182}183 184template <class _ForwardIterator, class _Map, class _Radix, class _RandomAccessIterator1, class _RandomAccessIterator2>185_LIBCPP_HIDE_FROM_ABI constexpr bool186__collect(_ForwardIterator __first,187 _ForwardIterator __last,188 _Map __map,189 _Radix __radix,190 _RandomAccessIterator1 __counters,191 _RandomAccessIterator2 __maximums) {192 using __value_type = __iterator_value_type<_ForwardIterator>;193 constexpr auto __radix_count = __radix_sort_traits<__value_type, _Map, _Radix>::__radix_count;194 return std::__collect_impl(195 __first, __last, __map, __radix, __counters, __maximums, make_index_sequence<__radix_count>());196}197 198template <class _BidirectionalIterator, class _RandomAccessIterator1, class _Map, class _RandomAccessIterator2>199_LIBCPP_HIDE_FROM_ABI constexpr void __dispose_backward(200 _BidirectionalIterator __first,201 _BidirectionalIterator __last,202 _RandomAccessIterator1 __result,203 _Map __map,204 _RandomAccessIterator2 __counters) {205 std::for_each(std::make_reverse_iterator(__last),206 std::make_reverse_iterator(__first),207 [&__result, &__counters, &__map](auto&& __preimage) {208 auto __index = --__counters[__map(__preimage)];209 __result[__index] = std::move(__preimage);210 });211}212 213template <class _ForwardIterator, class _RandomAccessIterator, class _Map>214_LIBCPP_HIDE_FROM_ABI constexpr _RandomAccessIterator215__counting_sort_impl(_ForwardIterator __first, _ForwardIterator __last, _RandomAccessIterator __result, _Map __map) {216 using __value_type = __iterator_value_type<_ForwardIterator>;217 using __traits = __counting_sort_traits<__value_type, _Map>;218 219 __iterator_difference_type<_RandomAccessIterator> __counters[__traits::__value_range + 1] = {0};220 221 std::__collect(__first, __last, __map, std::next(std::begin(__counters)));222 std::__dispose(__first, __last, __result, __map, std::begin(__counters));223 224 return __result + __counters[__traits::__value_range];225}226 227template <228 class _RandomAccessIterator1,229 class _RandomAccessIterator2,230 class _Map,231 class _Radix,232 enable_if_t<__radix_sort_traits<__iterator_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count == 1,233 int> = 0>234_LIBCPP_HIDE_FROM_ABI constexpr void __radix_sort_impl(235 _RandomAccessIterator1 __first,236 _RandomAccessIterator1 __last,237 _RandomAccessIterator2 __buffer,238 _Map __map,239 _Radix __radix) {240 auto __buffer_end = std::__counting_sort_impl(__first, __last, __buffer, [&__map, &__radix](const auto& __value) {241 return __radix(__map(__value));242 });243 244 std::move(__buffer, __buffer_end, __first);245}246 247template <class _RandomAccessIterator1,248 class _RandomAccessIterator2,249 class _Map,250 class _Radix,251 enable_if_t<252 __radix_sort_traits<__iterator_value_type<_RandomAccessIterator1>, _Map, _Radix>::__radix_count % 2 == 0,253 int> = 0>254_LIBCPP_HIDE_FROM_ABI constexpr void __radix_sort_impl(255 _RandomAccessIterator1 __first,256 _RandomAccessIterator1 __last,257 _RandomAccessIterator2 __buffer_begin,258 _Map __map,259 _Radix __radix) {260 using __value_type = __iterator_value_type<_RandomAccessIterator1>;261 using __traits = __radix_sort_traits<__value_type, _Map, _Radix>;262 263 __iterator_difference_type<_RandomAccessIterator1>264 __counters[__traits::__radix_count][__traits::__radix_value_range] = {{0}};265 __iterator_difference_type<_RandomAccessIterator1> __maximums[__traits::__radix_count] = {0};266 const auto __is_sorted = std::__collect(__first, __last, __map, __radix, __counters, __maximums);267 if (!__is_sorted) {268 const auto __range_size = std::distance(__first, __last);269 auto __buffer_end = __buffer_begin + __range_size;270 for (size_t __radix_number = 0; __radix_number < __traits::__radix_count; __radix_number += 2) {271 const auto __n0th_is_single = __maximums[__radix_number] == __range_size;272 const auto __n1th_is_single = __maximums[__radix_number + 1] == __range_size;273 274 if (__n0th_is_single && __n1th_is_single) {275 continue;276 }277 278 if (__n0th_is_single) {279 std::move(__first, __last, __buffer_begin);280 } else {281 auto __n0th = [__radix_number, &__map, &__radix](const auto& __v) {282 return std::__nth_radix(__radix_number, __radix, __map(__v));283 };284 std::__dispose_backward(__first, __last, __buffer_begin, __n0th, __counters[__radix_number]);285 }286 287 if (__n1th_is_single) {288 std::move(__buffer_begin, __buffer_end, __first);289 } else {290 auto __n1th = [__radix_number, &__map, &__radix](const auto& __v) {291 return std::__nth_radix(__radix_number + 1, __radix, __map(__v));292 };293 std::__dispose_backward(__buffer_begin, __buffer_end, __first, __n1th, __counters[__radix_number + 1]);294 }295 }296 }297}298 299_LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(bool __b) { return __b; }300 301template <class _Ip>302_LIBCPP_HIDE_FROM_ABI constexpr auto __shift_to_unsigned(_Ip __n) {303 constexpr const auto __min_value = numeric_limits<_Ip>::min();304 return static_cast<make_unsigned_t<_Ip> >(__n ^ __min_value);305}306 307template <size_t _Size>308struct __unsigned_integer_of_size;309 310template <>311struct __unsigned_integer_of_size<1> {312 using type _LIBCPP_NODEBUG = uint8_t;313};314 315template <>316struct __unsigned_integer_of_size<2> {317 using type _LIBCPP_NODEBUG = uint16_t;318};319 320template <>321struct __unsigned_integer_of_size<4> {322 using type _LIBCPP_NODEBUG = uint32_t;323};324 325template <>326struct __unsigned_integer_of_size<8> {327 using type _LIBCPP_NODEBUG = uint64_t;328};329 330# if _LIBCPP_HAS_INT128331template <>332struct __unsigned_integer_of_size<16> {333 using type _LIBCPP_NODEBUG = unsigned __int128;334};335# endif336 337template <size_t _Size>338using __unsigned_integer_of_size_t _LIBCPP_NODEBUG = typename __unsigned_integer_of_size<_Size>::type;339 340template <class _Sc>341using __unsigned_representation_for_t _LIBCPP_NODEBUG = __unsigned_integer_of_size_t<sizeof(_Sc)>;342 343// The function `__to_ordered_integral` is defined for integers and IEEE 754 floating-point numbers.344// Returns an integer representation such that for any `x` and `y` such that `x < y`, the expression345// `__to_ordered_integral(x) < __to_ordered_integral(y)` is true, where `x`, `y` are integers or IEEE 754 floats.346template <class _Integral, enable_if_t< is_integral<_Integral>::value, int> = 0>347_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Integral __n) {348 return __n;349}350 351// An overload for IEEE 754 floating-point numbers352 353// For the floats conforming to IEEE 754 (IEC 559) standard, we know that:354// 1. The bit representation of positive floats directly reflects their order:355// When comparing floats by magnitude, the number with the larger exponent is greater, and if the exponents are356// equal, the one with the larger mantissa is greater.357// 2. The bit representation of negative floats reflects their reverse order (for the same reasons).358// 3. The most significant bit (sign bit) is zero for positive floats and one for negative floats. Therefore, in the raw359// bit representation, any negative number will be greater than any positive number.360 361// The only exception from this rule is `NaN`, which is unordered by definition.362 363// Based on the above, to obtain correctly ordered integral representation of floating-point numbers, we need to:364// 1. Invert the bit representation (including the sign bit) of negative floats to switch from reverse order to direct365// order;366// 2. Invert the sign bit for positive floats.367 368// Thus, in final integral representation, we have reversed the order for negative floats and made all negative floats369// smaller than all positive numbers (by inverting the sign bit).370template <class _Floating, enable_if_t< numeric_limits<_Floating>::is_iec559, int> = 0>371_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Floating __f) {372 using __integral_type = __unsigned_representation_for_t<_Floating>;373 constexpr auto __bit_count = std::numeric_limits<__integral_type>::digits;374 constexpr auto __sign_bit_mask = static_cast<__integral_type>(__integral_type{1} << (__bit_count - 1));375 376 const auto __u = std::__bit_cast<__integral_type>(__f);377 378 return static_cast<__integral_type>(__u & __sign_bit_mask ? ~__u : __u ^ __sign_bit_mask);379}380 381// There may exist user-defined comparison for enum, so we cannot compare enums just like integers.382template <class _Enum, enable_if_t< is_enum<_Enum>::value, int> = 0>383_LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(_Enum __e) = delete;384 385// `long double` varies significantly across platforms and compilers, making it practically386// impossible to determine its actual bit width for conversion to an ordered integer.387inline _LIBCPP_HIDE_FROM_ABI constexpr auto __to_ordered_integral(long double) = delete;388 389template <class _Tp, class = void>390inline const bool __is_ordered_integer_representable_v = false;391 392template <class _Tp>393inline const bool394 __is_ordered_integer_representable_v<_Tp, __void_t<decltype(std::__to_ordered_integral(std::declval<_Tp>()))>> =395 true;396 397struct __low_byte_fn {398 template <class _Ip>399 _LIBCPP_HIDE_FROM_ABI constexpr uint8_t operator()(_Ip __integer) const {400 static_assert(is_unsigned<_Ip>::value);401 402 return static_cast<uint8_t>(__integer & 0xff);403 }404};405 406template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _Map, class _Radix>407_LIBCPP_HIDE_FROM_ABI constexpr void408__radix_sort(_RandomAccessIterator1 __first,409 _RandomAccessIterator1 __last,410 _RandomAccessIterator2 __buffer,411 _Map __map,412 _Radix __radix) {413 auto __map_to_unsigned = [__map = std::move(__map)](const auto& __x) {414 return std::__shift_to_unsigned(__map(std::__to_ordered_integral(__x)));415 };416 std::__radix_sort_impl(__first, __last, __buffer, __map_to_unsigned, __radix);417}418 419template <class _RandomAccessIterator1, class _RandomAccessIterator2>420_LIBCPP_HIDE_FROM_ABI constexpr void421__radix_sort(_RandomAccessIterator1 __first, _RandomAccessIterator1 __last, _RandomAccessIterator2 __buffer) {422 std::__radix_sort(__first, __last, __buffer, __identity{}, __low_byte_fn{});423}424 425#endif // _LIBCPP_STD_VER >= 14426 427_LIBCPP_END_NAMESPACE_STD428 429_LIBCPP_POP_MACROS430 431#endif // _LIBCPP___ALGORITHM_RADIX_SORT_H432