1.1 --- a/lemon/radix_sort.h	Tue Dec 02 10:17:30 2008 +0000
     1.2 +++ b/lemon/radix_sort.h	Tue Dec 02 23:15:43 2008 +0100
     1.3 @@ -217,7 +217,7 @@
     1.4    /// which maps the items to any integer type which can be either
     1.5    /// signed or unsigned.
     1.6    ///
     1.7 -  /// \sa counterSort()
     1.8 +  /// \sa stableRadixSort()
     1.9    template <typename Iterator, typename Functor>
    1.10    void radixSort(Iterator first, Iterator last, Functor functor) {
    1.11      using namespace _radix_sort_bits;
    1.12 @@ -264,8 +264,8 @@
    1.13      }
    1.14  
    1.15      template <typename Functor, typename Key>
    1.16 -    void counterIntroSort(Key *first, Key *last, Key *target,
    1.17 -                          int byte, Functor functor) {
    1.18 +    void stableRadixIntroSort(Key *first, Key *last, Key *target,
    1.19 +                              int byte, Functor functor) {
    1.20        const int size =
    1.21          unsigned(std::numeric_limits<unsigned char>::max()) + 1;
    1.22        std::vector<int> counter(size);
    1.23 @@ -290,8 +290,8 @@
    1.24      }
    1.25  
    1.26      template <typename Functor, typename Key>
    1.27 -    void signedCounterIntroSort(Key *first, Key *last, Key *target,
    1.28 -                                int byte, Functor functor) {
    1.29 +    void signedStableRadixIntroSort(Key *first, Key *last, Key *target,
    1.30 +                                    int byte, Functor functor) {
    1.31        const int size =
    1.32          unsigned(std::numeric_limits<unsigned char>::max()) + 1;
    1.33        std::vector<int> counter(size);
    1.34 @@ -322,7 +322,7 @@
    1.35  
    1.36  
    1.37      template <typename Value, typename Iterator, typename Functor>
    1.38 -    void counterSignedSort(Iterator first, Iterator last, Functor functor) {
    1.39 +    void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) {
    1.40        if (first == last) return;
    1.41        typedef typename std::iterator_traits<Iterator>::value_type Key;
    1.42        typedef std::allocator<Key> Allocator;
    1.43 @@ -335,21 +335,21 @@
    1.44          std::copy(first, last, buffer);
    1.45          for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
    1.46            if (dir) {
    1.47 -            counterIntroSort(buffer, buffer + length, buffer + length,
    1.48 -                             i, functor);
    1.49 +            stableRadixIntroSort(buffer, buffer + length, buffer + length,
    1.50 +                                 i, functor);
    1.51            } else {
    1.52 -            counterIntroSort(buffer + length, buffer + 2 * length, buffer,
    1.53 -                             i, functor);
    1.54 +            stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
    1.55 +                                 i, functor);
    1.56            }
    1.57            dir = !dir;
    1.58          }
    1.59          if (dir) {
    1.60 -          signedCounterIntroSort(buffer, buffer + length, buffer + length,
    1.61 -                                 sizeof(Value) - 1, functor);
    1.62 +          signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
    1.63 +                                     sizeof(Value) - 1, functor);
    1.64            std::copy(buffer + length, buffer + 2 * length, first);
    1.65          }        else {
    1.66 -          signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
    1.67 -                                 sizeof(Value) - 1, functor);
    1.68 +          signedStableRadixIntroSort(buffer + length, buffer + 2 * length, 
    1.69 +                                     buffer, sizeof(Value) - 1, functor);
    1.70            std::copy(buffer, buffer + length, first);
    1.71          }
    1.72        } catch (...) {
    1.73 @@ -360,7 +360,8 @@
    1.74      }
    1.75  
    1.76      template <typename Value, typename Iterator, typename Functor>
    1.77 -    void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
    1.78 +    void stableRadixUnsignedSort(Iterator first, Iterator last, 
    1.79 +                                 Functor functor) {
    1.80        if (first == last) return;
    1.81        typedef typename std::iterator_traits<Iterator>::value_type Key;
    1.82        typedef std::allocator<Key> Allocator;
    1.83 @@ -373,11 +374,11 @@
    1.84          std::copy(first, last, buffer);
    1.85          for (int i = 0; i < int(sizeof(Value)); ++i) {
    1.86            if (dir) {
    1.87 -            counterIntroSort(buffer, buffer + length,
    1.88 -                             buffer + length, i, functor);
    1.89 +            stableRadixIntroSort(buffer, buffer + length,
    1.90 +                                 buffer + length, i, functor);
    1.91            } else {
    1.92 -            counterIntroSort(buffer + length, buffer + 2 * length,
    1.93 -                             buffer, i, functor);
    1.94 +            stableRadixIntroSort(buffer + length, buffer + 2 * length,
    1.95 +                                 buffer, i, functor);
    1.96            }
    1.97            dir = !dir;
    1.98          }
    1.99 @@ -397,18 +398,18 @@
   1.100  
   1.101      template <typename Value,
   1.102                bool sign = std::numeric_limits<Value>::is_signed >
   1.103 -    struct CounterSortSelector {
   1.104 +    struct StableRadixSortSelector {
   1.105        template <typename Iterator, typename Functor>
   1.106        static void sort(Iterator first, Iterator last, Functor functor) {
   1.107 -        counterSignedSort<Value>(first, last, functor);
   1.108 +        stableRadixSignedSort<Value>(first, last, functor);
   1.109        }
   1.110      };
   1.111  
   1.112      template <typename Value>
   1.113 -    struct CounterSortSelector<Value, false> {
   1.114 +    struct StableRadixSortSelector<Value, false> {
   1.115        template <typename Iterator, typename Functor>
   1.116        static void sort(Iterator first, Iterator last, Functor functor) {
   1.117 -        counterUnsignedSort<Value>(first, last, functor);
   1.118 +        stableRadixUnsignedSort<Value>(first, last, functor);
   1.119        }
   1.120      };
   1.121  
   1.122 @@ -423,7 +424,7 @@
   1.123    /// order according to an integer mapping in the same as radixSort() does.
   1.124    ///
   1.125    /// This sorting algorithm is stable, i.e. the order of two equal
   1.126 -  /// element remains the same after the sorting.
   1.127 +  /// elements remains the same after the sorting.
   1.128    ///
   1.129    /// This sort algorithm  use a radix forward sort on the
   1.130    /// bytes of the integer number. The algorithm sorts the items
   1.131 @@ -444,41 +445,41 @@
   1.132    /// signed or unsigned.
   1.133    /// \sa radixSort()
   1.134    template <typename Iterator, typename Functor>
   1.135 -  void counterSort(Iterator first, Iterator last, Functor functor) {
   1.136 +  void stableRadixSort(Iterator first, Iterator last, Functor functor) {
   1.137      using namespace _radix_sort_bits;
   1.138      typedef typename Functor::result_type Value;
   1.139 -    CounterSortSelector<Value>::sort(first, last, functor);
   1.140 +    StableRadixSortSelector<Value>::sort(first, last, functor);
   1.141    }
   1.142  
   1.143    template <typename Iterator, typename Value, typename Key>
   1.144 -  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
   1.145 +  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
   1.146      using namespace _radix_sort_bits;
   1.147 -    CounterSortSelector<Value>::sort(first, last, functor);
   1.148 +    StableRadixSortSelector<Value>::sort(first, last, functor);
   1.149    }
   1.150  
   1.151    template <typename Iterator, typename Value, typename Key>
   1.152 -  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
   1.153 +  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
   1.154      using namespace _radix_sort_bits;
   1.155 -    CounterSortSelector<Value>::sort(first, last, functor);
   1.156 +    StableRadixSortSelector<Value>::sort(first, last, functor);
   1.157    }
   1.158  
   1.159    template <typename Iterator, typename Value, typename Key>
   1.160 -  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
   1.161 +  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
   1.162      using namespace _radix_sort_bits;
   1.163 -    CounterSortSelector<Value>::sort(first, last, functor);
   1.164 +    StableRadixSortSelector<Value>::sort(first, last, functor);
   1.165    }
   1.166  
   1.167    template <typename Iterator, typename Value, typename Key>
   1.168 -  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
   1.169 +  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
   1.170      using namespace _radix_sort_bits;
   1.171 -    CounterSortSelector<Value>::sort(first, last, functor);
   1.172 +    StableRadixSortSelector<Value>::sort(first, last, functor);
   1.173    }
   1.174  
   1.175    template <typename Iterator>
   1.176 -  void counterSort(Iterator first, Iterator last) {
   1.177 +  void stableRadixSort(Iterator first, Iterator last) {
   1.178      using namespace _radix_sort_bits;
   1.179      typedef typename std::iterator_traits<Iterator>::value_type Value;
   1.180 -    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
   1.181 +    StableRadixSortSelector<Value>::sort(first, last, Identity<Value>());
   1.182    }
   1.183  
   1.184  }

     2.1 --- a/test/radix_sort_test.cc	Tue Dec 02 10:17:30 2008 +0000
     2.2 +++ b/test/radix_sort_test.cc	Tue Dec 02 23:15:43 2008 +0100
     2.3 @@ -99,7 +99,7 @@
     2.4  }
     2.5  
     2.6  
     2.7 -void checkCounterSort() {
     2.8 +void checkStableRadixSort() {
     2.9    {
    2.10      std::vector<int> data1;
    2.11      generateIntSequence(n, data1);
    2.12 @@ -107,17 +107,17 @@
    2.13      std::vector<int> data2(data1);
    2.14      std::sort(data1.begin(), data1.end());
    2.15  
    2.16 -    counterSort(data2.begin(), data2.end());
    2.17 +    stableRadixSort(data2.begin(), data2.end());
    2.18      for (int i = 0; i < n; ++i) {
    2.19        check(data1[i] == data2[i], "Test failed");
    2.20      }
    2.21  
    2.22 -    counterSort(data2.begin(), data2.end(), Negate());
    2.23 +    stableRadixSort(data2.begin(), data2.end(), Negate());
    2.24      for (int i = 0; i < n; ++i) {
    2.25        check(data1[i] == data2[n - 1 - i], "Test failed");
    2.26      }
    2.27  
    2.28 -    counterSort(data2.begin(), data2.end(), negate);
    2.29 +    stableRadixSort(data2.begin(), data2.end(), negate);
    2.30      for (int i = 0; i < n; ++i) {
    2.31        check(data1[i] == data2[n - 1 - i], "Test failed");
    2.32      }
    2.33 @@ -141,7 +141,7 @@
    2.34  int main() {
    2.35  
    2.36    checkRadixSort();
    2.37 -  checkCounterSort();
    2.38 +  checkStableRadixSort();
    2.39  
    2.40    return 0;
    2.41  }