Google Git
Sign in
gnu / gcc / a6d3012b274f38b20e2a57162106f625746af6c6 / . / libstdc++-v3 / testsuite / util / regression / rand / assoc / container_rand_regression_test.tcc
blob: 2da91082329af240ac17965ce23760b294334bf2 [file] [log] [blame]
// -*- C++ -*-
// Copyright (C) 2005-2021 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_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_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::point_const_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_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(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);
key_const_reference r_k = test_traits::extract_key(v);
typename cntnr::point_const_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::key_const_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_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::key_const_reference test_key_const_reference;
typedef typename Cntnr::key_pointer test_key_pointer;
typedef typename Cntnr::key_const_pointer test_key_const_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::mapped_const_reference test_mapped_const_reference;
typedef typename Cntnr::mapped_pointer test_mapped_pointer;
typedef typename Cntnr::mapped_const_pointer test_mapped_const_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::point_const_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::node_const_iterator test_node_const_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::access_traits 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::access_traits& r_t = m_p_c->get_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
};
typedef __gnu_pbds::detail::integral_constant<int, split_join> __true_type;
return split_join_imp(__true_type());
}
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::point_const_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::point_const_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::point_const_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::point_const_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::point_const_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::point_const_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::point_const_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::point_const_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