Changeset - r443:de16f1f2d228
« 442:31d224
444:ba4910 »
gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Rename counterSort to stableRadixSort
0 2 0
default
2 files changed with 42 insertions and 41 deletions:
lemon/radix_sort.h
37
36
test/radix_sort_test.cc
5
5
↑ Collapse diff ↑
lemon/radix_sort.h
Ignore white space 6 line context
... ... 
@@ -219,3 +219,3 @@
219 219 
  ///
220 
  /// \sa counterSort()
220 
  /// \sa stableRadixSort()
221 221 
  template <typename Iterator, typename Functor>
... ... 
@@ -266,4 +266,4 @@
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 =
... ... 
@@ -292,4 +292,4 @@
292 292 
    template <typename Functor, typename Key>
293 
    void signedCounterIntroSort(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 =
... ... 
@@ -324,3 +324,3 @@
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;
... ... 
@@ -337,7 +337,7 @@
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 
          }
... ... 
@@ -346,8 +346,8 @@
346 346 
        if (dir) {
347 
          signedCounterIntroSort(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 
          signedCounterIntroSort(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);
... ... 
@@ -362,3 +362,4 @@
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;
... ... 
@@ -375,7 +376,7 @@
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 
          }
... ... 
@@ -399,6 +400,6 @@
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 
      }
... ... 
@@ -407,6 +408,6 @@
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 
      }
... ... 
@@ -425,3 +426,3 @@
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 
  ///
... ... 
@@ -446,6 +447,6 @@
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 
    StableRadixSortSelector<Value>::sort(first, last, functor);
451 452 
  }
... ... 
@@ -453,5 +454,5 @@
453 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 456 
    using namespace _radix_sort_bits;
456 
    CounterSortSelector<Value>::sort(first, last, functor);
457 
    StableRadixSortSelector<Value>::sort(first, last, functor);
457 458 
  }
... ... 
@@ -459,5 +460,5 @@
459 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 462 
    using namespace _radix_sort_bits;
462 
    CounterSortSelector<Value>::sort(first, last, functor);
463 
    StableRadixSortSelector<Value>::sort(first, last, functor);
463 464 
  }
... ... 
@@ -465,5 +466,5 @@
465 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 468 
    using namespace _radix_sort_bits;
468 
    CounterSortSelector<Value>::sort(first, last, functor);
469 
    StableRadixSortSelector<Value>::sort(first, last, functor);
469 470 
  }
... ... 
@@ -471,5 +472,5 @@
471 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 474 
    using namespace _radix_sort_bits;
474 
    CounterSortSelector<Value>::sort(first, last, functor);
475 
    StableRadixSortSelector<Value>::sort(first, last, functor);
475 476 
  }
... ... 
@@ -477,6 +478,6 @@
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 
  }
test/radix_sort_test.cc
Ignore white space 2 line context
... ... 
@@ -101,3 +101,3 @@
101 101 

			




	102
	
	
		
void checkCounterSort() {


			




	
	102
	
		
void checkStableRadixSort() {


			




	103
	103
	
		
  {


			




	...
	...
	
		
@@ -109,3 +109,3 @@


			




	109
	109
	
		

			




	110
	
	
		
    counterSort(data2.begin(), data2.end());


			




	
	110
	
		
    stableRadixSort(data2.begin(), data2.end());


			




	111
	111
	
		
    for (int i = 0; i < n; ++i) {


			




	...
	...
	
		
@@ -114,3 +114,3 @@


			




	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) {


			




	...
	...
	
		
@@ -119,3 +119,3 @@


			




	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) {


			




	...
	...
	
		
@@ -143,3 +143,3 @@


			




	143
	143
	
		
  checkRadixSort();


			




	144
	
	
		
  checkCounterSort();


			




	
	144
	
		
  checkStableRadixSort();


			




	145
	145
	
		

			




        

    






    
    



    


    

     
    
0 comments (0 inline)