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