COIN-OR::LEMON - Graph Library

source: lemon/lemon/radix_sort.h @ 464:4f7224faf3bd

Last change on this file since 464:4f7224faf3bd was 464:4f7224faf3bd, checked in by Balazs Dezso <deba@…>, 11 years ago

Porting radix sorts from SVN #3509

File size: 14.4 KB
Line 
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
33namespace 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
Note: See TracBrowser for help on using the repository browser.