source: lemon-0.x/test/radix_sort_test.cc @ 1841:a2dfee683243

#include <lemon/time_measure.h>
#include <lemon/smart_graph.h>
#include <lemon/graph_utils.h>
#include <lemon/maps.h>
#include <lemon/radix_sort.h>

#include "test_tools.h"


#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
using namespace lemon;

void checkRadixSort() {
  int n = 10000;
  vector<int> data1(n), data2(n);
  for (int i = 0; i < n; ++i) {
    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
  }
  radixSort(data1.begin(), data1.end());
  sort(data2.begin(), data2.end());
  for (int i = 0; i < n; ++i) {
    check(data1[i] == data2[i], "Test failed");
  }
}


void checkCounterSort() {
  int n = 10000;
  vector<int> data1(n), data2(n);
  for (int i = 0; i < n; ++i) {
    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
  }
  counterSort(data1.begin(), data1.end());
  sort(data2.begin(), data2.end());
  for (int i = 0; i < n; ++i) {
    check(data1[i] == data2[i], "Test failed");
  }
}

void checkSorts() {
  checkRadixSort();
  checkCounterSort();
}

void checkGraphRadixSort() {
  typedef SmartGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::Edge Edge;

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

  Graph graph;
  vector<Node> nodes;

  for (int i = 0; i < n; ++i) {
    nodes.push_back(graph.addNode());
  }
  vector<Edge> edges;
  for (int i = 0; i < e; ++i) {
    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
  }

  radixSort(edges.begin(), edges.end(), 
            mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
                                  sourceMap(graph))));

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

  for (int i = 0; i < (int)edges.size(); ++i) {
    check(!was[edges[i]], "Test failed");
    was[edges[i]] = true;
  }

  for (int i = 1; i < (int)edges.size(); ++i) {
    check(graph.id(graph.source(edges[i - 1])) <= 
          graph.id(graph.source(edges[i])), "Test failed");
  }

}

void checkGraphCounterSort() {
  typedef SmartGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::Edge Edge;

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

  Graph graph;
  vector<Node> nodes;

  for (int i = 0; i < n; ++i) {
    nodes.push_back(graph.addNode());
  }
  vector<Edge> edges;
  for (int i = 0; i < e; ++i) {
    int s = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    int t = (int)(n * (double)rand() / (RAND_MAX + 1.0));
    edges.push_back(graph.addEdge(nodes[s], nodes[t]));
  }

  counterSort(edges.begin(), edges.end(), 
              mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
                                    sourceMap(graph))));

  counterSort(edges.begin(), edges.end(), 
              mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
                                    targetMap(graph))));

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

  for (int i = 0; i < (int)edges.size(); ++i) {
    check(!was[edges[i]], "Test failed");
    was[edges[i]] = true;
  }

  for (int i = 1; i < (int)edges.size(); ++i) {
    check(graph.id(graph.target(edges[i - 1])) < 
          graph.id(graph.target(edges[i])) || 
          (graph.id(graph.target(edges[i - 1])) ==
           graph.id(graph.target(edges[i])) &&
           graph.id(graph.source(edges[i - 1])) <= 
           graph.id(graph.source(edges[i]))), "Test failed");
  }

}

void checkGraphSorts() {
  checkGraphRadixSort();
  checkGraphCounterSort();
}

int main() {
  checkSorts();
  checkGraphSorts();
  return 0;
}