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

@@ -218,5 +218,5 @@
 		  /// signed or unsigned.
 		  ///
-		  /// \sa counterSort()
+		  /// \sa stableRadixSort()
 		  template <typename Iterator, typename Functor>
 		  void radixSort(Iterator first, Iterator last, Functor functor) {
@@ -265,6 +265,6 @@
 		    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;
@@ -291,6 +291,6 @@
 		    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;
@@ -323,5 +323,5 @@
 		    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;
@@ -336,19 +336,19 @@
 		        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);
+		        }
@@ -361,5 +361,6 @@
 		    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;
@@ -374,9 +375,9 @@
 		        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;
@@ -398,16 +399,16 @@
 		    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);
+		      }
 		    };
@@ -424,5 +425,5 @@
 		  ///
 		  /// 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
@@ -445,39 +446,39 @@
 		  /// \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

@@ -100,5 +100,5 @@
-		void checkCounterSort() {
+		void checkStableRadixSort() {
+		  {
 		    std::vector<int> data1;
@@ -108,15 +108,15 @@
 		    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");
@@ -142,5 +142,5 @@
 		  checkRadixSort();
-		  checkCounterSort();
+		  checkStableRadixSort();
 		  return 0;

0 comments (0 inline)

RhodeCode

Login to your account