123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294 |
- // Boost Sort library tests for integer_sort and float_sort details.
- // Copyright Steven Ross 2014. Use, modification and
- // distribution is subject to the Boost Software License, Version
- // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // See http://www.boost.org/libs/sort for library home page.
- #include <boost/cstdint.hpp>
- #include <boost/sort/spreadsort/detail/spreadsort_common.hpp>
- #include <boost/sort/spreadsort/detail/integer_sort.hpp>
- #include <boost/sort/spreadsort/detail/float_sort.hpp>
- #include <boost/sort/spreadsort/detail/string_sort.hpp>
- #include <boost/sort/spreadsort/float_sort.hpp>
- // Include unit test framework
- #include <boost/test/included/test_exec_monitor.hpp>
- #include <boost/test/test_tools.hpp>
- #include <vector>
- #include <iostream>
- using namespace std;
- using namespace boost::sort::spreadsort;
- using namespace boost::sort::spreadsort::detail;
- namespace {
- struct int_right_shift {
- int operator()(const int x, const unsigned offset) const {
- return x >> offset;
- }
- };
- struct float_right_shift {
- int operator()(const float x, const unsigned offset) const {
- return float_mem_cast<float, int>(x) >> offset;
- }
- };
- const int max_int_bits = sizeof(boost::uintmax_t) * 8;
- const int max_size_bits = sizeof(size_t) * 8;
- const boost::uintmax_t one = 1;
- // spreadsort won't recurse for inputs smaller than min_count.
- const int int_min_log_count =
- (std::min)((int)int_log_finishing_count,
- (int)int_log_mean_bin_size + int_log_min_split_count);
- const int float_min_log_count =
- (std::min)((int)float_log_finishing_count,
- (int)float_log_mean_bin_size + float_log_min_split_count);
- const unsigned absolute_min_count = (std::min)(1 << int_min_log_count,
- 1 << float_min_log_count);
- // Verify that roughlog2 is floor(log base 2) + 1.
- void roughlog2_test()
- {
- for (boost::uintmax_t i = 0; i < max_int_bits; ++i) {
- BOOST_CHECK(detail::rough_log_2_size(one << i) == i + 1);
- BOOST_CHECK(detail::rough_log_2_size((one << i) - 1) == i);
- }
- }
- // Test the worst-case performance handling, and assure that is using the
- // correct formula for the worst-case number of radix iterations.
- template<unsigned log_mean_bin_size, unsigned log_min_split_count,
- unsigned log_finishing_count>
- void get_min_count_test()
- {
- const unsigned min_log_size = log_mean_bin_size + log_min_split_count;
- size_t prev_min_count = absolute_min_count;
- for (int log_range = 0; log_range <= max_int_bits; ++log_range) {
- size_t min_count = get_min_count<log_mean_bin_size, log_min_split_count,
- log_finishing_count>(log_range);
- BOOST_CHECK(min_count >= prev_min_count);
- prev_min_count = min_count;
- // When the range is really small, the radix sort will complete in one
- // iteration and worst-case handling doesn't apply. The code below
- // guarantees the worst-case number of radix sorting iteration.
- if (log_range > min_log_size) {
- BOOST_CHECK(min_count >= (1 << min_log_size));
- int iterations = rough_log_2_size(min_count) - min_log_size;
- BOOST_CHECK(iterations >= 1);
- int base_iterations = max_splits - log_min_split_count;
- int covered_log_range = 0;
- if (iterations > base_iterations) {
- covered_log_range += max_splits * (iterations - base_iterations);
- } else {
- base_iterations = iterations;
- }
- // sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
- covered_log_range +=
- (base_iterations * (log_min_split_count * 2 + base_iterations - 1))/2 +
- log_mean_bin_size;
- BOOST_CHECK(covered_log_range >= log_range);
- BOOST_CHECK(covered_log_range - max_splits < log_range);
- }
- }
- }
- // Test the decision of how many pieces to split up the radix sort into
- // (roughly 2^(log_range - log_divisor)) to make sure the results are logical.
- void get_log_divisor_test()
- {
- for (int log_range = 0; log_range <= max_int_bits; ++log_range) {
- int prev_log_divisor = max_int_bits +
- (std::max)((int)int_log_mean_bin_size, (int)float_log_mean_bin_size);
- for (int log_count = 0; log_count < max_size_bits; ++log_count) {
- size_t count = (one << log_count) - 1;
- BOOST_CHECK(rough_log_2_size(count) == (unsigned)log_count);
- int log_divisor =
- get_log_divisor<int_log_mean_bin_size>(count, log_range);
- // Only process counts >= int_log_finishing_count in this function.
- if (count >= absolute_min_count)
- BOOST_CHECK(log_divisor <= log_range);
- // More pieces should be used the larger count is.
- BOOST_CHECK(log_divisor <= prev_log_divisor);
- prev_log_divisor = log_divisor;
- BOOST_CHECK(log_divisor >= 0);
- if (log_range > log_count) {
- BOOST_CHECK(log_range - log_divisor <= max_splits);
- } else if (log_range <= max_finishing_splits) {
- BOOST_CHECK(log_divisor == 0);
- }
- }
- }
- }
- // Verify that is_sorted_or_find_extremes returns true if the data is sorted,
- // and otherwise returns the actual min and max.
- void is_sorted_or_find_extremes_test()
- {
- vector<int> input;
- input.push_back(3);
- input.push_back(5);
- input.push_back(1);
- // Test a sorted input.
- vector<int> sorted_input(input);
- std::sort(sorted_input.begin(), sorted_input.end());
- vector<int>::iterator max, min;
- BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(),
- sorted_input.end(), max, min));
- // Test an unsorted input.
- BOOST_CHECK(!detail::is_sorted_or_find_extremes(input.begin(), input.end(),
- max, min));
- BOOST_CHECK(*min == 1);
- BOOST_CHECK(*max == 5);
- // Test the comparison function version.
- BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(),
- sorted_input.end(), max, min,
- std::less<int>()));
- BOOST_CHECK(!detail::is_sorted_or_find_extremes(sorted_input.begin(),
- sorted_input.end(),
- max, min,
- std::greater<int>()));
- BOOST_CHECK(*min == 5);
- BOOST_CHECK(*max == 1);
- // Test with floats
- vector<float> float_input;
- float_input.push_back(.3f);
- float_input.push_back(4.0f);
- float_input.push_back(.1f);
- vector<float> sorted_float_input(float_input);
- std::sort(sorted_float_input.begin(), sorted_float_input.end());
- // Test cast_float_iter
- int cast_min = detail::cast_float_iter<int, vector<float>::iterator>(
- sorted_float_input.begin());
- int cast_max = detail::cast_float_iter<int, vector<float>::iterator>(
- sorted_float_input.end() - 1);
- BOOST_CHECK(cast_min == float_right_shift()(.1f, 0));
- BOOST_CHECK(cast_max == float_right_shift()(4.0f, 0));
- // Test a sorted input
- int div_max, div_min;
- BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(),
- sorted_float_input.end(),
- div_max, div_min));
- // Test an unsorted input.
- BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(),
- float_input.end(),
- div_max, div_min));
- BOOST_CHECK(div_min == cast_min);
- BOOST_CHECK(div_max == cast_max);
- // Test with a right_shift functor.
- BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(),
- sorted_float_input.end(),
- div_max, div_min,
- float_right_shift()));
- // Test an unsorted input.
- BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(),
- float_input.end(), div_max,
- div_min,
- float_right_shift()));
- BOOST_CHECK(div_min == float_right_shift()(.1f, 0));
- BOOST_CHECK(div_max == float_right_shift()(4.0f, 0));
- }
- // Make sure bins are created correctly.
- void size_bins_test() {
- size_t bin_sizes[1 << detail::max_finishing_splits];
- bin_sizes[0] = 1;
- bin_sizes[2] = 7;
- const int old_bin_value = 7;
- std::vector<int> old_bins;
- old_bins.push_back(old_bin_value);
- std::vector<vector<int>::iterator> bin_cache;
- bin_cache.push_back(old_bins.begin());
- unsigned cache_offset = 1;
- unsigned cache_end;
- const unsigned bin_count = 2;
- std::vector<int>::iterator *new_cache_start =
- size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
- BOOST_CHECK((new_cache_start - &bin_cache[0]) == cache_offset);
- BOOST_CHECK(bin_sizes[0] == 0);
- BOOST_CHECK(bin_sizes[1] == 0);
- BOOST_CHECK(bin_sizes[2] == 7); // shouldn't modify past bin_count
- BOOST_CHECK(cache_end == 3);
- BOOST_CHECK(bin_cache.size() == cache_end);
- BOOST_CHECK(old_bins[0] == old_bin_value);
- }
- // Test the specialized 3-way swap loops.
- void swap_loop_test() {
- size_t bin_sizes[1 << detail::max_finishing_splits];
- bin_sizes[0] = bin_sizes[1] = 2;
- bin_sizes[2] = 1;
- // test integer swap loop
- vector<int> ints;
- const int int_div_min = 3;
- const int int_log_divisor = 1;
- const unsigned int_offset = int_div_min << int_log_divisor;
- ints.push_back(2 + int_offset);
- ints.push_back(1 + int_offset); // stays in place
- ints.push_back(4 + int_offset);
- ints.push_back(3 + int_offset);
- ints.push_back(0 + int_offset);
- vector<vector<int>::iterator> int_bin_vector;
- int_bin_vector.push_back(ints.begin());
- int_bin_vector.push_back(int_bin_vector[0] + bin_sizes[0]);
- int_bin_vector.push_back(int_bin_vector[1] + bin_sizes[1]);
- vector<int>::iterator next_int_bin_start = int_bin_vector[0];
- vector<int>::iterator *int_bins = &int_bin_vector[0];
- int_right_shift integer_right_shift;
- swap_loop(int_bins, next_int_bin_start, 0, integer_right_shift, bin_sizes,
- int_log_divisor, int_div_min);
- for (unsigned i = 0; i < ints.size(); ++i) {
- BOOST_CHECK(ints[i] == int(int_offset + i));
- }
- BOOST_CHECK(next_int_bin_start == ints.begin() + bin_sizes[0]);
- // test float swap loop
- vector<float> floats;
- const int float_four_as_int = float_mem_cast<float, int>(4.0f);
- const int float_log_divisor =
- rough_log_2_size(float_mem_cast<float, int>(5.0f) - float_four_as_int);
- const int float_div_min = float_four_as_int >> float_log_divisor;
- floats.push_back(6.0f);
- floats.push_back(5.0f); // stays in place
- floats.push_back(8.0f);
- floats.push_back(7.0f);
- floats.push_back(4.0f);
- vector<vector<float>::iterator> float_bin_vector;
- float_bin_vector.push_back(floats.begin());
- float_bin_vector.push_back(float_bin_vector[0] + bin_sizes[0]);
- float_bin_vector.push_back(float_bin_vector[1] + bin_sizes[1]);
- vector<float>::iterator next_float_bin_start = float_bin_vector[0];
- vector<float>::iterator *float_bins = &float_bin_vector[0];
- float_swap_loop(float_bins, next_float_bin_start, 0, bin_sizes,
- float_log_divisor, float_div_min);
- for (unsigned i = 0; i < floats.size(); ++i) {
- BOOST_CHECK(floats[i] == 4.0f + i);
- }
- BOOST_CHECK(next_float_bin_start == floats.begin() + bin_sizes[0]);
- }
- } // end anonymous namespace
- // test main
- int test_main( int, char*[] )
- {
- roughlog2_test();
- get_min_count_test<int_log_mean_bin_size, int_log_min_split_count,
- int_log_finishing_count>();
- get_min_count_test<float_log_mean_bin_size, float_log_min_split_count,
- float_log_finishing_count>();
- get_log_divisor_test();
- is_sorted_or_find_extremes_test();
- size_bins_test();
- swap_loop_test();
- return 0;
- }
|