1.1 --- a/test/radix_sort_test.cc	Fri Mar 19 18:23:47 2010 +0100
     1.2 +++ b/test/radix_sort_test.cc	Sat Mar 20 11:03:12 2010 +0100
     1.3 @@ -25,6 +25,7 @@
     1.4  #include "test_tools.h"
     1.5  
     1.6  #include <vector>
     1.7 +#include <list>
     1.8  #include <algorithm>
     1.9  
    1.10  using namespace lemon;
    1.11 @@ -39,8 +40,58 @@
    1.12  
    1.13  int negate(int a) { return - a; }
    1.14  
    1.15 +template<class T>
    1.16 +bool isTheSame(T &a, T&b)
    1.17 +{
    1.18 +  typename T::iterator ai=a.begin();
    1.19 +  typename T::iterator bi=b.begin();
    1.20 +  for(;ai!=a.end()||bi!=b.end();++ai,++bi)
    1.21 +    if(*ai!=*bi) return false;
    1.22 +  return ai==a.end()&&bi==b.end();
    1.23 +}
    1.24  
    1.25 -void generateIntSequence(int n, std::vector<int>& data) {
    1.26 +template<class T>
    1.27 +T listsort(typename T::iterator b, typename T::iterator e)
    1.28 +{ 
    1.29 +  if(b==e) return T();
    1.30 +  typename T::iterator bn=b;
    1.31 +  if(++bn==e) {
    1.32 +    T l;
    1.33 +    l.push_back(*b);
    1.34 +    return l;
    1.35 +  }
    1.36 +  typename T::iterator m=b;
    1.37 +  bool x=false;
    1.38 +  for(typename T::iterator i=b;i!=e;++i,x=!x)
    1.39 +    if(x) ++m;
    1.40 +  T l1(listsort<T>(b,m));
    1.41 +  T l2(listsort<T>(m,e));
    1.42 +  T l;
    1.43 +  while((!l1.empty())&&(!l2.empty()))
    1.44 +    if(l1.front()<=l2.front())
    1.45 +      {
    1.46 +        l.push_back(l1.front());
    1.47 +        l1.pop_front();
    1.48 +      }
    1.49 +    else {
    1.50 +      l.push_back(l2.front());
    1.51 +      l2.pop_front();
    1.52 +    }
    1.53 +  while(!l1.empty())
    1.54 +    {
    1.55 +      l.push_back(l1.front());
    1.56 +      l1.pop_front();
    1.57 +    }
    1.58 +  while(!l2.empty())
    1.59 +    {
    1.60 +      l.push_back(l2.front());
    1.61 +      l2.pop_front();
    1.62 +    }
    1.63 +  return l;
    1.64 +}
    1.65 +
    1.66 +template<class T>
    1.67 +void generateIntSequence(int n, T & data) {
    1.68    int prime = 9973;
    1.69    int root = 136, value = 1;
    1.70    for (int i = 0; i < n; ++i) {
    1.71 @@ -49,7 +100,8 @@
    1.72    }
    1.73  }
    1.74  
    1.75 -void generateCharSequence(int n, std::vector<unsigned char>& data) {
    1.76 +template<class T>
    1.77 +void generateCharSequence(int n, T & data) {
    1.78    int prime = 251;
    1.79    int root = 3, value = root;
    1.80    for (int i = 0; i < n; ++i) {
    1.81 @@ -71,15 +123,15 @@
    1.82        check(data1[i] == data2[i], "Test failed");
    1.83      }
    1.84  
    1.85 -    radixSort(data2.begin(), data2.end(), Negate());
    1.86 -    for (int i = 0; i < n; ++i) {
    1.87 -      check(data1[i] == data2[n - 1 - i], "Test failed");
    1.88 -    }
    1.89 +    // radixSort(data2.begin(), data2.end(), Negate());
    1.90 +    // for (int i = 0; i < n; ++i) {
    1.91 +    //   check(data1[i] == data2[n - 1 - i], "Test failed");
    1.92 +    // }
    1.93  
    1.94 -    radixSort(data2.begin(), data2.end(), negate);
    1.95 -    for (int i = 0; i < n; ++i) {
    1.96 -      check(data1[i] == data2[n - 1 - i], "Test failed");
    1.97 -    }
    1.98 +    // radixSort(data2.begin(), data2.end(), negate);
    1.99 +    // for (int i = 0; i < n; ++i) {
   1.100 +    //   check(data1[i] == data2[n - 1 - i], "Test failed");
   1.101 +    // }
   1.102  
   1.103    }
   1.104  
   1.105 @@ -96,6 +148,42 @@
   1.106      }
   1.107  
   1.108    }
   1.109 +  {
   1.110 +    std::list<int> data1;
   1.111 +    generateIntSequence(n, data1);
   1.112 +
   1.113 +    std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
   1.114 +
   1.115 +    radixSort(data1.begin(), data1.end());
   1.116 +
   1.117 +    check(isTheSame(data1,data2), "Test failed");
   1.118 +
   1.119 +
   1.120 +    // radixSort(data2.begin(), data2.end(), Negate());
   1.121 +    // check(isTheSame(data1,data2), "Test failed");
   1.122 +    // for (int i = 0; i < n; ++i) {
   1.123 +    //   check(data1[i] == data2[n - 1 - i], "Test failed");
   1.124 +    // }
   1.125 +
   1.126 +    // radixSort(data2.begin(), data2.end(), negate);
   1.127 +    // for (int i = 0; i < n; ++i) {
   1.128 +    //   check(data1[i] == data2[n - 1 - i], "Test failed");
   1.129 +    // }
   1.130 +
   1.131 +  }
   1.132 +
   1.133 +  {
   1.134 +    std::list<unsigned char> data1(n);
   1.135 +    generateCharSequence(n, data1);
   1.136 +
   1.137 +    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
   1.138 +                                   (data1.begin(),
   1.139 +                                    data1.end()));
   1.140 +
   1.141 +    radixSort(data1.begin(), data1.end());
   1.142 +    check(isTheSame(data1,data2), "Test failed");
   1.143 +
   1.144 +  }
   1.145  }
   1.146  
   1.147  
   1.148 @@ -136,6 +224,37 @@
   1.149      }
   1.150  
   1.151    }
   1.152 +  {
   1.153 +    std::list<int> data1;
   1.154 +    generateIntSequence(n, data1);
   1.155 +
   1.156 +    std::list<int> data2(listsort<std::list<int> >(data1.begin(),
   1.157 +                                                   data1.end()));
   1.158 +    stableRadixSort(data1.begin(), data1.end());
   1.159 +    check(isTheSame(data1,data2), "Test failed");
   1.160 +
   1.161 +    // stableRadixSort(data2.begin(), data2.end(), Negate());
   1.162 +    // for (int i = 0; i < n; ++i) {
   1.163 +    //   check(data1[i] == data2[n - 1 - i], "Test failed");
   1.164 +    // }
   1.165 +
   1.166 +    // stableRadixSort(data2.begin(), data2.end(), negate);
   1.167 +    // for (int i = 0; i < n; ++i) {
   1.168 +    //   check(data1[i] == data2[n - 1 - i], "Test failed");
   1.169 +    // }
   1.170 +  }
   1.171 +
   1.172 +  {
   1.173 +    std::list<unsigned char> data1(n);
   1.174 +    generateCharSequence(n, data1);
   1.175 +
   1.176 +    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
   1.177 +                                   (data1.begin(),
   1.178 +                                    data1.end()));
   1.179 +    radixSort(data1.begin(), data1.end());
   1.180 +    check(isTheSame(data1,data2), "Test failed");
   1.181 +
   1.182 +  }
   1.183  }
   1.184  
   1.185  int main() {