1 | // Boost Sort library tests for integer_sort and float_sort details. |
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/cstdint.hpp> |
11 | #include <boost/sort/spreadsort/detail/spreadsort_common.hpp> |
12 | #include <boost/sort/spreadsort/detail/integer_sort.hpp> |
13 | #include <boost/sort/spreadsort/detail/float_sort.hpp> |
14 | #include <boost/sort/spreadsort/detail/string_sort.hpp> |
15 | #include <boost/sort/spreadsort/float_sort.hpp> |
16 | // Include unit test framework |
17 | #include <boost/test/included/test_exec_monitor.hpp> |
18 | #include <boost/test/test_tools.hpp> |
19 | #include <vector> |
20 | |
21 | #include <iostream> |
22 | |
23 | |
24 | using namespace std; |
25 | using namespace boost::sort::spreadsort; |
26 | using namespace boost::sort::spreadsort::detail; |
27 | |
28 | namespace { |
29 | |
30 | struct int_right_shift { |
31 | int operator()(const int x, const unsigned offset) const { |
32 | return x >> offset; |
33 | } |
34 | }; |
35 | |
36 | struct float_right_shift { |
37 | int operator()(const float x, const unsigned offset) const { |
38 | return float_mem_cast<float, int>(data: x) >> offset; |
39 | } |
40 | }; |
41 | |
42 | const int max_int_bits = sizeof(boost::uintmax_t) * 8; |
43 | const int max_size_bits = sizeof(size_t) * 8; |
44 | const boost::uintmax_t one = 1; |
45 | |
46 | // spreadsort won't recurse for inputs smaller than min_count. |
47 | const int int_min_log_count = |
48 | (std::min)(a: (int)int_log_finishing_count, |
49 | b: (int)int_log_mean_bin_size + int_log_min_split_count); |
50 | const int float_min_log_count = |
51 | (std::min)(a: (int)float_log_finishing_count, |
52 | b: (int)float_log_mean_bin_size + float_log_min_split_count); |
53 | const unsigned absolute_min_count = (std::min)(a: 1 << int_min_log_count, |
54 | b: 1 << float_min_log_count); |
55 | |
56 | // Verify that roughlog2 is floor(log base 2) + 1. |
57 | void roughlog2_test() |
58 | { |
59 | for (boost::uintmax_t i = 0; i < max_int_bits; ++i) { |
60 | BOOST_CHECK(detail::rough_log_2_size(one << i) == i + 1); |
61 | BOOST_CHECK(detail::rough_log_2_size((one << i) - 1) == i); |
62 | } |
63 | } |
64 | |
65 | // Test the worst-case performance handling, and assure that is using the |
66 | // correct formula for the worst-case number of radix iterations. |
67 | template<unsigned log_mean_bin_size, unsigned log_min_split_count, |
68 | unsigned log_finishing_count> |
69 | void get_min_count_test() |
70 | { |
71 | const unsigned min_log_size = log_mean_bin_size + log_min_split_count; |
72 | size_t prev_min_count = absolute_min_count; |
73 | for (int log_range = 0; log_range <= max_int_bits; ++log_range) { |
74 | size_t min_count = get_min_count<log_mean_bin_size, log_min_split_count, |
75 | log_finishing_count>(log_range); |
76 | BOOST_CHECK(min_count >= prev_min_count); |
77 | prev_min_count = min_count; |
78 | // When the range is really small, the radix sort will complete in one |
79 | // iteration and worst-case handling doesn't apply. The code below |
80 | // guarantees the worst-case number of radix sorting iteration. |
81 | if (log_range > min_log_size) { |
82 | BOOST_CHECK(min_count >= (1 << min_log_size)); |
83 | int iterations = rough_log_2_size(input: min_count) - min_log_size; |
84 | BOOST_CHECK(iterations >= 1); |
85 | int base_iterations = max_splits - log_min_split_count; |
86 | int covered_log_range = 0; |
87 | if (iterations > base_iterations) { |
88 | covered_log_range += max_splits * (iterations - base_iterations); |
89 | } else { |
90 | base_iterations = iterations; |
91 | } |
92 | // sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size |
93 | covered_log_range += |
94 | (base_iterations * (log_min_split_count * 2 + base_iterations - 1))/2 + |
95 | log_mean_bin_size; |
96 | BOOST_CHECK(covered_log_range >= log_range); |
97 | BOOST_CHECK(covered_log_range - max_splits < log_range); |
98 | } |
99 | } |
100 | } |
101 | |
102 | // Test the decision of how many pieces to split up the radix sort into |
103 | // (roughly 2^(log_range - log_divisor)) to make sure the results are logical. |
104 | void get_log_divisor_test() |
105 | { |
106 | for (int log_range = 0; log_range <= max_int_bits; ++log_range) { |
107 | int prev_log_divisor = max_int_bits + |
108 | (std::max)(a: (int)int_log_mean_bin_size, b: (int)float_log_mean_bin_size); |
109 | for (int log_count = 0; log_count < max_size_bits; ++log_count) { |
110 | size_t count = (one << log_count) - 1; |
111 | BOOST_CHECK(rough_log_2_size(count) == (unsigned)log_count); |
112 | int log_divisor = |
113 | get_log_divisor<int_log_mean_bin_size>(count, log_range); |
114 | // Only process counts >= int_log_finishing_count in this function. |
115 | if (count >= absolute_min_count) |
116 | BOOST_CHECK(log_divisor <= log_range); |
117 | // More pieces should be used the larger count is. |
118 | BOOST_CHECK(log_divisor <= prev_log_divisor); |
119 | prev_log_divisor = log_divisor; |
120 | BOOST_CHECK(log_divisor >= 0); |
121 | if (log_range > log_count) { |
122 | BOOST_CHECK(log_range - log_divisor <= max_splits); |
123 | } else if (log_range <= max_finishing_splits) { |
124 | BOOST_CHECK(log_divisor == 0); |
125 | } |
126 | } |
127 | } |
128 | } |
129 | |
130 | // Verify that is_sorted_or_find_extremes returns true if the data is sorted, |
131 | // and otherwise returns the actual min and max. |
132 | void is_sorted_or_find_extremes_test() |
133 | { |
134 | vector<int> input; |
135 | input.push_back(x: 3); |
136 | input.push_back(x: 5); |
137 | input.push_back(x: 1); |
138 | // Test a sorted input. |
139 | vector<int> sorted_input(input); |
140 | std::sort(first: sorted_input.begin(), last: sorted_input.end()); |
141 | vector<int>::iterator max, min; |
142 | BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(), |
143 | sorted_input.end(), max, min)); |
144 | // Test an unsorted input. |
145 | BOOST_CHECK(!detail::is_sorted_or_find_extremes(input.begin(), input.end(), |
146 | max, min)); |
147 | BOOST_CHECK(*min == 1); |
148 | BOOST_CHECK(*max == 5); |
149 | // Test the comparison function version. |
150 | BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(), |
151 | sorted_input.end(), max, min, |
152 | std::less<int>())); |
153 | BOOST_CHECK(!detail::is_sorted_or_find_extremes(sorted_input.begin(), |
154 | sorted_input.end(), |
155 | max, min, |
156 | std::greater<int>())); |
157 | BOOST_CHECK(*min == 5); |
158 | BOOST_CHECK(*max == 1); |
159 | |
160 | // Test with floats |
161 | vector<float> float_input; |
162 | float_input.push_back(x: .3f); |
163 | float_input.push_back(x: 4.0f); |
164 | float_input.push_back(x: .1f); |
165 | vector<float> sorted_float_input(float_input); |
166 | std::sort(first: sorted_float_input.begin(), last: sorted_float_input.end()); |
167 | // Test cast_float_iter |
168 | int cast_min = detail::cast_float_iter<int, vector<float>::iterator>( |
169 | floatiter: sorted_float_input.begin()); |
170 | int cast_max = detail::cast_float_iter<int, vector<float>::iterator>( |
171 | floatiter: sorted_float_input.end() - 1); |
172 | BOOST_CHECK(cast_min == float_right_shift()(.1f, 0)); |
173 | BOOST_CHECK(cast_max == float_right_shift()(4.0f, 0)); |
174 | // Test a sorted input |
175 | int div_max, div_min; |
176 | BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(), |
177 | sorted_float_input.end(), |
178 | div_max, div_min)); |
179 | // Test an unsorted input. |
180 | BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(), |
181 | float_input.end(), |
182 | div_max, div_min)); |
183 | BOOST_CHECK(div_min == cast_min); |
184 | BOOST_CHECK(div_max == cast_max); |
185 | |
186 | // Test with a right_shift functor. |
187 | BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(), |
188 | sorted_float_input.end(), |
189 | div_max, div_min, |
190 | float_right_shift())); |
191 | // Test an unsorted input. |
192 | BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(), |
193 | float_input.end(), div_max, |
194 | div_min, |
195 | float_right_shift())); |
196 | BOOST_CHECK(div_min == float_right_shift()(.1f, 0)); |
197 | BOOST_CHECK(div_max == float_right_shift()(4.0f, 0)); |
198 | } |
199 | |
200 | // Make sure bins are created correctly. |
201 | void size_bins_test() { |
202 | size_t bin_sizes[1 << detail::max_finishing_splits]; |
203 | bin_sizes[0] = 1; |
204 | bin_sizes[2] = 7; |
205 | const int old_bin_value = 7; |
206 | std::vector<int> old_bins; |
207 | old_bins.push_back(x: old_bin_value); |
208 | std::vector<vector<int>::iterator> bin_cache; |
209 | bin_cache.push_back(x: old_bins.begin()); |
210 | unsigned cache_offset = 1; |
211 | unsigned cache_end; |
212 | const unsigned bin_count = 2; |
213 | std::vector<int>::iterator *new_cache_start = |
214 | size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); |
215 | BOOST_CHECK((new_cache_start - &bin_cache[0]) == cache_offset); |
216 | BOOST_CHECK(bin_sizes[0] == 0); |
217 | BOOST_CHECK(bin_sizes[1] == 0); |
218 | BOOST_CHECK(bin_sizes[2] == 7); // shouldn't modify past bin_count |
219 | BOOST_CHECK(cache_end == 3); |
220 | BOOST_CHECK(bin_cache.size() == cache_end); |
221 | BOOST_CHECK(old_bins[0] == old_bin_value); |
222 | } |
223 | |
224 | // Test the specialized 3-way swap loops. |
225 | void swap_loop_test() { |
226 | size_t bin_sizes[1 << detail::max_finishing_splits]; |
227 | bin_sizes[0] = bin_sizes[1] = 2; |
228 | bin_sizes[2] = 1; |
229 | |
230 | // test integer swap loop |
231 | vector<int> ints; |
232 | const int int_div_min = 3; |
233 | const int int_log_divisor = 1; |
234 | const unsigned int_offset = int_div_min << int_log_divisor; |
235 | ints.push_back(x: 2 + int_offset); |
236 | ints.push_back(x: 1 + int_offset); // stays in place |
237 | ints.push_back(x: 4 + int_offset); |
238 | ints.push_back(x: 3 + int_offset); |
239 | ints.push_back(x: 0 + int_offset); |
240 | vector<vector<int>::iterator> int_bin_vector; |
241 | int_bin_vector.push_back(x: ints.begin()); |
242 | int_bin_vector.push_back(x: int_bin_vector[0] + bin_sizes[0]); |
243 | int_bin_vector.push_back(x: int_bin_vector[1] + bin_sizes[1]); |
244 | vector<int>::iterator next_int_bin_start = int_bin_vector[0]; |
245 | vector<int>::iterator *int_bins = &int_bin_vector[0]; |
246 | int_right_shift integer_right_shift; |
247 | swap_loop(bins: int_bins, next_bin_start&: next_int_bin_start, ii: 0, rshift&: integer_right_shift, bin_sizes, |
248 | log_divisor: int_log_divisor, div_min: int_div_min); |
249 | for (unsigned i = 0; i < ints.size(); ++i) { |
250 | BOOST_CHECK(ints[i] == int(int_offset + i)); |
251 | } |
252 | BOOST_CHECK(next_int_bin_start == ints.begin() + bin_sizes[0]); |
253 | |
254 | // test float swap loop |
255 | vector<float> floats; |
256 | const int float_four_as_int = float_mem_cast<float, int>(data: 4.0f); |
257 | const int float_log_divisor = |
258 | rough_log_2_size(input: float_mem_cast<float, int>(data: 5.0f) - float_four_as_int); |
259 | const int float_div_min = float_four_as_int >> float_log_divisor; |
260 | floats.push_back(x: 6.0f); |
261 | floats.push_back(x: 5.0f); // stays in place |
262 | floats.push_back(x: 8.0f); |
263 | floats.push_back(x: 7.0f); |
264 | floats.push_back(x: 4.0f); |
265 | vector<vector<float>::iterator> float_bin_vector; |
266 | float_bin_vector.push_back(x: floats.begin()); |
267 | float_bin_vector.push_back(x: float_bin_vector[0] + bin_sizes[0]); |
268 | float_bin_vector.push_back(x: float_bin_vector[1] + bin_sizes[1]); |
269 | vector<float>::iterator next_float_bin_start = float_bin_vector[0]; |
270 | vector<float>::iterator *float_bins = &float_bin_vector[0]; |
271 | float_swap_loop(bins: float_bins, nextbinstart&: next_float_bin_start, ii: 0, bin_sizes, |
272 | log_divisor: float_log_divisor, div_min: float_div_min); |
273 | for (unsigned i = 0; i < floats.size(); ++i) { |
274 | BOOST_CHECK(floats[i] == 4.0f + i); |
275 | } |
276 | BOOST_CHECK(next_float_bin_start == floats.begin() + bin_sizes[0]); |
277 | } |
278 | |
279 | } // end anonymous namespace |
280 | |
281 | // test main |
282 | int test_main( int, char*[] ) |
283 | { |
284 | roughlog2_test(); |
285 | get_min_count_test<int_log_mean_bin_size, int_log_min_split_count, |
286 | int_log_finishing_count>(); |
287 | get_min_count_test<float_log_mean_bin_size, float_log_min_split_count, |
288 | float_log_finishing_count>(); |
289 | get_log_divisor_test(); |
290 | is_sorted_or_find_extremes_test(); |
291 | size_bins_test(); |
292 | swap_loop_test(); |
293 | return 0; |
294 | } |
295 | |