1 // Details for templated Spreadsort-based float_sort.
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)
8 // See http://www.boost.org/libs/sort for library home page.
11 Some improvements suggested by:
12 Phil Endecott and Frank Gennari
13 float_mem_cast fix provided by:
17 #ifndef BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP
18 #define BOOST_SORT_SPREADSORT_DETAIL_FLOAT_SORT_HPP
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>
33 namespace spreadsort {
35 //Casts a RandomAccessIter to the specified integer type
36 template<class Cast_type, class RandomAccessIter>
38 cast_float_iter(const RandomAccessIter & floatiter)
40 typedef typename std::iterator_traits<RandomAccessIter>::value_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);
47 std::memcpy(&result, &(*floatiter), sizeof(Data_type));
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>
55 is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
56 Div_type & max, Div_type & min, Right_shift rshift)
58 min = max = rshift(*current, 0);
59 RandomAccessIter prev = current;
61 while (++current < last) {
62 Div_type value = rshift(*current, 0);
63 sorted &= *current >= *prev;
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,
78 is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
79 Div_type & max, Div_type & min,
80 Right_shift rshift, Compare comp)
82 min = max = rshift(*current, 0);
83 RandomAccessIter prev = current;
85 while (++current < last) {
86 Div_type value = rshift(*current, 0);
87 sorted &= !comp(*current, *prev);
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)
103 RandomAccessIter * local_bin = bins + ii;
104 for (RandomAccessIter current = *local_bin; current < nextbinstart;
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)++;
128 *local_bin = nextbinstart;
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)
137 nextbinstart += bin_sizes[ii];
138 inner_float_swap_loop<RandomAccessIter, Div_type>
139 (bins, nextbinstart, ii, log_divisor, div_min);
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>
146 is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
147 Cast_type & max, Cast_type & min)
149 min = max = cast_float_iter<Cast_type, RandomAccessIter>(current);
150 RandomAccessIter prev = current;
152 while (++current < last) {
153 Cast_type value = cast_float_iter<Cast_type, RandomAccessIter>(current);
154 sorted &= *current >= *prev;
158 else if (value < min)
164 //Special-case sorting of positive floats with casting
165 template <class RandomAccessIter, class Div_type, class Size_type>
167 positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
168 std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
172 if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
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;
181 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
182 cache_end, bin_count);
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)]++;
189 for (unsigned u = 0; u < bin_count - 1; u++)
190 bins[u + 1] = bins[u] + bin_sizes[u];
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;
200 //Return if we've completed bucketsorting
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],
211 size_t count = bin_cache[u] - lastPos;
214 if (count < max_count)
215 std::sort(lastPos, bin_cache[u]);
217 positive_float_sort_rec<RandomAccessIter, Div_type, Size_type>
218 (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
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>
226 negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last,
227 std::vector<RandomAccessIter> &bin_cache,
228 unsigned cache_offset, size_t *bin_sizes)
231 if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
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;
241 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
242 cache_end, bin_count);
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];
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;
261 //Return if we've completed bucketsorting
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;
275 if (count < max_count)
276 std::sort(lastPos, bin_cache[ii]);
278 negative_float_sort_rec<RandomAccessIter, Div_type, Size_type>
279 (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
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,
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)
293 if (is_sorted_or_find_extremes(first, last, max, min, rshift))
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;
301 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
302 cache_end, bin_count);
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];
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;
320 //Return if we've completed bucketsorting
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;
334 if (count < max_count)
335 std::sort(lastPos, bin_cache[ii]);
337 negative_float_sort_rec<RandomAccessIter, Div_type, Right_shift,
339 (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, rshift);
343 template <class RandomAccessIter, class Div_type, class Right_shift,
344 class Compare, class Size_type>
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)
351 if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
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;
359 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
360 cache_end, bin_count);
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];
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;
378 //Return if we've completed bucketsorting
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;
392 if (count < max_count)
393 std::sort(lastPos, bin_cache[ii], comp);
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);
402 //Casting special-case for floating-point sorting
403 template <class RandomAccessIter, class Div_type, class Size_type>
405 float_sort_rec(RandomAccessIter first, RandomAccessIter last,
406 std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
410 if (is_sorted_or_find_extremes<RandomAccessIter, Div_type>(first, last,
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;
419 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
420 cache_end, bin_count);
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];
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];
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];
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);
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;
477 if (count < max_count)
478 std::sort(lastPos, bin_cache[ii]);
479 //sort negative values using reversed-bin spreadsort
481 negative_float_sort_rec<RandomAccessIter, Div_type, Size_type>
482 (lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
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;
490 if (count < max_count)
491 std::sort(lastPos, bin_cache[u]);
492 //sort positive values using normal spreadsort
494 positive_float_sort_rec<RandomAccessIter, Div_type, Size_type>
495 (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
499 //Functor implementation for recursive sorting
500 template <class RandomAccessIter, class Div_type, class Right_shift
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)
508 if (is_sorted_or_find_extremes(first, last, max, min, rshift))
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;
516 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
517 cache_end, bin_count);
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];
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];
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];
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);
558 //Return if we've completed bucketsorting
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;
573 if (count < max_count)
574 std::sort(lastPos, bin_cache[ii]);
575 //sort negative values using reversed-bin spreadsort
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);
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;
587 if (count < max_count)
588 std::sort(lastPos, bin_cache[u]);
589 //sort positive values using normal spreadsort
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);
598 template <class RandomAccessIter, class Div_type, class Right_shift,
599 class Compare, class Size_type>
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)
606 if (is_sorted_or_find_extremes(first, last, max, min, rshift, comp))
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;
614 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
615 cache_end, bin_count);
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];
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];
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];
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);
657 //Return if we've completed bucketsorting
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;
672 if (count < max_count)
673 std::sort(lastPos, bin_cache[ii], comp);
674 //sort negative values using reversed-bin spreadsort
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);
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;
687 if (count < max_count)
688 std::sort(lastPos, bin_cache[u], comp);
689 //sort positive values using normal spreadsort
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);
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,
705 float_sort(RandomAccessIter first, RandomAccessIter last)
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);
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,
720 float_sort(RandomAccessIter first, RandomAccessIter last)
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);
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,
736 float_sort(RandomAccessIter first, RandomAccessIter last)
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);
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),
752 float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
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);
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,
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);
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,
781 BOOST_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
782 std::sort(first, last);
785 //specialized comparison
786 template <class RandomAccessIter, class Div_type, class Right_shift,
788 inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type),
790 float_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
791 Right_shift rshift, Compare comp)
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,
797 (first, last, bin_cache, 0, bin_sizes, rshift, comp);
800 //max-sized integer with specialized comparison
801 template <class RandomAccessIter, class Div_type, class Right_shift,
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)
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,
812 (first, last, bin_cache, 0, bin_sizes, rshift, comp);
815 //sizeof(Div_type) doesn't match, so use std::sort
816 template <class RandomAccessIter, class Div_type, class Right_shift,
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)
823 BOOST_STATIC_WARNING(sizeof(boost::uintmax_t) >= sizeof(Div_type));
824 std::sort(first, last, comp);