boost/sort/spreadsort/detail/float_sort.hpp
// Details for templated Spreadsort-based float_sort. // Copyright Steven J. Ross 2001 - 2014. // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // See http://www.boost.org/libs/sort for library home page. /* Some improvements suggested by: Phil Endecott and Frank Gennari float_mem_cast fix provided by: Scott McMurray */ #ifndef BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP #define BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP #include <algorithm> #include <vector> #include <limits> #include <functional> #include <boost/static_assert.hpp> #include <boost/utility/enable_if.hpp> #include <boost/sort/spreadsort/detail/constants.hpp> #include <boost/sort/spreadsort/detail/integer_sort.hpp> #include <boost/sort/spreadsort/detail/spreadsort_common.hpp> #include <boost/cstdint.hpp> namespace boost { namespace sort { namespace spreadsort { namespace detail { //Casts a RandomAccessIter to the specified integer type template<class Cast_type, class RandomAccessIter> inline Cast_type cast_float_iter(const RandomAccessIter & floatiter) { typedef typename std::iterator_traits<RandomAccessIter>::value_type Data_type; //Only cast IEEE floating-point numbers, and only to same-sized integers BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type)); BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559); BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer); Cast_type result; std::memcpy(&result, &(*floatiter), sizeof(Data_type)); return result; } // Return true if the list is sorted. Otherwise, find the minimum and // maximum. Values are Right_shifted 0 bits before comparison. template <class RandomAccessIter, class Div_type, class Right_shift> inline bool is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last, Div_type & max, Div_type & min, Right_shift rshift) { min = max = rshift(*current, 0); RandomAccessIter prev = current; bool sorted = true; while (++current < last) { Div_type value = rshift(*current, 0); sorted &= *current >= *prev; prev = current; if (max < value) max = value; else if (value < min) min = value; } return sorted; } // Return true if the list is sorted. Otherwise, find the minimum and // maximum. Uses comp to check if the data is already sorted. template <class RandomAccessIter, class Div_type, class Right_shift, class Compare> inline bool is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last, Div_type & max, Div_type & min, Right_shift rshift, Compare comp) { min = max = rshift(*current, 0); RandomAccessIter prev = current; bool sorted = true; while (++current < last) { Div_type value = rshift(*current, 0); sorted &= !comp(*current, *prev); prev = current; if (max < value) max = value; else if (value < min) min = value; } return sorted; } //Specialized swap loops for floating-point casting template <class RandomAccessIter, class Div_type> inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii , const unsigned log_divisor, const Div_type div_min) { RandomAccessIter * local_bin = bins + ii; for (RandomAccessIter current = *local_bin; current < nextbinstart; ++current) { for (RandomAccessIter * target_bin = (bins + ((cast_float_iter<Div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin; target_bin = bins + ((cast_float_iter<Div_type, RandomAccessIter> (current) >> log_divisor) - div_min)) { typename std::iterator_traits<RandomAccessIter>::value_type tmp; RandomAccessIter b = (*target_bin)++; RandomAccessIter * b_bin = bins + ((cast_float_iter<Div_type, RandomAccessIter>(b) >> log_divisor) - div_min); //Three-way swap; if the item to be swapped doesn't belong in the //current bin, swap it to where it belongs if (b_bin != local_bin) { RandomAccessIter c = (*b_bin)++; tmp = *c; *c = *b; } else tmp = *b; *b = *current; *current = tmp; } } *local_bin = nextbinstart; } template <class RandomAccessIter, class Div_type> inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, const size_t *bin_sizes, const unsigned log_divisor, const Div_type div_min) { nextbinstart += bin_sizes[ii]; inner_float_swap_loop<RandomAccessIter, Div_type> (bins, nextbinstart, ii, log_divisor, div_min); } // Return true if the list is sorted. Otherwise, find the minimum and // maximum. Values are cast to Cast_type before comparison. template <class RandomAccessIter, class Cast_type> inline bool is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last, Cast_type & max, Cast_type & min) { min = max = cast_float_iter<Cast_type, RandomAccessIter>(current); RandomAccessIter prev = current; bool sorted = true; while (++current < last) { Cast_type value = cast_float_iter<Cast_type, RandomAccessIter>(current); sorted &= *current >= *prev; prev = current; if (max < value) max = value; else if (value < min) min = value; } return sorted; } //Special-case sorting of positive floats with casting template <class RandomAccessIter, class Div_type, class Size_type> inline void positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset , size_t *bin_sizes) { Div_type max, min; if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last, max, min)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max - min))); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>( current++) >> log_divisor) - div_min)]++; bins[0] = first; for (unsigned u = 0; u < bin_count - 1; u++) bins[u + 1] = bins[u] + bin_sizes[u]; //Swap into place RandomAccessIter nextbinstart = first; for (unsigned u = 0; u < bin_count - 1; ++u) float_swap_loop<RandomAccessIter, Div_type> (bins, nextbinstart, u, bin_sizes, log_divisor, div_min); bins[bin_count - 1] = last; //Return if we've completed bucketsorting if (!log_divisor) return; //Recursing size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) { size_t count = bin_cache[u] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[u]); else positive_float_sort_rec<RandomAccessIter, Div_type, Size_type> (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes); } } //Sorting negative floats //Bins are iterated in reverse because max_neg_float = min_neg_int template <class RandomAccessIter, class Div_type, class Size_type> inline void negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, size_t *bin_sizes) { Div_type max, min; if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last, max, min)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max - min))); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>( current++) >> log_divisor) - div_min)]++; bins[bin_count - 1] = first; for (int ii = bin_count - 2; ii >= 0; --ii) bins[ii] = bins[ii + 1] + bin_sizes[ii + 1]; //Swap into place RandomAccessIter nextbinstart = first; //The last bin will always have the correct elements in it for (int ii = bin_count - 1; ii > 0; --ii) float_swap_loop<RandomAccessIter, Div_type> (bins, nextbinstart, ii, bin_sizes, log_divisor, div_min); //Update the end position because we don't process the last bin bin_cache[cache_offset] = last; //Return if we've completed bucketsorting if (!log_divisor) return; //Recursing size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset); lastPos = bin_cache[ii], --ii) { size_t count = bin_cache[ii] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[ii]); else negative_float_sort_rec<RandomAccessIter, Div_type, Size_type> (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes); } } //Sorting negative floats //Bins are iterated in reverse order because max_neg_float = min_neg_int template <class RandomAccessIter, class Div_type, class Right_shift, class Size_type> inline void negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset , size_t *bin_sizes, Right_shift rshift) { Div_type max, min; if (is_sorted_or_find_extremes(first, last, max, min, rshift)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max - min))); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++; bins[bin_count - 1] = first; for (int ii = bin_count - 2; ii >= 0; --ii) bins[ii] = bins[ii + 1] + bin_sizes[ii + 1]; //Swap into place RandomAccessIter nextbinstart = first; //The last bin will always have the correct elements in it for (int ii = bin_count - 1; ii > 0; --ii) swap_loop<RandomAccessIter, Div_type, Right_shift> (bins, nextbinstart, ii, rshift, bin_sizes, log_divisor, div_min); //Update the end position of the unprocessed last bin bin_cache[cache_offset] = last; //Return if we've completed bucketsorting if (!log_divisor) return; //Recursing size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset); lastPos = bin_cache[ii], --ii) { size_t count = bin_cache[ii] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[ii]); else negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift, Size_type> (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift); } } template <class RandomAccessIter, class Div_type, class Right_shift, class Compare, class Size_type> inline void negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, size_t *bin_sizes, Right_shift rshift, Compare comp) { Div_type max, min; if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max - min))); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++; bins[bin_count - 1] = first; for (int ii = bin_count - 2; ii >= 0; --ii) bins[ii] = bins[ii + 1] + bin_sizes[ii + 1]; //Swap into place RandomAccessIter nextbinstart = first; //The last bin will always have the correct elements in it for (int ii = bin_count - 1; ii > 0; --ii) swap_loop<RandomAccessIter, Div_type, Right_shift> (bins, nextbinstart, ii, rshift, bin_sizes, log_divisor, div_min); //Update the end position of the unprocessed last bin bin_cache[cache_offset] = last; //Return if we've completed bucketsorting if (!log_divisor) return; //Recursing size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset); lastPos = bin_cache[ii], --ii) { size_t count = bin_cache[ii] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[ii], comp); else negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare, Size_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift, comp); } } //Casting special-case for floating-point sorting template <class RandomAccessIter, class Div_type, class Size_type> inline void float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset , size_t *bin_sizes) { Div_type max, min; if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last, max, min)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max/2 - min/2)) + 1); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>( current++) >> log_divisor) - div_min)]++; //The index of the first positive bin //Must be divided small enough to fit into an integer unsigned first_positive = (div_min < 0) ? unsigned(-div_min) : 0; //Resetting if all bins are negative if (cache_offset + first_positive > cache_end) first_positive = cache_end - cache_offset; //Reversing the order of the negative bins //Note that because of the negative/positive ordering direction flip //We can not depend upon bin order and positions matching up //so bin_sizes must be reused to contain the end of the bin if (first_positive > 0) { bins[first_positive - 1] = first; for (int ii = first_positive - 2; ii >= 0; --ii) { bins[ii] = first + bin_sizes[ii + 1]; bin_sizes[ii] += bin_sizes[ii + 1]; } //Handling positives following negatives if (first_positive < bin_count) { bins[first_positive] = first + bin_sizes[0]; bin_sizes[first_positive] += bin_sizes[0]; } } else bins[0] = first; for (unsigned u = first_positive; u < bin_count - 1; u++) { bins[u + 1] = first + bin_sizes[u]; bin_sizes[u + 1] += bin_sizes[u]; } //Swap into place RandomAccessIter nextbinstart = first; for (unsigned u = 0; u < bin_count; ++u) { nextbinstart = first + bin_sizes[u]; inner_float_swap_loop<RandomAccessIter, Div_type> (bins, nextbinstart, u, log_divisor, div_min); } if (!log_divisor) return; //Handling negative values first size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (int ii = cache_offset + first_positive - 1; ii >= static_cast<int>(cache_offset); lastPos = bin_cache[ii--]) { size_t count = bin_cache[ii] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[ii]); //sort negative values using reversed-bin spreadsort else negative_float_sort_rec<RandomAccessIter, Div_type, Size_type> (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes); } for (unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) { size_t count = bin_cache[u] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[u]); //sort positive values using normal spreadsort else positive_float_sort_rec<RandomAccessIter, Div_type, Size_type> (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes); } } //Functor implementation for recursive sorting template <class RandomAccessIter, class Div_type, class Right_shift , class Size_type> inline void float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset , size_t *bin_sizes, Right_shift rshift) { Div_type max, min; if (is_sorted_or_find_extremes(first, last, max, min, rshift)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max/2 - min/2)) + 1); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++; //The index of the first positive bin unsigned first_positive = (div_min < 0) ? unsigned(-div_min) : 0; //Resetting if all bins are negative if (cache_offset + first_positive > cache_end) first_positive = cache_end - cache_offset; //Reversing the order of the negative bins //Note that because of the negative/positive ordering direction flip //We can not depend upon bin order and positions matching up //so bin_sizes must be reused to contain the end of the bin if (first_positive > 0) { bins[first_positive - 1] = first; for (int ii = first_positive - 2; ii >= 0; --ii) { bins[ii] = first + bin_sizes[ii + 1]; bin_sizes[ii] += bin_sizes[ii + 1]; } //Handling positives following negatives if (static_cast<unsigned>(first_positive) < bin_count) { bins[first_positive] = first + bin_sizes[0]; bin_sizes[first_positive] += bin_sizes[0]; } } else bins[0] = first; for (unsigned u = first_positive; u < bin_count - 1; u++) { bins[u + 1] = first + bin_sizes[u]; bin_sizes[u + 1] += bin_sizes[u]; } //Swap into place RandomAccessIter next_bin_start = first; for (unsigned u = 0; u < bin_count; ++u) { next_bin_start = first + bin_sizes[u]; inner_swap_loop<RandomAccessIter, Div_type, Right_shift> (bins, next_bin_start, u, rshift, log_divisor, div_min); } //Return if we've completed bucketsorting if (!log_divisor) return; //Handling negative values first size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (int ii = cache_offset + first_positive - 1; ii >= static_cast<int>(cache_offset); lastPos = bin_cache[ii--]) { size_t count = bin_cache[ii] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[ii]); //sort negative values using reversed-bin spreadsort else negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift, Size_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift); } for (unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) { size_t count = bin_cache[u] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[u]); //sort positive values using normal spreadsort else spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Size_type, float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count> (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift); } } template <class RandomAccessIter, class Div_type, class Right_shift, class Compare, class Size_type> inline void float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, size_t *bin_sizes, Right_shift rshift, Compare comp) { Div_type max, min; if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp)) return; unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>( last - first, rough_log_2_size(Size_type(max/2 - min/2)) + 1); Div_type div_min = min >> log_divisor; Div_type div_max = max >> log_divisor; unsigned bin_count = unsigned(div_max - div_min) + 1; unsigned cache_end; RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); //Calculating the size of each bin for (RandomAccessIter current = first; current != last;) bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++; //The index of the first positive bin unsigned first_positive = (div_min < 0) ? static_cast<unsigned>(-div_min) : 0; //Resetting if all bins are negative if (cache_offset + first_positive > cache_end) first_positive = cache_end - cache_offset; //Reversing the order of the negative bins //Note that because of the negative/positive ordering direction flip //We can not depend upon bin order and positions matching up //so bin_sizes must be reused to contain the end of the bin if (first_positive > 0) { bins[first_positive - 1] = first; for (int ii = first_positive - 2; ii >= 0; --ii) { bins[ii] = first + bin_sizes[ii + 1]; bin_sizes[ii] += bin_sizes[ii + 1]; } //Handling positives following negatives if (static_cast<unsigned>(first_positive) < bin_count) { bins[first_positive] = first + bin_sizes[0]; bin_sizes[first_positive] += bin_sizes[0]; } } else bins[0] = first; for (unsigned u = first_positive; u < bin_count - 1; u++) { bins[u + 1] = first + bin_sizes[u]; bin_sizes[u + 1] += bin_sizes[u]; } //Swap into place RandomAccessIter next_bin_start = first; for (unsigned u = 0; u < bin_count; ++u) { next_bin_start = first + bin_sizes[u]; inner_swap_loop<RandomAccessIter, Div_type, Right_shift> (bins, next_bin_start, u, rshift, log_divisor, div_min); } //Return if we've completed bucketsorting if (!log_divisor) return; //Handling negative values first size_t max_count = get_min_count<float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count>(log_divisor); RandomAccessIter lastPos = first; for (int ii = cache_offset + first_positive - 1; ii >= static_cast<int>(cache_offset); lastPos = bin_cache[ii--]) { size_t count = bin_cache[ii] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[ii], comp); //sort negative values using reversed-bin spreadsort else negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare, Size_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift, comp); } for (unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) { size_t count = bin_cache[u] - lastPos; if (count < 2) continue; if (count < max_count) boost::sort::pdqsort(lastPos, bin_cache[u], comp); //sort positive values using normal spreadsort else spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare, Size_type, float_log_mean_bin_size, float_log_min_split_count, float_log_finishing_count> (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift, comp); } } //Checking whether the value type is a float, and trying a 32-bit integer template <class RandomAccessIter> inline typename boost::enable_if_c< sizeof(boost::uint32_t) == sizeof(typename std::iterator_traits<RandomAccessIter>::value_type) && std::numeric_limits<typename std::iterator_traits<RandomAccessIter>::value_type>::is_iec559, void >::type float_sort(RandomAccessIter first, RandomAccessIter last) { size_t bin_sizes[1 << max_finishing_splits]; std::vector<RandomAccessIter> bin_cache; float_sort_rec<RandomAccessIter, boost::int32_t, boost::uint32_t> (first, last, bin_cache, 0, bin_sizes); } //Checking whether the value type is a double, and using a 64-bit integer template <class RandomAccessIter> inline typename boost::enable_if_c< sizeof(boost::uint64_t) == sizeof(typename std::iterator_traits<RandomAccessIter>::value_type) && std::numeric_limits<typename std::iterator_traits<RandomAccessIter>::value_type>::is_iec559, void >::type float_sort(RandomAccessIter first, RandomAccessIter last) { size_t bin_sizes[1 << max_finishing_splits]; std::vector<RandomAccessIter> bin_cache; float_sort_rec<RandomAccessIter, boost::int64_t, boost::uint64_t> (first, last, bin_cache, 0, bin_sizes); } template <class RandomAccessIter> inline typename boost::disable_if_c< (sizeof(boost::uint64_t) == sizeof(typename std::iterator_traits<RandomAccessIter>::value_type) || sizeof(boost::uint32_t) == sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)) && std::numeric_limits<typename std::iterator_traits<RandomAccessIter>::value_type>::is_iec559, void >::type float_sort(RandomAccessIter first, RandomAccessIter last) { BOOST_STATIC_ASSERT(!(sizeof(boost::uint64_t) == sizeof(typename std::iterator_traits<RandomAccessIter>::value_type) || sizeof(boost::uint32_t) == sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)) || !std::numeric_limits<typename std::iterator_traits<RandomAccessIter>::value_type>::is_iec559); boost::sort::pdqsort(first, last); } //These approaches require the user to do the typecast //with rshift but default comparision template <class RandomAccessIter, class Div_type, class Right_shift> inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, Right_shift rshift) { size_t bin_sizes[1 << max_finishing_splits]; std::vector<RandomAccessIter> bin_cache; float_sort_rec<RandomAccessIter, Div_type, Right_shift, size_t> (first, last, bin_cache, 0, bin_sizes, rshift); } //maximum integer size with rshift but default comparision template <class RandomAccessIter, class Div_type, class Right_shift> inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type) && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, Right_shift rshift) { size_t bin_sizes[1 << max_finishing_splits]; std::vector<RandomAccessIter> bin_cache; float_sort_rec<RandomAccessIter, Div_type, Right_shift, boost::uintmax_t> (first, last, bin_cache, 0, bin_sizes, rshift); } //sizeof(Div_type) doesn't match, so use boost::sort::pdqsort template <class RandomAccessIter, class Div_type, class Right_shift> inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, Right_shift rshift) { boost::sort::pdqsort(first, last); } //specialized comparison template <class RandomAccessIter, class Div_type, class Right_shift, class Compare> inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, Right_shift rshift, Compare comp) { size_t bin_sizes[1 << max_finishing_splits]; std::vector<RandomAccessIter> bin_cache; float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare, size_t> (first, last, bin_cache, 0, bin_sizes, rshift, comp); } //max-sized integer with specialized comparison template <class RandomAccessIter, class Div_type, class Right_shift, class Compare> inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type) && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, Right_shift rshift, Compare comp) { size_t bin_sizes[1 << max_finishing_splits]; std::vector<RandomAccessIter> bin_cache; float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare, boost::uintmax_t> (first, last, bin_cache, 0, bin_sizes, rshift, comp); } //sizeof(Div_type) doesn't match, so use boost::sort::pdqsort template <class RandomAccessIter, class Div_type, class Right_shift, class Compare> inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, Right_shift rshift, Compare comp) { boost::sort::pdqsort(first, last, comp); } } } } } #endif