215 /// \param last The end of the given range. |
215 /// \param last The end of the given range. |
216 /// \param functor An adaptible unary function or a normal function |
216 /// \param functor An adaptible unary function or a normal function |
217 /// which maps the items to any integer type which can be either |
217 /// which maps the items to any integer type which can be either |
218 /// signed or unsigned. |
218 /// signed or unsigned. |
219 /// |
219 /// |
220 /// \sa counterSort() |
220 /// \sa stableRadixSort() |
221 template <typename Iterator, typename Functor> |
221 template <typename Iterator, typename Functor> |
222 void radixSort(Iterator first, Iterator last, Functor functor) { |
222 void radixSort(Iterator first, Iterator last, Functor functor) { |
223 using namespace _radix_sort_bits; |
223 using namespace _radix_sort_bits; |
224 typedef typename Functor::result_type Value; |
224 typedef typename Functor::result_type Value; |
225 RadixSortSelector<Value>::sort(first, last, functor); |
225 RadixSortSelector<Value>::sort(first, last, functor); |
262 unsigned char valueByte(Value value, int byte) { |
262 unsigned char valueByte(Value value, int byte) { |
263 return value >> (std::numeric_limits<unsigned char>::digits * byte); |
263 return value >> (std::numeric_limits<unsigned char>::digits * byte); |
264 } |
264 } |
265 |
265 |
266 template <typename Functor, typename Key> |
266 template <typename Functor, typename Key> |
267 void counterIntroSort(Key *first, Key *last, Key *target, |
267 void stableRadixIntroSort(Key *first, Key *last, Key *target, |
268 int byte, Functor functor) { |
268 int byte, Functor functor) { |
269 const int size = |
269 const int size = |
270 unsigned(std::numeric_limits<unsigned char>::max()) + 1; |
270 unsigned(std::numeric_limits<unsigned char>::max()) + 1; |
271 std::vector<int> counter(size); |
271 std::vector<int> counter(size); |
272 for (int i = 0; i < size; ++i) { |
272 for (int i = 0; i < size; ++i) { |
273 counter[i] = 0; |
273 counter[i] = 0; |
333 try { |
333 try { |
334 bool dir = true; |
334 bool dir = true; |
335 std::copy(first, last, buffer); |
335 std::copy(first, last, buffer); |
336 for (int i = 0; i < int(sizeof(Value)) - 1; ++i) { |
336 for (int i = 0; i < int(sizeof(Value)) - 1; ++i) { |
337 if (dir) { |
337 if (dir) { |
338 counterIntroSort(buffer, buffer + length, buffer + length, |
338 stableRadixIntroSort(buffer, buffer + length, buffer + length, |
339 i, functor); |
339 i, functor); |
340 } else { |
340 } else { |
341 counterIntroSort(buffer + length, buffer + 2 * length, buffer, |
341 stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer, |
342 i, functor); |
342 i, functor); |
343 } |
343 } |
344 dir = !dir; |
344 dir = !dir; |
345 } |
345 } |
346 if (dir) { |
346 if (dir) { |
347 signedCounterIntroSort(buffer, buffer + length, buffer + length, |
347 signedStableRadixIntroSort(buffer, buffer + length, buffer + length, |
348 sizeof(Value) - 1, functor); |
348 sizeof(Value) - 1, functor); |
349 std::copy(buffer + length, buffer + 2 * length, first); |
349 std::copy(buffer + length, buffer + 2 * length, first); |
350 } else { |
350 } else { |
351 signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer, |
351 signedStableRadixIntroSort(buffer + length, buffer + 2 * length, |
352 sizeof(Value) - 1, functor); |
352 buffer, sizeof(Value) - 1, functor); |
353 std::copy(buffer, buffer + length, first); |
353 std::copy(buffer, buffer + length, first); |
354 } |
354 } |
355 } catch (...) { |
355 } catch (...) { |
356 allocator.deallocate(buffer, 2 * length); |
356 allocator.deallocate(buffer, 2 * length); |
357 throw; |
357 throw; |
358 } |
358 } |
359 allocator.deallocate(buffer, 2 * length); |
359 allocator.deallocate(buffer, 2 * length); |
360 } |
360 } |
361 |
361 |
362 template <typename Value, typename Iterator, typename Functor> |
362 template <typename Value, typename Iterator, typename Functor> |
363 void counterUnsignedSort(Iterator first, Iterator last, Functor functor) { |
363 void stableRadixUnsignedSort(Iterator first, Iterator last, |
|
364 Functor functor) { |
364 if (first == last) return; |
365 if (first == last) return; |
365 typedef typename std::iterator_traits<Iterator>::value_type Key; |
366 typedef typename std::iterator_traits<Iterator>::value_type Key; |
366 typedef std::allocator<Key> Allocator; |
367 typedef std::allocator<Key> Allocator; |
367 Allocator allocator; |
368 Allocator allocator; |
368 |
369 |
371 try { |
372 try { |
372 bool dir = true; |
373 bool dir = true; |
373 std::copy(first, last, buffer); |
374 std::copy(first, last, buffer); |
374 for (int i = 0; i < int(sizeof(Value)); ++i) { |
375 for (int i = 0; i < int(sizeof(Value)); ++i) { |
375 if (dir) { |
376 if (dir) { |
376 counterIntroSort(buffer, buffer + length, |
377 stableRadixIntroSort(buffer, buffer + length, |
377 buffer + length, i, functor); |
378 buffer + length, i, functor); |
378 } else { |
379 } else { |
379 counterIntroSort(buffer + length, buffer + 2 * length, |
380 stableRadixIntroSort(buffer + length, buffer + 2 * length, |
380 buffer, i, functor); |
381 buffer, i, functor); |
381 } |
382 } |
382 dir = !dir; |
383 dir = !dir; |
383 } |
384 } |
384 if (dir) { |
385 if (dir) { |
385 std::copy(buffer, buffer + length, first); |
386 std::copy(buffer, buffer + length, first); |
395 |
396 |
396 |
397 |
397 |
398 |
398 template <typename Value, |
399 template <typename Value, |
399 bool sign = std::numeric_limits<Value>::is_signed > |
400 bool sign = std::numeric_limits<Value>::is_signed > |
400 struct CounterSortSelector { |
401 struct StableRadixSortSelector { |
401 template <typename Iterator, typename Functor> |
402 template <typename Iterator, typename Functor> |
402 static void sort(Iterator first, Iterator last, Functor functor) { |
403 static void sort(Iterator first, Iterator last, Functor functor) { |
403 counterSignedSort<Value>(first, last, functor); |
404 stableRadixSignedSort<Value>(first, last, functor); |
404 } |
405 } |
405 }; |
406 }; |
406 |
407 |
407 template <typename Value> |
408 template <typename Value> |
408 struct CounterSortSelector<Value, false> { |
409 struct StableRadixSortSelector<Value, false> { |
409 template <typename Iterator, typename Functor> |
410 template <typename Iterator, typename Functor> |
410 static void sort(Iterator first, Iterator last, Functor functor) { |
411 static void sort(Iterator first, Iterator last, Functor functor) { |
411 counterUnsignedSort<Value>(first, last, functor); |
412 stableRadixUnsignedSort<Value>(first, last, functor); |
412 } |
413 } |
413 }; |
414 }; |
414 |
415 |
415 } |
416 } |
416 |
417 |
421 /// |
422 /// |
422 /// This function sorts an STL compatible range into ascending |
423 /// This function sorts an STL compatible range into ascending |
423 /// order according to an integer mapping in the same as radixSort() does. |
424 /// order according to an integer mapping in the same as radixSort() does. |
424 /// |
425 /// |
425 /// This sorting algorithm is stable, i.e. the order of two equal |
426 /// This sorting algorithm is stable, i.e. the order of two equal |
426 /// element remains the same after the sorting. |
427 /// elements remains the same after the sorting. |
427 /// |
428 /// |
428 /// This sort algorithm use a radix forward sort on the |
429 /// This sort algorithm use a radix forward sort on the |
429 /// bytes of the integer number. The algorithm sorts the items |
430 /// bytes of the integer number. The algorithm sorts the items |
430 /// byte-by-byte. First, it counts how many times a byte value occurs |
431 /// byte-by-byte. First, it counts how many times a byte value occurs |
431 /// in the container, then it copies the corresponding items to |
432 /// in the container, then it copies the corresponding items to |
442 /// \param functor An adaptible unary function or a normal function |
443 /// \param functor An adaptible unary function or a normal function |
443 /// which maps the items to any integer type which can be either |
444 /// which maps the items to any integer type which can be either |
444 /// signed or unsigned. |
445 /// signed or unsigned. |
445 /// \sa radixSort() |
446 /// \sa radixSort() |
446 template <typename Iterator, typename Functor> |
447 template <typename Iterator, typename Functor> |
447 void counterSort(Iterator first, Iterator last, Functor functor) { |
448 void stableRadixSort(Iterator first, Iterator last, Functor functor) { |
448 using namespace _radix_sort_bits; |
449 using namespace _radix_sort_bits; |
449 typedef typename Functor::result_type Value; |
450 typedef typename Functor::result_type Value; |
450 CounterSortSelector<Value>::sort(first, last, functor); |
451 StableRadixSortSelector<Value>::sort(first, last, functor); |
451 } |
452 } |
452 |
453 |
453 template <typename Iterator, typename Value, typename Key> |
454 template <typename Iterator, typename Value, typename Key> |
454 void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) { |
455 void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) { |
455 using namespace _radix_sort_bits; |
456 using namespace _radix_sort_bits; |
456 CounterSortSelector<Value>::sort(first, last, functor); |
457 StableRadixSortSelector<Value>::sort(first, last, functor); |
457 } |
458 } |
458 |
459 |
459 template <typename Iterator, typename Value, typename Key> |
460 template <typename Iterator, typename Value, typename Key> |
460 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) { |
461 void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) { |
461 using namespace _radix_sort_bits; |
462 using namespace _radix_sort_bits; |
462 CounterSortSelector<Value>::sort(first, last, functor); |
463 StableRadixSortSelector<Value>::sort(first, last, functor); |
463 } |
464 } |
464 |
465 |
465 template <typename Iterator, typename Value, typename Key> |
466 template <typename Iterator, typename Value, typename Key> |
466 void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) { |
467 void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) { |
467 using namespace _radix_sort_bits; |
468 using namespace _radix_sort_bits; |
468 CounterSortSelector<Value>::sort(first, last, functor); |
469 StableRadixSortSelector<Value>::sort(first, last, functor); |
469 } |
470 } |
470 |
471 |
471 template <typename Iterator, typename Value, typename Key> |
472 template <typename Iterator, typename Value, typename Key> |
472 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { |
473 void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { |
473 using namespace _radix_sort_bits; |
474 using namespace _radix_sort_bits; |
474 CounterSortSelector<Value>::sort(first, last, functor); |
475 StableRadixSortSelector<Value>::sort(first, last, functor); |
475 } |
476 } |
476 |
477 |
477 template <typename Iterator> |
478 template <typename Iterator> |
478 void counterSort(Iterator first, Iterator last) { |
479 void stableRadixSort(Iterator first, Iterator last) { |
479 using namespace _radix_sort_bits; |
480 using namespace _radix_sort_bits; |
480 typedef typename std::iterator_traits<Iterator>::value_type Value; |
481 typedef typename std::iterator_traits<Iterator>::value_type Value; |
481 CounterSortSelector<Value>::sort(first, last, Identity<Value>()); |
482 StableRadixSortSelector<Value>::sort(first, last, Identity<Value>()); |
482 } |
483 } |
483 |
484 |
484 } |
485 } |
485 |
486 |
486 #endif |
487 #endif |