00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef RADIX_SORT_H
00020 #define RADIX_SORT_H
00021
00026
00027 #include <vector>
00028 #include <limits>
00029 #include <iterator>
00030 #include <algorithm>
00031
00032 #include <lemon/error.h>
00033
00034 namespace lemon {
00035
00036 namespace _radix_sort_bits {
00037
00038 template <typename Value>
00039 struct Identity {
00040 const Value& operator()(const Value& val) {
00041 return val;
00042 }
00043 };
00044
00045 }
00046
00047 template <typename Value, typename Iterator, typename Functor>
00048 Iterator radixSortPartition(Iterator first, Iterator last,
00049 Functor functor, Value mask) {
00050 while (first != last && !(functor(*first) & mask)) {
00051 ++first;
00052 }
00053 if (first == last) {
00054 return first;
00055 }
00056 --last;
00057 while (first != last && (functor(*last) & mask)) {
00058 --last;
00059 }
00060 if (first == last) {
00061 return first;
00062 }
00063 std::iter_swap(first, last);
00064 ++first;
00065 if (!(first < last)) {
00066 return first;
00067 }
00068 while (true) {
00069 while (!(functor(*first) & mask)) {
00070 ++first;
00071 }
00072 --last;
00073 while (functor(*last) & mask) {
00074 --last;
00075 }
00076 if (!(first < last)) {
00077 return first;
00078 }
00079 std::iter_swap(first, last);
00080 ++first;
00081 }
00082 }
00083
00084 template <typename Iterator, typename Functor>
00085 Iterator radixSortSignPartition(Iterator first, Iterator last,
00086 Functor functor) {
00087 while (first != last && functor(*first) < 0) {
00088 ++first;
00089 }
00090 if (first == last) {
00091 return first;
00092 }
00093 --last;
00094 while (first != last && functor(*last) >= 0) {
00095 --last;
00096 }
00097 if (first == last) {
00098 return first;
00099 }
00100 std::iter_swap(first, last);
00101 ++first;
00102 if (!(first < last)) {
00103 return first;
00104 }
00105 while (true) {
00106 while (functor(*first) < 0) {
00107 ++first;
00108 }
00109 --last;
00110 while (functor(*last) >= 0) {
00111 --last;
00112 }
00113 if (!(first < last)) {
00114 return first;
00115 }
00116 std::iter_swap(first, last);
00117 ++first;
00118 }
00119 }
00120
00121 template <typename Value, typename Iterator, typename Functor>
00122 void radixIntroSort(Iterator first, Iterator last,
00123 Functor functor, Value mask) {
00124 while (mask != 0 && last - first > 1) {
00125 Iterator cut = radixSortPartition(first, last, functor, mask);
00126 mask >>= 1;
00127 radixIntroSort(first, cut, functor, mask);
00128 first = cut;
00129 }
00130 }
00131
00132 template <typename Value, typename Iterator, typename Functor>
00133 void radixSignedSort(Iterator first, Iterator last, Functor functor) {
00134 Iterator cut = radixSortSignPartition(first, last, functor);
00135
00136 Value mask;
00137 int max_digit;
00138 Iterator it;
00139
00140 mask = 0; max_digit = 0;
00141 for (it = first; it != cut; ++it) {
00142 if ((mask | functor(*it)) != ~0) {
00143 ++max_digit;
00144 mask <<= 1;
00145 mask |= 1;
00146 }
00147 }
00148 radixIntroSort(first, cut, functor, 1 << max_digit);
00149
00150 mask = ~0; max_digit = 0;
00151 for (it = cut; it != last; ++it) {
00152 if (mask & functor(*it)) {
00153 ++max_digit;
00154 mask <<= 1;
00155 }
00156 }
00157 radixIntroSort(cut, last, functor, 1 << max_digit);
00158 }
00159
00160 template <typename Value, typename Iterator, typename Functor>
00161 void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
00162
00163 Value mask = ~0;
00164 int max_digit = 0;
00165
00166 Iterator it;
00167 for (it = first; it != last; ++it) {
00168 if (mask & functor(*it)) {
00169 ++max_digit;
00170 mask <<= 1;
00171 }
00172 }
00173 radixIntroSort(first, last, functor, 1 << max_digit);
00174 }
00175
00176 namespace _radix_sort_bits {
00177
00178 template <typename Value,
00179 bool sign = std::numeric_limits<Value>::is_signed >
00180 struct RadixSortSelector {
00181 template <typename Iterator, typename Functor>
00182 static void sort(Iterator first, Iterator last, Functor functor) {
00183 radixSignedSort<Value>(first, last, functor);
00184 }
00185 };
00186
00187 template <typename Value>
00188 struct RadixSortSelector<Value, false> {
00189 template <typename Iterator, typename Functor>
00190 static void sort(Iterator first, Iterator last, Functor functor) {
00191 radixUnsignedSort<Value>(first, last, functor);
00192 }
00193 };
00194
00195 }
00196
00219 template <typename Iterator, typename Functor>
00220 void radixSort(Iterator first, Iterator last, Functor functor) {
00221 using namespace _radix_sort_bits;
00222 typedef typename Functor::result_type Value;
00223 RadixSortSelector<Value>::sort(first, last, functor);
00224 }
00225
00226 template <typename Iterator, typename Value, typename Key>
00227 void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
00228 using namespace _radix_sort_bits;
00229 RadixSortSelector<Value>::sort(first, last, functor);
00230 }
00231
00232 template <typename Iterator, typename Value, typename Key>
00233 void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
00234 using namespace _radix_sort_bits;
00235 RadixSortSelector<Value>::sort(first, last, functor);
00236 }
00237
00238 template <typename Iterator, typename Value, typename Key>
00239 void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
00240 using namespace _radix_sort_bits;
00241 RadixSortSelector<Value>::sort(first, last, functor);
00242 }
00243
00244 template <typename Iterator, typename Value, typename Key>
00245 void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
00246 using namespace _radix_sort_bits;
00247 RadixSortSelector<Value>::sort(first, last, functor);
00248 }
00249
00250 template <typename Iterator>
00251 void radixSort(Iterator first, Iterator last) {
00252 using namespace _radix_sort_bits;
00253 typedef typename std::iterator_traits<Iterator>::value_type Value;
00254 RadixSortSelector<Value>::sort(first, last, Identity<Value>());
00255 }
00256
00257 template <typename Value>
00258 unsigned char valueByte(Value value, int byte) {
00259 return value >> (std::numeric_limits<unsigned char>::digits * byte);
00260 }
00261
00262 template <typename Functor, typename Key>
00263 void counterIntroSort(Key *first, Key *last, Key *target,
00264 int byte, Functor functor) {
00265 const int size =
00266 (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
00267 int counter[size];
00268 for (int i = 0; i < size; ++i) {
00269 counter[i] = 0;
00270 }
00271 Key *it = first;
00272 while (first != last) {
00273 ++counter[valueByte(functor(*first), byte)];
00274 ++first;
00275 }
00276 int prev, num = 0;
00277 for (int i = 0; i < size; ++i) {
00278 prev = num;
00279 num += counter[i];
00280 counter[i] = prev;
00281 }
00282 while (it != last) {
00283 target[counter[valueByte(functor(*it), byte)]++] = *it;
00284 ++it;
00285 }
00286 }
00287
00288 template <typename Functor, typename Key>
00289 void signedCounterIntroSort(Key *first, Key *last, Key *target,
00290 int byte, Functor functor) {
00291 const int size =
00292 (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
00293 int counter[size];
00294 for (int i = 0; i < size; ++i) {
00295 counter[i] = 0;
00296 }
00297 Key *it = first;
00298 while (first != last) {
00299 counter[valueByte(functor(*first), byte)]++;
00300 ++first;
00301 }
00302 int prev, num = 0;
00303 for (int i = size / 2; i < size; ++i) {
00304 prev = num;
00305 num += counter[i];
00306 counter[i] = prev;
00307 }
00308 for (int i = 0; i < size / 2; ++i) {
00309 prev = num;
00310 num += counter[i];
00311 counter[i] = prev;
00312 }
00313 while (it != last) {
00314 target[counter[valueByte(functor(*it), byte)]++] = *it;
00315 ++it;
00316 }
00317 }
00318
00319
00320 template <typename Value, typename Iterator, typename Functor>
00321 void counterSignedSort(Iterator first, Iterator last, Functor functor) {
00322 if (first == last) return;
00323 typedef typename std::iterator_traits<Iterator>::value_type Key;
00324 typedef std::allocator<Key> Allocator;
00325 Allocator allocator;
00326
00327 int length = std::distance(first, last);
00328 Key* buffer;
00329 buffer = allocator.allocate(2 * length);
00330 try {
00331 bool dir = true;
00332 std::copy(first, last, buffer);
00333 for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
00334 if (dir) {
00335 counterIntroSort(buffer, buffer + length, buffer + length,
00336 i, functor);
00337 } else {
00338 counterIntroSort(buffer + length, buffer + 2 * length, buffer,
00339 i, functor);
00340 }
00341 dir = !dir;
00342 }
00343 if (dir) {
00344 signedCounterIntroSort(buffer, buffer + length, buffer + length,
00345 sizeof(Value) - 1, functor);
00346 std::copy(buffer + length, buffer + 2 * length, first);
00347 } else {
00348 signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
00349 sizeof(Value) - 1, functor);
00350 std::copy(buffer, buffer + length, first);
00351 }
00352 } catch (...) {
00353 allocator.deallocate(buffer, 2 * length);
00354 throw;
00355 }
00356 allocator.deallocate(buffer, 2 * length);
00357 }
00358
00359 template <typename Value, typename Iterator, typename Functor>
00360 void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
00361 if (first == last) return;
00362 typedef typename std::iterator_traits<Iterator>::value_type Key;
00363 typedef std::allocator<Key> Allocator;
00364 Allocator allocator;
00365
00366 int length = std::distance(first, last);
00367 Key *buffer;
00368 buffer = allocator.allocate(2 * length);
00369 try {
00370 bool dir = true;
00371 std::copy(first, last, buffer);
00372 for (int i = 0; i < (int)sizeof(Value); ++i) {
00373 if (dir) {
00374 counterIntroSort(buffer, buffer + length, buffer + length, i, functor);
00375 } else {
00376 counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
00377 }
00378 dir = !dir;
00379 }
00380 if (dir) {
00381 std::copy(buffer, buffer + length, first);
00382 } else {
00383 std::copy(buffer + length, buffer + 2 * length, first);
00384 }
00385 } catch (...) {
00386 allocator.deallocate(buffer, 2 * length);
00387 throw;
00388 }
00389 allocator.deallocate(buffer, 2 * length);
00390 }
00391
00392 namespace _radix_sort_bits {
00393
00394 template <typename Value,
00395 bool sign = std::numeric_limits<Value>::is_signed >
00396 struct CounterSortSelector {
00397 template <typename Iterator, typename Functor>
00398 static void sort(Iterator first, Iterator last, Functor functor) {
00399 counterSignedSort<Value>(first, last, functor);
00400 }
00401 };
00402
00403 template <typename Value>
00404 struct CounterSortSelector<Value, false> {
00405 template <typename Iterator, typename Functor>
00406 static void sort(Iterator first, Iterator last, Functor functor) {
00407 counterUnsignedSort<Value>(first, last, functor);
00408 }
00409 };
00410
00411 }
00412
00443 template <typename Iterator, typename Functor>
00444 void counterSort(Iterator first, Iterator last, Functor functor) {
00445 using namespace _radix_sort_bits;
00446 typedef typename Functor::result_type Value;
00447 CounterSortSelector<Value>::sort(first, last, functor);
00448 }
00449
00450 template <typename Iterator, typename Value, typename Key>
00451 void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
00452 using namespace _radix_sort_bits;
00453 CounterSortSelector<Value>::sort(first, last, functor);
00454 }
00455
00456 template <typename Iterator, typename Value, typename Key>
00457 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
00458 using namespace _radix_sort_bits;
00459 CounterSortSelector<Value>::sort(first, last, functor);
00460 }
00461
00462 template <typename Iterator, typename Value, typename Key>
00463 void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
00464 using namespace _radix_sort_bits;
00465 CounterSortSelector<Value>::sort(first, last, functor);
00466 }
00467
00468 template <typename Iterator, typename Value, typename Key>
00469 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
00470 using namespace _radix_sort_bits;
00471 CounterSortSelector<Value>::sort(first, last, functor);
00472 }
00473
00474 template <typename Iterator>
00475 void counterSort(Iterator first, Iterator last) {
00476 using namespace _radix_sort_bits;
00477 typedef typename std::iterator_traits<Iterator>::value_type Value;
00478 CounterSortSelector<Value>::sort(first, last, Identity<Value>());
00479 }
00480
00481 }
00482
00483
00484
00485 #endif