test/radix_sort_test.cc
author alpar
Tue, 31 Jan 2006 20:16:53 +0000
changeset 1935 67b38d699ea7
parent 1833 6d107b0b6b46
child 1956 a055123339d5
permissions -rw-r--r--
Spellcheck
deba@1833
     1
#include <lemon/time_measure.h>
deba@1833
     2
#include <lemon/smart_graph.h>
deba@1833
     3
#include <lemon/graph_utils.h>
deba@1833
     4
#include <lemon/maps.h>
deba@1833
     5
#include <lemon/radix_sort.h>
deba@1833
     6
deba@1833
     7
#include "test_tools.h"
deba@1833
     8
deba@1833
     9
deba@1833
    10
#include <vector>
deba@1833
    11
#include <algorithm>
deba@1833
    12
#include <cmath>
deba@1833
    13
deba@1833
    14
using namespace std;
deba@1833
    15
using namespace lemon;
deba@1833
    16
deba@1833
    17
void checkRadixSort() {
deba@1844
    18
  {
deba@1844
    19
    int n = 10000;
deba@1844
    20
    vector<int> data1(n), data2(n);
deba@1844
    21
    for (int i = 0; i < n; ++i) {
deba@1844
    22
      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
deba@1844
    23
    }
deba@1844
    24
    radixSort(data1.begin(), data1.end());
deba@1844
    25
    sort(data2.begin(), data2.end());
deba@1844
    26
    for (int i = 0; i < n; ++i) {
deba@1844
    27
      check(data1[i] == data2[i], "Test failed");
deba@1844
    28
    }
deba@1844
    29
  } {
deba@1844
    30
    int n = 10000;
deba@1844
    31
    vector<unsigned char> data1(n), data2(n);
deba@1844
    32
    for (int i = 0; i < n; ++i) {
deba@1844
    33
      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
deba@1844
    34
    }
deba@1844
    35
    radixSort(data1.begin(), data1.end());
deba@1844
    36
    sort(data2.begin(), data2.end());
deba@1844
    37
    for (int i = 0; i < n; ++i) {
deba@1844
    38
      check(data1[i] == data2[i], "Test failed");
deba@1844
    39
    }
deba@1833
    40
  }
deba@1833
    41
}
deba@1833
    42
deba@1833
    43
deba@1833
    44
void checkCounterSort() {
deba@1844
    45
  {
deba@1844
    46
    int n = 10000;
deba@1844
    47
    vector<int> data1(n), data2(n);
deba@1844
    48
    for (int i = 0; i < n; ++i) {
deba@1844
    49
      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
deba@1844
    50
    }
deba@1844
    51
    counterSort(data1.begin(), data1.end());
deba@1844
    52
    sort(data2.begin(), data2.end());
deba@1844
    53
    for (int i = 0; i < n; ++i) {
deba@1844
    54
      check(data1[i] == data2[i], "Test failed");
deba@1844
    55
    } 
deba@1844
    56
  } {
deba@1844
    57
    int n = 10000;
deba@1844
    58
    vector<unsigned char> data1(n), data2(n);
deba@1844
    59
    for (int i = 0; i < n; ++i) {
deba@1844
    60
      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
deba@1844
    61
    }
deba@1844
    62
    counterSort(data1.begin(), data1.end());
deba@1844
    63
    sort(data2.begin(), data2.end());
deba@1844
    64
    for (int i = 0; i < n; ++i) {
deba@1844
    65
      check(data1[i] == data2[i], "Test failed");
deba@1844
    66
    } 
deba@1833
    67
  }
deba@1833
    68
}
deba@1833
    69
deba@1833
    70
void checkSorts() {
deba@1833
    71
  checkRadixSort();
deba@1833
    72
  checkCounterSort();
deba@1833
    73
}
deba@1833
    74
deba@1833
    75
