15 #ifndef BOOST_SORT_SPREADSORT_DETAIL_INTEGER_SORT_HPP
16 #define BOOST_SORT_SPREADSORT_DETAIL_INTEGER_SORT_HPP
21 #include <boost/static_assert.hpp>
22 #include <boost/serialization/static_warning.hpp>
23 #include <boost/utility/enable_if.hpp>
26 #include <boost/cstdint.hpp>
35 template <
class RandomAccessIter>
38 RandomAccessIter & max, RandomAccessIter & min)
42 while (!(*(current + 1) < *current)) {
44 if (++current == last - 1)
51 while (++current < last) {
54 else if (*current < *min)
63 template <
class RandomAccessIter,
class Compare>
66 RandomAccessIter & max, RandomAccessIter & min, Compare comp)
69 while (!comp(*(current + 1), *current)) {
71 if (++current == last - 1)
77 while (++current < last) {
78 if (comp(*max, *current))
80 else if (comp(*current, *min))
87 template<
unsigned log_mean_bin_size>
89 get_log_divisor(
size_t count,
int log_range)
99 log_divisor += log_mean_bin_size;
108 template <
class RandomAccessIter,
class Div_type,
class Size_type>
110 spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
111 std::vector<RandomAccessIter> &bin_cache,
unsigned cache_offset
118 RandomAccessIter max, min;
121 RandomAccessIter * target_bin;
122 unsigned log_divisor = get_log_divisor<int_log_mean_bin_size>(
124 Div_type div_min = *min >> log_divisor;
125 Div_type div_max = *max >> log_divisor;
126 unsigned bin_count = unsigned(div_max - div_min) + 1;
128 RandomAccessIter * bins =
129 size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
132 for (RandomAccessIter current = first; current != last;)
133 bin_sizes[
size_t((*(current++) >> log_divisor) - div_min)]++;
136 for (
unsigned u = 0; u < bin_count - 1; u++)
137 bins[u + 1] = bins[u] + bin_sizes[u];
139 RandomAccessIter nextbinstart = first;
142 for (
unsigned u = 0; u < bin_count - 1; ++u) {
143 RandomAccessIter * local_bin = bins + u;
144 nextbinstart += bin_sizes[u];
146 for (RandomAccessIter current = *local_bin; current < nextbinstart;
150 for (target_bin = (bins + ((*current >> log_divisor) - div_min));
151 target_bin != local_bin;
152 target_bin = bins + ((*current >> log_divisor) - div_min)) {
156 typename std::iterator_traits<RandomAccessIter>::value_type tmp;
157 RandomAccessIter b = (*target_bin)++;
158 RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
159 if (b_bin != local_bin) {
160 RandomAccessIter c = (*b_bin)++;
170 *local_bin = nextbinstart;
172 bins[bin_count - 1] = last;
183 RandomAccessIter lastPos = first;
184 for (
unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
186 Size_type count = bin_cache[u] - lastPos;
191 if (count < max_count)
192 std::sort(lastPos, bin_cache[u]);
194 spreadsort_rec<RandomAccessIter, Div_type, Size_type>(lastPos,
203 template <
class RandomAccessIter,
class Div_type,
class Right_shift>
204 inline void inner_swap_loop(RandomAccessIter * bins,
205 const RandomAccessIter & next_bin_start,
unsigned ii, Right_shift &rshift
206 ,
const unsigned log_divisor,
const Div_type div_min)
208 RandomAccessIter * local_bin = bins + ii;
209 for (RandomAccessIter current = *local_bin; current < next_bin_start;
211 for (RandomAccessIter * target_bin =
212 (bins + (rshift(*current, log_divisor) - div_min));
213 target_bin != local_bin;
214 target_bin = bins + (rshift(*current, log_divisor) - div_min)) {
215 typename std::iterator_traits<RandomAccessIter>::value_type tmp;
216 RandomAccessIter b = (*target_bin)++;
217 RandomAccessIter * b_bin =
218 bins + (rshift(*b, log_divisor) - div_min);
221 if (b_bin != local_bin) {
222 RandomAccessIter c = (*b_bin)++;
234 *local_bin = next_bin_start;
238 template <
class RandomAccessIter,
class Div_type,
class Right_shift>
239 inline void swap_loop(RandomAccessIter * bins,
240 RandomAccessIter & next_bin_start,
unsigned ii, Right_shift &rshift
241 ,
const size_t *bin_sizes
242 ,
const unsigned log_divisor,
const Div_type div_min)
244 next_bin_start += bin_sizes[ii];
245 inner_swap_loop<RandomAccessIter, Div_type, Right_shift>(bins,
246 next_bin_start, ii, rshift, log_divisor, div_min);
250 template <
class RandomAccessIter,
class Div_type,
class Right_shift,
251 class Compare,
class Size_type,
unsigned log_mean_bin_size,
252 unsigned log_min_split_count,
unsigned log_finishing_count>
254 spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
255 std::vector<RandomAccessIter> &bin_cache,
unsigned cache_offset
256 ,
size_t *bin_sizes, Right_shift rshift, Compare comp)
258 RandomAccessIter max, min;
261 unsigned log_divisor = get_log_divisor<log_mean_bin_size>(last - first,
263 Div_type div_min = rshift(*min, log_divisor);
264 Div_type div_max = rshift(*max, log_divisor);
265 unsigned bin_count = unsigned(div_max - div_min) + 1;
267 RandomAccessIter * bins =
size_bins(bin_sizes, bin_cache, cache_offset,
268 cache_end, bin_count);
271 for (RandomAccessIter current = first; current != last;)
272 bin_sizes[
unsigned(rshift(*(current++), log_divisor) - div_min)]++;
274 for (
unsigned u = 0; u < bin_count - 1; u++)
275 bins[u + 1] = bins[u] + bin_sizes[u];
278 RandomAccessIter next_bin_start = first;
279 for (
unsigned u = 0; u < bin_count - 1; ++u)
280 swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, next_bin_start,
281 u, rshift, bin_sizes, log_divisor, div_min);
282 bins[bin_count - 1] = last;
289 size_t max_count =
get_min_count<log_mean_bin_size, log_min_split_count,
290 log_finishing_count>(log_divisor);
291 RandomAccessIter lastPos = first;
292 for (
unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
294 size_t count = bin_cache[u] - lastPos;
297 if (count < max_count)
298 std::sort(lastPos, bin_cache[u], comp);
300 spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
301 Size_type, log_mean_bin_size, log_min_split_count, log_finishing_count>
302 (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift, comp);
307 template <
class RandomAccessIter,
class Div_type,
class Right_shift,
308 class Size_type,
unsigned log_mean_bin_size,
309 unsigned log_min_split_count,
unsigned log_finishing_count>
311 spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
312 std::vector<RandomAccessIter> &bin_cache,
unsigned cache_offset
313 ,
size_t *bin_sizes, Right_shift rshift)
315 RandomAccessIter max, min;
318 unsigned log_divisor = get_log_divisor<log_mean_bin_size>(last - first,
320 Div_type div_min = rshift(*min, log_divisor);
321 Div_type div_max = rshift(*max, log_divisor);
322 unsigned bin_count = unsigned(div_max - div_min) + 1;
324 RandomAccessIter * bins =
size_bins(bin_sizes, bin_cache, cache_offset,
325 cache_end, bin_count);
328 for (RandomAccessIter current = first; current != last;)
329 bin_sizes[
unsigned(rshift(*(current++), log_divisor) - div_min)]++;
331 for (
unsigned u = 0; u < bin_count - 1; u++)
332 bins[u + 1] = bins[u] + bin_sizes[u];
335 RandomAccessIter nextbinstart = first;
336 for (
unsigned ii = 0; ii < bin_count - 1; ++ii)
337 swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, nextbinstart,
338 ii, rshift, bin_sizes, log_divisor, div_min);
339 bins[bin_count - 1] = last;
346 size_t max_count =
get_min_count<log_mean_bin_size, log_min_split_count,
347 log_finishing_count>(log_divisor);
348 RandomAccessIter lastPos = first;
349 for (
unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
351 size_t count = bin_cache[u] - lastPos;
354 if (count < max_count)
355 std::sort(lastPos, bin_cache[u]);
357 spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Size_type,
358 log_mean_bin_size, log_min_split_count, log_finishing_count>(lastPos,
359 bin_cache[u], bin_cache, cache_end, bin_sizes, rshift);
364 template <
class RandomAccessIter,
class Div_type>
366 inline typename boost::enable_if_c<
sizeof(Div_type) <=
sizeof(
size_t),
368 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type)
371 std::vector<RandomAccessIter> bin_cache;
372 spreadsort_rec<RandomAccessIter, Div_type, size_t>(first, last,
373 bin_cache, 0, bin_sizes);
377 template <
class RandomAccessIter,
class Div_type>
379 inline typename boost::enable_if_c< (sizeof(Div_type) >
sizeof(size_t))
380 &&
sizeof(Div_type) <=
sizeof(boost::uintmax_t),
void >::type
381 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type)
384 std::vector<RandomAccessIter> bin_cache;
385 spreadsort_rec<RandomAccessIter, Div_type, boost::uintmax_t>(first,
386 last, bin_cache, 0, bin_sizes);
389 template <
class RandomAccessIter,
class Div_type>
390 inline typename boost::disable_if_c<
sizeof(Div_type) <=
sizeof(
size_t)
391 ||
sizeof(Div_type) <=
sizeof(boost::uintmax_t),
void >::type
393 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type)
396 BOOST_STATIC_WARNING(
sizeof(Div_type) <=
sizeof(
size_t) );
397 std::sort(first, last);
402 template <
class RandomAccessIter,
class Div_type,
class Right_shift,
405 inline typename boost::enable_if_c<
sizeof(Div_type) <=
sizeof(
size_t),
407 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
408 Right_shift shift, Compare comp)
411 std::vector<RandomAccessIter> bin_cache;
412 spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
415 (first, last, bin_cache, 0, bin_sizes, shift, comp);
418 template <
class RandomAccessIter,
class Div_type,
class Right_shift,
421 inline typename boost::enable_if_c< (sizeof(Div_type) >
sizeof(size_t))
422 &&
sizeof(Div_type) <=
sizeof(boost::uintmax_t),
void >::type
423 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
424 Right_shift shift, Compare comp)
427 std::vector<RandomAccessIter> bin_cache;
428 spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
431 (first, last, bin_cache, 0, bin_sizes, shift, comp);
434 template <
class RandomAccessIter,
class Div_type,
class Right_shift,
436 inline typename boost::disable_if_c<
sizeof(Div_type) <=
sizeof(
size_t)
437 ||
sizeof(Div_type) <=
sizeof(boost::uintmax_t),
void >::type
439 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
440 Right_shift shift, Compare comp)
443 BOOST_STATIC_WARNING(
sizeof(Div_type) <=
sizeof(
size_t) );
444 std::sort(first, last, comp);
449 template <
class RandomAccessIter,
class Div_type,
class Right_shift>
451 inline typename boost::enable_if_c<
sizeof(Div_type) <=
sizeof(
size_t),
453 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
457 std::vector<RandomAccessIter> bin_cache;
458 spreadsort_rec<RandomAccessIter, Div_type, Right_shift, size_t,
461 (first, last, bin_cache, 0, bin_sizes, shift);
464 template <
class RandomAccessIter,
class Div_type,
class Right_shift>
466 inline typename boost::enable_if_c< (sizeof(Div_type) >
sizeof(size_t))
467 &&
sizeof(Div_type) <=
sizeof(boost::uintmax_t),
void >::type
468 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
472 std::vector<RandomAccessIter> bin_cache;
473 spreadsort_rec<RandomAccessIter, Div_type, Right_shift,
476 (first, last, bin_cache, 0, bin_sizes, shift);
479 template <
class RandomAccessIter,
class Div_type,
class Right_shift>
480 inline typename boost::disable_if_c<
sizeof(Div_type) <=
sizeof(
size_t)
481 ||
sizeof(Div_type) <=
sizeof(boost::uintmax_t),
void >::type
483 integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
487 BOOST_STATIC_WARNING(
sizeof(Div_type) <=
sizeof(
size_t) );
488 std::sort(first, last);
void integer_sort(RandomAccessIter first, RandomAccessIter last)
Integer sort algorithm using random access iterators. (All variants fall back to std::sort if the dat...
Definition: integer_sort.hpp:78
Definition: constants.hpp:11
Definition: constants.hpp:30
Definition: constants.hpp:22
size_t get_min_count(unsigned log_range)
Definition: spreadsort_common.hpp:51
Definition: constants.hpp:27
Definition: constants.hpp:19
unsigned rough_log_2_size(const T &input)
Definition: spreadsort_common.hpp:34
bool is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last, Div_type &max, Div_type &min, Right_shift rshift)
Definition: float_sort.hpp:54
RandomAccessIter * size_bins(size_t *bin_sizes, std::vector< RandomAccessIter > &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
Definition: spreadsort_common.hpp:106
Definition: constants.hpp:24