// Details for templated Spreadsort-based integer_sort. | |
// Copyright Steven J. Ross 2001 - 2014. | |
// Distributed under the Boost Software License, Version 1.0. | |
// (See accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
// See http://www.boost.org/libs/sort for library home page. | |
/* | |
Some improvements suggested by: | |
Phil Endecott and Frank Gennari | |
*/ | |
#ifndef BOOST_SORT_SPREADSORT_DETAIL_INTEGER_SORT_HPP | |
#define BOOST_SORT_SPREADSORT_DETAIL_INTEGER_SORT_HPP | |
#include <algorithm> | |
#include <vector> | |
#include <limits> | |
#include <functional> | |
#include <boost/static_assert.hpp> | |
#include <boost/serialization/static_warning.hpp> | |
#include <boost/utility/enable_if.hpp> | |
#include <boost/sort/spreadsort/detail/constants.hpp> | |
#include <boost/sort/spreadsort/detail/spreadsort_common.hpp> | |
#include <boost/cstdint.hpp> | |
namespace boost { | |
namespace sort { | |
namespace spreadsort { | |
namespace detail { | |
// Return true if the list is sorted. Otherwise, find the minimum and | |
// maximum using <. | |
template <class RandomAccessIter> | |
inline bool | |
is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last, | |
RandomAccessIter & max, RandomAccessIter & min) | |
{ | |
min = max = current; | |
//This assumes we have more than 1 element based on prior checks. | |
while (!(*(current + 1) < *current)) { | |
//If everything is in sorted order, return | |
if (++current == last - 1) | |
return true; | |
} | |
//The maximum is the last sorted element | |
max = current; | |
//Start from the first unsorted element | |
while (++current < last) { | |
if (*max < *current) | |
max = current; | |
else if (*current < *min) | |
min = current; | |
} | |
return false; | |
} | |
// Return true if the list is sorted. Otherwise, find the minimum and | |
// maximum. | |
// Use a user-defined comparison operator | |
template <class RandomAccessIter, class Compare> | |
inline bool | |
is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last, | |
RandomAccessIter & max, RandomAccessIter & min, Compare comp) | |
{ | |
min = max = current; | |
while (!comp(*(current + 1), *current)) { | |
//If everything is in sorted order, return | |
if (++current == last - 1) | |
return true; | |
} | |
//The maximum is the last sorted element | |
max = current; | |
while (++current < last) { | |
if (comp(*max, *current)) | |
max = current; | |
else if (comp(*current, *min)) | |
min = current; | |
} | |
return false; | |
} | |
//Gets a non-negative right bit shift to operate as a logarithmic divisor | |
template<unsigned log_mean_bin_size> | |
inline int | |
get_log_divisor(size_t count, int log_range) | |
{ | |
int log_divisor; | |
//If we can finish in one iteration without exceeding either | |
//(2 to the max_finishing_splits) or n bins, do so | |
if ((log_divisor = log_range - rough_log_2_size(count)) <= 0 && | |
log_range <= max_finishing_splits) | |
log_divisor = 0; | |
else { | |
//otherwise divide the data into an optimized number of pieces | |
log_divisor += log_mean_bin_size; | |
//Cannot exceed max_splits or cache misses slow down bin lookups | |
if ((log_range - log_divisor) > max_splits) | |
log_divisor = log_range - max_splits; | |
} | |
return log_divisor; | |
} | |
//Implementation for recursive integer sorting | |
template <class RandomAccessIter, class Div_type, class Size_type> | |
inline void | |
spreadsort_rec(RandomAccessIter first, RandomAccessIter last, | |
std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset | |
, size_t *bin_sizes) | |
{ | |
//This step is roughly 10% of runtime, but it helps avoid worst-case | |
//behavior and improve behavior with real data | |
//If you know the maximum and minimum ahead of time, you can pass those | |
//values in and skip this step for the first iteration | |
RandomAccessIter max, min; | |
if (is_sorted_or_find_extremes(first, last, max, min)) | |
return; | |
RandomAccessIter * target_bin; | |
unsigned log_divisor = get_log_divisor<int_log_mean_bin_size>( | |
last - first, rough_log_2_size(Size_type((*max >> 0) - (*min >> 0)))); | |
Div_type div_min = *min >> log_divisor; | |
Div_type div_max = *max >> log_divisor; | |
unsigned bin_count = unsigned(div_max - div_min) + 1; | |
unsigned cache_end; | |
RandomAccessIter * bins = | |
size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); | |
//Calculating the size of each bin; this takes roughly 10% of runtime | |
for (RandomAccessIter current = first; current != last;) | |
bin_sizes[size_t((*(current++) >> log_divisor) - div_min)]++; | |
//Assign the bin positions | |
bins[0] = first; | |
for (unsigned u = 0; u < bin_count - 1; u++) | |
bins[u + 1] = bins[u] + bin_sizes[u]; | |
RandomAccessIter nextbinstart = first; | |
//Swap into place | |
//This dominates runtime, mostly in the swap and bin lookups | |
for (unsigned u = 0; u < bin_count - 1; ++u) { | |
RandomAccessIter * local_bin = bins + u; | |
nextbinstart += bin_sizes[u]; | |
//Iterating over each element in this bin | |
for (RandomAccessIter current = *local_bin; current < nextbinstart; | |
++current) { | |
//Swapping elements in current into place until the correct | |
//element has been swapped in | |
for (target_bin = (bins + ((*current >> log_divisor) - div_min)); | |
target_bin != local_bin; | |
target_bin = bins + ((*current >> log_divisor) - div_min)) { | |
//3-way swap; this is about 1% faster than a 2-way swap | |
//The main advantage is less copies are involved per item | |
//put in the correct place | |
typename std::iterator_traits<RandomAccessIter>::value_type tmp; | |
RandomAccessIter b = (*target_bin)++; | |
RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min); | |
if (b_bin != local_bin) { | |
RandomAccessIter c = (*b_bin)++; | |
tmp = *c; | |
*c = *b; | |
} | |
else | |
tmp = *b; | |
*b = *current; | |
*current = tmp; | |
} | |
} | |
*local_bin = nextbinstart; | |
} | |
bins[bin_count - 1] = last; | |
//If we've bucketsorted, the array is sorted and we should skip recursion | |
if (!log_divisor) | |
return; | |
//log_divisor is the remaining range; calculating the comparison threshold | |
size_t max_count = | |
get_min_count<int_log_mean_bin_size, int_log_min_split_count, | |
int_log_finishing_count>(log_divisor); | |
//Recursing | |
RandomAccessIter lastPos = first; | |
for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], | |
++u) { | |
Size_type count = bin_cache[u] - lastPos; | |
//don't sort unless there are at least two items to Compare | |
if (count < 2) | |
continue; | |
//using std::sort if its worst-case is better | |
if (count < max_count) | |
std::sort(lastPos, bin_cache[u]); | |
else | |
spreadsort_rec<RandomAccessIter, Div_type, Size_type>(lastPos, | |
bin_cache[u], | |
bin_cache, | |
cache_end, | |
bin_sizes); | |
} | |
} | |
//Generic bitshift-based 3-way swapping code | |
template <class RandomAccessIter, class Div_type, class Right_shift> | |
inline void inner_swap_loop(RandomAccessIter * bins, | |
const RandomAccessIter & next_bin_start, unsigned ii, Right_shift &rshift | |
, const unsigned log_divisor, const Div_type div_min) | |
{ | |
RandomAccessIter * local_bin = bins + ii; | |
for (RandomAccessIter current = *local_bin; current < next_bin_start; | |
++current) { | |
for (RandomAccessIter * target_bin = | |
(bins + (rshift(*current, log_divisor) - div_min)); | |
target_bin != local_bin; | |
target_bin = bins + (rshift(*current, log_divisor) - div_min)) { | |
typename std::iterator_traits<RandomAccessIter>::value_type tmp; | |
RandomAccessIter b = (*target_bin)++; | |
RandomAccessIter * b_bin = | |
bins + (rshift(*b, log_divisor) - div_min); | |
//Three-way swap; if the item to be swapped doesn't belong | |
//in the current bin, swap it to where it belongs | |
if (b_bin != local_bin) { | |
RandomAccessIter c = (*b_bin)++; | |
tmp = *c; | |
*c = *b; | |
} | |
//Note: we could increment current once the swap is done in this case | |
//but that seems to impair performance | |
else | |
tmp = *b; | |
*b = *current; | |
*current = tmp; | |
} | |
} | |
*local_bin = next_bin_start; | |
} | |
//Standard swapping wrapper for ascending values | |
template <class RandomAccessIter, class Div_type, class Right_shift> | |
inline void swap_loop(RandomAccessIter * bins, | |
RandomAccessIter & next_bin_start, unsigned ii, Right_shift &rshift | |
, const size_t *bin_sizes | |
, const unsigned log_divisor, const Div_type div_min) | |
{ | |
next_bin_start += bin_sizes[ii]; | |
inner_swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, | |
next_bin_start, ii, rshift, log_divisor, div_min); | |
} | |
//Functor implementation for recursive sorting | |
template <class RandomAccessIter, class Div_type, class Right_shift, | |
class Compare, class Size_type, unsigned log_mean_bin_size, | |
unsigned log_min_split_count, unsigned log_finishing_count> | |
inline void | |
spreadsort_rec(RandomAccessIter first, RandomAccessIter last, | |
std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset | |
, size_t *bin_sizes, Right_shift rshift, Compare comp) | |
{ | |
RandomAccessIter max, min; | |
if (is_sorted_or_find_extremes(first, last, max, min, comp)) | |
return; | |
unsigned log_divisor = get_log_divisor<log_mean_bin_size>(last - first, | |
rough_log_2_size(Size_type(rshift(*max, 0) - rshift(*min, 0)))); | |
Div_type div_min = rshift(*min, log_divisor); | |
Div_type div_max = rshift(*max, log_divisor); | |
unsigned bin_count = unsigned(div_max - div_min) + 1; | |
unsigned cache_end; | |
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, | |
cache_end, bin_count); | |
//Calculating the size of each bin | |
for (RandomAccessIter current = first; current != last;) | |
bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++; | |
bins[0] = first; | |
for (unsigned u = 0; u < bin_count - 1; u++) | |
bins[u + 1] = bins[u] + bin_sizes[u]; | |
//Swap into place | |
RandomAccessIter next_bin_start = first; | |
for (unsigned u = 0; u < bin_count - 1; ++u) | |
swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, next_bin_start, | |
u, rshift, bin_sizes, log_divisor, div_min); | |
bins[bin_count - 1] = last; | |
//If we've bucketsorted, the array is sorted | |
if (!log_divisor) | |
return; | |
//Recursing | |
size_t max_count = get_min_count<log_mean_bin_size, log_min_split_count, | |
log_finishing_count>(log_divisor); | |
RandomAccessIter lastPos = first; | |
for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], | |
++u) { | |
size_t count = bin_cache[u] - lastPos; | |
if (count < 2) | |
continue; | |
if (count < max_count) | |
std::sort(lastPos, bin_cache[u], comp); | |
else | |
spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare, | |
Size_type, log_mean_bin_size, log_min_split_count, log_finishing_count> | |
(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift, comp); | |
} | |
} | |
//Functor implementation for recursive sorting with only Shift overridden | |
template <class RandomAccessIter, class Div_type, class Right_shift, | |
class Size_type, unsigned log_mean_bin_size, | |
unsigned log_min_split_count, unsigned log_finishing_count> | |
inline void | |
spreadsort_rec(RandomAccessIter first, RandomAccessIter last, | |
std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset | |
, size_t *bin_sizes, Right_shift rshift) | |
{ | |
RandomAccessIter max, min; | |
if (is_sorted_or_find_extremes(first, last, max, min)) | |
return; | |
unsigned log_divisor = get_log_divisor<log_mean_bin_size>(last - first, | |
rough_log_2_size(Size_type(rshift(*max, 0) - rshift(*min, 0)))); | |
Div_type div_min = rshift(*min, log_divisor); | |
Div_type div_max = rshift(*max, log_divisor); | |
unsigned bin_count = unsigned(div_max - div_min) + 1; | |
unsigned cache_end; | |
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, | |
cache_end, bin_count); | |
//Calculating the size of each bin | |
for (RandomAccessIter current = first; current != last;) | |
bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++; | |
bins[0] = first; | |
for (unsigned u = 0; u < bin_count - 1; u++) | |
bins[u + 1] = bins[u] + bin_sizes[u]; | |
//Swap into place | |
RandomAccessIter nextbinstart = first; | |
for (unsigned ii = 0; ii < bin_count - 1; ++ii) | |
swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, nextbinstart, | |
ii, rshift, bin_sizes, log_divisor, div_min); | |
bins[bin_count - 1] = last; | |
//If we've bucketsorted, the array is sorted | |
if (!log_divisor) | |
return; | |
//Recursing | |
size_t max_count = get_min_count<log_mean_bin_size, log_min_split_count, | |
log_finishing_count>(log_divisor); | |
RandomAccessIter lastPos = first; | |
for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], | |
++u) { | |
size_t count = bin_cache[u] - lastPos; | |
if (count < 2) | |
continue; | |
if (count < max_count) | |
std::sort(lastPos, bin_cache[u]); | |
else | |
spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Size_type, | |
log_mean_bin_size, log_min_split_count, log_finishing_count>(lastPos, | |
bin_cache[u], bin_cache, cache_end, bin_sizes, rshift); | |
} | |
} | |
//Holds the bin vector and makes the initial recursive call | |
template <class RandomAccessIter, class Div_type> | |
//Only use spreadsort if the integer can fit in a size_t | |
inline typename boost::enable_if_c< sizeof(Div_type) <= sizeof(size_t), | |
void >::type | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type) | |
{ | |
size_t bin_sizes[1 << max_finishing_splits]; | |
std::vector<RandomAccessIter> bin_cache; | |
spreadsort_rec<RandomAccessIter, Div_type, size_t>(first, last, | |
bin_cache, 0, bin_sizes); | |
} | |
//Holds the bin vector and makes the initial recursive call | |
template <class RandomAccessIter, class Div_type> | |
//Only use spreadsort if the integer can fit in a uintmax_t | |
inline typename boost::enable_if_c< (sizeof(Div_type) > sizeof(size_t)) | |
&& sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type) | |
{ | |
size_t bin_sizes[1 << max_finishing_splits]; | |
std::vector<RandomAccessIter> bin_cache; | |
spreadsort_rec<RandomAccessIter, Div_type, boost::uintmax_t>(first, | |
last, bin_cache, 0, bin_sizes); | |
} | |
template <class RandomAccessIter, class Div_type> | |
inline typename boost::disable_if_c< sizeof(Div_type) <= sizeof(size_t) | |
|| sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type | |
//defaulting to std::sort when integer_sort won't work | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type) | |
{ | |
//Warning that we're using std::sort, even though integer_sort was called | |
BOOST_STATIC_WARNING( sizeof(Div_type) <= sizeof(size_t) ); | |
std::sort(first, last); | |
} | |
//Same for the full functor version | |
template <class RandomAccessIter, class Div_type, class Right_shift, | |
class Compare> | |
//Only use spreadsort if the integer can fit in a size_t | |
inline typename boost::enable_if_c< sizeof(Div_type) <= sizeof(size_t), | |
void >::type | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type, | |
Right_shift shift, Compare comp) | |
{ | |
size_t bin_sizes[1 << max_finishing_splits]; | |
std::vector<RandomAccessIter> bin_cache; | |
spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare, | |
size_t, int_log_mean_bin_size, int_log_min_split_count, | |
int_log_finishing_count> | |
(first, last, bin_cache, 0, bin_sizes, shift, comp); | |
} | |
template <class RandomAccessIter, class Div_type, class Right_shift, | |
class Compare> | |
//Only use spreadsort if the integer can fit in a uintmax_t | |
inline typename boost::enable_if_c< (sizeof(Div_type) > sizeof(size_t)) | |
&& sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type, | |
Right_shift shift, Compare comp) | |
{ | |
size_t bin_sizes[1 << max_finishing_splits]; | |
std::vector<RandomAccessIter> bin_cache; | |
spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare, | |
boost::uintmax_t, int_log_mean_bin_size, | |
int_log_min_split_count, int_log_finishing_count> | |
(first, last, bin_cache, 0, bin_sizes, shift, comp); | |
} | |
template <class RandomAccessIter, class Div_type, class Right_shift, | |
class Compare> | |
inline typename boost::disable_if_c< sizeof(Div_type) <= sizeof(size_t) | |
|| sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type | |
//defaulting to std::sort when integer_sort won't work | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type, | |
Right_shift shift, Compare comp) | |
{ | |
//Warning that we're using std::sort, even though integer_sort was called | |
BOOST_STATIC_WARNING( sizeof(Div_type) <= sizeof(size_t) ); | |
std::sort(first, last, comp); | |
} | |
//Same for the right shift version | |
template <class RandomAccessIter, class Div_type, class Right_shift> | |
//Only use spreadsort if the integer can fit in a size_t | |
inline typename boost::enable_if_c< sizeof(Div_type) <= sizeof(size_t), | |
void >::type | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type, | |
Right_shift shift) | |
{ | |
size_t bin_sizes[1 << max_finishing_splits]; | |
std::vector<RandomAccessIter> bin_cache; | |
spreadsort_rec<RandomAccessIter, Div_type, Right_shift, size_t, | |
int_log_mean_bin_size, int_log_min_split_count, | |
int_log_finishing_count> | |
(first, last, bin_cache, 0, bin_sizes, shift); | |
} | |
template <class RandomAccessIter, class Div_type, class Right_shift> | |
//Only use spreadsort if the integer can fit in a uintmax_t | |
inline typename boost::enable_if_c< (sizeof(Div_type) > sizeof(size_t)) | |
&& sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type, | |
Right_shift shift) | |
{ | |
size_t bin_sizes[1 << max_finishing_splits]; | |
std::vector<RandomAccessIter> bin_cache; | |
spreadsort_rec<RandomAccessIter, Div_type, Right_shift, | |
boost::uintmax_t, int_log_mean_bin_size, | |
int_log_min_split_count, int_log_finishing_count> | |
(first, last, bin_cache, 0, bin_sizes, shift); | |
} | |
template <class RandomAccessIter, class Div_type, class Right_shift> | |
inline typename boost::disable_if_c< sizeof(Div_type) <= sizeof(size_t) | |
|| sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type | |
//defaulting to std::sort when integer_sort won't work | |
integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type, | |
Right_shift shift) | |
{ | |
//Warning that we're using std::sort, even though integer_sort was called | |
BOOST_STATIC_WARNING( sizeof(Div_type) <= sizeof(size_t) ); | |
std::sort(first, last); | |
} | |
} | |
} | |
} | |
} | |
#endif |