COIN-OR::LEMON - Graph Library

Changeset 443:de16f1f2d228 in lemon-main


Ignore:
Timestamp:
12/02/08 23:15:43 (16 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Rename counterSort to stableRadixSort

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/radix_sort.h

    r442 r443  
    218218  /// signed or unsigned.
    219219  ///
    220   /// \sa counterSort()
     220  /// \sa stableRadixSort()
    221221  template <typename Iterator, typename Functor>
    222222  void radixSort(Iterator first, Iterator last, Functor functor) {
     
    265265
    266266    template <typename Functor, typename Key>
    267     void counterIntroSort(Key *first, Key *last, Key *target,
    268                           int byte, Functor functor) {
     267    void stableRadixIntroSort(Key *first, Key *last, Key *target,
     268                              int byte, Functor functor) {
    269269      const int size =
    270270        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
     
    291291
    292292    template <typename Functor, typename Key>
    293     void signedCounterIntroSort(Key *first, Key *last, Key *target,
    294                                 int byte, Functor functor) {
     293    void signedStableRadixIntroSort(Key *first, Key *last, Key *target,
     294                                    int byte, Functor functor) {
    295295      const int size =
    296296        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
     
    323323
    324324    template <typename Value, typename Iterator, typename Functor>
    325     void counterSignedSort(Iterator first, Iterator last, Functor functor) {
     325    void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) {
    326326      if (first == last) return;
    327327      typedef typename std::iterator_traits<Iterator>::value_type Key;
     
    336336        for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
    337337          if (dir) {
    338             counterIntroSort(buffer, buffer + length, buffer + length,
    339                              i, functor);
     338            stableRadixIntroSort(buffer, buffer + length, buffer + length,
     339                                 i, functor);
    340340          } else {
    341             counterIntroSort(buffer + length, buffer + 2 * length, buffer,
    342                              i, functor);
     341            stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
     342                                 i, functor);
    343343          }
    344344          dir = !dir;
    345345        }
    346346        if (dir) {
    347           signedCounterIntroSort(buffer, buffer + length, buffer + length,
    348                                  sizeof(Value) - 1, functor);
     347          signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
     348                                     sizeof(Value) - 1, functor);
    349349          std::copy(buffer + length, buffer + 2 * length, first);
    350350        }        else {
    351           signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
    352                                  sizeof(Value) - 1, functor);
     351          signedStableRadixIntroSort(buffer + length, buffer + 2 * length,
     352                                     buffer, sizeof(Value) - 1, functor);
    353353          std::copy(buffer, buffer + length, first);
    354354        }
     
    361361
    362362    template <typename Value, typename Iterator, typename Functor>
    363     void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
     363    void stableRadixUnsignedSort(Iterator first, Iterator last,
     364                                 Functor functor) {
    364365      if (first == last) return;
    365366      typedef typename std::iterator_traits<Iterator>::value_type Key;
     
    374375        for (int i = 0; i < int(sizeof(Value)); ++i) {
    375376          if (dir) {
    376             counterIntroSort(buffer, buffer + length,
    377                              buffer + length, i, functor);
     377            stableRadixIntroSort(buffer, buffer + length,
     378                                 buffer + length, i, functor);
    378379          } else {
    379             counterIntroSort(buffer + length, buffer + 2 * length,
    380                              buffer, i, functor);
     380            stableRadixIntroSort(buffer + length, buffer + 2 * length,
     381                                 buffer, i, functor);
    381382          }
    382383          dir = !dir;
     
    398399    template <typename Value,
    399400              bool sign = std::numeric_limits<Value>::is_signed >
    400     struct CounterSortSelector {
     401    struct StableRadixSortSelector {
    401402      template <typename Iterator, typename Functor>
    402403      static void sort(Iterator first, Iterator last, Functor functor) {
    403         counterSignedSort<Value>(first, last, functor);
     404        stableRadixSignedSort<Value>(first, last, functor);
    404405      }
    405406    };
    406407
    407408    template <typename Value>
    408     struct CounterSortSelector<Value, false> {
     409    struct StableRadixSortSelector<Value, false> {
    409410      template <typename Iterator, typename Functor>
    410411      static void sort(Iterator first, Iterator last, Functor functor) {
    411         counterUnsignedSort<Value>(first, last, functor);
     412        stableRadixUnsignedSort<Value>(first, last, functor);
    412413      }
    413414    };
     
    424425  ///
    425426  /// This sorting algorithm is stable, i.e. the order of two equal
    426   /// element remains the same after the sorting.
     427  /// elements remains the same after the sorting.
    427428  ///
    428429  /// This sort algorithm  use a radix forward sort on the
     
    445446  /// \sa radixSort()
    446447  template <typename Iterator, typename Functor>
    447   void counterSort(Iterator first, Iterator last, Functor functor) {
     448  void stableRadixSort(Iterator first, Iterator last, Functor functor) {
    448449    using namespace _radix_sort_bits;
    449450    typedef typename Functor::result_type Value;
    450     CounterSortSelector<Value>::sort(first, last, functor);
    451   }
    452 
    453   template <typename Iterator, typename Value, typename Key>
    454   void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
    455     using namespace _radix_sort_bits;
    456     CounterSortSelector<Value>::sort(first, last, functor);
    457   }
    458 
    459   template <typename Iterator, typename Value, typename Key>
    460   void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
    461     using namespace _radix_sort_bits;
    462     CounterSortSelector<Value>::sort(first, last, functor);
    463   }
    464 
    465   template <typename Iterator, typename Value, typename Key>
    466   void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
    467     using namespace _radix_sort_bits;
    468     CounterSortSelector<Value>::sort(first, last, functor);
    469   }
    470 
    471   template <typename Iterator, typename Value, typename Key>
    472   void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
    473     using namespace _radix_sort_bits;
    474     CounterSortSelector<Value>::sort(first, last, functor);
     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);
    475476  }
    476477
    477478  template <typename Iterator>
    478   void counterSort(Iterator first, Iterator last) {
     479  void stableRadixSort(Iterator first, Iterator last) {
    479480    using namespace _radix_sort_bits;
    480481    typedef typename std::iterator_traits<Iterator>::value_type Value;
    481     CounterSortSelector<Value>::sort(first, last, Identity<Value>());
     482    StableRadixSortSelector<Value>::sort(first, last, Identity<Value>());
    482483  }
    483484
  • test/radix_sort_test.cc

    r442 r443  
    100100
    101101
    102 void checkCounterSort() {
     102void checkStableRadixSort() {
    103103  {
    104104    std::vector<int> data1;
     
    108108    std::sort(data1.begin(), data1.end());
    109109
    110     counterSort(data2.begin(), data2.end());
     110    stableRadixSort(data2.begin(), data2.end());
    111111    for (int i = 0; i < n; ++i) {
    112112      check(data1[i] == data2[i], "Test failed");
    113113    }
    114114
    115     counterSort(data2.begin(), data2.end(), Negate());
     115    stableRadixSort(data2.begin(), data2.end(), Negate());
    116116    for (int i = 0; i < n; ++i) {
    117117      check(data1[i] == data2[n - 1 - i], "Test failed");
    118118    }
    119119
    120     counterSort(data2.begin(), data2.end(), negate);
     120    stableRadixSort(data2.begin(), data2.end(), negate);
    121121    for (int i = 0; i < n; ++i) {
    122122      check(data1[i] == data2[n - 1 - i], "Test failed");
     
    142142
    143143  checkRadixSort();
    144   checkCounterSort();
     144  checkStableRadixSort();
    145145
    146146  return 0;
Note: See TracChangeset for help on using the changeset viewer.