/* -*- 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;

 }