/* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2009 * 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 #include #include #include #include #include "test_tools.h" #include #include using namespace lemon; static const int n = 10000; struct Negate { typedef int argument_type; typedef int result_type; int operator()(int a) { return - a; } }; int negate(int a) { return - a; } void generateIntSequence(int n, std::vector& data) { int prime = 9973; int root = 136, value = 1; for (int i = 0; i < n; ++i) { data.push_back(value - prime / 2); value = (value * root) % prime; } } void generateCharSequence(int n, std::vector& data) { int prime = 251; int root = 3, value = root; for (int i = 0; i < n; ++i) { data.push_back(static_cast(value)); value = (value * root) % prime; } } void checkRadixSort() { { std::vector data1; generateIntSequence(n, data1); std::vector data2(data1); std::sort(data1.begin(), data1.end()); radixSort(data2.begin(), data2.end()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[i], "Test failed"); } radixSort(data2.begin(), data2.end(), Negate()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[n - 1 - i], "Test failed"); } radixSort(data2.begin(), data2.end(), negate); for (int i = 0; i < n; ++i) { check(data1[i] == data2[n - 1 - i], "Test failed"); } } { std::vector data1(n); generateCharSequence(n, data1); std::vector data2(data1); std::sort(data1.begin(), data1.end()); radixSort(data2.begin(), data2.end()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[i], "Test failed"); } } } void checkStableRadixSort() { { std::vector data1; generateIntSequence(n, data1); std::vector data2(data1); std::sort(data1.begin(), data1.end()); stableRadixSort(data2.begin(), data2.end()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[i], "Test failed"); } stableRadixSort(data2.begin(), data2.end(), Negate()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[n - 1 - i], "Test failed"); } stableRadixSort(data2.begin(), data2.end(), negate); for (int i = 0; i < n; ++i) { check(data1[i] == data2[n - 1 - i], "Test failed"); } } { std::vector data1(n); generateCharSequence(n, data1); std::vector data2(data1); std::sort(data1.begin(), data1.end()); radixSort(data2.begin(), data2.end()); for (int i = 0; i < n; ++i) { check(data1[i] == data2[i], "Test failed"); } } } int main() { checkRadixSort(); checkStableRadixSort(); return 0; }