1 // Boost Sort library tests for integer_sort and float_sort details.
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)
8 // See http://www.boost.org/libs/sort for library home page.
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>
25 using namespace boost::sort::spreadsort
;
26 using namespace boost::sort::spreadsort::detail
;
30 struct int_right_shift
{
31 int operator()(const int x
, const unsigned offset
) const {
36 struct float_right_shift
{
37 int operator()(const float x
, const unsigned offset
) const {
38 return float_mem_cast
<float, int>(x
) >> offset
;
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;
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
);
56 // Verify that roughlog2 is floor(log base 2) + 1.
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
);
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()
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
);
90 base_iterations
= iterations
;
92 // sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
94 (base_iterations
* (log_min_split_count
* 2 + base_iterations
- 1))/2 +
96 BOOST_CHECK(covered_log_range
>= log_range
);
97 BOOST_CHECK(covered_log_range
- max_splits
< log_range
);
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()
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
);
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);
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()
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(),
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
,
153 BOOST_CHECK(!detail::is_sorted_or_find_extremes(sorted_input
.begin(),
156 std::greater
<int>()));
157 BOOST_CHECK(*min
== 5);
158 BOOST_CHECK(*max
== 1);
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(),
179 // Test an unsorted input.
180 BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input
.begin(),
183 BOOST_CHECK(div_min
== cast_min
);
184 BOOST_CHECK(div_max
== cast_max
);
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(),
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
,
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));
200 // Make sure bins are created correctly.
201 void size_bins_test() {
202 size_t bin_sizes
[1 << detail::max_finishing_splits
];
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;
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
);
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;
230 // test integer swap loop
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
));
252 BOOST_CHECK(next_int_bin_start
== ints
.begin() + bin_sizes
[0]);
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
);
276 BOOST_CHECK(next_float_bin_start
== floats
.begin() + bin_sizes
[0]);
279 } // end anonymous namespace
282 int test_main( int, char*[] )
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();