# source:lemon-0.x/test/radix_sort_test.cc

Last change on this file was 2569:12c2c5c4330b, checked in by Alpar Juttner, 15 years ago

#include<cmath> -> #include<lemon/math.h>

File size: 4.5 KB
Line
1/* -*- C++ -*-
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 */
18
19#include <lemon/time_measure.h>
20#include <lemon/smart_graph.h>
21#include <lemon/graph_utils.h>
22#include <lemon/maps.h>
23#include <lemon/radix_sort.h>
24
25#include "test_tools.h"
26
27
28#include <vector>
29#include <algorithm>
30#include <lemon/math.h>
31
32using namespace std;
33using namespace lemon;
34
35typedef unsigned char uchar;
36
37void checkRadixSort() {
38  {
39    int n = 10000;
40    vector<int> data1(n), data2(n);
41    for (int i = 0; i < n; ++i) {
42      data1[i] = data2[i] = rnd[1000] - 500;
43    }
44    radixSort(data1.begin(), data1.end());
45    sort(data2.begin(), data2.end());
46    for (int i = 0; i < n; ++i) {
47      check(data1[i] == data2[i], "Test failed");
48    }
49  } {
50    int n = 10000;
51    vector<unsigned char> data1(n), data2(n);
52    for (int i = 0; i < n; ++i) {
53      data1[i] = data2[i] = rnd[uchar(200)];
54    }
55    radixSort(data1.begin(), data1.end());
56    sort(data2.begin(), data2.end());
57    for (int i = 0; i < n; ++i) {
58      check(data1[i] == data2[i], "Test failed");
59    }
60  }
61}
62
63
64void checkCounterSort() {
65  {
66    int n = 10000;
67    vector<int> data1(n), data2(n);
68    for (int i = 0; i < n; ++i) {
69      data1[i] = data2[i] = rnd[1000] - 500;
70    }
71    counterSort(data1.begin(), data1.end());
72    sort(data2.begin(), data2.end());
73    for (int i = 0; i < n; ++i) {
74      check(data1[i] == data2[i], "Test failed");
75    }
76  } {
77    int n = 10000;
78    vector<unsigned char> data1(n), data2(n);
79    for (int i = 0; i < n; ++i) {
80      data1[i] = data2[i] = rnd[uchar(200)];
81    }
82    counterSort(data1.begin(), data1.end());
83    sort(data2.begin(), data2.end());
84    for (int i = 0; i < n; ++i) {
85      check(data1[i] == data2[i], "Test failed");
86    }
87  }
88}
89
90void checkSorts() {
91  checkRadixSort();
92  checkCounterSort();
93}
94
95void checkGraphRadixSort() {
96  typedef SmartGraph Graph;
97  typedef Graph::Node Node;
98  typedef Graph::Edge Edge;
99
100  const int n = 100;
101  const int e = int(n * log(double(n)));
102
103  Graph graph;
104  vector<Node> nodes;
105
106  for (int i = 0; i < n; ++i) {
107    nodes.push_back(graph.addNode());
108  }
109  vector<Edge> edges;
110  for (int i = 0; i < e; ++i) {
111    int s = rnd[n];
112    int t = rnd[n];
113    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
114  }
115
116  radixSort(edges.begin(), edges.end(),
117            mapFunctor(composeMap(IdMap<Graph, Node>(graph),
118                                  sourceMap(graph))));
119
120  Graph::EdgeMap<bool> was(graph, false);
121
122  for (int i = 0; i < int(edges.size()); ++i) {
123    check(!was[edges[i]], "Test failed");
124    was[edges[i]] = true;
125  }
126
127  for (int i = 1; i < int(edges.size()); ++i) {
128    check(graph.id(graph.source(edges[i - 1])) <=
129          graph.id(graph.source(edges[i])), "Test failed");
130  }
131
132}
133
134void checkGraphCounterSort() {
135  typedef SmartGraph Graph;
136  typedef Graph::Node Node;
137  typedef Graph::Edge Edge;
138
139  const int n = 100;
140  const int e = int(n * log(double(n)));
141
142  Graph graph;
143  vector<Node> nodes;
144
145  for (int i = 0; i < n; ++i) {
146    nodes.push_back(graph.addNode());
147  }
148  vector<Edge> edges;
149  for (int i = 0; i < e; ++i) {
150    int s = rnd[n];
151    int t = rnd[n];
152    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
153  }
154
155  counterSort(edges.begin(), edges.end(),
156              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
157                                    sourceMap(graph))));
158
159  counterSort(edges.begin(), edges.end(),
160              mapFunctor(composeMap(IdMap<Graph, Node>(graph),
161                                    targetMap(graph))));
162
163  Graph::EdgeMap<bool> was(graph, false);
164
165  for (int i = 0; i < int(edges.size()); ++i) {
166    check(!was[edges[i]], "Test failed");
167    was[edges[i]] = true;
168  }
169
170  for (int i = 1; i < int(edges.size()); ++i) {
171    check(graph.id(graph.target(edges[i - 1])) <
172          graph.id(graph.target(edges[i])) ||
173          (graph.id(graph.target(edges[i - 1])) ==
174           graph.id(graph.target(edges[i])) &&
175           graph.id(graph.source(edges[i - 1])) <=
176           graph.id(graph.source(edges[i]))), "Test failed");
177  }
178
179}
180
181void checkGraphSorts() {
182  checkGraphRadixSort();
183  checkGraphCounterSort();
184}
185
186int main() {
187  checkSorts();
188  checkGraphSorts();
189  return 0;
190}
Note: See TracBrowser for help on using the repository browser.