test/radix_sort_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 25 Sep 2009 12:22:42 +0200
changeset 724 d8073df341f6
parent 443 de16f1f2d228
child 1043 1bafdbd2fc46
permissions -rw-r--r--
Rename ValueIterator to ValueIt in graph maps (#302)
but keep ValueIterator as an alias in CrossRefMap
(only for reverse compatibility).
     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-2009
     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/time_measure.h>
    20 #include <lemon/smart_graph.h>
    21 #include <lemon/maps.h>
    22 #include <lemon/radix_sort.h>
    23 #include <lemon/math.h>
    24 
    25 #include "test_tools.h"
    26 
    27 #include <vector>
    28 #include <algorithm>
    29 
    30 using namespace lemon;
    31 
    32 static const int n = 10000;
    33 
    34 struct Negate {
    35   typedef int argument_type;
    36   typedef int result_type;
    37   int operator()(int a) { return - a; }
    38 };
    39 
    40 int negate(int a) { return - a; }
    41 
    42 
    43 void generateIntSequence(int n, std::vector<int>& data) {
    44   int prime = 9973;
    45   int root = 136, value = 1;
    46   for (int i = 0; i < n; ++i) {
    47     data.push_back(value - prime / 2);
    48     value = (value * root) % prime;
    49   }
    50 }
    51 
    52 void generateCharSequence(int n, std::vector<unsigned char>& data) {
    53   int prime = 251;
    54   int root = 3, value = root;
    55   for (int i = 0; i < n; ++i) {
    56     data.push_back(static_cast<unsigned char>(value));
    57     value = (value * root) % prime;
    58   }
    59 }
    60 
    61 void checkRadixSort() {
    62   {
    63     std::vector<int> data1;
    64     generateIntSequence(n, data1);
    65 
    66     std::vector<int> data2(data1);
    67     std::sort(data1.begin(), data1.end());
    68 
    69     radixSort(data2.begin(), data2.end());
    70     for (int i = 0; i < n; ++i) {
    71       check(data1[i] == data2[i], "Test failed");
    72     }
    73 
    74     radixSort(data2.begin(), data2.end(), Negate());
    75     for (int i = 0; i < n; ++i) {
    76       check(data1[i] == data2[n - 1 - i], "Test failed");
    77     }
    78 
    79     radixSort(data2.begin(), data2.end(), negate);
    80     for (int i = 0; i < n; ++i) {
    81       check(data1[i] == data2[n - 1 - i], "Test failed");
    82     }
    83 
    84   }
    85 
    86   {
    87     std::vector<unsigned char> data1(n);
    88     generateCharSequence(n, data1);
    89 
    90     std::vector<unsigned char> data2(data1);
    91     std::sort(data1.begin(), data1.end());
    92 
    93     radixSort(data2.begin(), data2.end());
    94     for (int i = 0; i < n; ++i) {
    95       check(data1[i] == data2[i], "Test failed");
    96     }
    97 
    98   }
    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     }
   137 
   138   }
   139 }
   140 
   141 int main() {
   142 
   143   checkRadixSort();
   144   checkStableRadixSort();
   145 
   146   return 0;
   147 }