COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_sort.h @ 1882:2c3f6c7e01b4

Last change on this file since 1882:2c3f6c7e01b4 was 1875:98698b69a902, checked in by Alpar Juttner, 14 years ago

Happy new year to LEMON

File size: 14.5 KB
Line 
1/* -*- C++ -*-
2 * lemon/radix_sort.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef RADIX_SORT_H
18#define RADIX_SORT_H
19
20/// \ingroup auxdat
21/// \file
22/// \brief Radix sort
23///
24
25#include <vector>
26#include <limits>
27#include <iterator>
28#include <algorithm>
29
30#include <lemon/error.h>
31
32namespace lemon {
33
34  namespace _radix_sort_bits {
35
36    template <typename Value>
37    struct Identity {
38      const Value& operator()(const Value& val) {
39        return val;
40      }
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    Iterator cut = radixSortSignPartition(first, last, functor);
133
134    Value mask;
135    int max_digit;
136    Iterator it;
137
138    mask = 0; max_digit = 0;
139    for (it = first; it != cut; ++it) {
140      if ((mask | functor(*it)) != ~0) {
141        ++max_digit;
142        mask <<= 1;
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      if (mask & functor(*it)) {
151        ++max_digit;
152        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      if (mask & functor(*it)) {
167        ++max_digit;
168        mask <<= 1;
169      }
170    }
171    radixIntroSort(first, last, functor, 1 << max_digit);
172  }
173
174  namespace _radix_sort_bits {
175
176    template <typename Value,
177              bool sign = std::numeric_limits<Value>::is_signed >
178    struct RadixSortSelector {
179      template <typename Iterator, typename Functor>
180      static void sort(Iterator first, Iterator last, Functor functor) {
181        radixSignedSort<Value>(first, last, functor);
182      }
183    };
184
185    template <typename Value>
186    struct RadixSortSelector<Value, false> {
187      template <typename Iterator, typename Functor>
188      static void sort(Iterator first, Iterator last, Functor functor) {
189        radixUnsignedSort<Value>(first, last, functor);
190      }
191    };
192
193  }
194
195  /// \ingroup auxdat
196  ///
197  /// \brief Sorts the stl compatible range into ascending order.
198  ///
199  /// The \c radixSort sorts the stl compatible range into ascending order.
200  /// The radix sort algorithm can sort the items which mapped to an
201  /// integer by the adaptable unary function \c functor and the order
202  /// will be ascending by these mapped values. As function specialization
203  /// there is possible to use a normal function as the functor object
204  /// or if the functor is not given it will use an identity function instead.
205  ///
206  /// This implemented radix sort is a special quick sort which pivot value
207  /// is choosen to partite the items on the next bit. This way, let be
208  /// \c c the maximal capacity and \c n the number of the items in
209  /// the container, the time complexity of the algorithm \c O(log(c)*n)
210  /// and the additional space complexity is \c O(log(c)).
211  ///
212  /// \param first The begin of the given range.
213  /// \param last The end of the given range.
214  /// \param functor An adaptible unary function or a normal function which
215  /// maps the items to any integer type which can be wheter signed or
216  /// unsigned.
217  template <typename Iterator, typename Functor>
218  void radixSort(Iterator first, Iterator last, Functor functor) {
219    using namespace _radix_sort_bits;
220    typedef typename Functor::result_type Value;
221    RadixSortSelector<Value>::sort(first, last, functor);
222  }
223
224  template <typename Iterator, typename Value, typename Key>
225  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
226    using namespace _radix_sort_bits;
227    RadixSortSelector<Value>::sort(first, last, functor);
228  }
229
230  template <typename Iterator, typename Value, typename Key>
231  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
232    using namespace _radix_sort_bits;
233    RadixSortSelector<Value>::sort(first, last, functor);
234  }
235
236  template <typename Iterator, typename Value, typename Key>
237  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
238    using namespace _radix_sort_bits;
239    RadixSortSelector<Value>::sort(first, last, functor);
240  }
241
242  template <typename Iterator, typename Value, typename Key>
243  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
244    using namespace _radix_sort_bits;
245    RadixSortSelector<Value>::sort(first, last, functor);
246  }
247
248  template <typename Iterator>
249  void radixSort(Iterator first, Iterator last) {
250    using namespace _radix_sort_bits;
251    typedef typename std::iterator_traits<Iterator>::value_type Value;
252    RadixSortSelector<Value>::sort(first, last, Identity<Value>());
253  }
254
255  template <typename Value>
256  unsigned char valueByte(Value value, int byte) {
257    return value >> (std::numeric_limits<unsigned char>::digits * byte);
258  }
259
260  template <typename Functor, typename Key>
261  void counterIntroSort(Key *first, Key *last, Key *target,
262                       int byte, Functor functor) {
263    const int size =
264      (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
265    int counter[size];
266    for (int i = 0; i < size; ++i) {
267      counter[i] = 0;
268    }
269    Key *it = first;
270    while (first != last) {
271      ++counter[valueByte(functor(*first), byte)];
272      ++first;
273    }
274    int prev, num = 0;
275    for (int i = 0; i < size; ++i) {
276      prev = num;
277      num += counter[i];
278      counter[i] = prev;
279    }
280    while (it != last) {
281      target[counter[valueByte(functor(*it), byte)]++] = *it;
282      ++it;
283    }
284  }
285
286  template <typename Functor, typename Key>
287  void signedCounterIntroSort(Key *first, Key *last, Key *target,
288                             int byte, Functor functor) {
289    const int size =
290      (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
291    int counter[size];
292    for (int i = 0; i < size; ++i) {
293      counter[i] = 0;
294    }
295    Key *it = first;
296    while (first != last) {
297      counter[valueByte(functor(*first), byte)]++;
298      ++first;
299    }
300    int prev, num = 0;
301    for (int i = size / 2; i < size; ++i) {
302      prev = num;
303      num += counter[i];
304      counter[i] = prev;
305    }
306    for (int i = 0; i < size / 2; ++i) {
307      prev = num;
308      num += counter[i];
309      counter[i] = prev;
310    }
311    while (it != last) {
312      target[counter[valueByte(functor(*it), byte)]++] = *it;
313      ++it;
314    }
315  }
316
317 
318  template <typename Value, typename Iterator, typename Functor>
319  void counterSignedSort(Iterator first, Iterator last, Functor functor) {
320    typedef typename std::iterator_traits<Iterator>::value_type Key;
321    typedef std::allocator<Key> Allocator;
322    Allocator allocator;
323
324    int length = std::distance(first, last);
325    Key* buffer;
326    buffer = allocator.allocate(2 * length);
327    try {
328      bool dir = true;
329      std::copy(first, last, buffer);
330      for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
331        if (dir) {
332          counterIntroSort(buffer, buffer + length, buffer + length,
333                           i, functor);
334        } else {
335          counterIntroSort(buffer + length, buffer + 2 * length, buffer,
336                           i, functor);
337        }
338        dir = !dir;
339      }
340      if (dir) {
341        signedCounterIntroSort(buffer, buffer + length, buffer + length,
342                               sizeof(Value) - 1, functor);
343        std::copy(buffer + length, buffer + 2 * length, first);
344      } else {
345        signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
346                               sizeof(Value) - 1, functor);
347        std::copy(buffer, buffer + length, first);
348      }
349    } catch (...) {
350      allocator.deallocate(buffer, 2 * length);
351      throw;
352    }
353    allocator.deallocate(buffer, 2 * length);
354  }
355
356  template <typename Value, typename Iterator, typename Functor>
357  void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
358    typedef typename std::iterator_traits<Iterator>::value_type Key;
359    typedef std::allocator<Key> Allocator;
360    Allocator allocator;
361
362    int length = std::distance(first, last);
363    Key *buffer;
364    buffer = allocator.allocate(2 * length);
365    try {
366      bool dir = true;
367      std::copy(first, last, buffer);
368      for (int i = 0; i < (int)sizeof(Value); ++i) {
369        if (dir) {
370          counterIntroSort(buffer, buffer + length, buffer + length, i, functor);
371        } else {
372          counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
373        }
374        dir = !dir;
375      }
376      if (dir) {
377        std::copy(buffer, buffer + length, first);
378      } else {
379        std::copy(buffer + length, buffer + 2 * length, first);
380      }
381    } catch (...) {
382      allocator.deallocate(buffer, 2 * length);
383      throw;
384    }
385    allocator.deallocate(buffer, 2 * length);
386  }
387
388  namespace _radix_sort_bits {
389
390    template <typename Value,
391              bool sign = std::numeric_limits<Value>::is_signed >
392    struct CounterSortSelector {
393      template <typename Iterator, typename Functor>
394      static void sort(Iterator first, Iterator last, Functor functor) {
395        counterSignedSort<Value>(first, last, functor);
396      }
397    };
398
399    template <typename Value>
400    struct CounterSortSelector<Value, false> {
401      template <typename Iterator, typename Functor>
402      static void sort(Iterator first, Iterator last, Functor functor) {
403        counterUnsignedSort<Value>(first, last, functor);
404      }
405    };
406
407  }
408
409  /// \ingroup auxdat
410  ///
411  /// \brief Sorts stable the stl compatible range into ascending order.
412  ///
413  /// The \c counterSort sorts the stl compatible range into ascending order.
414  /// The counter sort algorithm can sort the items which mapped to an
415  /// integer by the adaptable unary function \c functor and the order
416  /// will be ascending by these mapped values. As function specialization
417  /// there is possible to use a normal function as the functor object
418  /// or if the functor is not given it will use an identity function instead.
419  ///
420  /// This implemented counter sort use a radix forward sort on the bytes of
421  /// the integer. The algorithm can sort the items on a given byte.
422  /// First time it counts how many times occurs a byte value in the container.
423  /// By the occurence number it is possible to copy the container
424  /// in the right order in \c O(n) time. The algorithm sorts the container
425  /// by each bytes in forward direction which sorts the container by the
426  /// whole value. This way, let be \c c the maximal capacity of the integer
427  /// type and \c n the number of the items in
428  /// the container, the time complexity of the algorithm \c O(log(c)*n)
429  /// and the additional space complexity is \c O(n).
430  ///
431  /// This sorting algorithm is stable so the order of two equal element
432  /// stay in the same order.
433  ///
434  /// \param first The begin of the given range.
435  /// \param last The end of the given range.
436  /// \param functor An adaptible unary function or a normal function which
437  /// maps the items to any integer type which can be wheter signed or
438  /// unsigned.
439  template <typename Iterator, typename Functor>
440  void counterSort(Iterator first, Iterator last, Functor functor) {
441    using namespace _radix_sort_bits;
442    typedef typename Functor::result_type Value;
443    CounterSortSelector<Value>::sort(first, last, functor);
444  }
445
446  template <typename Iterator, typename Value, typename Key>
447  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
448    using namespace _radix_sort_bits;
449    CounterSortSelector<Value>::sort(first, last, functor);
450  }
451
452  template <typename Iterator, typename Value, typename Key>
453  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
454    using namespace _radix_sort_bits;
455    CounterSortSelector<Value>::sort(first, last, functor);
456  }
457
458  template <typename Iterator, typename Value, typename Key>
459  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
460    using namespace _radix_sort_bits;
461    CounterSortSelector<Value>::sort(first, last, functor);
462  }
463
464  template <typename Iterator, typename Value, typename Key>
465  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
466    using namespace _radix_sort_bits;
467    CounterSortSelector<Value>::sort(first, last, functor);
468  }
469
470  template <typename Iterator>
471  void counterSort(Iterator first, Iterator last) {
472    using namespace _radix_sort_bits;
473    typedef typename std::iterator_traits<Iterator>::value_type Value;
474    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
475  }
476
477}
478
479
480
481#endif
Note: See TracBrowser for help on using the repository browser.