test/radix_sort_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 16 Mar 2013 13:16:27 +0100
changeset 1050 d9d1cb759951
parent 444 ba49101c9b07
child 1092 dceba191c00d
permissions -rw-r--r--
Add images to the doc of two groups (#459)
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>
alpar@1043
    28
#include <list>
deba@441
    29
#include <algorithm>
deba@441
    30
deba@441
    31
using namespace lemon;
deba@441
    32
deba@441
    33
static const int n = 10000;
deba@441
    34
deba@441
    35
struct Negate {
deba@441
    36
  typedef int argument_type;
deba@441
    37
  typedef int result_type;
deba@441
    38
  int operator()(int a) { return - a; }
deba@441
    39
};
deba@441
    40
deba@441
    41
int negate(int a) { return - a; }
deba@441
    42
alpar@1043
    43
template<class T>
alpar@1043
    44
bool isTheSame(T &a, T&b)
alpar@1043
    45
{
alpar@1043
    46
  typename T::iterator ai=a.begin();
alpar@1043
    47
  typename T::iterator bi=b.begin();
alpar@1043
    48
  for(;ai!=a.end()||bi!=b.end();++ai,++bi)
alpar@1043
    49
    if(*ai!=*bi) return false;
alpar@1043
    50
  return ai==a.end()&&bi==b.end();
alpar@1043
    51
}
deba@441
    52
alpar@1043
    53
template<class T>
alpar@1043
    54
T listsort(typename T::iterator b, typename T::iterator e)
alpar@1043
    55
{ 
alpar@1043
    56
  if(b==e) return T();
alpar@1043
    57
  typename T::iterator bn=b;
alpar@1043
    58
  if(++bn==e) {
alpar@1043
    59
    T l;
alpar@1043
    60
    l.push_back(*b);
alpar@1043
    61
    return l;
alpar@1043
    62
  }
alpar@1043
    63
  typename T::iterator m=b;
alpar@1043
    64
  bool x=false;
alpar@1043
    65
  for(typename T::iterator i=b;i!=e;++i,x=!x)
alpar@1043
    66
    if(x) ++m;
alpar@1043
    67
  T l1(listsort<T>(b,m));
alpar@1043
    68
  T l2(listsort<T>(m,e));
alpar@1043
    69
  T l;
alpar@1043
    70
  while((!l1.empty())&&(!l2.empty()))
alpar@1043
    71
    if(l1.front()<=l2.front())
alpar@1043
    72
      {
alpar@1043
    73
        l.push_back(l1.front());
alpar@1043
    74
        l1.pop_front();
alpar@1043
    75
      }
alpar@1043
    76
    else {
alpar@1043
    77
      l.push_back(l2.front());
alpar@1043
    78
      l2.pop_front();
alpar@1043
    79
    }
alpar@1043
    80
  while(!l1.empty())
alpar@1043
    81
    {
alpar@1043
    82
      l.push_back(l1.front());
alpar@1043
    83
      l1.pop_front();
alpar@1043
    84
    }
alpar@1043
    85
  while(!l2.empty())
alpar@1043
    86
    {
alpar@1043
    87
      l.push_back(l2.front());
alpar@1043
    88
      l2.pop_front();
alpar@1043
    89
    }
alpar@1043
    90
  return l;
alpar@1043
    91
}
alpar@1043
    92
alpar@1043
    93
template<class T>
alpar@1043
    94
void generateIntSequence(int n, T & data) {
deba@441
    95
  int prime = 9973;
deba@441
    96
  int root = 136, value = 1;
deba@441
    97
  for (int i = 0; i < n; ++i) {
deba@441
    98
    data.push_back(value - prime / 2);
deba@441
    99
    value = (value * root) % prime;
deba@441
   100
  }
deba@441
   101
}
deba@441
   102
alpar@1043
   103
template<class T>
alpar@1043
   104
void generateCharSequence(int n, T & data) {
deba@441
   105
  int prime = 251;
deba@441
   106
  int root = 3, value = root;
deba@441
   107
  for (int i = 0; i < n; ++i) {
deba@441
   108
    data.push_back(static_cast<unsigned char>(value));
deba@441
   109
    value = (value * root) % prime;
deba@441
   110
  }
deba@441
   111
}
deba@441
   112
deba@441
   113
void checkRadixSort() {
deba@441
   114
  {
deba@441
   115
    std::vector<int> data1;
deba@441
   116
    generateIntSequence(n, data1);
deba@441
   117
deba@441
   118
    std::vector<int> data2(data1);
deba@441
   119
    std::sort(data1.begin(), data1.end());
deba@441
   120
deba@441
   121
    radixSort(data2.begin(), data2.end());
deba@441
   122
    for (int i = 0; i < n; ++i) {
deba@441
   123
      check(data1[i] == data2[i], "Test failed");
deba@441
   124
    }
deba@441
   125
alpar@1043
   126
    // radixSort(data2.begin(), data2.end(), Negate());
alpar@1043
   127
    // for (int i = 0; i < n; ++i) {
alpar@1043
   128
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1043
   129
    // }
deba@441
   130
alpar@1043
   131
    // radixSort(data2.begin(), data2.end(), negate);
alpar@1043
   132
    // for (int i = 0; i < n; ++i) {
alpar@1043
   133
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1043
   134
    // }
deba@441
   135
alpar@442
   136
  }
alpar@442
   137
deba@441
   138
  {
deba@441
   139
    std::vector<unsigned char> data1(n);
deba@441
   140
    generateCharSequence(n, data1);
deba@441
   141
deba@441
   142
    std::vector<unsigned char> data2(data1);
deba@441
   143
    std::sort(data1.begin(), data1.end());
deba@441
   144
deba@441
   145
    radixSort(data2.begin(), data2.end());
deba@441
   146
    for (int i = 0; i < n; ++i) {
deba@441
   147
      check(data1[i] == data2[i], "Test failed");
deba@441
   148
    }
deba@441
   149
deba@441
   150
  }
alpar@1043
   151
  {
alpar@1043
   152
    std::list<int> data1;
alpar@1043
   153
    generateIntSequence(n, data1);
alpar@1043
   154
alpar@1043
   155
    std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
alpar@1043
   156
alpar@1043
   157
    radixSort(data1.begin(), data1.end());
alpar@1043
   158
alpar@1043
   159
    check(isTheSame(data1,data2), "Test failed");
alpar@1043
   160
alpar@1043
   161
alpar@1043
   162
    // radixSort(data2.begin(), data2.end(), Negate());
alpar@1043
   163
    // check(isTheSame(data1,data2), "Test failed");
alpar@1043
   164
    // for (int i = 0; i < n; ++i) {
alpar@1043
   165
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1043
   166
    // }
alpar@1043
   167
alpar@1043
   168
    // radixSort(data2.begin(), data2.end(), negate);
alpar@1043
   169
    // for (int i = 0; i < n; ++i) {
alpar@1043
   170
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1043
   171
    // }
alpar@1043
   172
alpar@1043
   173
  }
alpar@1043
   174
alpar@1043
   175
  {
alpar@1043
   176
    std::list<unsigned char> data1(n);
alpar@1043
   177
    generateCharSequence(n, data1);
alpar@1043
   178
alpar@1043
   179
    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
alpar@1043
   180
                                   (data1.begin(),
alpar@1043
   181
                                    data1.end()));
alpar@1043
   182
alpar@1043
   183
    radixSort(data1.begin(), data1.end());
alpar@1043
   184
    check(isTheSame(data1,data2), "Test failed");
alpar@1043
   185
alpar@1043
   186
  }
deba@441
   187
}
deba@441
   188
