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>(data: 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>(data: 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(x: 0.0); |
79 | else |
80 | base_vec.push_back(x: val); |
81 | } |
82 | test_vector(base_vec, shifter: 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(x: -i); |
87 | test_vector(base_vec, shifter: rightshift()); |
88 | base_vec.clear(); |
89 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(x: i - input_count); |
90 | test_vector(base_vec, shifter: rightshift()); |
91 | base_vec.clear(); |
92 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(x: input_count - i); |
93 | test_vector(base_vec, shifter: rightshift()); |
94 | base_vec.clear(); |
95 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(x: i); |
96 | test_vector(base_vec, shifter: rightshift()); |
97 | base_vec.clear(); |
98 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(x: i); |
99 | for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1; |
100 | test_vector(base_vec, shifter: 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(sign: 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(x: 0.0); |
112 | else |
113 | base_vec.push_back(x: val); |
114 | } |
115 | test_vector(base_vec, shifter: 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(x: -i); |
120 | test_vector(base_vec, shifter: rightshift_64()); |
121 | base_vec.clear(); |
122 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(x: i - input_count); |
123 | test_vector(base_vec, shifter: rightshift_64()); |
124 | base_vec.clear(); |
125 | for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(x: input_count - i); |
126 | test_vector(base_vec, shifter: rightshift_64()); |
127 | base_vec.clear(); |
128 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(x: i); |
129 | test_vector(base_vec, shifter: rightshift_64()); |
130 | base_vec.clear(); |
131 | for (size_t i = 0; i < input_count; ++i) base_vec.push_back(x: i); |
132 | for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1; |
133 | test_vector(base_vec, shifter: 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(first: test_vec.begin(), last: test_vec.end()); |
140 | const float test_value = -0.0; |
141 | test_vec.push_back(x: test_value); |
142 | boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: 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(seed: 1); |
151 | float_test(); |
152 | double_test(); |
153 | corner_test(); |
154 | return 0; |
155 | } |
156 | |