COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_sort.h @ 2039:dacc4ce9474d

Last change on this file since 2039:dacc4ce9474d was 2033:7bf1f64962c2, checked in by Balazs Dezso, 18 years ago

Small corrections

File size: 14.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 auxdat
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      if ((mask | functor(*it)) != ~0) {
143        ++max_digit;
144        mask <<= 1;
145        mask |= 1;
146      }
147    }
148    radixIntroSort(first, cut, functor, 1 << max_digit);
149
150    mask = ~0; max_digit = 0;
151    for (it = cut; it != last; ++it) {
152      if (mask & functor(*it)) {
153        ++max_digit;
154        mask <<= 1;
155      }
156    }
157    radixIntroSort(cut, last, functor, 1 << max_digit);
158  }
159
160  template <typename Value, typename Iterator, typename Functor>
161  void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
162
163    Value mask = ~0;
164    int max_digit = 0;
165
166    Iterator it;
167    for (it = first; it != last; ++it) {
168      if (mask & functor(*it)) {
169        ++max_digit;
170        mask <<= 1;
171      }
172    }
173    radixIntroSort(first, last, functor, 1 << max_digit);
174  }
175
176  namespace _radix_sort_bits {
177
178    template <typename Value,
179              bool sign = std::numeric_limits<Value>::is_signed >
180    struct RadixSortSelector {
181      template <typename Iterator, typename Functor>
182      static void sort(Iterator first, Iterator last, Functor functor) {
183        radixSignedSort<Value>(first, last, functor);
184      }
185    };
186
187    template <typename Value>
188    struct RadixSortSelector<Value, false> {
189      template <typename Iterator, typename Functor>
190      static void sort(Iterator first, Iterator last, Functor functor) {
191        radixUnsignedSort<Value>(first, last, functor);
192      }
193    };
194
195  }
196
197  /// \ingroup auxdat
198  ///
199  /// \brief Sorts the stl compatible range into ascending order.
200  ///
201  /// The \c radixSort sorts the stl compatible range into ascending order.
202  /// The radix sort algorithm can sort the items which mapped to an
203  /// integer by the adaptable unary function \c functor and the order
204  /// will be ascending by these mapped values. As function specialization
205  /// there is possible to use a normal function as the functor object
206  /// or if the functor is not given it will use an identity function instead.
207  ///
208  /// This implemented radix sort is a special quick sort which pivot value
209  /// is choosen to partite the items on the next bit. This way, let be
210  /// \c c the maximal capacity and \c n the number of the items in
211  /// the container, the time complexity of the algorithm \c O(log(c)*n)
212  /// and the additional space complexity is \c O(log(c)).
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 int)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 int)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 auxdat
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 \c O(log(c)*n)
433  /// and the additional space complexity is \c O(n).
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.