• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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>
pri_queue_test_update_decrease(void)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>
pri_queue_test_update_decrease_function(void)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>
pri_queue_test_update_function_identity(void)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>
pri_queue_test_update_shuffled(void)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);
85     random_shuffle(shuffled.begin(), 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>
pri_queue_test_update_increase(void)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>
pri_queue_test_update_increase_function(void)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>
pri_queue_test_decrease(void)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>
pri_queue_test_decrease_function(void)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>
pri_queue_test_decrease_function_identity(void)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>
pri_queue_test_increase(void)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>
pri_queue_test_increase_function(void)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>
pri_queue_test_increase_function_identity(void)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>
pri_queue_test_erase(void)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>
run_mutable_heap_update_tests(void)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>
run_mutable_heap_update_function_tests(void)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>
run_mutable_heap_decrease_tests(void)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>
run_mutable_heap_increase_tests(void)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>
run_mutable_heap_erase_tests(void)291 void run_mutable_heap_erase_tests(void)
292 {
293     pri_queue_test_erase<pri_queue>();
294 }
295 
296 template <typename pri_queue>
run_mutable_heap_test_handle_from_iterator(void)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>
run_mutable_heap_tests(void)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>
run_ordered_iterator_tests()322 void run_ordered_iterator_tests()
323 {
324     pri_queue_test_ordered_iterators<pri_queue>();
325 }
326