Changeset 466:de16f1f2d228 in lemon
 Timestamp:
 12/02/08 23:15:43 (11 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/radix_sort.h
r465 r466 218 218 /// signed or unsigned. 219 219 /// 220 /// \sa counterSort()220 /// \sa stableRadixSort() 221 221 template <typename Iterator, typename Functor> 222 222 void radixSort(Iterator first, Iterator last, Functor functor) { … … 265 265 266 266 template <typename Functor, typename Key> 267 void counterIntroSort(Key *first, Key *last, Key *target,268 int byte, Functor functor) {267 void stableRadixIntroSort(Key *first, Key *last, Key *target, 268 int byte, Functor functor) { 269 269 const int size = 270 270 unsigned(std::numeric_limits<unsigned char>::max()) + 1; … … 291 291 292 292 template <typename Functor, typename Key> 293 void signed CounterIntroSort(Key *first, Key *last, Key *target,294 int byte, Functor functor) {293 void signedStableRadixIntroSort(Key *first, Key *last, Key *target, 294 int byte, Functor functor) { 295 295 const int size = 296 296 unsigned(std::numeric_limits<unsigned char>::max()) + 1; … … 323 323 324 324 template <typename Value, typename Iterator, typename Functor> 325 void counterSignedSort(Iterator first, Iterator last, Functor functor) {325 void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) { 326 326 if (first == last) return; 327 327 typedef typename std::iterator_traits<Iterator>::value_type Key; … … 336 336 for (int i = 0; i < int(sizeof(Value))  1; ++i) { 337 337 if (dir) { 338 counterIntroSort(buffer, buffer + length, buffer + length,339 i, functor);338 stableRadixIntroSort(buffer, buffer + length, buffer + length, 339 i, functor); 340 340 } else { 341 counterIntroSort(buffer + length, buffer + 2 * length, buffer,342 i, functor);341 stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer, 342 i, functor); 343 343 } 344 344 dir = !dir; 345 345 } 346 346 if (dir) { 347 signed CounterIntroSort(buffer, buffer + length, buffer + length,348 sizeof(Value)  1, functor);347 signedStableRadixIntroSort(buffer, buffer + length, buffer + length, 348 sizeof(Value)  1, functor); 349 349 std::copy(buffer + length, buffer + 2 * length, first); 350 350 } else { 351 signed CounterIntroSort(buffer + length, buffer + 2 * length, buffer,352 sizeof(Value)  1, functor);351 signedStableRadixIntroSort(buffer + length, buffer + 2 * length, 352 buffer, sizeof(Value)  1, functor); 353 353 std::copy(buffer, buffer + length, first); 354 354 } … … 361 361 362 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 365 if (first == last) return; 365 366 typedef typename std::iterator_traits<Iterator>::value_type Key; … … 374 375 for (int i = 0; i < int(sizeof(Value)); ++i) { 375 376 if (dir) { 376 counterIntroSort(buffer, buffer + length,377 buffer + length, i, functor);377 stableRadixIntroSort(buffer, buffer + length, 378 buffer + length, i, functor); 378 379 } else { 379 counterIntroSort(buffer + length, buffer + 2 * length,380 buffer, i, functor);380 stableRadixIntroSort(buffer + length, buffer + 2 * length, 381 buffer, i, functor); 381 382 } 382 383 dir = !dir; … … 398 399 template <typename Value, 399 400 bool sign = std::numeric_limits<Value>::is_signed > 400 struct CounterSortSelector {401 struct StableRadixSortSelector { 401 402 template <typename Iterator, typename Functor> 402 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 408 template <typename Value> 408 struct CounterSortSelector<Value, false> {409 struct StableRadixSortSelector<Value, false> { 409 410 template <typename Iterator, typename Functor> 410 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 }; … … 424 425 /// 425 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 429 /// This sort algorithm use a radix forward sort on the … … 445 446 /// \sa radixSort() 446 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 449 using namespace _radix_sort_bits; 449 450 typedef typename Functor::result_type Value; 450 CounterSortSelector<Value>::sort(first, last, functor);451 } 452 453 template <typename Iterator, typename Value, typename Key> 454 void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {455 using namespace _radix_sort_bits; 456 CounterSortSelector<Value>::sort(first, last, functor);457 } 458 459 template <typename Iterator, typename Value, typename Key> 460 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {461 using namespace _radix_sort_bits; 462 CounterSortSelector<Value>::sort(first, last, functor);463 } 464 465 template <typename Iterator, typename Value, typename Key> 466 void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {467 using namespace _radix_sort_bits; 468 CounterSortSelector<Value>::sort(first, last, functor);469 } 470 471 template <typename Iterator, typename Value, typename Key> 472 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {473 using namespace _radix_sort_bits; 474 CounterSortSelector<Value>::sort(first, last, functor);451 StableRadixSortSelector<Value>::sort(first, last, functor); 452 } 453 454 template <typename Iterator, typename Value, typename Key> 455 void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) { 456 using namespace _radix_sort_bits; 457 StableRadixSortSelector<Value>::sort(first, last, functor); 458 } 459 460 template <typename Iterator, typename Value, typename Key> 461 void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) { 462 using namespace _radix_sort_bits; 463 StableRadixSortSelector<Value>::sort(first, last, functor); 464 } 465 466 template <typename Iterator, typename Value, typename Key> 467 void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) { 468 using namespace _radix_sort_bits; 469 StableRadixSortSelector<Value>::sort(first, last, functor); 470 } 471 472 template <typename Iterator, typename Value, typename Key> 473 void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { 474 using namespace _radix_sort_bits; 475 StableRadixSortSelector<Value>::sort(first, last, functor); 475 476 } 476 477 477 478 template <typename Iterator> 478 void counterSort(Iterator first, Iterator last) {479 void stableRadixSort(Iterator first, Iterator last) { 479 480 using namespace _radix_sort_bits; 480 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 
test/radix_sort_test.cc
r465 r466 100 100 101 101 102 void check CounterSort() {102 void checkStableRadixSort() { 103 103 { 104 104 std::vector<int> data1; … … 108 108 std::sort(data1.begin(), data1.end()); 109 109 110 counterSort(data2.begin(), data2.end());110 stableRadixSort(data2.begin(), data2.end()); 111 111 for (int i = 0; i < n; ++i) { 112 112 check(data1[i] == data2[i], "Test failed"); 113 113 } 114 114 115 counterSort(data2.begin(), data2.end(), Negate());115 stableRadixSort(data2.begin(), data2.end(), Negate()); 116 116 for (int i = 0; i < n; ++i) { 117 117 check(data1[i] == data2[n  1  i], "Test failed"); 118 118 } 119 119 120 counterSort(data2.begin(), data2.end(), negate);120 stableRadixSort(data2.begin(), data2.end(), negate); 121 121 for (int i = 0; i < n; ++i) { 122 122 check(data1[i] == data2[n  1  i], "Test failed"); … … 142 142 143 143 checkRadixSort(); 144 check CounterSort();144 checkStableRadixSort(); 145 145 146 146 return 0;
Note: See TracChangeset
for help on using the changeset viewer.