1/*=============================================================================
2 Copyright (c) 2010 Tim Blechmann
3
4 Use, modification and distribution is subject to the Boost Software
5 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
7=============================================================================*/
8
9// random uses boost.fusion, which clashes with boost.test
10//#define USE_BOOST_RANDOM
11
12#ifdef USE_BOOST_RANDOM
13#include <boost/random.hpp>
14#else
15#include <cstdlib>
16#endif
17
18#include "common_heap_tests.hpp"
19
20
21#define PUSH_WITH_HANDLES(HANDLES, Q, DATA) \
22 std::vector<typename pri_queue::handle_type> HANDLES; \
23 \
24 for (unsigned int k = 0; k != data.size(); ++k) \
25 HANDLES.push_back(Q.push(DATA[k]));
26
27
28
29template <typename pri_queue>
30void pri_queue_test_update_decrease(void)
31{
32 for (int i = 0; i != test_size; ++i) {
33 pri_queue q;
34 test_data data = make_test_data(size: test_size);
35 PUSH_WITH_HANDLES(handles, q, data);
36
37 *handles[i] = -1;
38 data[i] = -1;
39 q.update(handles[i]);
40
41 std::sort(first: data.begin(), last: data.end());
42 check_q(q, data);
43 }
44}
45
46template <typename pri_queue>
47void pri_queue_test_update_decrease_function(void)
48{
49 for (int i = 0; i != test_size; ++i) {
50 pri_queue q;
51 test_data data = make_test_data(size: test_size);
52 PUSH_WITH_HANDLES(handles, q, data);
53
54 data[i] = -1;
55 q.update(handles[i], -1);
56
57 std::sort(first: data.begin(), last: data.end());
58 check_q(q, data);
59 }
60}
61
62template <typename pri_queue>
63void pri_queue_test_update_function_identity(void)
64{
65 for (int i = 0; i != test_size; ++i) {
66 pri_queue q;
67 test_data data = make_test_data(size: test_size);
68 PUSH_WITH_HANDLES(handles, q, data);
69
70 q.update(handles[i], data[i]);
71
72 std::sort(first: data.begin(), last: data.end());
73 check_q(q, data);
74 }
75}
76
77template <typename pri_queue>
78void pri_queue_test_update_shuffled(void)
79{
80 pri_queue q;
81 test_data data = make_test_data(size: test_size);
82 PUSH_WITH_HANDLES(handles, q, data);
83
84 test_data shuffled (data);
85 random_shuffle(first: shuffled.begin(), last: shuffled.end());
86
87 for (int i = 0; i != test_size; ++i)
88 q.update(handles[i], shuffled[i]);
89
90 check_q(q, data);
91}
92
93
94template <typename pri_queue>
95void pri_queue_test_update_increase(void)
96{
97 for (int i = 0; i != test_size; ++i) {
98 pri_queue q;
99 test_data data = make_test_data(size: test_size);
100 PUSH_WITH_HANDLES(handles, q, data);
101
102 data[i] = data.back()+1;
103 *handles[i] = data[i];
104 q.update(handles[i]);
105
106 std::sort(first: data.begin(), last: data.end());
107 check_q(q, data);
108 }
109}
110
111template <typename pri_queue>
112void pri_queue_test_update_increase_function(void)
113{
114 for (int i = 0; i != test_size; ++i) {
115 pri_queue q;
116 test_data data = make_test_data(size: test_size);
117 PUSH_WITH_HANDLES(handles, q, data);
118
119 data[i] = data.back()+1;
120 q.update(handles[i], data[i]);
121
122 std::sort(first: data.begin(), last: data.end());
123 check_q(q, data);
124 }
125}
126
127template <typename pri_queue>
128void pri_queue_test_decrease(void)
129{
130 for (int i = 0; i != test_size; ++i) {
131 pri_queue q;
132 test_data data = make_test_data(size: test_size);
133 PUSH_WITH_HANDLES(handles, q, data);
134
135 *handles[i] = -1;
136 data[i] = -1;
137 q.decrease(handles[i]);
138
139 std::sort(first: data.begin(), last: data.end());
140 check_q(q, data);
141 }
142}
143
144template <typename pri_queue>
145void pri_queue_test_decrease_function(void)
146{
147 for (int i = 0; i != test_size; ++i) {
148 pri_queue q;
149 test_data data = make_test_data(size: test_size);
150 PUSH_WITH_HANDLES(handles, q, data);
151
152 data[i] = -1;
153 q.decrease(handles[i], -1);
154
155 std::sort(first: data.begin(), last: data.end());
156 check_q(q, data);
157 }
158}
159
160template <typename pri_queue>
161void pri_queue_test_decrease_function_identity(void)
162{
163 for (int i = 0; i != test_size; ++i) {
164 pri_queue q;
165 test_data data = make_test_data(size: test_size);
166 PUSH_WITH_HANDLES(handles, q, data);
167
168 q.decrease(handles[i], data[i]);
169
170 check_q(q, data);
171 }
172}
173
174
175template <typename pri_queue>
176void pri_queue_test_increase(void)
177{
178 for (int i = 0; i != test_size; ++i) {
179 pri_queue q;
180 test_data data = make_test_data(size: test_size);
181 PUSH_WITH_HANDLES(handles, q, data);
182
183 data[i] = data.back()+1;
184 *handles[i] = data[i];
185 q.increase(handles[i]);
186
187 std::sort(first: data.begin(), last: data.end());
188 check_q(q, data);
189 }
190}
191
192template <typename pri_queue>
193void pri_queue_test_increase_function(void)
194{
195 for (int i = 0; i != test_size; ++i) {
196 pri_queue q;
197 test_data data = make_test_data(size: test_size);
198 PUSH_WITH_HANDLES(handles, q, data);
199
200 data[i] = data.back()+1;
201 q.increase(handles[i], data[i]);
202
203 std::sort(first: data.begin(), last: data.end());
204 check_q(q, data);
205 }
206}
207
208template <typename pri_queue>
209void pri_queue_test_increase_function_identity(void)
210{
211 for (int i = 0; i != test_size; ++i) {
212 pri_queue q;
213 test_data data = make_test_data(size: test_size);
214 PUSH_WITH_HANDLES(handles, q, data);
215
216 q.increase(handles[i], data[i]);
217
218 check_q(q, data);
219 }
220}
221
222template <typename pri_queue>
223void pri_queue_test_erase(void)
224{
225#ifdef USE_BOOST_RANDOM
226 boost::mt19937 rng;
227#endif
228
229 for (int i = 0; i != test_size; ++i)
230 {
231 pri_queue q;
232 test_data data = make_test_data(size: test_size);
233 PUSH_WITH_HANDLES(handles, q, data);
234
235 for (int j = 0; j != i; ++j)
236 {
237#ifdef USE_BOOST_RANDOM
238 boost::uniform_int<> range(0, data.size() - 1);
239 boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, range);
240
241 int index = gen();
242#else
243 int index = std::rand() % (data.size() - 1);
244#endif
245 q.erase(handles[index]);
246 handles.erase(handles.begin() + index);
247 data.erase(position: data.begin() + index);
248 }
249
250 std::sort(first: data.begin(), last: data.end());
251 check_q(q, data);
252 }
253}
254
255
256template <typename pri_queue>
257void run_mutable_heap_update_tests(void)
258{
259 pri_queue_test_update_increase<pri_queue>();
260 pri_queue_test_update_decrease<pri_queue>();
261
262 pri_queue_test_update_shuffled<pri_queue>();
263}
264
265template <typename pri_queue>
266void run_mutable_heap_update_function_tests(void)
267{
268 pri_queue_test_update_increase_function<pri_queue>();
269 pri_queue_test_update_decrease_function<pri_queue>();
270 pri_queue_test_update_function_identity<pri_queue>();
271}
272
273
274template <typename pri_queue>
275void run_mutable_heap_decrease_tests(void)
276{
277 pri_queue_test_decrease<pri_queue>();
278 pri_queue_test_decrease_function<pri_queue>();
279 pri_queue_test_decrease_function_identity<pri_queue>();
280}
281
282template <typename pri_queue>
283void run_mutable_heap_increase_tests(void)
284{
285 pri_queue_test_increase<pri_queue>();
286 pri_queue_test_increase_function<pri_queue>();
287 pri_queue_test_increase_function_identity<pri_queue>();
288}
289
290template <typename pri_queue>
291void run_mutable_heap_erase_tests(void)
292{
293 pri_queue_test_erase<pri_queue>();
294}
295
296template <typename pri_queue>
297void run_mutable_heap_test_handle_from_iterator(void)
298{
299 pri_queue que;
300
301 que.push(3);
302 que.push(1);
303 que.push(4);
304
305 que.update(pri_queue::s_handle_from_iterator(que.begin()),
306 6);
307}
308
309
310template <typename pri_queue>
311void run_mutable_heap_tests(void)
312{
313 run_mutable_heap_update_function_tests<pri_queue>();
314 run_mutable_heap_update_tests<pri_queue>();
315 run_mutable_heap_decrease_tests<pri_queue>();
316 run_mutable_heap_increase_tests<pri_queue>();
317 run_mutable_heap_erase_tests<pri_queue>();
318 run_mutable_heap_test_handle_from_iterator<pri_queue>();
319}
320
321template <typename pri_queue>
322void run_ordered_iterator_tests()
323{
324 pri_queue_test_ordered_iterators<pri_queue>();
325}
326

source code of boost/libs/heap/test/mutable_heap_tests.hpp