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 | #include <boost/foreach.hpp> |
10 | #include "common_heap_tests.hpp" |
11 | |
12 | struct q_tester |
13 | { |
14 | q_tester(int i = 0, int j = 0): |
15 | value(i), id(j) |
16 | {} |
17 | |
18 | bool operator< (q_tester const & rhs) const |
19 | { |
20 | return value < rhs.value; |
21 | } |
22 | |
23 | bool operator> (q_tester const & rhs) const |
24 | { |
25 | return value > rhs.value; |
26 | } |
27 | |
28 | bool operator== (q_tester const & rhs) const |
29 | { |
30 | return (value == rhs.value) && (id == rhs.id); |
31 | } |
32 | |
33 | int value; |
34 | int id; |
35 | }; |
36 | |
37 | std::ostream& operator<< (std::ostream& out, q_tester const & t) |
38 | { |
39 | out << "[" << t.value << " " << t.id << "]" ; |
40 | return out; |
41 | } |
42 | |
43 | typedef std::vector<q_tester> stable_test_data; |
44 | |
45 | stable_test_data make_stable_test_data(int size, int same_count = 3, |
46 | int offset = 0, int strive = 1) |
47 | { |
48 | stable_test_data ret; |
49 | |
50 | for (int i = 0; i != size; ++i) |
51 | for (int j = 0; j != same_count; ++j) |
52 | ret.push_back(x: q_tester(i * strive + offset, j)); |
53 | return ret; |
54 | } |
55 | |
56 | struct compare_by_id |
57 | { |
58 | bool operator()(q_tester const & lhs, q_tester const & rhs) |
59 | { |
60 | return lhs.id > rhs.id; |
61 | } |
62 | }; |
63 | |
64 | template <typename pri_queue> |
65 | void pri_queue_stable_test_sequential_push(void) |
66 | { |
67 | stable_test_data data = make_stable_test_data(size: test_size); |
68 | |
69 | pri_queue q; |
70 | fill_q(q, data); |
71 | std::stable_sort(first: data.begin(), last: data.end(), comp: compare_by_id()); |
72 | std::stable_sort(first: data.begin(), last: data.end(), comp: std::less<q_tester>()); |
73 | check_q(q, data); |
74 | } |
75 | |
76 | template <typename pri_queue> |
77 | void pri_queue_stable_test_sequential_reverse_push(void) |
78 | { |
79 | stable_test_data data = make_stable_test_data(size: test_size); |
80 | pri_queue q; |
81 | stable_test_data push_data(data); |
82 | |
83 | std::stable_sort(first: push_data.begin(), last: push_data.end(), comp: std::greater<q_tester>()); |
84 | |
85 | fill_q(q, push_data); |
86 | |
87 | std::stable_sort(first: data.begin(), last: data.end(), comp: compare_by_id()); |
88 | std::stable_sort(first: data.begin(), last: data.end(), comp: std::less<q_tester>()); |
89 | |
90 | check_q(q, data); |
91 | } |
92 | |
93 | |
94 | template <typename pri_queue> |
95 | void run_stable_heap_tests(void) |
96 | { |
97 | pri_queue_stable_test_sequential_push<pri_queue>(); |
98 | pri_queue_stable_test_sequential_reverse_push<pri_queue>(); |
99 | } |
100 | |