1 // Boost Sort library float_sort_test.cpp file -----------------------------//
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/sort/spreadsort/spreadsort.hpp>
11 // Include unit test framework
12 #include <boost/test/included/test_exec_monitor.hpp>
13 #include <boost/test/test_tools.hpp>
14 #include <vector>
15
16
17 using namespace std;
18 using namespace boost::sort::spreadsort;
19
20 //Casting to an integer before bitshifting
21 struct rightshift {
operator ()rightshift22 int operator()(const float &x, const unsigned offset) const {
23 return float_mem_cast<float, int>(x) >> offset;
24 }
25 };
26
27 struct rightshift_64 {
operator ()rightshift_6428 boost::int64_t operator()(const double &x, const boost::uint64_t offset) const
29 {
30 return float_mem_cast<double, boost::int64_t>(x) >> offset;
31 }
32 };
33
34 boost::int32_t
rand_32(bool sign=true)35 rand_32(bool sign = true) {
36 boost::int32_t result = rand() | (rand()<< 16);
37 if (rand() % 2)
38 result |= 1 << 15;
39 //Adding the sign bit
40 if (sign && (rand() % 2))
41 result *= -1;
42 return result;
43 }
44
45 static const unsigned input_count = 1000000;
46
47 // Helper class to run tests across all float_sort interface variants.
48 template<class FloatType, class RightShift>
test_vector(vector<FloatType> base_vec,RightShift shifter)49 void test_vector(vector<FloatType> base_vec, RightShift shifter) {
50 vector<FloatType> sorted_vec = base_vec;
51 vector<FloatType> test_vec = base_vec;
52 std::sort(sorted_vec.begin(), sorted_vec.end());
53 //Testing boost::sort::spreadsort version
54 test_vec = base_vec;
55 boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
56 BOOST_CHECK(test_vec == sorted_vec);
57 //One functor
58 test_vec = base_vec;
59 float_sort(test_vec.begin(), test_vec.end(), shifter);
60 BOOST_CHECK(test_vec == sorted_vec);
61 //Both functors
62 test_vec = base_vec;
63 float_sort(test_vec.begin(), test_vec.end(), shifter, less<FloatType>());
64 BOOST_CHECK(test_vec == sorted_vec);
65 }
66
float_test()67 void float_test()
68 {
69 // Prepare inputs
70 vector<float> base_vec;
71
72 //Generating semirandom numbers that will work for basic testing
73 for (unsigned u = 0; u < input_count; ++u) {
74 float val = float(rand_32());
75 //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0, treat all
76 //those as just 0.0 for testing
77 if (!(val < 0.0) && !(0.0 < val))
78 base_vec.push_back(0.0);
79 else
80 base_vec.push_back(val);
81 }
82 test_vector(base_vec, rightshift());
83
84 // Trying both positive and negative sorted and reverse sorted data.
85 base_vec.clear();
86 for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i);
87 test_vector(base_vec, rightshift());
88 base_vec.clear();
89 for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count);
90 test_vector(base_vec, rightshift());
91 base_vec.clear();
92 for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i);
93 test_vector(base_vec, rightshift());
94 base_vec.clear();
95 for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
96 test_vector(base_vec, rightshift());
97 base_vec.clear();
98 for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
99 for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1;
100 test_vector(base_vec, rightshift());
101 }
102
double_test()103 void double_test() {
104 vector<double> base_vec;
105 for (unsigned u = 0; u < input_count; ++u) {
106 double val = double
107 ((((boost::int64_t)rand_32()) << ((8 * sizeof(int)) -1)) + rand_32(false));
108 //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0,
109 //treat all those as just 0.0 for testing
110 if (!(val < 0.0) && !(0.0 < val))
111 base_vec.push_back(0.0);
112 else
113 base_vec.push_back(val);
114 }
115 test_vector(base_vec, rightshift_64());
116
117 // Trying both positive and negative sorted and reverse sorted data.
118 base_vec.clear();
119 for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i);
120 test_vector(base_vec, rightshift_64());
121 base_vec.clear();
122 for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count);
123 test_vector(base_vec, rightshift_64());
124 base_vec.clear();
125 for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i);
126 test_vector(base_vec, rightshift_64());
127 base_vec.clear();
128 for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
129 test_vector(base_vec, rightshift_64());
130 base_vec.clear();
131 for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i);
132 for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1;
133 test_vector(base_vec, rightshift_64());
134 }
135
136 // Verify that 0 and 1 elements work correctly.
corner_test()137 void corner_test() {
138 vector<float> test_vec;
139 boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
140 const float test_value = -0.0;
141 test_vec.push_back(test_value);
142 boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end());
143 BOOST_CHECK(test_vec.size() == 1);
144 BOOST_CHECK(test_vec[0] == test_value);
145 }
146
147 // test main
test_main(int,char * [])148 int test_main( int, char*[] )
149 {
150 srand(1);
151 float_test();
152 double_test();
153 corner_test();
154 return 0;
155 }
156