equal
deleted
inserted
replaced
30 #include <cmath> |
30 #include <cmath> |
31 |
31 |
32 using namespace std; |
32 using namespace std; |
33 using namespace lemon; |
33 using namespace lemon; |
34 |
34 |
|
35 typedef unsigned char uchar; |
|
36 |
35 void checkRadixSort() { |
37 void checkRadixSort() { |
36 { |
38 { |
37 int n = 10000; |
39 int n = 10000; |
38 vector<int> data1(n), data2(n); |
40 vector<int> data1(n), data2(n); |
39 for (int i = 0; i < n; ++i) { |
41 for (int i = 0; i < n; ++i) { |
46 } |
48 } |
47 } { |
49 } { |
48 int n = 10000; |
50 int n = 10000; |
49 vector<unsigned char> data1(n), data2(n); |
51 vector<unsigned char> data1(n), data2(n); |
50 for (int i = 0; i < n; ++i) { |
52 for (int i = 0; i < n; ++i) { |
51 data1[i] = data2[i] = rnd[(unsigned char)200]; |
53 data1[i] = data2[i] = rnd[uchar(200)]; |
52 } |
54 } |
53 radixSort(data1.begin(), data1.end()); |
55 radixSort(data1.begin(), data1.end()); |
54 sort(data2.begin(), data2.end()); |
56 sort(data2.begin(), data2.end()); |
55 for (int i = 0; i < n; ++i) { |
57 for (int i = 0; i < n; ++i) { |
56 check(data1[i] == data2[i], "Test failed"); |
58 check(data1[i] == data2[i], "Test failed"); |
73 } |
75 } |
74 } { |
76 } { |
75 int n = 10000; |
77 int n = 10000; |
76 vector<unsigned char> data1(n), data2(n); |
78 vector<unsigned char> data1(n), data2(n); |
77 for (int i = 0; i < n; ++i) { |
79 for (int i = 0; i < n; ++i) { |
78 data1[i] = data2[i] = rnd[(unsigned char)200]; |
80 data1[i] = data2[i] = rnd[uchar(200)]; |
79 } |
81 } |
80 counterSort(data1.begin(), data1.end()); |
82 counterSort(data1.begin(), data1.end()); |
81 sort(data2.begin(), data2.end()); |
83 sort(data2.begin(), data2.end()); |
82 for (int i = 0; i < n; ++i) { |
84 for (int i = 0; i < n; ++i) { |
83 check(data1[i] == data2[i], "Test failed"); |
85 check(data1[i] == data2[i], "Test failed"); |
94 typedef SmartGraph Graph; |
96 typedef SmartGraph Graph; |
95 typedef Graph::Node Node; |
97 typedef Graph::Node Node; |
96 typedef Graph::Edge Edge; |
98 typedef Graph::Edge Edge; |
97 |
99 |
98 const int n = 100; |
100 const int n = 100; |
99 const int e = (int)(n * log((double)n)); |
101 const int e = int(n * log(double(n))); |
100 |
102 |
101 Graph graph; |
103 Graph graph; |
102 vector<Node> nodes; |
104 vector<Node> nodes; |
103 |
105 |
104 for (int i = 0; i < n; ++i) { |
106 for (int i = 0; i < n; ++i) { |
115 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
117 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
116 sourceMap(graph)))); |
118 sourceMap(graph)))); |
117 |
119 |
118 Graph::EdgeMap<bool> was(graph, false); |
120 Graph::EdgeMap<bool> was(graph, false); |
119 |
121 |
120 for (int i = 0; i < (int)edges.size(); ++i) { |
122 for (int i = 0; i < int(edges.size()); ++i) { |
121 check(!was[edges[i]], "Test failed"); |
123 check(!was[edges[i]], "Test failed"); |
122 was[edges[i]] = true; |
124 was[edges[i]] = true; |
123 } |
125 } |
124 |
126 |
125 for (int i = 1; i < (int)edges.size(); ++i) { |
127 for (int i = 1; i < int(edges.size()); ++i) { |
126 check(graph.id(graph.source(edges[i - 1])) <= |
128 check(graph.id(graph.source(edges[i - 1])) <= |
127 graph.id(graph.source(edges[i])), "Test failed"); |
129 graph.id(graph.source(edges[i])), "Test failed"); |
128 } |
130 } |
129 |
131 |
130 } |
132 } |
133 typedef SmartGraph Graph; |
135 typedef SmartGraph Graph; |
134 typedef Graph::Node Node; |
136 typedef Graph::Node Node; |
135 typedef Graph::Edge Edge; |
137 typedef Graph::Edge Edge; |
136 |
138 |
137 const int n = 100; |
139 const int n = 100; |
138 const int e = (int)(n * log((double)n)); |
140 const int e = int(n * log(double(n))); |
139 |
141 |
140 Graph graph; |
142 Graph graph; |
141 vector<Node> nodes; |
143 vector<Node> nodes; |
142 |
144 |
143 for (int i = 0; i < n; ++i) { |
145 for (int i = 0; i < n; ++i) { |
158 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
160 mapFunctor(composeMap(IdMap<Graph, Node>(graph), |
159 targetMap(graph)))); |
161 targetMap(graph)))); |
160 |
162 |
161 Graph::EdgeMap<bool> was(graph, false); |
163 Graph::EdgeMap<bool> was(graph, false); |
162 |
164 |
163 for (int i = 0; i < (int)edges.size(); ++i) { |
165 for (int i = 0; i < int(edges.size()); ++i) { |
164 check(!was[edges[i]], "Test failed"); |
166 check(!was[edges[i]], "Test failed"); |
165 was[edges[i]] = true; |
167 was[edges[i]] = true; |
166 } |
168 } |
167 |
169 |
168 for (int i = 1; i < (int)edges.size(); ++i) { |
170 for (int i = 1; i < int(edges.size()); ++i) { |
169 check(graph.id(graph.target(edges[i - 1])) < |
171 check(graph.id(graph.target(edges[i - 1])) < |
170 graph.id(graph.target(edges[i])) || |
172 graph.id(graph.target(edges[i])) || |
171 (graph.id(graph.target(edges[i - 1])) == |
173 (graph.id(graph.target(edges[i - 1])) == |
172 graph.id(graph.target(edges[i])) && |
174 graph.id(graph.target(edges[i])) && |
173 graph.id(graph.source(edges[i - 1])) <= |
175 graph.id(graph.source(edges[i - 1])) <= |