alpar@442: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@441:  *
alpar@442:  * This file is a part of LEMON, a generic C++ optimization library.
deba@441:  *
deba@441:  * Copyright (C) 2003-2008
deba@441:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@441:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@441:  *
deba@441:  * Permission to use, modify and distribute this software is granted
deba@441:  * provided that this copyright notice appears in all copies. For
deba@441:  * precise terms see the accompanying LICENSE file.
deba@441:  *
deba@441:  * This software is provided "AS IS" with no warranty of any kind,
deba@441:  * express or implied, and with no claim as to its suitability for any
deba@441:  * purpose.
deba@441:  *
deba@441:  */
deba@441: 
deba@441: #include <lemon/time_measure.h>
deba@441: #include <lemon/smart_graph.h>
deba@441: #include <lemon/maps.h>
deba@441: #include <lemon/radix_sort.h>
deba@441: #include <lemon/math.h>
deba@441: 
deba@441: #include "test_tools.h"
deba@441: 
deba@441: #include <vector>
deba@441: #include <algorithm>
deba@441: 
deba@441: using namespace lemon;
deba@441: 
deba@441: static const int n = 10000;
deba@441: 
deba@441: struct Negate {
deba@441:   typedef int argument_type;
deba@441:   typedef int result_type;
deba@441:   int operator()(int a) { return - a; }
deba@441: };
deba@441: 
deba@441: int negate(int a) { return - a; }
deba@441: 
deba@441: 
deba@441: void generateIntSequence(int n, std::vector<int>& data) {
deba@441:   int prime = 9973;
deba@441:   int root = 136, value = 1;
deba@441:   for (int i = 0; i < n; ++i) {
deba@441:     data.push_back(value - prime / 2);
deba@441:     value = (value * root) % prime;
deba@441:   }
deba@441: }
deba@441: 
deba@441: void generateCharSequence(int n, std::vector<unsigned char>& data) {
deba@441:   int prime = 251;
deba@441:   int root = 3, value = root;
deba@441:   for (int i = 0; i < n; ++i) {
deba@441:     data.push_back(static_cast<unsigned char>(value));
deba@441:     value = (value * root) % prime;
deba@441:   }
deba@441: }
deba@441: 
deba@441: void checkRadixSort() {
deba@441:   {
deba@441:     std::vector<int> data1;
deba@441:     generateIntSequence(n, data1);
deba@441: 
deba@441:     std::vector<int> data2(data1);
deba@441:     std::sort(data1.begin(), data1.end());
deba@441: 
deba@441:     radixSort(data2.begin(), data2.end());
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[i], "Test failed");
deba@441:     }
deba@441: 
deba@441:     radixSort(data2.begin(), data2.end(), Negate());
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[n - 1 - i], "Test failed");
deba@441:     }
deba@441: 
deba@441:     radixSort(data2.begin(), data2.end(), negate);
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[n - 1 - i], "Test failed");
deba@441:     }
deba@441: 
alpar@442:   }
alpar@442: 
deba@441:   {
deba@441:     std::vector<unsigned char> data1(n);
deba@441:     generateCharSequence(n, data1);
deba@441: 
deba@441:     std::vector<unsigned char> data2(data1);
deba@441:     std::sort(data1.begin(), data1.end());
deba@441: 
deba@441:     radixSort(data2.begin(), data2.end());
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[i], "Test failed");
deba@441:     }
deba@441: 
deba@441:   }
deba@441: }
deba@441: 
deba@441: 
deba@441: void checkCounterSort() {
deba@441:   {
deba@441:     std::vector<int> data1;
deba@441:     generateIntSequence(n, data1);
deba@441: 
deba@441:     std::vector<int> data2(data1);
deba@441:     std::sort(data1.begin(), data1.end());
deba@441: 
deba@441:     counterSort(data2.begin(), data2.end());
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[i], "Test failed");
deba@441:     }
deba@441: 
deba@441:     counterSort(data2.begin(), data2.end(), Negate());
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[n - 1 - i], "Test failed");
deba@441:     }
deba@441: 
deba@441:     counterSort(data2.begin(), data2.end(), negate);
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[n - 1 - i], "Test failed");
deba@441:     }
alpar@442:   }
deba@441: 
deba@441:   {
deba@441:     std::vector<unsigned char> data1(n);
deba@441:     generateCharSequence(n, data1);
deba@441: 
deba@441:     std::vector<unsigned char> data2(data1);
deba@441:     std::sort(data1.begin(), data1.end());
deba@441: 
deba@441:     radixSort(data2.begin(), data2.end());
deba@441:     for (int i = 0; i < n; ++i) {
deba@441:       check(data1[i] == data2[i], "Test failed");
deba@441:     }
deba@441: 
deba@441:   }
deba@441: }
deba@441: 
deba@441: int main() {
deba@441: 
alpar@442:   checkRadixSort();
deba@441:   checkCounterSort();
deba@441: 
deba@441:   return 0;
deba@441: }