123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155 |
- // Boost Sort library float_sort_test.cpp file -----------------------------//
- // 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/sort/spreadsort/spreadsort.hpp>
- // Include unit test framework
- #include <boost/test/included/test_exec_monitor.hpp>
- #include <boost/test/test_tools.hpp>
- #include <vector>
- using namespace std;
- using namespace boost::sort::spreadsort;
- //Casting to an integer before bitshifting
- struct rightshift {
- int operator()(const float &x, const unsigned offset) const {
- return float_mem_cast<float, int>(x) >> offset;
- }
- };
- struct rightshift_64 {
- boost::int64_t operator()(const double &x, const boost::uint64_t offset) const
- {
- return float_mem_cast<double, boost::int64_t>(x) >> offset;
- }
- };
- boost::int32_t
- rand_32(bool sign = true) {
- boost::int32_t result = rand() | (rand()<< 16);
- if (rand() % 2)
- result |= 1 << 15;
- //Adding the sign bit
- if (sign && (rand() % 2))
- result *= -1;
- return result;
- }
- static const unsigned input_count = 1000000;
- // Helper class to run tests across all float_sort interface variants.
- template<class FloatType, class RightShift>
- void test_vector(vector<FloatType> base_vec, RightShift shifter) {
- vector<FloatType> sorted_vec = base_vec;
- vector<FloatType> test_vec = base_vec;
- std::sort(sorted_vec.begin(), sorted_vec.end());
- //Testing boost::sort::spreadsort version
- test_vec = base_vec;
- boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
- BOOST_CHECK(test_vec == sorted_vec);
- //One functor
- test_vec = base_vec;
- float_sort(test_vec.begin(), test_vec.end(), shifter);
- BOOST_CHECK(test_vec == sorted_vec);
- //Both functors
- test_vec = base_vec;
- float_sort(test_vec.begin(), test_vec.end(), shifter, less<FloatType>());
- BOOST_CHECK(test_vec == sorted_vec);
- }
- void float_test()
- {
- // Prepare inputs
- vector<float> base_vec;
- //Generating semirandom numbers that will work for basic testing
- for (unsigned u = 0; u < input_count; ++u) {
- float val = float(rand_32());
- //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0, treat all
- //those as just 0.0 for testing
- if (!(val < 0.0) && !(0.0 < val))
- base_vec.push_back(0.0);
- else
- base_vec.push_back(val);
- }
- test_vector(base_vec, rightshift());
- // Trying both positive and negative sorted and reverse sorted data.
- base_vec.clear();
- for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i);
- test_vector(base_vec, rightshift());
- base_vec.clear();
- for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count);
- test_vector(base_vec, rightshift());
- base_vec.clear();
- for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i);
- test_vector(base_vec, rightshift());
- base_vec.clear();
- for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
- test_vector(base_vec, rightshift());
- base_vec.clear();
- for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
- for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1;
- test_vector(base_vec, rightshift());
- }
- void double_test() {
- vector<double> base_vec;
- for (unsigned u = 0; u < input_count; ++u) {
- double val = double
- ((((boost::int64_t)rand_32()) << ((8 * sizeof(int)) -1)) + rand_32(false));
- //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0,
- //treat all those as just 0.0 for testing
- if (!(val < 0.0) && !(0.0 < val))
- base_vec.push_back(0.0);
- else
- base_vec.push_back(val);
- }
- test_vector(base_vec, rightshift_64());
- // Trying both positive and negative sorted and reverse sorted data.
- base_vec.clear();
- for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i);
- test_vector(base_vec, rightshift_64());
- base_vec.clear();
- for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count);
- test_vector(base_vec, rightshift_64());
- base_vec.clear();
- for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i);
- test_vector(base_vec, rightshift_64());
- base_vec.clear();
- for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
- test_vector(base_vec, rightshift_64());
- base_vec.clear();
- for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
- for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1;
- test_vector(base_vec, rightshift_64());
- }
- // Verify that 0 and 1 elements work correctly.
- void corner_test() {
- vector<float> test_vec;
- boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
- const float test_value = -0.0;
- test_vec.push_back(test_value);
- boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
- BOOST_CHECK(test_vec.size() == 1);
- BOOST_CHECK(test_vec[0] == test_value);
- }
- // test main
- int test_main( int, char*[] )
- {
- srand(1);
- float_test();
- double_test();
- corner_test();
- return 0;
- }
|