[ceph.git] / ceph / src / boost / boost / sort / spreadsort / detail / float_sort.hpp

// 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