]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/sort/test/test_pdqsort.cpp
1 // Boost Sort library test_pdqsort.cpp file ----------------------------//
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)
8 // See http://www.boost.org/libs/sort for library home page.
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>
21 // Gives a vector containing strings with the same order.
22 std::string
u32_to_str(uint32_t n
) {
24 for (int i
= 0; i
< 32; ++i
) {
25 r
= char('0' + (n
& 1)) + r
;
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
]));
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
);
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
);
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);
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
);
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
) {
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
);
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
);
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
);
101 typedef std::vector
<uint32_t> (*DistrF
)(size_t, std::mt19937_64
&);
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
;
109 for (size_t sz
= 1; sz
<= 1000; sz
*= 10) {
110 // Consistent but pseudorandom tests.
111 std::mt19937_64 rng
; rng
.seed(0);
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
;
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
);
125 std::is_sorted(u32l
.begin(), u32l
.end(), u32less
),
126 "pdqsort<uint32_t, std::less> " + distr_name
+ " failed with size " + std::to_string(sz
)
130 std::is_sorted(u32g
.begin(), u32g
.end(), u32greater
),
131 "pdqsort<uint32_t, std::greater> " + distr_name
+ " failed with size " + std::to_string(sz
)
135 std::is_sorted(sl
.begin(), sl
.end(), sless
),
136 "pdqsort<std::string, std::less> " + distr_name
+ " failed with size " + std::to_string(sz
)
140 std::is_sorted(sg
.begin(), sg
.end(), sgreater
),
141 "pdqsort<std::string, std::greater> " + distr_name
+ " failed with size " + std::to_string(sz
)
149 int test_main(int argc
, char** argv
) {
150 // No unused warning.
151 (void) argc
; (void) argv
;
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);