]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc. |
4569a895 AT |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License | |
748086b7 JJ |
17 | // along with this library; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. | |
19 | ||
4569a895 AT |
20 | |
21 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
22 | ||
23 | // Permission to use, copy, modify, sell, and distribute this software | |
24 | // is hereby granted without fee, provided that the above copyright | |
25 | // notice appears in all copies, and that both that copyright notice | |
26 | // and this permission notice appear in supporting documentation. None | |
27 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
28 | // representation about the suitability of this software for any | |
29 | // purpose. It is provided "as is" without express or implied | |
30 | // warranty. | |
31 | ||
32 | /** | |
2e3f9c21 | 33 | * @file container_rand_regression_test.h |
4569a895 AT |
34 | * Contains a random regression test for a specific container type. |
35 | */ | |
36 | ||
2e3f9c21 BK |
37 | #ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H |
38 | #define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H | |
4569a895 AT |
39 | |
40 | #include <algorithm> | |
41 | #include <string> | |
42 | #include <sstream> | |
43 | #include <utility> | |
44 | #include <ext/pb_ds/assoc_container.hpp> | |
45 | #include <io/prog_bar.hpp> | |
2e3f9c21 | 46 | #include <testsuite_rng.h> |
4569a895 AT |
47 | #include <regression/trait/assoc/trait.hpp> |
48 | #include <common_type/assoc/string_form.hpp> | |
2e3f9c21 | 49 | #include <regression/rand/xml_formatter.hpp> |
4569a895 | 50 | |
5e11f978 | 51 | namespace __gnu_pbds |
4569a895 | 52 | { |
55a4c999 BK |
53 | namespace test |
54 | { | |
55 | namespace detail | |
56 | { | |
55a4c999 BK |
57 | // Rand test specialized for a specific container. |
58 | template<typename Cntnr> | |
59 | class container_rand_regression_test | |
60 | { | |
61 | public: | |
4569a895 | 62 | |
55a4c999 BK |
63 | container_rand_regression_test(unsigned long, size_t, size_t, double, |
64 | double, double, double, double, bool); | |
4569a895 | 65 | |
55a4c999 BK |
66 | virtual |
67 | ~container_rand_regression_test(); | |
4569a895 | 68 | |
55a4c999 BK |
69 | void |
70 | operator()(); | |
4569a895 | 71 | |
55a4c999 | 72 | private: |
3441f106 | 73 | typedef Cntnr cntnr; |
2e3f9c21 | 74 | typedef typename cntnr::allocator_type allocator_type; |
3441f106 BK |
75 | typedef typename cntnr::size_type size_type; |
76 | typedef regression_test_traits<Cntnr> test_traits; | |
77 | typedef typename test_traits::key_type key_type; | |
78 | typedef typename test_traits::const_key_reference const_key_reference; | |
79 | typedef typename test_traits::value_type value_type; | |
80 | typedef typename test_traits::native_type native_type; | |
81 | typedef twister_rand_gen gen; | |
2e3f9c21 | 82 | typedef __gnu_pbds::container_traits<Cntnr> container_traits; |
861de21e | 83 | typedef __gnu_cxx::throw_allocator_random<char> alloc_t; |
4569a895 | 84 | |
55a4c999 BK |
85 | enum op |
86 | { | |
87 | insert_op, | |
88 | erase_op, | |
89 | clear_op, | |
90 | other_op | |
91 | }; | |
4569a895 | 92 | |
55a4c999 BK |
93 | op |
94 | get_next_op(); | |
4569a895 | 95 | |
55a4c999 BK |
96 | size_t |
97 | get_next_sub_op(size_t); | |
4569a895 | 98 | |
55a4c999 BK |
99 | static void |
100 | defs(); | |
4569a895 | 101 | |
55a4c999 BK |
102 | static void |
103 | key_defs(); | |
4569a895 | 104 | |
55a4c999 BK |
105 | static void |
106 | mapped_defs(); | |
4569a895 | 107 | |
55a4c999 BK |
108 | static void |
109 | value_defs(); | |
4569a895 | 110 | |
55a4c999 BK |
111 | static void |
112 | ds_defs(); | |
4569a895 | 113 | |
55a4c999 BK |
114 | static void |
115 | iterator_defs(); | |
4569a895 | 116 | |
55a4c999 | 117 | static void |
5e11f978 | 118 | node_iterator_defs(__gnu_pbds::detail::false_type); |
4569a895 | 119 | |
55a4c999 | 120 | static void |
5e11f978 | 121 | node_iterator_defs(__gnu_pbds::detail::true_type); |
4569a895 | 122 | |
55a4c999 BK |
123 | static void |
124 | policy_defs(); | |
4569a895 | 125 | |
55a4c999 | 126 | static void |
5e11f978 | 127 | policy_defs(__gnu_pbds::basic_hash_tag); |
4569a895 | 128 | |
55a4c999 | 129 | static void |
5e11f978 | 130 | policy_defs(__gnu_pbds::cc_hash_tag); |
4569a895 | 131 | |
55a4c999 | 132 | static void |
5e11f978 | 133 | policy_defs(__gnu_pbds::gp_hash_tag); |
4569a895 | 134 | |
55a4c999 | 135 | static void |
5e11f978 | 136 | policy_defs(__gnu_pbds::tree_tag); |
4569a895 | 137 | |
55a4c999 | 138 | static void |
5e11f978 | 139 | policy_defs(__gnu_pbds::list_update_tag); |
4569a895 | 140 | |
55a4c999 | 141 | static void |
5e11f978 | 142 | policy_defs(__gnu_pbds::pat_trie_tag); |
4569a895 | 143 | |
55a4c999 BK |
144 | void |
145 | policy_access(); | |
4569a895 | 146 | |
55a4c999 | 147 | void |
5e11f978 | 148 | policy_access(__gnu_pbds::basic_hash_tag); |
4569a895 | 149 | |
55a4c999 | 150 | void |
5e11f978 | 151 | policy_access(__gnu_pbds::cc_hash_tag); |
4569a895 | 152 | |
55a4c999 | 153 | void |
5e11f978 | 154 | policy_access(__gnu_pbds::gp_hash_tag); |
4569a895 | 155 | |
55a4c999 | 156 | void |
5e11f978 | 157 | policy_access(__gnu_pbds::tree_tag); |
4569a895 | 158 | |
55a4c999 | 159 | void |
5e11f978 | 160 | policy_access(__gnu_pbds::list_update_tag); |
4569a895 | 161 | |
55a4c999 | 162 | void |
5e11f978 | 163 | policy_access(__gnu_pbds::pat_trie_tag); |
4569a895 | 164 | |
55a4c999 BK |
165 | void |
166 | it_copy(); | |
4569a895 | 167 | |
55a4c999 BK |
168 | void |
169 | it_assign(); | |
4569a895 | 170 | |
55a4c999 BK |
171 | void |
172 | rev_it_copy(); | |
4569a895 | 173 | |
55a4c999 BK |
174 | void |
175 | rev_it_assign(); | |
4569a895 | 176 | |
55a4c999 | 177 | void |
5e11f978 | 178 | rev_it_copy_imp(__gnu_pbds::detail::false_type); |
4569a895 | 179 | |
55a4c999 | 180 | void |
5e11f978 | 181 | rev_it_copy_imp(__gnu_pbds::detail::true_type); |
4569a895 | 182 | |
55a4c999 | 183 | void |
5e11f978 | 184 | rev_it_assign_imp(__gnu_pbds::detail::false_type); |
4569a895 | 185 | |
55a4c999 | 186 | void |
5e11f978 | 187 | rev_it_assign_imp(__gnu_pbds::detail::true_type); |
4569a895 | 188 | |
55a4c999 BK |
189 | bool |
190 | default_constructor(); | |
4569a895 | 191 | |
55a4c999 BK |
192 | void |
193 | swap(); | |
4569a895 | 194 | |
55a4c999 BK |
195 | bool |
196 | copy_constructor(); | |
4569a895 | 197 | |
55a4c999 BK |
198 | bool |
199 | assignment_operator(); | |
4569a895 | 200 | |
55a4c999 BK |
201 | bool |
202 | it_constructor(); | |
4569a895 | 203 | |
55a4c999 | 204 | bool |
5e11f978 | 205 | it_constructor_imp(__gnu_pbds::cc_hash_tag); |
4569a895 | 206 | |
55a4c999 | 207 | bool |
5e11f978 | 208 | it_constructor_imp(__gnu_pbds::gp_hash_tag); |
4569a895 | 209 | |
55a4c999 | 210 | bool |
5e11f978 | 211 | it_constructor_imp(__gnu_pbds::tree_tag); |
4569a895 | 212 | |
55a4c999 | 213 | bool |
5e11f978 | 214 | it_constructor_imp(__gnu_pbds::list_update_tag); |
4569a895 | 215 | |
55a4c999 | 216 | bool |
5e11f978 | 217 | it_constructor_imp(__gnu_pbds::pat_trie_tag); |
4569a895 | 218 | |
55a4c999 BK |
219 | bool |
220 | insert(); | |
4569a895 | 221 | |
55a4c999 BK |
222 | bool |
223 | erase(); | |
4569a895 | 224 | |
55a4c999 BK |
225 | bool |
226 | erase_it(); | |
4569a895 | 227 | |
55a4c999 | 228 | bool |
5e11f978 | 229 | erase_it_imp(__gnu_pbds::detail::false_type); |
4569a895 | 230 | |
55a4c999 | 231 | bool |
5e11f978 | 232 | erase_it_imp(__gnu_pbds::detail::true_type); |
4569a895 | 233 | |
55a4c999 BK |
234 | bool |
235 | erase_rev_it(); | |
4569a895 | 236 | |
55a4c999 | 237 | bool |
5e11f978 | 238 | erase_rev_it_imp(__gnu_pbds::detail::false_type); |
4569a895 | 239 | |
55a4c999 | 240 | bool |
5e11f978 | 241 | erase_rev_it_imp(__gnu_pbds::detail::true_type); |
4569a895 | 242 | |
55a4c999 BK |
243 | bool |
244 | erase_if(); | |
4569a895 | 245 | |
55a4c999 BK |
246 | bool |
247 | clear(); | |
4569a895 | 248 | |
55a4c999 BK |
249 | bool |
250 | resize(); | |
4569a895 | 251 | |
55a4c999 | 252 | bool |
5e11f978 | 253 | resize_imp(__gnu_pbds::detail::true_type); |
4569a895 | 254 | |
55a4c999 | 255 | bool |
5e11f978 | 256 | resize_imp(__gnu_pbds::detail::false_type); |
4569a895 | 257 | |
55a4c999 BK |
258 | bool |
259 | get_set_loads(); | |
4569a895 | 260 | |
55a4c999 | 261 | bool |
5e11f978 | 262 | get_set_loads_imp(__gnu_pbds::detail::true_type); |
4569a895 | 263 | |
55a4c999 | 264 | bool |
5e11f978 | 265 | get_set_loads_imp(__gnu_pbds::detail::false_type); |
4569a895 | 266 | |
55a4c999 BK |
267 | void |
268 | get_set_load(); | |
4569a895 | 269 | |
55a4c999 | 270 | void |
5e11f978 | 271 | get_set_load_imp(__gnu_pbds::detail::true_type); |
4569a895 | 272 | |
55a4c999 | 273 | void |
5e11f978 | 274 | get_set_load_imp(__gnu_pbds::detail::false_type); |
4569a895 | 275 | |
55a4c999 BK |
276 | bool |
277 | subscript(); | |
4569a895 | 278 | |
55a4c999 | 279 | bool |
5e11f978 | 280 | subscript_imp(__gnu_pbds::detail::false_type); |
4569a895 | 281 | |
55a4c999 | 282 | bool |
5e11f978 | 283 | subscript_imp(__gnu_pbds::detail::true_type); |
4569a895 | 284 | |
55a4c999 BK |
285 | bool |
286 | split_join(); | |
4569a895 | 287 | |
55a4c999 | 288 | bool |
5e11f978 | 289 | split_join_imp(__gnu_pbds::detail::false_type); |
4569a895 | 290 | |
55a4c999 | 291 | bool |
5e11f978 | 292 | split_join_imp(__gnu_pbds::detail::true_type); |
4569a895 | 293 | |
55a4c999 BK |
294 | void |
295 | cmp(const Cntnr&, const native_type&, const std::string&); | |
4569a895 | 296 | |
55a4c999 BK |
297 | void |
298 | basic_cmp_(const Cntnr&, const native_type&); | |
4569a895 | 299 | |
55a4c999 BK |
300 | void |
301 | cmp_(const Cntnr&, const native_type&); | |
4569a895 | 302 | |
55a4c999 BK |
303 | void |
304 | order_preserving_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 305 | __gnu_pbds::detail::false_type); |
4569a895 | 306 | |
55a4c999 BK |
307 | void |
308 | order_preserving_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 309 | __gnu_pbds::detail::true_type); |
4569a895 | 310 | |
55a4c999 BK |
311 | void |
312 | back_order_preserving_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 313 | __gnu_pbds::detail::false_type); |
4569a895 | 314 | |
55a4c999 BK |
315 | void |
316 | back_order_preserving_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 317 | __gnu_pbds::detail::true_type); |
4569a895 | 318 | |
55a4c999 BK |
319 | void |
320 | reverse_iteration_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 321 | __gnu_pbds::detail::false_type); |
4569a895 | 322 | |
55a4c999 BK |
323 | void |
324 | reverse_iteration_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 325 | __gnu_pbds::detail::true_type); |
4569a895 | 326 | |
55a4c999 BK |
327 | void |
328 | order_statistics_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 329 | __gnu_pbds::detail::false_type); |
4569a895 | 330 | |
55a4c999 BK |
331 | void |
332 | order_statistics_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 333 | __gnu_pbds::detail::true_type); |
4569a895 | 334 | |
55a4c999 BK |
335 | void |
336 | prefix_search_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 337 | __gnu_pbds::detail::false_type); |
4569a895 | 338 | |
55a4c999 BK |
339 | void |
340 | prefix_search_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 341 | __gnu_pbds::detail::true_type); |
4569a895 | 342 | |
55a4c999 BK |
343 | template<typename Const_It, class Const_Native_It> |
344 | void | |
345 | it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It); | |
4569a895 | 346 | |
55a4c999 BK |
347 | template<typename Const_It, class Const_Native_It> |
348 | void | |
349 | back_it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It); | |
4569a895 | 350 | |
55a4c999 BK |
351 | void |
352 | lower_bound_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 353 | __gnu_pbds::detail::false_type); |
4569a895 | 354 | |
55a4c999 BK |
355 | void |
356 | lower_bound_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 357 | __gnu_pbds::detail::true_type); |
4569a895 | 358 | |
55a4c999 BK |
359 | void |
360 | upper_bound_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 361 | __gnu_pbds::detail::false_type); |
4569a895 | 362 | |
55a4c999 BK |
363 | void |
364 | upper_bound_cmp_imp(const Cntnr&, const native_type&, | |
5e11f978 | 365 | __gnu_pbds::detail::true_type); |
4569a895 | 366 | |
55a4c999 BK |
367 | void |
368 | print_container(const native_type&, std::ostream& r_os = std::cerr) const; | |
4569a895 | 369 | |
55a4c999 BK |
370 | void |
371 | print_container(const cntnr&, std::ostream& r_os = std::cerr) const; | |
4569a895 | 372 | |
55a4c999 BK |
373 | struct destructor_printer |
374 | { | |
375 | destructor_printer(const std::string& r_msg) | |
376 | : m_msg(r_msg), m_print(true) { } | |
4569a895 | 377 | |
55a4c999 BK |
378 | void |
379 | cancel_print() | |
380 | { m_print = false; } | |
4569a895 | 381 | |
55a4c999 BK |
382 | ~destructor_printer() |
383 | { | |
384 | if (!m_print) | |
385 | return; | |
4569a895 | 386 | |
55a4c999 BK |
387 | std::cerr << std::endl << "Uncaught exception: " << std::endl |
388 | << m_msg << std::endl; | |
389 | } | |
4569a895 | 390 | |
55a4c999 BK |
391 | private: |
392 | const std::string m_msg; | |
393 | bool m_print; | |
394 | }; | |
4569a895 | 395 | |
3441f106 BK |
396 | const unsigned long m_seed; |
397 | const size_t m_n; | |
398 | const size_t m_m; | |
399 | const double m_tp; | |
400 | const double m_ip; | |
401 | const double m_ep; | |
402 | const double m_cp; | |
403 | const double m_mp; | |
404 | const bool m_disp; | |
405 | twister_rand_gen m_g; | |
406 | Cntnr* m_p_c; | |
407 | native_type m_native_c; | |
408 | alloc_t m_alloc; | |
409 | size_t m_i; | |
55a4c999 | 410 | }; |
4569a895 | 411 | |
2e3f9c21 BK |
412 | #ifdef PB_DS_REGRESSION_TRACE |
413 | #define PB_DS_TRACE(X) std::cerr << X << std::endl | |
414 | #else | |
415 | #define PB_DS_TRACE(X) | |
416 | #endif | |
417 | ||
418 | #define PB_DS_CLASS_T_DEC \ | |
419 | template<typename Cntnr> | |
420 | ||
421 | #define PB_DS_CLASS_C_DEC \ | |
422 | container_rand_regression_test<Cntnr> | |
423 | ||
424 | #define PB_DS_COND_COMPARE(L, R) \ | |
425 | if (m_g.get_prob() < m_mp) \ | |
426 | cmp(L, R, __FUNCTION__); | |
427 | ||
428 | #define PB_DS_RUN_MTHD(MTHD) \ | |
429 | { \ | |
430 | bool done = false; \ | |
431 | \ | |
432 | while (!done) \ | |
433 | done = MTHD(); \ | |
434 | } | |
435 | ||
436 | #define PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, F, L) \ | |
437 | if (!(PRED)) \ | |
438 | { \ | |
439 | std::cerr << "Failure at " << F << ": " << L << std::endl; \ | |
440 | std::cerr << MORE << std::endl; \ | |
441 | std::cerr << "container:" << std::endl; \ | |
442 | print_container(*(P_C)); \ | |
443 | std::cerr << std::endl; \ | |
444 | std::cerr << "native container:" << std::endl; \ | |
445 | print_container(*(P_NC)); \ | |
446 | std::cerr << std::endl; \ | |
447 | throw std::logic_error("fucked!"); \ | |
448 | } | |
449 | ||
450 | #define PB_DS_THROW_IF_FAILED(PRED, MORE, P_C, P_NC) \ | |
451 | PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__) | |
452 | ||
453 | #define PB_DS_SET_DESTRUCT_PRINT \ | |
454 | destructor_printer dest_print___(__FUNCTION__); | |
455 | ||
456 | #define PB_DS_CANCEL_DESTRUCT_PRINT \ | |
457 | dest_print___.cancel_print(); | |
458 | ||
459 | #include <regression/rand/assoc/container_rand_regression_test.tcc> | |
4569a895 AT |
460 | |
461 | #undef PB_DS_COND_COMPARE | |
4569a895 | 462 | #undef PB_DS_RUN_MTHD |
4569a895 | 463 | #undef PB_DS_CLASS_T_DEC |
4569a895 | 464 | #undef PB_DS_CLASS_C_DEC |
4569a895 | 465 | #undef PB_DS_THROW_IF_FAILED_ |
4569a895 | 466 | #undef PB_DS_THROW_IF_FAILED |
4569a895 | 467 | #undef PB_DS_SET_DESTRUCT_PRINT |
4569a895 | 468 | #undef PB_DS_CANCEL_DESTRUCT_PRINT |
4569a895 AT |
469 | #undef PB_DS_TRACE |
470 | ||
55a4c999 BK |
471 | } // namespace detail |
472 | } // namespace test | |
5e11f978 | 473 | } // namespace __gnu_pbds |
4569a895 | 474 | |
55a4c999 | 475 | #endif |