COIN-OR::LEMON - Graph Library

source: lemon/test/radix_sort_test.cc @ 1270:dceba191c00d

Last change on this file since 1270:dceba191c00d was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 6 years ago

Apply unify-sources.sh to the source tree

File size: 6.3 KB
Line 
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/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 <list>
29#include <algorithm>
30
31using namespace lemon;
32
33static const int n = 10000;
34
35struct Negate {
36  typedef int argument_type;
37  typedef int result_type;
38  int operator()(int a) { return - a; }
39};
40
41int negate(int a) { return - a; }
42
43template<class T>
44bool isTheSame(T &a, T&b)
45{
46  typename T::iterator ai=a.begin();
47  typename T::iterator bi=b.begin();
48  for(;ai!=a.end()||bi!=b.end();++ai,++bi)
49    if(*ai!=*bi) return false;
50  return ai==a.end()&&bi==b.end();
51}
52
53template<class T>
54T listsort(typename T::iterator b, typename T::iterator e)
55{
56  if(b==e) return T();
57  typename T::iterator bn=b;
58  if(++bn==e) {
59    T l;
60    l.push_back(*b);
61    return l;
62  }
63  typename T::iterator m=b;
64  bool x=false;
65  for(typename T::iterator i=b;i!=e;++i,x=!x)
66    if(x) ++m;
67  T l1(listsort<T>(b,m));
68  T l2(listsort<T>(m,e));
69  T l;
70  while((!l1.empty())&&(!l2.empty()))
71    if(l1.front()<=l2.front())
72      {
73        l.push_back(l1.front());
74        l1.pop_front();
75      }
76    else {
77      l.push_back(l2.front());
78      l2.pop_front();
79    }
80  while(!l1.empty())
81    {
82      l.push_back(l1.front());
83      l1.pop_front();
84    }
85  while(!l2.empty())
86    {
87      l.push_back(l2.front());
88      l2.pop_front();
89    }
90  return l;
91}
92
93template<class T>
94void generateIntSequence(int n, T & data) {
95  int prime = 9973;
96  int root = 136, value = 1;
97  for (int i = 0; i < n; ++i) {
98    data.push_back(value - prime / 2);
99    value = (value * root) % prime;
100  }
101}
102
103template<class T>
104void generateCharSequence(int n, T & data) {
105  int prime = 251;
106  int root = 3, value = root;
107  for (int i = 0; i < n; ++i) {
108    data.push_back(static_cast<unsigned char>(value));
109    value = (value * root) % prime;
110  }
111}
112
113void checkRadixSort() {
114  {
115    std::vector<int> data1;
116    generateIntSequence(n, data1);
117
118    std::vector<int> data2(data1);
119    std::sort(data1.begin(), data1.end());
120
121    radixSort(data2.begin(), data2.end());
122    for (int i = 0; i < n; ++i) {
123      check(data1[i] == data2[i], "Test failed");
124    }
125
126    // radixSort(data2.begin(), data2.end(), Negate());
127    // for (int i = 0; i < n; ++i) {
128    //   check(data1[i] == data2[n - 1 - i], "Test failed");
129    // }
130
131    // radixSort(data2.begin(), data2.end(), negate);
132    // for (int i = 0; i < n; ++i) {
133    //   check(data1[i] == data2[n - 1 - i], "Test failed");
134    // }
135
136  }
137
138  {
139    std::vector<unsigned char> data1(n);
140    generateCharSequence(n, data1);
141
142    std::vector<unsigned char> data2(data1);
143    std::sort(data1.begin(), data1.end());
144
145    radixSort(data2.begin(), data2.end());
146    for (int i = 0; i < n; ++i) {
147      check(data1[i] == data2[i], "Test failed");
148    }
149
150  }
151  {
152    std::list<int> data1;
153    generateIntSequence(n, data1);
154
155    std::list<int> data2(listsort<std::list<int> >(data1.begin(), data1.end()));
156
157    radixSort(data1.begin(), data1.end());
158
159    check(isTheSame(data1,data2), "Test failed");
160
161
162    // radixSort(data2.begin(), data2.end(), Negate());
163    // check(isTheSame(data1,data2), "Test failed");
164    // for (int i = 0; i < n; ++i) {
165    //   check(data1[i] == data2[n - 1 - i], "Test failed");
166    // }
167
168    // radixSort(data2.begin(), data2.end(), negate);
169    // for (int i = 0; i < n; ++i) {
170    //   check(data1[i] == data2[n - 1 - i], "Test failed");
171    // }
172
173  }
174
175  {
176    std::list<unsigned char> data1(n);
177    generateCharSequence(n, data1);
178
179    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
180                                   (data1.begin(),
181                                    data1.end()));
182
183    radixSort(data1.begin(), data1.end());
184    check(isTheSame(data1,data2), "Test failed");
185
186  }
187}
188
189
190void checkStableRadixSort() {
191  {
192    std::vector<int> data1;
193    generateIntSequence(n, data1);
194
195    std::vector<int> data2(data1);
196    std::sort(data1.begin(), data1.end());
197
198    stableRadixSort(data2.begin(), data2.end());
199    for (int i = 0; i < n; ++i) {
200      check(data1[i] == data2[i], "Test failed");
201    }
202
203    stableRadixSort(data2.begin(), data2.end(), Negate());
204    for (int i = 0; i < n; ++i) {
205      check(data1[i] == data2[n - 1 - i], "Test failed");
206    }
207
208    stableRadixSort(data2.begin(), data2.end(), negate);
209    for (int i = 0; i < n; ++i) {
210      check(data1[i] == data2[n - 1 - i], "Test failed");
211    }
212  }
213
214  {
215    std::vector<unsigned char> data1(n);
216    generateCharSequence(n, data1);
217
218    std::vector<unsigned char> data2(data1);
219    std::sort(data1.begin(), data1.end());
220
221    radixSort(data2.begin(), data2.end());
222    for (int i = 0; i < n; ++i) {
223      check(data1[i] == data2[i], "Test failed");
224    }
225
226  }
227  {
228    std::list<int> data1;
229    generateIntSequence(n, data1);
230
231    std::list<int> data2(listsort<std::list<int> >(data1.begin(),
232                                                   data1.end()));
233    stableRadixSort(data1.begin(), data1.end());
234    check(isTheSame(data1,data2), "Test failed");
235
236    // stableRadixSort(data2.begin(), data2.end(), Negate());
237    // for (int i = 0; i < n; ++i) {
238    //   check(data1[i] == data2[n - 1 - i], "Test failed");
239    // }
240
241    // stableRadixSort(data2.begin(), data2.end(), negate);
242    // for (int i = 0; i < n; ++i) {
243    //   check(data1[i] == data2[n - 1 - i], "Test failed");
244    // }
245  }
246
247  {
248    std::list<unsigned char> data1(n);
249    generateCharSequence(n, data1);
250
251    std::list<unsigned char> data2(listsort<std::list<unsigned char> >
252                                   (data1.begin(),
253                                    data1.end()));
254    radixSort(data1.begin(), data1.end());
255    check(isTheSame(data1,data2), "Test failed");
256
257  }
258}
259
260int main() {
261
262  checkRadixSort();
263  checkStableRadixSort();
264
265  return 0;
266}
Note: See TracBrowser for help on using the repository browser.