Changeset 465:31d224a3c0af in lemon
 Timestamp:
 12/02/08 11:17:30 (12 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/radix_sort.h
r464 r465 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 38 38 struct Identity { 39 39 const Value& operator()(const Value& val) { 40 40 return val; 41 41 } 42 42 }; … … 44 44 45 45 template <typename Value, typename Iterator, typename Functor> 46 Iterator radixSortPartition(Iterator first, Iterator last, 47 46 Iterator radixSortPartition(Iterator first, Iterator last, 47 Functor functor, Value mask) { 48 48 while (first != last && !(functor(*first) & mask)) { 49 49 ++first; 50 50 } 51 51 if (first == last) { 52 52 return first; 53 53 } 54 54 last; 55 55 while (first != last && (functor(*last) & mask)) { 56 56 last; 57 57 } 58 58 if (first == last) { 59 59 return first; 60 60 } 61 61 std::iter_swap(first, last); 62 62 ++first; 63 63 if (!(first < last)) { 64 64 return first; 65 65 } 66 66 while (true) { 67 68 69 70 71 72 73 74 75 76 77 78 67 while (!(functor(*first) & mask)) { 68 ++first; 69 } 70 last; 71 while (functor(*last) & mask) { 72 last; 73 } 74 if (!(first < last)) { 75 return first; 76 } 77 std::iter_swap(first, last); 78 ++first; 79 79 } 80 80 } 81 81 82 82 template <typename Iterator, typename Functor> 83 Iterator radixSortSignPartition(Iterator first, Iterator last, 84 83 Iterator radixSortSignPartition(Iterator first, Iterator last, 84 Functor functor) { 85 85 while (first != last && functor(*first) < 0) { 86 86 ++first; 87 87 } 88 88 if (first == last) { 89 89 return first; 90 90 } 91 91 last; 92 92 while (first != last && functor(*last) >= 0) { 93 93 last; 94 94 } 95 95 if (first == last) { 96 96 return first; 97 97 } 98 98 std::iter_swap(first, last); 99 99 ++first; 100 100 if (!(first < last)) { 101 101 return first; 102 102 } 103 103 while (true) { 104 105 106 107 108 109 110 111 112 113 114 115 116 } 117 } 118 119 template <typename Value, typename Iterator, typename Functor> 120 void radixIntroSort(Iterator first, Iterator last, 121 104 while (functor(*first) < 0) { 105 ++first; 106 } 107 last; 108 while (functor(*last) >= 0) { 109 last; 110 } 111 if (!(first < last)) { 112 return first; 113 } 114 std::iter_swap(first, last); 115 ++first; 116 } 117 } 118 119 template <typename Value, typename Iterator, typename Functor> 120 void radixIntroSort(Iterator first, Iterator last, 121 Functor functor, Value mask) { 122 122 while (mask != 0 && last  first > 1) { 123 124 125 126 123 Iterator cut = radixSortPartition(first, last, functor, mask); 124 mask >>= 1; 125 radixIntroSort(first, cut, functor, mask); 126 first = cut; 127 127 } 128 128 } … … 139 139 mask = ~0; max_digit = 0; 140 140 for (it = first; it != cut; ++it) { 141 142 143 144 141 while ((mask & functor(*it)) != mask) { 142 ++max_digit; 143 mask <<= 1; 144 } 145 145 } 146 146 radixIntroSort(first, cut, functor, 1 << max_digit); … … 148 148 mask = 0; max_digit = 0; 149 149 for (it = cut; it != last; ++it) { 150 151 152 153 150 while ((mask  functor(*it)) != mask) { 151 ++max_digit; 152 mask <<= 1; mask = 1; 153 } 154 154 } 155 155 radixIntroSort(cut, last, functor, 1 << max_digit); … … 164 164 Iterator it; 165 165 for (it = first; it != last; ++it) { 166 167 168 169 166 while ((mask  functor(*it)) != mask) { 167 ++max_digit; 168 mask <<= 1; mask = 1; 169 } 170 170 } 171 171 radixIntroSort(first, last, functor, 1 << max_digit); … … 173 173 174 174 175 template <typename Value, 176 175 template <typename Value, 176 bool sign = std::numeric_limits<Value>::is_signed > 177 177 struct RadixSortSelector { 178 178 template <typename Iterator, typename Functor> 179 179 static void sort(Iterator first, Iterator last, Functor functor) { 180 180 radixSignedSort<Value>(first, last, functor); 181 181 } 182 182 }; … … 186 186 template <typename Iterator, typename Functor> 187 187 static void sort(Iterator first, Iterator last, Functor functor) { 188 188 radixUnsignedSort<Value>(first, last, functor); 189 189 } 190 190 }; … … 196 196 /// \brief Sorts the STL compatible range into ascending order. 197 197 /// 198 /// The \c radixSort sorts the STL compatible range into ascending 199 /// order. The radix sort algorithm can sort the items which mapped 200 /// to an integer with an adaptable unary function \c functor and the 201 /// order will be ascending by these mapped values. As function 202 /// specialization it is possible to use a normal function instead 203 /// of the functor object or if the functor is not given it will use 204 /// an identity function instead. 205 /// 206 /// This implemented radix sort is a special quick sort which pivot 207 /// value is choosen to partite the items on the next 208 /// bit. Therefore, let be \c c the maximal capacity and \c n the 209 /// number of the items in the container, the time complexity of the 210 /// algorithm is \f$ O(\log(c)n) \f$ and the additional space 211 /// complexity is \f$ O(\log(c)) \f$. 198 /// The \c radixSort sorts an STL compatible range into ascending 199 /// order. The radix sort algorithm can sort items which are mapped 200 /// to integers with an adaptable unary function \c functor and the 201 /// order will be ascending according to these mapped values. 202 /// 203 /// It is also possible to use a normal function instead 204 /// of the functor object. If the functor is not given it will use 205 /// the identity function instead. 206 /// 207 /// This is a special quick sort algorithm where the pivot 208 /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k. 209 /// Therefore, the time complexity of the 210 /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$, 211 /// additional space, where \c c is the maximal value and \c n is the 212 /// number of the items in the container. 212 213 /// 213 214 /// \param first The begin of the given range. … … 216 217 /// which maps the items to any integer type which can be either 217 218 /// signed or unsigned. 219 /// 220 /// \sa counterSort() 218 221 template <typename Iterator, typename Functor> 219 222 void radixSort(Iterator first, Iterator last, Functor functor) { … … 262 265 263 266 template <typename Functor, typename Key> 264 void counterIntroSort(Key *first, Key *last, Key *target, 265 266 const int size = 267 267 void counterIntroSort(Key *first, Key *last, Key *target, 268 int byte, Functor functor) { 269 const int size = 270 unsigned(std::numeric_limits<unsigned char>::max()) + 1; 268 271 std::vector<int> counter(size); 269 272 for (int i = 0; i < size; ++i) { 270 273 counter[i] = 0; 271 274 } 272 275 Key *it = first; 273 276 while (first != last) { 274 ++counter[valueByte(functor(*first), byte)]; 275 277 ++counter[valueByte(functor(*first), byte)]; 278 ++first; 276 279 } 277 280 int prev, num = 0; 278 281 for (int i = 0; i < size; ++i) { 279 280 281 282 prev = num; 283 num += counter[i]; 284 counter[i] = prev; 282 285 } 283 286 while (it != last) { 284 285 287 target[counter[valueByte(functor(*it), byte)]++] = *it; 288 ++it; 286 289 } 287 290 } 288 291 289 292 template <typename Functor, typename Key> 290 void signedCounterIntroSort(Key *first, Key *last, Key *target, 291 292 const int size = 293 293 void signedCounterIntroSort(Key *first, Key *last, Key *target, 294 int byte, Functor functor) { 295 const int size = 296 unsigned(std::numeric_limits<unsigned char>::max()) + 1; 294 297 std::vector<int> counter(size); 295 298 for (int i = 0; i < size; ++i) { 296 299 counter[i] = 0; 297 300 } 298 301 Key *it = first; 299 302 while (first != last) { 300 301 303 counter[valueByte(functor(*first), byte)]++; 304 ++first; 302 305 } 303 306 int prev, num = 0; 304 307 for (int i = size / 2; i < size; ++i) { 305 306 307 308 prev = num; 309 num += counter[i]; 310 counter[i] = prev; 308 311 } 309 312 for (int i = 0; i < size / 2; ++i) { 310 311 312 313 prev = num; 314 num += counter[i]; 315 counter[i] = prev; 313 316 } 314 317 while (it != last) { 315 316 317 } 318 } 319 320 318 target[counter[valueByte(functor(*it), byte)]++] = *it; 319 ++it; 320 } 321 } 322 323 321 324 template <typename Value, typename Iterator, typename Functor> 322 325 void counterSignedSort(Iterator first, Iterator last, Functor functor) { … … 329 332 Key* buffer = allocator.allocate(2 * length); 330 333 try { 331 332 333 334 335 counterIntroSort(buffer, buffer + length, buffer + length, 336 337 338 counterIntroSort(buffer + length, buffer + 2 * length, buffer, 339 340 341 342 343 344 signedCounterIntroSort(buffer, buffer + length, buffer + length, 345 346 347 }else {348 signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer, 349 350 351 334 bool dir = true; 335 std::copy(first, last, buffer); 336 for (int i = 0; i < int(sizeof(Value))  1; ++i) { 337 if (dir) { 338 counterIntroSort(buffer, buffer + length, buffer + length, 339 i, functor); 340 } else { 341 counterIntroSort(buffer + length, buffer + 2 * length, buffer, 342 i, functor); 343 } 344 dir = !dir; 345 } 346 if (dir) { 347 signedCounterIntroSort(buffer, buffer + length, buffer + length, 348 sizeof(Value)  1, functor); 349 std::copy(buffer + length, buffer + 2 * length, first); 350 } else { 351 signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer, 352 sizeof(Value)  1, functor); 353 std::copy(buffer, buffer + length, first); 354 } 352 355 } catch (...) { 353 354 356 allocator.deallocate(buffer, 2 * length); 357 throw; 355 358 } 356 359 allocator.deallocate(buffer, 2 * length); … … 367 370 Key *buffer = allocator.allocate(2 * length); 368 371 try { 369 370 371 372 373 counterIntroSort(buffer, buffer + length, 374 375 376 counterIntroSort(buffer + length, buffer + 2 * length, 377 378 379 380 381 382 383 }else {384 385 372 bool dir = true; 373 std::copy(first, last, buffer); 374 for (int i = 0; i < int(sizeof(Value)); ++i) { 375 if (dir) { 376 counterIntroSort(buffer, buffer + length, 377 buffer + length, i, functor); 378 } else { 379 counterIntroSort(buffer + length, buffer + 2 * length, 380 buffer, i, functor); 381 } 382 dir = !dir; 383 } 384 if (dir) { 385 std::copy(buffer, buffer + length, first); 386 } else { 387 std::copy(buffer + length, buffer + 2 * length, first); 388 } 386 389 } catch (...) { 387 388 390 allocator.deallocate(buffer, 2 * length); 391 throw; 389 392 } 390 393 allocator.deallocate(buffer, 2 * length); … … 393 396 394 397 395 template <typename Value, 396 398 template <typename Value, 399 bool sign = std::numeric_limits<Value>::is_signed > 397 400 struct CounterSortSelector { 398 401 template <typename Iterator, typename Functor> 399 402 static void sort(Iterator first, Iterator last, Functor functor) { 400 403 counterSignedSort<Value>(first, last, functor); 401 404 } 402 405 }; … … 406 409 template <typename Iterator, typename Functor> 407 410 static void sort(Iterator first, Iterator last, Functor functor) { 408 411 counterUnsignedSort<Value>(first, last, functor); 409 412 } 410 413 }; … … 414 417 /// \ingroup auxalg 415 418 /// 416 /// \brief Sorts stable the STL compatible range into ascending order. 417 /// 418 /// The \c counterSort sorts the STL compatible range into ascending 419 /// order. The counter sort algorithm can sort the items which 420 /// mapped to an integer with an adaptable unary function \c functor 421 /// and the order will be ascending by these mapped values. As 422 /// function specialization it is possible to use a normal function 423 /// instead of the functor object or if the functor is not given it 424 /// will use an identity function instead. 425 /// 426 /// The implemented counter sort use a radix forward sort on the 419 /// \brief Sorts the STL compatible range into ascending order in a stable 420 /// way. 421 /// 422 /// This function sorts an STL compatible range into ascending 423 /// order according to an integer mapping in the same as radixSort() does. 424 /// 425 /// This sorting algorithm is stable, i.e. the order of two equal 426 /// element remains the same after the sorting. 427 /// 428 /// This sort algorithm use a radix forward sort on the 427 429 /// bytes of the integer number. The algorithm sorts the items 428 /// bytebybyte, first it counts how many times occurs a byte value 429 /// in the containerm, and with the occurence number the container 430 /// can be copied to an other in asceding order in \c O(n) time. 431 /// Let be \c c the maximal capacity of the integer type and \c n 432 /// the number of the items in the container, the time complexity of 433 /// the algorithm is \f$ O(\log(c)n) \f$ and the additional space 434 /// complexity is \f$ O(n) \f$. 435 /// 436 /// The sorting algorithm is stable, i.e. the order of two equal 437 /// element remains the same. 438 /// 430 /// bytebybyte. First, it counts how many times a byte value occurs 431 /// in the container, then it copies the corresponding items to 432 /// another container in asceding order in \c O(n) time. 433 /// 434 /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and 435 /// it uses \f$ O(n) \f$, additional space, where \c c is the 436 /// maximal value and \c n is the number of the items in the 437 /// container. 438 /// 439 439 440 /// \param first The begin of the given range. 440 441 /// \param last The end of the given range. … … 442 443 /// which maps the items to any integer type which can be either 443 444 /// signed or unsigned. 445 /// \sa radixSort() 444 446 template <typename Iterator, typename Functor> 445 447 void counterSort(Iterator first, Iterator last, Functor functor) { 
test/radix_sort_test.cc
r464 r465 1 /* * C++*1 /* * mode: C++; indenttabsmode: nil; * 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 82 82 } 83 83 84 } 85 84 } 85 86 86 { 87 87 std::vector<unsigned char> data1(n); … … 122 122 check(data1[i] == data2[n  1  i], "Test failed"); 123 123 } 124 } 124 } 125 125 126 126 { … … 141 141 int main() { 142 142 143 checkRadixSort(); 143 checkRadixSort(); 144 144 checkCounterSort(); 145 145
Note: See TracChangeset
for help on using the changeset viewer.