COIN-OR::LEMON - Graph Library

Changeset 1211:1bafdbd2fc46 in lemon


Ignore:
Timestamp:
03/20/10 11:03:12 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
1212:15d7c5eadaca, 1213:4e8787627db3, 1214:387483bf0a56, 1240:ee9bac10f58e
Phase:
public
Message:

More tests for radixSort() (#362)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/radix_sort_test.cc

    r467 r1211  
    2626
    2727#include <vector>
     28#include <list>
    2829#include <algorithm>
    2930
     
    4041int negate(int a) { return - a; }
    4142
    42 
    43 void generateIntSequence(int n, std::vector<int>& data) {
     43template<class T>
     44bool 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
     53template<class T>
     54T 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
     93template<class T>
     94void generateIntSequence(int n, T & data) {
    4495  int prime = 9973;
    4596  int root = 136, value = 1;
     
    50101}
    51102
    52 void generateCharSequence(int n, std::vector<unsigned char>& data) {
     103template<class T>
     104void generateCharSequence(int n, T & data) {
    53105  int prime = 251;
    54106  int root = 3, value = root;
     
    72124    }
    73125
    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
     190void 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());
    75204    for (int i = 0; i < n; ++i) {
    76205      check(data1[i] == data2[n - 1 - i], "Test failed");
    77206    }
    78207
    79     radixSort(data2.begin(), data2.end(), negate);
     208    stableRadixSort(data2.begin(), data2.end(), negate);
    80209    for (int i = 0; i < n; ++i) {
    81210      check(data1[i] == data2[n - 1 - i], "Test failed");
    82211    }
    83 
    84212  }
    85213
     
    97225
    98226  }
    99 }
    100 
    101 
    102 void checkStableRadixSort() {
    103   {
    104     std::vector<int> data1;
    105     generateIntSequence(n, data1);
    106 
    107     std::vector<int> data2(data1);
    108     std::sort(data1.begin(), data1.end());
    109 
    110     stableRadixSort(data2.begin(), data2.end());
    111     for (int i = 0; i < n; ++i) {
    112       check(data1[i] == data2[i], "Test failed");
    113     }
    114 
    115     stableRadixSort(data2.begin(), data2.end(), Negate());
    116     for (int i = 0; i < n; ++i) {
    117       check(data1[i] == data2[n - 1 - i], "Test failed");
    118     }
    119 
    120     stableRadixSort(data2.begin(), data2.end(), negate);
    121     for (int i = 0; i < n; ++i) {
    122       check(data1[i] == data2[n - 1 - i], "Test failed");
    123     }
    124   }
    125 
    126   {
    127     std::vector<unsigned char> data1(n);
    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     }
     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");
    137256
    138257  }
Note: See TracChangeset for help on using the changeset viewer.