Changeset 1211:1bafdbd2fc46 in lemon

Timestamp:

03/20/10 11:03:12 (14 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:

• test/radix_sort_test.cc (modified) (5 diffs)

test/radix_sort_test.cc

@@ -26 +26 @@
 
 #include <vector>
+#include <list>
 #include <algorithm>
 
@@ -40 +41 @@
 int negate(int a) { return - a; }
 
-
-void generateIntSequence(int n, std::vector<int>& data) {
+template<class T>
+bool isTheSame(T &a, T&b)
+{
+  typename T::iterator ai=a.begin();
+  typename T::iterator bi=b.begin();
+  for(;ai!=a.end()||bi!=b.end();++ai,++bi)
+    if(*ai!=*bi) return false;
+  return ai==a.end()&&bi==b.end();
+}
+
+template<class T>
+T listsort(typename T::iterator b, typename T::iterator e)
+{ 
+  if(b==e) return T();
+  typename T::iterator bn=b;
+  if(++bn==e) {
+    T l;
+    l.push_back(*b);
+    return l;
+  }
+  typename T::iterator m=b;
+  bool x=false;
+  for(typename T::iterator i=b;i!=e;++i,x=!x)
+    if(x) ++m;
+  T l1(listsort<T>(b,m));
+  T l2(listsort<T>(m,e));
+  T l;
+  while((!l1.empty())&&(!l2.empty()))
+    if(l1.front()<=l2.front())
+      {
+        l.push_back(l1.front());
+        l1.pop_front();
+      }
+    else {
+      l.push_back(l2.front());
+      l2.pop_front();
+    }
+  while(!l1.empty())
+    {
+      l.push_back(l1.front());
+      l1.pop_front();
+    }
+  while(!l2.empty())
+    {
+      l.push_back(l2.front());
+      l2.pop_front();
+    }
+  return l;
+}
+
+template<class T>
+void generateIntSequence(int n, T & data) {
   int prime = 9973;
   int root = 136, value = 1;
@@ -50 +101 @@
 }
 
-void generateCharSequence(int n, std::vector<unsigned char>& data) {
+template<class T>
+void generateCharSequence(int n, T & data) {
   int prime = 251;
   int root = 3, value = root;
@@ -72 +124 @@
     }
 
-    radixSort(data2.begin(), data2.end(), Negate());
+    // radixSort(data2.begin(), data2.end(), Negate());
+    // for (int i = 0; i < n; ++i) {
+    //   check(data1[i] == data2[n - 1 - i], "Test failed");
+    // }
+
+    // radixSort(data2.begin(), data2.end(), negate);
+    // for (int i = 0; i < n; ++i) {
+    //   check(data1[i] == data2[n - 1 - i], "Test failed");
+    // }
+
+  }
+
+  {
+    std::vector<unsigned char> data1(n);
+    generateCharSequence(n, data1);
+
+    std::vector<unsigned char> data2(data1);
+    std::sort(data1.begin(), data1.end());
+
+    radixSort(data2.begin(), data2.end());
+    for (int i = 0; i < n; ++i) {
+      check(data1[i] == data2[i], "Test failed");
+    }
+
+  }
+  {
+    std::list<int> data1;
+    generateIntSequence(n, data1);
+
+    std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
+
+    radixSort(data1.begin(), data1.end());
+
+    check(isTheSame(data1,data2), "Test failed");
+
+
+    // radixSort(data2.begin(), data2.end(), Negate());
+    // check(isTheSame(data1,data2), "Test failed");
+    // for (int i = 0; i < n; ++i) {
+    //   check(data1[i] == data2[n - 1 - i], "Test failed");
+    // }
+
+    // radixSort(data2.begin(), data2.end(), negate);
+    // for (int i = 0; i < n; ++i) {
+    //   check(data1[i] == data2[n - 1 - i], "Test failed");
+    // }
+
+  }
+
+  {
+    std::list<unsigned char> data1(n);
+    generateCharSequence(n, data1);
+
+    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
+                                   (data1.begin(),
+                                    data1.end()));
+
+    radixSort(data1.begin(), data1.end());
+    check(isTheSame(data1,data2), "Test failed");
+
+  }
+}
+
+
+void checkStableRadixSort() {
+  {
+    std::vector<int> data1;
+    generateIntSequence(n, data1);
+
+    std::vector<int> data2(data1);
+    std::sort(data1.begin(), data1.end());
+
+    stableRadixSort(data2.begin(), data2.end());
+    for (int i = 0; i < n; ++i) {
+      check(data1[i] == data2[i], "Test failed");
+    }
+
+    stableRadixSort(data2.begin(), data2.end(), Negate());
     for (int i = 0; i < n; ++i) {
       check(data1[i] == data2[n - 1 - i], "Test failed");
     }
 
-    radixSort(data2.begin(), data2.end(), negate);
+    stableRadixSort(data2.begin(), data2.end(), negate);
     for (int i = 0; i < n; ++i) {
       check(data1[i] == data2[n - 1 - i], "Test failed");
     }
-
   }
 
@@ -97 +225 @@
 
   }
-}
-
-
-void checkStableRadixSort() {
-  {
-    std::vector<int> data1;
-    generateIntSequence(n, data1);
-
-    std::vector<int> data2(data1);
-    std::sort(data1.begin(), data1.end());
-
-    stableRadixSort(data2.begin(), data2.end());
-    for (int i = 0; i < n; ++i) {
-      check(data1[i] == data2[i], "Test failed");
-    }
-
-    stableRadixSort(data2.begin(), data2.end(), Negate());
-    for (int i = 0; i < n; ++i) {
-      check(data1[i] == data2[n - 1 - i], "Test failed");
-    }
-
-    stableRadixSort(data2.begin(), data2.end(), negate);
-    for (int i = 0; i < n; ++i) {
-      check(data1[i] == data2[n - 1 - i], "Test failed");
-    }
-  }
-
-  {
-    std::vector<unsigned char> data1(n);
-    generateCharSequence(n, data1);
-
-    std::vector<unsigned char> data2(data1);
-    std::sort(data1.begin(), data1.end());
-
-    radixSort(data2.begin(), data2.end());
-    for (int i = 0; i < n; ++i) {
-      check(data1[i] == data2[i], "Test failed");
-    }
+  {
+    std::list<int> data1;
+    generateIntSequence(n, data1);
+
+    std::list<int> data2(listsort<std::list<int> >(data1.begin(),
+                                                   data1.end()));
+    stableRadixSort(data1.begin(), data1.end());
+    check(isTheSame(data1,data2), "Test failed");
+
+    // stableRadixSort(data2.begin(), data2.end(), Negate());
+    // for (int i = 0; i < n; ++i) {
+    //   check(data1[i] == data2[n - 1 - i], "Test failed");
+    // }
+
+    // stableRadixSort(data2.begin(), data2.end(), negate);
+    // for (int i = 0; i < n; ++i) {
+    //   check(data1[i] == data2[n - 1 - i], "Test failed");
+    // }
+  }
+
+  {
+    std::list<unsigned char> data1(n);
+    generateCharSequence(n, data1);
+
+    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
+                                   (data1.begin(),
+                                    data1.end()));
+    radixSort(data1.begin(), data1.end());
+    check(isTheSame(data1,data2), "Test failed");
 
   }