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 #ifndef COMMON_HEAP_TESTS_HPP_INCLUDED
10 #define COMMON_HEAP_TESTS_HPP_INCLUDED
11
12 #include <algorithm>
13 #include <vector>
14
15 #include <boost/concept/assert.hpp>
16 #include <boost/concept_archetype.hpp>
17 #include <boost/shared_ptr.hpp>
18
19 #include <boost/heap/heap_concepts.hpp>
20
21 #ifdef BOOST_NO_CXX98_RANDOM_SHUFFLE
22 #include <cstdlib>
23 #include <iterator>
24
25 template<class RandomIt>
random_shuffle(RandomIt first,RandomIt last)26 void random_shuffle(RandomIt first, RandomIt last)
27 {
28 typedef typename std::iterator_traits<RandomIt>::difference_type difference_type;
29 difference_type n = last - first;
30 for (difference_type i = n-1; i > 0; --i) {
31 difference_type j = std::rand() % (i + 1);
32 if (j != i) {
33 using std::swap;
34 swap(first[i], first[j]);
35 }
36 }
37 }
38
39 #else
40
41 using std::random_shuffle;
42
43 #endif
44
45 typedef boost::default_constructible_archetype<
46 boost::less_than_comparable_archetype<
47 boost::copy_constructible_archetype<
48 boost::assignable_archetype<
49 > > > > test_value_type;
50
51
52 typedef std::vector<int> test_data;
53 const int test_size = 32;
54
55 struct dummy_run
56 {
rundummy_run57 static void run(void)
58 {}
59 };
60
61
make_test_data(int size,int offset=0,int strive=1)62 test_data make_test_data(int size, int offset = 0, int strive = 1)
63 {
64 test_data ret;
65
66 for (int i = 0; i != size; ++i)
67 ret.push_back(i * strive + offset);
68 return ret;
69 }
70
71
72 template <typename pri_queue, typename data_container>
check_q(pri_queue & q,data_container const & expected)73 void check_q(pri_queue & q, data_container const & expected)
74 {
75 BOOST_REQUIRE_EQUAL(q.size(), expected.size());
76
77 for (unsigned int i = 0; i != expected.size(); ++i)
78 {
79 BOOST_REQUIRE_EQUAL(q.size(), expected.size() - i);
80 BOOST_REQUIRE_EQUAL(q.top(), expected[expected.size()-1-i]);
81 q.pop();
82 }
83
84 BOOST_REQUIRE(q.empty());
85 }
86
87
88 template <typename pri_queue, typename data_container>
fill_q(pri_queue & q,data_container const & data)89 void fill_q(pri_queue & q, data_container const & data)
90 {
91 for (unsigned int i = 0; i != data.size(); ++i)
92 q.push(data[i]);
93 }
94
95 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
96 template <typename pri_queue, typename data_container>
fill_emplace_q(pri_queue & q,data_container const & data)97 void fill_emplace_q(pri_queue & q, data_container const & data)
98 {
99 for (unsigned int i = 0; i != data.size(); ++i) {
100 typename pri_queue::value_type value = data[i];
101 q.emplace(std::move(value));
102 }
103 }
104 #endif
105
106 template <typename pri_queue>
pri_queue_test_sequential_push(void)107 void pri_queue_test_sequential_push(void)
108 {
109 for (int i = 0; i != test_size; ++i)
110 {
111 pri_queue q;
112 test_data data = make_test_data(i);
113 fill_q(q, data);
114 check_q(q, data);
115 }
116 }
117
118 template <typename pri_queue>
pri_queue_test_sequential_reverse_push(void)119 void pri_queue_test_sequential_reverse_push(void)
120 {
121 for (int i = 0; i != test_size; ++i)
122 {
123 pri_queue q;
124 test_data data = make_test_data(i);
125 std::reverse(data.begin(), data.end());
126 fill_q(q, data);
127 std::reverse(data.begin(), data.end());
128 check_q(q, data);
129 }
130 }
131
132 template <typename pri_queue>
pri_queue_test_emplace(void)133 void pri_queue_test_emplace(void)
134 {
135 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
136 for (int i = 0; i != test_size; ++i)
137 {
138 pri_queue q;
139 test_data data = make_test_data(i);
140 std::reverse(data.begin(), data.end());
141 fill_emplace_q(q, data);
142 std::reverse(data.begin(), data.end());
143 check_q(q, data);
144 }
145 #endif
146 }
147
148
149 template <typename pri_queue>
pri_queue_test_random_push(void)150 void pri_queue_test_random_push(void)
151 {
152 for (int i = 0; i != test_size; ++i)
153 {
154 pri_queue q;
155 test_data data = make_test_data(i);
156
157 test_data shuffled (data);
158 random_shuffle(shuffled.begin(), shuffled.end());
159
160 fill_q(q, shuffled);
161
162 check_q(q, data);
163 }
164 }
165
166 template <typename pri_queue>
pri_queue_test_copyconstructor(void)167 void pri_queue_test_copyconstructor(void)
168 {
169 for (int i = 0; i != test_size; ++i)
170 {
171 pri_queue q;
172 test_data data = make_test_data(i);
173 fill_q(q, data);
174
175 pri_queue r(q);
176
177 check_q(r, data);
178 }
179 }
180
181 template <typename pri_queue>
pri_queue_test_assignment(void)182 void pri_queue_test_assignment(void)
183 {
184 for (int i = 0; i != test_size; ++i)
185 {
186 pri_queue q;
187 test_data data = make_test_data(i);
188 fill_q(q, data);
189
190 pri_queue r;
191 r = q;
192
193 check_q(r, data);
194 }
195 }
196
197 template <typename pri_queue>
pri_queue_test_moveconstructor(void)198 void pri_queue_test_moveconstructor(void)
199 {
200 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
201 pri_queue q;
202 test_data data = make_test_data(test_size);
203 fill_q(q, data);
204
205 pri_queue r(std::move(q));
206
207 check_q(r, data);
208 BOOST_REQUIRE(q.empty());
209 #endif
210 }
211
212 template <typename pri_queue>
pri_queue_test_move_assignment(void)213 void pri_queue_test_move_assignment(void)
214 {
215 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
216 pri_queue q;
217 test_data data = make_test_data(test_size);
218 fill_q(q, data);
219
220 pri_queue r;
221 r = std::move(q);
222
223 check_q(r, data);
224 BOOST_REQUIRE(q.empty());
225 #endif
226 }
227
228
229 template <typename pri_queue>
pri_queue_test_swap(void)230 void pri_queue_test_swap(void)
231 {
232 for (int i = 0; i != test_size; ++i)
233 {
234 pri_queue q;
235 test_data data = make_test_data(i);
236 test_data shuffled (data);
237 random_shuffle(shuffled.begin(), shuffled.end());
238 fill_q(q, shuffled);
239
240 pri_queue r;
241
242 q.swap(r);
243 check_q(r, data);
244 BOOST_REQUIRE(q.empty());
245 }
246 }
247
248
249 template <typename pri_queue>
pri_queue_test_iterators(void)250 void pri_queue_test_iterators(void)
251 {
252 for (int i = 0; i != test_size; ++i) {
253 test_data data = make_test_data(test_size);
254 test_data shuffled (data);
255 random_shuffle(shuffled.begin(), shuffled.end());
256 pri_queue q;
257 BOOST_REQUIRE(q.begin() == q.end());
258 fill_q(q, shuffled);
259
260 for (unsigned long j = 0; j != data.size(); ++j)
261 BOOST_REQUIRE(std::find(q.begin(), q.end(), data[j]) != q.end());
262
263 for (unsigned long j = 0; j != data.size(); ++j)
264 BOOST_REQUIRE(std::find(q.begin(), q.end(), data[j] + data.size()) == q.end());
265
266 test_data data_from_queue(q.begin(), q.end());
267 std::sort(data_from_queue.begin(), data_from_queue.end());
268
269 BOOST_REQUIRE(data == data_from_queue);
270
271 for (unsigned long j = 0; j != data.size(); ++j) {
272 BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - j));
273 q.pop();
274 }
275 }
276 }
277
278 template <typename pri_queue>
pri_queue_test_ordered_iterators(void)279 void pri_queue_test_ordered_iterators(void)
280 {
281 for (int i = 0; i != test_size; ++i) {
282 test_data data = make_test_data(i);
283 test_data shuffled (data);
284 random_shuffle(shuffled.begin(), shuffled.end());
285 pri_queue q;
286 BOOST_REQUIRE(q.ordered_begin() == q.ordered_end());
287 fill_q(q, shuffled);
288
289 test_data data_from_queue(q.ordered_begin(), q.ordered_end());
290 std::reverse(data_from_queue.begin(), data_from_queue.end());
291 BOOST_REQUIRE(data == data_from_queue);
292
293 for (unsigned long j = 0; j != data.size(); ++j)
294 BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[j]) != q.ordered_end());
295
296 for (unsigned long j = 0; j != data.size(); ++j)
297 BOOST_REQUIRE(std::find(q.ordered_begin(), q.ordered_end(), data[j] + data.size()) == q.ordered_end());
298
299 for (unsigned long j = 0; j != data.size(); ++j) {
300 BOOST_REQUIRE_EQUAL((long)std::distance(q.begin(), q.end()), (long)(data.size() - j));
301 q.pop();
302 }
303 }
304 }
305
306
307 template <typename pri_queue>
pri_queue_test_equality(void)308 void pri_queue_test_equality(void)
309 {
310 for (int i = 0; i != test_size; ++i)
311 {
312 pri_queue q, r;
313 test_data data = make_test_data(i);
314 fill_q(q, data);
315 std::reverse(data.begin(), data.end());
316 fill_q(r, data);
317
318 BOOST_REQUIRE(r == q);
319 }
320 }
321
322 template <typename pri_queue>
pri_queue_test_inequality(void)323 void pri_queue_test_inequality(void)
324 {
325 for (int i = 1; i != test_size; ++i)
326 {
327 pri_queue q, r;
328 test_data data = make_test_data(i);
329 fill_q(q, data);
330 data[0] = data.back() + 1;
331 fill_q(r, data);
332
333 BOOST_REQUIRE(r != q);
334 }
335 }
336
337 template <typename pri_queue>
pri_queue_test_less(void)338 void pri_queue_test_less(void)
339 {
340 for (int i = 1; i != test_size; ++i)
341 {
342 pri_queue q, r;
343 test_data data = make_test_data(i);
344 test_data r_data(data);
345 r_data.pop_back();
346
347 fill_q(q, data);
348 fill_q(r, r_data);
349
350 BOOST_REQUIRE(r < q);
351 }
352
353 for (int i = 1; i != test_size; ++i)
354 {
355 pri_queue q, r;
356 test_data data = make_test_data(i);
357 test_data r_data(data);
358 data.push_back(data.back() + 1);
359
360 fill_q(q, data);
361 fill_q(r, r_data);
362
363 BOOST_REQUIRE(r < q);
364 }
365
366 for (int i = 1; i != test_size; ++i)
367 {
368 pri_queue q, r;
369 test_data data = make_test_data(i);
370 test_data r_data(data);
371
372 data.back() += 1;
373
374 fill_q(q, data);
375 fill_q(r, r_data);
376
377 BOOST_REQUIRE(r < q);
378 }
379
380 for (int i = 1; i != test_size; ++i)
381 {
382 pri_queue q, r;
383 test_data data = make_test_data(i);
384 test_data r_data(data);
385
386 r_data.front() -= 1;
387
388 fill_q(q, data);
389 fill_q(r, r_data);
390
391 BOOST_REQUIRE(r < q);
392 }
393
394 }
395
396 template <typename pri_queue>
pri_queue_test_clear(void)397 void pri_queue_test_clear(void)
398 {
399 for (int i = 0; i != test_size; ++i)
400 {
401 pri_queue q;
402 test_data data = make_test_data(i);
403 fill_q(q, data);
404
405 q.clear();
406 BOOST_REQUIRE(q.size() == 0);
407 BOOST_REQUIRE(q.empty());
408 }
409 }
410
411
412 template <typename pri_queue>
run_concept_check(void)413 void run_concept_check(void)
414 {
415 BOOST_CONCEPT_ASSERT((boost::heap::PriorityQueue<pri_queue>));
416 }
417
418 template <typename pri_queue>
run_common_heap_tests(void)419 void run_common_heap_tests(void)
420 {
421 pri_queue_test_sequential_push<pri_queue>();
422 pri_queue_test_sequential_reverse_push<pri_queue>();
423 pri_queue_test_random_push<pri_queue>();
424 pri_queue_test_equality<pri_queue>();
425 pri_queue_test_inequality<pri_queue>();
426 pri_queue_test_less<pri_queue>();
427 pri_queue_test_clear<pri_queue>();
428
429 pri_queue_test_emplace<pri_queue>();
430 }
431
432 template <typename pri_queue>
run_iterator_heap_tests(void)433 void run_iterator_heap_tests(void)
434 {
435 pri_queue_test_iterators<pri_queue>();
436 }
437
438
439 template <typename pri_queue>
run_copyable_heap_tests(void)440 void run_copyable_heap_tests(void)
441 {
442 pri_queue_test_copyconstructor <pri_queue>();
443 pri_queue_test_assignment<pri_queue>();
444 pri_queue_test_swap<pri_queue>();
445 }
446
447
448 template <typename pri_queue>
run_moveable_heap_tests(void)449 void run_moveable_heap_tests(void)
450 {
451 pri_queue_test_moveconstructor <pri_queue>();
452 pri_queue_test_move_assignment <pri_queue>();
453 }
454
455
456 template <typename pri_queue>
run_reserve_heap_tests(void)457 void run_reserve_heap_tests(void)
458 {
459 test_data data = make_test_data(test_size);
460 pri_queue q;
461 q.reserve(6);
462 fill_q(q, data);
463
464 check_q(q, data);
465 }
466
467 template <typename pri_queue>
run_leak_check_test(void)468 void run_leak_check_test(void)
469 {
470 pri_queue q;
471 q.push(boost::shared_ptr<int>(new int(0)));
472 }
473
474
475 struct less_with_T
476 {
477 typedef int T;
operator ()less_with_T478 bool operator()(const int& a, const int& b) const
479 {
480 return a < b;
481 }
482 };
483
484
485 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
486
487 class thing {
488 public:
thing(int a_,int b_,int c_)489 thing( int a_, int b_, int c_ ) : a(a_), b(b_), c(c_) {}
490 public:
491 int a;
492 int b;
493 int c;
494 };
495
496 class cmpthings {
497 public:
operator ()(const thing & lhs,const thing & rhs) const498 bool operator() ( const thing& lhs, const thing& rhs ) const {
499 return lhs.a > rhs.a;
500 }
operator ()(const thing & lhs,const thing & rhs)501 bool operator() ( const thing& lhs, const thing& rhs ) {
502 return lhs.a > rhs.a;
503 }
504 };
505
506 #define RUN_EMPLACE_TEST(HEAP_TYPE) \
507 do { \
508 cmpthings ord; \
509 boost::heap::HEAP_TYPE<thing, boost::heap::compare<cmpthings> > vpq(ord); \
510 vpq.emplace(5, 6, 7); \
511 boost::heap::HEAP_TYPE<thing, boost::heap::compare<cmpthings>, boost::heap::stable<true> > vpq2(ord); \
512 vpq2.emplace(5, 6, 7); \
513 } while(0);
514
515 #else
516 #define RUN_EMPLACE_TEST(HEAP_TYPE)
517 #endif
518
519
520 #endif // COMMON_HEAP_TESTS_HPP_INCLUDED
521