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

@@ -196,291 +196,292 @@
 		  /// \brief Sorts the STL compatible range into ascending order.
 		  ///
 		  /// The \c radixSort sorts an STL compatible range into ascending
 		  /// order.  The radix sort algorithm can sort items which are mapped
 		  /// to integers with an adaptable unary function \c functor and the
 		  /// order will be ascending according to these mapped values.
 		  ///
 		  /// It is also possible to use a normal function instead
 		  /// of the functor object. If the functor is not given it will use
 		  /// the identity function instead.
 		  ///
 		  /// This is a special quick sort algorithm where the pivot
 		  /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.
 		  /// Therefore, the time complexity of the
 		  /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
 		  /// additional space, where \c c is the maximal value and \c n is the
 		  /// number of the items in the container.
 		  ///
 		  /// \param first The begin of the given range.
 		  /// \param last The end of the given range.
 		  /// \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;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator, typename Value, typename Key>
 		  void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
 		    using namespace _radix_sort_bits;
 		    RadixSortSelector<Value>::sort(first, last, functor);
+		  }
 		  template <typename Iterator>
 		  void radixSort(Iterator first, Iterator last) {
 		    using namespace _radix_sort_bits;
 		    typedef typename std::iterator_traits<Iterator>::value_type Value;
 		    RadixSortSelector<Value>::sort(first, last, Identity<Value>());
+		  }
 		  namespace _radix_sort_bits {
 		    template <typename Value>
 		    unsigned char valueByte(Value value, int byte) {
 		      return value >> (std::numeric_limits<unsigned char>::digits * byte);
+		    }
 		    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);
 		      for (int i = 0; i < size; ++i) {
 		        counter[i] = 0;
+		      }
 		      Key *it = first;
 		      while (first != last) {
 		        ++counter[valueByte(functor(*first), byte)];
 		        ++first;
+		      }
 		      int prev, num = 0;
 		      for (int i = 0; i < size; ++i) {
 		        prev = num;
 		        num += counter[i];
 		        counter[i] = prev;
+		      }
 		      while (it != last) {
 		        target[counter[valueByte(functor(*it), byte)]++] = *it;
 		        ++it;
+		      }
+		    }
 		    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);
 		      for (int i = 0; i < size; ++i) {
 		        counter[i] = 0;
+		      }
 		      Key *it = first;
 		      while (first != last) {
 		        counter[valueByte(functor(*first), byte)]++;
 		        ++first;
+		      }
 		      int prev, num = 0;
 		      for (int i = size / 2; i < size; ++i) {
 		        prev = num;
 		        num += counter[i];
 		        counter[i] = prev;
+		      }
 		      for (int i = 0; i < size / 2; ++i) {
 		        prev = num;
 		        num += counter[i];
 		        counter[i] = prev;
+		      }
 		      while (it != last) {
 		        target[counter[valueByte(functor(*it), byte)]++] = *it;
 		        ++it;
+		      }
+		    }
 		    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;
 		      int length = std::distance(first, last);
 		      Key* buffer = allocator.allocate(2 * length);
 		      try {
 		        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,
 		                             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 (...) {
 		        allocator.deallocate(buffer, 2 * length);
 		        throw;
+		      }
 		      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;
 		      int length = std::distance(first, last);
 		      Key *buffer = allocator.allocate(2 * length);
 		      try {
 		        bool dir = true;
 		        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;
+		        }
 		        if (dir) {
 		          std::copy(buffer, buffer + length, first);
 		        }        else {
 		          std::copy(buffer + length, buffer + 2 * length, first);
+		        }
 		      } catch (...) {
 		        allocator.deallocate(buffer, 2 * length);
 		        throw;
+		      }
 		      allocator.deallocate(buffer, 2 * length);
+		    }
 		    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);
+		      }
 		    };
+		  }
 		  /// \ingroup auxalg
 		  ///
 		  /// \brief Sorts the STL compatible range into ascending order in a stable
 		  /// way.
 		  ///
 		  /// 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
 		  /// in the container, then it copies the corresponding items to
 		  /// another container in asceding order in \c O(n) time.
 		  ///
 		  /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
 		  /// it uses \f$ O(n) \f$, additional space, where \c c is the
 		  /// maximal value and \c n is the number of the items in the
 		  /// container.
 		  ///
 		  /// \param first The begin of the given range.
 		  /// \param last The end of the given range.
 		  /// \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 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>());
+		  }
+		}
 		#endif

test/radix_sort_test.cc

Show inline comments

@@ -78,70 +78,70 @@

    radixSort(data2.begin(), data2.end(), negate);
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[n - 1 - i], "Test failed");
    }

  }

  {
    std::vector<unsigned char> data1(n);
    generateCharSequence(n, data1);

    std::vector<unsigned char> data2(data1);
    std::sort(data1.begin(), data1.end());

    radixSort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }

  }
}


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");
    }
  }

  {
    std::vector<unsigned char> data1(n);
    generateCharSequence(n, data1);

    std::vector<unsigned char> data2(data1);
    std::sort(data1.begin(), data1.end());

    radixSort(data2.begin(), data2.end());
    for (int i = 0; i < n; ++i) {
      check(data1[i] == data2[i], "Test failed");
    }

  }
}

int main() {

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

  return 0;
}

0 comments (0 inline)

...	...	@@ -78,70 +78,70 @@
78	78
79	79	radixSort(data2.begin(), data2.end(), negate);
80	80	for (int i = 0; i < n; ++i) {
81	81	check(data1[i] == data2[n - 1 - i], "Test failed");
82	82	}
83	83
84	84	}
85	85
86	86	{
87	87	std::vector<unsigned char> data1(n);
88	88	generateCharSequence(n, data1);
89	89
90	90	std::vector<unsigned char> data2(data1);
91	91	std::sort(data1.begin(), data1.end());
92	92
93	93	radixSort(data2.begin(), data2.end());
94	94	for (int i = 0; i < n; ++i) {
95	95	check(data1[i] == data2[i], "Test failed");
96	96	}
97	97
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	}
125	125
126	126	{
127	127	std::vector<unsigned char> data1(n);
128	128	generateCharSequence(n, data1);
129	129
130	130	std::vector<unsigned char> data2(data1);
131	131	std::sort(data1.begin(), data1.end());
132	132
133	133	radixSort(data2.begin(), data2.end());
134	134	for (int i = 0; i < n; ++i) {
135	135	check(data1[i] == data2[i], "Test failed");
136	136	}
137	137
138	138	}
139	139	}
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