LEMON/LEMON-main Changeset - r443:de16f1f2d228

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r443:de16f1f2d228

« 442:31d224

444:ba4910 »

r443:de16f1f2d228

Tue, 02 Dec 2008 23:15:43

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Rename counterSort to stableRadixSort

0 2 0

default

2 files changed with 42 insertions and 41 deletions:

lemon/radix_sort.h

test/radix_sort_test.cc

↑ Collapse diff ↑

lemon/radix_sort.h

Show inline comments

@@ -217,7 +217,7 @@
 		  /// which maps the items to any integer type which can be either
 		  /// signed or unsigned.
 		  ///
-		  /// \sa counterSort()
+		  /// \sa stableRadixSort()
 		  template <typename Iterator, typename Functor>
 		  void radixSort(Iterator first, Iterator last, Functor functor) {
 		    using namespace _radix_sort_bits;
@@ -264,8 +264,8 @@
+		    }
 		    template <typename Functor, typename Key>
 		    void counterIntroSort(Key *first, Key *last, Key *target,
 		                          int byte, Functor functor) {
 		    void stableRadixIntroSort(Key *first, Key *last, Key *target,
 		                              int byte, Functor functor) {
 		      const int size =
 		        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
 		      std::vector<int> counter(size);
@@ -290,8 +290,8 @@
+		    }
 		    template <typename Functor, typename Key>
 		    void signedCounterIntroSort(Key *first, Key *last, Key *target,
 		                                int byte, Functor functor) {
 		    void signedStableRadixIntroSort(Key *first, Key *last, Key *target,
 		                                    int byte, Functor functor) {
 		      const int size =
 		        unsigned(std::numeric_limits<unsigned char>::max()) + 1;
 		      std::vector<int> counter(size);
@@ -322,7 +322,7 @@
 		    template <typename Value, typename Iterator, typename Functor>
-		    void counterSignedSort(Iterator first, Iterator last, Functor functor) {
+		    void stableRadixSignedSort(Iterator first, Iterator last, Functor functor) {
 		      if (first == last) return;
 		      typedef typename std::iterator_traits<Iterator>::value_type Key;
 		      typedef std::allocator<Key> Allocator;
@@ -335,21 +335,21 @@
 		        std::copy(first, last, buffer);
 		        for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
 		          if (dir) {
 		            counterIntroSort(buffer, buffer + length, buffer + length,
 		                             i, functor);
 		            stableRadixIntroSort(buffer, buffer + length, buffer + length,
 		                                 i, functor);
 		          } else {
 		            counterIntroSort(buffer + length, buffer + 2 * length, buffer,
 		                             i, functor);
 		            stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
 		                                 i, functor);
+		          }
 		          dir = !dir;
+		        }
 		        if (dir) {
 		          signedCounterIntroSort(buffer, buffer + length, buffer + length,
 		                                 sizeof(Value) - 1, functor);
 		          signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
 		                                     sizeof(Value) - 1, functor);
 		          std::copy(buffer + length, buffer + 2 * length, first);
 		        }        else {
 		          signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
 		                                 sizeof(Value) - 1, functor);
 		          signedStableRadixIntroSort(buffer + length, buffer + 2 * length,
 		                                     buffer, sizeof(Value) - 1, functor);
 		          std::copy(buffer, buffer + length, first);
+		        }
 		      } catch (...) {
@@ -360,7 +360,8 @@
+		    }
 		    template <typename Value, typename Iterator, typename Functor>
