/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2007

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

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

typedef unsigned char uchar;

void checkRadixSort() {

  {

    int n = 10000;

    vector<int> data1(n), data2(n);

    for (int i = 0; i < n; ++i) {

      data1[i] = data2[i] = rnd[1000] - 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");

    }

  } {

    int n = 10000;

    vector<unsigned char> data1(n), data2(n);

    for (int i = 0; i < n; ++i) {

      data1[i] = data2[i] = rnd[uchar(200)];

    }

    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] = rnd[1000] - 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");

    } 

  } {

    int n = 10000;

    vector<unsigned char> data1(n), data2(n);

    for (int i = 0; i < n; ++i) {

      data1[i] = data2[i] = rnd[uchar(200)];

    }

    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 = rnd[n];

    int t = rnd[n];

    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 = rnd[n];

    int t = rnd[n];

    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;

}