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

source code of boost/libs/sort/include/boost/sort/spreadsort/detail/float_sort.hpp