void checkGraphRadixSort() {
deba@1833
    76
  typedef SmartGraph Graph;
deba@1833
    77
  typedef Graph::Node Node;
deba@1833
    78
  typedef Graph::Edge Edge;
deba@1833
    79
deba@1833
    80
  const int n = 100;
deba@1833
    81
  const int e = (int)(n * log((double)n));
deba@1833
    82
deba@1833
    83
  Graph graph;
deba@1833
    84
  vector<Node> nodes;
deba@1833
    85
deba@1833
    86
  for (int i = 0; i < n; ++i) {
deba@1833
    87
    nodes.push_back(graph.addNode());
deba@1833
    88
  }
deba@1833
    89
  vector<Edge> edges;
deba@1833
    90
  for (int i = 0; i < e; ++i) {
deba@1833
    91
    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@1833
    92
    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@1833
    93
    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
deba@1833
    94
  }
deba@1833
    95
deba@1833
    96
  radixSort(edges.begin(), edges.end(), 
deba@1833
    97
	    mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
deba@1833
    98
				  sourceMap(graph))));
deba@1833
    99
deba@1833
   100
  Graph::EdgeMap<bool> was(graph, false);
deba@1833
   101
deba@1833
   102
  for (int i = 0; i < (int)edges.size(); ++i) {
deba@1833
   103
    check(!was[edges[i]], "Test failed");
deba@1833
   104
    was[edges[i]] = true;
deba@1833
   105
  }
deba@1833
   106
deba@1833
   107
  for (int i = 1; i < (int)edges.size(); ++i) {
deba@1833
   108
    check(graph.id(graph.source(edges[i - 1])) <= 
deba@1833
   109
	  graph.id(graph.source(edges[i])), "Test failed");
deba@1833
   110
  }
deba@1833
   111
deba@1833
   112
}
deba@1833
   113
deba@1833
   114
void checkGraphCounterSort() {
deba@1833
   115
  typedef SmartGraph Graph;
deba@1833
   116
  typedef Graph::Node Node;
deba@1833
   117
  typedef Graph::Edge Edge;
deba@1833
   118
deba@1833
   119
  const int n = 100;
deba@1833
   120
  const int e = (int)(n * log((double)n));
deba@1833
   121
deba@1833
   122
  Graph graph;
deba@1833
   123
  vector<Node> nodes;
deba@1833
   124
deba@1833
   125
  for (int i = 0; i < n; ++i) {
deba@1833
   126
    nodes.push_back(graph.addNode());
deba@1833
   127
  }
deba@1833
   128
  vector<Edge> edges;
deba@1833
   129
  for (int i = 0; i < e; ++i) {
deba@1833
   130
    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@1833
   131
    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
deba@1833
   132
    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
deba@1833
   133
  }
deba@1833
   134
deba@1833
   135
  counterSort(edges.begin(), edges.end(), 
deba@1833
   136
	      mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
deba@1833
   137
				    sourceMap(graph))));
deba@1833
   138
deba@1833
   139
  counterSort(edges.begin(), edges.end(), 
deba@1833
   140
	      mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
deba@1833
   141
				    targetMap(graph))));
deba@1833
   142
deba@1833
   143
  Graph::EdgeMap<bool> was(graph, false);
deba@1833
   144
deba@1833
   145
  for (int i = 0; i < (int)edges.size(); ++i) {
deba@1833
   146
    check(!was[edges[i]], "Test failed");
deba@1833
   147
    was[edges[i]] = true;
deba@1833
   148
  }
deba@1833
   149
deba@1833
   150
  for (int i = 1; i < (int)edges.size(); ++i) {
deba@1833
   151
    check(graph.id(graph.target(edges[i - 1])) < 
deba@1833
   152
	  graph.id(graph.target(edges[i])) || 
deba@1833
   153
	  (graph.id(graph.target(edges[i - 1])) ==
deba@1833
   154
	   graph.id(graph.target(edges[i])) &&
deba@1833
   155
	   graph.id(graph.source(edges[i - 1])) <= 
deba@1833
   156
	   graph.id(graph.source(edges[i]))), "Test failed");
deba@1833
   157
  }
deba@1833
   158
deba@1833
   159
}
deba@1833
   160
deba@1833
   161
void checkGraphSorts() {
deba@1833
   162
  checkGraphRadixSort();
deba@1833
   163
  checkGraphCounterSort();
deba@1833
   164
}
deba@1833
   165
deba@1833
   166
int main() {
deba@1833
   167
  checkSorts();
deba@1833
   168
  checkGraphSorts();
deba@1833
   169
  return 0;
deba@1833
   170
}