]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(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(data.begin(), 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(test_size); | |
52 | PUSH_WITH_HANDLES(handles, q, data); | |
53 | ||
54 | data[i] = -1; | |
55 | q.update(handles[i], -1); | |
56 | ||
57 | std::sort(data.begin(), 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(test_size); | |
68 | PUSH_WITH_HANDLES(handles, q, data); | |
69 | ||
70 | q.update(handles[i], data[i]); | |
71 | ||
72 | std::sort(data.begin(), 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(test_size); | |
82 | PUSH_WITH_HANDLES(handles, q, data); | |
83 | ||
84 | test_data shuffled (data); | |
92f5a8d4 | 85 | random_shuffle(shuffled.begin(), shuffled.end()); |
7c673cae FG |
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(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(data.begin(), 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(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(data.begin(), 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(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(data.begin(), 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(test_size); | |
150 | PUSH_WITH_HANDLES(handles, q, data); | |
151 | ||
152 | data[i] = -1; | |
153 | q.decrease(handles[i], -1); | |
154 | ||
155 | std::sort(data.begin(), 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(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(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(data.begin(), 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(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(data.begin(), 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(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(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(data.begin() + index); | |
248 | } | |
249 | ||
250 | std::sort(data.begin(), 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 | } |