1// Boost Sort library int_test.cpp file ------------------------------------//
2
3// Copyright Steven Ross 2009-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/cstdint.hpp>
11#include <boost/sort/spreadsort/spreadsort.hpp>
12// Include unit test framework
13#include <boost/test/included/test_exec_monitor.hpp>
14#include <boost/test/test_tools.hpp>
15#include <vector>
16
17#include <iostream>
18
19
20using namespace std;
21using namespace boost::sort::spreadsort;
22
23struct rightshift {
24 int operator()(int x, unsigned offset) { return x >> offset; }
25};
26
27struct rightshift_max {
28 boost::intmax_t operator()(const boost::intmax_t &x, unsigned offset) {
29 return x >> offset;
30 }
31};
32
33struct negrightshift {
34 int operator()(const int &x, const unsigned offset) { return -(x >> offset); }
35};
36
37struct negrightshift_max {
38 boost::intmax_t operator()(const boost::intmax_t &x, const unsigned offset) {
39 return -(x >> offset);
40 }
41};
42
43boost::int32_t
44rand_32(bool sign = true) {
45 boost::int32_t result = rand() | (rand()<< 16);
46 if (rand() % 2)
47 result |= 1 << 15;
48 //Adding the sign bit
49 if (sign && (rand() % 2))
50 result *= -1;
51 return result;
52}
53
54void int_test()
55{
56 // Prepare inputs
57 vector<int> base_vec;
58 unsigned count = 100000;
59 srand(seed: 1);
60 //Generating semirandom numbers
61 for (unsigned u = 0; u < count; ++u)
62 base_vec.push_back(x: rand_32());
63 vector<int> sorted_vec = base_vec;
64 vector<int> test_vec = base_vec;
65 std::sort(first: sorted_vec.begin(), last: sorted_vec.end());
66 //Testing basic call
67 integer_sort(first: test_vec.begin(), last: test_vec.end());
68 BOOST_CHECK(test_vec == sorted_vec);
69 //boost::sort::spreadsort variant
70 test_vec = base_vec;
71 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
72 BOOST_CHECK(test_vec == sorted_vec);
73 //One functor
74 test_vec = base_vec;
75 integer_sort(first: test_vec.begin(), last: test_vec.end(), shift: rightshift());
76 BOOST_CHECK(test_vec == sorted_vec);
77 //Both functors
78 test_vec = base_vec;
79 integer_sort(first: test_vec.begin(), last: test_vec.end(), shift: rightshift(), comp: less<int>());
80 BOOST_CHECK(test_vec == sorted_vec);
81 //reverse order
82 std::sort(first: sorted_vec.begin(), last: sorted_vec.end(), comp: greater<int>());
83 integer_sort(first: test_vec.begin(), last: test_vec.end(), shift: negrightshift(),
84 comp: greater<int>());
85 BOOST_CHECK(test_vec == sorted_vec);
86
87 //Making sure we're correctly sorting boost::intmax_ts; should use std::sort
88 vector<boost::intmax_t> long_base_vec;
89 for (unsigned u = 0; u < base_vec.size(); ++u)
90 long_base_vec.push_back(x: (((boost::intmax_t)rand_32()) <<
91 ((8 * sizeof(int)) -1)) + rand_32(sign: false));
92 vector<boost::intmax_t> long_sorted_vec = long_base_vec;
93 vector<boost::intmax_t> long_test_vec = long_base_vec;
94 integer_sort(first: long_test_vec.begin(), last: long_test_vec.end());
95 std::sort(first: long_sorted_vec.begin(), last: long_sorted_vec.end());
96 BOOST_CHECK(long_test_vec == long_sorted_vec);
97 //One functor
98 long_test_vec = long_base_vec;
99 integer_sort(first: long_test_vec.begin(), last: long_test_vec.end(), shift: rightshift_max());
100 BOOST_CHECK(long_test_vec == long_sorted_vec);
101 //Both functors
102 long_test_vec = long_base_vec;
103 integer_sort(first: long_test_vec.begin(), last: long_test_vec.end(), shift: rightshift_max(),
104 comp: less<boost::intmax_t>());
105 BOOST_CHECK(long_test_vec == long_sorted_vec);
106 //reverse order
107 std::sort(first: long_sorted_vec.begin(), last: long_sorted_vec.end(),
108 comp: greater<boost::intmax_t>());
109 integer_sort(first: long_test_vec.begin(), last: long_test_vec.end(), shift: negrightshift_max(),
110 comp: greater<boost::intmax_t>());
111 BOOST_CHECK(long_test_vec == long_sorted_vec);
112}
113
114// Verify that 0 and 1 elements work correctly.
115void corner_test() {
116 vector<int> test_vec;
117 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
118 const int test_value = 42;
119 test_vec.push_back(x: test_value);
120 boost::sort::spreadsort::spreadsort(first: test_vec.begin(), last: test_vec.end());
121 BOOST_CHECK(test_vec.size() == 1);
122 BOOST_CHECK(test_vec[0] == test_value);
123}
124
125// test main
126int test_main( int, char*[] )
127{
128 int_test();
129 corner_test();
130 return 0;
131}
132

source code of boost/libs/sort/test/integer_sort_test.cpp