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