COIN-OR::LEMON - Graph Library

source: lemon/test/radix_sort_test.cc @ 555:861a9d5ff283

Last change on this file since 555:861a9d5ff283 was 467:ba49101c9b07, checked in by Alpar Juttner <alpar@…>, 16 years ago

Update to 2009 plus whitespace unification

File size: 3.4 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-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
30using namespace lemon;
31
32static const int n = 10000;
33
34struct Negate {
35  typedef int argument_type;
36  typedef int result_type;
37  int operator()(int a) { return - a; }
38};
39
40int negate(int a) { return - a; }
41
42
43void 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
52void 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
61void 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
102void 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
141int main() {
142
143  checkRadixSort();
144  checkStableRadixSort();
145
146  return 0;
147}
Note: See TracBrowser for help on using the repository browser.