|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef RADIX_SORT_H |
|
20 #define RADIX_SORT_H |
|
21 |
|
22 /// \ingroup auxalg |
|
23 /// \file |
|
24 /// \brief Radix sort |
|
25 /// |
|
26 /// Linear time sorting algorithms |
|
27 |
|
28 #include <vector> |
|
29 #include <limits> |
|
30 #include <iterator> |
|
31 #include <algorithm> |
|
32 |
|
33 namespace lemon { |
|
34 |
|
35 namespace _radix_sort_bits { |
|
36 |
|
37 template <typename Value> |
|
38 struct Identity { |
|
39 const Value& operator()(const Value& val) { |
|
40 return val; |
|
41 } |
|
42 }; |
|
43 |
|
44 |
|
45 template <typename Value, typename Iterator, typename Functor> |
|
46 Iterator radixSortPartition(Iterator first, Iterator last, |
|
47 Functor functor, Value mask) { |
|
48 while (first != last && !(functor(*first) & mask)) { |
|
49 ++first; |
|
50 } |
|
51 if (first == last) { |
|
52 return first; |
|
53 } |
|
54 --last; |
|
55 while (first != last && (functor(*last) & mask)) { |
|
56 --last; |
|
57 } |
|
58 if (first == last) { |
|
59 return first; |
|
60 } |
|
61 std::iter_swap(first, last); |
|
62 ++first; |
|
63 if (!(first < last)) { |
|
64 return first; |
|
65 } |
|
66 while (true) { |
|
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 } |
|
80 } |
|
81 |
|
82 template <typename Iterator, typename Functor> |
|
83 Iterator radixSortSignPartition(Iterator first, Iterator last, |
|
84 Functor functor) { |
|
85 while (first != last && functor(*first) < 0) { |
|
86 ++first; |
|
87 } |
|
88 if (first == last) { |
|
89 return first; |
|
90 } |
|
91 --last; |
|
92 while (first != last && functor(*last) >= 0) { |
|
93 --last; |
|
94 } |
|
95 if (first == last) { |
|
96 return first; |
|
97 } |
|
98 std::iter_swap(first, last); |
|
99 ++first; |
|
100 if (!(first < last)) { |
|
101 return first; |
|
102 } |
|
103 while (true) { |
|
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 while (mask != 0 && last - first > 1) { |
|
123 Iterator cut = radixSortPartition(first, last, functor, mask); |
|
124 mask >>= 1; |
|
125 radixIntroSort(first, cut, functor, mask); |
|
126 first = cut; |
|
127 } |
|
128 } |
|
129 |
|
130 template <typename Value, typename Iterator, typename Functor> |
|
131 void radixSignedSort(Iterator first, Iterator last, Functor functor) { |
|
132 |
|
133 Iterator cut = radixSortSignPartition(first, last, functor); |
|
134 |
|
135 Value mask; |
|
136 int max_digit; |
|
137 Iterator it; |
|
138 |
|
139 mask = ~0; max_digit = 0; |
|
140 for (it = first; it != cut; ++it) { |
|
141 while ((mask & functor(*it)) != mask) { |
|
142 ++max_digit; |
|
143 mask <<= 1; |
|
144 } |
|
145 } |
|
146 radixIntroSort(first, cut, functor, 1 << max_digit); |
|
147 |
|
148 mask = 0; max_digit = 0; |
|
149 for (it = cut; it != last; ++it) { |
|
150 while ((mask | functor(*it)) != mask) { |
|
151 ++max_digit; |
|
152 mask <<= 1; mask |= 1; |
|
153 } |
|
154 } |
|
155 radixIntroSort(cut, last, functor, 1 << max_digit); |
|
156 } |
|
157 |
|
158 template <typename Value, typename Iterator, typename Functor> |
|
159 void radixUnsignedSort(Iterator first, Iterator last, Functor functor) { |
|
160 |
|
161 Value mask = 0; |
|
162 int max_digit = 0; |
|
163 |
|
164 Iterator it; |
|
165 for (it = first; it != last; ++it) { |
|
166 while ((mask | functor(*it)) != mask) { |
|
167 ++max_digit; |
|
168 mask <<= 1; mask |= 1; |
|
169 } |
|
170 } |
|
171 radixIntroSort(first, last, functor, 1 << max_digit); |
|
172 } |
|
173 |
|
174 |
|
175 template <typename Value, |
|
176 bool sign = std::numeric_limits<Value>::is_signed > |
|
177 struct RadixSortSelector { |
|
178 template <typename Iterator, typename Functor> |
|
179 static void sort(Iterator first, Iterator last, Functor functor) { |
|
180 radixSignedSort<Value>(first, last, functor); |
|
181 } |
|
182 }; |
|
183 |
|
184 template <typename Value> |
|
185 struct RadixSortSelector<Value, false> { |
|
186 template <typename Iterator, typename Functor> |
|
187 static void sort(Iterator first, Iterator last, Functor functor) { |
|
188 radixUnsignedSort<Value>(first, last, functor); |
|
189 } |
|
190 }; |
|
191 |
|
192 } |
|
193 |
|
194 /// \ingroup auxalg |
|
195 /// |
|
196 /// \brief Sorts the STL compatible range into ascending order. |
|
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$. |
|
212 /// |
|
213 /// \param first The begin of the given range. |
|
214 /// \param last The end of the given range. |
|
215 /// \param functor An adaptible unary function or a normal function |
|
216 /// which maps the items to any integer type which can be either |
|
217 /// signed or unsigned. |
|
218 template <typename Iterator, typename Functor> |
|
219 void radixSort(Iterator first, Iterator last, Functor functor) { |
|
220 using namespace _radix_sort_bits; |
|
221 typedef typename Functor::result_type Value; |
|
222 RadixSortSelector<Value>::sort(first, last, functor); |
|
223 } |
|
224 |
|
225 template <typename Iterator, typename Value, typename Key> |
|
226 void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) { |
|
227 using namespace _radix_sort_bits; |
|
228 RadixSortSelector<Value>::sort(first, last, functor); |
|
229 } |
|
230 |
|
231 template <typename Iterator, typename Value, typename Key> |
|
232 void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) { |
|
233 using namespace _radix_sort_bits; |
|
234 RadixSortSelector<Value>::sort(first, last, functor); |
|
235 } |
|
236 |
|
237 template <typename Iterator, typename Value, typename Key> |
|
238 void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) { |
|
239 using namespace _radix_sort_bits; |
|
240 RadixSortSelector<Value>::sort(first, last, functor); |
|
241 } |
|
242 |
|
243 template <typename Iterator, typename Value, typename Key> |
|
244 void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { |
|
245 using namespace _radix_sort_bits; |
|
246 RadixSortSelector<Value>::sort(first, last, functor); |
|
247 } |
|
248 |
|
249 template <typename Iterator> |
|
250 void radixSort(Iterator first, Iterator last) { |
|
251 using namespace _radix_sort_bits; |
|
252 typedef typename std::iterator_traits<Iterator>::value_type Value; |
|
253 RadixSortSelector<Value>::sort(first, last, Identity<Value>()); |
|
254 } |
|
255 |
|
256 namespace _radix_sort_bits { |
|
257 |
|
258 template <typename Value> |
|
259 unsigned char valueByte(Value value, int byte) { |
|
260 return value >> (std::numeric_limits<unsigned char>::digits * byte); |
|
261 } |
|
262 |
|
263 template <typename Functor, typename Key> |
|
264 void counterIntroSort(Key *first, Key *last, Key *target, |
|
265 int byte, Functor functor) { |
|
266 const int size = |
|
267 unsigned(std::numeric_limits<unsigned char>::max()) + 1; |
|
268 std::vector<int> counter(size); |
|
269 for (int i = 0; i < size; ++i) { |
|
270 counter[i] = 0; |
|
271 } |
|
272 Key *it = first; |
|
273 while (first != last) { |
|
274 ++counter[valueByte(functor(*first), byte)]; |
|
275 ++first; |
|
276 } |
|
277 int prev, num = 0; |
|
278 for (int i = 0; i < size; ++i) { |
|
279 prev = num; |
|
280 num += counter[i]; |
|
281 counter[i] = prev; |
|
282 } |
|
283 while (it != last) { |
|
284 target[counter[valueByte(functor(*it), byte)]++] = *it; |
|
285 ++it; |
|
286 } |
|
287 } |
|
288 |
|
289 template <typename Functor, typename Key> |
|
290 void signedCounterIntroSort(Key *first, Key *last, Key *target, |
|
291 int byte, Functor functor) { |
|
292 const int size = |
|
293 unsigned(std::numeric_limits<unsigned char>::max()) + 1; |
|
294 std::vector<int> counter(size); |
|
295 for (int i = 0; i < size; ++i) { |
|
296 counter[i] = 0; |
|
297 } |
|
298 Key *it = first; |
|
299 while (first != last) { |
|
300 counter[valueByte(functor(*first), byte)]++; |
|
301 ++first; |
|
302 } |
|
303 int prev, num = 0; |
|
304 for (int i = size / 2; i < size; ++i) { |
|
305 prev = num; |
|
306 num += counter[i]; |
|
307 counter[i] = prev; |
|
308 } |
|
309 for (int i = 0; i < size / 2; ++i) { |
|
310 prev = num; |
|
311 num += counter[i]; |
|
312 counter[i] = prev; |
|
313 } |
|
314 while (it != last) { |
|
315 target[counter[valueByte(functor(*it), byte)]++] = *it; |
|
316 ++it; |
|
317 } |
|
318 } |
|
319 |
|
320 |
|
321 template <typename Value, typename Iterator, typename Functor> |
|
322 void counterSignedSort(Iterator first, Iterator last, Functor functor) { |
|
323 if (first == last) return; |
|
324 typedef typename std::iterator_traits<Iterator>::value_type Key; |
|
325 typedef std::allocator<Key> Allocator; |
|
326 Allocator allocator; |
|
327 |
|
328 int length = std::distance(first, last); |
|
329 Key* buffer = allocator.allocate(2 * length); |
|
330 try { |
|
331 bool dir = true; |
|
332 std::copy(first, last, buffer); |
|
333 for (int i = 0; i < int(sizeof(Value)) - 1; ++i) { |
|
334 if (dir) { |
|
335 counterIntroSort(buffer, buffer + length, buffer + length, |
|
336 i, functor); |
|
337 } else { |
|
338 counterIntroSort(buffer + length, buffer + 2 * length, buffer, |
|
339 i, functor); |
|
340 } |
|
341 dir = !dir; |
|
342 } |
|
343 if (dir) { |
|
344 signedCounterIntroSort(buffer, buffer + length, buffer + length, |
|
345 sizeof(Value) - 1, functor); |
|
346 std::copy(buffer + length, buffer + 2 * length, first); |
|
347 } else { |
|
348 signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer, |
|
349 sizeof(Value) - 1, functor); |
|
350 std::copy(buffer, buffer + length, first); |
|
351 } |
|
352 } catch (...) { |
|
353 allocator.deallocate(buffer, 2 * length); |
|
354 throw; |
|
355 } |
|
356 allocator.deallocate(buffer, 2 * length); |
|
357 } |
|
358 |
|
359 template <typename Value, typename Iterator, typename Functor> |
|
360 void counterUnsignedSort(Iterator first, Iterator last, Functor functor) { |
|
361 if (first == last) return; |
|
362 typedef typename std::iterator_traits<Iterator>::value_type Key; |
|
363 typedef std::allocator<Key> Allocator; |
|
364 Allocator allocator; |
|
365 |
|
366 int length = std::distance(first, last); |
|
367 Key *buffer = allocator.allocate(2 * length); |
|
368 try { |
|
369 bool dir = true; |
|
370 std::copy(first, last, buffer); |
|
371 for (int i = 0; i < int(sizeof(Value)); ++i) { |
|
372 if (dir) { |
|
373 counterIntroSort(buffer, buffer + length, |
|
374 buffer + length, i, functor); |
|
375 } else { |
|
376 counterIntroSort(buffer + length, buffer + 2 * length, |
|
377 buffer, i, functor); |
|
378 } |
|
379 dir = !dir; |
|
380 } |
|
381 if (dir) { |
|
382 std::copy(buffer, buffer + length, first); |
|
383 } else { |
|
384 std::copy(buffer + length, buffer + 2 * length, first); |
|
385 } |
|
386 } catch (...) { |
|
387 allocator.deallocate(buffer, 2 * length); |
|
388 throw; |
|
389 } |
|
390 allocator.deallocate(buffer, 2 * length); |
|
391 } |
|
392 |
|
393 |
|
394 |
|
395 template <typename Value, |
|
396 bool sign = std::numeric_limits<Value>::is_signed > |
|
397 struct CounterSortSelector { |
|
398 template <typename Iterator, typename Functor> |
|
399 static void sort(Iterator first, Iterator last, Functor functor) { |
|
400 counterSignedSort<Value>(first, last, functor); |
|
401 } |
|
402 }; |
|
403 |
|
404 template <typename Value> |
|
405 struct CounterSortSelector<Value, false> { |
|
406 template <typename Iterator, typename Functor> |
|
407 static void sort(Iterator first, Iterator last, Functor functor) { |
|
408 counterUnsignedSort<Value>(first, last, functor); |
|
409 } |
|
410 }; |
|
411 |
|
412 } |
|
413 |
|
414 /// \ingroup auxalg |
|
415 /// |
|
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 |
|
427 /// bytes of the integer number. The algorithm sorts the items |
|
428 /// byte-by-byte, 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 /// |
|
439 /// \param first The begin of the given range. |
|
440 /// \param last The end of the given range. |
|
441 /// \param functor An adaptible unary function or a normal function |
|
442 /// which maps the items to any integer type which can be either |
|
443 /// signed or unsigned. |
|
444 template <typename Iterator, typename Functor> |
|
445 void counterSort(Iterator first, Iterator last, Functor functor) { |
|
446 using namespace _radix_sort_bits; |
|
447 typedef typename Functor::result_type Value; |
|
448 CounterSortSelector<Value>::sort(first, last, functor); |
|
449 } |
|
450 |
|
451 template <typename Iterator, typename Value, typename Key> |
|
452 void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) { |
|
453 using namespace _radix_sort_bits; |
|
454 CounterSortSelector<Value>::sort(first, last, functor); |
|
455 } |
|
456 |
|
457 template <typename Iterator, typename Value, typename Key> |
|
458 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) { |
|
459 using namespace _radix_sort_bits; |
|
460 CounterSortSelector<Value>::sort(first, last, functor); |
|
461 } |
|
462 |
|
463 template <typename Iterator, typename Value, typename Key> |
|
464 void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) { |
|
465 using namespace _radix_sort_bits; |
|
466 CounterSortSelector<Value>::sort(first, last, functor); |
|
467 } |
|
468 |
|
469 template <typename Iterator, typename Value, typename Key> |
|
470 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { |
|
471 using namespace _radix_sort_bits; |
|
472 CounterSortSelector<Value>::sort(first, last, functor); |
|
473 } |
|
474 |
|
475 template <typename Iterator> |
|
476 void counterSort(Iterator first, Iterator last) { |
|
477 using namespace _radix_sort_bits; |
|
478 typedef typename std::iterator_traits<Iterator>::value_type Value; |
|
479 CounterSortSelector<Value>::sort(first, last, Identity<Value>()); |
|
480 } |
|
481 |
|
482 } |
|
483 |
|
484 #endif |