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.
22std::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
31std::vector<std::string> vec_u32_to_str(const std::vector<uint32_t>& v) {
32 std::vector<std::string> r; r.reserve(n: v.size());
33 for (size_t i = 0; i < v.size(); ++i) {
34 r.push_back(x: u32_to_str(n: v[i]));
35 }
36 return r;
37}
38
39
40// Distributions.
41std::vector<uint32_t> shuffled(size_t size, std::mt19937_64& rng) {
42 std::vector<uint32_t> v; v.reserve(n: size);
43 for (uint32_t i = 0; i < size; ++i) v.push_back(x: i);
44 std::shuffle(first: v.begin(), last: v.end(), g&: rng);
45 return v;
46}
47
48std::vector<uint32_t> shuffled_16_values(size_t size, std::mt19937_64& rng) {
49 std::vector<uint32_t> v; v.reserve(n: size);
50 for (uint32_t i = 0; i < size; ++i) v.push_back(x: i % 16);
51 std::shuffle(first: v.begin(), last: v.end(), g&: rng);
52 return v;
53}
54
55std::vector<uint32_t> all_equal(size_t size, std::mt19937_64& rng) {
56 std::vector<uint32_t> v; v.reserve(n: size);
57 for (uint32_t i = 0; i < size; ++i) v.push_back(x: 0);
58 return v;
59}
60
61std::vector<uint32_t> ascending(size_t size, std::mt19937_64& rng) {
62 std::vector<uint32_t> v; v.reserve(n: size);
63 for (uint32_t i = 0; i < size; ++i) v.push_back(x: i);
64 return v;
65}
66
67std::vector<uint32_t> descending(size_t size, std::mt19937_64& rng) {
68 std::vector<uint32_t> v; v.reserve(n: size);
69 for (uint32_t i = size - 1; ; --i) {
70 v.push_back(x: i);
71 if (i == 0) break;
72 }
73 return v;
74}
75
76std::vector<uint32_t> pipe_organ(size_t size, std::mt19937_64& rng) {
77 std::vector<uint32_t> v; v.reserve(n: size);
78 for (uint32_t i = 0; i < size/2; ++i) v.push_back(x: i);
79 for (uint32_t i = size/2; i < size; ++i) v.push_back(x: size - i);
80 return v;
81}
82
83std::vector<uint32_t> push_front(size_t size, std::mt19937_64& rng) {
84 std::vector<uint32_t> v; v.reserve(n: size);
85 for (uint32_t i = 1; i < size; ++i) v.push_back(x: i);
86 v.push_back(x: 0);
87 return v;
88}
89
90std::vector<uint32_t> push_middle(size_t size, std::mt19937_64& rng) {
91 std::vector<uint32_t> v; v.reserve(n: size);
92 for (uint32_t i = 0; i < size; ++i) {
93 if (i != size/2) v.push_back(x: i);
94 }
95 v.push_back(x: size/2);
96 return v;
97}
98
99
100// Tests.
101typedef std::vector<uint32_t> (*DistrF)(size_t, std::mt19937_64&);
102void 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(sd: 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(v: u32l);
117 std::vector<std::string> sg = sl;
118
119 boost::sort::pdqsort(first: u32l.begin(), last: u32l.end(), comp: u32less);
120 boost::sort::pdqsort(first: u32g.begin(), last: u32g.end(), comp: u32greater);
121 boost::sort::pdqsort(first: sl.begin(), last: sl.end(), comp: sless);
122 boost::sort::pdqsort(first: sg.begin(), last: sg.end(), comp: 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
149int test_main(int argc, char** argv) {
150 // No unused warning.
151 (void) argc; (void) argv;
152
153 execute_test(distr: shuffled, distr_name: "shuffled", repeats: 100);
154 execute_test(distr: shuffled_16_values, distr_name: "shuffled_16_values", repeats: 100);
155 execute_test(distr: all_equal, distr_name: "all_equal", repeats: 1);
156 execute_test(distr: ascending, distr_name: "ascending", repeats: 1);
157 execute_test(distr: descending, distr_name: "descending", repeats: 1);
158 execute_test(distr: pipe_organ, distr_name: "pipe_organ", repeats: 1);
159 execute_test(distr: push_front, distr_name: "push_front", repeats: 1);
160 execute_test(distr: push_middle, distr_name: "push_middle", repeats: 1);
161
162 return 0;
163}
164

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