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 deba@1833: #include deba@1833: #include deba@1833: #include deba@1833: #include deba@1833: deba@1833: #include "test_tools.h" deba@1833: deba@1833: deba@1833: #include deba@1833: #include deba@1833: #include 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 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 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 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 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 nodes; deba@1833: deba@1833: for (int i = 0; i < n; ++i) { deba@1833: nodes.push_back(graph.addNode()); deba@1833: } deba@1833: vector 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), deba@1833: sourceMap(graph)))); deba@1833: deba@1833: Graph::EdgeMap 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 nodes; deba@1833: deba@1833: for (int i = 0; i < n; ++i) { deba@1833: nodes.push_back(graph.addNode()); deba@1833: } deba@1833: vector 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), deba@1833: sourceMap(graph)))); deba@1833: deba@1833: counterSort(edges.begin(), edges.end(), deba@1833: mapFunctor(composeMap(IdMap(graph), deba@1833: targetMap(graph)))); deba@1833: deba@1833: Graph::EdgeMap 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: }