diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -36,6 +36,7 @@ lemon/maps.h \ lemon/math.h \ lemon/path.h \ + lemon/radix_sort.h \ lemon/random.h \ lemon/smart_graph.h \ lemon/time_measure.h \ diff --git a/lemon/radix_sort.h b/lemon/radix_sort.h new file mode 100644 --- /dev/null +++ b/lemon/radix_sort.h @@ -0,0 +1,484 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef RADIX_SORT_H +#define RADIX_SORT_H + +/// \ingroup auxalg +/// \file +/// \brief Radix sort +/// +/// Linear time sorting algorithms + +#include +#include +#include +#include + +namespace lemon { + + namespace _radix_sort_bits { + + template + struct Identity { + const Value& operator()(const Value& val) { + return val; + } + }; + + + template + Iterator radixSortPartition(Iterator first, Iterator last, + Functor functor, Value mask) { + while (first != last && !(functor(*first) & mask)) { + ++first; + } + if (first == last) { + return first; + } + --last; + while (first != last && (functor(*last) & mask)) { + --last; + } + if (first == last) { + return first; + } + std::iter_swap(first, last); + ++first; + if (!(first < last)) { + return first; + } + while (true) { + while (!(functor(*first) & mask)) { + ++first; + } + --last; + while (functor(*last) & mask) { + --last; + } + if (!(first < last)) { + return first; + } + std::iter_swap(first, last); + ++first; + } + } + + template + Iterator radixSortSignPartition(Iterator first, Iterator last, + Functor functor) { + while (first != last && functor(*first) < 0) { + ++first; + } + if (first == last) { + return first; + } + --last; + while (first != last && functor(*last) >= 0) { + --last; + } + if (first == last) { + return first; + } + std::iter_swap(first, last); + ++first; + if (!(first < last)) { + return first; + } + while (true) { + while (functor(*first) < 0) { + ++first; + } + --last; + while (functor(*last) >= 0) { + --last; + } + if (!(first < last)) { + return first; + } + std::iter_swap(first, last); + ++first; + } + } + + template + void radixIntroSort(Iterator first, Iterator last, + Functor functor, Value mask) { + while (mask != 0 && last - first > 1) { + Iterator cut = radixSortPartition(first, last, functor, mask); + mask >>= 1; + radixIntroSort(first, cut, functor, mask); + first = cut; + } + } + + template + void radixSignedSort(Iterator first, Iterator last, Functor functor) { + + Iterator cut = radixSortSignPartition(first, last, functor); + + Value mask; + int max_digit; + Iterator it; + + mask = ~0; max_digit = 0; + for (it = first; it != cut; ++it) { + while ((mask & functor(*it)) != mask) { + ++max_digit; + mask <<= 1; + } + } + radixIntroSort(first, cut, functor, 1 << max_digit); + + mask = 0; max_digit = 0; + for (it = cut; it != last; ++it) { + while ((mask | functor(*it)) != mask) { + ++max_digit; + mask <<= 1; mask |= 1; + } + } + radixIntroSort(cut, last, functor, 1 << max_digit); + } + + template + void radixUnsignedSort(Iterator first, Iterator last, Functor functor) { + + Value mask = 0; + int max_digit = 0; + + Iterator it; + for (it = first; it != last; ++it) { + while ((mask | functor(*it)) != mask) { + ++max_digit; + mask <<= 1; mask |= 1; + } + } + radixIntroSort(first, last, functor, 1 << max_digit); + } + + + template ::is_signed > + struct RadixSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + radixSignedSort(first, last, functor); + } + }; + + template + struct RadixSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + radixUnsignedSort(first, last, functor); + } + }; + + } + + /// \ingroup auxalg + /// + /// \brief Sorts the STL compatible range into ascending order. + /// + /// The \c radixSort sorts the STL compatible range into ascending + /// order. The radix sort algorithm can sort the items which mapped + /// to an integer with an adaptable unary function \c functor and the + /// order will be ascending by these mapped values. As function + /// specialization it is possible to use a normal function instead + /// of the functor object or if the functor is not given it will use + /// an identity function instead. + /// + /// This implemented radix sort is a special quick sort which pivot + /// value is choosen to partite the items on the next + /// bit. Therefore, let be \c c the maximal capacity and \c n the + /// number of the items in the container, the time complexity of the + /// algorithm is \f$ O(\log(c)n) \f$ and the additional space + /// complexity is \f$ O(\log(c)) \f$. + /// + /// \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. + template + void radixSort(Iterator first, Iterator last, Functor functor) { + using namespace _radix_sort_bits; + typedef typename Functor::result_type Value; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { + using namespace _radix_sort_bits; + RadixSortSelector::sort(first, last, functor); + } + + template + void radixSort(Iterator first, Iterator last) { + using namespace _radix_sort_bits; + typedef typename std::iterator_traits::value_type Value; + RadixSortSelector::sort(first, last, Identity()); + } + + namespace _radix_sort_bits { + + template + unsigned char valueByte(Value value, int byte) { + return value >> (std::numeric_limits::digits * byte); + } + + template + void counterIntroSort(Key *first, Key *last, Key *target, + int byte, Functor functor) { + const int size = + unsigned(std::numeric_limits::max()) + 1; + std::vector 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 + void signedCounterIntroSort(Key *first, Key *last, Key *target, + int byte, Functor functor) { + const int size = + unsigned(std::numeric_limits::max()) + 1; + std::vector 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 + void counterSignedSort(Iterator first, Iterator last, Functor functor) { + if (first == last) return; + typedef typename std::iterator_traits::value_type Key; + typedef std::allocator 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); + } else { + counterIntroSort(buffer + length, buffer + 2 * length, buffer, + i, functor); + } + dir = !dir; + } + if (dir) { + signedCounterIntroSort(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); + std::copy(buffer, buffer + length, first); + } + } catch (...) { + allocator.deallocate(buffer, 2 * length); + throw; + } + allocator.deallocate(buffer, 2 * length); + } + + template + void counterUnsignedSort(Iterator first, Iterator last, Functor functor) { + if (first == last) return; + typedef typename std::iterator_traits::value_type Key; + typedef std::allocator 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); + } else { + counterIntroSort(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 ::is_signed > + struct CounterSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + counterSignedSort(first, last, functor); + } + }; + + template + struct CounterSortSelector { + template + static void sort(Iterator first, Iterator last, Functor functor) { + counterUnsignedSort(first, last, functor); + } + }; + + } + + /// \ingroup auxalg + /// + /// \brief Sorts stable the STL compatible range into ascending order. + /// + /// The \c counterSort sorts the STL compatible range into ascending + /// order. The counter sort algorithm can sort the items which + /// mapped to an integer with an adaptable unary function \c functor + /// and the order will be ascending by these mapped values. As + /// function specialization it is possible to use a normal function + /// instead of the functor object or if the functor is not given it + /// will use an identity function instead. + /// + /// The implemented counter sort 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 occurs a byte value + /// in the containerm, and with the occurence number the container + /// can be copied to an other in asceding order in \c O(n) time. + /// Let be \c c the maximal capacity of the integer type and \c n + /// the number of the items in the container, the time complexity of + /// the algorithm is \f$ O(\log(c)n) \f$ and the additional space + /// complexity is \f$ O(n) \f$. + /// + /// The sorting algorithm is stable, i.e. the order of two equal + /// element remains the same. + /// + /// \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. + template + void counterSort(Iterator first, Iterator last, Functor functor) { + using namespace _radix_sort_bits; + typedef typename Functor::result_type Value; + CounterSortSelector::sort(first, last, functor); + } + + template + void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) { + using namespace _radix_sort_bits; + CounterSortSelector::sort(first, last, functor); + } + + template + void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) { + using namespace _radix_sort_bits; + CounterSortSelector::sort(first, last, functor); + } + + template + void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) { + using namespace _radix_sort_bits; + CounterSortSelector::sort(first, last, functor); + } + + template + void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) { + using namespace _radix_sort_bits; + CounterSortSelector::sort(first, last, functor); + } + + template + void counterSort(Iterator first, Iterator last) { + using namespace _radix_sort_bits; + typedef typename std::iterator_traits::value_type Value; + CounterSortSelector::sort(first, last, Identity()); + } + +} + +#endif diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -16,6 +16,7 @@ heap_test kruskal_test maps_test + radix_sort_test random_test path_test time_measure_test diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -19,6 +19,7 @@ test/heap_test \ test/kruskal_test \ test/maps_test \ + test/radix_sort_test \ test/random_test \ test/path_test \ test/test_tools_fail \ @@ -43,6 +44,7 @@ test_kruskal_test_SOURCES = test/kruskal_test.cc test_maps_test_SOURCES = test/maps_test.cc test_path_test_SOURCES = test/path_test.cc +test_radix_sort_test_SOURCES = test/radix_sort_test.cc test_random_test_SOURCES = test/random_test.cc test_test_tools_fail_SOURCES = test/test_tools_fail.cc test_test_tools_pass_SOURCES = test/test_tools_pass.cc diff --git a/test/radix_sort_test.cc b/test/radix_sort_test.cc new file mode 100644 --- /dev/null +++ b/test/radix_sort_test.cc @@ -0,0 +1,147 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +#include +#include +#include +#include + +#include "test_tools.h" + +#include +#include + +using namespace lemon; + +static const int n = 10000; + +struct Negate { + typedef int argument_type; + typedef int result_type; + int operator()(int a) { return - a; } +}; + +int negate(int a) { return - a; } + + +void generateIntSequence(int n, std::vector& data) { + int prime = 9973; + int root = 136, value = 1; + for (int i = 0; i < n; ++i) { + data.push_back(value - prime / 2); + value = (value * root) % prime; + } +} + +void generateCharSequence(int n, std::vector& data) { + int prime = 251; + int root = 3, value = root; + for (int i = 0; i < n; ++i) { + data.push_back(static_cast(value)); + value = (value * root) % prime; + } +} + +void checkRadixSort() { + { + std::vector data1; + generateIntSequence(n, data1); + + std::vector 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"); + } + + radixSort(data2.begin(), data2.end(), Negate()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + + radixSort(data2.begin(), data2.end(), negate); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + + } + + { + std::vector data1(n); + generateCharSequence(n, data1); + + std::vector 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() { + { + std::vector data1; + generateIntSequence(n, data1); + + std::vector data2(data1); + std::sort(data1.begin(), data1.end()); + + counterSort(data2.begin(), data2.end()); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[i], "Test failed"); + } + + counterSort(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); + for (int i = 0; i < n; ++i) { + check(data1[i] == data2[n - 1 - i], "Test failed"); + } + } + + { + std::vector data1(n); + generateCharSequence(n, data1); + + std::vector 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(); + + return 0; +}