]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | // Boost Sort library int_test.cpp file ------------------------------------// |
2 | ||
3 | // Copyright Steven Ross 2009-2014. Use, modification and | |
4 | // distribution is subject to the Boost Software License, Version | |
5 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // See http://www.boost.org/libs/sort for library home page. | |
9 | ||
10 | #include <boost/cstdint.hpp> | |
11 | #include <boost/sort/spreadsort/spreadsort.hpp> | |
12 | // Include unit test framework | |
13 | #include <boost/test/included/test_exec_monitor.hpp> | |
14 | #include <boost/test/test_tools.hpp> | |
15 | #include <vector> | |
16 | ||
17 | #include <iostream> | |
18 | ||
19 | ||
20 | using namespace std; | |
21 | using namespace boost::sort::spreadsort; | |
22 | ||
23 | struct rightshift { | |
24 | int operator()(int x, unsigned offset) { return x >> offset; } | |
25 | }; | |
26 | ||
27 | struct rightshift_max { | |
28 | boost::intmax_t operator()(const boost::intmax_t &x, unsigned offset) { | |
29 | return x >> offset; | |
30 | } | |
31 | }; | |
32 | ||
33 | struct negrightshift { | |
34 | int operator()(const int &x, const unsigned offset) { return -(x >> offset); } | |
35 | }; | |
36 | ||
37 | struct negrightshift_max { | |
38 | boost::intmax_t operator()(const boost::intmax_t &x, const unsigned offset) { | |
39 | return -(x >> offset); | |
40 | } | |
41 | }; | |
42 | ||
43 | boost::int32_t | |
44 | rand_32(bool sign = true) { | |
45 | boost::int32_t result = rand() | (rand()<< 16); | |
46 | if (rand() % 2) | |
47 | result |= 1 << 15; | |
48 | //Adding the sign bit | |
49 | if (sign && (rand() % 2)) | |
50 | result *= -1; | |
51 | return result; | |
52 | } | |
53 | ||
54 | void int_test() | |
55 | { | |
56 | // Prepare inputs | |
57 | vector<int> base_vec; | |
58 | unsigned count = 100000; | |
59 | srand(1); | |
60 | //Generating semirandom numbers | |
61 | for (unsigned u = 0; u < count; ++u) | |
62 | base_vec.push_back(rand_32()); | |
63 | vector<int> sorted_vec = base_vec; | |
64 | vector<int> test_vec = base_vec; | |
65 | std::sort(sorted_vec.begin(), sorted_vec.end()); | |
66 | //Testing basic call | |
67 | integer_sort(test_vec.begin(), test_vec.end()); | |
68 | BOOST_CHECK(test_vec == sorted_vec); | |
69 | //boost::sort::spreadsort variant | |
70 | test_vec = base_vec; | |
71 | boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); | |
72 | BOOST_CHECK(test_vec == sorted_vec); | |
73 | //One functor | |
74 | test_vec = base_vec; | |
75 | integer_sort(test_vec.begin(), test_vec.end(), rightshift()); | |
76 | BOOST_CHECK(test_vec == sorted_vec); | |
77 | //Both functors | |
78 | test_vec = base_vec; | |
79 | integer_sort(test_vec.begin(), test_vec.end(), rightshift(), less<int>()); | |
80 | BOOST_CHECK(test_vec == sorted_vec); | |
81 | //reverse order | |
82 | std::sort(sorted_vec.begin(), sorted_vec.end(), greater<int>()); | |
83 | integer_sort(test_vec.begin(), test_vec.end(), negrightshift(), | |
84 | greater<int>()); | |
85 | BOOST_CHECK(test_vec == sorted_vec); | |
86 | ||
87 | //Making sure we're correctly sorting boost::intmax_ts; should use std::sort | |
88 | vector<boost::intmax_t> long_base_vec; | |
89 | for (unsigned u = 0; u < base_vec.size(); ++u) | |
90 | long_base_vec.push_back((((boost::intmax_t)rand_32()) << | |
91 | ((8 * sizeof(int)) -1)) + rand_32(false)); | |
92 | vector<boost::intmax_t> long_sorted_vec = long_base_vec; | |
93 | vector<boost::intmax_t> long_test_vec = long_base_vec; | |
94 | integer_sort(long_test_vec.begin(), long_test_vec.end()); | |
95 | std::sort(long_sorted_vec.begin(), long_sorted_vec.end()); | |
96 | BOOST_CHECK(long_test_vec == long_sorted_vec); | |
97 | //One functor | |
98 | long_test_vec = long_base_vec; | |
99 | integer_sort(long_test_vec.begin(), long_test_vec.end(), rightshift_max()); | |
100 | BOOST_CHECK(long_test_vec == long_sorted_vec); | |
101 | //Both functors | |
102 | long_test_vec = long_base_vec; | |
103 | integer_sort(long_test_vec.begin(), long_test_vec.end(), rightshift_max(), | |
104 | less<boost::intmax_t>()); | |
105 | BOOST_CHECK(long_test_vec == long_sorted_vec); | |
106 | //reverse order | |
107 | std::sort(long_sorted_vec.begin(), long_sorted_vec.end(), | |
108 | greater<boost::intmax_t>()); | |
109 | integer_sort(long_test_vec.begin(), long_test_vec.end(), negrightshift_max(), | |
110 | greater<boost::intmax_t>()); | |
111 | BOOST_CHECK(long_test_vec == long_sorted_vec); | |
112 | } | |
113 | ||
114 | // Verify that 0 and 1 elements work correctly. | |
115 | void corner_test() { | |
116 | vector<int> test_vec; | |
117 | boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); | |
118 | const int test_value = 42; | |
119 | test_vec.push_back(test_value); | |
120 | boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); | |
121 | BOOST_CHECK(test_vec.size() == 1); | |
122 | BOOST_CHECK(test_vec[0] == test_value); | |
123 | } | |
124 | ||
125 | // test main | |
126 | int test_main( int, char*[] ) | |
127 | { | |
128 | int_test(); | |
129 | corner_test(); | |
130 | return 0; | |
131 | } |