lemon/radix_sort.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 24 Feb 2009 06:52:17 +0000
changeset 536 97674155c135
parent 443 de16f1f2d228
child 559 c5fd2d996909
permissions -rw-r--r--
Merge
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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 /// Linear time sorting algorithms
    27 
    28 #include <vector>
    29 #include <limits>
    30 #include <iterator>
    31 #include <algorithm>
    32 
    33 namespace lemon {
    34 
    35   namespace _radix_sort_bits {
    36 
    37     template <typename Value>
    38     struct Identity {
    39       const Value& operator()(const Value& val) {
    40         return val;
    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 
   133       Iterator cut = radixSortSignPartition(first, last, functor);
   134 
   135       Value mask;
   136       int max_digit;
   137       Iterator it;
   138 
   139       mask = ~0; max_digit = 0;
   140       for (it = first; it != cut; ++it) {
   141         while ((mask & functor(*it)) != mask) {
   142           ++max_digit;
   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         while ((mask | functor(*it)) != mask) {
   151           ++max_digit;
   152           mask <<= 1; 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         while ((mask | functor(*it)) != mask) {
   167           ++max_digit;
   168           mask <<= 1; mask |= 1;
   169         }
   170       }
   171       radixIntroSort(first, last, functor, 1 << max_digit);
   172     }
   173 
   174 
   175     template <typename Value,
   176               bool sign = std::numeric_limits<Value>::is_signed >
   177     struct RadixSortSelector {
   178       template <typename Iterator, typename Functor>
   179       static void sort(Iterator first, Iterator last, Functor functor) {
   180         radixSignedSort<Value>(first, last, functor);
   181       }
   182     };
   183 
   184     template <typename Value>
   185     struct RadixSortSelector<Value, false> {
   186       template <typename Iterator, typename Functor>
   187       static void sort(Iterator first, Iterator last, Functor functor) {
   188         radixUnsignedSort<Value>(first, last, functor);
   189       }
   190     };
   191 
   192   }
   193 
   194   /// \ingroup auxalg
   195   ///
   196   /// \brief Sorts the STL compatible range into ascending order.
   197   ///
   198   /// The \c radixSort sorts an STL compatible range into ascending
   199   /// order.  The radix sort algorithm can sort items which are mapped
   200   /// to integers with an adaptable unary function \c functor and the
   201   /// order will be ascending according to these mapped values.
   202   ///
   203   /// It is also possible to use a normal function instead
   204   /// of the functor object. If the functor is not given it will use
   205   /// the identity function instead.
   206   ///
   207   /// This is a special quick sort algorithm where the pivot
   208   /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.
   209   /// Therefore, the time complexity of the
   210   /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
   211   /// additional space, where \c c is the maximal value and \c n is the
   212   /// number of the items in the container.
   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
   217   /// which maps the items to any integer type which can be either
   218   /// signed or unsigned.
   219   ///
   220   /// \sa stableRadixSort()
   221   template <typename Iterator, typename Functor>
   222   void radixSort(Iterator first, Iterator last, Functor functor) {
   223     using namespace _radix_sort_bits;
   224     typedef typename Functor::result_type Value;
   225     RadixSortSelector<Value>::sort(first, last, functor);
   226   }
   227 
   228   template <typename Iterator, typename Value, typename Key>
   229   void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
   230     using namespace _radix_sort_bits;
   231     RadixSortSelector<Value>::sort(first, last, functor);
   232   }
   233 
   234   template <typename Iterator, typename Value, typename Key>
   235   void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
   236     using namespace _radix_sort_bits;
   237     RadixSortSelector<Value>::sort(first, last, functor);
   238   }
   239 
   240   template <typename Iterator, typename Value, typename Key>
   241   void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
   242     using namespace _radix_sort_bits;
   243     RadixSortSelector<Value>::sort(first, last, functor);
   244   }
   245 
   246   template <typename Iterator, typename Value, typename Key>
   247   void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
   248     using namespace _radix_sort_bits;
   249     RadixSortSelector<Value>::sort(first, last, functor);
   250   }
   251 
   252   template <typename Iterator>
   253   void radixSort(Iterator first, Iterator last) {
   254     using namespace _radix_sort_bits;
   255     typedef typename std::iterator_traits<Iterator>::value_type Value;
   256     RadixSortSelector<Value>::sort(first, last, Identity<Value>());
   257   }
   258 
   259   namespace _radix_sort_bits {
   260 
   261     template <typename Value>
   262     unsigned char valueByte(Value value, int byte) {
   263       return value >> (std::numeric_limits<unsigned char>::digits * byte);
   264     }
   265 
   266     template <typename Functor, typename Key>
   267     void stableRadixIntroSort(Key *first, Key *last, Key *target,
   268                               int byte, Functor functor) {
   269       const int size =
   270         unsigned(std::numeric_limits<unsigned char>::max()) + 1;
   271       std::vector<int> counter(size);
   272       for (int i = 0; i < size; ++i) {
   273         counter[i] = 0;
   274       }
   275       Key *it = first;
   276       while (first != last) {
   277         ++counter[valueByte(functor(*first), byte)];
   278         ++first;
   279       }
   280       int prev, num = 0;
   281       for (int i = 0; i < size; ++i) {
   282         prev = num;
   283         num += counter[i];
   284         counter[i] = prev;
   285       }
   286       while (it != last) {
   287         target[counter[valueByte(functor(*it), byte)]++] = *it;
   288         ++it;
   289       }
   290     }
   291 
   292     template <typename Functor, typename Key>
   293     void signedStableRadixIntroSort(Key *first, Key *last, Key *target,
   294                                     int byte, Functor functor) {
   295       const int size =
   296         unsigned(std::numeric_limits<unsigned char>::max()) + 1;
   297       std::vector<int> counter(size);
   298       for (int i = 0; i < size; ++i) {
   299         counter[i] = 0;
   300       }
   301       Key *it = first;
   302       while (first != last) {
   303         counter[valueByte(functor(*first), byte)]++;
   304         ++first;
   305       }
   306       int prev, num = 0;
   307       for (int i = size / 2; i < size; ++i) {
   308         prev = num;
   309         num += counter[i];
   310         counter[i] = prev;
   311       }
   312       for (int i = 0; i < size / 2; ++i) {
   313         prev = num;
   314         num += counter[i];
   315         counter[i] = prev;
   316       }
   317       while (it != last) {
   318         target[counter[valueByte(functor(*it), byte)]++] = *it;
   319         ++it;
   320       }
   321     }
   322 
   323 
   324     template <typename Value, typename Iterator, typename Functor>
   325     void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) {
   326       if (first == last) return;
   327       typedef typename std::iterator_traits<Iterator>::value_type Key;
   328       typedef std::allocator<Key> Allocator;
   329       Allocator allocator;
   330 
   331       int length = std::distance(first, last);
   332       Key* buffer = allocator.allocate(2 * length);
   333       try {
   334         bool dir = true;
   335         std::copy(first, last, buffer);
   336         for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
   337           if (dir) {
   338             stableRadixIntroSort(buffer, buffer + length, buffer + length,
   339                                  i, functor);
   340           } else {
   341             stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
   342                                  i, functor);
   343           }
   344           dir = !dir;
   345         }
   346         if (dir) {
   347           signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
   348                                      sizeof(Value) - 1, functor);
   349           std::copy(buffer + length, buffer + 2 * length, first);
   350         }        else {
   351           signedStableRadixIntroSort(buffer + length, buffer + 2 * length,
   352                                      buffer, sizeof(Value) - 1, functor);
   353           std::copy(buffer, buffer + length, first);
   354         }
   355       } catch (...) {
   356         allocator.deallocate(buffer, 2 * length);
   357         throw;
   358       }
   359       allocator.deallocate(buffer, 2 * length);
   360     }
   361 
   362     template <typename Value, typename Iterator, typename Functor>
   363     void stableRadixUnsignedSort(Iterator first, Iterator last,
   364                                  Functor functor) {
   365       if (first == last) return;
   366       typedef typename std::iterator_traits<Iterator>::value_type Key;
   367       typedef std::allocator<Key> Allocator;
   368       Allocator allocator;
   369 
   370       int length = std::distance(first, last);
   371       Key *buffer = allocator.allocate(2 * length);
   372       try {
   373         bool dir = true;
   374         std::copy(first, last, buffer);
   375         for (int i = 0; i < int(sizeof(Value)); ++i) {
   376           if (dir) {
   377             stableRadixIntroSort(buffer, buffer + length,
   378                                  buffer + length, i, functor);
   379           } else {
   380             stableRadixIntroSort(buffer + length, buffer + 2 * length,
   381                                  buffer, i, functor);
   382           }
   383           dir = !dir;
   384         }
   385         if (dir) {
   386           std::copy(buffer, buffer + length, first);
   387         }        else {
   388           std::copy(buffer + length, buffer + 2 * length, first);
   389         }
   390       } catch (...) {
   391         allocator.deallocate(buffer, 2 * length);
   392         throw;
   393       }
   394       allocator.deallocate(buffer, 2 * length);
   395     }
   396 
   397 
   398 
   399     template <typename Value,
   400               bool sign = std::numeric_limits<Value>::is_signed >
   401     struct StableRadixSortSelector {
   402       template <typename Iterator, typename Functor>
   403       static void sort(Iterator first, Iterator last, Functor functor) {
   404         stableRadixSignedSort<Value>(first, last, functor);
   405       }
   406     };
   407 
   408     template <typename Value>
   409     struct StableRadixSortSelector<Value, false> {
   410       template <typename Iterator, typename Functor>
   411       static void sort(Iterator first, Iterator last, Functor functor) {
   412         stableRadixUnsignedSort<Value>(first, last, functor);
   413       }
   414     };
   415 
   416   }
   417 
   418   /// \ingroup auxalg
   419   ///
   420   /// \brief Sorts the STL compatible range into ascending order in a stable
   421   /// way.
   422   ///
   423   /// This function sorts an STL compatible range into ascending
   424   /// order according to an integer mapping in the same as radixSort() does.
   425   ///
   426   /// This sorting algorithm is stable, i.e. the order of two equal
   427   /// elements remains the same after the sorting.
   428   ///
   429   /// This sort algorithm  use a radix forward sort on the
   430   /// bytes of the integer number. The algorithm sorts the items
   431   /// byte-by-byte. First, it counts how many times a byte value occurs
   432   /// in the container, then it copies the corresponding items to
   433   /// another container in asceding order in \c O(n) time.
   434   ///
   435   /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
   436   /// it uses \f$ O(n) \f$, additional space, where \c c is the
   437   /// maximal value and \c n is the number of the items in the
   438   /// container.
   439   ///
   440 
   441   /// \param first The begin of the given range.
   442   /// \param last The end of the given range.
   443   /// \param functor An adaptible unary function or a normal function
   444   /// which maps the items to any integer type which can be either
   445   /// signed or unsigned.
   446   /// \sa radixSort()
   447   template <typename Iterator, typename Functor>
   448   void stableRadixSort(Iterator first, Iterator last, Functor functor) {
   449     using namespace _radix_sort_bits;
   450     typedef typename Functor::result_type Value;
   451     StableRadixSortSelector<Value>::sort(first, last, functor);
   452   }
   453 
   454   template <typename Iterator, typename Value, typename Key>
   455   void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
   456     using namespace _radix_sort_bits;
   457     StableRadixSortSelector<Value>::sort(first, last, functor);
   458   }
   459 
   460   template <typename Iterator, typename Value, typename Key>
   461   void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
   462     using namespace _radix_sort_bits;
   463     StableRadixSortSelector<Value>::sort(first, last, functor);
   464   }
   465 
   466   template <typename Iterator, typename Value, typename Key>
   467   void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
   468     using namespace _radix_sort_bits;
   469     StableRadixSortSelector<Value>::sort(first, last, functor);
   470   }
   471 
   472   template <typename Iterator, typename Value, typename Key>
   473   void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
   474     using namespace _radix_sort_bits;
   475     StableRadixSortSelector<Value>::sort(first, last, functor);
   476   }
   477 
   478   template <typename Iterator>
   479   void stableRadixSort(Iterator first, Iterator last) {
   480     using namespace _radix_sort_bits;
   481     typedef typename std::iterator_traits<Iterator>::value_type Value;
   482     StableRadixSortSelector<Value>::sort(first, last, Identity<Value>());
   483   }
   484 
   485 }
   486 
   487 #endif