test/radix_sort_test.cc
 author Alpar Juttner Tue, 02 Dec 2008 10:17:30 +0000 changeset 442 31d224a3c0af parent 441 4f7224faf3bd child 443 de16f1f2d228 permissions -rw-r--r--
Doc improvements and source unification in radix_sort (#72)
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
2  *
3  * This file is a part of LEMON, a generic C++ optimization library.
4  *
5  * Copyright (C) 2003-2008
6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
8  *
9  * Permission to use, modify and distribute this software is granted
10  * provided that this copyright notice appears in all copies. For
11  * precise terms see the accompanying LICENSE file.
12  *
13  * This software is provided "AS IS" with no warranty of any kind,
14  * express or implied, and with no claim as to its suitability for any
15  * purpose.
16  *
17  */
19 #include <lemon/time_measure.h>
20 #include <lemon/smart_graph.h>
21 #include <lemon/maps.h>
22 #include <lemon/radix_sort.h>
23 #include <lemon/math.h>
25 #include "test_tools.h"
27 #include <vector>
28 #include <algorithm>
30 using namespace lemon;
32 static const int n = 10000;
34 struct Negate {
35   typedef int argument_type;
36   typedef int result_type;
37   int operator()(int a) { return - a; }
38 };
40 int negate(int a) { return - a; }
43 void generateIntSequence(int n, std::vector<int>& data) {
44   int prime = 9973;
45   int root = 136, value = 1;
46   for (int i = 0; i < n; ++i) {
47     data.push_back(value - prime / 2);
48     value = (value * root) % prime;
49   }
50 }
52 void generateCharSequence(int n, std::vector<unsigned char>& data) {
53   int prime = 251;
54   int root = 3, value = root;
55   for (int i = 0; i < n; ++i) {
56     data.push_back(static_cast<unsigned char>(value));
57     value = (value * root) % prime;
58   }
59 }
61 void checkRadixSort() {
62   {
63     std::vector<int> data1;
64     generateIntSequence(n, data1);
66     std::vector<int> data2(data1);
67     std::sort(data1.begin(), data1.end());
69     radixSort(data2.begin(), data2.end());
70     for (int i = 0; i < n; ++i) {
71       check(data1[i] == data2[i], "Test failed");
72     }
74     radixSort(data2.begin(), data2.end(), Negate());
75     for (int i = 0; i < n; ++i) {
76       check(data1[i] == data2[n - 1 - i], "Test failed");
77     }
79     radixSort(data2.begin(), data2.end(), negate);
80     for (int i = 0; i < n; ++i) {
81       check(data1[i] == data2[n - 1 - i], "Test failed");
82     }
84   }
86   {
87     std::vector<unsigned char> data1(n);
88     generateCharSequence(n, data1);
90     std::vector<unsigned char> data2(data1);
91     std::sort(data1.begin(), data1.end());
93     radixSort(data2.begin(), data2.end());
94     for (int i = 0; i < n; ++i) {
95       check(data1[i] == data2[i], "Test failed");
96     }
98   }
99 }
102 void checkCounterSort() {
103   {
104     std::vector<int> data1;
105     generateIntSequence(n, data1);
107     std::vector<int> data2(data1);
108     std::sort(data1.begin(), data1.end());
110     counterSort(data2.begin(), data2.end());
111     for (int i = 0; i < n; ++i) {
112       check(data1[i] == data2[i], "Test failed");
113     }
115     counterSort(data2.begin(), data2.end(), Negate());
116     for (int i = 0; i < n; ++i) {
117       check(data1[i] == data2[n - 1 - i], "Test failed");
118     }
120     counterSort(data2.begin(), data2.end(), negate);
121     for (int i = 0; i < n; ++i) {
122       check(data1[i] == data2[n - 1 - i], "Test failed");
123     }
124   }
126   {
127     std::vector<unsigned char> data1(n);
128     generateCharSequence(n, data1);
130     std::vector<unsigned char> data2(data1);
131     std::sort(data1.begin(), data1.end());
133     radixSort(data2.begin(), data2.end());
134     for (int i = 0; i < n; ++i) {
135       check(data1[i] == data2[i], "Test failed");
136     }
138   }
139 }
141 int main() {
143   checkRadixSort();
144   checkCounterSort();
146   return 0;
147 }