test/radix_sort_test.cc
author Balazs Dezso <deba@google.com>
Wed, 17 Oct 2018 17:52:11 +0200
changeset 1182 6b79d93e812f
parent 1092 dceba191c00d
permissions -rw-r--r--
Planar drawing algorithm now works for less than 3 nodes (#611)
     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  */
    18 
    19 #include <lemon/core.h>
    20 
    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>
    26 
    27 #include "test_tools.h"
    28 
    29 #include <vector>
    30 #include <list>
    31 #include <algorithm>
    32 
    33 using namespace lemon;
    34 
    35 static const int n = 10000;
    36 
    37 struct Negate {
    38   typedef int argument_type;
    39   typedef int result_type;
    40   int operator()(int a) { return - a; }
    41 };
    42 
    43 int negate(int a) { return - a; }
    44 
    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 }
    54 
    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 }
    94 
    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 }
   104 
   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 }
   114 
   115 void checkRadixSort() {
   116   {
   117     std::vector<int> data1;
   118     generateIntSequence(n, data1);
   119 
   120     std::vector<int> data2(data1);
   121     std::sort(data1.begin(), data1.end());
   122 
   123     radixSort(data2.begin(), data2.end());
   124     for (int i = 0; i < n; ++i) {
   125       check(data1[i] == data2[i], "Test failed");
   126     }
   127 
   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     // }
   132 
   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     // }
   137 
   138   }
   139 
   140   {
   141     std::vector<unsigned char> data1(n);
   142     generateCharSequence(n, data1);
   143 
   144     std::vector<unsigned char> data2(data1);
   145     std::sort(data1.begin(), data1.end());
   146 
   147     radixSort(data2.begin(), data2.end());
   148     for (int i = 0; i < n; ++i) {
   149       check(data1[i] == data2[i], "Test failed");
   150     }
   151 
   152   }
   153   {
   154     std::list<int> data1;
   155     generateIntSequence(n, data1);
   156 
   157     std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
   158 
   159     radixSort(data1.begin(), data1.end());
   160 
   161     check(isTheSame(data1,data2), "Test failed");
   162 
   163 
   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     // }
   169 
   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     // }
   174 
   175   }
   176 
   177   {
   178     std::list<unsigned char> data1(n);
   179     generateCharSequence(n, data1);
   180 
   181     std::list<unsigned char> data2(listsort<std::list<unsigned char> >
   182                                    (data1.begin(),
   183                                     data1.end()));
   184 
   185     radixSort(data1.begin(), data1.end());
   186     check(isTheSame(data1,data2), "Test failed");
   187 
   188   }
   189 }
   190 
   191 
   192 void checkStableRadixSort() {
   193   {
   194     std::vector<int> data1;
   195     generateIntSequence(n, data1);
   196 
   197     std::vector<int> data2(data1);
   198     std::sort(data1.begin(), data1.end());
   199 
   200     stableRadixSort(data2.begin(), data2.end());
   201     for (int i = 0; i < n; ++i) {
   202       check(data1[i] == data2[i], "Test failed");
   203     }
   204 
   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     }
   209 
   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   }
   215 
   216   {
   217     std::vector<unsigned char> data1(n);
   218     generateCharSequence(n, data1);
   219 
   220     std::vector<unsigned char> data2(data1);
   221     std::sort(data1.begin(), data1.end());
   222 
   223     radixSort(data2.begin(), data2.end());
   224     for (int i = 0; i < n; ++i) {
   225       check(data1[i] == data2[i], "Test failed");
   226     }
   227 
   228   }
   229   {
   230     std::list<int> data1;
   231     generateIntSequence(n, data1);
   232 
   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");
   237 
   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     // }
   242 
   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   }
   248 
   249   {
   250     std::list<unsigned char> data1(n);
   251     generateCharSequence(n, data1);
   252 
   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");
   258 
   259   }
   260 }
   261 
   262 int main() {
   263 
   264   checkRadixSort();
   265   checkStableRadixSort();
   266 
   267   return 0;
   268 }