COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_sort.h @ 2042:bdc953f2a449

Last change on this file since 2042:bdc953f2a449 was 2042:bdc953f2a449, checked in by Balazs Dezso, 14 years ago

New Algorithm group for matchings

LaTeX formulas
Bug fix => /\f$ will cause parsing error in doxygen

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
212  /// \f$ O(\log(c)n) \f$ and the additional space complexity is
213  /// \f$ O(\log(c)) \f$.
214  ///
215  /// \param first The begin of the given range.
216  /// \param last The end of the given range.
217  /// \param functor An adaptible unary function or a normal function which
218  /// maps the items to any integer type which can be wheter signed or
219  /// unsigned.
220  template <typename Iterator, typename Functor>
221  void radixSort(Iterator first, Iterator last, Functor functor) {
222    using namespace _radix_sort_bits;
223    typedef typename Functor::result_type Value;
224    RadixSortSelector<Value>::sort(first, last, functor);
225  }
226
227  template <typename Iterator, typename Value, typename Key>
228  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
229    using namespace _radix_sort_bits;
230    RadixSortSelector<Value>::sort(first, last, functor);
231  }
232
233  template <typename Iterator, typename Value, typename Key>
234  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
235    using namespace _radix_sort_bits;
236    RadixSortSelector<Value>::sort(first, last, functor);
237  }
238
239  template <typename Iterator, typename Value, typename Key>
240  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
241    using namespace _radix_sort_bits;
242    RadixSortSelector<Value>::sort(first, last, functor);
243  }
244
245  template <typename Iterator, typename Value, typename Key>
246  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
247    using namespace _radix_sort_bits;
248    RadixSortSelector<Value>::sort(first, last, functor);
249  }
250
251  template <typename Iterator>
252  void radixSort(Iterator first, Iterator last) {
253    using namespace _radix_sort_bits;
254    typedef typename std::iterator_traits<Iterator>::value_type Value;
255    RadixSortSelector<Value>::sort(first, last, Identity<Value>());
256  }
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 int)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 int)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  namespace _radix_sort_bits {
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 auxdat
415  ///
416  /// \brief Sorts stable the stl compatible range into ascending order.
417  ///
418  /// The \c counterSort sorts the stl compatible range into ascending order.
419  /// The counter sort algorithm can sort the items which mapped to an
420  /// integer by the adaptable unary function \c functor and the order
421  /// will be ascending by these mapped values. As function specialization
422  /// there is possible to use a normal function as the functor object
423  /// or if the functor is not given it will use an identity function instead.
424  ///
425  /// This implemented counter sort use a radix forward sort on the bytes of
426  /// the integer. The algorithm can sort the items on a given byte.
427  /// First time it counts how many times occurs a byte value in the container.
428  /// By the occurence number it is possible to copy the container
429  /// in the right order in \c O(n) time. The algorithm sorts the container
430  /// by each bytes in forward direction which sorts the container by the
431  /// whole value. This way, let be \c c the maximal capacity of the integer
432  /// type and \c n the number of the items in
433  /// the container, the time complexity of the algorithm \f$ O(\log(c)n) \f$
434  /// and the additional space complexity is \f$ O(n) \f$.
435  ///
436  /// This sorting algorithm is stable so the order of two equal element
437  /// stay in the same order.
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 which
442  /// maps the items to any integer type which can be wheter signed or
443  /// 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
485
486#endif
Note: See TracBrowser for help on using the repository browser.