test/radix_sort_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 443 de16f1f2d228
child 1043 1bafdbd2fc46
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
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
}