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 }