EIC code displayed by LXR master/​include/​boost/​sort/​spreadsort/​detail/​float_sort.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:51:48

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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team