1 // Boost Sort library test_pdqsort.cpp file ----------------------------//
2
3 // Copyright Orson Peters 2017. 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
11 #include <vector>
12 #include <string>
13 #include <random>
14
15 #include <boost/sort/pdqsort/pdqsort.hpp>
16 // Include unit test framework
17 #include <boost/test/included/test_exec_monitor.hpp>
18 #include <boost/test/test_tools.hpp>
19
20
21 // Gives a vector containing strings with the same order.
u32_to_str(uint32_t n)22 std::string u32_to_str(uint32_t n) {
23 std::string r;
24 for (int i = 0; i < 32; ++i) {
25 r = char('0' + (n & 1)) + r;
26 n >>= 1;
27 }
28 return r;
29 }
30
vec_u32_to_str(const std::vector<uint32_t> & v)31 std::vector<std::string> vec_u32_to_str(const std::vector<uint32_t>& v) {
32 std::vector<std::string> r; r.reserve(v.size());
33 for (size_t i = 0; i < v.size(); ++i) {
34 r.push_back(u32_to_str(v[i]));
35 }
36 return r;
37 }
38
39
40 // Distributions.
shuffled(size_t size,std::mt19937_64 & rng)41 std::vector<uint32_t> shuffled(size_t size, std::mt19937_64& rng) {
42 std::vector<uint32_t> v; v.reserve(size);
43 for (uint32_t i = 0; i < size; ++i) v.push_back(i);
44 std::shuffle(v.begin(), v.end(), rng);
45 return v;
46 }
47
shuffled_16_values(size_t size,std::mt19937_64 & rng)48 std::vector<uint32_t> shuffled_16_values(size_t size, std::mt19937_64& rng) {
49 std::vector<uint32_t> v; v.reserve(size);
50 for (uint32_t i = 0; i < size; ++i) v.push_back(i % 16);
51 std::shuffle(v.begin(), v.end(), rng);
52 return v;
53 }
54
all_equal(size_t size,std::mt19937_64 & rng)55 std::vector<uint32_t> all_equal(size_t size, std::mt19937_64& rng) {
56 std::vector<uint32_t> v; v.reserve(size);
57 for (uint32_t i = 0; i < size; ++i) v.push_back(0);
58 return v;
59 }
60
ascending(size_t size,std::mt19937_64 & rng)61 std::vector<uint32_t> ascending(size_t size, std::mt19937_64& rng) {
62 std::vector<uint32_t> v; v.reserve(size);
63 for (uint32_t i = 0; i < size; ++i) v.push_back(i);
64 return v;
65 }
66
descending(size_t size,std::mt19937_64 & rng)67 std::vector<uint32_t> descending(size_t size, std::mt19937_64& rng) {
68 std::vector<uint32_t> v; v.reserve(size);
69 for (uint32_t i = size - 1; ; --i) {
70 v.push_back(i);
71 if (i == 0) break;
72 }
73 return v;
74 }
75
pipe_organ(size_t size,std::mt19937_64 & rng)76 std::vector<uint32_t> pipe_organ(size_t size, std::mt19937_64& rng) {
77 std::vector<uint32_t> v; v.reserve(size);
78 for (uint32_t i = 0; i < size/2; ++i) v.push_back(i);
79 for (uint32_t i = size/2; i < size; ++i) v.push_back(size - i);
80 return v;
81 }
82
push_front(size_t size,std::mt19937_64 & rng)83 std::vector<uint32_t> push_front(size_t size, std::mt19937_64& rng) {
84 std::vector<uint32_t> v; v.reserve(size);
85 for (uint32_t i = 1; i < size; ++i) v.push_back(i);
86 v.push_back(0);
87 return v;
88 }
89
push_middle(size_t size,std::mt19937_64 & rng)90 std::vector<uint32_t> push_middle(size_t size, std::mt19937_64& rng) {
91 std::vector<uint32_t> v; v.reserve(size);
92 for (uint32_t i = 0; i < size; ++i) {
93 if (i != size/2) v.push_back(i);
94 }
95 v.push_back(size/2);
96 return v;
97 }
98
99
100 // Tests.
101 typedef std::vector<uint32_t> (*DistrF)(size_t, std::mt19937_64&);
execute_test(DistrF distr,std::string distr_name,int repeats)102 void execute_test(DistrF distr, std::string distr_name, int repeats) {
103 // In C++14 we'd just use std::less<>().
104 std::less<uint32_t> u32less;
105 std::greater<uint32_t> u32greater;
106 std::less<std::string> sless;
107 std::greater<std::string> sgreater;
108
109 for (size_t sz = 1; sz <= 1000; sz *= 10) {
110 // Consistent but pseudorandom tests.
111 std::mt19937_64 rng; rng.seed(0);
112
113 for (int i = 0; i < repeats; ++i) {
114 std::vector<uint32_t> u32l = distr(sz, rng);
115 std::vector<uint32_t> u32g = u32l;
116 std::vector<std::string> sl = vec_u32_to_str(u32l);
117 std::vector<std::string> sg = sl;
118
119 boost::sort::pdqsort(u32l.begin(), u32l.end(), u32less);
120 boost::sort::pdqsort(u32g.begin(), u32g.end(), u32greater);
121 boost::sort::pdqsort(sl.begin(), sl.end(), sless);
122 boost::sort::pdqsort(sg.begin(), sg.end(), sgreater);
123
124 BOOST_CHECK_MESSAGE(
125 std::is_sorted(u32l.begin(), u32l.end(), u32less),
126 "pdqsort<uint32_t, std::less> " + distr_name + " failed with size " + std::to_string(sz)
127 );
128
129 BOOST_CHECK_MESSAGE(
130 std::is_sorted(u32g.begin(), u32g.end(), u32greater),
131 "pdqsort<uint32_t, std::greater> " + distr_name + " failed with size " + std::to_string(sz)
132 );
133
134 BOOST_CHECK_MESSAGE(
135 std::is_sorted(sl.begin(), sl.end(), sless),
136 "pdqsort<std::string, std::less> " + distr_name + " failed with size " + std::to_string(sz)
137 );
138
139 BOOST_CHECK_MESSAGE(
140 std::is_sorted(sg.begin(), sg.end(), sgreater),
141 "pdqsort<std::string, std::greater> " + distr_name + " failed with size " + std::to_string(sz)
142 );
143 }
144 }
145 }
146
147
148 // test main
test_main(int argc,char ** argv)149 int test_main(int argc, char** argv) {
150 // No unused warning.
151 (void) argc; (void) argv;
152
153 execute_test(shuffled, "shuffled", 100);
154 execute_test(shuffled_16_values, "shuffled_16_values", 100);
155 execute_test(all_equal, "all_equal", 1);
156 execute_test(ascending, "ascending", 1);
157 execute_test(descending, "descending", 1);
158 execute_test(pipe_organ, "pipe_organ", 1);
159 execute_test(push_front, "push_front", 1);
160 execute_test(push_middle, "push_middle", 1);
161
162 return 0;
163 }
164