lemon: test/radix_sort_test.cc@1de908281369

     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library.

     4  *

     5  * Copyright (C) 2003-2013

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #include <lemon/core.h>

    21 #include <lemon/time_measure.h>

    22 #include <lemon/smart_graph.h>

    23 #include <lemon/maps.h>

    24 #include <lemon/radix_sort.h>

    25 #include <lemon/math.h>

    27 #include "test_tools.h"

    29 #include <vector>

    30 #include <list>

    31 #include <algorithm>

    33 using namespace lemon;

    35 static const int n = 10000;

    37 struct Negate {

    38   typedef int argument_type;

    39   typedef int result_type;

    40   int operator()(int a) { return - a; }

    41 };

    43 int negate(int a) { return - a; }

    45 template<class T>

    46 bool isTheSame(T &a, T&b)

    47 {

    48   typename T::iterator ai=a.begin();

    49   typename T::iterator bi=b.begin();

    50   for(;ai!=a.end()||bi!=b.end();++ai,++bi)

    51     if(*ai!=*bi) return false;

    52   return ai==a.end()&&bi==b.end();

    53 }

    55 template<class T>

    56 T listsort(typename T::iterator b, typename T::iterator e)

    57 {

    58   if(b==e) return T();

    59   typename T::iterator bn=b;

    60   if(++bn==e) {

    61     T l;

    62     l.push_back(*b);

    63     return l;

    64   }

    65   typename T::iterator m=b;

    66   bool x=false;

    67   for(typename T::iterator i=b;i!=e;++i,x=!x)

    68     if(x) ++m;

    69   T l1(listsort<T>(b,m));

    70   T l2(listsort<T>(m,e));

    71   T l;

    72   while((!l1.empty())&&(!l2.empty()))

    73     if(l1.front()<=l2.front())

    74       {

    75         l.push_back(l1.front());

    76         l1.pop_front();

    77       }

    78     else {

    79       l.push_back(l2.front());

    80       l2.pop_front();

    81     }

    82   while(!l1.empty())

    83     {

    84       l.push_back(l1.front());

    85       l1.pop_front();

    86     }

    87   while(!l2.empty())

    88     {

    89       l.push_back(l2.front());

    90       l2.pop_front();

    91     }

    92   return l;

    93 }

    95 template<class T>

    96 void generateIntSequence(int n, T & data) {

    97   int prime = 9973;

    98   int root = 136, value = 1;

    99   for (int i = 0; i < n; ++i) {

   100     data.push_back(value - prime / 2);

   101     value = (value * root) % prime;

   102   }

   103 }

   105 template<class T>

   106 void generateCharSequence(int n, T & data) {

   107   int prime = 251;

   108   int root = 3, value = root;

   109   for (int i = 0; i < n; ++i) {

   110     data.push_back(static_cast<unsigned char>(value));

   111     value = (value * root) % prime;

   112   }

   113 }

   115 void checkRadixSort() {

   116   {

   117     std::vector<int> data1;

   118     generateIntSequence(n, data1);

   120     std::vector<int> data2(data1);

   121     std::sort(data1.begin(), data1.end());

   123     radixSort(data2.begin(), data2.end());

   124     for (int i = 0; i < n; ++i) {

   125       check(data1[i] == data2[i], "Test failed");

   126     }

   128     // radixSort(data2.begin(), data2.end(), Negate());

   129     // for (int i = 0; i < n; ++i) {

   130     //   check(data1[i] == data2[n - 1 - i], "Test failed");

   131     // }

   133     // radixSort(data2.begin(), data2.end(), negate);

   134     // for (int i = 0; i < n; ++i) {

   135     //   check(data1[i] == data2[n - 1 - i], "Test failed");

   136     // }

   138   }

   140   {

   141     std::vector<unsigned char> data1(n);

   142     generateCharSequence(n, data1);

   144     std::vector<unsigned char> data2(data1);

   145     std::sort(data1.begin(), data1.end());

   147     radixSort(data2.begin(), data2.end());

   148     for (int i = 0; i < n; ++i) {

   149       check(data1[i] == data2[i], "Test failed");

   150     }

   152   }

   153   {

   154     std::list<int> data1;

   155     generateIntSequence(n, data1);

   157     std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));

   159     radixSort(data1.begin(), data1.end());

   161     check(isTheSame(data1,data2), "Test failed");

   164     // radixSort(data2.begin(), data2.end(), Negate());

   165     // check(isTheSame(data1,data2), "Test failed");

   166     // for (int i = 0; i < n; ++i) {

   167     //   check(data1[i] == data2[n - 1 - i], "Test failed");

   168     // }

   170     // radixSort(data2.begin(), data2.end(), negate);

   171     // for (int i = 0; i < n; ++i) {

   172     //   check(data1[i] == data2[n - 1 - i], "Test failed");

   173     // }

   175   }

   177   {

   178     std::list<unsigned char> data1(n);

   179     generateCharSequence(n, data1);

   181     std::list<unsigned char> data2(listsort<std::list<unsigned char> >

   182                                    (data1.begin(),

   183                                     data1.end()));

   185     radixSort(data1.begin(), data1.end());

   186     check(isTheSame(data1,data2), "Test failed");

   188   }

   189 }

   192 void checkStableRadixSort() {

   193   {

   194     std::vector<int> data1;

   195     generateIntSequence(n, data1);

   197     std::vector<int> data2(data1);

   198     std::sort(data1.begin(), data1.end());

   200     stableRadixSort(data2.begin(), data2.end());

   201     for (int i = 0; i < n; ++i) {

   202       check(data1[i] == data2[i], "Test failed");

   203     }

   205     stableRadixSort(data2.begin(), data2.end(), Negate());

   206     for (int i = 0; i < n; ++i) {

   207       check(data1[i] == data2[n - 1 - i], "Test failed");

   208     }

   210     stableRadixSort(data2.begin(), data2.end(), negate);

   211     for (int i = 0; i < n; ++i) {

   212       check(data1[i] == data2[n - 1 - i], "Test failed");

   213     }

   214   }

   216   {

   217     std::vector<unsigned char> data1(n);

   218     generateCharSequence(n, data1);

   220     std::vector<unsigned char> data2(data1);

   221     std::sort(data1.begin(), data1.end());

   223     radixSort(data2.begin(), data2.end());

   224     for (int i = 0; i < n; ++i) {

   225       check(data1[i] == data2[i], "Test failed");

   226     }

   228   }

   229   {

   230     std::list<int> data1;

   231     generateIntSequence(n, data1);

   233     std::list<int> data2(listsort<std::list<int> >(data1.begin(),

   234                                                    data1.end()));

   235     stableRadixSort(data1.begin(), data1.end());

   236     check(isTheSame(data1,data2), "Test failed");

   238     // stableRadixSort(data2.begin(), data2.end(), Negate());

   239     // for (int i = 0; i < n; ++i) {

   240     //   check(data1[i] == data2[n - 1 - i], "Test failed");

   241     // }

   243     // stableRadixSort(data2.begin(), data2.end(), negate);

   244     // for (int i = 0; i < n; ++i) {

   245     //   check(data1[i] == data2[n - 1 - i], "Test failed");

   246     // }

   247   }

   249   {

   250     std::list<unsigned char> data1(n);

   251     generateCharSequence(n, data1);

   253     std::list<unsigned char> data2(listsort<std::list<unsigned char> >

   254                                    (data1.begin(),

   255                                     data1.end()));

   256     radixSort(data1.begin(), data1.end());

   257     check(isTheSame(data1,data2), "Test failed");

   259   }

   260 }

   262 int main() {

   264   checkRadixSort();

   265   checkStableRadixSort();

   267   return 0;

   268 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 15 May 2015 10:16:48 +0200
changeset 1354	1de908281369
parent 1270	dceba191c00d
permissions	-rw-r--r--