lemon/radix_sort.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 443 de16f1f2d228
child 559 c5fd2d996909
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
     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