lemon: comparison lemon/radix

equal deleted inserted replaced

-:7a86dd6badd7
+:4e4f960b5780
 /// \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);
 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,
+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;
 ++it;
 }
 }
 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);
 for (int i = 0; i < size; ++i) {
 counter[i] = 0;
 }
 }
 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;
 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,
+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,
+signedStableRadixIntroSort(buffer + length, buffer + 2 * length,
-sizeof(Value) - 1, functor);
+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;
 try {
 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;
 }
 if (dir) {
 std::copy(buffer, buffer + length, first);
 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);
 }
 };
 }
 ///
 /// 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
 /// \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

changeset 466	de16f1f2d228
parent 465	31d224a3c0af
child 467	ba49101c9b07