1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 Free Software Foundation, Inc.
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
8// Foundation; either version 3, or (at your option) any later
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
17// along with this library; see the file COPYING3.  If not see
18// <http://www.gnu.org/licenses/>.
19
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/**
33 * @file container_rand_regression_test.h
34 * Contains a random regression test for a specific container type.
35 */
36
37#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
38#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
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>
46#include <testsuite_rng.h>
47#include <regression/trait/assoc/trait.hpp>
48#include <common_type/assoc/string_form.hpp>
49#include <regression/rand/xml_formatter.hpp>
50
51namespace __gnu_pbds
52{
53namespace test
54{
55namespace detail
56{
57  // Rand test specialized for a specific container.
58  template<typename Cntnr>
59  class container_rand_regression_test
60  {
61  public:
62
63    container_rand_regression_test(unsigned long, size_t, size_t, double,
64				   double, double, double, double, bool);
65
66    virtual
67    ~container_rand_regression_test();
68
69    void
70    operator()();
71
72  private:
73    typedef Cntnr 					cntnr;
74    typedef typename cntnr::allocator_type 		allocator_type;
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::key_const_reference	key_const_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;
82    typedef __gnu_pbds::container_traits<Cntnr> 	container_traits;
83    typedef __gnu_cxx::throw_allocator_random<char>    	alloc_t;
84
85    enum op
86      {
87	insert_op,
88	erase_op,
89	clear_op,
90	other_op
91      };
92
93    op
94    get_next_op();
95
96    size_t
97    get_next_sub_op(size_t);
98
99    static void
100    defs();
101
102    static void
103    key_defs();
104
105    static void
106    mapped_defs();
107
108    static void
109    value_defs();
110
111    static void
112    ds_defs();
113
114    static void
115    iterator_defs();
116
117    static void
118    node_iterator_defs(__gnu_pbds::detail::false_type);
119
120    static void
121    node_iterator_defs(__gnu_pbds::detail::true_type);
122
123    static void
124    policy_defs();
125
126    static void
127    policy_defs(__gnu_pbds::basic_hash_tag);
128
129    static void
130    policy_defs(__gnu_pbds::cc_hash_tag);
131
132    static void
133    policy_defs(__gnu_pbds::gp_hash_tag);
134
135    static void
136    policy_defs(__gnu_pbds::tree_tag);
137
138    static void
139    policy_defs(__gnu_pbds::list_update_tag);
140
141    static void
142    policy_defs(__gnu_pbds::pat_trie_tag);
143
144    void
145    policy_access();
146
147    void
148    policy_access(__gnu_pbds::basic_hash_tag);
149
150    void
151    policy_access(__gnu_pbds::cc_hash_tag);
152
153    void
154    policy_access(__gnu_pbds::gp_hash_tag);
155
156    void
157    policy_access(__gnu_pbds::tree_tag);
158
159    void
160    policy_access(__gnu_pbds::list_update_tag);
161
162    void
163    policy_access(__gnu_pbds::pat_trie_tag);
164
165    void
166    it_copy();
167
168    void
169    it_assign();
170
171    void
172    rev_it_copy();
173
174    void
175    rev_it_assign();
176
177    void
178    rev_it_copy_imp(__gnu_pbds::detail::false_type);
179
180    void
181    rev_it_copy_imp(__gnu_pbds::detail::true_type);
182
183    void
184    rev_it_assign_imp(__gnu_pbds::detail::false_type);
185
186    void
187    rev_it_assign_imp(__gnu_pbds::detail::true_type);
188
189    bool
190    default_constructor();
191
192    void
193    swap();
194
195    bool
196    copy_constructor();
197
198    bool
199    assignment_operator();
200
201    bool
202    it_constructor();
203
204    bool
205    it_constructor_imp(__gnu_pbds::cc_hash_tag);
206
207    bool
208    it_constructor_imp(__gnu_pbds::gp_hash_tag);
209
210    bool
211    it_constructor_imp(__gnu_pbds::tree_tag);
212
213    bool
214    it_constructor_imp(__gnu_pbds::list_update_tag);
215
216    bool
217    it_constructor_imp(__gnu_pbds::pat_trie_tag);
218
219    bool
220    insert();
221
222    bool
223    erase();
224
225    bool
226    erase_it();
227
228    bool
229    erase_it_imp(__gnu_pbds::detail::false_type);
230
231    bool
232    erase_it_imp(__gnu_pbds::detail::true_type);
233
234    bool
235    erase_rev_it();
236
237    bool
238    erase_rev_it_imp(__gnu_pbds::detail::false_type);
239
240    bool
241    erase_rev_it_imp(__gnu_pbds::detail::true_type);
242
243    bool
244    erase_if();
245
246    bool
247    clear();
248
249    bool
250    resize();
251
252    bool
253    resize_imp(__gnu_pbds::detail::true_type);
254
255    bool
256    resize_imp(__gnu_pbds::detail::false_type);
257
258    bool
259    get_set_loads();
260
261    bool
262    get_set_loads_imp(__gnu_pbds::detail::true_type);
263
264    bool
265    get_set_loads_imp(__gnu_pbds::detail::false_type);
266
267    void
268    get_set_load();
269
270    void
271    get_set_load_imp(__gnu_pbds::detail::true_type);
272
273    void
274    get_set_load_imp(__gnu_pbds::detail::false_type);
275
276    bool
277    subscript();
278
279    bool
280    subscript_imp(__gnu_pbds::detail::false_type);
281
282    bool
283    subscript_imp(__gnu_pbds::detail::true_type);
284
285    bool
286    split_join();
287
288    bool
289    split_join_imp(__gnu_pbds::detail::false_type);
290
291    bool
292    split_join_imp(__gnu_pbds::detail::true_type);
293
294    void
295    cmp(const Cntnr&, const native_type&, const std::string&);
296
297    void
298    basic_cmp_(const Cntnr&, const native_type&);
299
300    void
301    cmp_(const Cntnr&, const native_type&);
302
303    void
304    order_preserving_cmp_imp(const Cntnr&, const native_type&,
305			     __gnu_pbds::detail::false_type);
306
307    void
308    order_preserving_cmp_imp(const Cntnr&, const native_type&,
309			     __gnu_pbds::detail::true_type);
310
311    void
312    back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
313				  __gnu_pbds::detail::false_type);
314
315    void
316    back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
317				  __gnu_pbds::detail::true_type);
318
319    void
320    reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
321			      __gnu_pbds::detail::false_type);
322
323    void
324    reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
325			      __gnu_pbds::detail::true_type);
326
327    void
328    order_statistics_cmp_imp(const Cntnr&, const native_type&,
329			     __gnu_pbds::detail::false_type);
330
331    void
332    order_statistics_cmp_imp(const Cntnr&, const native_type&,
333			     __gnu_pbds::detail::true_type);
334
335    void
336    prefix_search_cmp_imp(const Cntnr&, const native_type&,
337			  __gnu_pbds::detail::false_type);
338
339    void
340    prefix_search_cmp_imp(const Cntnr&, const native_type&,
341			  __gnu_pbds::detail::true_type);
342
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);
346
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);
350
351    void
352    lower_bound_cmp_imp(const Cntnr&, const native_type&,
353			__gnu_pbds::detail::false_type);
354
355    void
356    lower_bound_cmp_imp(const Cntnr&, const native_type&,
357			__gnu_pbds::detail::true_type);
358
359    void
360    upper_bound_cmp_imp(const Cntnr&, const native_type&,
361			__gnu_pbds::detail::false_type);
362
363    void
364    upper_bound_cmp_imp(const Cntnr&, const native_type&,
365			__gnu_pbds::detail::true_type);
366
367    void
368    print_container(const native_type&, std::ostream& r_os = std::cerr) const;
369
370    void
371    print_container(const cntnr&, std::ostream& r_os = std::cerr) const;
372
373    struct destructor_printer
374    {
375      destructor_printer(const std::string& r_msg)
376      : m_msg(r_msg), m_print(true) { }
377
378      void
379      cancel_print()
380      { m_print = false; }
381
382      ~destructor_printer()
383      {
384	if (!m_print)
385	  return;
386
387	std::cerr << std::endl << "Uncaught exception: " << std::endl
388		  << m_msg << std::endl;
389      }
390
391    private:
392      const std::string m_msg;
393      bool m_print;
394    };
395
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;
410  };
411
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>
460
461#undef PB_DS_COND_COMPARE
462#undef PB_DS_RUN_MTHD
463#undef PB_DS_CLASS_T_DEC
464#undef PB_DS_CLASS_C_DEC
465#undef PB_DS_THROW_IF_FAILED_
466#undef PB_DS_THROW_IF_FAILED
467#undef PB_DS_SET_DESTRUCT_PRINT
468#undef PB_DS_CANCEL_DESTRUCT_PRINT
469#undef PB_DS_TRACE
470
471} // namespace detail
472} // namespace test
473} // namespace __gnu_pbds
474
475#endif
476