alpar@465: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@464:  *
alpar@465:  * This file is a part of LEMON, a generic C++ optimization library.
deba@464:  *
alpar@1270:  * Copyright (C) 2003-2013
deba@464:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@464:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@464:  *
deba@464:  * Permission to use, modify and distribute this software is granted
deba@464:  * provided that this copyright notice appears in all copies. For
deba@464:  * precise terms see the accompanying LICENSE file.
deba@464:  *
deba@464:  * This software is provided "AS IS" with no warranty of any kind,
deba@464:  * express or implied, and with no claim as to its suitability for any
deba@464:  * purpose.
deba@464:  *
deba@464:  */
deba@464: 
alpar@1341: #include <lemon/core.h>
alpar@1341: 
deba@464: #include <lemon/time_measure.h>
deba@464: #include <lemon/smart_graph.h>
deba@464: #include <lemon/maps.h>
deba@464: #include <lemon/radix_sort.h>
deba@464: #include <lemon/math.h>
deba@464: 
deba@464: #include "test_tools.h"
deba@464: 
deba@464: #include <vector>
alpar@1211: #include <list>
deba@464: #include <algorithm>
deba@464: 
deba@464: using namespace lemon;
deba@464: 
deba@464: static const int n = 10000;
deba@464: 
deba@464: struct Negate {
deba@464:   typedef int argument_type;
deba@464:   typedef int result_type;
deba@464:   int operator()(int a) { return - a; }
deba@464: };
deba@464: 
deba@464: int negate(int a) { return - a; }
deba@464: 
alpar@1211: template<class T>
alpar@1211: bool isTheSame(T &a, T&b)
alpar@1211: {
alpar@1211:   typename T::iterator ai=a.begin();
alpar@1211:   typename T::iterator bi=b.begin();
alpar@1211:   for(;ai!=a.end()||bi!=b.end();++ai,++bi)
alpar@1211:     if(*ai!=*bi) return false;
alpar@1211:   return ai==a.end()&&bi==b.end();
alpar@1211: }
deba@464: 
alpar@1211: template<class T>
alpar@1211: T listsort(typename T::iterator b, typename T::iterator e)
alpar@1270: {
alpar@1211:   if(b==e) return T();
alpar@1211:   typename T::iterator bn=b;
alpar@1211:   if(++bn==e) {
alpar@1211:     T l;
alpar@1211:     l.push_back(*b);
alpar@1211:     return l;
alpar@1211:   }
alpar@1211:   typename T::iterator m=b;
alpar@1211:   bool x=false;
alpar@1211:   for(typename T::iterator i=b;i!=e;++i,x=!x)
alpar@1211:     if(x) ++m;
alpar@1211:   T l1(listsort<T>(b,m));
alpar@1211:   T l2(listsort<T>(m,e));
alpar@1211:   T l;
alpar@1211:   while((!l1.empty())&&(!l2.empty()))
alpar@1211:     if(l1.front()<=l2.front())
alpar@1211:       {
alpar@1211:         l.push_back(l1.front());
alpar@1211:         l1.pop_front();
alpar@1211:       }
alpar@1211:     else {
alpar@1211:       l.push_back(l2.front());
alpar@1211:       l2.pop_front();
alpar@1211:     }
alpar@1211:   while(!l1.empty())
alpar@1211:     {
alpar@1211:       l.push_back(l1.front());
alpar@1211:       l1.pop_front();
alpar@1211:     }
alpar@1211:   while(!l2.empty())
alpar@1211:     {
alpar@1211:       l.push_back(l2.front());
alpar@1211:       l2.pop_front();
alpar@1211:     }
alpar@1211:   return l;
alpar@1211: }
alpar@1211: 
alpar@1211: template<class T>
alpar@1211: void generateIntSequence(int n, T & data) {
deba@464:   int prime = 9973;
deba@464:   int root = 136, value = 1;
deba@464:   for (int i = 0; i < n; ++i) {
deba@464:     data.push_back(value - prime / 2);
deba@464:     value = (value * root) % prime;
deba@464:   }
deba@464: }
deba@464: 
alpar@1211: template<class T>
alpar@1211: void generateCharSequence(int n, T & data) {
deba@464:   int prime = 251;
deba@464:   int root = 3, value = root;
deba@464:   for (int i = 0; i < n; ++i) {
deba@464:     data.push_back(static_cast<unsigned char>(value));
deba@464:     value = (value * root) % prime;
deba@464:   }
deba@464: }
deba@464: 
deba@464: void checkRadixSort() {
deba@464:   {
deba@464:     std::vector<int> data1;
deba@464:     generateIntSequence(n, data1);
deba@464: 
deba@464:     std::vector<int> data2(data1);
deba@464:     std::sort(data1.begin(), data1.end());
deba@464: 
deba@464:     radixSort(data2.begin(), data2.end());
deba@464:     for (int i = 0; i < n; ++i) {
deba@464:       check(data1[i] == data2[i], "Test failed");
deba@464:     }
deba@464: 
alpar@1211:     // radixSort(data2.begin(), data2.end(), Negate());
alpar@1211:     // for (int i = 0; i < n; ++i) {
alpar@1211:     //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1211:     // }
deba@464: 
alpar@1211:     // radixSort(data2.begin(), data2.end(), negate);
alpar@1211:     // for (int i = 0; i < n; ++i) {
alpar@1211:     //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1211:     // }
deba@464: 
alpar@465:   }
alpar@465: 
deba@464:   {
deba@464:     std::vector<unsigned char> data1(n);
deba@464:     generateCharSequence(n, data1);
deba@464: 
deba@464:     std::vector<unsigned char> data2(data1);
deba@464:     std::sort(data1.begin(), data1.end());
deba@464: 
deba@464:     radixSort(data2.begin(), data2.end());
deba@464:     for (int i = 0; i < n; ++i) {
deba@464:       check(data1[i] == data2[i], "Test failed");
deba@464:     }
deba@464: 
deba@464:   }
alpar@1211:   {
alpar@1211:     std::list<int> data1;
alpar@1211:     generateIntSequence(n, data1);
alpar@1211: 
alpar@1211:     std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
alpar@1211: 
alpar@1211:     radixSort(data1.begin(), data1.end());
alpar@1211: 
alpar@1211:     check(isTheSame(data1,data2), "Test failed");
alpar@1211: 
alpar@1211: 
alpar@1211:     // radixSort(data2.begin(), data2.end(), Negate());
alpar@1211:     // check(isTheSame(data1,data2), "Test failed");
alpar@1211:     // for (int i = 0; i < n; ++i) {
alpar@1211:     //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1211:     // }
alpar@1211: 
alpar@1211:     // radixSort(data2.begin(), data2.end(), negate);
alpar@1211:     // for (int i = 0; i < n; ++i) {
alpar@1211:     //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1211:     // }
alpar@1211: 
alpar@1211:   }
alpar@1211: 
alpar@1211:   {
alpar@1211:     std::list<unsigned char> data1(n);
alpar@1211:     generateCharSequence(n, data1);
alpar@1211: 
alpar@1211:     std::list<unsigned char> data2(listsort<std::list<unsigned char> >
alpar@1211:                                    (data1.begin(),
alpar@1211:                                     data1.end()));
alpar@1211: 
alpar@1211:     radixSort(data1.begin(), data1.end());
alpar@1211:     check(isTheSame(data1,data2), "Test failed");
alpar@1211: 
alpar@1211:   }
deba@464: }
deba@464: 
deba@464: 
deba@466: void checkStableRadixSort() {
deba@464:   {
deba@464:     std::vector<int> data1;
deba@464:     generateIntSequence(n, data1);
deba@464: 
deba@464:     std::vector<int> data2(data1);
deba@464:     std::sort(data1.begin(), data1.end());
deba@464: 
deba@466:     stableRadixSort(data2.begin(), data2.end());
deba@464:     for (int i = 0; i < n; ++i) {
deba@464:       check(data1[i] == data2[i], "Test failed");
deba@464:     }
deba@464: 
deba@466:     stableRadixSort(data2.begin(), data2.end(), Negate());
deba@464:     for (int i = 0; i < n; ++i) {
deba@464:       check(data1[i] == data2[n - 1 - i], "Test failed");
deba@464:     }
deba@464: 
deba@466:     stableRadixSort(data2.begin(), data2.end(), negate);
deba@464:     for (int i = 0; i < n; ++i) {
deba@464:       check(data1[i] == data2[n - 1 - i], "Test failed");
deba@464:     }
alpar@465:   }
deba@464: 
deba@464:   {
deba@464:     std::vector<unsigned char> data1(n);
deba@464:     generateCharSequence(n, data1);
deba@464: 
deba@464:     std::vector<unsigned char> data2(data1);
deba@464:     std::sort(data1.begin(), data1.end());
deba@464: 
deba@464:     radixSort(data2.begin(), data2.end());
deba@464:     for (int i = 0; i < n; ++i) {
deba@464:       check(data1[i] == data2[i], "Test failed");
deba@464:     }
deba@464: 
deba@464:   }
alpar@1211:   {
alpar@1211:     std::list<int> data1;
alpar@1211:     generateIntSequence(n, data1);
alpar@1211: 
alpar@1211:     std::list<int> data2(listsort<std::list<int> >(data1.begin(),
alpar@1211:                                                    data1.end()));
alpar@1211:     stableRadixSort(data1.begin(), data1.end());
alpar@1211:     check(isTheSame(data1,data2), "Test failed");
alpar@1211: 
alpar@1211:     // stableRadixSort(data2.begin(), data2.end(), Negate());
alpar@1211:     // for (int i = 0; i < n; ++i) {
alpar@1211:     //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1211:     // }
alpar@1211: 
alpar@1211:     // stableRadixSort(data2.begin(), data2.end(), negate);
alpar@1211:     // for (int i = 0; i < n; ++i) {
alpar@1211:     //   check(data1[i] == data2[n - 1 - i], "Test failed");
alpar@1211:     // }
alpar@1211:   }
alpar@1211: 
alpar@1211:   {
alpar@1211:     std::list<unsigned char> data1(n);
alpar@1211:     generateCharSequence(n, data1);
alpar@1211: 
alpar@1211:     std::list<unsigned char> data2(listsort<std::list<unsigned char> >
alpar@1211:                                    (data1.begin(),
alpar@1211:                                     data1.end()));
alpar@1211:     radixSort(data1.begin(), data1.end());
alpar@1211:     check(isTheSame(data1,data2), "Test failed");
alpar@1211: 
alpar@1211:   }
deba@464: }
deba@464: 
deba@464: int main() {
deba@464: 
alpar@465:   checkRadixSort();
deba@466:   checkStableRadixSort();
deba@464: 
deba@464:   return 0;
deba@464: }