COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/radix_sort.h @ 1933:a876a3d6a4c7

Last change on this file since 1933:a876a3d6a4c7 was 1904:a64e4735bda6, checked in by Balazs Dezso, 14 years ago

Bug fix for empty intervall sorting

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    if (first == last) return;
321    typedef typename std::iterator_traits<Iterator>::value_type Key;
322    typedef std::allocator<Key> Allocator;
323    Allocator allocator;
324
325    int length = std::distance(first, last);
326    Key* buffer;
327    buffer = allocator.allocate(2 * length);
328    try {
329      bool dir = true;
330      std::copy(first, last, buffer);
331      for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
332        if (dir) {
333          counterIntroSort(buffer, buffer + length, buffer + length,
334                           i, functor);
335        } else {
336          counterIntroSort(buffer + length, buffer + 2 * length, buffer,
337                           i, functor);
338        }
339        dir = !dir;
340      }
341      if (dir) {
342        signedCounterIntroSort(buffer, buffer + length, buffer + length,
343                               sizeof(Value) - 1, functor);
344        std::copy(buffer + length, buffer + 2 * length, first);
345      } else {
346        signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
347                               sizeof(Value) - 1, functor);
348        std::copy(buffer, buffer + length, first);
349      }
350    } catch (...) {
351      allocator.deallocate(buffer, 2 * length);
352      throw;
353    }
354    allocator.deallocate(buffer, 2 * length);
355  }
356
357  template <typename Value, typename Iterator, typename Functor>
358  void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
359    if (first == last) return;
360    typedef typename std::iterator_traits<Iterator>::value_type Key;
361    typedef std::allocator<Key> Allocator;
362    Allocator allocator;
363
364    int length = std::distance(first, last);
365    Key *buffer;
366    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, buffer + length, i, functor);
373        } else {
374          counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
375        }
376        dir = !dir;
377      }
378      if (dir) {
379        std::copy(buffer, buffer + length, first);
380      } else {
381        std::copy(buffer + length, buffer + 2 * length, first);
382      }
383    } catch (...) {
384      allocator.deallocate(buffer, 2 * length);
385      throw;
386    }
387    allocator.deallocate(buffer, 2 * length);
388  }
389
390  namespace _radix_sort_bits {
391
392    template <typename Value,
393              bool sign = std::numeric_limits<Value>::is_signed >
394    struct CounterSortSelector {
395      template <typename Iterator, typename Functor>
396      static void sort(Iterator first, Iterator last, Functor functor) {
397        counterSignedSort<Value>(first, last, functor);
398      }
399    };
400
401    template <typename Value>
402    struct CounterSortSelector<Value, false> {
403      template <typename Iterator, typename Functor>
404      static void sort(Iterator first, Iterator last, Functor functor) {
405        counterUnsignedSort<Value>(first, last, functor);
406      }
407    };
408
409  }
410
411  /// \ingroup auxdat
412  ///
413  /// \brief Sorts stable the stl compatible range into ascending order.
414  ///
415  /// The \c counterSort sorts the stl compatible range into ascending order.
416  /// The counter sort algorithm can sort the items which mapped to an
417  /// integer by the adaptable unary function \c functor and the order
418  /// will be ascending by these mapped values. As function specialization
419  /// there is possible to use a normal function as the functor object
420  /// or if the functor is not given it will use an identity function instead.
421  ///
422  /// This implemented counter sort use a radix forward sort on the bytes of
423  /// the integer. The algorithm can sort the items on a given byte.
424  /// First time it counts how many times occurs a byte value in the container.
425  /// By the occurence number it is possible to copy the container
426  /// in the right order in \c O(n) time. The algorithm sorts the container
427  /// by each bytes in forward direction which sorts the container by the
428  /// whole value. This way, let be \c c the maximal capacity of the integer
429  /// type and \c n the number of the items in
430  /// the container, the time complexity of the algorithm \c O(log(c)*n)
431  /// and the additional space complexity is \c O(n).
432  ///
433  /// This sorting algorithm is stable so the order of two equal element
434  /// stay in the same order.
435  ///
436  /// \param first The begin of the given range.
437  /// \param last The end of the given range.
438  /// \param functor An adaptible unary function or a normal function which
439  /// maps the items to any integer type which can be wheter signed or
440  /// unsigned.
441  template <typename Iterator, typename Functor>
442  void counterSort(Iterator first, Iterator last, Functor functor) {
443    using namespace _radix_sort_bits;
444    typedef typename Functor::result_type Value;
445    CounterSortSelector<Value>::sort(first, last, functor);
446  }
447
448  template <typename Iterator, typename Value, typename Key>
449  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
450    using namespace _radix_sort_bits;
451    CounterSortSelector<Value>::sort(first, last, functor);
452  }
453
454  template <typename Iterator, typename Value, typename Key>
455  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
456    using namespace _radix_sort_bits;
457    CounterSortSelector<Value>::sort(first, last, functor);
458  }
459
460  template <typename Iterator, typename Value, typename Key>
461  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
462    using namespace _radix_sort_bits;
463    CounterSortSelector<Value>::sort(first, last, functor);
464  }
465
466  template <typename Iterator, typename Value, typename Key>
467  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
468    using namespace _radix_sort_bits;
469    CounterSortSelector<Value>::sort(first, last, functor);
470  }
471
472  template <typename Iterator>
473  void counterSort(Iterator first, Iterator last) {
474    using namespace _radix_sort_bits;
475    typedef typename std::iterator_traits<Iterator>::value_type Value;
476    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
477  }
478
479}
480
481
482
483#endif
Note: See TracBrowser for help on using the repository browser.