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 | |
29 | template <typename pri_queue> |
30 | void 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 | |
46 | template <typename pri_queue> |
47 | void 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 | |
62 | template <typename pri_queue> |
63 | void 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 | |
77 | template <typename pri_queue> |
78 | void 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 | |
94 | template <typename pri_queue> |
95 | void 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 | |
111 | template <typename pri_queue> |
112 | void 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 | |
127 | template <typename pri_queue> |
128 | void 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 | |
144 | template <typename pri_queue> |
145 | void 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 | |
160 | template <typename pri_queue> |
161 | void 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 | |
175 | template <typename pri_queue> |
176 | void 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 | |
192 | template <typename pri_queue> |
193 | void 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 | |
208 | template <typename pri_queue> |
209 | void 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 | |
222 | template <typename pri_queue> |
223 | void 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 | |
256 | template <typename pri_queue> |
257 | void 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 | |
265 | template <typename pri_queue> |
266 | void 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 | |
274 | template <typename pri_queue> |
275 | void 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 | |
282 | template <typename pri_queue> |
283 | void 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 | |
290 | template <typename pri_queue> |
291 | void run_mutable_heap_erase_tests(void) |
292 | { |
293 | pri_queue_test_erase<pri_queue>(); |
294 | } |
295 | |
296 | template <typename pri_queue> |
297 | void 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 | |
310 | template <typename pri_queue> |
311 | void 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 | |
321 | template <typename pri_queue> |
322 | void run_ordered_iterator_tests() |
323 | { |
324 | pri_queue_test_ordered_iterators<pri_queue>(); |
325 | } |
326 | |