1e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent//Templated spread_sort library 2e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 3e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent// Copyright Steven J. Ross 2001 - 2009. 4e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent// Distributed under the Boost Software License, Version 1.0. 5e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent// (See accompanying file LICENSE_1_0.txt or copy at 6e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent// http://www.boost.org/LICENSE_1_0.txt) 7e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 8e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent// See http://www.boost.org/ for updates, documentation, and revision history. 9e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 10e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent/* 11e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric LaurentSome improvements suggested by: 12e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric LaurentPhil Endecott and Frank Gennari 13e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric LaurentCygwin fix provided by: 14e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric LaurentScott McMurray 15e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent*/ 16e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 17e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#ifndef BOOST_SPREAD_SORT_H 18e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#define BOOST_SPREAD_SORT_H 19e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#include <algorithm> 20e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#include <vector> 21e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#include "constants.hpp" 22e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#include <cstring> 23e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 24e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurentnamespace boost { 25e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent namespace detail { 26e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This only works on unsigned data types 27e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <typename T> 28e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline unsigned 29e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent rough_log_2_size(const T& input) 30e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 31e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned result = 0; 32e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance 33e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while((input >> result) && (result < (8*sizeof(T)))) ++result; 34e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return result; 35e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 36e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 37e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Gets the maximum size which we'll call spread_sort on to control worst-case performance 38e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Maintains both a minimum size to recurse and a check of distribution size versus count 39e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead 40e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline size_t 41e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent get_max_count(unsigned log_range, size_t count) 42e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 43e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned divisor = rough_log_2_size(count); 44e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Making sure the divisor is positive 45e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(divisor > LOG_MEAN_BIN_SIZE) 46e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent divisor -= LOG_MEAN_BIN_SIZE; 47e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 48e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent divisor = 1; 49e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor); 50e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't try to bitshift more than the size of an element 51e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((8*sizeof(size_t)) <= relative_width) 52e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent relative_width = (8*sizeof(size_t)) - 1; 53e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ? 54e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_width); 55e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 56e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 57e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Find the minimum and maximum using < 58e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter> 59e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 60e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min) 61e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 62e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = max = current; 63e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Start from the second item, as max and min are initialized to the first 64e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(++current < last) { 65e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(*max < *current) 66e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent max = current; 67e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(*current < *min) 68e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = current; 69e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 70e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 71e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 72e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Uses a user-defined comparison operator to find minimum and maximum 73e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class compare> 74e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 75e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp) 76e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 77e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = max = current; 78e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(++current < last) { 79e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(comp(*max, *current)) 80e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent max = current; 81e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(comp(*current, *min)) 82e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = current; 83e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 84e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 85e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 86e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Gets a non-negative right bit shift to operate as a logarithmic divisor 87e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline int 88e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent get_log_divisor(size_t count, unsigned log_range) 89e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 90e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent int log_divisor; 91e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so 92e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS) 93e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent log_divisor = 0; 94e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else { 95e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //otherwise divide the data into an optimized number of pieces 96e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent log_divisor += LOG_MEAN_BIN_SIZE; 97e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(log_divisor < 0) 98e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent log_divisor = 0; 99e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically 100e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((log_range - log_divisor) > MAX_SPLITS) 101e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent log_divisor = log_range - MAX_SPLITS; 102e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 103e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return log_divisor; 104e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 105e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 106e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter> 107e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline RandomAccessIter * 108e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count) 109e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 110e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assure space for the size of each bin, followed by initializing sizes 111e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(bin_count > bin_sizes.size()) 112e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes.resize(bin_count); 113e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(size_t u = 0; u < bin_count; u++) 114e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[u] = 0; 115e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Make sure there is space for the bins 116e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent cache_end = cache_offset + bin_count; 117e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(cache_end > bin_cache.size()) 118e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache.resize(cache_end); 119e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return &(bin_cache[cache_offset]); 120e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 121e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 122e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Implementation for recursive integer sorting 123e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 124e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 125e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 126e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes) 127e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 128e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data 129e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration 130e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter max, min; 131e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min); 132e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //max and min will be the same (the first item) iff all values are equivalent 133e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 134e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 135e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * target_bin; 136e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0))); 137e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = *min >> log_divisor; 138e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = *max >> log_divisor; 139e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 140e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 141e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 142e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 143e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin; this takes roughly 10% of runtime 144e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 145e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[(*(current++) >> log_divisor) - div_min]++; 146e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assign the bin positions 147e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 148e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; u++) 149e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = bins[u] + bin_sizes[u]; 150e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 151e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 152e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This dominates runtime, mostly in the swap and bin lookups 153e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 154e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; ++u) { 155e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = bins + u; 156e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[u]; 157e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in this bin 158e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 159e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swapping elements in current into place until the correct element has been swapped in 160e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(target_bin = (bins + ((*current >> log_divisor) - div_min)); target_bin != local_bin; 161e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + ((*current >> log_divisor) - div_min)) { 162e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //3-way swap; this is about 1% faster than a 2-way swap with integers 163e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The main advantage is less copies are involved per item put in the correct place 164e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent data_type tmp; 165e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter b = (*target_bin)++; 166e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min); 167e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if (b_bin != local_bin) { 168e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter c = (*b_bin)++; 169e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent tmp = *c; 170e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *c = *b; 171e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 172e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 173e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent tmp = *b; 174e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *b = *current; 175e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *current = tmp; 176e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 177e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 178e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 179e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 180e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = last; 181e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 182e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //If we've bucketsorted, the array is sorted and we should skip recursion 183e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 184e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 185e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 186e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing; log_divisor is the remaining range 187e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 188e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 189e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) { 190e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 191e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //don't sort unless there are at least two items to compare 192e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 193e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 194e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //using std::sort if its worst-case is better 195e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 196e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u]); 197e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 198e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes); 199e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 200e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 201e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 202e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Generic bitshift-based 3-way swapping code 203e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 204e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift 205e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , const unsigned log_divisor, const div_type div_min) 206e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 207e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = bins + ii; 208e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 209e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min)); target_bin != local_bin; 210e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + (shift(*current, log_divisor) - div_min)) { 211e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent data_type tmp; 212e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter b = (*target_bin)++; 213e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min); 214e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs 215e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if (b_bin != local_bin) { 216e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter c = (*b_bin)++; 217e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent tmp = *c; 218e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *c = *b; 219e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 220e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note: we could increment current once the swap is done in this case, but that seems to impair performance 221e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 222e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent tmp = *b; 223e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *b = *current; 224e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *current = tmp; 225e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 226e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 227e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 228e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 229e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 230e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Standard swapping wrapper for ascending values 231e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 232e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift 233e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 234e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 235e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[ii]; 236e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min); 237e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 238e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 239e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Functor implementation for recursive sorting 240e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare> 241e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 242e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 243e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes, right_shift shift, compare comp) 244e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 245e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter max, min; 246e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min, comp); 247e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 248e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 249e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0)))); 250e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = shift(*min, log_divisor); 251e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = shift(*max, log_divisor); 252e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 253e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 254e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 255e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 256e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 257e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 258e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[shift(*(current++), log_divisor) - div_min]++; 259e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 260e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; u++) 261e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = bins[u] + bin_sizes[u]; 262e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 263e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 264e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 265e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; ++u) 266e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min); 267e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = last; 268e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 269e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //If we've bucketsorted, the array is sorted and we should skip recursion 270e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 271e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 272e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 273e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 274e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 275e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 276e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) { 277e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 278e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 279e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 280e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 281e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u], comp); 282e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 283e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp); 284e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 285e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 286e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 287e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Functor implementation for recursive sorting with only Shift overridden 288e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 289e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 290e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 291e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes, right_shift shift) 292e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 293e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter max, min; 294e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min); 295e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 296e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 297e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0)))); 298e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = shift(*min, log_divisor); 299e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = shift(*max, log_divisor); 300e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 301e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 302e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 303e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 304e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 305e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 306e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[shift(*(current++), log_divisor) - div_min]++; 307e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 308e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; u++) 309e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = bins[u] + bin_sizes[u]; 310e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 311e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 312e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 313e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned ii = 0; ii < bin_count - 1; ++ii) 314e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min); 315e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = last; 316e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 317e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //If we've bucketsorted, the array is sorted and we should skip recursion 318e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 319e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 320e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 321e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 322e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 323e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 324e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) { 325e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 326e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 327e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 328e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 329e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u]); 330e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 331e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift); 332e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 333e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 334e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 335e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Holds the bin vector and makes the initial recursive call 336e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 337e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 338e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type) 339e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 340e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 341e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 342e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes); 343e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 344e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 345e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare> 346e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 347e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp) 348e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 349e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 350e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 351e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp); 352e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 353e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 354e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 355e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 356e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift) 357e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 358e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 359e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 360e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift); 361e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 362e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 363e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 364e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Top-level sorting call for integers 365e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter> 366e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void integer_sort(RandomAccessIter first, RandomAccessIter last) 367e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 368e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't sort if it's too small to optimize 369e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 370e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last); 371e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 372e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::spread_sort(first, last, *first >> 0, *first); 373e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 374e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 375e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //integer_sort with functors 376e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class right_shift, class compare> 377e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void integer_sort(RandomAccessIter first, RandomAccessIter last, 378e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent right_shift shift, compare comp) { 379e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 380e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last, comp); 381e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 382e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp); 383e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 384e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 385e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //integer_sort with right_shift functor 386e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class right_shift> 387e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void integer_sort(RandomAccessIter first, RandomAccessIter last, 388e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent right_shift shift) { 389e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 390e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last); 391e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 392e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::spread_sort(first, last, shift(*first, 0), *first, shift); 393e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 394e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 395e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //------------------------------------------------------ float_sort source -------------------------------------- 396e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Casts a RandomAccessIter to the specified data type 397e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class cast_type, class RandomAccessIter> 398e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline cast_type 399e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent cast_float_iter(const RandomAccessIter & floatiter) 400e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 401e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent cast_type result; 402e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::memcpy(&result, &(*floatiter), sizeof(cast_type)); 403e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return result; 404e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 405e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 406e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Casts a data element to the specified datinner_float_a type 407e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class data_type, class cast_type> 408e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline cast_type 409e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent mem_cast(const data_type & data) 410e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 411e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent cast_type result; 412e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::memcpy(&result, &data, sizeof(cast_type)); 413e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return result; 414e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 415e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 416e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent namespace detail { 417e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class right_shift> 418e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 419e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift) 420e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 421e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = max = shift(*current, 0); 422e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(++current < last) { 423e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type value = shift(*current, 0); 424e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max < value) 425e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent max = value; 426e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(value < min) 427e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = value; 428e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 429e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 430e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 431e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Specialized swap loops for floating-point casting 432e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 433e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii 434e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , const unsigned log_divisor, const div_type div_min) 435e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 436e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = bins + ii; 437e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 438e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin; 439e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) { 440e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent data_type tmp; 441e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter b = (*target_bin)++; 442e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min); 443e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs 444e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if (b_bin != local_bin) { 445e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter c = (*b_bin)++; 446e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent tmp = *c; 447e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *c = *b; 448e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 449e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 450e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent tmp = *b; 451e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *b = *current; 452e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *current = tmp; 453e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 454e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 455e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 456e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 457e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 458e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 459e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii 460e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min) 461e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 462e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[ii]; 463e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min); 464e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 465e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 466e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class cast_type> 467e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 468e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min) 469e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 470e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = max = cast_float_iter<cast_type, RandomAccessIter>(current); 471e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(++current < last) { 472e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current); 473e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max < value) 474e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent max = value; 475e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(value < min) 476e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent min = value; 477e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 478e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 479e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 480e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Special-case sorting of positive floats with casting instead of a right_shift 481e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 482e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 483e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 484e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes) 485e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 486e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 487e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min); 488e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 489e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 490e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 491e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 492e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 493e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 494e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 495e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 496e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 497e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 498e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 499e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++; 500e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 501e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; u++) 502e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = bins[u] + bin_sizes[u]; 503e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 504e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 505e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 506e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count - 1; ++u) 507e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min); 508e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = last; 509e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 510e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Return if we've completed bucketsorting 511e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 512e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 513e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 514e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 515e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 516e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 517e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) { 518e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 519e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 520e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 521e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 522e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u]); 523e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 524e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes); 525e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 526e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 527e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 528e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Sorting negative_ float_s 529e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note that bins are iterated in reverse order because max_neg_float = min_neg_int 530e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 531e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 532e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 533e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes) 534e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 535e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 536e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min); 537e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 538e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 539e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 540e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 541e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 542e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 543e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 544e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 545e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 546e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 547e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 548e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++; 549e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = first; 550e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = bin_count - 2; ii >= 0; --ii) 551e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[ii] = bins[ii + 1] + bin_sizes[ii + 1]; 552e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 553e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 554e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 555e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The last bin will always have the correct elements in it 556e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = bin_count - 1; ii > 0; --ii) 557e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min); 558e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Since we don't process the last bin, we need to update its end position 559e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = last; 560e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 561e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Return if we've completed bucketsorting 562e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 563e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 564e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 565e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 566e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 567e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 568e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) { 569e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[ii] - lastPos; 570e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 571e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 572e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 573e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[ii]); 574e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 575e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes); 576e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 577e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 578e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 579e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Sorting negative_ float_s 580e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note that bins are iterated in reverse order because max_neg_float = min_neg_int 581e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 582e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 583e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 584e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes, right_shift shift) 585e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 586e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 587e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min, shift); 588e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 589e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 590e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 591e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 592e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 593e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 594e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 595e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 596e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 597e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 598e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 599e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[shift(*(current++), log_divisor) - div_min]++; 600e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = first; 601e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = bin_count - 2; ii >= 0; --ii) 602e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[ii] = bins[ii + 1] + bin_sizes[ii + 1]; 603e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 604e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 605e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 606e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The last bin will always have the correct elements in it 607e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = bin_count - 1; ii > 0; --ii) 608e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min); 609e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Since we don't process the last bin, we need to update its end position 610e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = last; 611e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 612e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Return if we've completed bucketsorting 613e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 614e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 615e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 616e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 617e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 618e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 619e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) { 620e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[ii] - lastPos; 621e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 622e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 623e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 624e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[ii]); 625e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 626e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift); 627e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 628e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 629e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 630e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare> 631e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 632e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 633e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes, right_shift shift, compare comp) 634e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 635e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 636e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min, shift); 637e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 638e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 639e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 640e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 641e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 642e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 643e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 644e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 645e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 646e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 647e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 648e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[shift(*(current++), log_divisor) - div_min]++; 649e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[bin_count - 1] = first; 650e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = bin_count - 2; ii >= 0; --ii) 651e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[ii] = bins[ii + 1] + bin_sizes[ii + 1]; 652e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 653e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 654e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 655e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The last bin will always have the correct elements in it 656e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = bin_count - 1; ii > 0; --ii) 657e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min); 658e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Since we don't process the last bin, we need to update its end position 659e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = last; 660e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 661e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Return if we've completed bucketsorting 662e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 663e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 664e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 665e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 666e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 667e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 668e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) { 669e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[ii] - lastPos; 670e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 671e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 672e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 673e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[ii], comp); 674e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 675e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp); 676e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 677e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 678e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 679e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Casting special-case for floating-point sorting 680e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type> 681e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 682e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 683e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes) 684e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 685e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 686e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min); 687e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 688e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 689e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 690e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 691e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 692e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 693e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 694e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 695e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 696e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 697e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 698e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++; 699e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The index of the first positive bin 700e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type first_positive = (div_min < 0) ? -div_min : 0; 701e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Resetting if all bins are negative 702e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(cache_offset + first_positive > cache_end) 703e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent first_positive = cache_end - cache_offset; 704e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Reversing the order of the negative bins 705e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note that because of the negative/positive ordering direction flip 706e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //We can not depend upon bin order and positions matching up 707e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //so bin_sizes must be reused to contain the end of the bin 708e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(first_positive > 0) { 709e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[first_positive - 1] = first; 710e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = first_positive - 2; ii >= 0; --ii) { 711e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[ii] = first + bin_sizes[ii + 1]; 712e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[ii] += bin_sizes[ii + 1]; 713e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 714e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Handling positives following negatives 715e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((unsigned)first_positive < bin_count) { 716e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[first_positive] = first + bin_sizes[0]; 717e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[first_positive] += bin_sizes[0]; 718e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 719e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 720e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 721e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 722e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = first_positive; u < bin_count - 1; u++) { 723e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = first + bin_sizes[u]; 724e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[u + 1] += bin_sizes[u]; 725e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 726e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 727e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 728e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 729e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count; ++u) { 730e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart = first + bin_sizes[u]; 731e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min); 732e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 733e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 734e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 735e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 736e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 737e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Handling negative values first 738e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 739e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 740e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) { 741e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[ii] - lastPos; 742e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 743e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 744e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 745e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[ii]); 746e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //sort negative values using reversed-bin spread_sort 747e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 748e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes); 749e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 750e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 751e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) { 752e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 753e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 754e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 755e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 756e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u]); 757e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //sort positive values using normal spread_sort 758e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 759e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes); 760e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 761e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 762e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 763e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Functor implementation for recursive sorting 764e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 765e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 766e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 767e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes, right_shift shift) 768e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 769e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 770e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min, shift); 771e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 772e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 773e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 774e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 775e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 776e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 777e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 778e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 779e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 780e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 781e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 782e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[shift(*(current++), log_divisor) - div_min]++; 783e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The index of the first positive bin 784e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type first_positive = (div_min < 0) ? -div_min : 0; 785e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Resetting if all bins are negative 786e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(cache_offset + first_positive > cache_end) 787e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent first_positive = cache_end - cache_offset; 788e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Reversing the order of the negative bins 789e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note that because of the negative/positive ordering direction flip 790e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //We can not depend upon bin order and positions matching up 791e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //so bin_sizes must be reused to contain the end of the bin 792e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(first_positive > 0) { 793e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[first_positive - 1] = first; 794e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = first_positive - 2; ii >= 0; --ii) { 795e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[ii] = first + bin_sizes[ii + 1]; 796e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[ii] += bin_sizes[ii + 1]; 797e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 798e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Handling positives following negatives 799e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((unsigned)first_positive < bin_count) { 800e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[first_positive] = first + bin_sizes[0]; 801e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[first_positive] += bin_sizes[0]; 802e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 803e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 804e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 805e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 806e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = first_positive; u < bin_count - 1; u++) { 807e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = first + bin_sizes[u]; 808e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[u + 1] += bin_sizes[u]; 809e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 810e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 811e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 812e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 813e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count; ++u) { 814e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart = first + bin_sizes[u]; 815e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min); 816e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 817e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 818e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Return if we've completed bucketsorting 819e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 820e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 821e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 822e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Handling negative values first 823e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 824e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 825e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) { 826e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[ii] - lastPos; 827e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 828e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 829e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 830e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[ii]); 831e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //sort negative values using reversed-bin spread_sort 832e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 833e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift); 834e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 835e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 836e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) { 837e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 838e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 839e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 840e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 841e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u]); 842e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //sort positive values using normal spread_sort 843e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 844e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift); 845e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 846e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 847e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 848e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare> 849e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 850e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset 851e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , std::vector<size_t> &bin_sizes, right_shift shift, compare comp) 852e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 853e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type max, min; 854e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent find_extremes(first, last, max, min, shift); 855e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(max == min) 856e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 857e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min)); 858e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_min = min >> log_divisor; 859e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type div_max = max >> log_divisor; 860e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned bin_count = div_max - div_min + 1; 861e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 862e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); 863e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 864e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin 865e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last;) 866e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[shift(*(current++), log_divisor) - div_min]++; 867e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The index of the first positive bin 868e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent div_type first_positive = (div_min < 0) ? -div_min : 0; 869e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Resetting if all bins are negative 870e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(cache_offset + first_positive > cache_end) 871e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent first_positive = cache_end - cache_offset; 872e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Reversing the order of the negative bins 873e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note that because of the negative/positive ordering direction flip 874e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //We can not depend upon bin order and positions matching up 875e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //so bin_sizes must be reused to contain the end of the bin 876e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(first_positive > 0) { 877e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[first_positive - 1] = first; 878e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = first_positive - 2; ii >= 0; --ii) { 879e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[ii] = first + bin_sizes[ii + 1]; 880e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[ii] += bin_sizes[ii + 1]; 881e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 882e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Handling positives following negatives 883e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((unsigned)first_positive < bin_count) { 884e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[first_positive] = first + bin_sizes[0]; 885e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[first_positive] += bin_sizes[0]; 886e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 887e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 888e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 889e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[0] = first; 890e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = first_positive; u < bin_count - 1; u++) { 891e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[u + 1] = first + bin_sizes[u]; 892e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[u + 1] += bin_sizes[u]; 893e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 894e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 895e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 896e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 897e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < bin_count; ++u) { 898e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart = first + bin_sizes[u]; 899e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min); 900e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 901e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 902e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Return if we've completed bucketsorting 903e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!log_divisor) 904e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 905e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 906e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Handling negative values first 907e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t max_count = get_max_count(log_divisor, last - first); 908e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 909e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) { 910e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[ii] - lastPos; 911e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 912e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 913e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 914e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[ii]); 915e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //sort negative values using reversed-bin spread_sort 916e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 917e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp); 918e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 919e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 920e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) { 921e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 922e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 923e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 924e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_count) 925e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u]); 926e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //sort positive values using normal spread_sort 927e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 928e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp); 929e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 930e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 931e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 932e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class cast_type, class data_type> 933e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 934e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type) 935e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 936e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 937e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 938e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes); 939e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 940e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 941e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift> 942e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 943e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift) 944e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 945e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 946e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 947e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift); 948e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 949e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 950e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare> 951e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 952e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp) 953e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 954e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 955e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 956e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp); 957e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 958e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 959e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 960e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //float_sort with casting 961e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //The cast_type must be equal in size to the data type, and must be a signed integer 962e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class cast_type> 963e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal) 964e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 965e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 966e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last); 967e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 968e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::float_Sort(first, last, cVal, *first); 969e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 970e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 971e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //float_sort with casting to an int 972e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Only use this with IEEE floating-point numbers 973e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter> 974e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last) 975e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 976e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent int cVal = 0; 977e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent float_sort_cast(first, last, cVal); 978e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 979e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 980e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //float_sort with functors 981e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class right_shift> 982e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift) 983e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 984e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 985e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last); 986e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 987e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::float_Sort(first, last, shift(*first, 0), *first, shift); 988e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 989e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 990e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class right_shift, class compare> 991e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp) 992e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 993e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 994e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last, comp); 995e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 996e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp); 997e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 998e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 999e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //------------------------------------------------- string_sort source --------------------------------------------- 1000e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent namespace detail { 1001e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance. 1002e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class RandomAccessIter> 1003e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1004e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset) 1005e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1006e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned nextOffset = char_offset; 1007e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bool done = false; 1008e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(!done) { 1009e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter curr = first; 1010e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent do { 1011e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character 1012e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) { 1013e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent done = true; 1014e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent break; 1015e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1016e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } while(++curr != finish); 1017e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!done) 1018e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++nextOffset; 1019e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1020e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent char_offset = nextOffset; 1021e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1022e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1023e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance. 1024e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class RandomAccessIter, class get_char, class get_length> 1025e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1026e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length) 1027e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1028e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned nextOffset = char_offset; 1029e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bool done = false; 1030e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(!done) { 1031e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter curr = first; 1032e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent do { 1033e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character 1034e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) { 1035e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent done = true; 1036e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent break; 1037e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1038e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } while(++curr != finish); 1039e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(!done) 1040e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++nextOffset; 1041e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1042e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent char_offset = nextOffset; 1043e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1044e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1045e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //A comparison functor for strings that assumes they are identical up to char_offset 1046e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class data_type, class unsignedchar_type> 1047e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent struct offset_lessthan { 1048e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){} 1049e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline bool operator()(const data_type &x, const data_type &y) const 1050e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1051e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned minSize = std::min(x.size(), y.size()); 1052e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = fchar_offset; u < minSize; ++u) { 1053e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u])) 1054e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return true; 1055e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u])) 1056e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return false; 1057e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1058e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return x.size() < y.size(); 1059e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1060e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned fchar_offset; 1061e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent }; 1062e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1063e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //A comparison functor for strings that assumes they are identical up to char_offset 1064e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class data_type, class unsignedchar_type> 1065e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent struct offset_greaterthan { 1066e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){} 1067e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline bool operator()(const data_type &x, const data_type &y) const 1068e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1069e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned minSize = std::min(x.size(), y.size()); 1070e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = fchar_offset; u < minSize; ++u) { 1071e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u])) 1072e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return true; 1073e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u])) 1074e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return false; 1075e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1076e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return x.size() > y.size(); 1077e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1078e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned fchar_offset; 1079e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent }; 1080e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1081e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //A comparison functor for strings that assumes they are identical up to char_offset 1082e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template<class data_type, class get_char, class get_length> 1083e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent struct offset_char_lessthan { 1084e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){} 1085e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline bool operator()(const data_type &x, const data_type &y) const 1086e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1087e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned minSize = std::min(length(x), length(y)); 1088e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = fchar_offset; u < minSize; ++u) { 1089e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(getchar(x, u) < getchar(y, u)) 1090e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return true; 1091e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else if(getchar(y, u) < getchar(x, u)) 1092e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return false; 1093e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1094e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return length(x) < length(y); 1095e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1096e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned fchar_offset; 1097e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent get_char getchar; 1098e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent get_length length; 1099e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent }; 1100e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1101e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //String sorting recursive implementation 1102e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type> 1103e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1104e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache 1105e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , unsigned cache_offset, std::vector<size_t> &bin_sizes) 1106e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1107e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact. 1108e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterate to the end of the empties. If all empty, return 1109e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while((*first).size() <= char_offset) { 1110e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++first == last) 1111e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1112e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1113e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter finish = last - 1; 1114e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Getting the last non-empty 1115e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(;(*finish).size() <= char_offset; --finish) { } 1116e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++finish; 1117e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance. 1118e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(first, finish, char_offset); 1119e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1120e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8)); 1121e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Equal worst-case between radix and comparison-based is when bin_count = n*log(n). 1122e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_size = bin_count; 1123e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned membin_count = bin_count + 1; 1124e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 1125e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1; 1126e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1127e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin; this takes roughly 10% of runtime 1128e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last; ++current) { 1129e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((*current).size() <= char_offset) { 1130e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[0]++; 1131e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1132e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1133e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++; 1134e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1135e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assign the bin positions 1136e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = first; 1137e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < membin_count - 1; u++) 1138e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u]; 1139e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1140e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 1141e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 1142e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //handling empty bins 1143e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = &(bin_cache[cache_offset]); 1144e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[0]; 1145e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * target_bin; 1146e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in the bin of empties 1147e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1148e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //empties belong in this bin 1149e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while((*current).size() > char_offset) { 1150e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]); 1151e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1152e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1153e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1154e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1155e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops 1156e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned last_bin = bin_count - 1; 1157e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { } 1158e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This dominates runtime, mostly in the swap and bin lookups 1159e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < last_bin; ++u) { 1160e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent local_bin = bins + u; 1161e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[u + 1]; 1162e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in this bin 1163e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1164e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swapping elements in current into place until the correct element has been swapped in 1165e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin; 1166e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset])) 1167e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1168e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1169e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1170e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1171e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[last_bin] = last; 1172e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 1173e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = bin_cache[cache_offset]; 1174e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Skip this loop for empties 1175e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) { 1176e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 1177e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //don't sort unless there are at least two items to compare 1178e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 1179e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 1180e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //using std::sort if its worst-case is better 1181e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_size) 1182e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1)); 1183e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1184e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes); 1185e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1186e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1187e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1188e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Sorts strings in reverse order, with empties at the end 1189e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type> 1190e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1191e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache 1192e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , unsigned cache_offset, std::vector<size_t> &bin_sizes) 1193e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1194e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact. 1195e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter curr = first; 1196e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterate to the end of the empties. If all empty, return 1197e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while((*curr).size() <= char_offset) { 1198e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++curr == last) 1199e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1200e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1201e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Getting the last non-empty 1202e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while((*(--last)).size() <= char_offset) { } 1203e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++last; 1204e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance. 1205e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(curr, last, char_offset); 1206e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * target_bin; 1207e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1208e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8)); 1209e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Equal worst-case between radix and comparison-based is when bin_count = n*log(n). 1210e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_size = bin_count; 1211e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned membin_count = bin_count + 1; 1212e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_bin = bin_count - 1; 1213e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 1214e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count); 1215e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]); 1216e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1217e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin; this takes roughly 10% of runtime 1218e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last; ++current) { 1219e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if((*current).size() <= char_offset) { 1220e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[bin_count]++; 1221e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1222e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1223e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++; 1224e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1225e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assign the bin positions 1226e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = first; 1227e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < membin_count - 1; u++) 1228e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u]; 1229e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1230e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 1231e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = last; 1232e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //handling empty bins 1233e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]); 1234e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastFull = *local_bin; 1235e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in the bin of empties 1236e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1237e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //empties belong in this bin 1238e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while((*current).size() > char_offset) { 1239e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]); 1240e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1241e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1242e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1243e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1244e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart = first; 1245e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops 1246e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned last_bin = max_bin; 1247e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(; last_bin && !bin_sizes[last_bin]; --last_bin) { } 1248e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This dominates runtime, mostly in the swap and bin lookups 1249e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < last_bin; ++u) { 1250e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent local_bin = bins + u; 1251e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[u]; 1252e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in this bin 1253e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1254e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swapping elements in current into place until the correct element has been swapped in 1255e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin; 1256e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset])) 1257e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1258e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1259e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1260e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1261e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[last_bin] = lastFull; 1262e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 1263e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 1264e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Skip this loop for empties 1265e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) { 1266e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 1267e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //don't sort unless there are at least two items to compare 1268e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 1269e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 1270e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //using std::sort if its worst-case is better 1271e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_size) 1272e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1)); 1273e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1274e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes); 1275e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1276e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1277e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1278e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //String sorting recursive implementation 1279e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length> 1280e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1281e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache 1282e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length) 1283e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1284e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact. 1285e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterate to the end of the empties. If all empty, return 1286e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*first) <= char_offset) { 1287e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++first == last) 1288e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1289e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1290e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter finish = last - 1; 1291e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Getting the last non-empty 1292e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(;length(*finish) <= char_offset; --finish) { } 1293e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++finish; 1294e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(first, finish, char_offset, getchar, length); 1295e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1296e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8)); 1297e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Equal worst-case between radix and comparison-based is when bin_count = n*log(n). 1298e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_size = bin_count; 1299e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned membin_count = bin_count + 1; 1300e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 1301e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1; 1302e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1303e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin; this takes roughly 10% of runtime 1304e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last; ++current) { 1305e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(length(*current) <= char_offset) { 1306e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[0]++; 1307e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1308e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1309e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[getchar((*current), char_offset) + 1]++; 1310e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1311e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assign the bin positions 1312e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = first; 1313e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < membin_count - 1; u++) 1314e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u]; 1315e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1316e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 1317e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 1318e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //handling empty bins 1319e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = &(bin_cache[cache_offset]); 1320e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[0]; 1321e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * target_bin; 1322e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in the bin of empties 1323e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1324e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //empties belong in this bin 1325e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*current) > char_offset) { 1326e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + getchar((*current), char_offset); 1327e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1328e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1329e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1330e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1331e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops 1332e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned last_bin = bin_count - 1; 1333e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { } 1334e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This dominates runtime, mostly in the swap and bin lookups 1335e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned ii = 0; ii < last_bin; ++ii) { 1336e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent local_bin = bins + ii; 1337e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[ii + 1]; 1338e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in this bin 1339e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1340e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swapping elements in current into place until the correct element has been swapped in 1341e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin; 1342e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + getchar((*current), char_offset)) 1343e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1344e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1345e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1346e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1347e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[last_bin] = last; 1348e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1349e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 1350e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = bin_cache[cache_offset]; 1351e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Skip this loop for empties 1352e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) { 1353e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 1354e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //don't sort unless there are at least two items to compare 1355e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 1356e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 1357e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //using std::sort if its worst-case is better 1358e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_size) 1359e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1)); 1360e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1361e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 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); 1362e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1363e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1364e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1365e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //String sorting recursive implementation 1366e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare> 1367e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1368e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache 1369e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp) 1370e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1371e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact. 1372e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterate to the end of the empties. If all empty, return 1373e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*first) <= char_offset) { 1374e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++first == last) 1375e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1376e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1377e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter finish = last - 1; 1378e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Getting the last non-empty 1379e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(;length(*finish) <= char_offset; --finish) { } 1380e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++finish; 1381e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(first, finish, char_offset, getchar, length); 1382e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1383e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8)); 1384e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Equal worst-case between radix and comparison-based is when bin_count = n*log(n). 1385e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_size = bin_count; 1386e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned membin_count = bin_count + 1; 1387e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 1388e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1; 1389e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1390e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin; this takes roughly 10% of runtime 1391e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last; ++current) { 1392e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(length(*current) <= char_offset) { 1393e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[0]++; 1394e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1395e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1396e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[getchar((*current), char_offset) + 1]++; 1397e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1398e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assign the bin positions 1399e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = first; 1400e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < membin_count - 1; u++) 1401e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u]; 1402e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1403e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 1404e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = first; 1405e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //handling empty bins 1406e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = &(bin_cache[cache_offset]); 1407e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[0]; 1408e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * target_bin; 1409e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in the bin of empties 1410e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1411e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //empties belong in this bin 1412e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*current) > char_offset) { 1413e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + getchar((*current), char_offset); 1414e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1415e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1416e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1417e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1418e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops 1419e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned last_bin = bin_count - 1; 1420e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { } 1421e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This dominates runtime, mostly in the swap and bin lookups 1422e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < last_bin; ++u) { 1423e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent local_bin = bins + u; 1424e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[u + 1]; 1425e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in this bin 1426e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1427e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swapping elements in current into place until the correct element has been swapped in 1428e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin; 1429e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = bins + getchar((*current), char_offset)) 1430e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1431e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1432e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1433e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1434e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[last_bin] = last; 1435e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1436e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 1437e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = bin_cache[cache_offset]; 1438e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Skip this loop for empties 1439e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) { 1440e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 1441e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //don't sort unless there are at least two items to compare 1442e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 1443e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 1444e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //using std::sort if its worst-case is better 1445e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_size) 1446e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u], comp); 1447e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1448e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos 1449e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp); 1450e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1451e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1452e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1453e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Sorts strings in reverse order, with empties at the end 1454e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare> 1455e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1456e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache 1457e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp) 1458e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1459e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact. 1460e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter curr = first; 1461e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterate to the end of the empties. If all empty, return 1462e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*curr) <= char_offset) { 1463e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++curr == last) 1464e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1465e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1466e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Getting the last non-empty 1467e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*(--last)) <= char_offset) { } 1468e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++last; 1469e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance. 1470e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent update_offset(first, last, char_offset, getchar, length); 1471e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1472e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8)); 1473e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Equal worst-case between radix and comparison-based is when bin_count = n*log(n). 1474e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_size = bin_count; 1475e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned membin_count = bin_count + 1; 1476e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent const unsigned max_bin = bin_count - 1; 1477e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned cache_end; 1478e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count); 1479e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]); 1480e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1481e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Calculating the size of each bin; this takes roughly 10% of runtime 1482e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for (RandomAccessIter current = first; current != last; ++current) { 1483e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(length(*current) <= char_offset) { 1484e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[bin_count]++; 1485e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1486e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1487e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_sizes[max_bin - getchar((*current), char_offset)]++; 1488e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1489e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Assign the bin positions 1490e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset] = first; 1491e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < membin_count - 1; u++) 1492e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u]; 1493e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1494e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swap into place 1495e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter nextbinstart = last; 1496e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //handling empty bins 1497e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]); 1498e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastFull = *local_bin; 1499e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter * target_bin; 1500e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in the bin of empties 1501e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1502e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //empties belong in this bin 1503e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(length(*current) > char_offset) { 1504e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = end_bin - getchar((*current), char_offset); 1505e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1506e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1507e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1508e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1509e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart = first; 1510e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops 1511e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned last_bin = max_bin; 1512e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(; last_bin && !bin_sizes[last_bin]; --last_bin) { } 1513e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //This dominates runtime, mostly in the swap and bin lookups 1514e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = 0; u < last_bin; ++u) { 1515e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent local_bin = bins + u; 1516e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent nextbinstart += bin_sizes[u]; 1517e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Iterating over each element in this bin 1518e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { 1519e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Swapping elements in current into place until the correct element has been swapped in 1520e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(target_bin = end_bin - getchar((*current), char_offset); target_bin != local_bin; 1521e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent target_bin = end_bin - getchar((*current), char_offset)) 1522e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent iter_swap(current, (*target_bin)++); 1523e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1524e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent *local_bin = nextbinstart; 1525e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1526e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent bins[last_bin] = lastFull; 1527e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Recursing 1528e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent RandomAccessIter lastPos = first; 1529e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Skip this loop for empties 1530e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) { 1531e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent size_t count = bin_cache[u] - lastPos; 1532e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //don't sort unless there are at least two items to compare 1533e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < 2) 1534e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent continue; 1535e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //using std::sort if its worst-case is better 1536e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(count < max_size) 1537e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(lastPos, bin_cache[u], comp); 1538e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1539e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos 1540e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp); 1541e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1542e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1543e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1544e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Holds the bin vector and makes the initial recursive call 1545e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type> 1546e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1547e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type) 1548e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1549e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 1550e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 1551e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes); 1552e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1553e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1554e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Holds the bin vector and makes the initial recursive call 1555e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class data_type, class unsignedchar_type> 1556e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1557e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type) 1558e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1559e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 1560e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 1561e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes); 1562e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1563e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1564e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Holds the bin vector and makes the initial recursive call 1565e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type> 1566e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1567e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type) 1568e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1569e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 1570e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 1571e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length); 1572e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1573e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1574e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Holds the bin vector and makes the initial recursive call 1575e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type> 1576e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1577e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type) 1578e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1579e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 1580e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 1581e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp); 1582e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1583e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1584e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Holds the bin vector and makes the initial recursive call 1585e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type> 1586e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void 1587e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type) 1588e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1589e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<size_t> bin_sizes; 1590e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::vector<RandomAccessIter> bin_cache; 1591e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 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); 1592e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1593e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1594e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1595e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Allows character-type overloads 1596e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class unsignedchar_type> 1597e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused) 1598e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1599e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't sort if it's too small to optimize 1600e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 1601e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last); 1602e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1603e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::string_sort(first, last, *first, unused); 1604e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1605e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1606e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Top-level sorting call; wraps using default of unsigned char 1607e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter> 1608e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void string_sort(RandomAccessIter first, RandomAccessIter last) 1609e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1610e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned char unused = '\0'; 1611e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent string_sort(first, last, unused); 1612e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1613e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1614e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Allows character-type overloads 1615e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class compare, class unsignedchar_type> 1616e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused) 1617e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1618e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't sort if it's too small to optimize 1619e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 1620e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last, comp); 1621e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else 1622e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::reverse_string_sort(first, last, *first, unused); 1623e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1624e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1625e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Top-level sorting call; wraps using default of unsigned char 1626e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class compare> 1627e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp) 1628e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1629e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent unsigned char unused = '\0'; 1630e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent reverse_string_sort(first, last, comp, unused); 1631e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1632e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1633e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class get_char, class get_length> 1634e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length) 1635e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1636e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't sort if it's too small to optimize 1637e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 1638e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last); 1639e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else { 1640e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //skipping past empties at the beginning, which allows us to get the character type 1641e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //.empty() is not used so as not to require a user declaration of it 1642e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(!length(*first)) { 1643e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++first == last) 1644e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1645e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1646e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0)); 1647e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1648e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1649e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1650e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class get_char, class get_length, class compare> 1651e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 1652e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1653e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't sort if it's too small to optimize 1654e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 1655e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last, comp); 1656e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else { 1657e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //skipping past empties at the beginning, which allows us to get the character type 1658e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //.empty() is not used so as not to require a user declaration of it 1659e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(!length(*first)) { 1660e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(++first == last) 1661e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1662e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1663e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0)); 1664e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1665e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1666e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1667e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent template <class RandomAccessIter, class get_char, class get_length, class compare> 1668e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp) 1669e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent { 1670e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Don't sort if it's too small to optimize 1671e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(last - first < detail::MIN_SORT_SIZE) 1672e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent std::sort(first, last, comp); 1673e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent else { 1674e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //skipping past empties at the beginning, which allows us to get the character type 1675e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //.empty() is not used so as not to require a user declaration of it 1676e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent while(!length(*(--last))) { 1677e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order 1678e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent if(first == last) 1679e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent return; 1680e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1681e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent //making last just after the end of the non-empty part of the array 1682e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent ++last; 1683e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0)); 1684e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1685e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent } 1686e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent} 1687e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent 1688e48d5845c8b35de2ab73ea055c18a61fa3a9f0beEric Laurent#endif 1689