EnTT  3.6.0
algorithm.hpp
1 #ifndef ENTT_CORE_ALGORITHM_HPP
2 #define ENTT_CORE_ALGORITHM_HPP
3 
4 
5 #include <vector>
6 #include <utility>
7 #include <iterator>
8 #include <algorithm>
9 #include <functional>
10 #include "utility.hpp"
11 
12 
13 namespace entt {
14 
15 
24 struct std_sort {
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));
41  }
42 };
43 
44 
58  template<typename It, typename Compare = std::less<>>
59  void operator()(It first, It last, Compare compare = Compare{}) const {
60  if(first < last) {
61  for(auto it = first + 1; it < last; ++it) {
62  auto value = std::move(*it);
63  auto pre = it;
64 
65  for(; pre > first && compare(value, *(pre-1)); --pre) {
66  *pre = std::move(*(pre-1));
67  }
68 
69  *pre = std::move(value);
70  }
71  }
72  }
73 };
74 
75 
81 template<std::size_t Bit, std::size_t N>
82 struct radix_sort {
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");
84 
100  template<typename It, typename Getter = identity>
101  void operator()(It first, It last, Getter getter = Getter{}) const {
102  if(first < last) {
103  static constexpr auto mask = (1 << Bit) - 1;
104  static constexpr auto buckets = 1 << Bit;
105  static constexpr auto passes = N / Bit;
106 
107  using value_type = typename std::iterator_traits<It>::value_type;
108  std::vector<value_type> aux(std::distance(first, last));
109 
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]{};
113 
114  for(auto it = from; it != to; ++it) {
115  ++count[(getter(*it) >> start) & mask];
116  }
117 
118  for(std::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
119  index[pos + 1u] = index[pos] + count[pos];
120  }
121 
122  for(auto it = from; it != to; ++it) {
123  out[index[(getter(*it) >> start) & mask]++] = std::move(*it);
124  }
125  };
126 
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);
130  }
131 
132  if constexpr(passes & 1) {
133  part(first, last, aux.begin(), (passes - 1) * Bit);
134  std::move(aux.begin(), aux.end(), first);
135  }
136  }
137  }
138 };
139 
140 
141 }
142 
143 
144 #endif
entt::radix_sort::operator()
void operator()(It first, It last, Getter getter=Getter{}) const
Sorts the elements in a range.
Definition: algorithm.hpp:101
entt::std_sort::operator()
void operator()(It first, It last, Compare compare=Compare{}, Args &&... args) const
Sorts the elements in a range.
Definition: algorithm.hpp:39
entt::insertion_sort
Function object for performing insertion sort.
Definition: algorithm.hpp:46
entt::radix_sort
Function object for performing LSD radix sort.
Definition: algorithm.hpp:82
entt
EnTT default namespace.
Definition: algorithm.hpp:13
entt::insertion_sort::operator()
void operator()(It first, It last, Compare compare=Compare{}) const
Sorts the elements in a range.
Definition: algorithm.hpp:59
entt::std_sort
Function object to wrap std::sort in a class type.
Definition: algorithm.hpp:24