ceph/src/boost/libs/sort/include/boost/sort/spreadsort/detail/float_sort.hpp

   1 // Details for templated Spreadsort-based float_sort.
   2
   3 //          Copyright Steven J. Ross 2001 - 2014.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 //    (See accompanying file LICENSE_1_0.txt or copy at
   6 //          http://www.boost.org/LICENSE_1_0.txt)
   7
   8 // See http://www.boost.org/libs/sort for library home page.
   9
  10 /*
  11 Some improvements suggested by:
  12 Phil Endecott and Frank Gennari
  13 float_mem_cast fix provided by:
  14 Scott McMurray
  15 */
  16
  17 #ifndef BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP
  18 #define BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP
  19 #include <algorithm>
  20 #include <vector>
  21 #include <limits>
  22 #include <functional>
  23 #include <boost/static_assert.hpp>
  24 #include <boost/serialization/static_warning.hpp>
  25 #include <boost/utility/enable_if.hpp>
  26 #include <boost/sort/spreadsort/detail/constants.hpp>
  27 #include <boost/sort/spreadsort/detail/integer_sort.hpp>
  28 #include <boost/sort/spreadsort/detail/spreadsort_common.hpp>
  29 #include <boost/cstdint.hpp>
  30
  31 namespace boost {
  32 namespace sort {
  33 namespace spreadsort {
  34   namespace detail {
  35     //Casts a RandomAccessIter to the specified integer type
  36     template<class Cast_type, class RandomAccessIter>
  37     inline Cast_type
  38     cast_float_iter(const RandomAccessIter & floatiter)
  39     {
  40       typedef typename std::iterator_traits<RandomAccessIter>::value_type
  41         Data_type;
  42       //Only cast IEEE floating-point numbers, and only to same-sized integers
  43       BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type));
  44       BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559);
  45       BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer);
  46       Cast_type result;
  47       std::memcpy(&result, &(*floatiter), sizeof(Data_type));
  48       return result;
  49     }
  50
  51     // Return true if the list is sorted.  Otherwise, find the minimum and
  52     // maximum.  Values are Right_shifted 0 bits before comparison.
  53     template <class RandomAccessIter, class Div_type, class Right_shift>
  54     inline bool
  55     is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
  56                   Div_type & max, Div_type & min, Right_shift rshift)
  57     {
  58       min = max = rshift(*current, 0);
  59       RandomAccessIter prev = current;
  60       bool sorted = true;
  61       while (++current < last) {
  62         Div_type value = rshift(*current, 0);
  63         sorted &= *current >= *prev;
  64         prev = current;
  65         if (max < value)
  66           max = value;
  67         else if (value < min)
  68           min = value;
  69       }
  70       return sorted;
  71     }
  72
  73     // Return true if the list is sorted.  Otherwise, find the minimum and
  74     // maximum.  Uses comp to check if the data is already sorted.
  75     template <class RandomAccessIter, class Div_type, class Right_shift,
  76               class Compare>
  77     inline bool
  78     is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
  79                                Div_type & max, Div_type & min,
  80                                Right_shift rshift, Compare comp)
  81     {
  82       min = max = rshift(*current, 0);
  83       RandomAccessIter prev = current;
  84       bool sorted = true;
  85       while (++current < last) {
  86         Div_type value = rshift(*current, 0);
  87         sorted &= !comp(*current, *prev);
  88         prev = current;
  89         if (max < value)
  90           max = value;
  91         else if (value < min)
  92           min = value;
  93       }
  94       return sorted;
  95     }
  96
  97     //Specialized swap loops for floating-point casting
  98     template <class RandomAccessIter, class Div_type>
  99     inline void inner_float_swap_loop(RandomAccessIter * bins,
 100                         const RandomAccessIter & nextbinstart, unsigned ii
 101                         , const unsigned log_divisor, const Div_type div_min)
 102     {
 103       RandomAccessIter * local_bin = bins + ii;
 104       for (RandomAccessIter current = *local_bin; current < nextbinstart;
 105           ++current) {
 106         for (RandomAccessIter * target_bin =
 107             (bins + ((cast_float_iter<Div_type, RandomAccessIter>(current) >>
 108                       log_divisor) - div_min));  target_bin != local_bin;
 109           target_bin = bins + ((cast_float_iter<Div_type, RandomAccessIter>
 110                                (current) >> log_divisor) - div_min)) {
 111           typename std::iterator_traits<RandomAccessIter>::value_type tmp;
 112           RandomAccessIter b = (*target_bin)++;
 113           RandomAccessIter * b_bin = bins + ((cast_float_iter<Div_type,
 114                               RandomAccessIter>(b) >> log_divisor) - div_min);
 115           //Three-way swap; if the item to be swapped doesn't belong in the
 116           //current bin, swap it to where it belongs
 117           if (b_bin != local_bin) {
 118             RandomAccessIter c = (*b_bin)++;
 119             tmp = *c;
 120             *c = *b;
 121           }
 122           else
 123             tmp = *b;
 124           *b = *current;
 125           *current = tmp;
 126         }
 127       }
 128       *local_bin = nextbinstart;
 129     }
 130
 131     template <class RandomAccessIter, class Div_type>
 132     inline void float_swap_loop(RandomAccessIter * bins,
 133                           RandomAccessIter & nextbinstart, unsigned ii,
 134                           const size_t *bin_sizes,
 135                           const unsigned log_divisor, const Div_type div_min)
 136     {
 137       nextbinstart += bin_sizes[ii];
 138       inner_float_swap_loop<RandomAccessIter, Div_type>
 139         (bins, nextbinstart, ii, log_divisor, div_min);
 140     }
 141
 142     // Return true if the list is sorted.  Otherwise, find the minimum and
 143     // maximum.  Values are cast to Cast_type before comparison.
 144     template <class RandomAccessIter, class Cast_type>
 145     inline bool
 146     is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
 147                   Cast_type & max, Cast_type & min)
 148     {
 149       min = max = cast_float_iter<Cast_type, RandomAccessIter>(current);
 150       RandomAccessIter prev = current;
 151       bool sorted = true;
 152       while (++current < last) {
 153         Cast_type value = cast_float_iter<Cast_type, RandomAccessIter>(current);
 154         sorted &= *current >= *prev;
 155         prev = current;
 156         if (max < value)
 157           max = value;
 158         else if (value < min)
 159           min = value;
 160       }
 161       return sorted;
 162     }
 163
 164     //Special-case sorting of positive floats with casting
 165     template <class RandomAccessIter, class Div_type, class Size_type>
 166     inline void
 167     positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 168               std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 169               , size_t *bin_sizes)
 170     {
 171       Div_type max, min;
 172       if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
 173                                                                 max, min))
 174         return;
 175       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 176           last - first, rough_log_2_size(Size_type(max - min)));
 177       Div_type div_min = min >> log_divisor;
 178       Div_type div_max = max >> log_divisor;
 179       unsigned bin_count = unsigned(div_max - div_min) + 1;
 180       unsigned cache_end;
 181       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 182                                           cache_end, bin_count);
 183
 184       //Calculating the size of each bin
 185       for (RandomAccessIter current = first; current != last;)
 186         bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>(
 187             current++) >> log_divisor) - div_min)]++;
 188       bins[0] = first;
 189       for (unsigned u = 0; u < bin_count - 1; u++)
 190         bins[u + 1] = bins[u] + bin_sizes[u];
 191
 192
 193       //Swap into place
 194       RandomAccessIter nextbinstart = first;
 195       for (unsigned u = 0; u < bin_count - 1; ++u)
 196         float_swap_loop<RandomAccessIter, Div_type>
 197           (bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
 198       bins[bin_count - 1] = last;
 199
 200       //Return if we've completed bucketsorting
 201       if (!log_divisor)
 202         return;
 203
 204       //Recursing
 205       size_t max_count = get_min_count<float_log_mean_bin_size,
 206                                        float_log_min_split_count,
 207                                        float_log_finishing_count>(log_divisor);
 208       RandomAccessIter lastPos = first;
 209       for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
 210           ++u) {
 211         size_t count = bin_cache[u] - lastPos;
 212         if (count < 2)
 213           continue;
 214         if (count < max_count)
 215           std::sort(lastPos, bin_cache[u]);
 216         else
 217           positive_float_sort_rec<RandomAccessIter, Div_type, Size_type>
 218             (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
 219       }
 220     }
 221
 222     //Sorting negative floats
 223     //Bins are iterated in reverse because max_neg_float = min_neg_int
 224     template <class RandomAccessIter, class Div_type, class Size_type>
 225     inline void
 226     negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 227                         std::vector<RandomAccessIter> &bin_cache,
 228                         unsigned cache_offset, size_t *bin_sizes)
 229     {
 230       Div_type max, min;
 231       if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
 232                                                                  max, min))
 233         return;
 234
 235       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 236           last - first, rough_log_2_size(Size_type(max - min)));
 237       Div_type div_min = min >> log_divisor;
 238       Div_type div_max = max >> log_divisor;
 239       unsigned bin_count = unsigned(div_max - div_min) + 1;
 240       unsigned cache_end;
 241       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 242                                           cache_end, bin_count);
 243
 244       //Calculating the size of each bin
 245       for (RandomAccessIter current = first; current != last;)
 246         bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>(
 247             current++) >> log_divisor) - div_min)]++;
 248       bins[bin_count - 1] = first;
 249       for (int ii = bin_count - 2; ii >= 0; --ii)
 250         bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
 251
 252       //Swap into place
 253       RandomAccessIter nextbinstart = first;
 254       //The last bin will always have the correct elements in it
 255       for (int ii = bin_count - 1; ii > 0; --ii)
 256         float_swap_loop<RandomAccessIter, Div_type>
 257           (bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
 258       //Update the end position because we don't process the last bin
 259       bin_cache[cache_offset] = last;
 260
 261       //Return if we've completed bucketsorting
 262       if (!log_divisor)
 263         return;
 264
 265       //Recursing
 266       size_t max_count = get_min_count<float_log_mean_bin_size,
 267                                        float_log_min_split_count,
 268                                        float_log_finishing_count>(log_divisor);
 269       RandomAccessIter lastPos = first;
 270       for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset);
 271           lastPos = bin_cache[ii], --ii) {
 272         size_t count = bin_cache[ii] - lastPos;
 273         if (count < 2)
 274           continue;
 275         if (count < max_count)
 276           std::sort(lastPos, bin_cache[ii]);
 277         else
 278           negative_float_sort_rec<RandomAccessIter, Div_type, Size_type>
 279             (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
 280       }
 281     }
 282
 283     //Sorting negative floats
 284     //Bins are iterated in reverse order because max_neg_float = min_neg_int
 285     template <class RandomAccessIter, class Div_type, class Right_shift,
 286               class Size_type>
 287     inline void
 288     negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 289               std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 290               , size_t *bin_sizes, Right_shift rshift)
 291     {
 292       Div_type max, min;
 293       if (is_sorted_or_find_extremes(first, last, max, min, rshift))
 294         return;
 295       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 296           last - first, rough_log_2_size(Size_type(max - min)));
 297       Div_type div_min = min >> log_divisor;
 298       Div_type div_max = max >> log_divisor;
 299       unsigned bin_count = unsigned(div_max - div_min) + 1;
 300       unsigned cache_end;
 301       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 302                                           cache_end, bin_count);
 303
 304       //Calculating the size of each bin
 305       for (RandomAccessIter current = first; current != last;)
 306         bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
 307       bins[bin_count - 1] = first;
 308       for (int ii = bin_count - 2; ii >= 0; --ii)
 309         bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
 310
 311       //Swap into place
 312       RandomAccessIter nextbinstart = first;
 313       //The last bin will always have the correct elements in it
 314       for (int ii = bin_count - 1; ii > 0; --ii)
 315         swap_loop<RandomAccessIter, Div_type, Right_shift>
 316           (bins, nextbinstart, ii, rshift, bin_sizes, log_divisor, div_min);
 317       //Update the end position of the unprocessed last bin
 318       bin_cache[cache_offset] = last;
 319
 320       //Return if we've completed bucketsorting
 321       if (!log_divisor)
 322         return;
 323
 324       //Recursing
 325       size_t max_count = get_min_count<float_log_mean_bin_size,
 326                                        float_log_min_split_count,
 327                                        float_log_finishing_count>(log_divisor);
 328       RandomAccessIter lastPos = first;
 329       for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset);
 330           lastPos = bin_cache[ii], --ii) {
 331         size_t count = bin_cache[ii] - lastPos;
 332         if (count < 2)
 333           continue;
 334         if (count < max_count)
 335           std::sort(lastPos, bin_cache[ii]);
 336         else
 337           negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
 338                                   Size_type>
 339             (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift);
 340       }
 341     }
 342
 343     template <class RandomAccessIter, class Div_type, class Right_shift,
 344               class Compare, class Size_type>
 345     inline void
 346     negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 347             std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset,
 348             size_t *bin_sizes, Right_shift rshift, Compare comp)
 349     {
 350       Div_type max, min;
 351       if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
 352         return;
 353       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 354           last - first, rough_log_2_size(Size_type(max - min)));
 355       Div_type div_min = min >> log_divisor;
 356       Div_type div_max = max >> log_divisor;
 357       unsigned bin_count = unsigned(div_max - div_min) + 1;
 358       unsigned cache_end;
 359       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 360                                           cache_end, bin_count);
 361
 362       //Calculating the size of each bin
 363       for (RandomAccessIter current = first; current != last;)
 364         bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
 365       bins[bin_count - 1] = first;
 366       for (int ii = bin_count - 2; ii >= 0; --ii)
 367         bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
 368
 369       //Swap into place
 370       RandomAccessIter nextbinstart = first;
 371       //The last bin will always have the correct elements in it
 372       for (int ii = bin_count - 1; ii > 0; --ii)
 373         swap_loop<RandomAccessIter, Div_type, Right_shift>
 374           (bins, nextbinstart, ii, rshift, bin_sizes, log_divisor, div_min);
 375       //Update the end position of the unprocessed last bin
 376       bin_cache[cache_offset] = last;
 377
 378       //Return if we've completed bucketsorting
 379       if (!log_divisor)
 380         return;
 381
 382       //Recursing
 383       size_t max_count = get_min_count<float_log_mean_bin_size,
 384                                        float_log_min_split_count,
 385                                        float_log_finishing_count>(log_divisor);
 386       RandomAccessIter lastPos = first;
 387       for (int ii = cache_end - 1; ii >= static_cast<int>(cache_offset);
 388           lastPos = bin_cache[ii], --ii) {
 389         size_t count = bin_cache[ii] - lastPos;
 390         if (count < 2)
 391           continue;
 392         if (count < max_count)
 393           std::sort(lastPos, bin_cache[ii], comp);
 394         else
 395           negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
 396                                   Compare, Size_type>(lastPos, bin_cache[ii],
 397                                                       bin_cache, cache_end,
 398                                                       bin_sizes, rshift, comp);
 399       }
 400     }
 401
 402     //Casting special-case for floating-point sorting
 403     template <class RandomAccessIter, class Div_type, class Size_type>
 404     inline void
 405     float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 406                 std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 407                 , size_t *bin_sizes)
 408     {
 409       Div_type max, min;
 410       if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
 411                                                                 max, min))
 412         return;
 413       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 414           last - first, rough_log_2_size(Size_type(max - min)));
 415       Div_type div_min = min >> log_divisor;
 416       Div_type div_max = max >> log_divisor;
 417       unsigned bin_count = unsigned(div_max - div_min) + 1;
 418       unsigned cache_end;
 419       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 420                                           cache_end, bin_count);
 421
 422       //Calculating the size of each bin
 423       for (RandomAccessIter current = first; current != last;)
 424         bin_sizes[unsigned((cast_float_iter<Div_type, RandomAccessIter>(
 425             current++) >> log_divisor) - div_min)]++;
 426       //The index of the first positive bin
 427       //Must be divided small enough to fit into an integer
 428       unsigned first_positive = (div_min < 0) ? unsigned(-div_min) : 0;
 429       //Resetting if all bins are negative
 430       if (cache_offset + first_positive > cache_end)
 431         first_positive = cache_end - cache_offset;
 432       //Reversing the order of the negative bins
 433       //Note that because of the negative/positive ordering direction flip
 434       //We can not depend upon bin order and positions matching up
 435       //so bin_sizes must be reused to contain the end of the bin
 436       if (first_positive > 0) {
 437         bins[first_positive - 1] = first;
 438         for (int ii = first_positive - 2; ii >= 0; --ii) {
 439           bins[ii] = first + bin_sizes[ii + 1];
 440           bin_sizes[ii] += bin_sizes[ii + 1];
 441         }
 442         //Handling positives following negatives
 443         if (first_positive < bin_count) {
 444           bins[first_positive] = first + bin_sizes[0];
 445           bin_sizes[first_positive] += bin_sizes[0];
 446         }
 447       }
 448       else
 449         bins[0] = first;
 450       for (unsigned u = first_positive; u < bin_count - 1; u++) {
 451         bins[u + 1] = first + bin_sizes[u];
 452         bin_sizes[u + 1] += bin_sizes[u];
 453       }
 454
 455       //Swap into place
 456       RandomAccessIter nextbinstart = first;
 457       for (unsigned u = 0; u < bin_count; ++u) {
 458         nextbinstart = first + bin_sizes[u];
 459         inner_float_swap_loop<RandomAccessIter, Div_type>
 460           (bins, nextbinstart, u, log_divisor, div_min);
 461       }
 462
 463       if (!log_divisor)
 464         return;
 465
 466       //Handling negative values first
 467       size_t max_count = get_min_count<float_log_mean_bin_size,
 468                                        float_log_min_split_count,
 469                                        float_log_finishing_count>(log_divisor);
 470       RandomAccessIter lastPos = first;
 471       for (int ii = cache_offset + first_positive - 1;
 472            ii >= static_cast<int>(cache_offset);
 473            lastPos = bin_cache[ii--]) {
 474         size_t count = bin_cache[ii] - lastPos;
 475         if (count < 2)
 476           continue;
 477         if (count < max_count)
 478           std::sort(lastPos, bin_cache[ii]);
 479         //sort negative values using reversed-bin spreadsort
 480         else
 481           negative_float_sort_rec<RandomAccessIter, Div_type, Size_type>
 482             (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
 483       }
 484
 485       for (unsigned u = cache_offset + first_positive; u < cache_end;
 486           lastPos = bin_cache[u], ++u) {
 487         size_t count = bin_cache[u] - lastPos;
 488         if (count < 2)
 489           continue;
 490         if (count < max_count)
 491           std::sort(lastPos, bin_cache[u]);
 492         //sort positive values using normal spreadsort
 493         else
 494           positive_float_sort_rec<RandomAccessIter, Div_type, Size_type>
 495             (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
 496       }
 497     }
 498
 499     //Functor implementation for recursive sorting
 500     template <class RandomAccessIter, class Div_type, class Right_shift
 501       , class Size_type>
 502     inline void
 503     float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 504               std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 505               , size_t *bin_sizes, Right_shift rshift)
 506     {
 507       Div_type max, min;
 508       if (is_sorted_or_find_extremes(first, last, max, min, rshift))
 509         return;
 510       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 511           last - first, rough_log_2_size(Size_type(max - min)));
 512       Div_type div_min = min >> log_divisor;
 513       Div_type div_max = max >> log_divisor;
 514       unsigned bin_count = unsigned(div_max - div_min) + 1;
 515       unsigned cache_end;
 516       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 517                                           cache_end, bin_count);
 518
 519       //Calculating the size of each bin
 520       for (RandomAccessIter current = first; current != last;)
 521         bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
 522       //The index of the first positive bin
 523       unsigned first_positive = (div_min < 0) ? unsigned(-div_min) : 0;
 524       //Resetting if all bins are negative
 525       if (cache_offset + first_positive > cache_end)
 526         first_positive = cache_end - cache_offset;
 527       //Reversing the order of the negative bins
 528       //Note that because of the negative/positive ordering direction flip
 529       //We can not depend upon bin order and positions matching up
 530       //so bin_sizes must be reused to contain the end of the bin
 531       if (first_positive > 0) {
 532         bins[first_positive - 1] = first;
 533         for (int ii = first_positive - 2; ii >= 0; --ii) {
 534           bins[ii] = first + bin_sizes[ii + 1];
 535           bin_sizes[ii] += bin_sizes[ii + 1];
 536         }
 537         //Handling positives following negatives
 538         if (static_cast<unsigned>(first_positive) < bin_count) {
 539           bins[first_positive] = first + bin_sizes[0];
 540           bin_sizes[first_positive] += bin_sizes[0];
 541         }
 542       }
 543       else
 544         bins[0] = first;
 545       for (unsigned u = first_positive; u < bin_count - 1; u++) {
 546         bins[u + 1] = first + bin_sizes[u];
 547         bin_sizes[u + 1] += bin_sizes[u];
 548       }
 549
 550       //Swap into place
 551       RandomAccessIter next_bin_start = first;
 552       for (unsigned u = 0; u < bin_count; ++u) {
 553         next_bin_start = first + bin_sizes[u];
 554         inner_swap_loop<RandomAccessIter, Div_type, Right_shift>
 555           (bins, next_bin_start, u, rshift, log_divisor, div_min);
 556       }
 557
 558       //Return if we've completed bucketsorting
 559       if (!log_divisor)
 560         return;
 561
 562       //Handling negative values first
 563       size_t max_count = get_min_count<float_log_mean_bin_size,
 564                                        float_log_min_split_count,
 565                                        float_log_finishing_count>(log_divisor);
 566       RandomAccessIter lastPos = first;
 567       for (int ii = cache_offset + first_positive - 1;
 568            ii >= static_cast<int>(cache_offset);
 569            lastPos = bin_cache[ii--]) {
 570         size_t count = bin_cache[ii] - lastPos;
 571         if (count < 2)
 572           continue;
 573         if (count < max_count)
 574           std::sort(lastPos, bin_cache[ii]);
 575         //sort negative values using reversed-bin spreadsort
 576         else
 577           negative_float_sort_rec<RandomAccessIter, Div_type,
 578             Right_shift, Size_type>(lastPos, bin_cache[ii], bin_cache,
 579                                     cache_end, bin_sizes, rshift);
 580       }
 581
 582       for (unsigned u = cache_offset + first_positive; u < cache_end;
 583           lastPos = bin_cache[u], ++u) {
 584         size_t count = bin_cache[u] - lastPos;
 585         if (count < 2)
 586           continue;
 587         if (count < max_count)
 588           std::sort(lastPos, bin_cache[u]);
 589         //sort positive values using normal spreadsort
 590         else
 591           spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Size_type,
 592                           float_log_mean_bin_size, float_log_min_split_count,
 593                           float_log_finishing_count>
 594             (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift);
 595       }
 596     }
 597
 598     template <class RandomAccessIter, class Div_type, class Right_shift,
 599               class Compare, class Size_type>
 600     inline void
 601     float_sort_rec(RandomAccessIter first, RandomAccessIter last,
 602             std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset,
 603             size_t *bin_sizes, Right_shift rshift, Compare comp)
 604     {
 605       Div_type max, min;
 606       if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
 607         return;
 608       unsigned log_divisor = get_log_divisor<float_log_mean_bin_size>(
 609           last - first, rough_log_2_size(Size_type(max - min)));
 610       Div_type div_min = min >> log_divisor;
 611       Div_type div_max = max >> log_divisor;
 612       unsigned bin_count = unsigned(div_max - div_min) + 1;
 613       unsigned cache_end;
 614       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 615                                           cache_end, bin_count);
 616
 617       //Calculating the size of each bin
 618       for (RandomAccessIter current = first; current != last;)
 619         bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
 620       //The index of the first positive bin
 621       unsigned first_positive =
 622         (div_min < 0) ? static_cast<unsigned>(-div_min) : 0;
 623       //Resetting if all bins are negative
 624       if (cache_offset + first_positive > cache_end)
 625         first_positive = cache_end - cache_offset;
 626       //Reversing the order of the negative bins
 627       //Note that because of the negative/positive ordering direction flip
 628       //We can not depend upon bin order and positions matching up
 629       //so bin_sizes must be reused to contain the end of the bin
 630       if (first_positive > 0) {
 631         bins[first_positive - 1] = first;
 632         for (int ii = first_positive - 2; ii >= 0; --ii) {
 633           bins[ii] = first + bin_sizes[ii + 1];
 634           bin_sizes[ii] += bin_sizes[ii + 1];
 635         }
 636         //Handling positives following negatives
 637         if (static_cast<unsigned>(first_positive) < bin_count) {
 638           bins[first_positive] = first + bin_sizes[0];
 639           bin_sizes[first_positive] += bin_sizes[0];
 640         }
 641       }
 642       else
 643         bins[0] = first;
 644       for (unsigned u = first_positive; u < bin_count - 1; u++) {
 645         bins[u + 1] = first + bin_sizes[u];
 646         bin_sizes[u + 1] += bin_sizes[u];
 647       }
 648
 649       //Swap into place
 650       RandomAccessIter next_bin_start = first;
 651       for (unsigned u = 0; u < bin_count; ++u) {
 652         next_bin_start = first + bin_sizes[u];
 653         inner_swap_loop<RandomAccessIter, Div_type, Right_shift>
 654           (bins, next_bin_start, u, rshift, log_divisor, div_min);
 655       }
 656
 657       //Return if we've completed bucketsorting
 658       if (!log_divisor)
 659         return;
 660
 661       //Handling negative values first
 662       size_t max_count = get_min_count<float_log_mean_bin_size,
 663                                        float_log_min_split_count,
 664                                        float_log_finishing_count>(log_divisor);
 665       RandomAccessIter lastPos = first;
 666       for (int ii = cache_offset + first_positive - 1;
 667            ii >= static_cast<int>(cache_offset);
 668            lastPos = bin_cache[ii--]) {
 669         size_t count = bin_cache[ii] - lastPos;
 670         if (count < 2)
 671           continue;
 672         if (count < max_count)
 673           std::sort(lastPos, bin_cache[ii], comp);
 674         //sort negative values using reversed-bin spreadsort
 675         else
 676           negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
 677                                   Compare, Size_type>(lastPos, bin_cache[ii],
 678                                                       bin_cache, cache_end,
 679                                                       bin_sizes, rshift, comp);
 680       }
 681
 682       for (unsigned u = cache_offset + first_positive; u < cache_end;
 683           lastPos = bin_cache[u], ++u) {
 684         size_t count = bin_cache[u] - lastPos;
 685         if (count < 2)
 686           continue;
 687         if (count < max_count)
 688           std::sort(lastPos, bin_cache[u], comp);
 689         //sort positive values using normal spreadsort
 690         else
 691           spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
 692                           Size_type, float_log_mean_bin_size,
 693                           float_log_min_split_count, float_log_finishing_count>
 694       (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift, comp);
 695       }
 696     }
 697
 698     //Checking whether the value type is a float, and trying a 32-bit integer
 699     template <class RandomAccessIter>
 700     inline typename boost::enable_if_c< sizeof(boost::uint32_t) ==
 701       sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
 702       && std::numeric_limits<typename
 703       std::iterator_traits<RandomAccessIter>::value_type>::is_iec559,
 704       void >::type
 705     float_sort(RandomAccessIter first, RandomAccessIter last)
 706     {
 707       size_t bin_sizes[1 << max_finishing_splits];
 708       std::vector<RandomAccessIter> bin_cache;
 709       float_sort_rec<RandomAccessIter, boost::int32_t, boost::uint32_t>
 710         (first, last, bin_cache, 0, bin_sizes);
 711     }
 712
 713     //Checking whether the value type is a double, and using a 64-bit integer
 714     template <class RandomAccessIter>
 715     inline typename boost::enable_if_c< sizeof(boost::uint64_t) ==
 716       sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
 717       && std::numeric_limits<typename
 718       std::iterator_traits<RandomAccessIter>::value_type>::is_iec559,
 719       void >::type
 720     float_sort(RandomAccessIter first, RandomAccessIter last)
 721     {
 722       size_t bin_sizes[1 << max_finishing_splits];
 723       std::vector<RandomAccessIter> bin_cache;
 724       float_sort_rec<RandomAccessIter, boost::int64_t, boost::uint64_t>
 725         (first, last, bin_cache, 0, bin_sizes);
 726     }
 727
 728     template <class RandomAccessIter>
 729     inline typename boost::disable_if_c< (sizeof(boost::uint64_t) ==
 730       sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
 731       || sizeof(boost::uint32_t) ==
 732       sizeof(typename std::iterator_traits<RandomAccessIter>::value_type))
 733       && std::numeric_limits<typename
 734       std::iterator_traits<RandomAccessIter>::value_type>::is_iec559,
 735       void >::type
 736     float_sort(RandomAccessIter first, RandomAccessIter last)
 737     {
 738       BOOST_STATIC_WARNING(!(sizeof(boost::uint64_t) ==
 739       sizeof(typename std::iterator_traits<RandomAccessIter>::value_type)
 740       || sizeof(boost::uint32_t) ==
 741       sizeof(typename std::iterator_traits<RandomAccessIter>::value_type))
 742       || !std::numeric_limits<typename
 743       std::iterator_traits<RandomAccessIter>::value_type>::is_iec559);
 744       std::sort(first, last);
 745     }
 746
 747     //These approaches require the user to do the typecast
 748     //with rshift but default comparision
 749     template <class RandomAccessIter, class Div_type, class Right_shift>
 750     inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type),
 751       void >::type
 752     float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 753                Right_shift rshift)
 754     {
 755       size_t bin_sizes[1 << max_finishing_splits];
 756       std::vector<RandomAccessIter> bin_cache;
 757       float_sort_rec<RandomAccessIter, Div_type, Right_shift, size_t>
 758         (first, last, bin_cache, 0, bin_sizes, rshift);
 759     }
 760
 761     //maximum integer size with rshift but default comparision
 762     template <class RandomAccessIter, class Div_type, class Right_shift>
 763     inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type)
 764       && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type
 765     float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 766                Right_shift rshift)
 767     {
 768       size_t bin_sizes[1 << max_finishing_splits];
 769       std::vector<RandomAccessIter> bin_cache;
 770       float_sort_rec<RandomAccessIter, Div_type, Right_shift, boost::uintmax_t>
 771         (first, last, bin_cache, 0, bin_sizes, rshift);
 772     }
 773
 774     //sizeof(Div_type) doesn't match, so use std::sort
 775     template <class RandomAccessIter, class Div_type, class Right_shift>
 776     inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >=
 777       sizeof(Div_type), void >::type
 778     float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 779                Right_shift rshift)
 780     {
 781       BOOST_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
 782       std::sort(first, last);
 783     }
 784
 785     //specialized comparison
 786     template <class RandomAccessIter, class Div_type, class Right_shift,
 787               class Compare>
 788     inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type),
 789       void >::type
 790     float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 791                Right_shift rshift, Compare comp)
 792     {
 793       size_t bin_sizes[1 << max_finishing_splits];
 794       std::vector<RandomAccessIter> bin_cache;
 795       float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
 796         size_t>
 797         (first, last, bin_cache, 0, bin_sizes, rshift, comp);
 798     }
 799
 800     //max-sized integer with specialized comparison
 801     template <class RandomAccessIter, class Div_type, class Right_shift,
 802               class Compare>
 803     inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type)
 804       && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type
 805     float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 806                Right_shift rshift, Compare comp)
 807     {
 808       size_t bin_sizes[1 << max_finishing_splits];
 809       std::vector<RandomAccessIter> bin_cache;
 810       float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
 811         boost::uintmax_t>
 812         (first, last, bin_cache, 0, bin_sizes, rshift, comp);
 813     }
 814
 815     //sizeof(Div_type) doesn't match, so use std::sort
 816     template <class RandomAccessIter, class Div_type, class Right_shift,
 817               class Compare>
 818     inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >=
 819       sizeof(Div_type), void >::type
 820     float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 821                Right_shift rshift, Compare comp)
 822     {
 823       BOOST_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
 824       std::sort(first, last, comp);
 825     }
 826   }
 827 }
 828 }
 829 }
 830
 831 #endif