Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/radix_sort_test.cc
author alpar
Fri, 02 Dec 2005 10:02:40 +0000
changeset 1843 1e386f4047c9
child 1844 eaa5f5b855f7
permissions -rw-r--r--
bugfix 
     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>

     6 

     7 #include "test_tools.h"

     8 

     9 

    10 #include <vector>

    11 #include <algorithm>

    12 #include <cmath>

    13 

    14 using namespace std;

    15 using namespace lemon;

    16 

    17 void checkRadixSort() {

    18   int n = 10000;

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

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

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

    22   }

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

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

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

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

    27   }

    28 }

    29 

    30 

    31 void checkCounterSort() {

    32   int n = 10000;

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

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

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

    36   }

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

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

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

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

    41   }

    42 }

    43 

    44 void checkSorts() {

    45   checkRadixSort();

    46   checkCounterSort();

    47 }

    48 

    49 void checkGraphRadixSort() {

    50   typedef SmartGraph Graph;

    51   typedef Graph::Node Node;

    52   typedef Graph::Edge Edge;

    53 

    54   const int n = 100;

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

    56 

    57   Graph graph;

    58   vector<Node> nodes;

    59 

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

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

    62   }

    63   vector<Edge> edges;

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

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

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

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

    68   }

    69 

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

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

    72 				  sourceMap(graph))));

    73 

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

    75 

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

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

    78     was[edges[i]] = true;

    79   }

    80 

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

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

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

    84   }

    85 

    86 }

    87 

    88 void checkGraphCounterSort() {

    89   typedef SmartGraph Graph;

    90   typedef Graph::Node Node;

    91   typedef Graph::Edge Edge;

    92 

    93   const int n = 100;

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

    95 

    96   Graph graph;

    97   vector<Node> nodes;

    98 

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

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

   101   }

   102   vector<Edge> edges;

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

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

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

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

   107   }

   108 

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

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

   111 				    sourceMap(graph))));

   112 

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

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

   115 				    targetMap(graph))));

   116 

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

   118 

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

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

   121     was[edges[i]] = true;

   122   }

   123 

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

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

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

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

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

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

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

   131   }

   132 

   133 }

   134 

   135 void checkGraphSorts() {

   136   checkGraphRadixSort();

   137   checkGraphCounterSort();

   138 }

   139 

   140 int main() {

   141   checkSorts();

   142   checkGraphSorts();

   143   return 0;

   144 }
lemon-0.x