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 hegyi
Thu, 05 Jan 2006 12:30:09 +0000
changeset 1878 409a31271efd
parent 1833 6d107b0b6b46
child 1956 a055123339d5
permissions -rw-r--r--
Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox. 
     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   {

    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 }

    42 

    43 

    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 }

    69 

    70 void checkSorts() {

    71   checkRadixSort();

    72   checkCounterSort();

    73 }

    74 

    75 void checkGraphRadixSort() {

    76   typedef SmartGraph Graph;

    77   typedef Graph::Node Node;

    78   typedef Graph::Edge Edge;

    79 

    80   const int n = 100;

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

    82 

    83   Graph graph;

    84   vector<Node> nodes;

    85 

    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   }

    95 

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

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

    98 				  sourceMap(graph))));

    99 

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

   101 

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

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

   104     was[edges[i]] = true;

   105   }

   106 

   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   }

   111 

   112 }

   113 

   114 void checkGraphCounterSort() {

   115   typedef SmartGraph Graph;

   116   typedef Graph::Node Node;

   117   typedef Graph::Edge Edge;

   118 

   119   const int n = 100;

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

   121 

   122   Graph graph;

   123   vector<Node> nodes;

   124 

   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   }

   134 

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

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

   137 				    sourceMap(graph))));

   138 

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

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

   141 				    targetMap(graph))));

   142 

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

   144 

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

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

   147     was[edges[i]] = true;

   148   }

   149 

   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   }

   158 

   159 }

   160 

   161 void checkGraphSorts() {

   162   checkGraphRadixSort();

   163   checkGraphCounterSort();

   164 }

   165 

   166 int main() {

   167   checkSorts();

   168   checkGraphSorts();

   169   return 0;

   170 }
lemon-0.x