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/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 30 namespace boost { 31 namespace sort { 32 namespace spreadsort { 33 namespace detail { 34 //Casts a RandomAccessIter to the specified integer type 35 template<class Cast_type, class RandomAccessIter> 36 inline Cast_type cast_float_iter(const RandomAccessIter & floatiter)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(&result, &(*floatiter), 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 is_sorted_or_find_extremes(RandomAccessIter current,RandomAccessIter last,Div_type & max,Div_type & min,Right_shift rshift)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 is_sorted_or_find_extremes(RandomAccessIter current,RandomAccessIter last,Div_type & max,Div_type & min,Right_shift rshift,Compare comp)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> inner_float_swap_loop(RandomAccessIter * bins,const RandomAccessIter & nextbinstart,unsigned ii,const unsigned log_divisor,const Div_type div_min)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> float_swap_loop(RandomAccessIter * bins,RandomAccessIter & nextbinstart,unsigned ii,const size_t * bin_sizes,const unsigned log_divisor,const Div_type div_min)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 is_sorted_or_find_extremes(RandomAccessIter current,RandomAccessIter last,Cast_type & max,Cast_type & min)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 positive_float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes)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_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 negative_float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes)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_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 negative_float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes,Right_shift rshift)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_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 negative_float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes,Right_shift rshift,Compare comp)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_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 float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes)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 - min))); 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_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 float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes,Right_shift rshift)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 - min))); 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_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 float_sort_rec(RandomAccessIter first,RandomAccessIter last,std::vector<RandomAccessIter> & bin_cache,unsigned cache_offset,size_t * bin_sizes,Right_shift rshift,Compare comp)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 - min))); 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_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 float_sort(RandomAccessIter first,RandomAccessIter last)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 float_sort(RandomAccessIter first,RandomAccessIter last)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 float_sort(RandomAccessIter first,RandomAccessIter last)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 float_sort(RandomAccessIter first,RandomAccessIter last,Div_type,Right_shift rshift)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_STATIC_ASSERT(sizeof(boost::uintmax_t) >= sizeof(Div_type)); 781 boost::sort::pdqsort(first, last); 782 } 783 784 //specialized comparison 785 template <class RandomAccessIter, class Div_type, class Right_shift, 786 class Compare> 787 inline typename boost::enable_if_c< sizeof(size_t) >= sizeof(Div_type), 788 void >::type 789 float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, 790 Right_shift rshift, Compare comp) 791 { 792 size_t bin_sizes[1 << max_finishing_splits]; 793 std::vector<RandomAccessIter> bin_cache; 794 float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare, 795 size_t> 796 (first, last, bin_cache, 0, bin_sizes, rshift, comp); 797 } 798 799 //max-sized integer with specialized comparison 800 template <class RandomAccessIter, class Div_type, class Right_shift, 801 class Compare> 802 inline typename boost::enable_if_c< sizeof(size_t) < sizeof(Div_type) 803 && sizeof(boost::uintmax_t) >= sizeof(Div_type), void >::type float_sort(RandomAccessIter first,RandomAccessIter last,Div_type,Right_shift rshift,Compare comp)804 float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, 805 Right_shift rshift, Compare comp) 806 { 807 size_t bin_sizes[1 << max_finishing_splits]; 808 std::vector<RandomAccessIter> bin_cache; 809 float_sort_rec<RandomAccessIter, Div_type, Right_shift, Compare, 810 boost::uintmax_t> 811 (first, last, bin_cache, 0, bin_sizes, rshift, comp); 812 } 813 814 //sizeof(Div_type) doesn't match, so use boost::sort::pdqsort 815 template <class RandomAccessIter, class Div_type, class Right_shift, 816 class Compare> 817 inline typename boost::disable_if_c< sizeof(boost::uintmax_t) >= 818 sizeof(Div_type), void >::type 819 float_sort(RandomAccessIter first, RandomAccessIter last, Div_type, 820 Right_shift rshift, Compare comp) 821 { 822 BOOST_STATIC_ASSERT(sizeof(boost::uintmax_t) >= sizeof(Div_type)); 823 boost::sort::pdqsort(first, last, comp); 824 } 825 } 826 } 827 } 828 } 829 830 #endif 831