1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/radix_sort_test.cc	Thu Nov 05 15:50:01 2009 +0100
     1.3 @@ -0,0 +1,147 @@
     1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library.
     1.7 + *
     1.8 + * Copyright (C) 2003-2009
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#include <lemon/time_measure.h>
    1.23 +#include <lemon/smart_graph.h>
    1.24 +#include <lemon/maps.h>
    1.25 +#include <lemon/radix_sort.h>
    1.26 +#include <lemon/math.h>
    1.27 +
    1.28 +#include "test_tools.h"
    1.29 +
    1.30 +#include <vector>
    1.31 +#include <algorithm>
    1.32 +
    1.33 +using namespace lemon;
    1.34 +
    1.35 +static const int n = 10000;
    1.36 +
    1.37 +struct Negate {
    1.38 +  typedef int argument_type;
    1.39 +  typedef int result_type;
    1.40 +  int operator()(int a) { return - a; }
    1.41 +};
    1.42 +
    1.43 +int negate(int a) { return - a; }
    1.44 +
    1.45 +
    1.46 +void generateIntSequence(int n, std::vector<int>& data) {
    1.47 +  int prime = 9973;
    1.48 +  int root = 136, value = 1;
    1.49 +  for (int i = 0; i < n; ++i) {
    1.50 +    data.push_back(value - prime / 2);
    1.51 +    value = (value * root) % prime;
    1.52 +  }
    1.53 +}
    1.54 +
    1.55 +void generateCharSequence(int n, std::vector<unsigned char>& data) {
    1.56 +  int prime = 251;
    1.57 +  int root = 3, value = root;
    1.58 +  for (int i = 0; i < n; ++i) {
    1.59 +    data.push_back(static_cast<unsigned char>(value));
    1.60 +    value = (value * root) % prime;
    1.61 +  }
    1.62 +}
    1.63 +
    1.64 +void checkRadixSort() {
    1.65 +  {
    1.66 +    std::vector<int> data1;
    1.67 +    generateIntSequence(n, data1);
    1.68 +
    1.69 +    std::vector<int> data2(data1);
    1.70 +    std::sort(data1.begin(), data1.end());
    1.71 +
    1.72 +    radixSort(data2.begin(), data2.end());
    1.73 +    for (int i = 0; i < n; ++i) {
    1.74 +      check(data1[i] == data2[i], "Test failed");
    1.75 +    }
    1.76 +
    1.77 +    radixSort(data2.begin(), data2.end(), Negate());
    1.78 +    for (int i = 0; i < n; ++i) {
    1.79 +      check(data1[i] == data2[n - 1 - i], "Test failed");
    1.80 +    }
    1.81 +
    1.82 +    radixSort(data2.begin(), data2.end(), negate);
    1.83 +    for (int i = 0; i < n; ++i) {
    1.84 +      check(data1[i] == data2[n - 1 - i], "Test failed");
    1.85 +    }
    1.86 +
    1.87 +  }
    1.88 +
    1.89 +  {
    1.90 +    std::vector<unsigned char> data1(n);
    1.91 +    generateCharSequence(n, data1);
    1.92 +
    1.93 +    std::vector<unsigned char> data2(data1);
    1.94 +    std::sort(data1.begin(), data1.end());
    1.95 +
    1.96 +    radixSort(data2.begin(), data2.end());
    1.97 +    for (int i = 0; i < n; ++i) {
    1.98 +      check(data1[i] == data2[i], "Test failed");
    1.99 +    }
   1.100 +
   1.101 +  }
   1.102 +}
   1.103 +
   1.104 +
   1.105 +void checkStableRadixSort() {
   1.106 +  {
   1.107 +    std::vector<int> data1;
   1.108 +    generateIntSequence(n, data1);
   1.109 +
   1.110 +    std::vector<int> data2(data1);
   1.111 +    std::sort(data1.begin(), data1.end());
   1.112 +
   1.113 +    stableRadixSort(data2.begin(), data2.end());
   1.114 +    for (int i = 0; i < n; ++i) {
   1.115 +      check(data1[i] == data2[i], "Test failed");
   1.116 +    }
   1.117 +
   1.118 +    stableRadixSort(data2.begin(), data2.end(), Negate());
   1.119 +    for (int i = 0; i < n; ++i) {
   1.120 +      check(data1[i] == data2[n - 1 - i], "Test failed");
   1.121 +    }
   1.122 +
   1.123 +    stableRadixSort(data2.begin(), data2.end(), negate);
   1.124 +    for (int i = 0; i < n; ++i) {
   1.125 +      check(data1[i] == data2[n - 1 - i], "Test failed");
   1.126 +    }
   1.127 +  }
   1.128 +
   1.129 +  {
   1.130 +    std::vector<unsigned char> data1(n);
   1.131 +    generateCharSequence(n, data1);
   1.132 +
   1.133 +    std::vector<unsigned char> data2(data1);
   1.134 +    std::sort(data1.begin(), data1.end());
   1.135 +
   1.136 +    radixSort(data2.begin(), data2.end());
   1.137 +    for (int i = 0; i < n; ++i) {
   1.138 +      check(data1[i] == data2[i], "Test failed");
   1.139 +    }
   1.140 +
   1.141 +  }
   1.142 +}
   1.143 +
   1.144 +int main() {
   1.145 +
   1.146 +  checkRadixSort();
   1.147 +  checkStableRadixSort();
   1.148 +
   1.149 +  return 0;
   1.150 +}