test/radix_sort_test.cc
changeset 1046 387483bf0a56
parent 444 ba49101c9b07
child 1092 dceba191c00d
equal deleted inserted replaced
3:faa3321b7e85 4:ae3c7e3ac6c0
    23 #include <lemon/math.h>
    23 #include <lemon/math.h>
    24 
    24 
    25 #include "test_tools.h"
    25 #include "test_tools.h"
    26 
    26 
    27 #include <vector>
    27 #include <vector>
       
    28 #include <list>
    28 #include <algorithm>
    29 #include <algorithm>
    29 
    30 
    30 using namespace lemon;
    31 using namespace lemon;
    31 
    32 
    32 static const int n = 10000;
    33 static const int n = 10000;
    37   int operator()(int a) { return - a; }
    38   int operator()(int a) { return - a; }
    38 };
    39 };
    39 
    40 
    40 int negate(int a) { return - a; }
    41 int negate(int a) { return - a; }
    41 
    42 
    42 
    43 template<class T>
    43 void generateIntSequence(int n, std::vector<int>& data) {
    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) {
    44   int prime = 9973;
    95   int prime = 9973;
    45   int root = 136, value = 1;
    96   int root = 136, value = 1;
    46   for (int i = 0; i < n; ++i) {
    97   for (int i = 0; i < n; ++i) {
    47     data.push_back(value - prime / 2);
    98     data.push_back(value - prime / 2);
    48     value = (value * root) % prime;
    99     value = (value * root) % prime;
    49   }
   100   }
    50 }
   101 }
    51 
   102 
    52 void generateCharSequence(int n, std::vector<unsigned char>& data) {
   103 template<class T>
       
   104 void generateCharSequence(int n, T & data) {
    53   int prime = 251;
   105   int prime = 251;
    54   int root = 3, value = root;
   106   int root = 3, value = root;
    55   for (int i = 0; i < n; ++i) {
   107   for (int i = 0; i < n; ++i) {
    56     data.push_back(static_cast<unsigned char>(value));
   108     data.push_back(static_cast<unsigned char>(value));
    57     value = (value * root) % prime;
   109     value = (value * root) % prime;
    69     radixSort(data2.begin(), data2.end());
   121     radixSort(data2.begin(), data2.end());
    70     for (int i = 0; i < n; ++i) {
   122     for (int i = 0; i < n; ++i) {
    71       check(data1[i] == data2[i], "Test failed");
   123       check(data1[i] == data2[i], "Test failed");
    72     }
   124     }
    73 
   125 
    74     radixSort(data2.begin(), data2.end(), Negate());
   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());
    75     for (int i = 0; i < n; ++i) {
   204     for (int i = 0; i < n; ++i) {
    76       check(data1[i] == data2[n - 1 - i], "Test failed");
   205       check(data1[i] == data2[n - 1 - i], "Test failed");
    77     }
   206     }
    78 
   207 
    79     radixSort(data2.begin(), data2.end(), negate);
   208     stableRadixSort(data2.begin(), data2.end(), negate);
    80     for (int i = 0; i < n; ++i) {
   209     for (int i = 0; i < n; ++i) {
    81       check(data1[i] == data2[n - 1 - i], "Test failed");
   210       check(data1[i] == data2[n - 1 - i], "Test failed");
    82     }
   211     }
    83 
       
    84   }
   212   }
    85 
   213 
    86   {
   214   {
    87     std::vector<unsigned char> data1(n);
   215     std::vector<unsigned char> data1(n);
    88     generateCharSequence(n, data1);
   216     generateCharSequence(n, data1);
    94     for (int i = 0; i < n; ++i) {
   222     for (int i = 0; i < n; ++i) {
    95       check(data1[i] == data2[i], "Test failed");
   223       check(data1[i] == data2[i], "Test failed");
    96     }
   224     }
    97 
   225 
    98   }
   226   }
    99 }
   227   {
   100 
   228     std::list<int> data1;
   101 
   229     generateIntSequence(n, data1);
   102 void checkStableRadixSort() {
   230 
   103   {
   231     std::list<int> data2(listsort<std::list<int> >(data1.begin(),
   104     std::vector<int> data1;
   232                                                    data1.end()));
   105     generateIntSequence(n, data1);
   233     stableRadixSort(data1.begin(), data1.end());
   106 
   234     check(isTheSame(data1,data2), "Test failed");
   107     std::vector<int> data2(data1);
   235 
   108     std::sort(data1.begin(), data1.end());
   236     // stableRadixSort(data2.begin(), data2.end(), Negate());
   109 
   237     // for (int i = 0; i < n; ++i) {
   110     stableRadixSort(data2.begin(), data2.end());
   238     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   111     for (int i = 0; i < n; ++i) {
   239     // }
   112       check(data1[i] == data2[i], "Test failed");
   240 
   113     }
   241     // stableRadixSort(data2.begin(), data2.end(), negate);
   114 
   242     // for (int i = 0; i < n; ++i) {
   115     stableRadixSort(data2.begin(), data2.end(), Negate());
   243     //   check(data1[i] == data2[n - 1 - i], "Test failed");
   116     for (int i = 0; i < n; ++i) {
   244     // }
   117       check(data1[i] == data2[n - 1 - i], "Test failed");
   245   }
   118     }
   246 
   119 
   247   {
   120     stableRadixSort(data2.begin(), data2.end(), negate);
   248     std::list<unsigned char> data1(n);
   121     for (int i = 0; i < n; ++i) {
   249     generateCharSequence(n, data1);
   122       check(data1[i] == data2[n - 1 - i], "Test failed");
   250 
   123     }
   251     std::list<unsigned char> data2(listsort<std::list<unsigned char> >
   124   }
   252                                    (data1.begin(),
   125 
   253                                     data1.end()));
   126   {
   254     radixSort(data1.begin(), data1.end());
   127     std::vector<unsigned char> data1(n);
   255     check(isTheSame(data1,data2), "Test failed");
   128     generateCharSequence(n, data1);
       
   129 
       
   130     std::vector<unsigned char> data2(data1);
       
   131     std::sort(data1.begin(), data1.end());
       
   132 
       
   133     radixSort(data2.begin(), data2.end());
       
   134     for (int i = 0; i < n; ++i) {
       
   135       check(data1[i] == data2[i], "Test failed");
       
   136     }
       
   137 
   256 
   138   }
   257   }
   139 }
   258 }
   140 
   259 
   141 int main() {
   260 int main() {