123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831 |
- // 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)
- 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 - 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)
- 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 - 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)
- 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 - 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)
- 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_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);
- 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_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
- 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_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
- boost::sort::pdqsort(first, last, comp);
- }
- }
- }
- }
- }
- #endif
|