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