//Templated spread_sort library
// Copyright Steven J. Ross 2001 - 2009.
// 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/ for updates, documentation, and revision history.
/*
Some improvements suggested by:
Phil Endecott and Frank Gennari
Cygwin fix provided by:
Scott McMurray
*/
/*Boost Software License - Version 1.0 - August 17th, 2003
Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:
The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.*/
#ifndef BOOST_SPREAD_SORT_H
#define BOOST_SPREAD_SORT_H
#include <algorithm>
#include <vector>
#include <cstring>
#ifndef BOOST_SPREADSORT_CONSTANTS
#define BOOST_SPREADSORT_CONSTANTS
namespace boost {
namespace detail {
//Tuning constants
//Sets the minimum number of items per bin.
static const unsigned LOG_MEAN_BIN_SIZE = 2;
//This should be tuned to your processor cache; if you go too large you get cache misses on bins
//The smaller this number, the less worst-case memory usage. If too small, too many recursions slow down spreadsort
static const unsigned MAX_SPLITS = 10;
//Used to force a comparison-based sorting for small bins, if it's faster. Minimum value 0
static const unsigned LOG_MIN_SPLIT_COUNT = 5;
//There is a minimum size below which it is not worth using spreadsort
static const long MIN_SORT_SIZE = 1;
//This is the constant on the log base n of m calculation; make this larger the faster std::sort is relative to spreadsort
static const unsigned LOG_CONST = 2;
}
}
#endif
namespace boost {
namespace detail {
//This only works on unsigned data types
template <typename T>
inline unsigned
rough_log_2_size(const T& input)
{
unsigned result = 0;
//The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
while((input >> result) && (result < (8*sizeof(T)))) ++result;
return result;
}
//Gets the maximum size which we'll call spread_sort on to control worst-case performance
//Maintains both a minimum size to recurse and a check of distribution size versus count
//This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
inline size_t
get_max_count(unsigned log_range, size_t count)
{
unsigned divisor = rough_log_2_size(count);
//Making sure the divisor is positive
if(divisor > LOG_MEAN_BIN_SIZE)
divisor -= LOG_MEAN_BIN_SIZE;
else
divisor = 1;
unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
//Don't try to bitshift more than the size of an element
if((8*sizeof(size_t)) <= relative_width)
relative_width = (8*sizeof(size_t)) - 1;
return 1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?
(LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_width);
}
//Find the minimum and maximum using <
template <class RandomAccessIter>
inline void
find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
{
min = max = current;
//Start from the second item, as max and min are initialized to the first
while(++current < last) {
if(*max < *current)
max = current;
else if(*current < *min)
min = current;
}
}
//Uses a user-defined comparison operator to find minimum and maximum
template <class RandomAccessIter, class compare>
inline void
find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
{
min = max = current;
while(++current < last) {
if(comp(*max, *current))
max = current;
else if(comp(*current, *min))
min = current;
}
}
//Gets a non-negative right bit shift to operate as a logarithmic divisor
inline int
get_log_divisor(size_t count, unsigned log_range)
{
int log_divisor;
//If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
log_divisor = 0;
else {
//otherwise divide the data into an optimized number of pieces
log_divisor += LOG_MEAN_BIN_SIZE;
if(log_divisor < 0)
log_divisor = 0;
//Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
if((log_range - log_divisor) > MAX_SPLITS)
log_divisor = log_range - MAX_SPLITS;
}
return log_divisor;
}
template <class RandomAccessIter>
inline RandomAccessIter *
size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
{
//Assure space for the size of each bin, followed by initializing sizes
if(bin_count > bin_sizes.size())
bin_sizes.resize(bin_count);
for(size_t u = 0; u < bin_count; u++)
bin_sizes[u] = 0;
//Make sure there is space for the bins
cache_end = cache_offset + bin_count;
if(cache_end > bin_cache.size())
bin_cache.resize(cache_end);
return &(bin_cache[cache_offset]);
}
//Implementation for recursive integer sorting
template <class RandomAccessIter, class div_type, class data_type>
inline void
spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<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;
find_extremes(first, last, max, min);
//max and min will be the same (the first item) iff all values are equivalent
if(max == min)
return;
RandomAccessIter * target_bin;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
div_type div_min = *min >> log_divisor;
div_type div_max = *max >> log_divisor;
unsigned bin_count = 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[(*(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];
//Swap into place
//This dominates runtime, mostly in the swap and bin lookups
RandomAccessIter nextbinstart = first;
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 with integers
//The main advantage is less copies are involved per item put in the correct place
data_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;
//Recursing; log_divisor is the remaining range
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
size_t 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
spread_sort_rec<RandomAccessIter, div_type, data_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 data_type, class right_shift>
inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
, const unsigned log_divisor, const div_type div_min)
{
RandomAccessIter * local_bin = bins + ii;
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min)); target_bin != local_bin;
target_bin = bins + (shift(*current, log_divisor) - div_min)) {
data_type tmp;
RandomAccessIter b = (*target_bin)++;
RandomAccessIter * b_bin = bins + (shift(*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 = nextbinstart;
}
//Standard swapping wrapper for ascending values
template <class RandomAccessIter, class div_type, class data_type, class right_shift>
inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
{
nextbinstart += bin_sizes[ii];
inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
}
//Functor implementation for recursive sorting
template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
inline void
spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
{
RandomAccessIter max, min;
find_extremes(first, last, max, min, comp);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
div_type div_min = shift(*min, log_divisor);
div_type div_max = shift(*max, log_divisor);
unsigned bin_count = 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[shift(*(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 u = 0; u < bin_count - 1; ++u)
swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
bins[bin_count - 1] = last;
//If we've bucketsorted, the array is sorted and we should skip recursion
if(!log_divisor)
return;
//Recursing
size_t max_count = get_max_count(log_divisor, last - first);
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
spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
}
}
//Functor implementation for recursive sorting with only Shift overridden
template <class RandomAccessIter, class div_type, class data_type, class right_shift>
inline void
spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes, right_shift shift)
{
RandomAccessIter max, min;
find_extremes(first, last, max, min);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
div_type div_min = shift(*min, log_divisor);
div_type div_max = shift(*max, log_divisor);
unsigned bin_count = 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[shift(*(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, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
bins[bin_count - 1] = last;
//If we've bucketsorted, the array is sorted and we should skip recursion
if(!log_divisor)
return;
//Recursing
size_t max_count = get_max_count(log_divisor, last - first);
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
spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
}
}
//Holds the bin vector and makes the initial recursive call
template <class RandomAccessIter, class div_type, class data_type>
inline void
spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
}
template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
inline void
spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
}
template <class RandomAccessIter, class div_type, class data_type, class right_shift>
inline void
spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
}
}
//Top-level sorting call for integers
template <class RandomAccessIter>
inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
{
//Don't sort if it's too small to optimize
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last);
else
detail::spread_sort(first, last, *first >> 0, *first);
}
//integer_sort with functors
template <class RandomAccessIter, class right_shift, class compare>
inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
right_shift shift, compare comp) {
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last, comp);
else
detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
}
//integer_sort with right_shift functor
template <class RandomAccessIter, class right_shift>
inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
right_shift shift) {
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last);
else
detail::spread_sort(first, last, shift(*first, 0), *first, shift);
}
//------------------------------------------------------ float_sort source --------------------------------------
//Casts a RandomAccessIter to the specified data type
template<class cast_type, class RandomAccessIter>
inline cast_type
cast_float_iter(const RandomAccessIter & floatiter)
{
cast_type result;
std::memcpy(&result, &(*floatiter), sizeof(cast_type));
return result;
}
//Casts a data element to the specified datinner_float_a type
template<class data_type, class cast_type>
inline cast_type
mem_cast(const data_type & data)
{
cast_type result;
std::memcpy(&result, &data, sizeof(cast_type));
return result;
}
namespace detail {
template <class RandomAccessIter, class div_type, class right_shift>
inline void
find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
{
min = max = shift(*current, 0);
while(++current < last) {
div_type value = shift(*current, 0);
if(max < value)
max = value;
else if(value < min)
min = value;
}
}
//Specialized swap loops for floating-point casting
template <class RandomAccessIter, class div_type, class data_type>
inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
, const unsigned log_divisor, const div_type div_min)
{
RandomAccessIter * local_bin = bins + ii;
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin;
target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
data_type tmp;
RandomAccessIter b = (*target_bin)++;
RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(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;
}
else
tmp = *b;
*b = *current;
*current = tmp;
}
}
*local_bin = nextbinstart;
}
template <class RandomAccessIter, class div_type, class data_type>
inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
, const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
{
nextbinstart += bin_sizes[ii];
inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
}
template <class RandomAccessIter, class cast_type>
inline void
find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
{
min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
while(++current < last) {
cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
if(max < value)
max = value;
else if(value < min)
min = value;
}
}
//Special-case sorting of positive floats with casting instead of a right_shift
template <class RandomAccessIter, class div_type, class data_type>
inline void
positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes)
{
div_type max, min;
find_extremes(first, last, max, min);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[(cast_float_iter<div_type, RandomAccessIter>(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 u = 0; u < bin_count - 1; ++u)
float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
bins[bin_count - 1] = last;
//Return if we've completed bucketsorting
if(!log_divisor)
return;
//Recursing
size_t max_count = get_max_count(log_divisor, last - first);
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
positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
}
}
//Sorting negative_ float_s
//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
template <class RandomAccessIter, class div_type, class data_type>
inline void
negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes)
{
div_type max, min;
find_extremes(first, last, max, min);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
bins[bin_count - 1] = first;
for(int ii = bin_count - 2; ii >= 0; --ii)
bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
//Swap into place
RandomAccessIter nextbinstart = first;
//The last bin will always have the correct elements in it
for(int ii = bin_count - 1; ii > 0; --ii)
float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
//Since we don't process the last bin, we need to update its end position
bin_cache[cache_offset] = last;
//Return if we've completed bucketsorting
if(!log_divisor)
return;
//Recursing
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
size_t count = bin_cache[ii] - lastPos;
if(count < 2)
continue;
if(count < max_count)
std::sort(lastPos, bin_cache[ii]);
else
negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
}
}
//Sorting negative_ float_s
//Note that bins are iterated in reverse order because max_neg_float = min_neg_int
template <class RandomAccessIter, class div_type, class data_type, class right_shift>
inline void
negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes, right_shift shift)
{
div_type max, min;
find_extremes(first, last, max, min, shift);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[shift(*(current++), log_divisor) - div_min]++;
bins[bin_count - 1] = first;
for(int ii = bin_count - 2; ii >= 0; --ii)
bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
//Swap into place
RandomAccessIter nextbinstart = first;
//The last bin will always have the correct elements in it
for(int ii = bin_count - 1; ii > 0; --ii)
swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
//Since we don't process the last bin, we need to update its end position
bin_cache[cache_offset] = last;
//Return if we've completed bucketsorting
if(!log_divisor)
return;
//Recursing
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
size_t count = bin_cache[ii] - lastPos;
if(count < 2)
continue;
if(count < max_count)
std::sort(lastPos, bin_cache[ii]);
else
negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
}
}
template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
inline void
negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
{
div_type max, min;
find_extremes(first, last, max, min, shift);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[shift(*(current++), log_divisor) - div_min]++;
bins[bin_count - 1] = first;
for(int ii = bin_count - 2; ii >= 0; --ii)
bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
//Swap into place
RandomAccessIter nextbinstart = first;
//The last bin will always have the correct elements in it
for(int ii = bin_count - 1; ii > 0; --ii)
swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
//Since we don't process the last bin, we need to update its end position
bin_cache[cache_offset] = last;
//Return if we've completed bucketsorting
if(!log_divisor)
return;
//Recursing
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
size_t count = bin_cache[ii] - lastPos;
if(count < 2)
continue;
if(count < max_count)
std::sort(lastPos, bin_cache[ii], comp);
else
negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
}
}
//Casting special-case for floating-point sorting
template <class RandomAccessIter, class div_type, class data_type>
inline void
float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes)
{
div_type max, min;
find_extremes(first, last, max, min);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
//The index of the first positive bin
div_type first_positive = (div_min < 0) ? -div_min : 0;
//Resetting if all bins are negative
if(cache_offset + first_positive > cache_end)
first_positive = cache_end - cache_offset;
//Reversing the order of the negative bins
//Note that because of the negative/positive ordering direction flip
//We can not depend upon bin order and positions matching up
//so bin_sizes must be reused to contain the end of the bin
if(first_positive > 0) {
bins[first_positive - 1] = first;
for(int ii = first_positive - 2; ii >= 0; --ii) {
bins[ii] = first + bin_sizes[ii + 1];
bin_sizes[ii] += bin_sizes[ii + 1];
}
//Handling positives following negatives
if((unsigned)first_positive < bin_count) {
bins[first_positive] = first + bin_sizes[0];
bin_sizes[first_positive] += bin_sizes[0];
}
}
else
bins[0] = first;
for(unsigned u = first_positive; u < bin_count - 1; u++) {
bins[u + 1] = first + bin_sizes[u];
bin_sizes[u + 1] += bin_sizes[u];
}
//Swap into place
RandomAccessIter nextbinstart = first;
for(unsigned u = 0; u < bin_count; ++u) {
nextbinstart = first + bin_sizes[u];
inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
}
if(!log_divisor)
return;
//Handling negative values first
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
size_t count = bin_cache[ii] - lastPos;
if(count < 2)
continue;
if(count < max_count)
std::sort(lastPos, bin_cache[ii]);
//sort negative values using reversed-bin spread_sort
else
negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
}
for(unsigned u = cache_offset + first_positive; 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]);
//sort positive values using normal spread_sort
else
positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
}
}
//Functor implementation for recursive sorting
template <class RandomAccessIter, class div_type, class data_type, class right_shift>
inline void
float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes, right_shift shift)
{
div_type max, min;
find_extremes(first, last, max, min, shift);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[shift(*(current++), log_divisor) - div_min]++;
//The index of the first positive bin
div_type first_positive = (div_min < 0) ? -div_min : 0;
//Resetting if all bins are negative
if(cache_offset + first_positive > cache_end)
first_positive = cache_end - cache_offset;
//Reversing the order of the negative bins
//Note that because of the negative/positive ordering direction flip
//We can not depend upon bin order and positions matching up
//so bin_sizes must be reused to contain the end of the bin
if(first_positive > 0) {
bins[first_positive - 1] = first;
for(int ii = first_positive - 2; ii >= 0; --ii) {
bins[ii] = first + bin_sizes[ii + 1];
bin_sizes[ii] += bin_sizes[ii + 1];
}
//Handling positives following negatives
if((unsigned)first_positive < bin_count) {
bins[first_positive] = first + bin_sizes[0];
bin_sizes[first_positive] += bin_sizes[0];
}
}
else
bins[0] = first;
for(unsigned u = first_positive; u < bin_count - 1; u++) {
bins[u + 1] = first + bin_sizes[u];
bin_sizes[u + 1] += bin_sizes[u];
}
//Swap into place
RandomAccessIter nextbinstart = first;
for(unsigned u = 0; u < bin_count; ++u) {
nextbinstart = first + bin_sizes[u];
inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
}
//Return if we've completed bucketsorting
if(!log_divisor)
return;
//Handling negative values first
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
size_t count = bin_cache[ii] - lastPos;
if(count < 2)
continue;
if(count < max_count)
std::sort(lastPos, bin_cache[ii]);
//sort negative values using reversed-bin spread_sort
else
negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
}
for(unsigned u = cache_offset + first_positive; 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]);
//sort positive values using normal spread_sort
else
spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
}
}
template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
inline void
float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
, std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
{
div_type max, min;
find_extremes(first, last, max, min, shift);
if(max == min)
return;
unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
div_type div_min = min >> log_divisor;
div_type div_max = max >> log_divisor;
unsigned bin_count = 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[shift(*(current++), log_divisor) - div_min]++;
//The index of the first positive bin
div_type first_positive = (div_min < 0) ? -div_min : 0;
//Resetting if all bins are negative
if(cache_offset + first_positive > cache_end)
first_positive = cache_end - cache_offset;
//Reversing the order of the negative bins
//Note that because of the negative/positive ordering direction flip
//We can not depend upon bin order and positions matching up
//so bin_sizes must be reused to contain the end of the bin
if(first_positive > 0) {
bins[first_positive - 1] = first;
for(int ii = first_positive - 2; ii >= 0; --ii) {
bins[ii] = first + bin_sizes[ii + 1];
bin_sizes[ii] += bin_sizes[ii + 1];
}
//Handling positives following negatives
if((unsigned)first_positive < bin_count) {
bins[first_positive] = first + bin_sizes[0];
bin_sizes[first_positive] += bin_sizes[0];
}
}
else
bins[0] = first;
for(unsigned u = first_positive; u < bin_count - 1; u++) {
bins[u + 1] = first + bin_sizes[u];
bin_sizes[u + 1] += bin_sizes[u];
}
//Swap into place
RandomAccessIter nextbinstart = first;
for(unsigned u = 0; u < bin_count; ++u) {
nextbinstart = first + bin_sizes[u];
inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
}
//Return if we've completed bucketsorting
if(!log_divisor)
return;
//Handling negative values first
size_t max_count = get_max_count(log_divisor, last - first);
RandomAccessIter lastPos = first;
for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
size_t count = bin_cache[ii] - lastPos;
if(count < 2)
continue;
if(count < max_count)
std::sort(lastPos, bin_cache[ii]);
//sort negative values using reversed-bin spread_sort
else
negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
}
for(unsigned u = cache_offset + first_positive; 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]);
//sort positive values using normal spread_sort
else
spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
}
}
template <class RandomAccessIter, class cast_type, class data_type>
inline void
float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
}
template <class RandomAccessIter, class div_type, class data_type, class right_shift>
inline void
float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
}
template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
inline void
float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
}
}
//float_sort with casting
//The cast_type must be equal in size to the data type, and must be a signed integer
template <class RandomAccessIter, class cast_type>
inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal)
{
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last);
else
detail::float_Sort(first, last, cVal, *first);
}
//float_sort with casting to an int
//Only use this with IEEE floating-point numbers
template <class RandomAccessIter>
inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last)
{
int cVal = 0;
float_sort_cast(first, last, cVal);
}
//float_sort with functors
template <class RandomAccessIter, class right_shift>
inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift)
{
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last);
else
detail::float_Sort(first, last, shift(*first, 0), *first, shift);
}
template <class RandomAccessIter, class right_shift, class compare>
inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp)
{
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last, comp);
else
detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
}
//------------------------------------------------- string_sort source ---------------------------------------------
namespace detail {
//Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
template<class RandomAccessIter>
inline void
update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
{
unsigned nextOffset = char_offset;
bool done = false;
while(!done) {
RandomAccessIter curr = first;
do {
//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
done = true;
break;
}
} while(++curr != finish);
if(!done)
++nextOffset;
}
char_offset = nextOffset;
}
//Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
template<class RandomAccessIter, class get_char, class get_length>
inline void
update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
{
unsigned nextOffset = char_offset;
bool done = false;
while(!done) {
RandomAccessIter curr = first;
do {
//ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
done = true;
break;
}
} while(++curr != finish);
if(!done)
++nextOffset;
}
char_offset = nextOffset;
}
//A comparison functor for strings that assumes they are identical up to char_offset
template<class data_type, class unsignedchar_type>
struct offset_lessthan {
offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
inline bool operator()(const data_type &x, const data_type &y) const
{
unsigned minSize = std::min(x.size(), y.size());
for(unsigned u = fchar_offset; u < minSize; ++u) {
if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
return true;
else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
return false;
}
return x.size() < y.size();
}
unsigned fchar_offset;
};
//A comparison functor for strings that assumes they are identical up to char_offset
template<class data_type, class unsignedchar_type>
struct offset_greaterthan {
offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
inline bool operator()(const data_type &x, const data_type &y) const
{
unsigned minSize = std::min(x.size(), y.size());
for(unsigned u = fchar_offset; u < minSize; ++u) {
if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
return true;
else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
return false;
}
return x.size() > y.size();
}
unsigned fchar_offset;
};
//A comparison functor for strings that assumes they are identical up to char_offset
template<class data_type, class get_char, class get_length>
struct offset_char_lessthan {
offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
inline bool operator()(const data_type &x, const data_type &y) const
{
unsigned minSize = std::min(length(x), length(y));
for(unsigned u = fchar_offset; u < minSize; ++u) {
if(getchar(x, u) < getchar(y, u))
return true;
else if(getchar(y, u) < getchar(x, u))
return false;
}
return length(x) < length(y);
}
unsigned fchar_offset;
get_char getchar;
get_length length;
};
//String sorting recursive implementation
template <class RandomAccessIter, class data_type, class unsignedchar_type>
inline void
string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
, unsigned cache_offset, std::vector<size_t> &bin_sizes)
{
//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
//Iterate to the end of the empties. If all empty, return
while((*first).size() <= char_offset) {
if(++first == last)
return;
}
RandomAccessIter finish = last - 1;
//Getting the last non-empty
for(;(*finish).size() <= char_offset; --finish);
++finish;
//Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
update_offset(first, finish, char_offset);
const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
const unsigned max_size = bin_count;
const unsigned membin_count = bin_count + 1;
unsigned cache_end;
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
//Calculating the size of each bin; this takes roughly 10% of runtime
for (RandomAccessIter current = first; current != last; ++current) {
if((*current).size() <= char_offset) {
bin_sizes[0]++;
}
else
bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
}
//Assign the bin positions
bin_cache[cache_offset] = first;
for(unsigned u = 0; u < membin_count - 1; u++)
bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
//Swap into place
RandomAccessIter nextbinstart = first;
//handling empty bins
RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
nextbinstart += bin_sizes[0];
RandomAccessIter * target_bin;
//Iterating over each element in the bin of empties
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
//empties belong in this bin
while((*current).size() > char_offset) {
target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
iter_swap(current, (*target_bin)++);
}
}
*local_bin = nextbinstart;
//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
unsigned last_bin = bin_count - 1;
for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin);
//This dominates runtime, mostly in the swap and bin lookups
for(unsigned u = 0; u < last_bin; ++u) {
local_bin = bins + u;
nextbinstart += bin_sizes[u + 1];
//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 + static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
iter_swap(current, (*target_bin)++);
}
*local_bin = nextbinstart;
}
bins[last_bin] = last;
//Recursing
RandomAccessIter lastPos = bin_cache[cache_offset];
//Skip this loop for empties
for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
size_t 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_size)
std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
else
string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
}
}
//Sorts strings in reverse order, with empties at the end
template <class RandomAccessIter, class data_type, class unsignedchar_type>
inline void
reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
, unsigned cache_offset, std::vector<size_t> &bin_sizes)
{
//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
RandomAccessIter curr = first;
//Iterate to the end of the empties. If all empty, return
while((*curr).size() <= char_offset) {
if(++curr == last)
return;
}
//Getting the last non-empty
while((*(--last)).size() <= char_offset);
++last;
//Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
update_offset(curr, last, char_offset);
RandomAccessIter * target_bin;
const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
const unsigned max_size = bin_count;
const unsigned membin_count = bin_count + 1;
const unsigned max_bin = bin_count - 1;
unsigned cache_end;
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
//Calculating the size of each bin; this takes roughly 10% of runtime
for (RandomAccessIter current = first; current != last; ++current) {
if((*current).size() <= char_offset) {
bin_sizes[bin_count]++;
}
else
bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
}
//Assign the bin positions
bin_cache[cache_offset] = first;
for(unsigned u = 0; u < membin_count - 1; u++)
bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
//Swap into place
RandomAccessIter nextbinstart = last;
//handling empty bins
RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
RandomAccessIter lastFull = *local_bin;
//Iterating over each element in the bin of empties
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
//empties belong in this bin
while((*current).size() > char_offset) {
target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
iter_swap(current, (*target_bin)++);
}
}
*local_bin = nextbinstart;
nextbinstart = first;
//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
unsigned last_bin = max_bin;
for(; last_bin && !bin_sizes[last_bin]; --last_bin);
//This dominates runtime, mostly in the swap and bin lookups
for(unsigned u = 0; u < last_bin; ++u) {
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 = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
iter_swap(current, (*target_bin)++);
}
*local_bin = nextbinstart;
}
bins[last_bin] = lastFull;
//Recursing
RandomAccessIter lastPos = first;
//Skip this loop for empties
for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
size_t 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_size)
std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
else
reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
}
}
//String sorting recursive implementation
template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
inline void
string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
{
//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
//Iterate to the end of the empties. If all empty, return
while(length(*first) <= char_offset) {
if(++first == last)
return;
}
RandomAccessIter finish = last - 1;
//Getting the last non-empty
for(;length(*finish) <= char_offset; --finish);
++finish;
update_offset(first, finish, char_offset, getchar, length);
const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
const unsigned max_size = bin_count;
const unsigned membin_count = bin_count + 1;
unsigned cache_end;
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
//Calculating the size of each bin; this takes roughly 10% of runtime
for (RandomAccessIter current = first; current != last; ++current) {
if(length(*current) <= char_offset) {
bin_sizes[0]++;
}
else
bin_sizes[getchar((*current), char_offset) + 1]++;
}
//Assign the bin positions
bin_cache[cache_offset] = first;
for(unsigned u = 0; u < membin_count - 1; u++)
bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
//Swap into place
RandomAccessIter nextbinstart = first;
//handling empty bins
RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
nextbinstart += bin_sizes[0];
RandomAccessIter * target_bin;
//Iterating over each element in the bin of empties
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
//empties belong in this bin
while(length(*current) > char_offset) {
target_bin = bins + getchar((*current), char_offset);
iter_swap(current, (*target_bin)++);
}
}
*local_bin = nextbinstart;
//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
unsigned last_bin = bin_count - 1;
for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin);
//This dominates runtime, mostly in the swap and bin lookups
for(unsigned ii = 0; ii < last_bin; ++ii) {
local_bin = bins + ii;
nextbinstart += bin_sizes[ii + 1];
//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 + getchar((*current), char_offset); target_bin != local_bin;
target_bin = bins + getchar((*current), char_offset))
iter_swap(current, (*target_bin)++);
}
*local_bin = nextbinstart;
}
bins[last_bin] = last;
//Recursing
RandomAccessIter lastPos = bin_cache[cache_offset];
//Skip this loop for empties
for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
size_t 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_size)
std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
else
string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
}
}
//String sorting recursive implementation
template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
inline void
string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
{
//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
//Iterate to the end of the empties. If all empty, return
while(length(*first) <= char_offset) {
if(++first == last)
return;
}
RandomAccessIter finish = last - 1;
//Getting the last non-empty
for(;length(*finish) <= char_offset; --finish);
++finish;
update_offset(first, finish, char_offset, getchar, length);
const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
const unsigned max_size = bin_count;
const unsigned membin_count = bin_count + 1;
unsigned cache_end;
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
//Calculating the size of each bin; this takes roughly 10% of runtime
for (RandomAccessIter current = first; current != last; ++current) {
if(length(*current) <= char_offset) {
bin_sizes[0]++;
}
else
bin_sizes[getchar((*current), char_offset) + 1]++;
}
//Assign the bin positions
bin_cache[cache_offset] = first;
for(unsigned u = 0; u < membin_count - 1; u++)
bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
//Swap into place
RandomAccessIter nextbinstart = first;
//handling empty bins
RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
nextbinstart += bin_sizes[0];
RandomAccessIter * target_bin;
//Iterating over each element in the bin of empties
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
//empties belong in this bin
while(length(*current) > char_offset) {
target_bin = bins + getchar((*current), char_offset);
iter_swap(current, (*target_bin)++);
}
}
*local_bin = nextbinstart;
//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
unsigned last_bin = bin_count - 1;
for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin);
//This dominates runtime, mostly in the swap and bin lookups
for(unsigned u = 0; u < last_bin; ++u) {
local_bin = bins + u;
nextbinstart += bin_sizes[u + 1];
//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 + getchar((*current), char_offset); target_bin != local_bin;
target_bin = bins + getchar((*current), char_offset))
iter_swap(current, (*target_bin)++);
}
*local_bin = nextbinstart;
}
bins[last_bin] = last;
//Recursing
RandomAccessIter lastPos = bin_cache[cache_offset];
//Skip this loop for empties
for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
size_t 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_size)
std::sort(lastPos, bin_cache[u], comp);
else
string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
}
}
//Sorts strings in reverse order, with empties at the end
template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
inline void
reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
, unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
{
//This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
RandomAccessIter curr = first;
//Iterate to the end of the empties. If all empty, return
while(length(*curr) <= char_offset) {
if(++curr == last)
return;
}
//Getting the last non-empty
while(length(*(--last)) <= char_offset);
++last;
//Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
update_offset(first, last, char_offset, getchar, length);
const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
//Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
const unsigned max_size = bin_count;
const unsigned membin_count = bin_count + 1;
const unsigned max_bin = bin_count - 1;
unsigned cache_end;
RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
//Calculating the size of each bin; this takes roughly 10% of runtime
for (RandomAccessIter current = first; current != last; ++current) {
if(length(*current) <= char_offset) {
bin_sizes[bin_count]++;
}
else
bin_sizes[max_bin - getchar((*current), char_offset)]++;
}
//Assign the bin positions
bin_cache[cache_offset] = first;
for(unsigned u = 0; u < membin_count - 1; u++)
bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
//Swap into place
RandomAccessIter nextbinstart = last;
//handling empty bins
RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
RandomAccessIter lastFull = *local_bin;
RandomAccessIter * target_bin;
//Iterating over each element in the bin of empties
for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
//empties belong in this bin
while(length(*current) > char_offset) {
target_bin = end_bin - getchar((*current), char_offset);
iter_swap(current, (*target_bin)++);
}
}
*local_bin = nextbinstart;
nextbinstart = first;
//iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
unsigned last_bin = max_bin;
for(; last_bin && !bin_sizes[last_bin]; --last_bin);
//This dominates runtime, mostly in the swap and bin lookups
for(unsigned u = 0; u < last_bin; ++u) {
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 = end_bin - getchar((*current), char_offset); target_bin != local_bin;
target_bin = end_bin - getchar((*current), char_offset))
iter_swap(current, (*target_bin)++);
}
*local_bin = nextbinstart;
}
bins[last_bin] = lastFull;
//Recursing
RandomAccessIter lastPos = first;
//Skip this loop for empties
for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
size_t 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_size)
std::sort(lastPos, bin_cache[u], comp);
else
reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
}
}
//Holds the bin vector and makes the initial recursive call
template <class RandomAccessIter, class data_type, class unsignedchar_type>
inline void
string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
}
//Holds the bin vector and makes the initial recursive call
template <class RandomAccessIter, class data_type, class unsignedchar_type>
inline void
reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
}
//Holds the bin vector and makes the initial recursive call
template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
inline void
string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
}
//Holds the bin vector and makes the initial recursive call
template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
inline void
string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
}
//Holds the bin vector and makes the initial recursive call
template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
inline void
reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
{
std::vector<size_t> bin_sizes;
std::vector<RandomAccessIter> bin_cache;
reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
}
}
//Allows character-type overloads
template <class RandomAccessIter, class unsignedchar_type>
inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused)
{
//Don't sort if it's too small to optimize
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last);
else
detail::string_sort(first, last, *first, unused);
}
//Top-level sorting call; wraps using default of unsigned char
template <class RandomAccessIter>
inline void string_sort(RandomAccessIter first, RandomAccessIter last)
{
unsigned char unused = '\0';
string_sort(first, last, unused);
}
//Allows character-type overloads
template <class RandomAccessIter, class compare, class unsignedchar_type>
inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused)
{
//Don't sort if it's too small to optimize
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last, comp);
else
detail::reverse_string_sort(first, last, *first, unused);
}
//Top-level sorting call; wraps using default of unsigned char
template <class RandomAccessIter, class compare>
inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp)
{
unsigned char unused = '\0';
reverse_string_sort(first, last, comp, unused);
}
template <class RandomAccessIter, class get_char, class get_length>
inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length)
{
//Don't sort if it's too small to optimize
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last);
else {
//skipping past empties at the beginning, which allows us to get the character type
//.empty() is not used so as not to require a user declaration of it
while(!length(*first)) {
if(++first == last)
return;
}
detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
}
}
template <class RandomAccessIter, class get_char, class get_length, class compare>
inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
{
//Don't sort if it's too small to optimize
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last, comp);
else {
//skipping past empties at the beginning, which allows us to get the character type
//.empty() is not used so as not to require a user declaration of it
while(!length(*first)) {
if(++first == last)
return;
}
detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
}
}
template <class RandomAccessIter, class get_char, class get_length, class compare>
inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
{
//Don't sort if it's too small to optimize
if(last - first < detail::MIN_SORT_SIZE)
std::sort(first, last, comp);
else {
//skipping past empties at the beginning, which allows us to get the character type
//.empty() is not used so as not to require a user declaration of it
while(!length(*(--last))) {
//Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
if(first == last)
return;
}
//making last just after the end of the non-empty part of the array
++last;
detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
}
}
}
#endif
#include <fstream>
using namespace std;
#define DIM 500005
int main ()
{
ifstream fin ("algsort.in");
ofstream fout ("algsort.out");
int v[DIM];
int N,i;
fin>>N;
for (i=1; i<=N; ++i)
fin>>v[i];
boost::integer_sort (v+1,v+N+1);
for (i=1; i<=N; ++i)
fout<<v[i]<<" ";
return 0;
}
Dragos Oprica DraStiK