]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |