test/radix_sort_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 06 May 2012 16:52:11 +0200
branch1.2
changeset 1142 4764031c082c
parent 466 de16f1f2d228
child 1211 1bafdbd2fc46
permissions -rw-r--r--
Merge bugfix #441 to branch 1.2
alpar@465
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@464
     2
 *
alpar@465
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@464
     4
 *
alpar@467
     5
 * Copyright (C) 2003-2009
deba@464
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@464
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@464
     8
 *
deba@464
     9
 * Permission to use, modify and distribute this software is granted
deba@464
    10
 * provided that this copyright notice appears in all copies. For
deba@464
    11
 * precise terms see the accompanying LICENSE file.
deba@464
    12
 *
deba@464
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@464
    14
 * express or implied, and with no claim as to its suitability for any
deba@464
    15
 * purpose.
deba@464
    16
 *
deba@464
    17
 */
deba@464
    18
deba@464
    19
#include <lemon/time_measure.h>
deba@464
    20
#include <lemon/smart_graph.h>
deba@464
    21
#include <lemon/maps.h>
deba@464
    22
#include <lemon/radix_sort.h>
deba@464
    23
#include <lemon/math.h>
deba@464
    24
deba@464
    25
#include "test_tools.h"
deba@464
    26
deba@464
    27
#include <vector>
deba@464
    28
#include <algorithm>
deba@464
    29
deba@464
    30
using namespace lemon;
deba@464
    31
deba@464
    32
static const int n = 10000;
deba@464
    33
deba@464
    34
struct Negate {
deba@464
    35
  typedef int argument_type;
deba@464
    36
  typedef int result_type;
deba@464
    37
  int operator()(int a) { return - a; }
deba@464
    38
};
deba@464
    39
deba@464
    40
int negate(int a) { return - a; }
deba@464
    41
deba@464
    42
deba@464
    43
void generateIntSequence(int n, std::vector<int>& data) {
deba@464
    44
  int prime = 9973;
deba@464
    45
  int root = 136, value = 1;
deba@464
    46
  for (int i = 0; i < n; ++i) {
deba@464
    47
    data.push_back(value - prime / 2);
deba@464
    48
    value = (value * root) % prime;
deba@464
    49
  }
deba@464
    50
}
deba@464
    51
deba@464
    52
void generateCharSequence(int n, std::vector<unsigned char>& data) {
deba@464
    53
  int prime = 251;
deba@464
    54
  int root = 3, value = root;
deba@464
    55
  for (int i = 0; i < n; ++i) {
deba@464
    56
    data.push_back(static_cast<unsigned char>(value));
deba@464
    57
    value = (value * root) % prime;
deba@464
    58
  }
deba@464
    59
}
deba@464
    60
deba@464
    61
void checkRadixSort() {
deba@464
    62
  {
deba@464
    63
    std::vector<int> data1;
deba@464
    64
    generateIntSequence(n, data1);
deba@464
    65
deba@464
    66
    std::vector<int> data2(data1);
deba@464
    67
    std::sort(data1.begin(), data1.end());
deba@464
    68
deba@464
    69
    radixSort(data2.begin(), data2.end());
deba@464
    70
    for (int i = 0; i < n; ++i) {
deba@464
    71
      check(data1[i] == data2[i], "Test failed");
deba@464
    72
    }
deba@464
    73
deba@464
    74
    radixSort(data2.begin(), data2.end(), Negate());
deba@464
    75
    for (int i = 0; i < n; ++i) {
deba@464
    76
      check(data1[i] == data2[n - 1 - i], "Test failed");
deba@464
    77
    }
deba@464
    78
deba@464
    79
    radixSort(data2.begin(), data2.end(), negate);
deba@464
    80
    for (int i = 0; i < n; ++i) {
deba@464
    81
      check(data1[i] == data2[n - 1 - i], "Test failed");
deba@464
    82
    }
deba@464
    83
alpar@465
    84
  }
alpar@465
    85
deba@464
    86
  {
deba@464
    87
    std::vector<unsigned char> data1(n);
deba@464
    88
    generateCharSequence(n, data1);
deba@464
    89
deba@464
    90
    std::vector<unsigned char> data2(data1);
deba@464
    91
    std::sort(data1.begin(), data1.end());
deba@464
    92
deba@464
    93
    radixSort(data2.begin(), data2.end());
deba@464
    94
    for (int i = 0; i < n; ++i) {
deba@464
    95
      check(data1[i] == data2[i], "Test failed");
deba@464
    96
    }
deba@464
    97
deba@464
    98
  }
deba@464
    99
}
deba@464
   100
deba@464
   101
deba@466
   102
void checkStableRadixSort() {
deba@464
   103
  {
deba@464
   104
    std::vector<int> data1;
deba@464
   105
    generateIntSequence(n, data1);
deba@464
   106
deba@464
   107
    std::vector<int> data2(data1);
deba@464
   108
    std::sort(data1.begin(), data1.end());
deba@464
   109
deba@466
   110
    stableRadixSort(data2.begin(), data2.end());
deba@464
   111
    for (int i = 0; i < n; ++i) {
deba@464
   112
      check(data1[i] == data2[i], "Test failed");
deba@464
   113
    }
deba@464
   114
deba@466
   115
    stableRadixSort(data2.begin(), data2.end(), Negate());
deba@464
   116
    for (int i = 0; i < n; ++i) {
deba@464
   117
      check(data1[i] == data2[n - 1 - i], "Test failed");
deba@464
   118
    }
deba@464
   119
deba@466
   120
    stableRadixSort(data2.begin(), data2.end(), negate);
deba@464
   121
    for (int i = 0; i < n; ++i) {
deba@464
   122
      check(data1[i] == data2[n - 1 - i], "Test failed");
deba@464
   123
    }
alpar@465
   124
  }
deba@464
   125
deba@464
   126
  {
deba@464
   127
    std::vector<unsigned char> data1(n);
deba@464
   128
    generateCharSequence(n, data1);
deba@464
   129
deba@464
   130
    std::vector<unsigned char> data2(data1);
deba@464
   131
    std::sort(data1.begin(), data1.end());
deba@464
   132
deba@464
   133
    radixSort(data2.begin(), data2.end());
deba@464
   134
    for (int i = 0; i < n; ++i) {
deba@464
   135
      check(data1[i] == data2[i], "Test failed");
deba@464
   136
    }
deba@464
   137
deba@464
   138
  }
deba@464
   139
}
deba@464
   140
deba@464
   141
int main() {
deba@464
   142
alpar@465
   143
  checkRadixSort();
deba@466
   144
  checkStableRadixSort();
deba@464
   145
deba@464
   146
  return 0;
deba@464
   147
}