COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_sort.h @ 2527:10f3b3286e63

Last change on this file since 2527:10f3b3286e63 was 2479:221cfaf118a6, checked in by Balazs Dezso, 17 years ago

Once again bug fix in significant bit calculation

File size: 14.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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
27#include <vector>
28#include <limits>
29#include <iterator>
30#include <algorithm>
31
32#include <lemon/error.h>
33
34namespace lemon {
35
36  namespace _radix_sort_bits {
37
38    template <typename Value>
39    struct Identity {
40      const Value& operator()(const Value& val) {
41        return val;
42      }
43    };
44
45  }
46
47  template <typename Value, typename Iterator, typename Functor>
48  Iterator radixSortPartition(Iterator first, Iterator last,
49                              Functor functor, Value mask) {
50    while (first != last && !(functor(*first) & mask)) {
51      ++first;
52    }
53    if (first == last) {
54      return first;
55    }
56    --last;
57    while (first != last && (functor(*last) & mask)) {
58      --last;
59    }
60    if (first == last) {
61      return first;
62    }
63    std::iter_swap(first, last);
64    ++first;
65    if (!(first < last)) {
66      return first;
67    }
68    while (true) {
69      while (!(functor(*first) & mask)) {
70        ++first;
71      }
72      --last;
73      while (functor(*last) & mask) {
74        --last;
75      }
76      if (!(first < last)) {
77        return first;
78      }
79      std::iter_swap(first, last);
80      ++first;
81    }
82  }
83
84  template <typename Iterator, typename Functor>
85  Iterator radixSortSignPartition(Iterator first, Iterator last,
86                                  Functor functor) {
87    while (first != last && functor(*first) < 0) {
88      ++first;
89    }
90    if (first == last) {
91      return first;
92    }
93    --last;
94    while (first != last && functor(*last) >= 0) {
95      --last;
96    }
97    if (first == last) {
98      return first;
99    }
100    std::iter_swap(first, last);
101    ++first;
102    if (!(first < last)) {
103      return first;
104    }
105    while (true) {
106      while (functor(*first) < 0) {
107        ++first;
108      }
109      --last;
110      while (functor(*last) >= 0) {
111        --last;
112      }
113      if (!(first < last)) {
114        return first;
115      }
116      std::iter_swap(first, last);
117      ++first;
118    }
119  }
120
121  template <typename Value, typename Iterator, typename Functor>
122  void radixIntroSort(Iterator first, Iterator last,
123                      Functor functor, Value mask) {
124    while (mask != 0 && last - first > 1) {
125      Iterator cut = radixSortPartition(first, last, functor, mask);
126      mask >>= 1;
127      radixIntroSort(first, cut, functor, mask);
128      first = cut;
129    }
130  }
131
132  template <typename Value, typename Iterator, typename Functor>
133  void radixSignedSort(Iterator first, Iterator last, Functor functor) {
134    Iterator cut = radixSortSignPartition(first, last, functor);
135
136    Value mask;
137    int max_digit;
138    Iterator it;
139
140    mask = ~0; max_digit = 0;
141    for (it = first; it != cut; ++it) {
142      while ((mask & functor(*it)) != mask) {
143        ++max_digit;
144        mask <<= 1;
145      }
146    }
147    radixIntroSort(first, cut, functor, 1 << max_digit);
148
149    mask = 0; max_digit = 0;
150    for (it = cut; it != last; ++it) {
151      while ((mask | functor(*it)) != mask) {
152        ++max_digit;
153        mask <<= 1; mask |= 1;
154      }
155    }
156    radixIntroSort(cut, last, functor, 1 << max_digit);
157  }
158
159  template <typename Value, typename Iterator, typename Functor>
160  void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
161
162    Value mask = 0;
163    int max_digit = 0;
164
165    Iterator it;
166    for (it = first; it != last; ++it) {
167      while ((mask | functor(*it)) != mask) {
168        ++max_digit;
169        mask <<= 1; mask |= 1;
170      }
171    }
172    radixIntroSort(first, last, functor, 1 << max_digit);
173  }
174
175  namespace _radix_sort_bits {
176
177    template <typename Value,
178              bool sign = std::numeric_limits<Value>::is_signed >
179    struct RadixSortSelector {
180      template <typename Iterator, typename Functor>
181      static void sort(Iterator first, Iterator last, Functor functor) {
182        radixSignedSort<Value>(first, last, functor);
183      }
184    };
185
186    template <typename Value>
187    struct RadixSortSelector<Value, false> {
188      template <typename Iterator, typename Functor>
189      static void sort(Iterator first, Iterator last, Functor functor) {
190        radixUnsignedSort<Value>(first, last, functor);
191      }
192    };
193
194  }
195
196  /// \ingroup auxalg
197  ///
198  /// \brief Sorts the stl compatible range into ascending order.
199  ///
200  /// The \c radixSort sorts the stl compatible range into ascending order.
201  /// The radix sort algorithm can sort the items which mapped to an
202  /// integer by the adaptable unary function \c functor and the order
203  /// will be ascending by these mapped values. As function specialization
204  /// there is possible to use a normal function as the functor object
205  /// or if the functor is not given it will use an identity function instead.
206  ///
207  /// This implemented radix sort is a special quick sort which pivot value
208  /// is choosen to partite the items on the next bit. This way, let be
209  /// \c c the maximal capacity and \c n the number of the items in
210  /// the container, the time complexity of the algorithm
211  /// \f$ O(\log(c)n) \f$ and the additional space complexity is
212  /// \f$ O(\log(c)) \f$.
213  ///
214  /// \param first The begin of the given range.
215  /// \param last The end of the given range.
216  /// \param functor An adaptible unary function or a normal function which
217  /// maps the items to any integer type which can be wheter signed or
218  /// unsigned.
219  template <typename Iterator, typename Functor>
220  void radixSort(Iterator first, Iterator last, Functor functor) {
221    using namespace _radix_sort_bits;
222    typedef typename Functor::result_type Value;
223    RadixSortSelector<Value>::sort(first, last, functor);
224  }
225
226  template <typename Iterator, typename Value, typename Key>
227  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
228    using namespace _radix_sort_bits;
229    RadixSortSelector<Value>::sort(first, last, functor);
230  }
231
232  template <typename Iterator, typename Value, typename Key>
233  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
234    using namespace _radix_sort_bits;
235    RadixSortSelector<Value>::sort(first, last, functor);
236  }
237
238  template <typename Iterator, typename Value, typename Key>
239  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
240    using namespace _radix_sort_bits;
241    RadixSortSelector<Value>::sort(first, last, functor);
242  }
243
244  template <typename Iterator, typename Value, typename Key>
245  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
246    using namespace _radix_sort_bits;
247    RadixSortSelector<Value>::sort(first, last, functor);
248  }
249
250  template <typename Iterator>
251  void radixSort(Iterator first, Iterator last) {
252    using namespace _radix_sort_bits;
253    typedef typename std::iterator_traits<Iterator>::value_type Value;
254    RadixSortSelector<Value>::sort(first, last, Identity<Value>());
255  }
256
257  template <typename Value>
258  unsigned char valueByte(Value value, int byte) {
259    return value >> (std::numeric_limits<unsigned char>::digits * byte);
260  }
261
262  template <typename Functor, typename Key>
263  void counterIntroSort(Key *first, Key *last, Key *target,
264                       int byte, Functor functor) {
265    const int size =
266      unsigned(std::numeric_limits<unsigned char>::max()) + 1;
267    std::vector<int> counter(size);
268    for (int i = 0; i < size; ++i) {
269      counter[i] = 0;
270    }
271    Key *it = first;
272    while (first != last) {
273      ++counter[valueByte(functor(*first), byte)];
274      ++first;
275    }
276    int prev, num = 0;
277    for (int i = 0; i < size; ++i) {
278      prev = num;
279      num += counter[i];
280      counter[i] = prev;
281    }
282    while (it != last) {
283      target[counter[valueByte(functor(*it), byte)]++] = *it;
284      ++it;
285    }
286  }
287
288  template <typename Functor, typename Key>
289  void signedCounterIntroSort(Key *first, Key *last, Key *target,
290                             int byte, Functor functor) {
291    const int size =
292      unsigned(std::numeric_limits<unsigned char>::max()) + 1;
293    std::vector<int> counter(size);
294    for (int i = 0; i < size; ++i) {
295      counter[i] = 0;
296    }
297    Key *it = first;
298    while (first != last) {
299      counter[valueByte(functor(*first), byte)]++;
300      ++first;
301    }
302    int prev, num = 0;
303    for (int i = size / 2; i < size; ++i) {
304      prev = num;
305      num += counter[i];
306      counter[i] = prev;
307    }
308    for (int i = 0; i < size / 2; ++i) {
309      prev = num;
310      num += counter[i];
311      counter[i] = prev;
312    }
313    while (it != last) {
314      target[counter[valueByte(functor(*it), byte)]++] = *it;
315      ++it;
316    }
317  }
318
319 
320  template <typename Value, typename Iterator, typename Functor>
321  void counterSignedSort(Iterator first, Iterator last, Functor functor) {
322    if (first == last) return;
323    typedef typename std::iterator_traits<Iterator>::value_type Key;
324    typedef std::allocator<Key> Allocator;
325    Allocator allocator;
326
327    int length = std::distance(first, last);
328    Key* buffer = allocator.allocate(2 * length);
329    try {
330      bool dir = true;
331      std::copy(first, last, buffer);
332      for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
333        if (dir) {
334          counterIntroSort(buffer, buffer + length, buffer + length,
335                           i, functor);
336        } else {
337          counterIntroSort(buffer + length, buffer + 2 * length, buffer,
338                           i, functor);
339        }
340        dir = !dir;
341      }
342      if (dir) {
343        signedCounterIntroSort(buffer, buffer + length, buffer + length,
344                               sizeof(Value) - 1, functor);
345        std::copy(buffer + length, buffer + 2 * length, first);
346      } else {
347        signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
348                               sizeof(Value) - 1, functor);
349        std::copy(buffer, buffer + length, first);
350      }
351    } catch (...) {
352      allocator.deallocate(buffer, 2 * length);
353      throw;
354    }
355    allocator.deallocate(buffer, 2 * length);
356  }
357
358  template <typename Value, typename Iterator, typename Functor>
359  void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
360    if (first == last) return;
361    typedef typename std::iterator_traits<Iterator>::value_type Key;
362    typedef std::allocator<Key> Allocator;
363    Allocator allocator;
364
365    int length = std::distance(first, last);
366    Key *buffer = allocator.allocate(2 * length);
367    try {
368      bool dir = true;
369      std::copy(first, last, buffer);
370      for (int i = 0; i < int(sizeof(Value)); ++i) {
371        if (dir) {
372          counterIntroSort(buffer, buffer + length,
373                           buffer + length, i, functor);
374        } else {
375          counterIntroSort(buffer + length, buffer + 2 * length,
376                           buffer, i, functor);
377        }
378        dir = !dir;
379      }
380      if (dir) {
381        std::copy(buffer, buffer + length, first);
382      } else {
383        std::copy(buffer + length, buffer + 2 * length, first);
384      }
385    } catch (...) {
386      allocator.deallocate(buffer, 2 * length);
387      throw;
388    }
389    allocator.deallocate(buffer, 2 * length);
390  }
391
392  namespace _radix_sort_bits {
393
394    template <typename Value,
395              bool sign = std::numeric_limits<Value>::is_signed >
396    struct CounterSortSelector {
397      template <typename Iterator, typename Functor>
398      static void sort(Iterator first, Iterator last, Functor functor) {
399        counterSignedSort<Value>(first, last, functor);
400      }
401    };
402
403    template <typename Value>
404    struct CounterSortSelector<Value, false> {
405      template <typename Iterator, typename Functor>
406      static void sort(Iterator first, Iterator last, Functor functor) {
407        counterUnsignedSort<Value>(first, last, functor);
408      }
409    };
410
411  }
412
413  /// \ingroup auxalg
414  ///
415  /// \brief Sorts stable the stl compatible range into ascending order.
416  ///
417  /// The \c counterSort sorts the stl compatible range into ascending order.
418  /// The counter sort algorithm can sort the items which mapped to an
419  /// integer by the adaptable unary function \c functor and the order
420  /// will be ascending by these mapped values. As function specialization
421  /// there is possible to use a normal function as the functor object
422  /// or if the functor is not given it will use an identity function instead.
423  ///
424  /// This implemented counter sort use a radix forward sort on the bytes of
425  /// the integer. The algorithm can sort the items on a given byte.
426  /// First time it counts how many times occurs a byte value in the container.
427  /// By the occurence number it is possible to copy the container
428  /// in the right order in \c O(n) time. The algorithm sorts the container
429  /// by each bytes in forward direction which sorts the container by the
430  /// whole value. This way, let be \c c the maximal capacity of the integer
431  /// type and \c n the number of the items in
432  /// the container, the time complexity of the algorithm \f$ O(\log(c)n) \f$
433  /// and the additional space complexity is \f$ O(n) \f$.
434  ///
435  /// This sorting algorithm is stable so the order of two equal element
436  /// stay in the same order.
437  ///
438  /// \param first The begin of the given range.
439  /// \param last The end of the given range.
440  /// \param functor An adaptible unary function or a normal function which
441  /// maps the items to any integer type which can be wheter signed or
442  /// unsigned.
443  template <typename Iterator, typename Functor>
444  void counterSort(Iterator first, Iterator last, Functor functor) {
445    using namespace _radix_sort_bits;
446    typedef typename Functor::result_type Value;
447    CounterSortSelector<Value>::sort(first, last, functor);
448  }
449
450  template <typename Iterator, typename Value, typename Key>
451  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
452    using namespace _radix_sort_bits;
453    CounterSortSelector<Value>::sort(first, last, functor);
454  }
455
456  template <typename Iterator, typename Value, typename Key>
457  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
458    using namespace _radix_sort_bits;
459    CounterSortSelector<Value>::sort(first, last, functor);
460  }
461
462  template <typename Iterator, typename Value, typename Key>
463  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
464    using namespace _radix_sort_bits;
465    CounterSortSelector<Value>::sort(first, last, functor);
466  }
467
468  template <typename Iterator, typename Value, typename Key>
469  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
470    using namespace _radix_sort_bits;
471    CounterSortSelector<Value>::sort(first, last, functor);
472  }
473
474  template <typename Iterator>
475  void counterSort(Iterator first, Iterator last) {
476    using namespace _radix_sort_bits;
477    typedef typename std::iterator_traits<Iterator>::value_type Value;
478    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
479  }
480
481}
482
483
484
485#endif
Note: See TracBrowser for help on using the repository browser.