]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | // Boost Sort library float_sort_test.cpp file -----------------------------// |
2 | ||
3 | // Copyright Steven Ross 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/sort/spreadsort/spreadsort.hpp> | |
11 | // Include unit test framework | |
12 | #include <boost/test/included/test_exec_monitor.hpp> | |
13 | #include <boost/test/test_tools.hpp> | |
14 | #include <vector> | |
15 | ||
16 | ||
17 | using namespace std; | |
18 | using namespace boost::sort::spreadsort; | |
19 | ||
20 | //Casting to an integer before bitshifting | |
21 | struct rightshift { | |
22 | int operator()(const float &x, const unsigned offset) const { | |
23 | return float_mem_cast<float, int>(x) >> offset; | |
24 | } | |
25 | }; | |
26 | ||
27 | struct rightshift_64 { | |
28 | boost::int64_t operator()(const double &x, const boost::uint64_t offset) const | |
29 | { | |
30 | return float_mem_cast<double, boost::int64_t>(x) >> offset; | |
31 | } | |
32 | }; | |
33 | ||
34 | boost::int32_t | |
35 | rand_32(bool sign = true) { | |
36 | boost::int32_t result = rand() | (rand()<< 16); | |
37 | if (rand() % 2) | |
38 | result |= 1 << 15; | |
39 | //Adding the sign bit | |
40 | if (sign && (rand() % 2)) | |
41 | result *= -1; | |
42 | return result; | |
43 | } | |
44 | ||
45 | static const unsigned input_count = 1000000; | |
46 | ||
47 | // Helper class to run tests across all float_sort interface variants. | |
48 | template<class FloatType, class RightShift> | |
49 | void test_vector(vector<FloatType> base_vec, RightShift shifter) { | |
50 | vector<FloatType> sorted_vec = base_vec; | |
51 | vector<FloatType> test_vec = base_vec; | |
52 | std::sort(sorted_vec.begin(), sorted_vec.end()); | |
53 | //Testing boost::sort::spreadsort version | |
54 | test_vec = base_vec; | |
55 | boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); | |
56 | BOOST_CHECK(test_vec == sorted_vec); | |
57 | //One functor | |
58 | test_vec = base_vec; | |
59 | float_sort(test_vec.begin(), test_vec.end(), shifter); | |
60 | BOOST_CHECK(test_vec == sorted_vec); | |
61 | //Both functors | |
62 | test_vec = base_vec; | |
63 | float_sort(test_vec.begin(), test_vec.end(), shifter, less<FloatType>()); | |
64 | BOOST_CHECK(test_vec == sorted_vec); | |
65 | } | |
66 | ||
67 | void float_test() | |
68 | { | |
69 | // Prepare inputs | |
70 | vector<float> base_vec; | |
71 | ||
72 | //Generating semirandom numbers that will work for basic testing | |
73 | for (unsigned u = 0; u < input_count; ++u) { | |
74 | float val = float(rand_32()); | |
75 | //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0, treat all | |
76 | //those as just 0.0 for testing | |
77 | if (!(val < 0.0) && !(0.0 < val)) | |
78 | base_vec.push_back(0.0); | |
79 | else | |
80 | base_vec.push_back(val); | |
81 | } | |
82 | test_vector(base_vec, rightshift()); | |
83 | ||
84 | // Trying both positive and negative sorted and reverse sorted data. | |
85 | base_vec.clear(); | |
86 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i); | |
87 | test_vector(base_vec, rightshift()); | |
88 | base_vec.clear(); | |
89 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count); | |
90 | test_vector(base_vec, rightshift()); | |
91 | base_vec.clear(); | |
92 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i); | |
93 | test_vector(base_vec, rightshift()); | |
94 | base_vec.clear(); | |
95 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); | |
96 | test_vector(base_vec, rightshift()); | |
97 | base_vec.clear(); | |
98 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); | |
99 | for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1; | |
100 | test_vector(base_vec, rightshift()); | |
101 | } | |
102 | ||
103 | void double_test() { | |
104 | vector<double> base_vec; | |
105 | for (unsigned u = 0; u < input_count; ++u) { | |
106 | double val = double | |
107 | ((((boost::int64_t)rand_32()) << ((8 * sizeof(int)) -1)) + rand_32(false)); | |
108 | //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0, | |
109 | //treat all those as just 0.0 for testing | |
110 | if (!(val < 0.0) && !(0.0 < val)) | |
111 | base_vec.push_back(0.0); | |
112 | else | |
113 | base_vec.push_back(val); | |
114 | } | |
115 | test_vector(base_vec, rightshift_64()); | |
116 | ||
117 | // Trying both positive and negative sorted and reverse sorted data. | |
118 | base_vec.clear(); | |
119 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i); | |
120 | test_vector(base_vec, rightshift_64()); | |
121 | base_vec.clear(); | |
122 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count); | |
123 | test_vector(base_vec, rightshift_64()); | |
124 | base_vec.clear(); | |
125 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i); | |
126 | test_vector(base_vec, rightshift_64()); | |
127 | base_vec.clear(); | |
128 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); | |
129 | test_vector(base_vec, rightshift_64()); | |
130 | base_vec.clear(); | |
131 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); | |
132 | for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1; | |
133 | test_vector(base_vec, rightshift_64()); | |
134 | } | |
135 | ||
136 | // Verify that 0 and 1 elements work correctly. | |
137 | void corner_test() { | |
138 | vector<float> test_vec; | |
139 | boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); | |
140 | const float test_value = -0.0; | |
141 | test_vec.push_back(test_value); | |
142 | boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); | |
143 | BOOST_CHECK(test_vec.size() == 1); | |
144 | BOOST_CHECK(test_vec[0] == test_value); | |
145 | } | |
146 | ||
147 | // test main | |
148 | int test_main( int, char*[] ) | |
149 | { | |
150 | srand(1); | |
151 | float_test(); | |
152 | double_test(); | |
153 | corner_test(); | |
154 | return 0; | |
155 | } |