alpar@1956: /* -*- C++ -*-
alpar@1956:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1956:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@1956:  *
alpar@1956:  * Permission to use, modify and distribute this software is granted
alpar@1956:  * provided that this copyright notice appears in all copies. For
alpar@1956:  * precise terms see the accompanying LICENSE file.
alpar@1956:  *
alpar@1956:  * This software is provided "AS IS" with no warranty of any kind,
alpar@1956:  * express or implied, and with no claim as to its suitability for any
alpar@1956:  * purpose.
alpar@1956:  *
alpar@1956:  */
alpar@1956: 
deba@1833: #include <lemon/time_measure.h>
deba@1833: #include <lemon/smart_graph.h>
deba@1833: #include <lemon/graph_utils.h>
deba@1833: #include <lemon/maps.h>
deba@1833: #include <lemon/radix_sort.h>
deba@1833: 
deba@1833: #include "test_tools.h"
deba@1833: 
deba@1833: 
deba@1833: #include <vector>
deba@1833: #include <algorithm>
deba@1833: #include <cmath>
deba@1833: 
deba@1833: using namespace std;
deba@1833: using namespace lemon;
deba@1833: 
deba@2386: typedef unsigned char uchar;
deba@2386: 
deba@1833: void checkRadixSort() {
deba@1844:   {
deba@1844:     int n = 10000;
deba@1844:     vector<int> data1(n), data2(n);
deba@1844:     for (int i = 0; i < n; ++i) {
deba@2242:       data1[i] = data2[i] = rnd[1000] - 500;
deba@1844:     }
deba@1844:     radixSort(data1.begin(), data1.end());
deba@1844:     sort(data2.begin(), data2.end());
deba@1844:     for (int i = 0; i < n; ++i) {
deba@1844:       check(data1[i] == data2[i], "Test failed");
deba@1844:     }
deba@1844:   } {
deba@1844:     int n = 10000;
deba@1844:     vector<unsigned char> data1(n), data2(n);
deba@1844:     for (int i = 0; i < n; ++i) {
deba@2386:       data1[i] = data2[i] = rnd[uchar(200)];
deba@1844:     }
deba@1844:     radixSort(data1.begin(), data1.end());
deba@1844:     sort(data2.begin(), data2.end());
deba@1844:     for (int i = 0; i < n; ++i) {
deba@1844:       check(data1[i] == data2[i], "Test failed");
deba@1844:     }
deba@1833:   }
deba@1833: }
deba@1833: 
deba@1833: 
deba@1833: void checkCounterSort() {
deba@1844:   {
deba@1844:     int n = 10000;
deba@1844:     vector<int> data1(n), data2(n);
deba@1844:     for (int i = 0; i < n; ++i) {
deba@2242:       data1[i] = data2[i] = rnd[1000] - 500;
deba@1844:     }
deba@1844:     counterSort(data1.begin(), data1.end());
deba@1844:     sort(data2.begin(), data2.end());
deba@1844:     for (int i = 0; i < n; ++i) {
deba@1844:       check(data1[i] == data2[i], "Test failed");
deba@1844:     } 
deba@1844:   } {
deba@1844:     int n = 10000;
deba@1844:     vector<unsigned char> data1(n), data2(n);
deba@1844:     for (int i = 0; i < n; ++i) {
deba@2386:       data1[i] = data2[i] = rnd[uchar(200)];
deba@1844:     }
deba@1844:     counterSort(data1.begin(), data1.end());
deba@1844:     sort(data2.begin(), data2.end());
deba@1844:     for (int i = 0; i < n; ++i) {
deba@1844:       check(data1[i] == data2[i], "Test failed");
deba@1844:     } 
deba@1833:   }
deba@1833: }
deba@1833: 
deba@1833: void checkSorts() {
deba@1833:   checkRadixSort();
deba@1833:   checkCounterSort();
deba@1833: }
deba@1833: 
deba@1833: void checkGraphRadixSort() {
deba@1833:   typedef SmartGraph Graph;
deba@1833:   typedef Graph::Node Node;
deba@1833:   typedef Graph::Edge Edge;
deba@1833: 
deba@1833:   const int n = 100;
deba@2386:   const int e = int(n * log(double(n)));
deba@1833: 
deba@1833:   Graph graph;
deba@1833:   vector<Node> nodes;
deba@1833: 
deba@1833:   for (int i = 0; i < n; ++i) {
deba@1833:     nodes.push_back(graph.addNode());
deba@1833:   }
deba@1833:   vector<Edge> edges;
deba@1833:   for (int i = 0; i < e; ++i) {
deba@2242:     int s = rnd[n];
deba@2242:     int t = rnd[n];
deba@1833:     edges.push_back(graph.addEdge(nodes[s], nodes[t]));
deba@1833:   }
deba@1833: 
deba@1833:   radixSort(edges.begin(), edges.end(), 
deba@1833: 	    mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
deba@1833: 				  sourceMap(graph))));
deba@1833: 
deba@1833:   Graph::EdgeMap<bool> was(graph, false);
deba@1833: 
deba@2386:   for (int i = 0; i < int(edges.size()); ++i) {
deba@1833:     check(!was[edges[i]], "Test failed");
deba@1833:     was[edges[i]] = true;
deba@1833:   }
deba@1833: 
deba@2386:   for (int i = 1; i < int(edges.size()); ++i) {
deba@1833:     check(graph.id(graph.source(edges[i - 1])) <= 
deba@1833: 	  graph.id(graph.source(edges[i])), "Test failed");
deba@1833:   }
deba@1833: 
deba@1833: }
deba@1833: 
deba@1833: void checkGraphCounterSort() {
deba@1833:   typedef SmartGraph Graph;
deba@1833:   typedef Graph::Node Node;
deba@1833:   typedef Graph::Edge Edge;
deba@1833: 
deba@1833:   const int n = 100;
deba@2386:   const int e = int(n * log(double(n)));
deba@1833: 
deba@1833:   Graph graph;
deba@1833:   vector<Node> nodes;
deba@1833: 
deba@1833:   for (int i = 0; i < n; ++i) {
deba@1833:     nodes.push_back(graph.addNode());
deba@1833:   }
deba@1833:   vector<Edge> edges;
deba@1833:   for (int i = 0; i < e; ++i) {
deba@2242:     int s = rnd[n];
deba@2242:     int t = rnd[n];
deba@1833:     edges.push_back(graph.addEdge(nodes[s], nodes[t]));
deba@1833:   }
deba@1833: 
deba@1833:   counterSort(edges.begin(), edges.end(), 
deba@1833: 	      mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
deba@1833: 				    sourceMap(graph))));
deba@1833: 
deba@1833:   counterSort(edges.begin(), edges.end(), 
deba@1833: 	      mapFunctor(composeMap(IdMap<Graph, Node>(graph), 
deba@1833: 				    targetMap(graph))));
deba@1833: 
deba@1833:   Graph::EdgeMap<bool> was(graph, false);
deba@1833: 
deba@2386:   for (int i = 0; i < int(edges.size()); ++i) {
deba@1833:     check(!was[edges[i]], "Test failed");
deba@1833:     was[edges[i]] = true;
deba@1833:   }
deba@1833: 
deba@2386:   for (int i = 1; i < int(edges.size()); ++i) {
deba@1833:     check(graph.id(graph.target(edges[i - 1])) < 
deba@1833: 	  graph.id(graph.target(edges[i])) || 
deba@1833: 	  (graph.id(graph.target(edges[i - 1])) ==
deba@1833: 	   graph.id(graph.target(edges[i])) &&
deba@1833: 	   graph.id(graph.source(edges[i - 1])) <= 
deba@1833: 	   graph.id(graph.source(edges[i]))), "Test failed");
deba@1833:   }
deba@1833: 
deba@1833: }
deba@1833: 
deba@1833: void checkGraphSorts() {
deba@1833:   checkGraphRadixSort();
deba@1833:   checkGraphCounterSort();
deba@1833: }
deba@1833: 
deba@1833: int main() {
deba@1833:   checkSorts();
deba@1833:   checkGraphSorts();
deba@1833:   return 0;
deba@1833: }