summaryrefslogtreecommitdiff
path: root/libstdc++-v3/testsuite/util/regression
diff options
context:
space:
mode:
Diffstat (limited to 'libstdc++-v3/testsuite/util/regression')
-rw-r--r--libstdc++-v3/testsuite/util/regression/basic_type.hpp94
-rw-r--r--libstdc++-v3/testsuite/util/regression/common_type.hpp194
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h475
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc2133
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp198
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h265
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc838
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp202
-rw-r--r--libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp100
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp90
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp90
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp185
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp124
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp90
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp81
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp206
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp111
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp85
-rw-r--r--libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp82
19 files changed, 5643 insertions, 0 deletions
diff --git a/libstdc++-v3/testsuite/util/regression/basic_type.hpp b/libstdc++-v3/testsuite/util/regression/basic_type.hpp
new file mode 100644
index 000000000..9fe6ef24d
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/basic_type.hpp
@@ -0,0 +1,94 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file basic_type.hpp
+ * Contains a type used for regression tests' key and data.
+ */
+
+#ifndef PB_DS_BASIC_TYPE_HPP
+#define PB_DS_BASIC_TYPE_HPP
+
+#include <string>
+#include <ext/throw_allocator.h>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+#define PB_DS_BASE_C_DEC \
+ std::basic_string<char, std::char_traits<char>, \
+ __gnu_cxx::throw_allocator_random<char> >
+
+ struct basic_type : public PB_DS_BASE_C_DEC
+ {
+ private:
+ typedef PB_DS_BASE_C_DEC base_type;
+
+ public:
+ enum
+ {
+ distinct_chars = 4
+ };
+
+ basic_type() { }
+
+ template<typename Gen>
+ basic_type(Gen& r_gen, size_t max)
+ {
+ size_t rnd = r_gen.get_unsigned_long(0, static_cast<unsigned long>(max));
+ while (rnd > 0)
+ {
+ base_type::push_back('a' + static_cast<char>(rnd % distinct_chars));
+ rnd /= distinct_chars;
+ }
+ }
+
+ basic_type(const std::string other)
+ {
+ std::string::const_iterator it = other.begin();
+ while (it != other.end())
+ {
+ base_type::push_back(*it);
+ ++it;
+ }
+ }
+
+ operator std::string() const
+ { return std::string(base_type::c_str());}
+ };
+
+#undef PB_DS_BASE_C_DEC
+
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/common_type.hpp b/libstdc++-v3/testsuite/util/regression/common_type.hpp
new file mode 100644
index 000000000..37705bc2d
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/common_type.hpp
@@ -0,0 +1,194 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file common_type.hpp
+ * Contains types used for regression tests.
+ */
+
+#ifndef PB_DS_RAND_REGRESSION_TEST_COMMON_TYPE_HPP
+#define PB_DS_RAND_REGRESSION_TEST_COMMON_TYPE_HPP
+
+#include <vector>
+#include <regression/basic_type.hpp>
+#include <common_type/assoc/common_type.hpp>
+#include <common_type/priority_queue/common_type.hpp>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+ typedef __gnu_cxx::throw_allocator_random<basic_type> alloc_type;
+
+ struct hash
+ {
+ typedef alloc_type::rebind<basic_type>::other basic_type_rebind;
+ typedef basic_type_rebind::const_reference const_reference;
+ typedef basic_type::const_iterator const_iterator;
+
+ size_t
+ operator()(const_reference r_key) const
+ {
+ size_t ret = 0;
+ for (const_iterator it = r_key.begin(); it != r_key.end(); ++it)
+ ret = ret * 5 + static_cast<size_t>(*it);
+ return ret;
+ }
+ };
+
+ typedef __gnu_pbds::string_trie_e_access_traits<basic_type, 'a', 'a' + basic_type::distinct_chars - 1, false, alloc_type> e_access_traits_t;
+
+ template<typename Data_Type>
+ struct tree_types
+ {
+ private:
+ typedef typename tree_common_types<basic_type, Data_Type, std::less<basic_type>, __gnu_pbds::null_tree_node_update, alloc_type>::regression_tl no_order_statistics_tl_t;
+
+ typedef typename tree_common_types<basic_type, Data_Type, std::less<basic_type>, __gnu_pbds::tree_order_statistics_node_update, alloc_type>::regression_tl order_statistics_tl_t;
+
+ public:
+ typedef typename __gnu_cxx::typelist::append<no_order_statistics_tl_t, order_statistics_tl_t>::type tl_t;
+
+ typedef no_order_statistics_tl_t min_tl_t;
+ };
+
+ template<typename Data_Type>
+ struct trie_types
+ {
+ private:
+ typedef typename trie_common_types<basic_type, Data_Type, e_access_traits_t, __gnu_pbds::pat_trie_tag, __gnu_pbds::null_trie_node_update, alloc_type>::regression_tl no_updates_tl_t;
+
+ typedef typename trie_common_types<basic_type, Data_Type, e_access_traits_t, __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_order_statistics_node_update, alloc_type>::regression_tl order_statistics_tl_t;
+
+ typedef typename trie_common_types<basic_type, Data_Type, e_access_traits_t, __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_prefix_search_node_update, alloc_type>::regression_tl prefix_search_tl_t;
+
+ public:
+ typedef typename __gnu_cxx::typelist::append<no_updates_tl_t, typename __gnu_cxx::typelist::append<prefix_search_tl_t, order_statistics_tl_t>::type>::type tl_t;
+
+ typedef no_updates_tl_t min_tl_t;
+ };
+
+ template<typename Data_Type>
+ struct hash_types
+ {
+ typedef typename hash_common_types<basic_type, Data_Type, hash, std::equal_to<basic_type>, alloc_type>::regression_tl tl_t;
+
+ typedef tl_t min_tl_t;
+ };
+
+ template<typename Data_Type>
+ struct lu_types
+ {
+ typedef typename lu_common_types<basic_type, Data_Type, std::equal_to<basic_type>, alloc_type>::regression_tl tl_t;
+
+ typedef tl_t min_tl_t;
+ };
+
+ // Sequence types.
+ typedef pq_common_types<basic_type, std::less<basic_type>, alloc_type> pq_types;
+
+ typedef pq_types::regression_tl pq_tl_t;
+ typedef pq_tl_t min_pq_tl_t;
+
+ template<typename _Tp, typename _Alloc>
+ struct vector_adaptor : public std::vector<_Tp, _Alloc>
+ {
+ private:
+ typedef std::vector<_Tp, _Alloc> base_type;
+
+ public:
+ typedef typename base_type::value_type value_type;
+ typedef typename base_type::pointer pointer;
+ typedef typename base_type::const_pointer const_pointer;
+ typedef typename base_type::reference reference;
+ typedef typename base_type::const_reference const_reference;
+ typedef typename base_type::iterator iterator;
+ typedef typename base_type::const_iterator const_iterator;
+ typedef typename base_type::reverse_iterator reverse_iterator;
+ typedef typename base_type::const_reverse_iterator const_reverse_iterator;
+ typedef typename base_type::size_type size_type;
+ typedef typename base_type::difference_type difference_type;
+ typedef typename base_type::allocator_type allocator_type;
+
+ typedef __gnu_pbds::sequence_tag container_category;
+ typedef std::less<_Tp> cmp_fn;
+
+ const cmp_fn&
+ get_cmp_fn() const
+ { return _M_cmp; }
+
+ vector_adaptor() { }
+ vector_adaptor(iterator) { }
+ vector_adaptor(iterator, iterator) { }
+ vector_adaptor(iterator, iterator, const cmp_fn&) { }
+ vector_adaptor(const cmp_fn& other) { }
+
+ using base_type::push_back;
+ using base_type::pop_back;
+
+ // erase_if
+
+ cmp_fn _M_cmp;
+
+ };
+
+ namespace detail
+ {
+
+ };
+
+ typedef vector_adaptor<basic_type, alloc_type> vector_type;
+ typedef __gnu_cxx::typelist::create1<vector_type>::type vector_tl_t;
+
+ // Associative types.
+ typedef tree_types<null_mapped_type>::tl_t tree_set_tl_t;
+ typedef tree_types<null_mapped_type>::min_tl_t min_tree_set_tl_t;
+ typedef tree_types<basic_type>::tl_t tree_map_tl_t;
+ typedef tree_types<basic_type>::min_tl_t min_tree_map_tl_t;
+
+ typedef hash_types<null_mapped_type>::tl_t hash_set_tl_t;
+ typedef hash_types<null_mapped_type>::min_tl_t min_hash_set_tl_t;
+ typedef hash_types<basic_type>::tl_t hash_map_tl_t;
+ typedef hash_types<basic_type>::min_tl_t min_hash_map_tl_t;
+
+ typedef lu_types<null_mapped_type>::tl_t lu_set_tl_t;
+ typedef lu_types<null_mapped_type>::min_tl_t min_lu_set_tl_t;
+ typedef lu_types<basic_type>::tl_t lu_map_tl_t;
+ typedef lu_types<basic_type>::min_tl_t min_lu_map_tl_t;
+
+ typedef trie_types<null_mapped_type>::tl_t trie_set_tl_t;
+ typedef trie_types<null_mapped_type>::min_tl_t min_trie_set_tl_t;
+ typedef trie_types<basic_type>::tl_t trie_map_tl_t;
+ typedef trie_types<basic_type>::min_tl_t min_trie_map_tl_t;
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h
new file mode 100644
index 000000000..ca4433212
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.h
@@ -0,0 +1,475 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file container_rand_regression_test.h
+ * Contains a random regression test for a specific container type.
+ */
+
+#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
+#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
+
+#include <algorithm>
+#include <string>
+#include <sstream>
+#include <utility>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <io/prog_bar.hpp>
+#include <testsuite_rng.h>
+#include <regression/trait/assoc/trait.hpp>
+#include <common_type/assoc/string_form.hpp>
+#include <regression/rand/xml_formatter.hpp>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+ // Rand test specialized for a specific container.
+ template<typename Cntnr>
+ class container_rand_regression_test
+ {
+ public:
+
+ container_rand_regression_test(unsigned long, size_t, size_t, double,
+ double, double, double, double, bool);
+
+ virtual
+ ~container_rand_regression_test();
+
+ void
+ operator()();
+
+ private:
+ typedef Cntnr cntnr;
+ typedef typename cntnr::allocator_type allocator_type;
+ typedef typename cntnr::size_type size_type;
+ typedef regression_test_traits<Cntnr> test_traits;
+ typedef typename test_traits::key_type key_type;
+ typedef typename test_traits::const_key_reference const_key_reference;
+ typedef typename test_traits::value_type value_type;
+ typedef typename test_traits::native_type native_type;
+ typedef twister_rand_gen gen;
+ typedef __gnu_pbds::container_traits<Cntnr> container_traits;
+ typedef __gnu_cxx::throw_allocator_random<char> alloc_t;
+
+ enum op
+ {
+ insert_op,
+ erase_op,
+ clear_op,
+ other_op
+ };
+
+ op
+ get_next_op();
+
+ size_t
+ get_next_sub_op(size_t);
+
+ static void
+ defs();
+
+ static void
+ key_defs();
+
+ static void
+ mapped_defs();
+
+ static void
+ value_defs();
+
+ static void
+ ds_defs();
+
+ static void
+ iterator_defs();
+
+ static void
+ node_iterator_defs(__gnu_pbds::detail::false_type);
+
+ static void
+ node_iterator_defs(__gnu_pbds::detail::true_type);
+
+ static void
+ policy_defs();
+
+ static void
+ policy_defs(__gnu_pbds::basic_hash_tag);
+
+ static void
+ policy_defs(__gnu_pbds::cc_hash_tag);
+
+ static void
+ policy_defs(__gnu_pbds::gp_hash_tag);
+
+ static void
+ policy_defs(__gnu_pbds::tree_tag);
+
+ static void
+ policy_defs(__gnu_pbds::list_update_tag);
+
+ static void
+ policy_defs(__gnu_pbds::pat_trie_tag);
+
+ void
+ policy_access();
+
+ void
+ policy_access(__gnu_pbds::basic_hash_tag);
+
+ void
+ policy_access(__gnu_pbds::cc_hash_tag);
+
+ void
+ policy_access(__gnu_pbds::gp_hash_tag);
+
+ void
+ policy_access(__gnu_pbds::tree_tag);
+
+ void
+ policy_access(__gnu_pbds::list_update_tag);
+
+ void
+ policy_access(__gnu_pbds::pat_trie_tag);
+
+ void
+ it_copy();
+
+ void
+ it_assign();
+
+ void
+ rev_it_copy();
+
+ void
+ rev_it_assign();
+
+ void
+ rev_it_copy_imp(__gnu_pbds::detail::false_type);
+
+ void
+ rev_it_copy_imp(__gnu_pbds::detail::true_type);
+
+ void
+ rev_it_assign_imp(__gnu_pbds::detail::false_type);
+
+ void
+ rev_it_assign_imp(__gnu_pbds::detail::true_type);
+
+ bool
+ default_constructor();
+
+ void
+ swap();
+
+ bool
+ copy_constructor();
+
+ bool
+ assignment_operator();
+
+ bool
+ it_constructor();
+
+ bool
+ it_constructor_imp(__gnu_pbds::cc_hash_tag);
+
+ bool
+ it_constructor_imp(__gnu_pbds::gp_hash_tag);
+
+ bool
+ it_constructor_imp(__gnu_pbds::tree_tag);
+
+ bool
+ it_constructor_imp(__gnu_pbds::list_update_tag);
+
+ bool
+ it_constructor_imp(__gnu_pbds::pat_trie_tag);
+
+ bool
+ insert();
+
+ bool
+ erase();
+
+ bool
+ erase_it();
+
+ bool
+ erase_it_imp(__gnu_pbds::detail::false_type);
+
+ bool
+ erase_it_imp(__gnu_pbds::detail::true_type);
+
+ bool
+ erase_rev_it();
+
+ bool
+ erase_rev_it_imp(__gnu_pbds::detail::false_type);
+
+ bool
+ erase_rev_it_imp(__gnu_pbds::detail::true_type);
+
+ bool
+ erase_if();
+
+ bool
+ clear();
+
+ bool
+ resize();
+
+ bool
+ resize_imp(__gnu_pbds::detail::true_type);
+
+ bool
+ resize_imp(__gnu_pbds::detail::false_type);
+
+ bool
+ get_set_loads();
+
+ bool
+ get_set_loads_imp(__gnu_pbds::detail::true_type);
+
+ bool
+ get_set_loads_imp(__gnu_pbds::detail::false_type);
+
+ void
+ get_set_load();
+
+ void
+ get_set_load_imp(__gnu_pbds::detail::true_type);
+
+ void
+ get_set_load_imp(__gnu_pbds::detail::false_type);
+
+ bool
+ subscript();
+
+ bool
+ subscript_imp(__gnu_pbds::detail::false_type);
+
+ bool
+ subscript_imp(__gnu_pbds::detail::true_type);
+
+ bool
+ split_join();
+
+ bool
+ split_join_imp(__gnu_pbds::detail::false_type);
+
+ bool
+ split_join_imp(__gnu_pbds::detail::true_type);
+
+ void
+ cmp(const Cntnr&, const native_type&, const std::string&);
+
+ void
+ basic_cmp_(const Cntnr&, const native_type&);
+
+ void
+ cmp_(const Cntnr&, const native_type&);
+
+ void
+ order_preserving_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ order_preserving_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ void
+ back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ void
+ reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ void
+ order_statistics_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ order_statistics_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ void
+ prefix_search_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ prefix_search_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ template<typename Const_It, class Const_Native_It>
+ void
+ it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It);
+
+ template<typename Const_It, class Const_Native_It>
+ void
+ back_it_cmp_imp(Const_It, Const_It, Const_Native_It, Const_Native_It);
+
+ void
+ lower_bound_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ lower_bound_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ void
+ upper_bound_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type);
+
+ void
+ upper_bound_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::true_type);
+
+ void
+ print_container(const native_type&, std::ostream& r_os = std::cerr) const;
+
+ void
+ print_container(const cntnr&, std::ostream& r_os = std::cerr) const;
+
+ struct destructor_printer
+ {
+ destructor_printer(const std::string& r_msg)
+ : m_msg(r_msg), m_print(true) { }
+
+ void
+ cancel_print()
+ { m_print = false; }
+
+ ~destructor_printer()
+ {
+ if (!m_print)
+ return;
+
+ std::cerr << std::endl << "Uncaught exception: " << std::endl
+ << m_msg << std::endl;
+ }
+
+ private:
+ const std::string m_msg;
+ bool m_print;
+ };
+
+ const unsigned long m_seed;
+ const size_t m_n;
+ const size_t m_m;
+ const double m_tp;
+ const double m_ip;
+ const double m_ep;
+ const double m_cp;
+ const double m_mp;
+ const bool m_disp;
+ twister_rand_gen m_g;
+ Cntnr* m_p_c;
+ native_type m_native_c;
+ alloc_t m_alloc;
+ size_t m_i;
+ };
+
+#ifdef PB_DS_REGRESSION_TRACE
+#define PB_DS_TRACE(X) std::cerr << X << std::endl
+#else
+#define PB_DS_TRACE(X)
+#endif
+
+#define PB_DS_CLASS_T_DEC \
+ template<typename Cntnr>
+
+#define PB_DS_CLASS_C_DEC \
+ container_rand_regression_test<Cntnr>
+
+#define PB_DS_COND_COMPARE(L, R) \
+ if (m_g.get_prob() < m_mp) \
+ cmp(L, R, __FUNCTION__);
+
+#define PB_DS_RUN_MTHD(MTHD) \
+ { \
+ bool done = false; \
+ \
+ while (!done) \
+ done = MTHD(); \
+ }
+
+#define PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, F, L) \
+ if (!(PRED)) \
+ { \
+ std::cerr << "Failure at " << F << ": " << L << std::endl; \
+ std::cerr << MORE << std::endl; \
+ std::cerr << "container:" << std::endl; \
+ print_container(*(P_C)); \
+ std::cerr << std::endl; \
+ std::cerr << "native container:" << std::endl; \
+ print_container(*(P_NC)); \
+ std::cerr << std::endl; \
+ throw std::logic_error("fucked!"); \
+ }
+
+#define PB_DS_THROW_IF_FAILED(PRED, MORE, P_C, P_NC) \
+ PB_DS_THROW_IF_FAILED_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__)
+
+#define PB_DS_SET_DESTRUCT_PRINT \
+ destructor_printer dest_print___(__FUNCTION__);
+
+#define PB_DS_CANCEL_DESTRUCT_PRINT \
+ dest_print___.cancel_print();
+
+#include <regression/rand/assoc/container_rand_regression_test.tcc>
+
+#undef PB_DS_COND_COMPARE
+#undef PB_DS_RUN_MTHD
+#undef PB_DS_CLASS_T_DEC
+#undef PB_DS_CLASS_C_DEC
+#undef PB_DS_THROW_IF_FAILED_
+#undef PB_DS_THROW_IF_FAILED
+#undef PB_DS_SET_DESTRUCT_PRINT
+#undef PB_DS_CANCEL_DESTRUCT_PRINT
+#undef PB_DS_TRACE
+
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc
new file mode 100644
index 000000000..0f1586648
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc
@@ -0,0 +1,2133 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file container_rand_regression_test.tcc
+ * Contains a random regression test for a specific container type.
+ */
+
+#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
+#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
+
+// Constructors/Destructors.
+PB_DS_CLASS_T_DEC
+PB_DS_CLASS_C_DEC::
+container_rand_regression_test(unsigned long seed, size_t n, size_t m,
+ double tp, double ip, double ep, double cp,
+ double mp, bool disp)
+: m_seed((seed == 0) ? twister_rand_gen::get_time_determined_seed() : seed),
+ m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_ep(ep), m_cp(cp), m_mp(mp),
+ m_disp(disp), m_p_c(0)
+{ }
+
+PB_DS_CLASS_T_DEC
+PB_DS_CLASS_C_DEC::
+~container_rand_regression_test()
+{ }
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+default_constructor()
+{
+ PB_DS_TRACE("default_constructor");
+ bool done = true;
+ m_alloc.set_probability(m_tp);
+
+ try
+ {
+ m_p_c = new Cntnr;
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ if (m_p_c)
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+swap()
+{
+ PB_DS_TRACE("swap");
+ m_alloc.set_probability(0);
+ Cntnr* p_c = new Cntnr;
+ m_alloc.set_probability(1);
+ p_c->swap(*m_p_c);
+ std::swap(p_c, m_p_c);
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+copy_constructor()
+{
+ PB_DS_TRACE("copy_constructor");
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ p_c = new Cntnr(*m_p_c);
+ std::swap(p_c, m_p_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+assignment_operator()
+{
+ PB_DS_TRACE("assignment operator");
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ p_c = new Cntnr();
+ * p_c =* m_p_c;
+ std::swap(p_c, m_p_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor()
+{
+ PB_DS_TRACE("it_constructor");
+ return it_constructor_imp(typename Cntnr::container_category());
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor_imp(__gnu_pbds::cc_hash_tag)
+{
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ switch(get_next_sub_op(8))
+ {
+ case 0:
+ p_c = new Cntnr(m_p_c->get_hash_fn());
+ m_native_c.clear();
+ break;
+ case 1:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
+ m_native_c.clear();
+ break;
+ case 2:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_hash_fn());
+ m_native_c.clear();
+ break;
+ case 3:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_hash_fn(),
+ m_p_c->get_resize_policy());
+ m_native_c.clear();
+ break;
+ case 4:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
+ break;
+ case 5:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
+ break;
+ case 6:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn());
+ break;
+ case 7:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn());
+ break;
+ case 8:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn(),
+ m_p_c->get_resize_policy());
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ };
+ std::swap(p_c, m_p_c);
+ }
+ catch (__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor_imp(__gnu_pbds::gp_hash_tag)
+{
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ switch(get_next_sub_op(11))
+ {
+ case 0:
+ p_c = new Cntnr(m_p_c->get_hash_fn());
+ m_native_c.clear();
+ break;
+ case 1:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
+ m_native_c.clear();
+ break;
+ case 2:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_probe_fn());
+ m_native_c.clear();
+ break;
+ case 3:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_probe_fn());
+ m_native_c.clear();
+ break;
+ case 4:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn());
+ m_native_c.clear();
+ break;
+ case 5:
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn(),
+ m_p_c->get_resize_policy());
+ m_native_c.clear();
+ break;
+ case 6:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
+ break;
+ case 7:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn());
+ break;
+ case 8:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
+ break;
+ case 9:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
+ break;
+ case 10:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
+ m_p_c->get_probe_fn());
+ break;
+ case 11:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
+ m_p_c->get_probe_fn(), m_p_c->get_resize_policy());
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ };
+ std::swap(p_c, m_p_c);
+ }
+ catch (__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor_imp(__gnu_pbds::tree_tag)
+{
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ switch(get_next_sub_op(2))
+ {
+ case 0:
+ p_c = new Cntnr(m_p_c->get_cmp_fn());
+ m_native_c.clear();
+ break;
+ case 1:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn());
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ };
+ std::swap(p_c, m_p_c);
+ }
+ catch (__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor_imp(__gnu_pbds::list_update_tag)
+{
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
+ std::swap(p_c, m_p_c);
+ }
+ catch (__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor_imp(__gnu_pbds::pat_trie_tag)
+{
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ try
+ {
+ switch(get_next_sub_op(2))
+ {
+ case 0:
+ p_c = new Cntnr(m_p_c->get_e_access_traits());
+ m_native_c.clear();
+ break;
+ case 1:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(),
+ m_p_c->get_e_access_traits());
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ };
+
+ std::swap(p_c, m_p_c);
+ }
+ catch (__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+// Cmp.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+cmp(const Cntnr& r_c, const native_type& r_native_c,
+ const std::string& r_call_fn)
+{
+ m_alloc.set_probability(1);
+ const size_t size = r_c.size();
+ const size_t native_size = r_native_c.size();
+ PB_DS_THROW_IF_FAILED(size == native_size,
+ size << " " << native_size, &r_c, &r_native_c);
+
+ const bool empty = r_c.empty();
+ const bool native_empty = r_native_c.empty();
+ PB_DS_THROW_IF_FAILED(empty == native_empty,
+ empty << " " << native_empty, &r_c, &r_native_c);
+
+ try
+ {
+ basic_cmp_(r_c, r_native_c);
+ cmp_(r_c, r_native_c);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(false, "call-fn: " + r_call_fn, &r_c, &r_native_c);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+basic_cmp_(const Cntnr& r_c, const native_type& r_native_c)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+
+ if (static_cast<size_t>(std::distance(r_c.begin(), r_c.end())) != r_c.size())
+ PB_DS_THROW_IF_FAILED(false,
+ static_cast<unsigned long>(std::distance(r_c.begin(), r_c.end())) << " " << static_cast<unsigned long>(r_c.size()), &r_c, &r_native_c);
+
+ typename native_type::const_iterator it = r_native_c.begin();
+ while (it != r_native_c.end())
+ {
+ typename native_type::key_type native_key = test_traits::extract_native_key(*it);
+
+ m_alloc.set_probability(0);
+ const key_type k = native_key;
+ m_alloc.set_probability(1);
+ typename cntnr::const_point_iterator found_it = r_c.find(k);
+ PB_DS_THROW_IF_FAILED(found_it != r_c.end(),
+ test_traits::native_val_to_string(*it),
+ &r_c, &r_native_c);
+
+ if (!test_traits::cmp(*found_it, * it))
+ PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c);
+
+ ++it;
+ }
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+cmp_(const Cntnr& r_c, const native_type& r_native_c)
+{
+ enum
+ {
+ order_preserving = container_traits::order_preserving,
+ back_order_preserving = container_traits::order_preserving
+ &&
+ !__gnu_pbds::detail::is_same<
+ typename std::iterator_traits<
+ typename cntnr::const_iterator>::iterator_category,
+ std::forward_iterator_tag>::value,
+ reverse_iteration = container_traits::reverse_iteration,
+ order_statistics = test_traits::order_statistics,
+ prefix_search = test_traits::prefix_search,
+ has_mapped = !__gnu_pbds::detail::is_same<
+ typename Cntnr::mapped_type,
+ __gnu_pbds::null_mapped_type>::value
+ };
+
+ order_preserving_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,order_preserving>());
+
+ back_order_preserving_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,back_order_preserving>());
+
+ order_statistics_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,order_statistics>());
+
+ prefix_search_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,prefix_search>());
+
+ reverse_iteration_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,reverse_iteration>());
+
+ lower_bound_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,order_preserving>());
+
+ upper_bound_cmp_imp(r_c, r_native_c,
+ __gnu_pbds::detail::integral_constant<int,order_preserving>());
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+order_preserving_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+
+ typename cntnr::const_iterator b = r_c.begin();
+ typename cntnr::const_iterator e = r_c.end();
+
+ typename native_type::const_iterator native_b = r_native_c.begin();
+ typename native_type::const_iterator native_e = r_native_c.end();
+
+ try
+ {
+ it_cmp_imp(b, e, native_b, native_e);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
+ }
+
+ try
+ {
+ back_it_cmp_imp(b, e, native_b, native_e);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
+ }
+
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+back_order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c,
+ __gnu_pbds::detail::true_type)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+ typename cntnr::const_iterator b = r_c.begin();
+ typename cntnr::const_iterator e = r_c.end();
+ typename native_type::const_iterator native_b = r_native_c.begin();
+ typename native_type::const_iterator native_e = r_native_c.end();
+ it_cmp_imp(b, e, native_b, native_e);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
+ __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+reverse_iteration_cmp_imp(const Cntnr& r_c, const native_type&r_native_c, __gnu_pbds::detail::true_type)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+
+ typename cntnr::const_reverse_iterator b = r_c.rbegin();
+ typename cntnr::const_reverse_iterator e = r_c.rend();
+
+ typename native_type::const_reverse_iterator native_b = r_native_c.rbegin();
+ typename native_type::const_reverse_iterator native_e = r_native_c.rend();
+
+ try
+ {
+ it_cmp_imp(b, e, native_b, native_e);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
+ }
+
+ try
+ {
+ back_it_cmp_imp(b, e, native_b, native_e);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
+ }
+
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+order_statistics_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+order_statistics_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
+{
+ {
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(1);
+ const size_type order = r_c.order_of_key(k);
+ const size_type native_order = std::distance(r_native_c.begin(),
+ r_native_c.lower_bound(test_traits::native_key(k)));
+
+ PB_DS_THROW_IF_FAILED(order == native_order,
+ test_traits::key_to_string(k) << " " <<
+ static_cast<unsigned long>(order) << " " <<
+ static_cast<unsigned long>(native_order),
+ &r_c,
+ &r_native_c);
+ }
+
+ const size_type rand_ord =
+ static_cast<size_t>(m_g.get_unsigned_long(0,
+ 2 * static_cast<unsigned long>(m_m)));
+
+ typename cntnr::const_iterator it = r_c.find_by_order(rand_ord);
+ typename native_type::const_iterator native_it = r_native_c.begin();
+ std::advance(native_it, std::min(rand_ord, r_native_c.size()));
+ if (it == r_c.end()&& native_it != r_native_c.end())
+ PB_DS_THROW_IF_FAILED(false,
+ static_cast<unsigned long>(rand_ord),
+ m_p_c,
+ &m_native_c);
+
+ if (it != r_c.end()&& native_it == r_native_c.end())
+ PB_DS_THROW_IF_FAILED(false,
+ static_cast<unsigned long>(rand_ord),
+ m_p_c,
+ &m_native_c);
+
+ if (it != r_c.end()&& native_it != r_native_c.end())
+ PB_DS_THROW_IF_FAILED(test_traits::cmp(*it, * native_it),
+ static_cast<unsigned long>(rand_ord),
+ m_p_c,
+ &m_native_c);
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+prefix_search_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+prefix_search_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(1);
+ try
+ {
+ typedef
+ std::pair<typename Cntnr::const_iterator, typename Cntnr::const_iterator>
+ pref_ret_t;
+
+ const pref_ret_t pref_ret = r_c.prefix_range(k);
+
+ typename native_type::const_iterator native_start_it = r_native_c.begin();
+
+ while (native_start_it != r_native_c.end() &&
+ !test_traits::prefix_match(k,
+ test_traits::extract_native_key(*native_start_it)))
+ ++native_start_it;
+
+ typename native_type::const_iterator native_end_it =
+ native_start_it;
+
+ do
+ {
+ if (native_end_it != r_native_c.end())
+ ++native_end_it;
+ }
+ while (native_end_it != r_native_c.end() &&
+ test_traits::prefix_match(k,
+ test_traits::extract_native_key(*native_end_it)));
+
+ it_cmp_imp(pref_ret.first, pref_ret.second, native_start_it, native_end_it);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(false, "prefix key " << k, &r_c, &r_native_c);
+ }
+
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+template<typename Const_It, class Const_Native_It>
+void
+PB_DS_CLASS_C_DEC::
+it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b,
+ Const_Native_It native_e)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+
+ if (std::distance(b, e) != std::distance(native_b, native_e))
+ {
+ const size_t dist = std::distance(b, e);
+ const size_t native_dist = std::distance(native_b, native_e);
+ PB_DS_THROW_IF_FAILED(false,
+ static_cast<unsigned long>(dist) << " "
+ << static_cast<unsigned long>(native_dist),
+ m_p_c, &m_native_c);
+ }
+
+ while (b != e)
+ {
+ PB_DS_THROW_IF_FAILED(native_b != native_e, "", m_p_c, &m_native_c);
+
+ if (!test_traits::cmp(*b, * native_b))
+ PB_DS_THROW_IF_FAILED(false,
+ test_traits::val_to_string(*b) << " " <<
+ test_traits::val_to_string(*native_b),
+ m_p_c, &m_native_c);
+
+ ++b;
+ ++native_b;
+ }
+
+ PB_DS_THROW_IF_FAILED(native_b == native_e, "", m_p_c, &m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+template<typename Const_It, class Const_Native_It>
+void
+PB_DS_CLASS_C_DEC::
+back_it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b,
+ Const_Native_It native_e)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+ while (b != e)
+ {
+ PB_DS_THROW_IF_FAILED(native_b != native_e,
+ test_traits::val_to_string(*native_e),
+ m_p_c, &m_native_c);
+
+ --e;
+ --native_e;
+
+ PB_DS_THROW_IF_FAILED(test_traits::cmp(*e, * native_e),
+ test_traits::val_to_string(*e) <<
+ test_traits::val_to_string(*native_e),
+ m_p_c, &m_native_c);
+ }
+
+ PB_DS_THROW_IF_FAILED(native_b == native_e,
+ test_traits::val_to_string(*native_e),
+ m_p_c, &m_native_c);
+
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+lower_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+lower_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(1);
+ typename cntnr::const_iterator it = r_c.lower_bound(k);
+ typename native_type::key_type native_k = test_traits::native_key(k);
+ typename native_type::const_iterator native_it = r_native_c.lower_bound(native_k);
+
+ if (it != r_c.end() && native_it == r_native_c.end())
+ PB_DS_THROW_IF_FAILED("",
+ "it: " + test_traits::val_to_string(*it) + "\n\n",
+ &r_c, &r_native_c);
+
+ if (it == r_c.end() && native_it != r_native_c.end())
+ PB_DS_THROW_IF_FAILED("",
+ "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
+ &r_c, &r_native_c);
+
+ if (it != r_c.end() && !test_traits::cmp(*it, * native_it))
+ PB_DS_THROW_IF_FAILED(false,
+ "key: " + test_traits::key_to_string(k) + "\n\n" +
+ "it: " + test_traits::val_to_string(*it) + "\n\n" +
+ "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
+ &r_c, &r_native_c);
+
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+upper_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+upper_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
+{
+ PB_DS_SET_DESTRUCT_PRINT
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(1);
+ typename cntnr::const_iterator it = r_c.upper_bound(k);
+ typename native_type::key_type native_k = test_traits::native_key(k);
+ typename native_type::const_iterator native_it = r_native_c.upper_bound(native_k);
+
+ if (it == r_c.end() && native_it != r_native_c.end())
+ PB_DS_THROW_IF_FAILED(false,
+ "key: " + test_traits::key_to_string(k) + "\n\n" +
+ "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
+ &r_c, &r_native_c);
+
+ if (it != r_c.end() && native_it == r_native_c.end())
+ PB_DS_THROW_IF_FAILED(false,
+ "key: " + test_traits::key_to_string(k) + "\n\n" +
+ "it: " + test_traits::val_to_string(*it) + "\n\n",
+ &r_c, &r_native_c);
+
+ if (it != r_c.end() && !test_traits::cmp(*it, * native_it))
+ PB_DS_THROW_IF_FAILED(false,
+ "key: " + test_traits::key_to_string(k) + "\n\n" +
+ "it: " + test_traits::val_to_string(*it) + "\n\n" +
+ "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
+ &r_c, &r_native_c);
+
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+// Operators.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+operator()()
+{
+ typedef xml_result_set_regression_formatter formatter_type;
+ formatter_type* p_fmt = 0;
+
+ if (m_disp)
+ p_fmt = new formatter_type(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
+
+ m_g.init(m_seed);
+
+ // Track allocation from this point only.
+ const size_t memory_label = 775;
+ m_alloc.seed(m_seed);
+ m_alloc.set_label(memory_label);
+
+ prog_bar pb(m_n, std::cout, m_disp);
+ m_i = 0;
+
+ try
+ {
+ for (m_i = 0; m_i < m_n; ++m_i)
+ {
+ PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i));
+ allocator_type::set_label(m_i);
+ switch (m_i)
+ {
+ case 0:
+ PB_DS_RUN_MTHD(default_constructor);
+ break;
+ case 1:
+ defs();
+ break;
+ case 2:
+ policy_access();
+ break;
+ case 3:
+ it_copy();
+ break;
+ case 4:
+ it_assign();
+ break;
+ case 5:
+ rev_it_copy();
+ break;
+ case 6:
+ rev_it_assign();
+ break;
+ default:
+ switch(get_next_op())
+ {
+ case insert_op:
+ switch(get_next_sub_op(2))
+ {
+ case 0:
+ PB_DS_RUN_MTHD(insert)
+ break;
+ case 1:
+ PB_DS_RUN_MTHD(subscript)
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ }
+ break;
+ case erase_op:
+ switch(get_next_sub_op(4))
+ {
+ case 0:
+ PB_DS_RUN_MTHD(erase)
+ break;
+ case 1:
+ PB_DS_RUN_MTHD(erase_if)
+ break;
+ case 2:
+ PB_DS_RUN_MTHD(erase_it)
+ break;
+ case 3:
+ PB_DS_RUN_MTHD(erase_rev_it)
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ }
+ break;
+ case clear_op:
+ PB_DS_RUN_MTHD(clear)
+ break;
+ case other_op:
+ switch(get_next_sub_op(8))
+ {
+ case 0:
+ swap();
+ break;
+ case 1:
+ PB_DS_RUN_MTHD(copy_constructor)
+ break;
+ case 2:
+ PB_DS_RUN_MTHD(it_constructor)
+ break;
+ case 3:
+ PB_DS_RUN_MTHD(assignment_operator)
+ break;
+ case 4:
+ PB_DS_RUN_MTHD(split_join)
+ break;
+ case 5:
+ resize();
+ break;
+ case 6:
+ get_set_load();
+ break;
+ case 7:
+ get_set_loads();
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ }
+ break;
+ default:
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ };
+ }
+
+ pb.inc();
+ }
+ }
+ catch (...)
+ {
+ std::cerr << "Failed at index " << static_cast<unsigned long>(m_i)
+ << std::endl;
+ delete m_p_c;
+ throw;
+ }
+
+ // Clean up, then check for allocation by special label, set above.
+ delete m_p_c;
+
+ try
+ { m_alloc.check_allocated(memory_label); }
+ catch (...)
+ {
+ std::cerr << "detected leaks!" << std::endl;
+ std::cerr << m_alloc << std::endl;
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ }
+
+ // Reset throw probability.
+ m_alloc.set_probability(0);
+
+ if (m_disp)
+ {
+ std::cout << std::endl;
+ delete p_fmt;
+ }
+}
+
+PB_DS_CLASS_T_DEC
+typename PB_DS_CLASS_C_DEC::op
+PB_DS_CLASS_C_DEC::
+get_next_op()
+{
+ const double prob = m_g.get_prob();
+ if (prob < m_ip)
+ return insert_op;
+
+ if (prob < m_ip + m_ep)
+ return erase_op;
+
+ if (prob < m_ip + m_ep + m_cp)
+ return clear_op;
+
+ PB_DS_THROW_IF_FAILED(prob <= 1, prob, m_p_c, &m_native_c);
+ return other_op;
+}
+
+PB_DS_CLASS_T_DEC
+size_t
+PB_DS_CLASS_C_DEC::
+get_next_sub_op(size_t max)
+{
+ const double p = m_g.get_prob();
+ const double delta = 1 / static_cast<double>(max);
+ size_t i = 0;
+ while (true)
+ if (p <= (i + 1) * delta)
+ {
+ PB_DS_THROW_IF_FAILED(i < max, i << " " << max, m_p_c, &m_native_c);
+ return i;
+ }
+ else
+ ++i;
+}
+
+// Insert.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+insert()
+{
+ PB_DS_TRACE("insert");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+ try
+ {
+ m_alloc.set_probability(0);
+ value_type v = test_traits::generate_value(m_g, m_m);
+ m_alloc.set_probability(m_tp);
+ const_key_reference r_k = test_traits::extract_key(v);
+ typename cntnr::const_point_iterator found_it = m_p_c->find(r_k);
+ const bool existed = (found_it != m_p_c->end());
+ const std::pair<typename cntnr::point_iterator, bool> ins_ret = m_p_c->insert(v);
+
+ if (ins_ret.second)
+ {
+ PB_DS_THROW_IF_FAILED(!existed, "", m_p_c, &m_native_c);
+ }
+ else
+ {
+ PB_DS_THROW_IF_FAILED(existed, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(found_it == ins_ret.first, "", m_p_c, &m_native_c);
+ }
+ m_native_c.insert(test_traits::native_value(v));
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+ catch(__gnu_pbds::insert_error&)
+ {
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+// Subscript.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+subscript()
+{
+ PB_DS_TRACE("subscript");
+
+ enum
+ {
+ no_data = __gnu_pbds::detail::is_same<
+ typename Cntnr::const_key_reference,
+ typename Cntnr::const_reference>::value
+ };
+
+ return (subscript_imp(__gnu_pbds::detail::integral_constant<int,no_data>()));
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+subscript_imp(__gnu_pbds::detail::false_type)
+{
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+
+ try
+ {
+ m_alloc.set_probability(0);
+ value_type v = test_traits::generate_value(m_g, m_m);
+
+ m_alloc.set_probability(m_tp);
+ (*m_p_c)[v.first] = v.second;
+
+ m_native_c[test_traits::native_value(v).first] =
+ test_traits::native_value(v).second;
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+subscript_imp(__gnu_pbds::detail::true_type)
+{
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+ try
+ {
+ m_alloc.set_probability(0);
+ value_type v = test_traits::generate_value(m_g, m_m);
+ m_alloc.set_probability(m_tp);
+ (*m_p_c)[v] = __gnu_pbds::null_mapped_type();
+ m_native_c.insert(test_traits::native_value(v));
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+// Clear.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+clear()
+{
+ m_p_c->clear();
+ m_native_c.clear();
+ return true;
+}
+
+
+// Erase.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase()
+{
+ PB_DS_TRACE("erase");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(m_tp);
+
+ try
+ {
+ const bool cntnd = m_p_c->find(k) != m_p_c->end();
+ PB_DS_THROW_IF_FAILED(cntnd ==(m_native_c.find(test_traits::native_key(k)) != m_native_c.end()), test_traits::key_to_string(k), m_p_c, &m_native_c);
+
+ const bool ersd = m_p_c->erase(k);
+ const bool native_ersd = m_native_c.erase(test_traits::native_key(k)) != 0;
+
+ PB_DS_THROW_IF_FAILED(ersd == native_ersd, ersd << " " << native_ersd,
+ m_p_c, &m_native_c);
+
+ PB_DS_THROW_IF_FAILED(m_p_c->find(k) == m_p_c->end(), "",
+ m_p_c, &m_native_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+
+ PB_DS_THROW_IF_FAILED( container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_if()
+{
+ PB_DS_TRACE("erase_if");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+
+ try
+ {
+ typedef
+ typename std::iterator_traits<typename cntnr::iterator>::reference
+ it_const_reference;
+
+ typedef
+ typename test_traits::template erase_if_fn<value_type>
+ erase_if_fn_t;
+
+ m_alloc.set_probability(m_tp);
+
+ const size_t ersd = m_p_c->erase_if(erase_if_fn_t());
+ const size_t native_ersd = test_traits::erase_if(m_native_c);
+ PB_DS_THROW_IF_FAILED(ersd == native_ersd,
+ ersd << " " << native_ersd, m_p_c, &m_native_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw,
+ container_traits::erase_can_throw,
+ m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_it()
+{
+ enum
+ {
+ erase_iterators = container_traits::order_preserving
+ };
+
+ return (erase_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>()));
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_it_imp(__gnu_pbds::detail::false_type)
+{
+ return true;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_it_imp(__gnu_pbds::detail::true_type)
+{
+ PB_DS_TRACE("erase_it");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+
+ try
+ {
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(m_tp);
+
+ typename cntnr::iterator found_it = m_p_c->find(k);
+
+ typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k));
+
+ const bool found = found_it != m_p_c->end();
+ const bool native_found = native_it != m_native_c.end();
+
+ PB_DS_THROW_IF_FAILED(
+ found == native_found,
+ found << " " << native_found,
+ m_p_c,
+ &m_native_c);
+
+ typename cntnr::const_iterator next_it = found_it;
+ if (next_it != m_p_c->end())
+ ++next_it;
+
+ typename cntnr::iterator next_ers_it = m_p_c->erase(found_it);
+
+ if (native_it != m_native_c.end())
+ m_native_c.erase(native_it);
+
+ bool range_guarantee = __gnu_pbds::detail::is_same<
+ typename container_traits::invalidation_guarantee,
+ __gnu_pbds::range_invalidation_guarantee>::value ;
+
+ if (range_guarantee)
+ PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_rev_it()
+{
+ enum
+ {
+ erase_iterators = container_traits::order_preserving
+ && container_traits::reverse_iteration
+ };
+
+ return (erase_rev_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>()));
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_rev_it_imp(__gnu_pbds::detail::false_type)
+{
+ return true;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_rev_it_imp(__gnu_pbds::detail::true_type)
+{
+ PB_DS_TRACE("erase_rev_it");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+
+ try
+ {
+ m_alloc.set_probability(0);
+ const key_type k = test_traits::generate_key(m_g, m_m);
+ m_alloc.set_probability(m_tp);
+
+ typename cntnr::iterator found_it = m_p_c->find(k);
+ typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k));
+
+ typename cntnr::const_reverse_iterator next_it = found_it;
+ if (next_it != m_p_c->end())
+ ++next_it;
+
+ typename cntnr::reverse_iterator next_ers_it =
+ m_p_c->erase((typename cntnr::reverse_iterator)found_it);
+
+ PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c);
+
+ if (native_it != m_native_c.end())
+ m_native_c.erase(native_it);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw,
+ container_traits::erase_can_throw,
+ m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+// Defs.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+defs()
+{
+ // General container types.
+ typedef typename Cntnr::size_type test_size_type;
+ typedef typename Cntnr::difference_type difference_type;
+
+ key_defs();
+ mapped_defs();
+ value_defs();
+ iterator_defs();
+ node_iterator_defs(__gnu_pbds::detail::integral_constant<int,
+ container_traits::order_preserving>());
+ policy_defs();
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+key_defs()
+{
+ typedef typename Cntnr::key_type test_key_type;
+ typedef typename Cntnr::key_reference test_key_reference;
+ typedef typename Cntnr::const_key_reference test_const_key_reference;
+ typedef typename Cntnr::key_pointer test_key_pointer;
+ typedef typename Cntnr::const_key_pointer test_const_key_pointer;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+mapped_defs()
+{
+ typedef typename Cntnr::mapped_type test_mapped_type;
+ typedef typename Cntnr::mapped_reference test_mapped_reference;
+ typedef typename Cntnr::const_mapped_reference test_const_mapped_reference;
+ typedef typename Cntnr::mapped_pointer test_mapped_pointer;
+ typedef typename Cntnr::const_mapped_pointer test_const_mapped_pointer;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+value_defs()
+{
+ typedef typename Cntnr::value_type test_value_type;
+ typedef typename Cntnr::reference test_reference;
+ typedef typename Cntnr::const_reference test_const_reference;
+ typedef typename Cntnr::pointer test_pointer;
+ typedef typename Cntnr::const_pointer test_const_pointer;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+ds_defs()
+{
+ typedef __gnu_pbds::container_traits< Cntnr> test_container_traits;
+
+ typedef typename test_container_traits::container_category test_container_category;
+
+ typedef
+ typename test_container_traits::invalidation_guarantee
+ test_invalidation_guarantee;
+
+ enum
+ {
+ test_order_preserving = test_container_traits::order_preserving
+ };
+
+ enum
+ {
+ test_erase_can_throw = test_container_traits::erase_can_throw
+ };
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+iterator_defs()
+{
+ typedef typename Cntnr::point_iterator test_point_iterator;
+ typedef typename Cntnr::const_point_iterator const_test_point_iterator;
+ typedef typename Cntnr::iterator test_iterator;
+ typedef typename Cntnr::const_iterator const_test_iterator;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+node_iterator_defs(__gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+node_iterator_defs(__gnu_pbds::detail::true_type)
+{
+ typedef typename Cntnr::node_iterator test_node_iterator;
+ typedef typename Cntnr::const_node_iterator test_const_node_iterator;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs()
+{
+ typedef typename Cntnr::allocator_type test_allocator;
+ policy_defs(typename Cntnr::container_category());
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs(__gnu_pbds::basic_hash_tag)
+{
+ typedef typename Cntnr::hash_fn test_hash_fn;
+ typedef typename Cntnr::eq_fn test_eq_fn;
+ typedef typename Cntnr::resize_policy test_resize_policy;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs(__gnu_pbds::cc_hash_tag)
+{
+ policy_defs(__gnu_pbds::basic_hash_tag());
+ typedef typename Cntnr::comb_hash_fn test_comb_hash_fn;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs(__gnu_pbds::gp_hash_tag)
+{
+ policy_defs(__gnu_pbds::basic_hash_tag());
+ typedef typename Cntnr::comb_probe_fn test_comb_probe_fn;
+ typedef typename Cntnr::probe_fn test_probe_fn;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs(__gnu_pbds::tree_tag)
+{
+ typedef typename Cntnr::cmp_fn test_cmp_fn;
+ typedef typename Cntnr::node_update test_node_update;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs(__gnu_pbds::list_update_tag)
+{
+ typedef typename Cntnr::eq_fn test_eq_fn;
+ typedef typename Cntnr::update_policy test_update_policy;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs(__gnu_pbds::pat_trie_tag)
+{
+ typedef typename Cntnr::e_access_traits e_access_traits;
+}
+
+
+// Policy Access.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access()
+{
+ policy_access(typename Cntnr::container_category());
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access(__gnu_pbds::basic_hash_tag)
+{
+ {
+ typename Cntnr::hash_fn& r_t = m_p_c->get_hash_fn();
+ assert(&r_t);
+ }
+ {
+ const typename Cntnr::hash_fn& r_t =((const Cntnr& )*m_p_c).get_hash_fn();
+ assert(&r_t);
+ }
+
+ {
+ typename Cntnr::eq_fn& r_t = m_p_c->get_eq_fn();
+ assert(&r_t);
+ }
+ {
+ const typename Cntnr::eq_fn& r_t =((const Cntnr& )*m_p_c).get_eq_fn();
+ assert(&r_t);
+ }
+
+ {
+ typename Cntnr::resize_policy& r_t = m_p_c->get_resize_policy();
+ assert(&r_t);
+ }
+ {
+ const typename Cntnr::resize_policy& r_t =((const Cntnr& )*m_p_c).get_resize_policy();
+
+ assert(&r_t);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access(__gnu_pbds::cc_hash_tag)
+{
+ policy_access(__gnu_pbds::basic_hash_tag());
+
+ {
+ typename Cntnr::comb_hash_fn& r_t = m_p_c->get_comb_hash_fn();
+ assert(&r_t);
+ }
+ {
+ const typename Cntnr::comb_hash_fn& r_t =((const Cntnr& )*m_p_c).get_comb_hash_fn();
+
+ assert(&r_t);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access(__gnu_pbds::gp_hash_tag)
+{
+ policy_access(__gnu_pbds::basic_hash_tag());
+
+ {
+ typename Cntnr::comb_probe_fn& r_t = m_p_c->get_comb_probe_fn();
+ assert(&r_t);
+ }
+ {
+ const typename Cntnr::comb_probe_fn& r_t =((const Cntnr& )*m_p_c).get_comb_probe_fn();
+
+ assert(&r_t);
+ }
+
+ {
+ typename Cntnr::probe_fn& r_t = m_p_c->get_probe_fn();
+ assert(&r_t);
+ }
+ {
+ const typename Cntnr::probe_fn& r_t =((const Cntnr& )*m_p_c).get_probe_fn();
+ assert(&r_t);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access(__gnu_pbds::tree_tag)
+{
+ {
+ typename Cntnr::cmp_fn& r_t = m_p_c->get_cmp_fn();
+ assert(&r_t);
+ }
+
+ {
+ const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn();
+ assert(&r_t);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access(__gnu_pbds::list_update_tag)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access(__gnu_pbds::pat_trie_tag)
+{
+ typename Cntnr::e_access_traits& r_t = m_p_c->get_e_access_traits();
+ assert(&r_t);
+}
+
+
+// Split/Join.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+split_join()
+{
+ enum
+ {
+ split_join = container_traits::order_preserving
+ };
+
+ return (split_join_imp(__gnu_pbds::detail::integral_constant<int,split_join>()));
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+split_join_imp(__gnu_pbds::detail::false_type)
+{
+ return true;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+split_join_imp(__gnu_pbds::detail::true_type)
+{
+ PB_DS_TRACE("split_join");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+
+ try
+ {
+ m_alloc.set_probability(0);
+ Cntnr lhs(*m_p_c);
+ Cntnr rhs;
+ native_type native_lhs(m_native_c);
+ native_type native_rhs;
+ const key_type k = test_traits::generate_key(m_g, m_m);
+
+ m_alloc.set_probability(m_tp);
+ lhs.split(k, rhs);
+
+ typename native_type::const_iterator it =
+ native_lhs.upper_bound(test_traits::native_key(k));
+
+ while (!native_lhs.empty()&& it != native_lhs.end())
+ {
+ native_rhs.insert(*it);
+ typename native_type::const_iterator next_it = it;
+ ++next_it;
+ native_lhs.erase(test_traits::extract_native_key(*it));
+ it = next_it;
+ }
+
+ PB_DS_COND_COMPARE(lhs, native_lhs);
+ PB_DS_COND_COMPARE(rhs, native_rhs);
+
+ m_alloc.set_probability(m_tp);
+
+ if (m_g.get_prob() < 0.5)
+ lhs.swap(rhs);
+
+ lhs.join(rhs);
+ PB_DS_THROW_IF_FAILED(rhs.size() == 0, rhs.size(), m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(rhs.empty(), rhs.size(), m_p_c, &m_native_c);
+ m_p_c->swap(lhs);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ PB_DS_THROW_IF_FAILED(container_traits::split_join_can_throw,
+ container_traits::split_join_can_throw,
+ m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+// Iterator conversions.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+it_copy()
+{
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_iterator const_it(it);
+ PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::const_point_iterator const_find_it(it);
+ PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it(it);
+ PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::const_iterator const_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it(const_it);
+ PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::point_iterator find_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it(find_it);
+ PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+it_assign()
+{
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_iterator const_it;
+ const_it = it;
+ PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = it;
+ PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it;
+ find_it = it;
+ PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::const_iterator const_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = const_it;
+ PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::point_iterator find_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = find_it;
+ PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+rev_it_copy()
+{
+ enum
+ {
+ reverse_iteration = container_traits::reverse_iteration
+ };
+
+ rev_it_copy_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+rev_it_assign()
+{
+ enum
+ {
+ reverse_iteration = container_traits::reverse_iteration
+ };
+
+ rev_it_assign_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+rev_it_copy_imp(__gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+rev_it_copy_imp(__gnu_pbds::detail::true_type)
+{
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_reverse_iterator const_it(it);
+ PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::const_point_iterator const_find_it(it);
+ PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it(it);
+ PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+rev_it_assign_imp(__gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+rev_it_assign_imp(__gnu_pbds::detail::true_type)
+{
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_reverse_iterator const_it;
+ const_it = it;
+ PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = it;
+ PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it;
+ find_it = it;
+ PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
+ }
+}
+
+// Resize.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+resize()
+{
+ typedef __gnu_pbds::detail::integral_constant<int, test_traits::resize> resize_ind;
+
+ return resize_imp(resize_ind());
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+resize_imp(__gnu_pbds::detail::false_type)
+{
+ return true;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+resize_imp(__gnu_pbds::detail::true_type)
+{
+ PB_DS_TRACE("resize");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+ const size_t old_size = m_p_c->get_actual_size();
+
+ try
+ {
+ enum
+ {
+ min_new_size = 200,
+ max_new_size = 2000
+ };
+
+ m_alloc.set_probability(m_tp);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+ const size_t new_size = m_g.get_unsigned_long(min_new_size, max_new_size);
+ m_p_c->resize(new_size);
+ const size_t actual_new_size = m_p_c->get_actual_size();
+ PB_DS_THROW_IF_FAILED(actual_new_size >= new_size,
+ actual_new_size << " " << new_size,
+ m_p_c, &m_native_c);
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(m_p_c->get_actual_size() == old_size,
+ m_p_c->get_actual_size() << " " << old_size,
+ m_p_c, &m_native_c);
+
+ done = false;
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+
+// Get/Set load.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+get_set_load()
+{
+ typedef
+ __gnu_pbds::detail::integral_constant<int, test_traits::get_set_load>
+ get_set_load_ind;
+
+ get_set_load_imp(get_set_load_ind());
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+get_set_load_imp(__gnu_pbds::detail::false_type)
+{ }
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+get_set_load_imp(__gnu_pbds::detail::true_type)
+{
+ PB_DS_TRACE("get_set_load");
+ PB_DS_SET_DESTRUCT_PRINT
+ m_p_c->get_load();
+ m_alloc.set_probability(1);
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+ const float min_load = static_cast<float>(0.05);
+ const float max_load = static_cast<float>(0.9);
+
+ const float new_load = static_cast<float>(m_g.get_prob() * (max_load - min_load) + min_load);
+
+ m_p_c->set_load(new_load);
+ PB_DS_THROW_IF_FAILED(m_p_c->get_load() == new_load, "", m_p_c, &m_native_c);
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+}
+
+
+// Get/Set loads.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+get_set_loads()
+{
+ typedef
+ __gnu_pbds::detail::integral_constant<int, test_traits::get_set_loads>
+ get_set_loads_ind;
+
+ return get_set_loads_imp(get_set_loads_ind());
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+get_set_loads_imp(__gnu_pbds::detail::false_type)
+{
+ return true;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+get_set_loads_imp(__gnu_pbds::detail::true_type)
+{
+ PB_DS_TRACE("get_set_loads");
+ bool done = true;
+ PB_DS_SET_DESTRUCT_PRINT
+ const std::pair<float, float> old_loads = m_p_c->get_loads();
+
+ try
+ {
+ m_alloc.set_probability(m_tp);
+
+ typename alloc_t::group_adjustor adjust(m_p_c->size());
+
+ const float min_min_load = static_cast<float>(0.05);
+ const float max_min_load = static_cast<float>(0.2);
+
+ const float new_min_load =
+ static_cast<float>(m_g.get_prob()* (max_min_load - min_min_load) +
+ min_min_load);
+
+ const float new_max_load = static_cast<float>(new_min_load* 2.5);
+ PB_DS_THROW_IF_FAILED(new_max_load < 1, new_max_load, m_p_c, &m_native_c);
+ m_p_c->set_loads(std::make_pair(new_min_load, new_max_load));
+ }
+ catch(...)
+ {
+ PB_DS_THROW_IF_FAILED(old_loads == m_p_c->get_loads(),
+ old_loads.first << " " << old_loads.second << " " <<
+ m_p_c->get_loads().first << " " <<
+ m_p_c->get_loads().second,
+ m_p_c, &m_native_c);
+
+ done = false;
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ PB_DS_CANCEL_DESTRUCT_PRINT
+ return done;
+}
+
+// Diagnostics.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+print_container(const native_type& r_cnt, std::ostream& r_os) const
+{
+ m_alloc.set_probability(0);
+ typename native_type::const_iterator it = r_cnt.begin();
+ while (it != r_cnt.end())
+ {
+ r_os << test_traits::val_to_string(*it) + "\n";
+ ++it;
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+print_container(const cntnr& r_cnt, std::ostream& r_os) const
+{
+ m_alloc.set_probability(0);
+ typename cntnr::const_iterator it = r_cnt.begin();
+ while (it != r_cnt.end())
+ {
+ r_os << test_traits::val_to_string(*it) + "\n";
+ ++it;
+ }
+}
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp
new file mode 100644
index 000000000..5f2304952
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/rand_regression_test.hpp
@@ -0,0 +1,198 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file rand_regression_test.hpp
+ * Contains a random-operation test.
+ */
+
+#ifndef PB_DS_ASSOC_RAND_REGRESSION_TEST_HPP
+#define PB_DS_ASSOC_RAND_REGRESSION_TEST_HPP
+
+#include <iostream>
+#include <vector>
+#include <regression/rand/assoc/container_rand_regression_test.h>
+#include <io/verified_cmd_line_input.hpp>
+#include <common_type/assoc/common_type.hpp>
+#include <regression/basic_type.hpp>
+#include <regression/common_type.hpp>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+#ifndef PB_DS_REGRESSION
+#error "Must define PB_DS_REGRESSION"
+#endif
+
+ struct rand_reg_test
+ {
+ public:
+ rand_reg_test(size_t seed, size_t n, size_t m, double tp, double ip,
+ double ep, double cp, double mp, bool d)
+ : m_sd(seed), m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_ep(ep), m_cp(cp),
+ m_mp(mp), m_disp(d)
+ { }
+
+ template<typename Cntnr>
+ void
+ operator()(Cntnr)
+ {
+ unsigned long ul = static_cast<unsigned long>(m_sd);
+ container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip,
+ m_ep, m_cp, m_mp, m_disp);
+ t();
+ }
+
+ private:
+ const size_t m_sd;
+ const size_t m_n;
+ const size_t m_m;
+ const double m_tp;
+ const double m_ip;
+ const double m_ep;
+ const double m_cp;
+ const double m_mp;
+ const bool m_disp;
+ };
+
+ void
+ usage(const std::string& r_name);
+
+ void
+ verify_params(size_t&, size_t&, size_t&,
+ double&, double&, double&, double&, double&, bool&);
+} // namespace detail
+
+ template<typename TL>
+ int
+ rand_regression_test(size_t iter, size_t keys, const std::string name, TL tl)
+ {
+ // Sane defaults.
+ size_t n = iter;
+ size_t m = keys;
+ size_t sd = twister_rand_gen::get_time_determined_seed();
+ double tp = 0.2;
+ double ip = 0.6;
+ double ep = 0.2;
+ double cp = 0.001;
+ double mp = 0.25;
+ bool disp = false; // show progress
+
+ try
+ {
+ detail::verify_params(sd, n, m, tp, ip, ep, cp, mp, disp);
+ }
+ catch (__gnu_pbds::test::illegal_input_error&)
+ {
+ detail::usage(name);
+ return -1;
+ }
+ catch (...)
+ {
+ return -2;
+ };
+
+ // XXX RAII, constructor takes bool for display
+ xml_test_rand_regression_formatter* p_fmt = 0;
+ if (disp)
+ p_fmt = new xml_test_rand_regression_formatter(sd, n, m, tp, ip, ep, cp, mp);
+
+ try
+ {
+ detail::rand_reg_test tst(sd, n, m, tp, ip, ep, cp, mp, disp);
+ __gnu_cxx::typelist::apply(tst, tl);
+ }
+ catch (...)
+ {
+ std::cerr << "Test failed with seed " << sd << std::endl;
+ if (disp)
+ delete p_fmt;
+ throw;
+ }
+
+ if (disp)
+ delete p_fmt;
+ return 0;
+ }
+
+namespace detail
+{
+ inline void
+ usage(const std::string& name)
+ {
+ using namespace std;
+ cerr << "usage: " << name << " <sd> <n> <m> <tp> <ip> <ep> <cp> <mp> ['t' | 'f']" <<
+ endl << endl;
+
+ cerr << "This test performs basic regression tests on various associative containers."
+ "For each container, it performs a sequence of operations. At each iteration, it does "
+ "the following: " << endl;
+ cerr << "* Performs an operation on the container " << endl;
+ cerr << "* Performs the same operation on an cntnr object" << endl;
+ cerr << "* Possibly compares the container to the cntnr object" << endl;
+ cerr << "* Checks that exceptions (thrown by an allocator) "
+ "do not violate exception guarantees";
+
+ cerr << endl << endl;
+
+ cerr << "sd = seed for random-number generator; "
+ "0 = time determined value" << endl;
+ cerr << "n = number of iterations" << endl;
+ cerr << "m = number of distinct values" << endl;
+ cerr << "tp = probability that an exception will be actively thrown" << endl;
+ cerr << "ip = probability that an operation will be insert" << endl;
+ cerr << "ep = probability that an operation will be erase" << endl;
+ cerr << "cp = probability that an operation will be clear" << endl;
+ cerr << "(therefore, 1 - (ip + ep + cp) = probability of any other operation)" << endl;
+ cerr << "mp = probability that the container will be compared to the cntnr object" << endl;
+ cerr << "'t' or 'f' determine whether progress will be displayed" << endl;
+ }
+
+ inline void
+ verify_params(size_t& r_seed, size_t& r_n,
+ size_t& r_m, double& r_tp, double& r_ip, double& r_ep,
+ double& r_cp, double& r_mp, bool& r_d)
+ {
+ verify_prob(r_tp);
+ verify_prob(r_ip);
+ verify_prob(r_ep);
+ verify_prob(r_cp);
+ verify_prob(r_mp);
+ verify_prob(r_ip + r_ep + r_cp);
+ }
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h
new file mode 100644
index 000000000..828541ce7
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.h
@@ -0,0 +1,265 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file container_rand_regression_test.h
+ * Contains a random regression test for a specific container type.
+ */
+
+#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
+#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_H
+
+#include <algorithm>
+#include <string>
+#include <sstream>
+#include <utility>
+#include <cassert>
+#include <regression/basic_type.hpp>
+#include <ext/pb_ds/priority_queue.hpp>
+#include <io/prog_bar.hpp>
+#include <testsuite_rng.h>
+#include <common_type/priority_queue/string_form.hpp>
+#include <regression/rand/xml_formatter.hpp>
+#include <regression/trait/priority_queue/trait.hpp>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+ // Rand test specialized for a specific container.
+ template<typename Cntnr>
+ class container_rand_regression_test
+ {
+ private:
+ typedef Cntnr cntnr;
+ typedef typename cntnr::allocator_type allocator_type;
+ typedef typename cntnr::size_type size_type;
+ typedef twister_rand_gen gen;
+ typedef basic_type value_type;
+ typedef native_priority_queue<std::string, true> native_type;
+ typedef regression_test_traits<cntnr> test_traits;
+
+ enum op
+ {
+ insert_op,
+ modify_op,
+ erase_op,
+ clear_op,
+ other_op
+ };
+
+ op
+ get_next_op();
+
+ size_t
+ get_next_sub_op(size_t max);
+
+ static void
+ defs();
+
+ static void
+ value_defs();
+
+ static void
+ ds_defs();
+
+ static void
+ iterator_defs();
+
+ static void
+ policy_defs();
+
+ void
+ policy_access();
+
+ void
+ it_copy();
+
+ void
+ it_assign();
+
+ bool
+ default_constructor();
+
+ void
+ swap();
+
+ bool
+ copy_constructor();
+
+ bool
+ assignment_operator();
+
+ bool
+ it_constructor();
+
+ bool
+ push();
+
+ bool
+ modify();
+
+ bool
+ pop();
+
+ bool
+ erase_if();
+
+ bool
+ erase_it();
+
+ bool
+ clear();
+
+ bool
+ split_join();
+
+ void
+ cmp(const Cntnr& r_container, const native_type& r_native_c,
+ const std::string& r_call_fn);
+
+ void
+ print_container(const native_type& r_cnt,
+ std::ostream& r_os = std::cerr) const;
+
+ void
+ print_container(const cntnr& r_cnt,
+ std::ostream& r_os = std::cerr) const;
+
+ struct destructor_printer
+ {
+ destructor_printer(const std::string& r_msg)
+ : m_msg(r_msg), m_print(true) { }
+
+ void
+ cancel()
+ { m_print = false; }
+
+ ~destructor_printer()
+ {
+ if (m_print)
+ {
+ std::cerr << std::endl << "Uncaught exception: " << std::endl
+ << m_msg << std::endl;
+ }
+ }
+
+ const std::string m_msg;
+ bool m_print;
+ };
+
+ const unsigned long m_seed;
+ const size_t m_n;
+ const size_t m_m;
+ const double m_tp;
+ const double m_ip;
+ const double m_dp;
+ const double m_ep;
+ const double m_cp;
+ const double m_mp;
+ const bool m_disp;
+ twister_rand_gen m_g;
+ Cntnr* m_p_c;
+ native_type m_native_c;
+ allocator_type m_alloc;
+ size_t m_i;
+
+ public:
+ container_rand_regression_test(unsigned long seed, size_t n, size_t m,
+ double tp, double ip, double dp,
+ double ep, double cp, double mp,
+ bool disp);
+
+ virtual
+ ~container_rand_regression_test();
+
+ void
+ operator()();
+ };
+
+
+#ifdef PB_DS_REGRESSION_TRACE
+# define PB_DS_TRACE(X) std::cerr << X << std::endl
+#else
+# define PB_DS_TRACE(X)
+#endif
+
+#define PB_DS_CLASS_T_DEC \
+ template<typename Cntnr>
+
+#define PB_DS_CLASS_C_DEC \
+ container_rand_regression_test<Cntnr>
+
+#define PB_DS_COND_COMPARE(L, R) \
+ if (m_g.get_prob() < m_mp) \
+ cmp(L, R, __FUNCTION__);
+
+#define PB_DS_RUN_MTHD(MTHD) \
+ { \
+ bool done = false; \
+ while (!done) \
+ done = MTHD(); \
+ }
+
+#define _GLIBCXX_THROW_IF_(PRED, MORE, P_C, P_NC, F, L) \
+ if (PRED) \
+ { \
+ std::cerr << "Failure at " << F << ": " << L << std::endl; \
+ std::cerr << MORE << std::endl; \
+ std::cerr << "container:" << std::endl; \
+ print_container(*(P_C)); \
+ std::cerr << std::endl; \
+ std::cerr << "native container:" << std::endl; \
+ print_container(*(P_NC)); \
+ std::cerr << std::endl; \
+ throw std::logic_error("pbds throw if failed"); \
+ }
+
+#define _GLIBCXX_THROW_IF(PRED, MORE, P_C, P_NC) \
+ _GLIBCXX_THROW_IF_(PRED, MORE, P_C, P_NC, __FILE__, __LINE__)
+
+#include <regression/rand/priority_queue/container_rand_regression_test.tcc>
+
+#undef PB_DS_COND_COMPARE
+#undef PB_DS_RUN_MTHD
+#undef PB_DS_CLASS_T_DEC
+#undef PB_DS_CLASS_C_DEC
+#undef _GLIBCXX_THROW_IF_
+#undef _GLIBCXX_THROW_IF
+#undef PB_DS_TRACE
+
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc
new file mode 100644
index 000000000..e929f3533
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.tcc
@@ -0,0 +1,838 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file container_rand_regression_test.tcc
+ * Contains a random regression test for a specific container type.
+ */
+
+#ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
+#define PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
+
+ // Constructor, copy constructor, assignment and destructor.
+PB_DS_CLASS_T_DEC
+PB_DS_CLASS_C_DEC::
+container_rand_regression_test(unsigned long seed, size_t n, size_t m,
+ double tp, double ip, double dp, double ep,
+ double cp, double mp, bool disp)
+: m_seed(seed == 0 ? twister_rand_gen::get_time_determined_seed(): seed),
+ m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep), m_cp(cp),
+ m_mp(mp), m_disp(disp), m_p_c(0)
+{ }
+
+PB_DS_CLASS_T_DEC
+PB_DS_CLASS_C_DEC::
+~container_rand_regression_test()
+{ }
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+default_constructor()
+{
+ PB_DS_TRACE("default_constructor");
+ bool done = true;
+ m_alloc.set_probability(m_tp);
+
+ try
+ {
+ m_p_c = new Cntnr;
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ if (m_p_c)
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+swap()
+{
+ PB_DS_TRACE("swap");
+ m_alloc.set_probability(0);
+ Cntnr* p_c = new Cntnr;
+ m_alloc.set_probability(1);
+ p_c->swap(*m_p_c);
+ std::swap(p_c, m_p_c);
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+copy_constructor()
+{
+ PB_DS_TRACE("copy_constructor");
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+
+ typedef typename allocator_type::group_adjustor adjustor;
+ adjustor adjust(m_p_c->size());
+
+ try
+ {
+ p_c = new Cntnr(*m_p_c);
+ std::swap(p_c, m_p_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+assignment_operator()
+{
+ PB_DS_TRACE("assignment operator");
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+
+ typedef typename allocator_type::group_adjustor adjustor;
+ adjustor adjust(m_p_c->size());
+
+ try
+ {
+ p_c = new Cntnr();
+ *p_c = *m_p_c;
+ std::swap(p_c, m_p_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+it_constructor()
+{
+ bool done = true;
+ Cntnr* p_c = 0;
+ m_alloc.set_probability(m_tp);
+ typedef typename allocator_type::group_adjustor adjustor;
+ adjustor adjust(m_p_c->size());
+
+ try
+ {
+ switch(get_next_sub_op(3))
+ {
+ case 0:
+ p_c = new Cntnr(m_p_c->get_cmp_fn());
+ m_native_c.clear();
+ break;
+ case 1:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
+ break;
+ case 2:
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn());
+ break;
+ default:
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ };
+
+ std::swap(p_c, m_p_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+
+ delete p_c;
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ return done;
+}
+
+
+ // Compare.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+cmp(const Cntnr& c, const native_type& native, const std::string& callfn)
+{
+ destructor_printer notify(__FUNCTION__);
+
+ try
+ {
+ m_alloc.set_probability(1);
+
+ const size_t size = c.size();
+ const size_t native_size = native.size();
+ _GLIBCXX_THROW_IF(size != native_size, size << " " << native_size,
+ &c, &native);
+
+ const bool empty = c.empty();
+ const bool native_empty = native.empty();
+ _GLIBCXX_THROW_IF(empty != native_empty, empty << " " << native_empty,
+ &c, &native);
+
+ const size_t it_size = std::distance(c.begin(), c.end());
+ _GLIBCXX_THROW_IF(it_size != size, it_size << " " << size, &c, &native);
+
+ if (!c.empty())
+ {
+ const std::string native_top = native.top();
+ const std::string top = test_traits::native_value(c.top());
+ const bool top_smaller = std::less<std::string>()(top, native_top);
+ const bool top_larger = std::less<std::string>()(native_top, top);
+
+ if (top_smaller || top_larger)
+ _GLIBCXX_THROW_IF(true, top << " " << native_top, &c, &native);
+ }
+ }
+ catch(...)
+ {
+ _GLIBCXX_THROW_IF(true, "call-fn: " + callfn, &c, &native);
+ }
+
+ notify.cancel();
+}
+
+ // Operators.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+operator()()
+{
+ typedef xml_result_set_regression_formatter formatter_type;
+ formatter_type* p_fmt = 0;
+ if (m_disp)
+ p_fmt = new formatter_type(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
+
+ m_g.init(m_seed);
+ m_alloc.seed(m_seed);
+
+ // The __throw_allocator::_S_label defaults to 0, so to make things
+ // easier and more precise when debugging, start at 1.
+ const size_t starting_label(1);
+
+ try
+ {
+ prog_bar pb(m_n, std::cout, m_disp);
+
+ for (m_i = starting_label; m_i <= m_n; ++m_i)
+ {
+ PB_DS_TRACE("Op #" << m_i);
+
+ // Track allocation from this point only.
+ allocator_type::set_label(m_i);
+ switch(m_i)
+ {
+ case 1:
+ PB_DS_RUN_MTHD(default_constructor);
+ break;
+ case 2:
+ defs();
+ break;
+ case 3:
+ policy_access();
+ break;
+ case 4:
+ it_copy();
+ break;
+ case 5:
+ it_assign();
+ break;
+ default:
+ switch(get_next_op())
+ {
+ case insert_op:
+ PB_DS_RUN_MTHD(push)
+ break;
+ case modify_op:
+ PB_DS_RUN_MTHD(modify)
+ break;
+ case erase_op:
+ switch(get_next_sub_op(3))
+ {
+ case 0:
+ PB_DS_RUN_MTHD(pop)
+ break;
+ case 1:
+ PB_DS_RUN_MTHD(erase_if)
+ break;
+ case 2:
+ PB_DS_RUN_MTHD(erase_it)
+ break;
+ default:
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+ break;
+ case clear_op:
+ PB_DS_RUN_MTHD(clear)
+ break;
+ case other_op:
+ switch(get_next_sub_op(5))
+ {
+ case 0:
+ swap();
+ break;
+ case 1:
+ PB_DS_RUN_MTHD(copy_constructor)
+ break;
+ case 2:
+ PB_DS_RUN_MTHD(it_constructor)
+ break;
+ case 3:
+ PB_DS_RUN_MTHD(assignment_operator)
+ break;
+ case 4:
+ PB_DS_RUN_MTHD(split_join)
+ break;
+ default:
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+ break;
+ default:
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ };
+ }
+ pb.inc();
+ }
+ }
+ catch (...)
+ {
+ std::cerr << "Failed at index " << m_i << std::endl;
+ delete m_p_c;
+ throw;
+ }
+
+ // Clean up, then check for allocation by special label, set above.
+ allocator_type::set_label(0);
+ delete m_p_c;
+
+ try
+ {
+ for (size_t n = starting_label; n <= m_n; ++n)
+ m_alloc.check_allocated(n);
+ }
+ catch (std::logic_error& obj)
+ {
+ // On fail, check_allocated should throw std::logic_error.
+ std::cerr << obj.what() << std::endl;
+ std::cerr << typeid(Cntnr).name() << std::endl;
+ throw;
+ }
+
+ // Reset throw probability.
+ m_alloc.set_probability(0);
+
+ if (m_disp)
+ {
+ std::cout << std::endl;
+ delete p_fmt;
+ }
+}
+
+PB_DS_CLASS_T_DEC
+typename PB_DS_CLASS_C_DEC::op
+PB_DS_CLASS_C_DEC::
+get_next_op()
+{
+ const double prob = m_g.get_prob();
+
+ if (prob < m_ip)
+ return insert_op;
+
+ if (prob < m_ip + m_dp)
+ return modify_op;
+
+ if (prob < m_ip + m_dp + m_ep)
+ return erase_op;
+
+ if (prob < m_ip + m_dp + m_ep + m_cp)
+ return clear_op;
+
+ _GLIBCXX_THROW_IF(prob > 1, prob, m_p_c, &m_native_c);
+ return other_op;
+}
+
+PB_DS_CLASS_T_DEC
+size_t
+PB_DS_CLASS_C_DEC::
+get_next_sub_op(size_t max)
+{
+ const double p = m_g.get_prob();
+ const double delta = 1 / static_cast<double>(max);
+ size_t i = 0;
+ while (true)
+ if (p <= (i + 1) * delta)
+ {
+ _GLIBCXX_THROW_IF(i >= max, i << " " << max, m_p_c, &m_native_c);
+ return i;
+ }
+ else
+ ++i;
+}
+
+ // Insert.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+push()
+{
+ PB_DS_TRACE("push");
+ bool done = true;
+ destructor_printer notify(__FUNCTION__);
+
+ try
+ {
+ m_alloc.set_probability(0);
+ value_type v = test_traits::generate_value(m_g, m_m);
+ m_alloc.set_probability(m_tp);
+ const typename cntnr::size_type sz = m_p_c->size();
+ m_p_c->push(v);
+ _GLIBCXX_THROW_IF(sz != m_p_c->size() - 1, sz, m_p_c, &m_native_c);
+ m_native_c.push(test_traits::native_value(v));
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ }
+ catch(...)
+ {
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ notify.cancel();
+ return done;
+}
+
+
+ // Modify.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+modify()
+{
+ PB_DS_TRACE("modify");
+ destructor_printer notify(__FUNCTION__);
+
+ bool done = true;
+ try
+ {
+ m_alloc.set_probability(0);
+ value_type v = test_traits::generate_value(m_g, m_m);
+
+ m_alloc.set_probability(m_tp);
+ typename cntnr::iterator it = m_p_c->begin();
+ std::advance(it, m_g.get_unsigned_long(0, m_p_c->size()));
+ if (it != m_p_c->end())
+ {
+ typedef typename test_traits::native_value_type native_value_type;
+ native_value_type native_v = test_traits::native_value(*it);
+ native_value_type new_native_v = test_traits::native_value(v);
+ m_p_c->modify(it, v);
+ m_native_c.modify(native_v, new_native_v);
+ }
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ notify.cancel();
+ return done;
+}
+
+ // Clear.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+clear()
+{
+ PB_DS_TRACE("clear");
+ m_p_c->clear();
+ m_native_c.clear();
+ return true;
+}
+
+ // Erase.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+pop()
+{
+ PB_DS_TRACE("pop");
+ destructor_printer notify(__FUNCTION__);
+
+ bool done = true;
+ try
+ {
+ m_alloc.set_probability(1);
+ if (!m_p_c->empty())
+ {
+ m_p_c->pop();
+ m_native_c.pop();
+ }
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ notify.cancel();
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_if()
+{
+ PB_DS_TRACE("erase_if");
+ destructor_printer notify(__FUNCTION__);
+
+ bool done = true;
+ try
+ {
+ typedef
+ typename std::iterator_traits<typename cntnr::iterator>::reference
+ it_const_reference;
+
+ m_alloc.set_probability(1);
+
+ typedef
+ typename test_traits::template erase_if_fn<value_type>
+ erase_if_fn_t;
+
+ const size_t ersd = m_p_c->erase_if(erase_if_fn_t());
+
+ typedef
+ typename test_traits::template erase_if_fn<std::string>
+ native_erase_if_fn_t;
+
+ const size_t native_ersd = m_native_c.erase_if(native_erase_if_fn_t());
+
+ _GLIBCXX_THROW_IF(ersd != native_ersd, ersd << " " << native_ersd,
+ m_p_c, &m_native_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ notify.cancel();
+ return done;
+}
+
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+erase_it()
+{
+ PB_DS_TRACE("erase_it");
+ destructor_printer notify(__FUNCTION__);
+
+ bool done = true;
+ try
+ {
+ m_alloc.set_probability(1);
+ typename cntnr::iterator it = m_p_c->begin();
+ std::advance(it, m_g.get_unsigned_long(0, m_p_c->size()));
+
+ if (it != m_p_c->end())
+ {
+ m_native_c.erase(*it);
+ m_p_c->erase(it);
+ }
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ _GLIBCXX_THROW_IF(true, "", m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ notify.cancel();
+ return done;
+}
+
+ // Defs.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+defs()
+{
+ // General container types.
+ typedef typename Cntnr::size_type test_size_type;
+ typedef typename Cntnr::difference_type difference_type;
+ value_defs();
+ iterator_defs();
+ policy_defs();
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+value_defs()
+{
+ typedef typename Cntnr::value_type test_value_type;
+ typedef typename Cntnr::reference test_reference;
+ typedef typename Cntnr::const_reference test_const_reference;
+ typedef typename Cntnr::pointer test_pointer;
+ typedef typename Cntnr::const_pointer test_const_pointer;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+ds_defs()
+{
+ typedef typename Cntnr::container_category test_container_category;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+iterator_defs()
+{
+ typedef typename Cntnr::point_iterator test_point_iterator;
+ typedef typename Cntnr::const_point_iterator const_test_point_iterator;
+ typedef typename Cntnr::iterator test_iterator;
+ typedef typename Cntnr::const_iterator const_test_iterator;
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_defs()
+{
+ typedef typename Cntnr::allocator_type test_allocator;
+ typedef typename Cntnr::cmp_fn test_cmp_fn;
+}
+
+
+// Policy access.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+policy_access()
+{
+ PB_DS_TRACE("policy_access");
+
+ {
+ typename Cntnr::cmp_fn& r_t = m_p_c->get_cmp_fn();
+ assert(&r_t);
+ }
+
+ {
+ const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn();
+ assert(&r_t);
+ }
+}
+
+// Split join.
+PB_DS_CLASS_T_DEC
+bool
+PB_DS_CLASS_C_DEC::
+split_join()
+{
+ PB_DS_TRACE("split_join");
+ destructor_printer notify(__FUNCTION__);
+
+ bool done = true;
+ try
+ {
+ m_alloc.set_probability(0);
+ Cntnr lhs(*m_p_c);
+ Cntnr rhs;
+ native_type native_lhs(m_native_c);
+ m_alloc.set_probability(m_tp);
+
+ typedef typename test_traits::template erase_if_fn<value_type> split_fn_t;
+ lhs.split(split_fn_t(), rhs);
+
+ typedef typename test_traits::template erase_if_fn<std::string>
+ native_split_fn_t;
+
+ native_type native_rhs;
+ native_lhs.split(native_split_fn_t(), native_rhs);
+ PB_DS_COND_COMPARE(lhs, native_lhs);
+ PB_DS_COND_COMPARE(rhs, native_rhs);
+
+ m_alloc.set_probability(m_tp);
+
+ if (m_g.get_prob() < 0.5)
+ lhs.swap(rhs);
+ lhs.join(rhs);
+
+ _GLIBCXX_THROW_IF(rhs.size() != 0, rhs.size(), m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!rhs.empty(), rhs.size(), m_p_c, &m_native_c);
+ }
+ catch(__gnu_cxx::forced_error&)
+ {
+ done = false;
+ const bool b = __gnu_pbds::container_traits<cntnr>::split_join_can_throw;
+ _GLIBCXX_THROW_IF(!b, b, m_p_c, &m_native_c);
+ }
+
+ PB_DS_COND_COMPARE(*m_p_c, m_native_c);
+ notify.cancel();
+ return done;
+}
+
+// Iterator conversions.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+it_copy()
+{
+ PB_DS_TRACE("it_copy");
+
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_iterator const_it(it);
+ _GLIBCXX_THROW_IF(const_it != it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(const_it == it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::const_iterator const_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it(const_it);
+ _GLIBCXX_THROW_IF(const_find_it != const_it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(const_find_it == const_it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it1(it);
+ _GLIBCXX_THROW_IF(const_find_it1 != it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(const_find_it1 == it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it1(it);
+ _GLIBCXX_THROW_IF(find_it1 != it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(find_it1 == it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it(find_it);
+ _GLIBCXX_THROW_IF(find_it != const_find_it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(find_it == const_find_it), "", m_p_c, &m_native_c);
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+it_assign()
+{
+ PB_DS_TRACE("it_assign");
+
+ {
+ typename cntnr::iterator it = m_p_c->end();
+ typename cntnr::const_iterator const_it;
+ const_it = it;
+ _GLIBCXX_THROW_IF(const_it != it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(const_it == it), "", m_p_c, &m_native_c);
+
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = it;
+ _GLIBCXX_THROW_IF(const_find_it != it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(const_find_it == it), "", m_p_c, &m_native_c);
+
+ typename cntnr::point_iterator find_it;
+ find_it = it;
+ _GLIBCXX_THROW_IF(find_it != it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(find_it == it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::const_iterator const_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = const_it;
+ _GLIBCXX_THROW_IF(const_find_it != const_it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(const_find_it == const_it), "", m_p_c, &m_native_c);
+ }
+
+ {
+ typename cntnr::point_iterator find_it = m_p_c->end();
+ typename cntnr::const_point_iterator const_find_it;
+ const_find_it = find_it;
+ _GLIBCXX_THROW_IF(find_it != const_find_it, "", m_p_c, &m_native_c);
+ _GLIBCXX_THROW_IF(!(find_it == const_find_it), "", m_p_c, &m_native_c);
+ }
+}
+
+
+// Diagnostics.
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+print_container(const native_type& cnt, std::ostream& os) const
+{
+ m_alloc.set_probability(0);
+ native_type cpy(cnt);
+ while (!cpy.empty())
+ {
+ os << cpy.top() << std::endl;
+ cpy.pop();
+ }
+}
+
+PB_DS_CLASS_T_DEC
+void
+PB_DS_CLASS_C_DEC::
+print_container(const cntnr& cnt, std::ostream& os) const
+{
+ typedef typename cntnr::const_iterator const_iterator;
+ m_alloc.set_probability(0);
+ for (const_iterator it = cnt.begin(); it != cnt.end(); ++it)
+ os << *it << std::endl;
+}
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp
new file mode 100644
index 000000000..37f8d51af
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/rand_regression_test.hpp
@@ -0,0 +1,202 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2008, 2009, 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file rand_regression_test.hpp
+ * Contains a random-operation test.
+ */
+
+#ifndef PB_DS_PQ_RAND_REGRESSION_TEST_HPP
+#define PB_DS_PQ_RAND_REGRESSION_TEST_HPP
+
+#include <iostream>
+#include <vector>
+#include <io/verified_cmd_line_input.hpp>
+#include <regression/common_type.hpp>
+#include <regression/rand/priority_queue/container_rand_regression_test.h>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+#ifndef PB_DS_REGRESSION
+#error "Must define PB_DS_REGRESSION"
+#endif
+
+ struct rand_reg_test
+ {
+ public:
+ rand_reg_test(size_t seed, size_t n, size_t m, double tp, double ip,
+ double dp, double ep, double cp, double mp, bool d)
+ : m_sd(seed), m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_dp(dp), m_ep(ep),
+ m_cp(cp), m_mp(mp), m_disp(d)
+ { }
+
+ template<typename Cntnr>
+ void
+ operator()(Cntnr)
+ {
+ unsigned long ul = static_cast<unsigned long>(m_sd);
+ container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip, m_dp,
+ m_ep, m_cp, m_mp, m_disp);
+ t();
+ }
+
+ private:
+ const size_t m_sd;
+ const size_t m_n;
+ const size_t m_m;
+ const double m_tp;
+ const double m_ip;
+ const double m_dp;
+ const double m_ep;
+ const double m_cp;
+ const double m_mp;
+ const bool m_disp;
+ };
+
+ void
+ usage(const std::string& r_name);
+
+ void
+ verify_params(size_t&, size_t&, size_t&,
+ double&, double&, double&, double&, double&, double&, bool&);
+} // namespace detail
+
+ template<typename TL>
+ int
+ rand_regression_test(size_t iter, size_t keys, const std::string name, TL tl)
+ {
+ // Sane defaults.
+ size_t n = iter;
+ size_t m = keys;
+ size_t sd = 0; // 0 = time-determined arbitrary
+ double tp = 0.2;
+ double ip = 0.6;
+ double dp = 0.1;
+ double ep = 0.2;
+ double cp = 0.001;
+ double mp = 1;
+ bool disp = false; // show progress
+
+ try
+ {
+ detail::verify_params(sd, n, m, tp, ip, dp, ep, cp, mp, disp);
+ }
+ catch(__gnu_pbds::test::illegal_input_error&)
+ {
+ detail::usage(name);
+ return -1;
+ }
+ catch(...)
+ {
+ return -2;
+ };
+
+ xml_test_rand_regression_formatter* p_fmt = 0;
+ if (sd == 0)
+ sd = twister_rand_gen::get_time_determined_seed();
+ if (disp)
+ p_fmt = new xml_test_rand_regression_formatter(sd, n, m, tp, ip, dp,
+ ep, cp, mp);
+
+ try
+ {
+ detail::rand_reg_test tst(sd, n, m, tp, ip, dp, ep, cp, mp, disp);
+ __gnu_cxx::typelist::apply(tst, tl);
+ }
+ catch(...)
+ {
+ std::cerr << "Test failed with seed " << sd << std::endl;
+ if (disp)
+ delete p_fmt;
+ return -1;
+ }
+
+ if (disp)
+ delete p_fmt;
+ return 0;
+ }
+
+namespace detail
+{
+ inline void
+ usage(const std::string& name)
+ {
+ using namespace std;
+ cerr << "usage: " << name << " <sd> <n> <m> <tp> <ip> <dp> <ep> <cp> <mp> ['t' | 'f']" <<
+ endl << endl;
+
+ cerr << "This test performs basic regression tests on various priority queues."
+ "For each container, it performs a sequence of operations. At each iteration, it does "
+ "the following: " << endl;
+ cerr << "* Performs an operation on the container " << endl;
+ cerr << "* Performs the same operation on an cntnr object" << endl;
+ cerr << "* Possibly compares the container to the cntnr object" << endl;
+ cerr << "* Checks that exceptions (thrown by an allocator) "
+ "do not violate exception guarantees";
+
+ cerr << endl << endl;
+
+ cerr << "sd = seed for random-number generator; 0 = "
+ "time determined value" << endl;
+ cerr << "n = number of iterations" << endl;
+ cerr << "m = number of distinct values" << endl;
+ cerr << "tp = probability that an exception will be actively thrown" << endl;
+ cerr << "ip = probability that an operation will be insert" << endl;
+ cerr << "dp = probability that an operation will be modify" << endl;
+ cerr << "ep = probability that an operation will be erase" << endl;
+ cerr << "cp = probability that an operation will be clear" << endl;
+ cerr << "(therefore, 1 - (ip + dp + ep + cp) = probability of any other operation)" << endl;
+ cerr << "mp = probability that the container will be compared to the cntnr object" << endl;
+ cerr << "'t' or 'f' determine whether progress will be displayed" << endl;
+ }
+
+ inline void
+ verify_params(size_t& r_seed, size_t& r_n,
+ size_t& r_m, double& r_tp, double& r_ip, double& r_dp,
+ double& r_ep, double& r_cp, double& r_mp, bool& r_d)
+ {
+ verify_prob(r_tp);
+ verify_prob(r_ip);
+ verify_prob(r_dp);
+ verify_prob(r_ep);
+ verify_prob(r_cp);
+ verify_prob(r_mp);
+ verify_prob(r_ip + r_dp + r_ep + r_cp);
+ }
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp b/libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp
new file mode 100644
index 000000000..5dca782c5
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/rand/xml_formatter.hpp
@@ -0,0 +1,100 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file xml_formatter.hpp
+ * Contains an XML formatter for regression tests.
+ */
+
+#ifndef PB_DS_COMMON_XML_TEST_REGRESSION_FORMATTER_HPP
+#define PB_DS_COMMON_XML_TEST_REGRESSION_FORMATTER_HPP
+
+#include <string>
+#include <iostream>
+#include <io/xml_test_formatter.hpp>
+
+namespace __gnu_pbds
+{
+ namespace test
+ {
+ // Test formatters.
+ struct xml_test_rand_regression_formatter : public xml_test_formatter
+ {
+ // Associative.
+ xml_test_rand_regression_formatter(size_t sd, size_t n, size_t m,
+ double tp, double ip, double ep,
+ double cp, double mp)
+ {
+ std::cout << make_xml_tag("sd", "value", sd);
+ std::cout << make_xml_tag("n", "value", n);
+ std::cout << make_xml_tag("m", "value", m);
+ std::cout << make_xml_tag("tp", "value", tp);
+ std::cout << make_xml_tag("ip", "value", ip);
+ std::cout << make_xml_tag("ep", "value", ep);
+ std::cout << make_xml_tag("cp", "value", cp);
+ std::cout << make_xml_tag("mp", "value", mp);
+ }
+
+ // Priority Queue.
+ xml_test_rand_regression_formatter(size_t sd, size_t n, size_t m,
+ double tp, double ip, double dp,
+ double ep, double cp, double mp)
+ {
+ std::cout << make_xml_tag("sd", "value", sd);
+ std::cout << make_xml_tag("n", "value", n);
+ std::cout << make_xml_tag("m", "value", m);
+ std::cout << make_xml_tag("tp", "value", tp);
+ std::cout << make_xml_tag("ip", "value", ip);
+ std::cout << make_xml_tag("dp", "value", dp);
+ std::cout << make_xml_tag("ep", "value", ep);
+ std::cout << make_xml_tag("cp", "value", cp);
+ std::cout << make_xml_tag("mp", "value", mp);
+ }
+ };
+
+ // Result formatter.
+ struct xml_result_set_regression_formatter : public xml_result_set_formatter
+ {
+ xml_result_set_regression_formatter(const std::string& r_container_name,
+ const std::string& r_container_desc)
+ : xml_result_set_formatter(r_container_name, r_container_desc)
+ {
+ std::cout << detail::make_xml_name_start_tag("progress");
+ std::cout << detail::make_xml_name_start_tag_end_delimiter();
+ }
+
+ ~xml_result_set_regression_formatter()
+ { std::cout << detail::make_xml_name_end_tag("progress"); }
+ };
+ } // namespace test
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_COMMON_XML_TEST_REGRESSION_FORMATTER_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp
new file mode 100644
index 000000000..b771b8020
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_load_trait.hpp
@@ -0,0 +1,90 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file get_set_load_trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_SET_LOAD_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_SET_LOAD_TRAIT_HPP
+
+#include <ext/pb_ds/assoc_container.hpp>
+
+namespace __gnu_pbds
+{
+
+ namespace test
+ {
+
+ namespace detail
+ {
+
+ template<typename Cntnr, class Tag>
+ struct regression_test_get_set_load_traits
+ {
+ enum
+ {
+ value = false
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_hash_get_set_load_traits
+ {
+ enum
+ {
+ value = Cntnr::resize_policy::trigger_policy::get_set_load
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_get_set_load_traits<
+ Cntnr,
+ __gnu_pbds::cc_hash_tag> : public regression_test_hash_get_set_load_traits<
+ Cntnr>
+ { };
+
+ template<typename Cntnr>
+ struct regression_test_get_set_load_traits<
+ Cntnr,
+ __gnu_pbds::gp_hash_tag> : public regression_test_hash_get_set_load_traits<
+ Cntnr>
+ { };
+
+ } // namespace detail
+
+ } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_REGRESSION_TEST_SET_LOAD_TRAIT_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp
new file mode 100644
index 000000000..6d7508da8
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/get_set_loads_trait.hpp
@@ -0,0 +1,90 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file get_set_loads_trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_SET_LOADS_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_SET_LOADS_TRAIT_HPP
+
+#include <ext/pb_ds/assoc_container.hpp>
+
+namespace __gnu_pbds
+{
+
+ namespace test
+ {
+
+ namespace detail
+ {
+
+ template<typename Cntnr, class Tag>
+ struct regression_test_get_set_loacontainer_traits
+ {
+ enum
+ {
+ value = false
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_hash_get_set_loacontainer_traits
+ {
+ enum
+ {
+ value = Cntnr::resize_policy::trigger_policy::get_set_loads
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_get_set_loacontainer_traits<
+ Cntnr,
+ __gnu_pbds::cc_hash_tag> : public regression_test_hash_get_set_loacontainer_traits<
+ Cntnr>
+ { };
+
+ template<typename Cntnr>
+ struct regression_test_get_set_loacontainer_traits<
+ Cntnr,
+ __gnu_pbds::gp_hash_tag> : public regression_test_hash_get_set_loacontainer_traits<
+ Cntnr>
+ { };
+
+ } // namespace detail
+
+ } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_REGRESSION_TEST_SET_LOADS_TRAIT_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp
new file mode 100644
index 000000000..38761a177
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/native_type_trait.hpp
@@ -0,0 +1,185 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file native_type_trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_NATIVE_TYPE_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_NATIVE_TYPE_TRAIT_HPP
+
+namespace __gnu_pbds
+{
+
+ namespace test
+ {
+
+ namespace detail
+ {
+
+ template<typename Key, class Allocator>
+ struct native_key_type;
+
+ template<typename Allocator>
+ struct native_key_type<
+ basic_type,
+ Allocator>
+ {
+ typedef std::string type;
+
+ static type
+ native_key(typename Allocator::template rebind<
+ basic_type>::other::const_reference r_key)
+ {
+ return (std::string(r_key));
+ }
+ };
+
+ template<typename Hd, class Tl, class Allocator>
+ struct native_key_type<
+ std::pair<
+ Hd,
+ Tl>,
+ Allocator>
+ {
+ typedef typename native_key_type< Hd, Allocator>::type hd_type;
+
+ typedef typename native_key_type< Tl, Allocator>::type tl_type;
+
+ typedef std::pair< hd_type, tl_type> type;
+
+ static type
+ native_key(typename Allocator::template rebind< std::pair<Hd, Tl> >::other::const_reference r_key)
+ {
+ return (std::make_pair(
+ native_key_type<Hd, Allocator>::native_key(r_key.first),
+ native_key_type<Tl, Allocator>::native_key(r_key.second)));
+ }
+ };
+
+ template<typename Native_Key_Type,
+ class Key_Type,
+ class Data_Type,
+ class Allocator>
+ struct native_type_traits_base;
+
+ template<typename Native_Key_Type, class Key_Type, class Allocator>
+ struct native_type_traits_base<
+ Native_Key_Type,
+ Key_Type,
+ basic_type,
+ Allocator>
+ {
+ public:
+ typedef std::map< Native_Key_Type, std::string> type;
+
+ public:
+ static const typename type::key_type&
+ extract_key(typename type::const_reference r_val)
+ {
+ return (r_val.first);
+ }
+
+ static typename type::value_type
+ native_value(typename Allocator::template rebind< std::pair<Key_Type, basic_type> >::other::const_reference r_val)
+ {
+ return (std::make_pair(
+ native_key_type<Key_Type, Allocator>::native_key(r_val.first),
+ std::string(r_val.second)));
+ }
+ };
+
+ template<typename Native_Key_Type, class Key_Type, class Allocator>
+ struct native_type_traits_base<
+ Native_Key_Type,
+ Key_Type,
+ __gnu_pbds::null_mapped_type,
+ Allocator>
+ {
+ public:
+ typedef std::set< Native_Key_Type> type;
+
+ public:
+ static const typename type::key_type&
+ extract_key(typename type::const_reference r_val)
+ {
+ return (r_val);
+ }
+
+ static typename type::value_type
+ native_value(typename Allocator::template rebind<
+ Key_Type>::other::const_reference r_val)
+ {
+ return (native_key_type<Key_Type, Allocator>::native_key(
+ r_val));
+ }
+ };
+
+#define PB_DS_NATIVE_KEY_TYPE_C_DEC \
+ native_key_type< \
+ Key_Type, \
+ Allocator>
+
+#define PB_DS_BASE_C_DEC \
+ native_type_traits_base< \
+ typename PB_DS_NATIVE_KEY_TYPE_C_DEC::type, \
+ Key_Type, \
+ Data_Type, \
+ Allocator>
+
+ template<typename Key_Type, class Data_Type, class Allocator>
+ struct native_type_traits : public PB_DS_BASE_C_DEC
+ {
+ typedef typename PB_DS_BASE_C_DEC::type type;
+
+ typedef typename type::key_type key_type;
+
+ static typename PB_DS_NATIVE_KEY_TYPE_C_DEC::type
+ native_key(typename Allocator::template rebind<
+ Key_Type>::other::const_reference r_key)
+ {
+ return (PB_DS_NATIVE_KEY_TYPE_C_DEC::native_key(r_key));
+ }
+ };
+
+#undef PB_DS_BASE_C_DEC
+
+#undef PB_DS_NATIVE_KEY_TYPE_C_DEC
+
+ } // namespace detail
+
+ } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_REGRESSION_TEST_NATIVE_TYPE_TRAIT_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp
new file mode 100644
index 000000000..d971c1fb2
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/node_update_trait.hpp
@@ -0,0 +1,124 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file node_update_trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_NODE_UPDATOR_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_NODE_UPDATOR_TRAIT_HPP
+
+#include <ext/pb_ds/assoc_container.hpp>
+#include <common_type/assoc/detail/tree_supports_order_statistics.hpp>
+#include <common_type/assoc/detail/trie_supports_order_statistics.hpp>
+#include <common_type/assoc/detail/trie_supports_prefix_search.hpp>
+
+namespace __gnu_pbds
+{
+
+ namespace test
+ {
+
+ namespace detail
+ {
+
+ template<typename Cntnr, class Tag>
+ struct regression_test_node_update_traits
+ {
+ enum
+ {
+ order_statistics = false,
+ prefix_search = false
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_node_update_traits<
+ Cntnr,
+ __gnu_pbds::pat_trie_tag>
+ {
+ enum
+ {
+ order_statistics =
+ trie_supports_order_statistics<Cntnr>::value,
+ prefix_search =
+ trie_supports_prefix_search<Cntnr>::value
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_node_update_traits<
+ Cntnr,
+ __gnu_pbds::rb_tree_tag>
+ {
+ enum
+ {
+ order_statistics =
+ tree_supports_order_statistics<Cntnr>::value,
+ prefix_search = false
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_node_update_traits<
+ Cntnr,
+ __gnu_pbds::splay_tree_tag>
+ {
+ enum
+ {
+ order_statistics =
+ tree_supports_order_statistics<Cntnr>::value,
+ prefix_search = false
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_node_update_traits<
+ Cntnr,
+ __gnu_pbds::ov_tree_tag>
+ {
+ enum
+ {
+ order_statistics =
+ tree_supports_order_statistics<Cntnr>::value,
+ prefix_search = false
+ };
+ };
+
+ } // namespace detail
+
+ } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_REGRESSION_TEST_NODE_UPDATOR_TRAIT_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp
new file mode 100644
index 000000000..51e012775
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/resize_trait.hpp
@@ -0,0 +1,90 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file resize_trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_RESIZE_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_RESIZE_TRAIT_HPP
+
+#include <ext/pb_ds/assoc_container.hpp>
+
+namespace __gnu_pbds
+{
+
+ namespace test
+ {
+
+ namespace detail
+ {
+
+ template<typename Cntnr, class Tag>
+ struct regression_test_resize_traits
+ {
+ enum
+ {
+ value = false
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_hash_resize_traits
+ {
+ enum
+ {
+ value = Cntnr::resize_policy::external_size_access
+ };
+ };
+
+ template<typename Cntnr>
+ struct regression_test_resize_traits<
+ Cntnr,
+ __gnu_pbds::cc_hash_tag> : public regression_test_hash_resize_traits<
+ Cntnr>
+ { };
+
+ template<typename Cntnr>
+ struct regression_test_resize_traits<
+ Cntnr,
+ __gnu_pbds::gp_hash_tag> : public regression_test_hash_resize_traits<
+ Cntnr>
+ { };
+
+ } // namespace detail
+
+ } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_REGRESSION_TEST_RESIZE_TRAIT_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp
new file mode 100644
index 000000000..7a1a2e305
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/to_string.hpp
@@ -0,0 +1,81 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file to_string.hpp
+ * Contains classes for transforming stuff to strings.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_TO_STRING_HPP
+#define PB_DS_REGRESSION_TEST_TO_STRING_HPP
+
+#include <regression/basic_type.hpp>
+#include <string>
+
+namespace __gnu_pbds
+{
+
+ namespace test
+ {
+
+ namespace detail
+ {
+
+ std::string
+ to_string(const basic_type& r_t)
+ {
+ return (r_t);
+ }
+
+ std::string
+ to_string(const std::string& r_t)
+ {
+ return (r_t);
+ }
+
+ template<typename Hd, class Tl>
+ std::string
+ to_string(const std::pair<Hd, Tl>&r_t)
+ {
+ std::ostringstream ret;
+
+ ret << to_string(r_t.first) << " " << to_string(r_t.second);
+
+ return (ret.str());
+ }
+
+ } // namespace detail
+
+ } // namespace test
+
+} // namespace __gnu_pbds
+
+#endif // #ifndef PB_DS_REGRESSION_TEST_TO_STRING_HPP
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp
new file mode 100644
index 000000000..a4a768e5e
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp
@@ -0,0 +1,206 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_TRAIT_HPP
+
+#include <regression/trait/erase_if_fn.hpp>
+#include <regression/trait/assoc/to_string.hpp>
+#include <regression/trait/assoc/type_trait.hpp>
+#include <regression/trait/assoc/native_type_trait.hpp>
+#include <regression/trait/assoc/resize_trait.hpp>
+#include <regression/trait/assoc/get_set_loads_trait.hpp>
+#include <regression/trait/assoc/get_set_load_trait.hpp>
+#include <regression/trait/assoc/node_update_trait.hpp>
+
+namespace __gnu_pbds
+{
+namespace test
+{
+namespace detail
+{
+
+#define PB_DS_CLASS_T_DEC \
+ template<typename Cntnr>
+
+#define PB_DS_CLASS_C_DEC \
+ regression_test_traits<Cntnr>
+
+#define PB_DS_TYPE_TRAITS_C_DEC \
+ regression_test_type_traits<Cntnr>
+
+#define PB_DS_NATIVE_TYPE_TRAITS_C_DEC \
+ native_type_traits<typename PB_DS_TYPE_TRAITS_C_DEC::key_type, \
+ typename PB_DS_TYPE_TRAITS_C_DEC::mapped_type, \
+ typename Cntnr::allocator_type>
+
+#define PB_DS_RESIZE_TRAITS_C_DEC \
+ regression_test_resize_traits<Cntnr, typename Cntnr::container_category>
+
+#define PB_DS_SET_LOADS_TRAITS_C_DEC \
+ regression_test_get_set_loacontainer_traits<Cntnr, \
+ typename Cntnr::container_category>
+
+#define PB_DS_SET_LOAD_TRAITS_C_DEC \
+ regression_test_get_set_load_traits<Cntnr,typename Cntnr::container_category>
+
+#define PB_DS_NODE_UPDATOR_TRAITS_C_DEC \
+ regression_test_node_update_traits<Cntnr, typename Cntnr::container_category>
+
+ template<typename Cntnr>
+ struct regression_test_traits : private PB_DS_TYPE_TRAITS_C_DEC,
+ private PB_DS_NATIVE_TYPE_TRAITS_C_DEC,
+ private PB_DS_RESIZE_TRAITS_C_DEC,
+ private PB_DS_NODE_UPDATOR_TRAITS_C_DEC,
+ private PB_DS_SET_LOADS_TRAITS_C_DEC,
+ private PB_DS_SET_LOAD_TRAITS_C_DEC
+ {
+ private:
+ typedef PB_DS_NATIVE_TYPE_TRAITS_C_DEC native_type_traits_base;
+ typedef PB_DS_TYPE_TRAITS_C_DEC type_traits_base;
+
+ public:
+ typedef typename Cntnr::value_type value_type;
+ typedef typename Cntnr::const_reference const_reference;
+ typedef typename PB_DS_NATIVE_TYPE_TRAITS_C_DEC::type native_type;
+ typedef typename native_type::value_type native_value_type;
+
+ // Only associative containers.
+ typedef typename Cntnr::key_type key_type;
+ typedef typename Cntnr::const_key_reference const_key_reference;
+ typedef typename native_type::key_type native_key_type;
+
+ enum
+ {
+ resize = PB_DS_RESIZE_TRAITS_C_DEC::value,
+ get_set_loads = PB_DS_SET_LOADS_TRAITS_C_DEC::value,
+ get_set_load = PB_DS_SET_LOAD_TRAITS_C_DEC::value,
+ order_statistics = PB_DS_NODE_UPDATOR_TRAITS_C_DEC::order_statistics,
+ prefix_search = PB_DS_NODE_UPDATOR_TRAITS_C_DEC::prefix_search
+ };
+
+ template<typename T>
+ struct erase_if_fn : public regression_test_erase_if_fn<T>
+ { };
+
+ static size_t
+ erase_if(native_type& r_native_c)
+ {
+ typedef regression_test_erase_if_fn<native_value_type> erase_if_fn;
+ typename native_type::iterator it = r_native_c.begin();
+ size_t num_ersd = 0;
+ while (it != r_native_c.end())
+ if (erase_if_fn()(*it))
+ {
+ ++num_ersd;
+ r_native_c.erase(it);
+ it = r_native_c.begin();
+ }
+ else
+ ++it;
+ return num_ersd;
+ }
+
+ static void
+ print_container(const Cntnr& r_c, std::ostream& r_os)
+ { PB_DS_TYPE_TRAITS_C_DEC::print_container(r_c, r_os); }
+
+ template<typename Gen>
+ static key_type
+ generate_key(Gen& r_gen, size_t max)
+ { return PB_DS_TYPE_TRAITS_C_DEC::generate_key(r_gen, max); }
+
+ template<typename Gen>
+ static value_type
+ generate_value(Gen& r_gen, size_t max)
+ { return PB_DS_TYPE_TRAITS_C_DEC::generate_value(r_gen, max); }
+
+ static const_key_reference
+ extract_key(const_reference r_val)
+ { return type_traits_base::extract_key(r_val); }
+
+ static native_key_type
+ native_key(const_key_reference r_key)
+ { return native_type_traits_base::native_key(r_key); }
+
+ static native_value_type
+ native_value(const_reference r_val)
+ { return native_type_traits_base::native_value(r_val); }
+
+ static const native_key_type&
+ extract_native_key(const native_value_type& r_val)
+ { return native_type_traits_base::extract_key(r_val); }
+
+ static bool
+ cmp(const_reference r_val, const native_value_type& r_native_val)
+ { return val_to_string(r_val) == native_val_to_string(r_native_val); }
+
+ static std::string
+ val_to_string(const_reference r_val)
+ { return to_string(r_val); }
+
+ static std::string
+ key_to_string(const_key_reference r_key)
+ { return to_string(r_key); }
+
+ static std::string
+ native_val_to_string(const native_value_type& r_native_val)
+ { return to_string(r_native_val); }
+
+ static bool
+ prefix_match(const_key_reference r_key, const std::string& r_native_key)
+ {
+ const size_t len = std::min(r_key.length(), r_native_key.length());
+ const std::string substr = r_native_key.substr(0, len);
+ return substr == static_cast<const std::string&>(r_key);
+ }
+ };
+
+#undef PB_DS_TYPE_TRAITS_C_DEC
+#undef PB_DS_NATIVE_TYPE_TRAITS_C_DEC
+#undef PB_DS_RESIZE_TRAITS_C_DEC
+#undef PB_DS_SET_LOADS_TRAITS_C_DEC
+#undef PB_DS_SET_LOAD_TRAITS_C_DEC
+#undef PB_DS_NODE_UPDATOR_TRAITS_C_DEC
+#undef PB_DS_CLASS_T_DEC
+#undef PB_DS_CLASS_C_DEC
+
+} // namespace detail
+} // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp
new file mode 100644
index 000000000..c7ce5f7a3
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp
@@ -0,0 +1,111 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file type_trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_TYPE_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_TYPE_TRAIT_HPP
+
+#include <regression/basic_type.hpp>
+
+namespace __gnu_pbds
+{
+ namespace test
+ {
+ namespace detail
+ {
+ template<typename Cntnr>
+ struct regression_test_type_traits
+ {
+ typedef Cntnr cntnr;
+ typedef typename cntnr::key_type key_type;
+ typedef typename cntnr::const_key_reference const_key_reference;
+ typedef typename cntnr::value_type value_type;
+ typedef typename cntnr::const_reference const_reference;
+ typedef typename cntnr::mapped_type mapped_type;
+ typedef typename cntnr::const_mapped_reference const_mapped_reference;
+
+ template<typename Gen>
+ static key_type
+ generate_key(Gen& r_gen, size_t max)
+ { return basic_type(r_gen, max); }
+
+ template<typename Gen>
+ static value_type
+ generate_value(Gen& r_gen, size_t max)
+ { return generate_value(r_gen, max, value_type()); }
+
+ static const_key_reference
+ extract_key(const_reference r_val)
+ { return extract_key_imp(r_val); }
+
+ private:
+ typedef typename cntnr::allocator_type::template rebind<basic_type>::other
+ basic_type_rebind;
+
+ typedef typename basic_type_rebind::const_reference basic_type_const_reference;
+
+ typedef typename cntnr::allocator_type::template rebind<std::pair<const basic_type, basic_type> >::other pair_type_rebind;
+ typedef typename pair_type_rebind::const_reference pair_type_const_reference;
+
+ template<typename Gen>
+ static value_type
+ generate_value(Gen& r_gen, size_t max, __gnu_pbds::null_mapped_type)
+ { return basic_type(r_gen, max); }
+
+ template<typename Gen>
+ static value_type
+ generate_value(Gen& r_gen, size_t max, basic_type)
+ { return basic_type(r_gen, max); }
+
+ template<typename Gen>
+ static value_type
+ generate_value(Gen& gen, size_t max,
+ std::pair<const basic_type, basic_type>)
+ { return std::make_pair(basic_type(gen, max), basic_type(gen, max)); }
+
+ static const_key_reference
+ extract_key_imp(basic_type_const_reference r_val)
+ { return r_val; }
+
+ static const_key_reference
+ extract_key_imp(pair_type_const_reference r_val)
+ { return r_val.first; }
+ };
+ } // namespace detail
+ } // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp b/libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp
new file mode 100644
index 000000000..9903dfeb3
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/erase_if_fn.hpp
@@ -0,0 +1,85 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file erase_if_fn.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_ERASE_IF_FN_HPP
+#define PB_DS_REGRESSION_TEST_ERASE_IF_FN_HPP
+
+#include <functional>
+
+namespace __gnu_pbds
+{
+ namespace test
+ {
+ namespace detail
+ {
+ template<typename T>
+ struct regression_test_erase_if_fn
+ : public std::unary_function<T, bool>
+ {
+ private:
+ typedef const T& const_reference;
+
+ public:
+ bool
+ operator()(const_reference r_t) const
+ {
+ return (r_t.length() == 0 ||
+ static_cast<size_t>(*((r_t).begin())) % 2 == 1);
+ }
+ };
+
+ template<typename Hd, class Tl>
+ struct regression_test_erase_if_fn<std::pair<Hd, Tl> >
+ : public std::unary_function<std::pair<Hd, Tl>, bool>
+ {
+ private:
+ typedef const std::pair<Hd, Tl>& const_reference;
+ typedef regression_test_erase_if_fn<Hd> hd_erase_if_fn;
+ typedef regression_test_erase_if_fn<Tl> tl_erase_if_fn;
+
+ public:
+ bool
+ operator()(const_reference r_t) const
+ {
+ return (hd_erase_if_fn()(r_t.first) && tl_erase_if_fn()(r_t.second));
+ }
+ };
+ } // namespace detail
+ } // namespace test
+} // namespace __gnu_pbds
+
+#endif
diff --git a/libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp
new file mode 100644
index 000000000..f55dbbc99
--- /dev/null
+++ b/libstdc++-v3/testsuite/util/regression/trait/priority_queue/trait.hpp
@@ -0,0 +1,82 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file trait.hpp
+ * Contains traits for a random regression test
+ * for a specific container type.
+ */
+
+#ifndef PB_DS_REGRESSION_TEST_TRAIT_HPP
+#define PB_DS_REGRESSION_TEST_TRAIT_HPP
+
+#include <regression/trait/erase_if_fn.hpp>
+
+namespace __gnu_pbds
+{
+ namespace test
+ {
+ namespace detail
+ {
+ template<typename Cntnr>
+ struct regression_test_traits
+ {
+ typedef typename Cntnr::value_type value_type;
+ typedef typename Cntnr::const_reference const_reference;
+ typedef __gnu_pbds::test::native_priority_queue<std::string, true> native_type;
+ typedef typename native_type::value_type native_value_type;
+
+ template<typename T>
+ struct erase_if_fn : public regression_test_erase_if_fn<T>
+ { };
+
+ template<typename Gen>
+ static value_type
+ generate_value(Gen& r_gen, size_t max)
+ { return basic_type(r_gen, max); }
+
+ static native_value_type
+ native_value(const_reference r_val)
+ { return native_value_type(r_val); }
+
+ static bool
+ cmp(const_reference r_val, const native_value_type& r_native_val)
+ { return val_to_string(r_val) == r_native_val; }
+
+ static std::string
+ val_to_string(const_reference r_val)
+ { return std::string(r_val); }
+ };
+ } // namespace detail
+ } // namespace test
+} // namespace __gnu_pbds
+
+#endif