deba@441
   189
deba@443
   190
void checkStableRadixSort() {
deba@441
   191
  {
deba@441
   192
    std::vector<int> data1;
deba@441
   193
    generateIntSequence(n, data1);
deba@441
   194
deba@441
   195
    std::vector<int> data2(data1);
deba@441
   196
    std::sort(data1.begin(), data1.end());
deba@441
   197
deba@443
   198
    stableRadixSort(data2.begin(), data2.end());
deba@441
   199
    for (int i = 0; i < n; ++i) {
deba@441
   200
      check(data1[i] == data2[i], "Test failed");
deba@441
   201
    }
deba@441
   202
deba@443
   203
    stableRadixSort(data2.begin(), data2.end(), Negate());
deba@441
   204
    for (int i = 0; i < n; ++i) {
deba@441
   205
      check(data1[i] == data2[n - 1 - i], "Test failed");
deba@441
   206
    }
deba@441
   207
deba@443
   208
    stableRadixSort(data2.begin(), data2.end(), negate);
deba@441
   209
    for (int i = 0; i < n; ++i) {
deba@441
   210
      check(data1[i] == data2[n - 1 - i], "Test failed");
deba@441
   211
    }
alpar@442
   212
  }
deba@441
   213
deba@441
   214
  {
deba@441
   215
    std::vector<unsigned char> data1(n);
deba@441
   216
    generateCharSequence(n, data1);
deba@441
   217
deba@441
   218
    std::vector<unsigned char> data2(data1);
deba@441
   219
    std::sort(data1.begin(), data1.end());
deba@441
   220
deba@441
   221
    radixSort(data2.begin(), data2.end());
deba@441
   222
    for (int i = 0; i < n; ++i) {
deba@441
   223
      check(data1[i] == data2[i], "Test failed");
deba@441
   224
    }
deba@441
   225
deba@441
   226
  }
alpar@1043
   227
  {
alpar@1043
   228
    std::list<int> data1;
alpar@1043
   229
    generateIntSequence(n, data1);
alpar@1043
   230
alpar@1043
   231
    std::list<int> data2(listsort<std::list<int> >(data1.begin(),
alpar@1043
   232
                                                   data1.end()));
alpar@1043
   233
    stableRadixSort(data1.begin(), data1.end());
alpar@1043
   234
    check(isTheSame(data1,data2), "Test failed");
alpar@1043
   235
alpar@1043
   236
    // stableRadixSort(data2.begin(), data2.end(), Negate());
alpar@1043
   237
    // for (int i = 0; i < n; ++i) {
alpar@1043
   238
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1043
   239
    // }
alpar@1043
   240
alpar@1043
   241
    // stableRadixSort(data2.begin(), data2.end(), negate);
alpar@1043
   242
    // for (int i = 0; i < n; ++i) {
alpar@1043
   243
    //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1043
   244
    // }
alpar@1043
   245
  }
alpar@1043
   246
alpar@1043
   247
  {
alpar@1043
   248
    std::list<unsigned char> data1(n);
alpar@1043
   249
    generateCharSequence(n, data1);
alpar@1043
   250
alpar@1043
   251
    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
alpar@1043
   252
                                   (data1.begin(),
alpar@1043
   253
                                    data1.end()));
alpar@1043
   254
    radixSort(data1.begin(), data1.end());
alpar@1043
   255
    check(isTheSame(data1,data2), "Test failed");
alpar@1043
   256
alpar@1043
   257
  }
deba@441
   258
}
deba@441
   259
deba@441
   260
int main() {
deba@441
   261
alpar@442
   262
  checkRadixSort();
deba@443
   263
  checkStableRadixSort();
deba@441
   264
deba@441
   265
  return 0;
deba@441
   266
}