1 #ifndef ENTT_CORE_ALGORITHM_HPP
2 #define ENTT_CORE_ALGORITHM_HPP
10 #include "utility.hpp"
38 template<
typename It,
typename Compare = std::less<>,
typename... Args>
39 void operator()(It first, It last, Compare compare = Compare{}, Args &&... args)
const {
40 std::sort(std::forward<Args>(args)..., std::move(first), std::move(last), std::move(compare));
58 template<
typename It,
typename Compare = std::less<>>
59 void operator()(It first, It last, Compare compare = Compare{})
const {
61 for(
auto it = first + 1; it < last; ++it) {
62 auto value = std::move(*it);
65 for(; pre > first && compare(value, *(pre-1)); --pre) {
66 *pre = std::move(*(pre-1));
69 *pre = std::move(value);
81 template<std::
size_t Bit, std::
size_t N>
83 static_assert((N % Bit) == 0,
"The maximum number of bits to sort must be a multiple of the number of bits processed per pass");
100 template<
typename It,
typename Getter =
identity>
101 void operator()(It first, It last, Getter getter = Getter{})
const {
103 static constexpr
auto mask = (1 << Bit) - 1;
104 static constexpr
auto buckets = 1 << Bit;
105 static constexpr
auto passes = N / Bit;
107 using value_type =
typename std::iterator_traits<It>::value_type;
108 std::vector<value_type> aux(std::distance(first, last));
110 auto part = [getter = std::move(getter)](
auto from,
auto to,
auto out,
auto start) {
111 std::size_t index[buckets]{};
112 std::size_t count[buckets]{};
114 for(
auto it = from; it != to; ++it) {
115 ++count[(getter(*it) >> start) & mask];
118 for(std::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
119 index[pos + 1u] = index[pos] + count[pos];
122 for(
auto it = from; it != to; ++it) {
123 out[index[(getter(*it) >> start) & mask]++] = std::move(*it);
127 for(std::size_t pass = 0; pass < (passes & ~1); pass += 2) {
128 part(first, last, aux.begin(), pass * Bit);
129 part(aux.begin(), aux.end(), first, (pass + 1) * Bit);
132 if constexpr(passes & 1) {
133 part(first, last, aux.begin(), (passes - 1) * Bit);
134 std::move(aux.begin(), aux.end(), first);