COIN-OR::LEMON - Graph Library

source: lemon-main/test/radix_sort_test.cc @ 1163:db1d342a1087

Last change on this file since 1163:db1d342a1087 was 1135:c199e9976d93, checked in by Alpar Juttner <alpar@…>, 10 years ago

Resolve VS and MinGW warnings (#595)

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/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
33using namespace lemon;
34
35static const int n = 10000;
36
37struct Negate {
38  typedef int argument_type;
39  typedef int result_type;
40  int operator()(int a) { return - a; }
41};
42
43int negate(int a) { return - a; }
44
45template<class T>
46bool 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
55template<class T>
56T 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
95template<class T>
96void 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
105template<class T>
106void 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
115void 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
192void 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
262int main() {
263
264  checkRadixSort();
265  checkStableRadixSort();
266
267  return 0;
268}
Note: See TracBrowser for help on using the repository browser.