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 deba
Mon, 19 Dec 2005 09:43:13 +0000
changeset 1864 1788205e36af
parent 1833 6d107b0b6b46
child 1956 a055123339d5
permissions -rw-r--r--
Fixing Bellman's name 
     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