lemon-0.x: test/radix_sort_test.cc@054566ac0934

     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

     8  *

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

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

    11  * precise terms see the accompanying LICENSE file.

    12  *

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

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

    15  * purpose.

    16  *

    17  */

    19 #include <lemon/time_measure.h>

    20 #include <lemon/smart_graph.h>

    21 #include <lemon/graph_utils.h>

    22 #include <lemon/maps.h>

    23 #include <lemon/radix_sort.h>

    25 #include "test_tools.h"

    28 #include <vector>

    29 #include <algorithm>

    30 #include <lemon/math.h>

    32 using namespace std;

    33 using namespace lemon;

    35 typedef unsigned char uchar;

    37 void checkRadixSort() {

    38   {

    39     int n = 10000;

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

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

    42       data1[i] = data2[i] = rnd[1000] - 500;

    43     }

    44     radixSort(data1.begin(), data1.end());

    45     sort(data2.begin(), data2.end());

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

    47       check(data1[i] == data2[i], "Test failed");

    48     }

    49   } {

    50     int n = 10000;

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

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

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

    54     }

    55     radixSort(data1.begin(), data1.end());

    56     sort(data2.begin(), data2.end());

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

    58       check(data1[i] == data2[i], "Test failed");

    59     }

    60   }

    61 }

    64 void checkCounterSort() {

    65   {

    66     int n = 10000;

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

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

    69       data1[i] = data2[i] = rnd[1000] - 500;

    70     }

    71     counterSort(data1.begin(), data1.end());

    72     sort(data2.begin(), data2.end());

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

    74       check(data1[i] == data2[i], "Test failed");

    75     }

    76   } {

    77     int n = 10000;

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

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

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

    81     }

    82     counterSort(data1.begin(), data1.end());

    83     sort(data2.begin(), data2.end());

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

    85       check(data1[i] == data2[i], "Test failed");

    86     }

    87   }

    88 }

    90 void checkSorts() {

    91   checkRadixSort();

    92   checkCounterSort();

    93 }

    95 void checkGraphRadixSort() {

    96   typedef SmartGraph Graph;

    97   typedef Graph::Node Node;

    98   typedef Graph::Edge Edge;

   100   const int n = 100;

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

   103   Graph graph;

   104   vector<Node> nodes;

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

   107     nodes.push_back(graph.addNode());

   108   }

   109   vector<Edge> edges;

   110   for (int i = 0; i < e; ++i) {

   111     int s = rnd[n];

   112     int t = rnd[n];

   113     edges.push_back(graph.addEdge(nodes[s], nodes[t]));

   114   }

   116   radixSort(edges.begin(), edges.end(),

   117 	    mapFunctor(composeMap(IdMap<Graph, Node>(graph),

   118 				  sourceMap(graph))));

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

   122   for (int i = 0; i < int(edges.size()); ++i) {

   123     check(!was[edges[i]], "Test failed");

   124     was[edges[i]] = true;

   125   }

   127   for (int i = 1; i < int(edges.size()); ++i) {

   128     check(graph.id(graph.source(edges[i - 1])) <=

   129 	  graph.id(graph.source(edges[i])), "Test failed");

   130   }

   132 }

   134 void checkGraphCounterSort() {

   135   typedef SmartGraph Graph;

   136   typedef Graph::Node Node;

   137   typedef Graph::Edge Edge;

   139   const int n = 100;

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

   142   Graph graph;

   143   vector<Node> nodes;

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

   146     nodes.push_back(graph.addNode());

   147   }

   148   vector<Edge> edges;

   149   for (int i = 0; i < e; ++i) {

   150     int s = rnd[n];

   151     int t = rnd[n];

   152     edges.push_back(graph.addEdge(nodes[s], nodes[t]));

   153   }

   155   counterSort(edges.begin(), edges.end(),

   156 	      mapFunctor(composeMap(IdMap<Graph, Node>(graph),

   157 				    sourceMap(graph))));

   159   counterSort(edges.begin(), edges.end(),

   160 	      mapFunctor(composeMap(IdMap<Graph, Node>(graph),

   161 				    targetMap(graph))));

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

   165   for (int i = 0; i < int(edges.size()); ++i) {

   166     check(!was[edges[i]], "Test failed");

   167     was[edges[i]] = true;

   168   }

   170   for (int i = 1; i < int(edges.size()); ++i) {

   171     check(graph.id(graph.target(edges[i - 1])) <

   172 	  graph.id(graph.target(edges[i])) ||

   173 	  (graph.id(graph.target(edges[i - 1])) ==

   174 	   graph.id(graph.target(edges[i])) &&

   175 	   graph.id(graph.source(edges[i - 1])) <=

   176 	   graph.id(graph.source(edges[i]))), "Test failed");

   177   }

   179 }

   181 void checkGraphSorts() {

   182   checkGraphRadixSort();

   183   checkGraphCounterSort();

   184 }

   186 int main() {

   187   checkSorts();

   188   checkGraphSorts();

   189   return 0;

   190 }

author	kpeter
	Thu, 28 Feb 2008 02:54:27 +0000
changeset 2581	054566ac0934
parent 2553	bfced05fa852
permissions	-rw-r--r--