test/radix_sort_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 07 Aug 2013 07:04:58 +0200
changeset 1086 97f1760dcd13
parent 444 ba49101c9b07
child 1092 dceba191c00d
permissions -rw-r--r--
Merge #294
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/time_measure.h>
    20 #include <lemon/smart_graph.h>
    21 #include <lemon/maps.h>
    22 #include <lemon/radix_sort.h>
    23 #include <lemon/math.h>
    24 
    25 #include "test_tools.h"
    26 
    27 #include <vector>
    28 #include <list>
    29 #include <algorithm>
    30 
    31 using namespace lemon;
    32 
    33 static const int n = 10000;
    34 
    35 struct Negate {
    36   typedef int argument_type;
    37   typedef int result_type;
    38   int operator()(int a) { return - a; }
    39 };
    40 
    41 int negate(int a) { return - a; }
    42 
    43 template<class T>
    44 bool isTheSame(T &a, T&b)
    45 {
    46   typename T::iterator ai=a.begin();
    47   typename T::iterator bi=b.begin();
    48   for(;ai!=a.end()||bi!=b.end();++ai,++bi)
    49     if(*ai!=*bi) return false;
    50   return ai==a.end()&&bi==b.end();
    51 }
    52 
    53 template<class T>
    54 T listsort(typename T::iterator b, typename T::iterator e)
    55 { 
    56   if(b==e) return T();
    57   typename T::iterator bn=b;
    58   if(++bn==e) {
    59     T l;
    60     l.push_back(*b);
    61     return l;
    62   }
    63   typename T::iterator m=b;
    64   bool x=false;
    65   for(typename T::iterator i=b;i!=e;++i,x=!x)
    66     if(x) ++m;
    67   T l1(listsort<T>(b,m));
    68   T l2(listsort<T>(m,e));
    69   T l;
    70   while((!l1.empty())&&(!l2.empty()))
    71     if(l1.front()<=l2.front())
    72       {
    73         l.push_back(l1.front());
    74         l1.pop_front();
    75       }
    76     else {
    77       l.push_back(l2.front());
    78       l2.pop_front();
    79     }
    80   while(!l1.empty())
    81     {
    82       l.push_back(l1.front());
    83       l1.pop_front();
    84     }
    85   while(!l2.empty())
    86     {
    87       l.push_back(l2.front());
    88       l2.pop_front();
    89     }
    90   return l;
    91 }
    92 
    93 template<class T>
    94 void generateIntSequence(int n, T & data) {
    95   int prime = 9973;
    96   int root = 136, value = 1;
    97   for (int i = 0; i < n; ++i) {
    98     data.push_back(value - prime / 2);
    99     value = (value * root) % prime;
   100   }
   101 }
   102 
   103 template<class T>
   104 void generateCharSequence(int n, T & data) {
   105   int prime = 251;
   106   int root = 3, value = root;
   107   for (int i = 0; i < n; ++i) {
   108     data.push_back(static_cast<unsigned char>(value));
   109     value = (value * root) % prime;
   110   }
   111 }
   112 
   113 void checkRadixSort() {
   114   {
   115     std::vector<int> data1;
   116     generateIntSequence(n, data1);
   117 
   118     std::vector<int> data2(data1);
   119     std::sort(data1.begin(), data1.end());
   120 
   121     radixSort(data2.begin(), data2.end());
   122     for (int i = 0; i < n; ++i) {
   123       check(data1[i] == data2[i], "Test failed");
   124     }
   125 
   126     // radixSort(data2.begin(), data2.end(), Negate());
   127     // for (int i = 0; i < n; ++i) {
   128     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   129     // }
   130 
   131     // radixSort(data2.begin(), data2.end(), negate);
   132     // for (int i = 0; i < n; ++i) {
   133     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   134     // }
   135 
   136   }
   137 
   138   {
   139     std::vector<unsigned char> data1(n);
   140     generateCharSequence(n, data1);
   141 
   142     std::vector<unsigned char> data2(data1);
   143     std::sort(data1.begin(), data1.end());
   144 
   145     radixSort(data2.begin(), data2.end());
   146     for (int i = 0; i < n; ++i) {
   147       check(data1[i] == data2[i], "Test failed");
   148     }
   149 
   150   }
   151   {
   152     std::list<int> data1;
   153     generateIntSequence(n, data1);
   154 
   155     std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
   156 
   157     radixSort(data1.begin(), data1.end());
   158 
   159     check(isTheSame(data1,data2), "Test failed");
   160 
   161 
   162     // radixSort(data2.begin(), data2.end(), Negate());
   163     // check(isTheSame(data1,data2), "Test failed");
   164     // for (int i = 0; i < n; ++i) {
   165     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   166     // }
   167 
   168     // radixSort(data2.begin(), data2.end(), negate);
   169     // for (int i = 0; i < n; ++i) {
   170     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   171     // }
   172 
   173   }
   174 
   175   {
   176     std::list<unsigned char> data1(n);
   177     generateCharSequence(n, data1);
   178 
   179     std::list<unsigned char> data2(listsort<std::list<unsigned char> >
   180                                    (data1.begin(),
   181                                     data1.end()));
   182 
   183     radixSort(data1.begin(), data1.end());
   184     check(isTheSame(data1,data2), "Test failed");
   185 
   186   }
   187 }
   188 
   189 
   190 void checkStableRadixSort() {
   191   {
   192     std::vector<int> data1;
   193     generateIntSequence(n, data1);
   194 
   195     std::vector<int> data2(data1);
   196     std::sort(data1.begin(), data1.end());
   197 
   198     stableRadixSort(data2.begin(), data2.end());
   199     for (int i = 0; i < n; ++i) {
   200       check(data1[i] == data2[i], "Test failed");
   201     }
   202 
   203     stableRadixSort(data2.begin(), data2.end(), Negate());
   204     for (int i = 0; i < n; ++i) {
   205       check(data1[i] == data2[n - 1 - i], "Test failed");
   206     }
   207 
   208     stableRadixSort(data2.begin(), data2.end(), negate);
   209     for (int i = 0; i < n; ++i) {
   210       check(data1[i] == data2[n - 1 - i], "Test failed");
   211     }
   212   }
   213 
   214   {
   215     std::vector<unsigned char> data1(n);
   216     generateCharSequence(n, data1);
   217 
   218     std::vector<unsigned char> data2(data1);
   219     std::sort(data1.begin(), data1.end());
   220 
   221     radixSort(data2.begin(), data2.end());
   222     for (int i = 0; i < n; ++i) {
   223       check(data1[i] == data2[i], "Test failed");
   224     }
   225 
   226   }
   227   {
   228     std::list<int> data1;
   229     generateIntSequence(n, data1);
   230 
   231     std::list<int> data2(listsort<std::list<int> >(data1.begin(),
   232                                                    data1.end()));
   233     stableRadixSort(data1.begin(), data1.end());
   234     check(isTheSame(data1,data2), "Test failed");
   235 
   236     // stableRadixSort(data2.begin(), data2.end(), Negate());
   237     // for (int i = 0; i < n; ++i) {
   238     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   239     // }
   240 
   241     // stableRadixSort(data2.begin(), data2.end(), negate);
   242     // for (int i = 0; i < n; ++i) {
   243     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   244     // }
   245   }
   246 
   247   {
   248     std::list<unsigned char> data1(n);
   249     generateCharSequence(n, data1);
   250 
   251     std::list<unsigned char> data2(listsort<std::list<unsigned char> >
   252                                    (data1.begin(),
   253                                     data1.end()));
   254     radixSort(data1.begin(), data1.end());
   255     check(isTheSame(data1,data2), "Test failed");
   256 
   257   }
   258 }
   259 
   260 int main() {
   261 
   262   checkRadixSort();
   263   checkStableRadixSort();
   264 
   265   return 0;
   266 }