-		    void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
+		    void stableRadixUnsignedSort(Iterator first, Iterator last,
 		                                 Functor functor) {
 		      if (first == last) return;
 		      typedef typename std::iterator_traits<Iterator>::value_type Key;
 		      typedef std::allocator<Key> Allocator;
@@ -373,11 +374,11 @@
 		        std::copy(first, last, buffer);
 		        for (int i = 0; i < int(sizeof(Value)); ++i) {
 		          if (dir) {
 		            counterIntroSort(buffer, buffer + length,
 		                             buffer + length, i, functor);
 		            stableRadixIntroSort(buffer, buffer + length,
 		                                 buffer + length, i, functor);
 		          } else {
 		            counterIntroSort(buffer + length, buffer + 2 * length,
 		                             buffer, i, functor);
 		            stableRadixIntroSort(buffer + length, buffer + 2 * length,
 		                                 buffer, i, functor);
+		          }
 		          dir = !dir;
+		        }
@@ -397,18 +398,18 @@
 		    template <typename Value,
 		              bool sign = std::numeric_limits<Value>::is_signed >
-		    struct CounterSortSelector {
+		    struct StableRadixSortSelector {
 		      template <typename Iterator, typename Functor>
 		      static void sort(Iterator first, Iterator last, Functor functor) {
-		        counterSignedSort<Value>(first, last, functor);
+		        stableRadixSignedSort<Value>(first, last, functor);
+		      }
 		    };
 		    template <typename Value>
-		    struct CounterSortSelector<Value, false> {
+		    struct StableRadixSortSelector<Value, false> {
 		      template <typename Iterator, typename Functor>
 		      static void sort(Iterator first, Iterator last, Functor functor) {
-		        counterUnsignedSort<Value>(first, last, functor);
+		        stableRadixUnsignedSort<Value>(first, last, functor);
+		      }
 		    };
@@ -423,7 +424,7 @@
 		  /// order according to an integer mapping in the same as radixSort() does.
 		  ///
 		  /// This sorting algorithm is stable, i.e. the order of two equal
-		  /// element remains the same after the sorting.
+		  /// elements remains the same after the sorting.
 		  ///
 		  /// This sort algorithm  use a radix forward sort on the
 		  /// bytes of the integer number. The algorithm sorts the items
@@ -444,41 +445,41 @@
 		  /// signed or unsigned.
 		  /// \sa radixSort()
 		  template <typename Iterator, typename Functor>
-		  void counterSort(Iterator first, Iterator last, Functor functor) {
+		  void stableRadixSort(Iterator first, Iterator last, Functor functor) {
 		    using namespace _radix_sort_bits;
 		    typedef typename Functor::result_type Value;
-		    CounterSortSelector<Value>::sort(first, last, functor);
+		    StableRadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
-		  void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
+		  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
-		    CounterSortSelector<Value>::sort(first, last, functor);
+		    StableRadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
-		  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
+		  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
-		    CounterSortSelector<Value>::sort(first, last, functor);
+		    StableRadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
-		  void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
+		  void stableRadixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
-		    CounterSortSelector<Value>::sort(first, last, functor);
+		    StableRadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
-		  void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
+		  void stableRadixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
-		    CounterSortSelector<Value>::sort(first, last, functor);
+		    StableRadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator>
-		  void counterSort(Iterator first, Iterator last) {
+		  void stableRadixSort(Iterator first, Iterator last) {
 		    using namespace _radix_sort_bits;
 		    typedef typename std::iterator_traits<Iterator>::value_type Value;
-		    CounterSortSelector<Value>::sort(first, last, Identity<Value>());
+		    StableRadixSortSelector<Value>::sort(first, last, Identity<Value>());
+		  }
+		}

test/radix_sort_test.cc

Show inline comments

@@ -99,7 +99,7 @@
+		}
-		void checkCounterSort() {
+		void checkStableRadixSort() {
+		  {
 		    std::vector<int> data1;
 		    generateIntSequence(n, data1);
@@ -107,17 +107,17 @@
 		    std::vector<int> data2(data1);
 		    std::sort(data1.begin(), data1.end());
-		    counterSort(data2.begin(), data2.end());
+		    stableRadixSort(data2.begin(), data2.end());
 		    for (int i = 0; i < n; ++i) {
 		      check(data1[i] == data2[i], "Test failed");
+		    }
-		    counterSort(data2.begin(), data2.end(), Negate());
+		    stableRadixSort(data2.begin(), data2.end(), Negate());
 		    for (int i = 0; i < n; ++i) {
 		      check(data1[i] == data2[n - 1 - i], "Test failed");
+		    }
-		    counterSort(data2.begin(), data2.end(), negate);
+		    stableRadixSort(data2.begin(), data2.end(), negate);
 		    for (int i = 0; i < n; ++i) {
 		      check(data1[i] == data2[n - 1 - i], "Test failed");
+		    }
@@ -141,7 +141,7 @@
 		int main() {
 		  checkRadixSort();
-		  checkCounterSort();
+		  checkStableRadixSort();
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account