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 35 insertions and 34 deletions:

lemon/radix_sort.h

test/radix_sort_test.cc

↑ Collapse diff ↑

lemon/radix_sort.h

Show inline comments

@@ -216,9 +216,9 @@
 		  /// \param functor An adaptible unary function or a normal function
 		  /// 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;
 		    typedef typename Functor::result_type Value;
@@ -263,9 +263,9 @@
 		      return value >> (std::numeric_limits<unsigned char>::digits * byte);
+		    }
 		    template <typename Functor, typename Key>
-		    void counterIntroSort(Key *first, Key *last, Key *target,
+		    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);
@@ -289,9 +289,9 @@
+		      }
+		    }
 		    template <typename Functor, typename Key>
-		    void signedCounterIntroSort(Key *first, Key *last, Key *target,
+		    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);
@@ -321,9 +321,9 @@
+		    }
 		    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;
 		      Allocator allocator;
@@ -334,23 +334,23 @@
 		        bool dir = true;
 		        std::copy(first, last, buffer);
 		        for (int i = 0; i < int(sizeof(Value)) - 1; ++i) {
 		          if (dir) {
-		            counterIntroSort(buffer, buffer + length, buffer + length,
+		            stableRadixIntroSort(buffer, buffer + length, buffer + length,
 		                             i, functor);
 		          } else {
-		            counterIntroSort(buffer + length, buffer + 2 * length, buffer,
+		            stableRadixIntroSort(buffer + length, buffer + 2 * length, buffer,
 		                             i, functor);
+		          }
 		          dir = !dir;
+		        }
 		        if (dir) {
-		          signedCounterIntroSort(buffer, buffer + length, buffer + length,
+		          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 (...) {
 		        allocator.deallocate(buffer, 2 * length);
@@ -359,9 +359,10 @@
 		      allocator.deallocate(buffer, 2 * length);
+		    }
 		    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;
 		      Allocator allocator;
@@ -372,12 +373,12 @@
 		        bool dir = true;
 		        std::copy(first, last, buffer);
 		        for (int i = 0; i < int(sizeof(Value)); ++i) {
 		          if (dir) {
-		            counterIntroSort(buffer, buffer + length,
+		            stableRadixIntroSort(buffer, buffer + length,
 		                             buffer + length, i, functor);
 		          } else {
-		            counterIntroSort(buffer + length, buffer + 2 * length,
+		            stableRadixIntroSort(buffer + length, buffer + 2 * length,
 		                             buffer, i, functor);
+		          }
 		          dir = !dir;
+		        }
@@ -396,20 +397,20 @@
 		    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);
+		      }
 		    };
+		  }
@@ -422,9 +423,9 @@
 		  /// This function sorts an STL compatible range into ascending
 		  /// 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
 		  /// byte-by-byte. First, it counts how many times a byte value occurs
@@ -443,43 +444,43 @@
 		  /// which maps the items to any integer type which can be either
 		  /// 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

@@ -98,27 +98,27 @@
  }
}


void checkCounterSort() {
void checkStableRadixSort() {
  {
    std::vector<int> data1;
    generateIntSequence(n, data1);

    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");
    }
  }
@@ -140,8 +140,8 @@

int main() {

  checkRadixSort();
  checkCounterSort();
  checkStableRadixSort();

  return 0;
}

0 comments (0 inline)

...	...	@@ -98,27 +98,27 @@
98	98	}
99	99	}
100	100
101	101
102		void ~~checkCounterSort~~() {
	102	void checkStableRadixSort() {
103	103	{
104	104	std::vector<int> data1;
105	105	generateIntSequence(n, data1);
106	106
107	107	std::vector<int> data2(data1);
108	108	std::sort(data1.begin(), data1.end());
109	109
110		~~counterSort~~(data2.begin(), data2.end());
	110	stableRadixSort(data2.begin(), data2.end());
111	111	for (int i = 0; i < n; ++i) {
112	112	check(data1[i] == data2[i], "Test failed");
113	113	}
114	114
115		~~counterSort~~(data2.begin(), data2.end(), Negate());
	115	stableRadixSort(data2.begin(), data2.end(), Negate());
116	116	for (int i = 0; i < n; ++i) {
117	117	check(data1[i] == data2[n - 1 - i], "Test failed");
118	118	}
119	119
120		~~counterSort~~(data2.begin(), data2.end(), negate);
	120	stableRadixSort(data2.begin(), data2.end(), negate);
121	121	for (int i = 0; i < n; ++i) {
122	122	check(data1[i] == data2[n - 1 - i], "Test failed");
123	123	}
124	124	}
...	...	@@ -140,8 +140,8 @@
140	140
141	141	int main() {
142	142
143	143	checkRadixSort();
144		~~checkCounterSort~~();
	144	checkStableRadixSort();
145	145
146	146	return 0;
147	147	}

RhodeCode

Login to your account