radix_sort.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
00016  *
00017  */
00018 
00019 #ifndef RADIX_SORT_H
00020 #define RADIX_SORT_H
00021 
00026 
00027 #include <vector>
00028 #include <limits>
00029 #include <iterator>
00030 #include <algorithm>
00031 
00032 #include <lemon/error.h>
00033 
00034 namespace lemon {
00035 
00036   namespace _radix_sort_bits {
00037 
00038     template <typename Value>
00039     struct Identity {
00040       const Value& operator()(const Value& val) {
00041         return val;
00042       }
00043     };
00044 
00045   }
00046 
00047   template <typename Value, typename Iterator, typename Functor>
00048   Iterator radixSortPartition(Iterator first, Iterator last, 
00049                               Functor functor, Value mask) {
00050     while (first != last && !(functor(*first) & mask)) {
00051       ++first;
00052     }
00053     if (first == last) {
00054       return first;
00055     }
00056     --last;
00057     while (first != last && (functor(*last) & mask)) {
00058       --last;
00059     }
00060     if (first == last) {
00061       return first;
00062     }
00063     std::iter_swap(first, last);
00064     ++first;
00065     if (!(first < last)) {
00066       return first;
00067     }
00068     while (true) {
00069       while (!(functor(*first) & mask)) {
00070         ++first;
00071       }
00072       --last;
00073       while (functor(*last) & mask) {
00074         --last;
00075       }
00076       if (!(first < last)) {
00077         return first;
00078       }
00079       std::iter_swap(first, last);
00080       ++first;
00081     }
00082   }
00083 
00084   template <typename Iterator, typename Functor>
00085   Iterator radixSortSignPartition(Iterator first, Iterator last, 
00086                                   Functor functor) {
00087     while (first != last && functor(*first) < 0) {
00088       ++first;
00089     }
00090     if (first == last) {
00091       return first;
00092     }
00093     --last;
00094     while (first != last && functor(*last) >= 0) {
00095       --last;
00096     }
00097     if (first == last) {
00098       return first;
00099     }
00100     std::iter_swap(first, last);
00101     ++first;
00102     if (!(first < last)) {
00103       return first;
00104     }
00105     while (true) {
00106       while (functor(*first) < 0) {
00107         ++first;
00108       }
00109       --last;
00110       while (functor(*last) >= 0) {
00111         --last;
00112       }
00113       if (!(first < last)) {
00114         return first;
00115       }
00116       std::iter_swap(first, last);
00117       ++first;
00118     }
00119   }
00120 
00121   template <typename Value, typename Iterator, typename Functor>
00122   void radixIntroSort(Iterator first, Iterator last, 
00123                       Functor functor, Value mask) {
00124     while (mask != 0 && last - first > 1) {
00125       Iterator cut = radixSortPartition(first, last, functor, mask);
00126       mask >>= 1;
00127       radixIntroSort(first, cut, functor, mask);
00128       first = cut;
00129     }
00130   }
00131 
00132   template <typename Value, typename Iterator, typename Functor>
00133   void radixSignedSort(Iterator first, Iterator last, Functor functor) {
00134     Iterator cut = radixSortSignPartition(first, last, functor);
00135 
00136     Value mask;
00137     int max_digit;
00138     Iterator it;
00139 
00140     mask = 0; max_digit = 0;
00141     for (it = first; it != cut; ++it) {
00142       if ((mask | functor(*it)) != ~0) {
00143         ++max_digit;
00144         mask <<= 1; 
00145         mask |= 1;
00146       }
00147     }
00148     radixIntroSort(first, cut, functor, 1 << max_digit);
00149 
00150     mask = ~0; max_digit = 0;
00151     for (it = cut; it != last; ++it) {
00152       if (mask & functor(*it)) {
00153         ++max_digit;
00154         mask <<= 1;
00155       }
00156     }
00157     radixIntroSort(cut, last, functor, 1 << max_digit);
00158   }
00159 
00160   template <typename Value, typename Iterator, typename Functor>
00161   void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
00162 
00163     Value mask = ~0;
00164     int max_digit = 0;
00165 
00166     Iterator it;
00167     for (it = first; it != last; ++it) {
00168       if (mask & functor(*it)) {
00169         ++max_digit;
00170         mask <<= 1;
00171       }
00172     }
00173     radixIntroSort(first, last, functor, 1 << max_digit);
00174   }
00175 
00176   namespace _radix_sort_bits {
00177 
00178     template <typename Value, 
00179               bool sign = std::numeric_limits<Value>::is_signed >
00180     struct RadixSortSelector {
00181       template <typename Iterator, typename Functor>
00182       static void sort(Iterator first, Iterator last, Functor functor) {
00183         radixSignedSort<Value>(first, last, functor);
00184       }
00185     };
00186 
00187     template <typename Value>
00188     struct RadixSortSelector<Value, false> {
00189       template <typename Iterator, typename Functor>
00190       static void sort(Iterator first, Iterator last, Functor functor) {
00191         radixUnsignedSort<Value>(first, last, functor);
00192       }
00193     };
00194 
00195   }
00196 
00219   template <typename Iterator, typename Functor>
00220   void radixSort(Iterator first, Iterator last, Functor functor) {
00221     using namespace _radix_sort_bits;
00222     typedef typename Functor::result_type Value;
00223     RadixSortSelector<Value>::sort(first, last, functor);
00224   }
00225 
00226   template <typename Iterator, typename Value, typename Key>
00227   void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
00228     using namespace _radix_sort_bits;
00229     RadixSortSelector<Value>::sort(first, last, functor);
00230   }
00231 
00232   template <typename Iterator, typename Value, typename Key>
00233   void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
00234     using namespace _radix_sort_bits;
00235     RadixSortSelector<Value>::sort(first, last, functor);
00236   }
00237 
00238   template <typename Iterator, typename Value, typename Key>
00239   void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
00240     using namespace _radix_sort_bits;
00241     RadixSortSelector<Value>::sort(first, last, functor);
00242   }
00243 
00244   template <typename Iterator, typename Value, typename Key>
00245   void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
00246     using namespace _radix_sort_bits;
00247     RadixSortSelector<Value>::sort(first, last, functor);
00248   }
00249 
00250   template <typename Iterator>
00251   void radixSort(Iterator first, Iterator last) {
00252     using namespace _radix_sort_bits;
00253     typedef typename std::iterator_traits<Iterator>::value_type Value;
00254     RadixSortSelector<Value>::sort(first, last, Identity<Value>());
00255   }
00256 
00257   template <typename Value>
00258   unsigned char valueByte(Value value, int byte) {
00259     return value >> (std::numeric_limits<unsigned char>::digits * byte);
00260   }
00261 
00262   template <typename Functor, typename Key>
00263   void counterIntroSort(Key *first, Key *last, Key *target, 
00264                        int byte, Functor functor) {
00265     const int size = 
00266       (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
00267     int counter[size];
00268     for (int i = 0; i < size; ++i) {
00269       counter[i] = 0;
00270     }
00271     Key *it = first;
00272     while (first != last) {
00273       ++counter[valueByte(functor(*first), byte)]; 
00274       ++first;
00275     }
00276     int prev, num = 0;
00277     for (int i = 0; i < size; ++i) {
00278       prev = num;
00279       num += counter[i];
00280       counter[i] = prev;
00281     }
00282     while (it != last) {
00283       target[counter[valueByte(functor(*it), byte)]++] = *it;
00284       ++it;
00285     }
00286   }
00287 
00288   template <typename Functor, typename Key>
00289   void signedCounterIntroSort(Key *first, Key *last, Key *target, 
00290                              int byte, Functor functor) {
00291     const int size = 
00292       (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
00293     int counter[size];
00294     for (int i = 0; i < size; ++i) {
00295       counter[i] = 0;
00296     }
00297     Key *it = first;
00298     while (first != last) {
00299       counter[valueByte(functor(*first), byte)]++;
00300       ++first;
00301     }
00302     int prev, num = 0;
00303     for (int i = size / 2; i < size; ++i) {
00304       prev = num;
00305       num += counter[i];
00306       counter[i] = prev;
00307     }
00308     for (int i = 0; i < size / 2; ++i) {
00309       prev = num;
00310       num += counter[i];
00311       counter[i] = prev;
00312     }
00313     while (it != last) {
00314       target[counter[valueByte(functor(*it), byte)]++] = *it;
00315       ++it;
00316     }
00317   }
00318 
00319   
00320   template <typename Value, typename Iterator, typename Functor>
00321   void counterSignedSort(Iterator first, Iterator last, Functor functor) {
00322     if (first == last) return;
00323     typedef typename std::iterator_traits<Iterator>::value_type Key;
00324     typedef std::allocator<Key> Allocator;
00325     Allocator allocator;
00326 
00327     int length = std::distance(first, last);
00328     Key* buffer;
00329     buffer = allocator.allocate(2 * length);
00330     try {
00331       bool dir = true;
00332       std::copy(first, last, buffer);
00333       for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
00334         if (dir) {
00335           counterIntroSort(buffer, buffer + length, buffer + length, 
00336                            i, functor);
00337         } else {
00338           counterIntroSort(buffer + length, buffer + 2 * length, buffer, 
00339                            i, functor);
00340         }
00341         dir = !dir;
00342       }
00343       if (dir) {
00344         signedCounterIntroSort(buffer, buffer + length, buffer + length, 
00345                                sizeof(Value) - 1, functor);
00346         std::copy(buffer + length, buffer + 2 * length, first);
00347       } else {
00348         signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer, 
00349                                sizeof(Value) - 1, functor);
00350         std::copy(buffer, buffer + length, first);
00351       }
00352     } catch (...) {
00353       allocator.deallocate(buffer, 2 * length);
00354       throw;
00355     }
00356     allocator.deallocate(buffer, 2 * length);
00357   }
00358 
00359   template <typename Value, typename Iterator, typename Functor>
00360   void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
00361     if (first == last) return;
00362     typedef typename std::iterator_traits<Iterator>::value_type Key;
00363     typedef std::allocator<Key> Allocator;
00364     Allocator allocator;
00365 
00366     int length = std::distance(first, last);
00367     Key *buffer;
00368     buffer = allocator.allocate(2 * length);
00369     try {
00370       bool dir = true;
00371       std::copy(first, last, buffer);
00372       for (int i = 0; i < (int)sizeof(Value); ++i) {
00373         if (dir) {
00374           counterIntroSort(buffer, buffer + length, buffer + length, i, functor);
00375         } else {
00376           counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
00377         }
00378         dir = !dir;
00379       }
00380       if (dir) {
00381         std::copy(buffer, buffer + length, first);
00382       } else {
00383         std::copy(buffer + length, buffer + 2 * length, first);
00384       }
00385     } catch (...) {
00386       allocator.deallocate(buffer, 2 * length);
00387       throw;
00388     }
00389     allocator.deallocate(buffer, 2 * length);
00390   }
00391 
00392   namespace _radix_sort_bits {
00393 
00394     template <typename Value, 
00395               bool sign = std::numeric_limits<Value>::is_signed >
00396     struct CounterSortSelector {
00397       template <typename Iterator, typename Functor>
00398       static void sort(Iterator first, Iterator last, Functor functor) {
00399         counterSignedSort<Value>(first, last, functor);
00400       }
00401     };
00402 
00403     template <typename Value>
00404     struct CounterSortSelector<Value, false> {
00405       template <typename Iterator, typename Functor>
00406       static void sort(Iterator first, Iterator last, Functor functor) {
00407         counterUnsignedSort<Value>(first, last, functor);
00408       }
00409     };
00410 
00411   }
00412 
00443   template <typename Iterator, typename Functor>
00444   void counterSort(Iterator first, Iterator last, Functor functor) {
00445     using namespace _radix_sort_bits;
00446     typedef typename Functor::result_type Value;
00447     CounterSortSelector<Value>::sort(first, last, functor);
00448   }
00449 
00450   template <typename Iterator, typename Value, typename Key>
00451   void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
00452     using namespace _radix_sort_bits;
00453     CounterSortSelector<Value>::sort(first, last, functor);
00454   }
00455 
00456   template <typename Iterator, typename Value, typename Key>
00457   void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
00458     using namespace _radix_sort_bits;
00459     CounterSortSelector<Value>::sort(first, last, functor);
00460   }
00461 
00462   template <typename Iterator, typename Value, typename Key>
00463   void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
00464     using namespace _radix_sort_bits;
00465     CounterSortSelector<Value>::sort(first, last, functor);
00466   }
00467 
00468   template <typename Iterator, typename Value, typename Key>
00469   void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
00470     using namespace _radix_sort_bits;
00471     CounterSortSelector<Value>::sort(first, last, functor);
00472   }
00473 
00474   template <typename Iterator>
00475   void counterSort(Iterator first, Iterator last) {
00476     using namespace _radix_sort_bits;
00477     typedef typename std::iterator_traits<Iterator>::value_type Value;
00478     CounterSortSelector<Value>::sort(first, last, Identity<Value>());
00479   }
00480 
00481 }
00482 
00483 
00484 
00485 #endif

Generated on Fri Feb 3 18:39:41 2006 for LEMON by  doxygen 1.4.6