path: root/boost/sort/spreadsort/detail/float_sort.hpp

// Details for templated Spreadsort-based float_sort.

//          Copyright Steven J. Ross 2001 - 2014.
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

// See http://www.boost.org/libs/sort for library home page.

/*
Some improvements suggested by:
Phil Endecott and Frank Gennari
float_mem_cast fix provided by:
Scott McMurray
*/

#ifndef BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP
#define BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP
#include <algorithm>
#include <vector>
#include <limits>
#include <functional>
#include <boost/static_assert.hpp>
#include <boost/serialization/static_warning.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/sort/spreadsort/detail/constants.hpp>
#include <boost/sort/spreadsort/detail/integer_sort.hpp>
#include <boost/sort/spreadsort/detail/spreadsort_common.hpp>
#include <boost/cstdint.hpp>

namespace boost {
namespace sort {
namespace spreadsort {
  namespace detail {
    //Casts a RandomAccessIter to the specified integer type
    template<class Cast_type, class RandomAccessIter>
    inline Cast_type
    cast_float_iter(const RandomAccessIter & floatiter)
    {
      typedef typename std::iterator_traits<RandomAccessIter>::value_type
        Data_type;
      //Only cast IEEE floating-point numbers, and only to same-sized integers
      BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type));
      BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559);
      BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer);
      Cast_type result;
      std::memcpy(&result, &(*floatiter), sizeof(Data_type));
      return result;
    }

    // Return true if the list is sorted.  Otherwise, find the minimum and
    // maximum.  Values are Right_shifted 0 bits before comparison.
    template <class RandomAccessIter, class Div_type, class Right_shift>
    inline bool
    is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
                  Div_type & max, Div_type & min, Right_shift rshift)
    {
      min = max = rshift(*current, 0);
      RandomAccessIter prev = current;
      bool sorted = true;
      while (++current < last) {
        Div_type value = rshift(*current, 0);
        sorted &= *current >= *prev;
        prev = current;
        if (max < value)
          max = value;
        else if (value < min)
          min = value;
      }
      return sorted;
    }

    // Return true if the list is sorted.  Otherwise, find the minimum and
    // maximum.  Uses comp to check if the data is already sorted.
    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Compare>
    inline bool
    is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
                               Div_type & max, Div_type & min, 
                               Right_shift rshift, Compare comp)
    {
      min = max = rshift(*current, 0);
      RandomAccessIter prev = current;
      bool sorted = true;
      while (++current < last) {
        Div_type value = rshift(*current, 0);
        sorted &= !comp(*current, *prev);
        prev = current;
        if (max < value)
          max = value;
        else if (value < min)
          min = value;
      }
      return sorted;
    }

    //Specialized swap loops for floating-point casting
    template <class RandomAccessIter, class Div_type>
    inline void inner_float_swap_loop(RandomAccessIter * bins,
                        const RandomAccessIter & nextbinstart, unsigned ii
                        , const unsigned log_divisor, const Div_type div_min)
    {
      RandomAccessIter * local_bin = bins + ii;
      for (RandomAccessIter current = *local_bin; current < nextbinstart;
          ++current) {
        for (RandomAccessIter * target_bin =
            (bins + ((cast_float_iter<Div_type, RandomAccessIter>(current) >>
                      log_divisor) - div_min));  target_bin != local_bin;
          target_bin = bins + ((cast_float_iter<Div_type, RandomAccessIter>
                               (current) >> log_divisor) - div_min)) {
          typename std::iterator_traits<RandomAccessIter>::value_type tmp;
          RandomAccessIter b = (*target_bin)++;
          RandomAccessIter * b_bin = bins + ((cast_float_iter<Div_type,
                              RandomAccessIter>(b) >> log_divisor) - div_min);
          //Three-way swap; if the item to be swapped doesn't belong in the
          //current bin, swap it to where it belongs
          if (b_bin != local_bin) {
            RandomAccessIter c = (*b_bin)++;
            tmp = *c;
            *c = *b;
          }
          else
            tmp = *b;
          *b = *current;
          *current = tmp;
        }
      }
      *local_bin = nextbinstart;
    }

    template <class RandomAccessIter, class Div_type>
    inline void float_swap_loop(RandomAccessIter * bins,
                          RandomAccessIter & nextbinstart, unsigned ii,
                          const size_t *bin_sizes,
                          const unsigned log_divisor, const Div_type div_min)
    {
      nextbinstart += bin_sizes[ii];
      inner_float_swap_loop<RandomAccessIter, Div_type>
        (bins, nextbinstart, ii, log_divisor, div_min);
    }

    // Return true if the list is sorted.  Otherwise, find the minimum and
    // maximum.  Values are cast to Cast_type before comparison.
    template <class RandomAccessIter, class Cast_type>
    inline bool
    is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
                  Cast_type & max, Cast_type & min)
    {
      min = max = cast_float_iter<Cast_type, RandomAccessIter>(current);
      RandomAccessIter prev = current;
      bool sorted = true;
      while (++current < last) {
        Cast_type value = cast_float_iter<Cast_type, RandomAccessIter>(current);
        sorted &= *current >= *prev;
        prev = current;
        if (max < value)
          max = value;
        else if (value < min)
          min = value;
      }
      return sorted;
    }

    //Special-case sorting of positive floats with casting
    template <class RandomAccessIter, class Div_type, class Size_type>
    inline void
    positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
              std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
              , size_t *bin_sizes)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last, 
                                                                max, min))
        return;
      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>(
            current++) >> log_divisor) - div_min)]++;
      bins[0] = first;
      for (unsigned u = 0; u < bin_count - 1; u++)
        bins[u + 1] = bins[u] + bin_sizes[u];


      //Swap into place
      RandomAccessIter nextbinstart = first;
      for (unsigned u = 0; u < bin_count - 1; ++u)
        float_swap_loop<RandomAccessIter, Div_type>
          (bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
      bins[bin_count - 1] = last;

      //Return if we've completed bucketsorting
      if (!log_divisor)
        return;

      //Recursing
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
          ++u) {
        size_t count = bin_cache[u] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[u]);
        else
          positive_float_sort_rec<RandomAccessIter, Div_type, Size_type>
            (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
      }
    }

    //Sorting negative floats
    //Bins are iterated in reverse because max_neg_float = min_neg_int
    template <class RandomAccessIter, class Div_type, class Size_type>
    inline void
    negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
                        std::vector<RandomAccessIter> &bin_cache,
                        unsigned cache_offset, size_t *bin_sizes)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last, 
                                                                 max, min))
        return;

      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>(
            current++) >> log_divisor) - div_min)]++;
      bins[bin_count - 1] = first;
      for (int ii = bin_count - 2; ii >= 0; --ii)
        bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

      //Swap into place
      RandomAccessIter nextbinstart = first;
      //The last bin will always have the correct elements in it
      for (int ii = bin_count - 1; ii > 0; --ii)
        float_swap_loop<RandomAccessIter, Div_type>
          (bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
      //Update the end position because we don't process the last bin
      bin_cache[cache_offset] = last;

      //Return if we've completed bucketsorting
      if (!log_divisor)
        return;

      //Recursing
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset);
          lastPos = bin_cache[ii], --ii) {
        size_t count = bin_cache[ii] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[ii]);
        else
          negative_float_sort_rec<RandomAccessIter, Div_type, Size_type>
            (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
      }
    }

    //Sorting negative floats
    //Bins are iterated in reverse order because max_neg_float = min_neg_int
    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Size_type>
    inline void
    negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
              std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
              , size_t *bin_sizes, Right_shift rshift)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes(first, last, max, min, rshift))
        return;
      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
      bins[bin_count - 1] = first;
      for (int ii = bin_count - 2; ii >= 0; --ii)
        bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

      //Swap into place
      RandomAccessIter nextbinstart = first;
      //The last bin will always have the correct elements in it
      for (int ii = bin_count - 1; ii > 0; --ii)
        swap_loop<RandomAccessIter, Div_type, Right_shift>
          (bins, nextbinstart, ii, rshift, bin_sizes, log_divisor, div_min);
      //Update the end position of the unprocessed last bin
      bin_cache[cache_offset] = last;

      //Return if we've completed bucketsorting
      if (!log_divisor)
        return;

      //Recursing
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset);
          lastPos = bin_cache[ii], --ii) {
        size_t count = bin_cache[ii] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[ii]);
        else
          negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
                                  Size_type>
            (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift);
      }
    }

    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Compare, class Size_type>
    inline void
    negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
            std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset,
            size_t *bin_sizes, Right_shift rshift, Compare comp)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
        return;
      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
      bins[bin_count - 1] = first;
      for (int ii = bin_count - 2; ii >= 0; --ii)
        bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

      //Swap into place
      RandomAccessIter nextbinstart = first;
      //The last bin will always have the correct elements in it
      for (int ii = bin_count - 1; ii > 0; --ii)
        swap_loop<RandomAccessIter, Div_type, Right_shift>
          (bins, nextbinstart, ii, rshift, bin_sizes, log_divisor, div_min);
      //Update the end position of the unprocessed last bin
      bin_cache[cache_offset] = last;

      //Return if we've completed bucketsorting
      if (!log_divisor)
        return;

      //Recursing
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset);
          lastPos = bin_cache[ii], --ii) {
        size_t count = bin_cache[ii] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[ii], comp);
        else
          negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
                                  Compare, Size_type>(lastPos, bin_cache[ii],
                                                      bin_cache, cache_end,
                                                      bin_sizes, rshift, comp);
      }
    }

    //Casting special-case for floating-point sorting
    template <class RandomAccessIter, class Div_type, class Size_type>
    inline void
    float_sort_rec(RandomAccessIter first, RandomAccessIter last,
                std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
                , size_t *bin_sizes)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last, 
                                                                max, min))
        return;
      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>(
            current++) >> log_divisor) - div_min)]++;
      //The index of the first positive bin
      //Must be divided small enough to fit into an integer
      unsigned first_positive = (div_min < 0) ? unsigned(-div_min) : 0;
      //Resetting if all bins are negative
      if (cache_offset + first_positive > cache_end)
        first_positive = cache_end - cache_offset;
      //Reversing the order of the negative bins
      //Note that because of the negative/positive ordering direction flip
      //We can not depend upon bin order and positions matching up
      //so bin_sizes must be reused to contain the end of the bin
      if (first_positive > 0) {
        bins[first_positive - 1] = first;
        for (int ii = first_positive - 2; ii >= 0; --ii) {
          bins[ii] = first + bin_sizes[ii + 1];
          bin_sizes[ii] += bin_sizes[ii + 1];
        }
        //Handling positives following negatives
        if (first_positive < bin_count) {
          bins[first_positive] = first + bin_sizes[0];
          bin_sizes[first_positive] += bin_sizes[0];
        }
      }
      else
        bins[0] = first;
      for (unsigned u = first_positive; u < bin_count - 1; u++) {
        bins[u + 1] = first + bin_sizes[u];
        bin_sizes[u + 1] += bin_sizes[u];
      }

      //Swap into place
      RandomAccessIter nextbinstart = first;
      for (unsigned u = 0; u < bin_count; ++u) {
        nextbinstart = first + bin_sizes[u];
        inner_float_swap_loop<RandomAccessIter, Div_type>
          (bins, nextbinstart, u, log_divisor, div_min);
      }

      if (!log_divisor)
        return;

      //Handling negative values first
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (int ii = cache_offset + first_positive - 1; 
           ii >= static_cast<int>(cache_offset);
           lastPos = bin_cache[ii--]) {
        size_t count = bin_cache[ii] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[ii]);
        //sort negative values using reversed-bin spreadsort
        else
          negative_float_sort_rec<RandomAccessIter, Div_type, Size_type>
            (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
      }

      for (unsigned u = cache_offset + first_positive; u < cache_end;
          lastPos = bin_cache[u], ++u) {
        size_t count = bin_cache[u] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[u]);
        //sort positive values using normal spreadsort
        else
          positive_float_sort_rec<RandomAccessIter, Div_type, Size_type>
            (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
      }
    }

    //Functor implementation for recursive sorting
    template <class RandomAccessIter, class Div_type, class Right_shift
      , class Size_type>
    inline void
    float_sort_rec(RandomAccessIter first, RandomAccessIter last,
              std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
              , size_t *bin_sizes, Right_shift rshift)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes(first, last, max, min, rshift))
        return;
      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
      //The index of the first positive bin
      unsigned first_positive = (div_min < 0) ? unsigned(-div_min) : 0;
      //Resetting if all bins are negative
      if (cache_offset + first_positive > cache_end)
        first_positive = cache_end - cache_offset;
      //Reversing the order of the negative bins
      //Note that because of the negative/positive ordering direction flip
      //We can not depend upon bin order and positions matching up
      //so bin_sizes must be reused to contain the end of the bin
      if (first_positive > 0) {
        bins[first_positive - 1] = first;
        for (int ii = first_positive - 2; ii >= 0; --ii) {
          bins[ii] = first + bin_sizes[ii + 1];
          bin_sizes[ii] += bin_sizes[ii + 1];
        }
        //Handling positives following negatives
        if (static_cast<unsigned>(first_positive) < bin_count) {
          bins[first_positive] = first + bin_sizes[0];
          bin_sizes[first_positive] += bin_sizes[0];
        }
      }
      else
        bins[0] = first;
      for (unsigned u = first_positive; u < bin_count - 1; u++) {
        bins[u + 1] = first + bin_sizes[u];
        bin_sizes[u + 1] += bin_sizes[u];
      }

      //Swap into place
      RandomAccessIter next_bin_start = first;
      for (unsigned u = 0; u < bin_count; ++u) {
        next_bin_start = first + bin_sizes[u];
        inner_swap_loop<RandomAccessIter, Div_type, Right_shift>
          (bins, next_bin_start, u, rshift, log_divisor, div_min);
      }

      //Return if we've completed bucketsorting
      if (!log_divisor)
        return;

      //Handling negative values first
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (int ii = cache_offset + first_positive - 1; 
           ii >= static_cast<int>(cache_offset);
           lastPos = bin_cache[ii--]) {
        size_t count = bin_cache[ii] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[ii]);
        //sort negative values using reversed-bin spreadsort
        else
          negative_float_sort_rec<RandomAccessIter, Div_type,
            Right_shift, Size_type>(lastPos, bin_cache[ii], bin_cache,
                                    cache_end, bin_sizes, rshift);
      }

      for (unsigned u = cache_offset + first_positive; u < cache_end;
          lastPos = bin_cache[u], ++u) {
        size_t count = bin_cache[u] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[u]);
        //sort positive values using normal spreadsort
        else
          spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Size_type,
                          float_log_mean_bin_size, float_log_min_split_count,
                          float_log_finishing_count>
            (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift);
      }
    }

    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Compare, class Size_type>
    inline void
    float_sort_rec(RandomAccessIter first, RandomAccessIter last,
            std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset,
            size_t *bin_sizes, Right_shift rshift, Compare comp)
    {
      Div_type max, min;
      if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
        return;
      unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
          last - first, rough_log_2_size(Size_type(max - min)));
      Div_type div_min = min >> log_divisor;
      Div_type div_max = max >> log_divisor;
      unsigned bin_count = unsigned(div_max - div_min) + 1;
      unsigned cache_end;
      RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
                                          cache_end, bin_count);

      //Calculating the size of each bin
      for (RandomAccessIter current = first; current != last;)
        bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
      //The index of the first positive bin
      unsigned first_positive = 
        (div_min < 0) ? static_cast<unsigned>(-div_min) : 0;
      //Resetting if all bins are negative
      if (cache_offset + first_positive > cache_end)
        first_positive = cache_end - cache_offset;
      //Reversing the order of the negative bins
      //Note that because of the negative/positive ordering direction flip
      //We can not depend upon bin order and positions matching up
      //so bin_sizes must be reused to contain the end of the bin
      if (first_positive > 0) {
        bins[first_positive - 1] = first;
        for (int ii = first_positive - 2; ii >= 0; --ii) {
          bins[ii] = first + bin_sizes[ii + 1];
          bin_sizes[ii] += bin_sizes[ii + 1];
        }
        //Handling positives following negatives
        if (static_cast<unsigned>(first_positive) < bin_count) {
          bins[first_positive] = first + bin_sizes[0];
          bin_sizes[first_positive] += bin_sizes[0];
        }
      }
      else
        bins[0] = first;
      for (unsigned u = first_positive; u < bin_count - 1; u++) {
        bins[u + 1] = first + bin_sizes[u];
        bin_sizes[u + 1] += bin_sizes[u];
      }

      //Swap into place
      RandomAccessIter next_bin_start = first;
      for (unsigned u = 0; u < bin_count; ++u) {
        next_bin_start = first + bin_sizes[u];
        inner_swap_loop<RandomAccessIter, Div_type, Right_shift>
          (bins, next_bin_start, u, rshift, log_divisor, div_min);
      }

      //Return if we've completed bucketsorting
      if (!log_divisor)
        return;

      //Handling negative values first
      size_t max_count = get_min_count<float_log_mean_bin_size,
                                       float_log_min_split_count,
                                       float_log_finishing_count>(log_divisor);
      RandomAccessIter lastPos = first;
      for (int ii = cache_offset + first_positive - 1; 
           ii >= static_cast<int>(cache_offset);
           lastPos = bin_cache[ii--]) {
        size_t count = bin_cache[ii] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[ii], comp);
        //sort negative values using reversed-bin spreadsort
        else
          negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
                                  Compare, Size_type>(lastPos, bin_cache[ii],
                                                      bin_cache, cache_end,
                                                      bin_sizes, rshift, comp);
      }

      for (unsigned u = cache_offset + first_positive; u < cache_end;
          lastPos = bin_cache[u], ++u) {
        size_t count = bin_cache[u] - lastPos;
        if (count < 2)
          continue;
        if (count < max_count)
          std::sort(lastPos, bin_cache[u], comp);
        //sort positive values using normal spreadsort
        else
          spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
                          Size_type, float_log_mean_bin_size,
                          float_log_min_split_count, float_log_finishing_count>
      (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift, comp);
      }
    }

    //Checking whether the value type is a float, and trying a 32-bit integer
    template <class RandomAccessIter>
    inline typename boost::enable_if_c< sizeof(boost::uint32_t) ==
      sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
      && std::numeric_limits<typename
      std::iterator_traits<RandomAccessIter>::value_type>::is_iec559,
      void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last)
    {
      size_t bin_sizes[1 << max_finishing_splits];
      std::vector<RandomAccessIter> bin_cache;
      float_sort_rec<RandomAccessIter, boost::int32_t, boost::uint32_t>
        (first, last, bin_cache, 0, bin_sizes);
    }

    //Checking whether the value type is a double, and using a 64-bit integer
    template <class RandomAccessIter>
    inline typename boost::enable_if_c< sizeof(boost::uint64_t) ==
      sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
      && std::numeric_limits<typename
      std::iterator_traits<RandomAccessIter>::value_type>::is_iec559,
      void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last)
    {
      size_t bin_sizes[1 << max_finishing_splits];
      std::vector<RandomAccessIter> bin_cache;
      float_sort_rec<RandomAccessIter, boost::int64_t, boost::uint64_t>
        (first, last, bin_cache, 0, bin_sizes);
    }

    template <class RandomAccessIter>
    inline typename boost::disable_if_c< (sizeof(boost::uint64_t) ==
      sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
      || sizeof(boost::uint32_t) ==
      sizeof(typename std::iterator_traits<RandomAccessIter>::value_type))
      && std::numeric_limits<typename
      std::iterator_traits<RandomAccessIter>::value_type>::is_iec559,
      void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last)
    {
      BOOST_STATIC_WARNING(!(sizeof(boost::uint64_t) ==
      sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
      || sizeof(boost::uint32_t) ==
      sizeof(typename std::iterator_traits<RandomAccessIter>::value_type))
      || !std::numeric_limits<typename
      std::iterator_traits<RandomAccessIter>::value_type>::is_iec559);
      std::sort(first, last);
    }

    //These approaches require the user to do the typecast
    //with rshift but default comparision
    template <class RandomAccessIter, class Div_type, class Right_shift>
    inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type),
      void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
               Right_shift rshift)
    {
      size_t bin_sizes[1 << max_finishing_splits];
      std::vector<RandomAccessIter> bin_cache;
      float_sort_rec<RandomAccessIter, Div_type, Right_shift, size_t>
        (first, last, bin_cache, 0, bin_sizes, rshift);
    }

    //maximum integer size with rshift but default comparision
    template <class RandomAccessIter, class Div_type, class Right_shift>
    inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type)
      && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
               Right_shift rshift)
    {
      size_t bin_sizes[1 << max_finishing_splits];
      std::vector<RandomAccessIter> bin_cache;
      float_sort_rec<RandomAccessIter, Div_type, Right_shift, boost::uintmax_t>
        (first, last, bin_cache, 0, bin_sizes, rshift);
    }

    //sizeof(Div_type) doesn't match, so use std::sort
    template <class RandomAccessIter, class Div_type, class Right_shift>
    inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >=
      sizeof(Div_type), void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
               Right_shift rshift)
    {
      BOOST_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
      std::sort(first, last);
    }

    //specialized comparison
    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Compare>
    inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type),
      void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
               Right_shift rshift, Compare comp)
    {
      size_t bin_sizes[1 << max_finishing_splits];
      std::vector<RandomAccessIter> bin_cache;
      float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
        size_t>
        (first, last, bin_cache, 0, bin_sizes, rshift, comp);
    }

    //max-sized integer with specialized comparison
    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Compare>
    inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type)
      && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
               Right_shift rshift, Compare comp)
    {
      size_t bin_sizes[1 << max_finishing_splits];
      std::vector<RandomAccessIter> bin_cache;
      float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
        boost::uintmax_t>
        (first, last, bin_cache, 0, bin_sizes, rshift, comp);
    }

    //sizeof(Div_type) doesn't match, so use std::sort
    template <class RandomAccessIter, class Div_type, class Right_shift,
              class Compare>
    inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >=
      sizeof(Div_type), void >::type
    float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
               Right_shift rshift, Compare comp)
    {
      BOOST_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
      std::sort(first, last, comp);
    }
  }
}
}
}

#endif