1.1 --- a/benchmark/Makefile.am Thu Nov 24 15:48:53 2005 +0000
1.2 +++ b/benchmark/Makefile.am Mon Nov 28 11:14:01 2005 +0000
1.3 @@ -2,10 +2,12 @@
1.4
1.5 noinst_HEADERS = bench_tools.h
1.6
1.7 -noinst_PROGRAMS = graph-bench hcube bfs-bench
1.8 +noinst_PROGRAMS = graph-bench hcube bfs-bench radix_sort-bench
1.9
1.10 graph_bench_SOURCES = graph-bench.cc
1.11
1.12 hcube_SOURCES = hcube.cc
1.13
1.14 bfs_bench_SOURCES = bfs-bench.cc
1.15 +
1.16 +radix_sort_bench_SOURCES = radix_sort-bench.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/benchmark/radix_sort-bench.cc Mon Nov 28 11:14:01 2005 +0000
2.3 @@ -0,0 +1,70 @@
2.4 +#define NDEBUG
2.5 +
2.6 +#include <lemon/time_measure.h>
2.7 +#include <lemon/smart_graph.h>
2.8 +#include <lemon/graph_utils.h>
2.9 +#include <lemon/maps.h>
2.10 +#include <lemon/error.h>
2.11 +
2.12 +#include <lemon/radix_sort.h>
2.13 +
2.14 +#include <vector>
2.15 +#include <algorithm>
2.16 +#include <cmath>
2.17 +
2.18 +using namespace std;
2.19 +using namespace lemon;
2.20 +
2.21 +void testRadixSort() {
2.22 + int n = 10000000;
2.23 + vector<int> data(n);
2.24 + for (int i = 0; i < n; ++i) {
2.25 + data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
2.26 + }
2.27 + radixSort(data.begin(), data.end());
2.28 +}
2.29 +
2.30 +
2.31 +void testCounterSort() {
2.32 + int n = 10000000;
2.33 + vector<int> data(n);
2.34 + for (int i = 0; i < n; ++i) {
2.35 + data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
2.36 + }
2.37 + counterSort(data.begin(), data.end());
2.38 +}
2.39 +
2.40 +void testSort() {
2.41 + int n = 10000000;
2.42 + vector<int> data(n);
2.43 + for (int i = 0; i < n; ++i) {
2.44 + data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
2.45 + }
2.46 + sort(data.begin(), data.end());
2.47 +}
2.48 +
2.49 +void testStableSort() {
2.50 + int n = 10000000;
2.51 + vector<int> data(n);
2.52 + for (int i = 0; i < n; ++i) {
2.53 + data[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
2.54 + }
2.55 + stable_sort(data.begin(), data.end());
2.56 +}
2.57 +
2.58 +void testSorts() {
2.59 + {
2.60 + int n = 10000000;
2.61 + vector<int> data(n);
2.62 + }
2.63 + cout << "Radix sort: " << runningTimeTest(testRadixSort, 60) << endl;
2.64 + cout << "Counter sort: " << runningTimeTest(testCounterSort, 60) << endl;
2.65 + cout << "Standard sort: " << runningTimeTest(testSort, 60) << endl;
2.66 + cout << "Stable sort: " << runningTimeTest(testStableSort, 60) << endl;
2.67 +}
2.68 +
2.69 +
2.70 +int main() {
2.71 + testSorts();
2.72 + return 0;
2.73 +}
3.1 --- a/lemon/Makefile.am Thu Nov 24 15:48:53 2005 +0000
3.2 +++ b/lemon/Makefile.am Mon Nov 28 11:14:01 2005 +0000
3.3 @@ -57,6 +57,7 @@
3.4 preflow.h \
3.5 path.h \
3.6 radix_heap.h \
3.7 + radix_sort.h \
3.8 smart_graph.h \
3.9 time_measure.h \
3.10 topology.h \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/radix_sort.h Mon Nov 28 11:14:01 2005 +0000
4.3 @@ -0,0 +1,483 @@
4.4 +/* -*- C++ -*-
4.5 + * lemon/radix_sort.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef RADIX_SORT_H
4.21 +#define RADIX_SORT_H
4.22 +
4.23 +/// \ingroup auxdat
4.24 +/// \file
4.25 +/// \brief Radix sort
4.26 +///
4.27 +
4.28 +#include <vector>
4.29 +#include <limits>
4.30 +#include <iterator>
4.31 +#include <algorithm>
4.32 +
4.33 +#include <lemon/error.h>
4.34 +
4.35 +namespace lemon {
4.36 +
4.37 + namespace _radix_sort_bits {
4.38 +
4.39 + template <typename Value>
4.40 + struct Identity {
4.41 + const Value& operator()(const Value& val) {
4.42 + return val;
4.43 + }
4.44 + };
4.45 +
4.46 + }
4.47 +
4.48 + template <typename Value, typename Iterator, typename Functor>
4.49 + Iterator radixSortPartition(Iterator first, Iterator last,
4.50 + Functor functor, Value mask) {
4.51 + while (first != last && !(functor(*first) & mask)) {
4.52 + ++first;
4.53 + }
4.54 + if (first == last) {
4.55 + return first;
4.56 + }
4.57 + --last;
4.58 + while (first != last && (functor(*last) & mask)) {
4.59 + --last;
4.60 + }
4.61 + if (first == last) {
4.62 + return first;
4.63 + }
4.64 + std::iter_swap(first, last);
4.65 + ++first;
4.66 + if (!(first < last)) {
4.67 + return first;
4.68 + }
4.69 + while (true) {
4.70 + while (!(functor(*first) & mask)) {
4.71 + ++first;
4.72 + }
4.73 + --last;
4.74 + while (functor(*last) & mask) {
4.75 + --last;
4.76 + }
4.77 + if (!(first < last)) {
4.78 + return first;
4.79 + }
4.80 + std::iter_swap(first, last);
4.81 + ++first;
4.82 + }
4.83 + }
4.84 +
4.85 + template <typename Iterator, typename Functor>
4.86 + Iterator radixSortSignPartition(Iterator first, Iterator last,
4.87 + Functor functor) {
4.88 + while (first != last && functor(*first) < 0) {
4.89 + ++first;
4.90 + }
4.91 + if (first == last) {
4.92 + return first;
4.93 + }
4.94 + --last;
4.95 + while (first != last && functor(*last) >= 0) {
4.96 + --last;
4.97 + }
4.98 + if (first == last) {
4.99 + return first;
4.100 + }
4.101 + std::iter_swap(first, last);
4.102 + ++first;
4.103 + if (!(first < last)) {
4.104 + return first;
4.105 + }
4.106 + while (true) {
4.107 + while (functor(*first) < 0) {
4.108 + ++first;
4.109 + }
4.110 + --last;
4.111 + while (functor(*last) >= 0) {
4.112 + --last;
4.113 + }
4.114 + if (!(first < last)) {
4.115 + return first;
4.116 + }
4.117 + std::iter_swap(first, last);
4.118 + ++first;
4.119 + }
4.120 + }
4.121 +
4.122 + template <typename Value, typename Iterator, typename Functor>
4.123 + void radixIntroSort(Iterator first, Iterator last,
4.124 + Functor functor, Value mask) {
4.125 + while (mask != 0 && last - first > 1) {
4.126 + Iterator cut = radixSortPartition(first, last, functor, mask);
4.127 + mask >>= 1;
4.128 + radixIntroSort(first, cut, functor, mask);
4.129 + first = cut;
4.130 + }
4.131 + }
4.132 +
4.133 + template <typename Value, typename Iterator, typename Functor>
4.134 + void radixSignedSort(Iterator first, Iterator last, Functor functor) {
4.135 + Iterator cut = radixSortSignPartition(first, last, functor);
4.136 +
4.137 + Value mask;
4.138 + int max_digit;
4.139 + Iterator it;
4.140 +
4.141 + mask = 0; max_digit = 0;
4.142 + for (it = first; it != cut; ++it) {
4.143 + if ((mask | functor(*it)) != ~0) {
4.144 + ++max_digit;
4.145 + mask <<= 1;
4.146 + mask |= 1;
4.147 + }
4.148 + }
4.149 + radixIntroSort(first, cut, functor, 1 << max_digit);
4.150 +
4.151 + mask = ~0; max_digit = 0;
4.152 + for (it = cut; it != last; ++it) {
4.153 + if (mask & functor(*it)) {
4.154 + ++max_digit;
4.155 + mask <<= 1;
4.156 + }
4.157 + }
4.158 + radixIntroSort(cut, last, functor, 1 << max_digit);
4.159 + }
4.160 +
4.161 + template <typename Value, typename Iterator, typename Functor>
4.162 + void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
4.163 +
4.164 + Value mask = ~0;
4.165 + int max_digit = 0;
4.166 +
4.167 + Iterator it;
4.168 + for (it = first; it != last; ++it) {
4.169 + if (mask & functor(*it)) {
4.170 + ++max_digit;
4.171 + mask <<= 1;
4.172 + }
4.173 + }
4.174 + radixIntroSort(first, last, functor, 1 << max_digit);
4.175 + }
4.176 +
4.177 + namespace _radix_sort_bits {
4.178 +
4.179 + template <typename Value,
4.180 + bool sign = std::numeric_limits<Value>::is_signed >
4.181 + struct RadixSortSelector {
4.182 + template <typename Iterator, typename Functor>
4.183 + static void sort(Iterator first, Iterator last, Functor functor) {
4.184 + radixSignedSort<Value>(first, last, functor);
4.185 + }
4.186 + };
4.187 +
4.188 + template <typename Value>
4.189 + struct RadixSortSelector<Value, false> {
4.190 + template <typename Iterator, typename Functor>
4.191 + static void sort(Iterator first, Iterator last, Functor functor) {
4.192 + radixUnsignedSort<Value>(first, last, functor);
4.193 + }
4.194 + };
4.195 +
4.196 + }
4.197 +
4.198 + /// \ingroup auxdat
4.199 + ///
4.200 + /// \brief Sorts the stl compatible range into ascending order.
4.201 + ///
4.202 + /// The \c radixSort sorts the stl compatible range into ascending order.
4.203 + /// The radix sort algorithm can sort the items which mapped to an
4.204 + /// integer by the adaptable unary function \c functor and the order
4.205 + /// will be ascending by these mapped values. As function specialization
4.206 + /// there is possible to use a normal function as the functor object
4.207 + /// or if the functor is not given it will use an identity function instead.
4.208 + ///
4.209 + /// This implemented radix sort is a special quick sort which pivot value
4.210 + /// is choosen to partite the items on the next bit. This way, let be
4.211 + /// \c c the maximal capacity and \c n the number of the items in
4.212 + /// the container, the time complexity of the algorithm \c O(log(c)*n)
4.213 + /// and the additional space complexity is \c O(log(c)).
4.214 + ///
4.215 + /// \param first The begin of the given range.
4.216 + /// \param last The end of the given range.
4.217 + /// \param functor An adaptible unary function or a normal function which
4.218 + /// maps the items to any integer type which can be wheter signed or
4.219 + /// unsigned.
4.220 + template <typename Iterator, typename Functor>
4.221 + void radixSort(Iterator first, Iterator last, Functor functor) {
4.222 + using namespace _radix_sort_bits;
4.223 + typedef typename Functor::result_type Value;
4.224 + RadixSortSelector<Value>::sort(first, last, functor);
4.225 + }
4.226 +
4.227 + template <typename Iterator, typename Value, typename Key>
4.228 + void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
4.229 + using namespace _radix_sort_bits;
4.230 + RadixSortSelector<Value>::sort(first, last, functor);
4.231 + }
4.232 +
4.233 + template <typename Iterator, typename Value, typename Key>
4.234 + void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
4.235 + using namespace _radix_sort_bits;
4.236 + RadixSortSelector<Value>::sort(first, last, functor);
4.237 + }
4.238 +
4.239 + template <typename Iterator, typename Value, typename Key>
4.240 + void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
4.241 + using namespace _radix_sort_bits;
4.242 + RadixSortSelector<Value>::sort(first, last, functor);
4.243 + }
4.244 +
4.245 + template <typename Iterator, typename Value, typename Key>
4.246 + void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
4.247 + using namespace _radix_sort_bits;
4.248 + RadixSortSelector<Value>::sort(first, last, functor);
4.249 + }
4.250 +
4.251 + template <typename Iterator>
4.252 + void radixSort(Iterator first, Iterator last) {
4.253 + using namespace _radix_sort_bits;
4.254 + typedef typename std::iterator_traits<Iterator>::value_type Value;
4.255 + RadixSortSelector<Value>::sort(first, last, Identity<Value>());
4.256 + }
4.257 +
4.258 + template <typename Value>
4.259 + unsigned char valueByte(Value value, int byte) {
4.260 + return *((unsigned char *)(&value) + byte);
4.261 + }
4.262 +
4.263 + template <typename Functor, typename Key>
4.264 + void counterIntroSort(Key *first, Key *last, Key *target,
4.265 + int byte, Functor functor) {
4.266 + const int size =
4.267 + (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
4.268 + int counter[size];
4.269 + for (int i = 0; i < size; ++i) {
4.270 + counter[i] = 0;
4.271 + }
4.272 + Key *it = first;
4.273 + while (first != last) {
4.274 + ++counter[valueByte(functor(*first), byte)];
4.275 + ++first;
4.276 + }
4.277 + int prev, num = 0;
4.278 + for (int i = 0; i < size; ++i) {
4.279 + prev = num;
4.280 + num += counter[i];
4.281 + counter[i] = prev;
4.282 + }
4.283 + while (it != last) {
4.284 + target[counter[valueByte(functor(*it), byte)]++] = *it;
4.285 + ++it;
4.286 + }
4.287 + }
4.288 +
4.289 + template <typename Functor, typename Key>
4.290 + void signedCounterIntroSort(Key *first, Key *last, Key *target,
4.291 + int byte, Functor functor) {
4.292 + const int size =
4.293 + (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
4.294 + int counter[size];
4.295 + for (int i = 0; i < size; ++i) {
4.296 + counter[i] = 0;
4.297 + }
4.298 + Key *it = first;
4.299 + while (first != last) {
4.300 + counter[valueByte(functor(*first), byte)]++;
4.301 + ++first;
4.302 + }
4.303 + int prev, num = 0;
4.304 + for (int i = size / 2; i < size; ++i) {
4.305 + prev = num;
4.306 + num += counter[i];
4.307 + counter[i] = prev;
4.308 + }
4.309 + for (int i = 0; i < size / 2; ++i) {
4.310 + prev = num;
4.311 + num += counter[i];
4.312 + counter[i] = prev;
4.313 + }
4.314 + while (it != last) {
4.315 + target[counter[valueByte(functor(*it), byte)]++] = *it;
4.316 + ++it;
4.317 + }
4.318 + }
4.319 +
4.320 +
4.321 + template <typename Value, typename Iterator, typename Functor>
4.322 + void counterSignedSort(Iterator first, Iterator last, Functor functor) {
4.323 + typedef typename std::iterator_traits<Iterator>::value_type Key;
4.324 + typedef std::allocator<Key> Allocator;
4.325 + Allocator allocator;
4.326 +
4.327 + int length = std::distance(first, last);
4.328 + Key* buffer;
4.329 + buffer = allocator.allocate(2 * length);
4.330 + try {
4.331 + bool dir = true;
4.332 + std::copy(first, last, buffer);
4.333 + for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
4.334 + if (dir) {
4.335 + counterIntroSort(buffer, buffer + length, buffer + length,
4.336 + i, functor);
4.337 + } else {
4.338 + counterIntroSort(buffer + length, buffer + 2 * length, buffer,
4.339 + i, functor);
4.340 + }
4.341 + dir = !dir;
4.342 + }
4.343 + if (dir) {
4.344 + signedCounterIntroSort(buffer, buffer + length, buffer + length,
4.345 + sizeof(Value) - 1, functor);
4.346 + std::copy(buffer + length, buffer + 2 * length, first);
4.347 + } else {
4.348 + signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
4.349 + sizeof(Value) - 1, functor);
4.350 + std::copy(buffer, buffer + length, first);
4.351 + }
4.352 + } catch (...) {
4.353 + allocator.deallocate(buffer, 2 * length);
4.354 + throw;
4.355 + }
4.356 + allocator.deallocate(buffer, 2 * length);
4.357 + }
4.358 +
4.359 + template <typename Value, typename Iterator, typename Functor>
4.360 + void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
4.361 + typedef typename std::iterator_traits<Iterator>::value_type Key;
4.362 + typedef std::allocator<Key> Allocator;
4.363 + Allocator allocator;
4.364 +
4.365 + int length = std::distance(first, last);
4.366 + Key *buffer;
4.367 + buffer = allocator.allocate(2 * length);
4.368 + try {
4.369 + bool dir = true;
4.370 + std::copy(first, last, buffer);
4.371 + for (int i = 0; i < sizeof(Value); ++i) {
4.372 + if (dir) {
4.373 + counterIntroSort(buffer, buffer + length, buffer + length,
4.374 + i, functor);
4.375 + } else {
4.376 + counterIntroSort(buffer + length, buffer + 2 * length, buffer,
4.377 + i, functor);
4.378 + }
4.379 + dir = !dir;
4.380 + }
4.381 + if (dir) {
4.382 + std::copy(buffer, buffer + length, first);
4.383 + } else {
4.384 + std::copy(buffer + length, buffer + 2 * length, first);
4.385 + }
4.386 + } catch (...) {
4.387 + allocator.deallocate(buffer, 2 * length);
4.388 + throw;
4.389 + }
4.390 + allocator.deallocate(buffer, 2 * length);
4.391 + }
4.392 +
4.393 + namespace _radix_sort_bits {
4.394 +
4.395 + template <typename Value,
4.396 + bool sign = std::numeric_limits<Value>::is_signed >
4.397 + struct CounterSortSelector {
4.398 + template <typename Iterator, typename Functor>
4.399 + static void sort(Iterator first, Iterator last, Functor functor) {
4.400 + counterSignedSort<Value>(first, last, functor);
4.401 + }
4.402 + };
4.403 +
4.404 + template <typename Value>
4.405 + struct CounterSortSelector<Value, false> {
4.406 + template <typename Iterator, typename Functor>
4.407 + static void sort(Iterator first, Iterator last, Functor functor) {
4.408 + counterUnsignedSort<Value>(first, last, functor);
4.409 + }
4.410 + };
4.411 +
4.412 + }
4.413 +
4.414 + /// \ingroup auxdat
4.415 + ///
4.416 + /// \brief Sorts stable the stl compatible range into ascending order.
4.417 + ///
4.418 + /// The \c counterSort sorts the stl compatible range into ascending order.
4.419 + /// The counter sort algorithm can sort the items which mapped to an
4.420 + /// integer by the adaptable unary function \c functor and the order
4.421 + /// will be ascending by these mapped values. As function specialization
4.422 + /// there is possible to use a normal function as the functor object
4.423 + /// or if the functor is not given it will use an identity function instead.
4.424 + ///
4.425 + /// This implemented counter sort use a radix forward sort on the bytes of
4.426 + /// the integer. The algorithm can sort the items on a given byte.
4.427 + /// First time it counts how many times occurs a byte value in the container.
4.428 + /// By the occurence number it is possible to copy the container
4.429 + /// in the right order in \c O(n) time. The algorithm sorts the container
4.430 + /// by each bytes in forward direction which sorts the container by the
4.431 + /// whole value. This way, let be
4.432 + /// \c c the maximal capacity and \c n the number of the items in
4.433 + /// the container, the time complexity of the algorithm \c O(log(c)*n)
4.434 + /// and the additional space complexity is \c O(n).
4.435 + ///
4.436 + /// This sorting algorithm is stable so the order of two equal element
4.437 + /// stay in the same order.
4.438 + ///
4.439 + /// \param first The begin of the given range.
4.440 + /// \param last The end of the given range.
4.441 + /// \param functor An adaptible unary function or a normal function which
4.442 + /// maps the items to any integer type which can be wheter signed or
4.443 + /// unsigned.
4.444 + template <typename Iterator, typename Functor>
4.445 + void counterSort(Iterator first, Iterator last, Functor functor) {
4.446 + using namespace _radix_sort_bits;
4.447 + typedef typename Functor::result_type Value;
4.448 + CounterSortSelector<Value>::sort(first, last, functor);
4.449 + }
4.450 +
4.451 + template <typename Iterator, typename Value, typename Key>
4.452 + void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
4.453 + using namespace _radix_sort_bits;
4.454 + CounterSortSelector<Value>::sort(first, last, functor);
4.455 + }
4.456 +
4.457 + template <typename Iterator, typename Value, typename Key>
4.458 + void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
4.459 + using namespace _radix_sort_bits;
4.460 + CounterSortSelector<Value>::sort(first, last, functor);
4.461 + }
4.462 +
4.463 + template <typename Iterator, typename Value, typename Key>
4.464 + void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
4.465 + using namespace _radix_sort_bits;
4.466 + CounterSortSelector<Value>::sort(first, last, functor);
4.467 + }
4.468 +
4.469 + template <typename Iterator, typename Value, typename Key>
4.470 + void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
4.471 + using namespace _radix_sort_bits;
4.472 + CounterSortSelector<Value>::sort(first, last, functor);
4.473 + }
4.474 +
4.475 + template <typename Iterator>
4.476 + void counterSort(Iterator first, Iterator last) {
4.477 + using namespace _radix_sort_bits;
4.478 + typedef typename std::iterator_traits<Iterator>::value_type Value;
4.479 + CounterSortSelector<Value>::sort(first, last, Identity<Value>());
4.480 + }
4.481 +
4.482 +}
4.483 +
4.484 +
4.485 +
4.486 +#endif
5.1 --- a/test/Makefile.am Thu Nov 24 15:48:53 2005 +0000
5.2 +++ b/test/Makefile.am Mon Nov 28 11:14:01 2005 +0000
5.3 @@ -26,6 +26,7 @@
5.4 suurballe_test \
5.5 path_test \
5.6 preflow_test \
5.7 + radix_sort_test \
5.8 test_tools_fail \
5.9 test_tools_pass \
5.10 time_measure_test \
5.11 @@ -59,6 +60,7 @@
5.12 max_matching_test_SOURCES = max_matching_test.cc
5.13 suurballe_test_SOURCES = suurballe_test.cc
5.14 path_test_SOURCES = path_test.cc
5.15 +radix_sort_test_SOURCES = radix_sort_test.cc
5.16 preflow_test_SOURCES = preflow_test.cc
5.17 time_measure_test_SOURCES = time_measure_test.cc
5.18 test_tools_fail_SOURCES = test_tools_fail.cc
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/test/radix_sort_test.cc Mon Nov 28 11:14:01 2005 +0000
6.3 @@ -0,0 +1,144 @@
6.4 +#include <lemon/time_measure.h>
6.5 +#include <lemon/smart_graph.h>
6.6 +#include <lemon/graph_utils.h>
6.7 +#include <lemon/maps.h>
6.8 +#include <lemon/radix_sort.h>
6.9 +
6.10 +#include "test_tools.h"
6.11 +
6.12 +
6.13 +#include <vector>
6.14 +#include <algorithm>
6.15 +#include <cmath>
6.16 +
6.17 +using namespace std;
6.18 +using namespace lemon;
6.19 +
6.20 +void checkRadixSort() {
6.21 + int n = 10000;
6.22 + vector<int> data1(n), data2(n);
6.23 + for (int i = 0; i < n; ++i) {
6.24 + data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
6.25 + }
6.26 + radixSort(data1.begin(), data1.end());
6.27 + sort(data2.begin(), data2.end());
6.28 + for (int i = 0; i < n; ++i) {
6.29 + check(data1[i] == data2[i], "Test failed");
6.30 + }
6.31 +}
6.32 +
6.33 +
6.34 +void checkCounterSort() {
6.35 + int n = 10000;
6.36 + vector<int> data1(n), data2(n);
6.37 + for (int i = 0; i < n; ++i) {
6.38 + data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
6.39 + }
6.40 + counterSort(data1.begin(), data1.end());
6.41 + sort(data2.begin(), data2.end());
6.42 + for (int i = 0; i < n; ++i) {
6.43 + check(data1[i] == data2[i], "Test failed");
6.44 + }
6.45 +}
6.46 +
6.47 +void checkSorts() {
6.48 + checkRadixSort();
6.49 + checkCounterSort();
6.50 +}
6.51 +
6.52 +void checkGraphRadixSort() {
6.53 + typedef SmartGraph Graph;
6.54 + typedef Graph::Node Node;
6.55 + typedef Graph::Edge Edge;
6.56 +
6.57 + const int n = 100;
6.58 + const int e = (int)(n * log((double)n));
6.59 +
6.60 + Graph graph;
6.61 + vector<Node> nodes;
6.62 +
6.63 + for (int i = 0; i < n; ++i) {
6.64 + nodes.push_back(graph.addNode());
6.65 + }
6.66 + vector<Edge> edges;
6.67 + for (int i = 0; i < e; ++i) {
6.68 + int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
6.69 + int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
6.70 + edges.push_back(graph.addEdge(nodes[s], nodes[t]));
6.71 + }
6.72 +
6.73 + radixSort(edges.begin(), edges.end(),
6.74 + mapFunctor(composeMap(IdMap<Graph, Node>(graph),
6.75 + sourceMap(graph))));
6.76 +
6.77 + Graph::EdgeMap<bool> was(graph, false);
6.78 +
6.79 + for (int i = 0; i < (int)edges.size(); ++i) {
6.80 + check(!was[edges[i]], "Test failed");
6.81 + was[edges[i]] = true;
6.82 + }
6.83 +
6.84 + for (int i = 1; i < (int)edges.size(); ++i) {
6.85 + check(graph.id(graph.source(edges[i - 1])) <=
6.86 + graph.id(graph.source(edges[i])), "Test failed");
6.87 + }
6.88 +
6.89 +}
6.90 +
6.91 +void checkGraphCounterSort() {
6.92 + typedef SmartGraph Graph;
6.93 + typedef Graph::Node Node;
6.94 + typedef Graph::Edge Edge;
6.95 +
6.96 + const int n = 100;
6.97 + const int e = (int)(n * log((double)n));
6.98 +
6.99 + Graph graph;
6.100 + vector<Node> nodes;
6.101 +
6.102 + for (int i = 0; i < n; ++i) {
6.103 + nodes.push_back(graph.addNode());
6.104 + }
6.105 + vector<Edge> edges;
6.106 + for (int i = 0; i < e; ++i) {
6.107 + int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
6.108 + int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
6.109 + edges.push_back(graph.addEdge(nodes[s], nodes[t]));
6.110 + }
6.111 +
6.112 + counterSort(edges.begin(), edges.end(),
6.113 + mapFunctor(composeMap(IdMap<Graph, Node>(graph),
6.114 + sourceMap(graph))));
6.115 +
6.116 + counterSort(edges.begin(), edges.end(),
6.117 + mapFunctor(composeMap(IdMap<Graph, Node>(graph),
6.118 + targetMap(graph))));
6.119 +
6.120 + Graph::EdgeMap<bool> was(graph, false);
6.121 +
6.122 + for (int i = 0; i < (int)edges.size(); ++i) {
6.123 + check(!was[edges[i]], "Test failed");
6.124 + was[edges[i]] = true;
6.125 + }
6.126 +
6.127 + for (int i = 1; i < (int)edges.size(); ++i) {
6.128 + check(graph.id(graph.target(edges[i - 1])) <
6.129 + graph.id(graph.target(edges[i])) ||
6.130 + (graph.id(graph.target(edges[i - 1])) ==
6.131 + graph.id(graph.target(edges[i])) &&
6.132 + graph.id(graph.source(edges[i - 1])) <=
6.133 + graph.id(graph.source(edges[i]))), "Test failed");
6.134 + }
6.135 +
6.136 +}
6.137 +
6.138 +void checkGraphSorts() {
6.139 + checkGraphRadixSort();
6.140 + checkGraphCounterSort();
6.141 +}
6.142 +
6.143 +int main() {
6.144 + checkSorts();
6.145 + checkGraphSorts();
6.146 + return 0;
6.147 +}