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 {
operator ()__anonc9b3b8e30111::int_right_shift31 int operator()(const int x, const unsigned offset) const {
32 return x >> offset;
33 }
34 };
35
36 struct float_right_shift {
operator ()__anonc9b3b8e30111::float_right_shift37 int operator()(const float x, const unsigned offset) const {
38 return float_mem_cast<float, int>(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)((int)int_log_finishing_count,
49 (int)int_log_mean_bin_size + int_log_min_split_count);
50 const int float_min_log_count =
51 (std::min)((int)float_log_finishing_count,
52 (int)float_log_mean_bin_size + float_log_min_split_count);
53 const unsigned absolute_min_count = (std::min)(1 << int_min_log_count,
54 1 << float_min_log_count);
55
56 // Verify that roughlog2 is floor(log base 2) + 1.
roughlog2_test()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>
get_min_count_test()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(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.
get_log_divisor_test()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)((int)int_log_mean_bin_size, (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.
is_sorted_or_find_extremes_test()132 void is_sorted_or_find_extremes_test()
133 {
134 vector<int> input;
135 input.push_back(3);
136 input.push_back(5);
137 input.push_back(1);
138 // Test a sorted input.
139 vector<int> sorted_input(input);
140 std::sort(sorted_input.begin(), 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(.3f);
163 float_input.push_back(4.0f);
164 float_input.push_back(.1f);
165 vector<float> sorted_float_input(float_input);
166 std::sort(sorted_float_input.begin(), sorted_float_input.end());
167 // Test cast_float_iter
168 int cast_min = detail::cast_float_iter<int, vector<float>::iterator>(
169 sorted_float_input.begin());
170 int cast_max = detail::cast_float_iter<int, vector<float>::iterator>(
171 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.
size_bins_test()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(old_bin_value);
208 std::vector<vector<int>::iterator> bin_cache;
209 bin_cache.push_back(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.
swap_loop_test()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(2 + int_offset);
236 ints.push_back(1 + int_offset); // stays in place
237 ints.push_back(4 + int_offset);
238 ints.push_back(3 + int_offset);
239 ints.push_back(0 + int_offset);
240 vector<vector<int>::iterator> int_bin_vector;
241 int_bin_vector.push_back(ints.begin());
242 int_bin_vector.push_back(int_bin_vector[0] + bin_sizes[0]);
243 int_bin_vector.push_back(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(int_bins, next_int_bin_start, 0, integer_right_shift, bin_sizes,
248 int_log_divisor, 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>(4.0f);
257 const int float_log_divisor =
258 rough_log_2_size(float_mem_cast<float, int>(5.0f) - float_four_as_int);
259 const int float_div_min = float_four_as_int >> float_log_divisor;
260 floats.push_back(6.0f);
261 floats.push_back(5.0f); // stays in place
262 floats.push_back(8.0f);
263 floats.push_back(7.0f);
264 floats.push_back(4.0f);
265 vector<vector<float>::iterator> float_bin_vector;
266 float_bin_vector.push_back(floats.begin());
267 float_bin_vector.push_back(float_bin_vector[0] + bin_sizes[0]);
268 float_bin_vector.push_back(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(float_bins, next_float_bin_start, 0, bin_sizes,
272 float_log_divisor, 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
test_main(int,char * [])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