#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;

}