lemon-0.x: test/radix_sort_test.cc@a4d1362397fe

     1 #include <lemon/time_measure.h>

     2 #include <lemon/smart_graph.h>

     3 #include <lemon/graph_utils.h>

     4 #include <lemon/maps.h>

     5 #include <lemon/radix_sort.h>

     7 #include "test_tools.h"

    10 #include <vector>

    11 #include <algorithm>

    12 #include <cmath>

    14 using namespace std;

    15 using namespace lemon;

    17 void checkRadixSort() {

    18   {

    19     int n = 10000;

    20     vector<int> data1(n), data2(n);

    21     for (int i = 0; i < n; ++i) {

    22       data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;

    23     }

    24     radixSort(data1.begin(), data1.end());

    25     sort(data2.begin(), data2.end());

    26     for (int i = 0; i < n; ++i) {

    27       check(data1[i] == data2[i], "Test failed");

    28     }

    29   } {

    30     int n = 10000;

    31     vector<unsigned char> data1(n), data2(n);

    32     for (int i = 0; i < n; ++i) {

    33       data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));

    34     }

    35     radixSort(data1.begin(), data1.end());

    36     sort(data2.begin(), data2.end());

    37     for (int i = 0; i < n; ++i) {

    38       check(data1[i] == data2[i], "Test failed");

    39     }

    40   }

    41 }

    44 void checkCounterSort() {

    45   {

    46     int n = 10000;

    47     vector<int> data1(n), data2(n);

    48     for (int i = 0; i < n; ++i) {

    49       data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;

    50     }

    51     counterSort(data1.begin(), data1.end());

    52     sort(data2.begin(), data2.end());

    53     for (int i = 0; i < n; ++i) {

    54       check(data1[i] == data2[i], "Test failed");

    55     }

    56   } {

    57     int n = 10000;

    58     vector<unsigned char> data1(n), data2(n);

    59     for (int i = 0; i < n; ++i) {

    60       data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));

    61     }

    62     counterSort(data1.begin(), data1.end());

    63     sort(data2.begin(), data2.end());

    64     for (int i = 0; i < n; ++i) {

    65       check(data1[i] == data2[i], "Test failed");

    66     }

    67   }

    68 }

    70 void checkSorts() {

    71   checkRadixSort();

    72   checkCounterSort();

    73 }

    75 void checkGraphRadixSort() {

    76   typedef SmartGraph Graph;

    77   typedef Graph::Node Node;

    78   typedef Graph::Edge Edge;

    80   const int n = 100;

    81   const int e = (int)(n * log((double)n));

    83   Graph graph;

    84   vector<Node> nodes;

    86   for (int i = 0; i < n; ++i) {

    87     nodes.push_back(graph.addNode());

    88   }

    89   vector<Edge> edges;

    90   for (int i = 0; i < e; ++i) {

    91     int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));

    92     int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));

    93     edges.push_back(graph.addEdge(nodes[s], nodes[t]));

    94   }

    96   radixSort(edges.begin(), edges.end(),

    97 	    mapFunctor(composeMap(IdMap<Graph, Node>(graph),

    98 				  sourceMap(graph))));

   100   Graph::EdgeMap<bool> was(graph, false);

   102   for (int i = 0; i < (int)edges.size(); ++i) {

   103     check(!was[edges[i]], "Test failed");

   104     was[edges[i]] = true;

   105   }

   107   for (int i = 1; i < (int)edges.size(); ++i) {

   108     check(graph.id(graph.source(edges[i - 1])) <=

   109 	  graph.id(graph.source(edges[i])), "Test failed");

   110   }

   112 }

   114 void checkGraphCounterSort() {

   115   typedef SmartGraph Graph;

   116   typedef Graph::Node Node;

   117   typedef Graph::Edge Edge;

   119   const int n = 100;

   120   const int e = (int)(n * log((double)n));

   122   Graph graph;

   123   vector<Node> nodes;

   125   for (int i = 0; i < n; ++i) {

   126     nodes.push_back(graph.addNode());

   127   }

   128   vector<Edge> edges;

   129   for (int i = 0; i < e; ++i) {

   130     int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));

   131     int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));

   132     edges.push_back(graph.addEdge(nodes[s], nodes[t]));

   133   }

   135   counterSort(edges.begin(), edges.end(),

   136 	      mapFunctor(composeMap(IdMap<Graph, Node>(graph),

   137 				    sourceMap(graph))));

   139   counterSort(edges.begin(), edges.end(),

   140 	      mapFunctor(composeMap(IdMap<Graph, Node>(graph),

   141 				    targetMap(graph))));

   143   Graph::EdgeMap<bool> was(graph, false);

   145   for (int i = 0; i < (int)edges.size(); ++i) {

   146     check(!was[edges[i]], "Test failed");

   147     was[edges[i]] = true;

   148   }

   150   for (int i = 1; i < (int)edges.size(); ++i) {

   151     check(graph.id(graph.target(edges[i - 1])) <

   152 	  graph.id(graph.target(edges[i])) ||

   153 	  (graph.id(graph.target(edges[i - 1])) ==

   154 	   graph.id(graph.target(edges[i])) &&

   155 	   graph.id(graph.source(edges[i - 1])) <=

   156 	   graph.id(graph.source(edges[i]))), "Test failed");

   157   }

   159 }

   161 void checkGraphSorts() {

   162   checkGraphRadixSort();

   163   checkGraphCounterSort();

   164 }

   166 int main() {

   167   checkSorts();

   168   checkGraphSorts();

   169   return 0;

   170 }

author	hegyi
	Tue, 06 Dec 2005 10:53:38 +0000
changeset 1849	a4d1362397fe
parent 1833	6d107b0b6b46
child 1956	a055123339d5
permissions	-rw-r--r--