Changeset 443:de16f1f2d228 in lemon-main

Timestamp:

12/02/08 23:15:43 (16 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

Rename counterSort to stableRadixSort

Files:

• lemon/radix_sort.h (modified) (10 diffs)
• test/radix_sort_test.cc (modified) (3 diffs)

lemon/radix_sort.h

@@ -218 +218 @@
   /// signed or unsigned.
   ///
-  /// \sa counterSort()
+  /// \sa stableRadixSort()
   template <typename Iterator, typename Functor>
   void radixSort(Iterator first, Iterator last, Functor functor) {
@@ -265 +265 @@
 
     template <typename Functor, typename Key>
-    void counterIntroSort(Key *first, Key *last, Key *target,
-                          int byte, Functor functor) {
+    void stableRadixIntroSort(Key *first, Key *last, Key *target,
+                              int byte, Functor functor) {
       const int size =
         unsigned(std::numeric_limits<unsigned char>::max()) + 1;
@@ -291 +291 @@
 
     template <typename Functor, typename Key>
-    void signedCounterIntroSort(Key *first, Key *last, Key *target,
-                                int byte, Functor functor) {
+    void signedStableRadixIntroSort(Key *first, Key *last, Key *target,
+                                    int byte, Functor functor) {
       const int size =
         unsigned(std::numeric_limits<unsigned char>::max()) + 1;
@@ -323 +323 @@
 
     template <typename Value, typename Iterator, typename Functor>
-    void counterSignedSort(Iterator first, Iterator last, Functor functor) {
+    void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) {
       if (first == last) return;
       typedef typename std::iterator_traits<Iterator>::value_type Key;
@@ -336 +336 @@
         for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
           if (dir) {
-            counterIntroSort(buffer, buffer + length, buffer + length,
-                             i, functor);
+            stableRadixIntroSort(buffer, buffer + length, buffer + length,
+                                 i, functor);
           } else {
-            counterIntroSort(buffer + length, buffer + 2 * length, buffer,
-                             i, functor);
+            stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
+                                 i, functor);
           }
           dir = !dir;
         }
         if (dir) {
-          signedCounterIntroSort(buffer, buffer + length, buffer + length,
-                                 sizeof(Value) - 1, functor);
+          signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
+                                     sizeof(Value) - 1, functor);
           std::copy(buffer + length, buffer + 2 * length, first);
         }        else {
-          signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
-                                 sizeof(Value) - 1, functor);
+          signedStableRadixIntroSort(buffer + length, buffer + 2 * length, 
+                                     buffer, sizeof(Value) - 1, functor);
           std::copy(buffer, buffer + length, first);
         }
@@ -361 +361 @@
 
     template <typename Value, typename Iterator, typename Functor>
-    void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
+    void stableRadixUnsignedSort(Iterator first, Iterator last, 
+                                 Functor functor) {
       if (first == last) return;
       typedef typename std::iterator_traits<Iterator>::value_type Key;
@@ -374 +375 @@
         for (int i = 0; i < int(sizeof(Value)); ++i) {
           if (dir) {
-            counterIntroSort(buffer, buffer + length,
-                             buffer + length, i, functor);
+            stableRadixIntroSort(buffer, buffer + length,
+                                 buffer + length, i, functor);
           } else {
-            counterIntroSort(buffer + length, buffer + 2 * length,
-                             buffer, i, functor);
+            stableRadixIntroSort(buffer + length, buffer + 2 * length,
+                                 buffer, i, functor);
           }
           dir = !dir;
@@ -398 +399 @@
     template <typename Value,
               bool sign = std::numeric_limits<Value>::is_signed >
-    struct CounterSortSelector {
+    struct StableRadixSortSelector {
       template <typename Iterator, typename Functor>
       static void sort(Iterator first, Iterator last, Functor functor) {
-        counterSignedSort<Value>(first, last, functor);
+        stableRadixSignedSort<Value>(first, last, functor);
       }
     };
 
     template <typename Value>
-    struct CounterSortSelector<Value, false> {
+    struct StableRadixSortSelector<Value, false> {
       template <typename Iterator, typename Functor>
       static void sort(Iterator first, Iterator last, Functor functor) {
-        counterUnsignedSort<Value>(first, last, functor);
+        stableRadixUnsignedSort<Value>(first, last, functor);
       }
     };
@@ -424 +425 @@
   ///
   /// This sorting algorithm is stable, i.e. the order of two equal
-  /// element remains the same after the sorting.
+  /// elements remains the same after the sorting.
   ///
   /// This sort algorithm  use a radix forward sort on the
@@ -445 +446 @@
   /// \sa radixSort()
   template <typename Iterator, typename Functor>
-  void counterSort(Iterator first, Iterator last, Functor functor) {
+  void stableRadixSort(Iterator first, Iterator last, Functor functor) {
     using namespace _radix_sort_bits;
     typedef typename Functor::result_type Value;
-    CounterSortSelector<Value>::sort(first, last, functor);
-  }
-
-  template <typename Iterator, typename Value, typename Key>
-  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
-    using namespace _radix_sort_bits;
-    CounterSortSelector<Value>::sort(first, last, functor);
-  }
-
-  template <typename Iterator, typename Value, typename Key>
-  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
-    using namespace _radix_sort_bits;
-    CounterSortSelector<Value>::sort(first, last, functor);
-  }
-
-  template <typename Iterator, typename Value, typename Key>
-  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
-    using namespace _radix_sort_bits;
-    CounterSortSelector<Value>::sort(first, last, functor);
-  }
-
-  template <typename Iterator, typename Value, typename Key>
-  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
-    using namespace _radix_sort_bits;
-    CounterSortSelector<Value>::sort(first, last, functor);
+    StableRadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
+    using namespace _radix_sort_bits;
+    StableRadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
+    using namespace _radix_sort_bits;
+    StableRadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
+    using namespace _radix_sort_bits;
+    StableRadixSortSelector<Value>::sort(first, last, functor);
+  }
+
+  template <typename Iterator, typename Value, typename Key>
+  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
+    using namespace _radix_sort_bits;
+    StableRadixSortSelector<Value>::sort(first, last, functor);
   }
 
   template <typename Iterator>
-  void counterSort(Iterator first, Iterator last) {
+  void stableRadixSort(Iterator first, Iterator last) {
     using namespace _radix_sort_bits;
     typedef typename std::iterator_traits<Iterator>::value_type Value;
-    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
+    StableRadixSortSelector<Value>::sort(first, last, Identity<Value>());
   }
 

test/radix_sort_test.cc

@@ -100 +100 @@
 
 
-void checkCounterSort() {
+void checkStableRadixSort() {
   {
     std::vector<int> data1;
@@ -108 +108 @@
     std::sort(data1.begin(), data1.end());
 
-    counterSort(data2.begin(), data2.end());
+    stableRadixSort(data2.begin(), data2.end());
     for (int i = 0; i < n; ++i) {
       check(data1[i] == data2[i], "Test failed");
     }
 
-    counterSort(data2.begin(), data2.end(), Negate());
+    stableRadixSort(data2.begin(), data2.end(), Negate());
     for (int i = 0; i < n; ++i) {
       check(data1[i] == data2[n - 1 - i], "Test failed");
     }
 
-    counterSort(data2.begin(), data2.end(), negate);
+    stableRadixSort(data2.begin(), data2.end(), negate);
     for (int i = 0; i < n; ++i) {
       check(data1[i] == data2[n - 1 - i], "Test failed");
@@ -142 +142 @@
 
   checkRadixSort();
-  checkCounterSort();
+  checkStableRadixSort();
 
   return 0;