lemon-0.x: test/radix_sort_test.cc@b22dfb6c5ff3

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

     2  *

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

     4  *

     5  * Copyright (C) 2003-2006

     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 <cmath>

    32 using namespace std;

    33 using namespace lemon;

    35 void checkRadixSort() {

    36   {

    37     int n = 10000;

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

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

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

    41     }

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

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

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

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

    46     }

    47   } {

    48     int n = 10000;

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

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

    51       data1[i] = data2[i] = rnd[(unsigned char)200];

    52     }

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

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

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

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

    57     }

    58   }

    59 }

    62 void checkCounterSort() {

    63   {

    64     int n = 10000;

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

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

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

    68     }

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

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

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

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

    73     }

    74   } {

    75     int n = 10000;

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

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

    78       data1[i] = data2[i] = rnd[(unsigned char)200];

    79     }

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

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

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

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

    84     }

    85   }

    86 }

    88 void checkSorts() {

    89   checkRadixSort();

    90   checkCounterSort();

    91 }

    93 void checkGraphRadixSort() {

    94   typedef SmartGraph Graph;

    95   typedef Graph::Node Node;

    96   typedef Graph::Edge Edge;

    98   const int n = 100;

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

   101   Graph graph;

   102   vector<Node> nodes;

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

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

   106   }

   107   vector<Edge> edges;

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

   109     int s = rnd[n];

   110     int t = rnd[n];

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

   112   }

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

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

   116 				  sourceMap(graph))));

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

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

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

   122     was[edges[i]] = true;

   123   }

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

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

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

   128   }

   130 }

   132 void checkGraphCounterSort() {

   133   typedef SmartGraph Graph;

   134   typedef Graph::Node Node;

   135   typedef Graph::Edge Edge;

   137   const int n = 100;

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

   140   Graph graph;

   141   vector<Node> nodes;

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

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

   145   }

   146   vector<Edge> edges;

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

   148     int s = rnd[n];

   149     int t = rnd[n];

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

   151   }

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

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

   155 				    sourceMap(graph))));

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

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

   159 				    targetMap(graph))));

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

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

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

   165     was[edges[i]] = true;

   166   }

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

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

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

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

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

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

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

   175   }

   177 }

   179 void checkGraphSorts() {

   180   checkGraphRadixSort();

   181   checkGraphCounterSort();

   182 }

   184 int main() {

   185   checkSorts();

   186   checkGraphSorts();

   187   return 0;

   188 }

author	alpar
	Fri, 20 Oct 2006 12:05:54 +0000
changeset 2256	b22dfb6c5ff3
parent 1956	a055123339d5
child 2386	81b47fc5c444
permissions	-rw-r--r--