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