libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.tcc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2020 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file container_rand_regression_test.tcc
  34  * Contains a random regression test for a specific container type.
  35  */
  36
  37 #ifndef PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
  38 #define PB_DS_CONTAINER_RAND_REGRESSION_TEST_TCC
  39
  40 // Constructors/Destructors.
  41 PB_DS_CLASS_T_DEC
  42 PB_DS_CLASS_C_DEC::
  43 container_rand_regression_test(unsigned long seed, size_t n, size_t m,
  44                                double tp, double ip, double ep, double cp,
  45                                double mp, bool disp)
  46 : m_seed((seed == 0) ? twister_rand_gen::get_time_determined_seed() : seed),
  47   m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_ep(ep), m_cp(cp), m_mp(mp),
  48   m_disp(disp), m_p_c(0)
  49 { }
  50
  51 PB_DS_CLASS_T_DEC
  52 PB_DS_CLASS_C_DEC::
  53 ~container_rand_regression_test()
  54 { }
  55
  56 PB_DS_CLASS_T_DEC
  57 bool
  58 PB_DS_CLASS_C_DEC::
  59 default_constructor()
  60 {
  61   PB_DS_TRACE("default_constructor");
  62   bool done = true;
  63   m_alloc.set_probability(m_tp);
  64
  65   try
  66     {
  67       m_p_c = new Cntnr;
  68     }
  69   catch(__gnu_cxx::forced_error&)
  70     {
  71       done = false;
  72     }
  73
  74   if (m_p_c)
  75     PB_DS_COND_COMPARE(*m_p_c, m_native_c);
  76   return done;
  77 }
  78
  79 PB_DS_CLASS_T_DEC
  80 void
  81 PB_DS_CLASS_C_DEC::
  82 swap()
  83 {
  84   PB_DS_TRACE("swap");
  85   m_alloc.set_probability(0);
  86   Cntnr* p_c = new Cntnr;
  87   m_alloc.set_probability(1);
  88   p_c->swap(*m_p_c);
  89   std::swap(p_c, m_p_c);
  90   delete p_c;
  91   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
  92 }
  93
  94 PB_DS_CLASS_T_DEC
  95 bool
  96 PB_DS_CLASS_C_DEC::
  97 copy_constructor()
  98 {
  99   PB_DS_TRACE("copy_constructor");
 100   bool done = true;
 101   Cntnr* p_c = 0;
 102   m_alloc.set_probability(m_tp);
 103   typename alloc_t::group_adjustor adjust(m_p_c->size());
 104
 105   try
 106     {
 107       p_c = new Cntnr(*m_p_c);
 108       std::swap(p_c, m_p_c);
 109     }
 110   catch(__gnu_cxx::forced_error&)
 111     {
 112       done = false;
 113     }
 114
 115   delete p_c;
 116   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 117   return done;
 118 }
 119
 120 PB_DS_CLASS_T_DEC
 121 bool
 122 PB_DS_CLASS_C_DEC::
 123 assignment_operator()
 124 {
 125   PB_DS_TRACE("assignment operator");
 126   bool done = true;
 127   Cntnr* p_c = 0;
 128   m_alloc.set_probability(m_tp);
 129   typename alloc_t::group_adjustor adjust(m_p_c->size());
 130
 131   try
 132     {
 133       p_c = new Cntnr();
 134       *p_c = *m_p_c;
 135       std::swap(p_c, m_p_c);
 136     }
 137   catch(__gnu_cxx::forced_error&)
 138     {
 139       done = false;
 140     }
 141
 142   delete p_c;
 143   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 144   return done;
 145 }
 146
 147 PB_DS_CLASS_T_DEC
 148 bool
 149 PB_DS_CLASS_C_DEC::
 150 it_constructor()
 151 {
 152   PB_DS_TRACE("it_constructor");
 153   return it_constructor_imp(typename Cntnr::container_category());
 154 }
 155
 156 PB_DS_CLASS_T_DEC
 157 bool
 158 PB_DS_CLASS_C_DEC::
 159 it_constructor_imp(__gnu_pbds::cc_hash_tag)
 160 {
 161   bool done = true;
 162   Cntnr* p_c = 0;
 163   m_alloc.set_probability(m_tp);
 164   typename alloc_t::group_adjustor adjust(m_p_c->size());
 165
 166   try
 167     {
 168       switch(get_next_sub_op(8))
 169         {
 170         case 0:
 171           p_c = new Cntnr(m_p_c->get_hash_fn());
 172           m_native_c.clear();
 173           break;
 174         case 1:
 175           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
 176           m_native_c.clear();
 177           break;
 178         case 2:
 179           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
 180                           m_p_c->get_comb_hash_fn());
 181           m_native_c.clear();
 182           break;
 183         case 3:
 184           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
 185                           m_p_c->get_comb_hash_fn(),
 186                           m_p_c->get_resize_policy());
 187           m_native_c.clear();
 188           break;
 189         case 4:
 190           p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
 191           break;
 192         case 5:
 193           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
 194           break;
 195         case 6:
 196           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 197                           m_p_c->get_eq_fn());
 198           break;
 199         case 7:
 200           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 201                           m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn());
 202           break;
 203         case 8:
 204           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 205                           m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn(),
 206                           m_p_c->get_resize_policy());
 207           break;
 208         default:
 209           PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 210         };
 211       std::swap(p_c, m_p_c);
 212     }
 213   catch (__gnu_cxx::forced_error&)
 214     {
 215       done = false;
 216     }
 217
 218   delete p_c;
 219   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 220   return done;
 221 }
 222
 223 PB_DS_CLASS_T_DEC
 224 bool
 225 PB_DS_CLASS_C_DEC::
 226 it_constructor_imp(__gnu_pbds::gp_hash_tag)
 227 {
 228   bool done = true;
 229   Cntnr* p_c = 0;
 230   m_alloc.set_probability(m_tp);
 231   typename alloc_t::group_adjustor adjust(m_p_c->size());
 232
 233   try
 234     {
 235       switch(get_next_sub_op(11))
 236         {
 237         case 0:
 238           p_c = new Cntnr(m_p_c->get_hash_fn());
 239           m_native_c.clear();
 240           break;
 241         case 1:
 242           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
 243           m_native_c.clear();
 244           break;
 245         case 2:
 246           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
 247                           m_p_c->get_comb_probe_fn());
 248           m_native_c.clear();
 249           break;
 250         case 3:
 251           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
 252                           m_p_c->get_comb_probe_fn());
 253           m_native_c.clear();
 254           break;
 255         case 4:
 256           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
 257                           m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn());
 258           m_native_c.clear();
 259           break;
 260         case 5:
 261           p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
 262                           m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn(),
 263                           m_p_c->get_resize_policy());
 264           m_native_c.clear();
 265           break;
 266         case 6:
 267           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
 268           break;
 269         case 7:
 270           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 271                           m_p_c->get_eq_fn());
 272           break;
 273         case 8:
 274           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 275                           m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
 276           break;
 277         case 9:
 278           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 279                           m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
 280           break;
 281         case 10:
 282           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 283                           m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
 284                           m_p_c->get_probe_fn());
 285           break;
 286         case 11:
 287           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
 288                           m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
 289                           m_p_c->get_probe_fn(), m_p_c->get_resize_policy());
 290           break;
 291         default:
 292           PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 293         };
 294       std::swap(p_c, m_p_c);
 295     }
 296   catch (__gnu_cxx::forced_error&)
 297     {
 298       done = false;
 299     }
 300
 301   delete p_c;
 302   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 303   return done;
 304 }
 305
 306 PB_DS_CLASS_T_DEC
 307 bool
 308 PB_DS_CLASS_C_DEC::
 309 it_constructor_imp(__gnu_pbds::tree_tag)
 310 {
 311   bool done = true;
 312   Cntnr* p_c = 0;
 313   m_alloc.set_probability(m_tp);
 314   typename alloc_t::group_adjustor adjust(m_p_c->size());
 315
 316   try
 317     {
 318       switch(get_next_sub_op(2))
 319         {
 320         case 0:
 321           p_c = new Cntnr(m_p_c->get_cmp_fn());
 322           m_native_c.clear();
 323           break;
 324         case 1:
 325           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn());
 326           break;
 327         default:
 328           PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 329         };
 330       std::swap(p_c, m_p_c);
 331     }
 332   catch (__gnu_cxx::forced_error&)
 333     {
 334       done = false;
 335     }
 336
 337   delete p_c;
 338   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 339   return done;
 340 }
 341
 342 PB_DS_CLASS_T_DEC
 343 bool
 344 PB_DS_CLASS_C_DEC::
 345 it_constructor_imp(__gnu_pbds::list_update_tag)
 346 {
 347   bool done = true;
 348   Cntnr* p_c = 0;
 349   m_alloc.set_probability(m_tp);
 350   typename alloc_t::group_adjustor adjust(m_p_c->size());
 351
 352   try
 353     {
 354       p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
 355       std::swap(p_c, m_p_c);
 356     }
 357   catch (__gnu_cxx::forced_error&)
 358     {
 359       done = false;
 360     }
 361
 362   delete p_c;
 363   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 364   return done;
 365 }
 366
 367 PB_DS_CLASS_T_DEC
 368 bool
 369 PB_DS_CLASS_C_DEC::
 370 it_constructor_imp(__gnu_pbds::pat_trie_tag)
 371 {
 372   bool done = true;
 373   Cntnr* p_c = 0;
 374   m_alloc.set_probability(m_tp);
 375   typename alloc_t::group_adjustor adjust(m_p_c->size());
 376
 377   try
 378     {
 379       switch(get_next_sub_op(2))
 380         {
 381         case 0:
 382           p_c = new Cntnr(m_p_c->get_access_traits());
 383           m_native_c.clear();
 384           break;
 385         case 1:
 386           p_c = new Cntnr(m_p_c->begin(), m_p_c->end(),
 387                           m_p_c->get_access_traits());
 388           break;
 389         default:
 390           PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 391         };
 392
 393       std::swap(p_c, m_p_c);
 394     }
 395   catch (__gnu_cxx::forced_error&)
 396     {
 397       done = false;
 398     }
 399
 400   delete p_c;
 401   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
 402   return done;
 403 }
 404
 405 // Cmp.
 406 PB_DS_CLASS_T_DEC
 407 void
 408 PB_DS_CLASS_C_DEC::
 409 cmp(const Cntnr& r_c, const native_type& r_native_c,
 410     const std::string& r_call_fn)
 411 {
 412   m_alloc.set_probability(1);
 413   const size_t size = r_c.size();
 414   const size_t native_size = r_native_c.size();
 415   PB_DS_THROW_IF_FAILED(size == native_size,
 416                         size << " " << native_size, &r_c, &r_native_c);
 417
 418   const bool empty = r_c.empty();
 419   const bool native_empty = r_native_c.empty();
 420   PB_DS_THROW_IF_FAILED(empty == native_empty,
 421                         empty << " " << native_empty, &r_c, &r_native_c);
 422
 423   try
 424     {
 425       basic_cmp_(r_c, r_native_c);
 426       cmp_(r_c, r_native_c);
 427     }
 428   catch(...)
 429     {
 430       PB_DS_THROW_IF_FAILED(false, "call-fn: " + r_call_fn, &r_c, &r_native_c);
 431     }
 432 }
 433
 434 PB_DS_CLASS_T_DEC
 435 void
 436 PB_DS_CLASS_C_DEC::
 437 basic_cmp_(const Cntnr& r_c, const native_type& r_native_c)
 438 {
 439   PB_DS_SET_DESTRUCT_PRINT
 440
 441   if (static_cast<size_t>(std::distance(r_c.begin(), r_c.end())) != r_c.size())
 442     PB_DS_THROW_IF_FAILED(false,
 443                           static_cast<unsigned long>(std::distance(r_c.begin(), r_c.end())) << " " << static_cast<unsigned long>(r_c.size()), &r_c, &r_native_c);
 444
 445   typename native_type::const_iterator it = r_native_c.begin();
 446   while (it != r_native_c.end())
 447     {
 448       typename native_type::key_type native_key = test_traits::extract_native_key(*it);
 449
 450       m_alloc.set_probability(0);
 451       const key_type k = native_key;
 452       m_alloc.set_probability(1);
 453       typename cntnr::point_const_iterator found_it = r_c.find(k);
 454       PB_DS_THROW_IF_FAILED(found_it != r_c.end(),
 455                             test_traits::native_val_to_string(*it),
 456                             &r_c, &r_native_c);
 457
 458       if (!test_traits::cmp(*found_it, * it))
 459         PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c);
 460
 461       ++it;
 462     }
 463   PB_DS_CANCEL_DESTRUCT_PRINT
 464 }
 465
 466 PB_DS_CLASS_T_DEC
 467 void
 468 PB_DS_CLASS_C_DEC::
 469 cmp_(const Cntnr& r_c, const native_type& r_native_c)
 470 {
 471   enum
 472     {
 473       order_preserving = container_traits::order_preserving,
 474       back_order_preserving = container_traits::order_preserving
 475       &&
 476       !__gnu_pbds::detail::is_same<
 477       typename std::iterator_traits<
 478       typename cntnr::const_iterator>::iterator_category,
 479       std::forward_iterator_tag>::value,
 480       reverse_iteration = container_traits::reverse_iteration,
 481       order_statistics = test_traits::order_statistics,
 482       prefix_search = test_traits::prefix_search,
 483       has_mapped = !__gnu_pbds::detail::is_same<
 484       typename Cntnr::mapped_type,
 485       __gnu_pbds::null_type>::value
 486     };
 487
 488   order_preserving_cmp_imp(r_c, r_native_c,
 489                            __gnu_pbds::detail::integral_constant<int,order_preserving>());
 490
 491   back_order_preserving_cmp_imp(r_c, r_native_c,
 492                                 __gnu_pbds::detail::integral_constant<int,back_order_preserving>());
 493
 494   order_statistics_cmp_imp(r_c, r_native_c,
 495                            __gnu_pbds::detail::integral_constant<int,order_statistics>());
 496
 497   prefix_search_cmp_imp(r_c, r_native_c,
 498                         __gnu_pbds::detail::integral_constant<int,prefix_search>());
 499
 500   reverse_iteration_cmp_imp(r_c, r_native_c,
 501                             __gnu_pbds::detail::integral_constant<int,reverse_iteration>());
 502
 503   lower_bound_cmp_imp(r_c, r_native_c,
 504                       __gnu_pbds::detail::integral_constant<int,order_preserving>());
 505
 506   upper_bound_cmp_imp(r_c, r_native_c,
 507                       __gnu_pbds::detail::integral_constant<int,order_preserving>());
 508 }
 509
 510 PB_DS_CLASS_T_DEC
 511 void
 512 PB_DS_CLASS_C_DEC::
 513 order_preserving_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 514 { }
 515
 516 PB_DS_CLASS_T_DEC
 517 void
 518 PB_DS_CLASS_C_DEC::
 519 order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 520 {
 521   PB_DS_SET_DESTRUCT_PRINT
 522
 523     typename cntnr::const_iterator b = r_c.begin();
 524   typename cntnr::const_iterator e = r_c.end();
 525
 526   typename native_type::const_iterator native_b = r_native_c.begin();
 527   typename native_type::const_iterator native_e = r_native_c.end();
 528
 529   try
 530     {
 531       it_cmp_imp(b, e, native_b, native_e);
 532     }
 533   catch(...)
 534     {
 535       PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
 536     }
 537
 538   try
 539     {
 540       back_it_cmp_imp(b, e, native_b, native_e);
 541     }
 542   catch(...)
 543     {
 544       PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
 545     }
 546
 547   PB_DS_CANCEL_DESTRUCT_PRINT
 548 }
 549
 550 PB_DS_CLASS_T_DEC
 551 void
 552 PB_DS_CLASS_C_DEC::
 553 back_order_preserving_cmp_imp(const Cntnr&, const native_type&,
 554                                     __gnu_pbds::detail::false_type)
 555 { }
 556
 557 PB_DS_CLASS_T_DEC
 558 void
 559 PB_DS_CLASS_C_DEC::
 560 back_order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c,
 561                               __gnu_pbds::detail::true_type)
 562 {
 563   PB_DS_SET_DESTRUCT_PRINT
 564   typename cntnr::const_iterator b = r_c.begin();
 565   typename cntnr::const_iterator e = r_c.end();
 566   typename native_type::const_iterator native_b = r_native_c.begin();
 567   typename native_type::const_iterator native_e = r_native_c.end();
 568   it_cmp_imp(b, e, native_b, native_e);
 569   PB_DS_CANCEL_DESTRUCT_PRINT
 570 }
 571
 572 PB_DS_CLASS_T_DEC
 573 void
 574 PB_DS_CLASS_C_DEC::
 575 reverse_iteration_cmp_imp(const Cntnr&, const native_type&,
 576                           __gnu_pbds::detail::false_type)
 577 { }
 578
 579 PB_DS_CLASS_T_DEC
 580 void
 581 PB_DS_CLASS_C_DEC::
 582 reverse_iteration_cmp_imp(const Cntnr& r_c, const native_type&r_native_c, __gnu_pbds::detail::true_type)
 583 {
 584   PB_DS_SET_DESTRUCT_PRINT
 585
 586     typename cntnr::const_reverse_iterator b = r_c.rbegin();
 587   typename cntnr::const_reverse_iterator e = r_c.rend();
 588
 589   typename native_type::const_reverse_iterator native_b = r_native_c.rbegin();
 590   typename native_type::const_reverse_iterator native_e = r_native_c.rend();
 591
 592   try
 593     {
 594       it_cmp_imp(b, e, native_b, native_e);
 595     }
 596   catch(...)
 597     {
 598       PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
 599     }
 600
 601   try
 602     {
 603       back_it_cmp_imp(b, e, native_b, native_e);
 604     }
 605   catch(...)
 606     {
 607       PB_DS_THROW_IF_FAILED(false, "", &r_c, &r_native_c)
 608     }
 609
 610   PB_DS_CANCEL_DESTRUCT_PRINT
 611 }
 612
 613 PB_DS_CLASS_T_DEC
 614 void
 615 PB_DS_CLASS_C_DEC::
 616 order_statistics_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 617 { }
 618
 619 PB_DS_CLASS_T_DEC
 620 void
 621 PB_DS_CLASS_C_DEC::
 622 order_statistics_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 623 {
 624   {
 625     m_alloc.set_probability(0);
 626     const key_type k = test_traits::generate_key(m_g, m_m);
 627     m_alloc.set_probability(1);
 628     const size_type order = r_c.order_of_key(k);
 629     const size_type native_order = std::distance(r_native_c.begin(),
 630                                                  r_native_c.lower_bound(test_traits::native_key(k)));
 631
 632     PB_DS_THROW_IF_FAILED(order == native_order,
 633                           test_traits::key_to_string(k) << " " <<
 634                           static_cast<unsigned long>(order) << " " <<
 635                           static_cast<unsigned long>(native_order),
 636                           &r_c,
 637                           &r_native_c);
 638   }
 639
 640   const size_type rand_ord =
 641     static_cast<size_t>(m_g.get_unsigned_long(0,
 642                                               2 * static_cast<unsigned long>(m_m)));
 643
 644   typename cntnr::const_iterator it = r_c.find_by_order(rand_ord);
 645   typename native_type::const_iterator native_it = r_native_c.begin();
 646   std::advance(native_it, std::min(rand_ord, r_native_c.size()));
 647   if (it == r_c.end()&&  native_it != r_native_c.end())
 648     PB_DS_THROW_IF_FAILED(false,
 649                           static_cast<unsigned long>(rand_ord),
 650                           m_p_c,
 651                           &m_native_c);
 652
 653   if (it != r_c.end()&&  native_it == r_native_c.end())
 654     PB_DS_THROW_IF_FAILED(false,
 655                           static_cast<unsigned long>(rand_ord),
 656                           m_p_c,
 657                           &m_native_c);
 658
 659   if (it != r_c.end()&&     native_it != r_native_c.end())
 660     PB_DS_THROW_IF_FAILED(test_traits::cmp(*it, * native_it),
 661                           static_cast<unsigned long>(rand_ord),
 662                           m_p_c,
 663                           &m_native_c);
 664 }
 665
 666 PB_DS_CLASS_T_DEC
 667 void
 668 PB_DS_CLASS_C_DEC::
 669 prefix_search_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 670 { }
 671
 672 PB_DS_CLASS_T_DEC
 673 void
 674 PB_DS_CLASS_C_DEC::
 675 prefix_search_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 676 {
 677   PB_DS_SET_DESTRUCT_PRINT
 678   m_alloc.set_probability(0);
 679   const key_type k = test_traits::generate_key(m_g, m_m);
 680   m_alloc.set_probability(1);
 681   try
 682     {
 683       typedef
 684         std::pair<typename Cntnr::const_iterator, typename Cntnr::const_iterator>
 685         pref_ret_t;
 686
 687       const pref_ret_t pref_ret = r_c.prefix_range(k);
 688
 689       typename native_type::const_iterator native_start_it = r_native_c.begin();
 690
 691       while (native_start_it != r_native_c.end() &&
 692              !test_traits::prefix_match(k,
 693                                         test_traits::extract_native_key(*native_start_it)))
 694         ++native_start_it;
 695
 696       typename native_type::const_iterator native_end_it =
 697         native_start_it;
 698
 699       do
 700         {
 701           if (native_end_it != r_native_c.end())
 702             ++native_end_it;
 703         }
 704       while (native_end_it != r_native_c.end() &&
 705              test_traits::prefix_match(k,
 706                                        test_traits::extract_native_key(*native_end_it)));
 707
 708       it_cmp_imp(pref_ret.first, pref_ret.second, native_start_it, native_end_it);
 709     }
 710   catch(...)
 711     {
 712       PB_DS_THROW_IF_FAILED(false, "prefix key " << k, &r_c, &r_native_c);
 713     }
 714
 715   PB_DS_CANCEL_DESTRUCT_PRINT
 716 }
 717
 718 PB_DS_CLASS_T_DEC
 719 template<typename Const_It, class Const_Native_It>
 720 void
 721 PB_DS_CLASS_C_DEC::
 722 it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b,
 723            Const_Native_It native_e)
 724 {
 725   PB_DS_SET_DESTRUCT_PRINT
 726
 727   if (std::distance(b, e) != std::distance(native_b, native_e))
 728     {
 729       const size_t dist = std::distance(b, e);
 730       const size_t native_dist = std::distance(native_b, native_e);
 731       PB_DS_THROW_IF_FAILED(false,
 732                             static_cast<unsigned long>(dist) << " "
 733                             << static_cast<unsigned long>(native_dist),
 734                             m_p_c, &m_native_c);
 735     }
 736
 737   while (b != e)
 738     {
 739       PB_DS_THROW_IF_FAILED(native_b != native_e, "", m_p_c, &m_native_c);
 740
 741       if (!test_traits::cmp(*b, * native_b))
 742         PB_DS_THROW_IF_FAILED(false,
 743                               test_traits::val_to_string(*b) << " " <<
 744                               test_traits::val_to_string(*native_b),
 745                               m_p_c, &m_native_c);
 746
 747       ++b;
 748       ++native_b;
 749     }
 750
 751   PB_DS_THROW_IF_FAILED(native_b == native_e, "", m_p_c, &m_native_c);
 752   PB_DS_CANCEL_DESTRUCT_PRINT
 753 }
 754
 755 PB_DS_CLASS_T_DEC
 756 template<typename Const_It, class Const_Native_It>
 757 void
 758 PB_DS_CLASS_C_DEC::
 759 back_it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b,
 760                 Const_Native_It native_e)
 761 {
 762   PB_DS_SET_DESTRUCT_PRINT
 763   while (b != e)
 764   {
 765     PB_DS_THROW_IF_FAILED(native_b != native_e,
 766                           test_traits::val_to_string(*native_e),
 767                           m_p_c, &m_native_c);
 768
 769     --e;
 770     --native_e;
 771
 772     PB_DS_THROW_IF_FAILED(test_traits::cmp(*e, * native_e),
 773                           test_traits::val_to_string(*e) <<
 774                           test_traits::val_to_string(*native_e),
 775                           m_p_c, &m_native_c);
 776   }
 777
 778   PB_DS_THROW_IF_FAILED(native_b == native_e,
 779                         test_traits::val_to_string(*native_e),
 780                         m_p_c, &m_native_c);
 781
 782   PB_DS_CANCEL_DESTRUCT_PRINT
 783 }
 784
 785 PB_DS_CLASS_T_DEC
 786 void
 787 PB_DS_CLASS_C_DEC::
 788 lower_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 789 { }
 790
 791 PB_DS_CLASS_T_DEC
 792 void
 793 PB_DS_CLASS_C_DEC::
 794 lower_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 795 {
 796   PB_DS_SET_DESTRUCT_PRINT
 797   m_alloc.set_probability(0);
 798   const key_type k = test_traits::generate_key(m_g, m_m);
 799   m_alloc.set_probability(1);
 800   typename cntnr::const_iterator it = r_c.lower_bound(k);
 801   typename native_type::key_type native_k = test_traits::native_key(k);
 802   typename native_type::const_iterator native_it = r_native_c.lower_bound(native_k);
 803
 804   if (it != r_c.end() && native_it == r_native_c.end())
 805     PB_DS_THROW_IF_FAILED("",
 806                           "it: " + test_traits::val_to_string(*it) + "\n\n",
 807                           &r_c, &r_native_c);
 808
 809   if (it == r_c.end() && native_it != r_native_c.end())
 810     PB_DS_THROW_IF_FAILED("",
 811                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 812                           &r_c, &r_native_c);
 813
 814   if (it != r_c.end() && !test_traits::cmp(*it, * native_it))
 815     PB_DS_THROW_IF_FAILED(false,
 816                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 817                           "it: " + test_traits::val_to_string(*it) + "\n\n" +
 818                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 819                           &r_c, &r_native_c);
 820
 821   PB_DS_CANCEL_DESTRUCT_PRINT
 822 }
 823
 824 PB_DS_CLASS_T_DEC
 825 void
 826 PB_DS_CLASS_C_DEC::
 827 upper_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 828 { }
 829
 830 PB_DS_CLASS_T_DEC
 831 void
 832 PB_DS_CLASS_C_DEC::
 833 upper_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 834 {
 835   PB_DS_SET_DESTRUCT_PRINT
 836   m_alloc.set_probability(0);
 837   const key_type k = test_traits::generate_key(m_g, m_m);
 838   m_alloc.set_probability(1);
 839   typename cntnr::const_iterator it =  r_c.upper_bound(k);
 840   typename native_type::key_type native_k = test_traits::native_key(k);
 841   typename native_type::const_iterator native_it = r_native_c.upper_bound(native_k);
 842
 843   if (it == r_c.end() && native_it != r_native_c.end())
 844     PB_DS_THROW_IF_FAILED(false,
 845                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 846                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 847                           &r_c, &r_native_c);
 848
 849   if (it != r_c.end() && native_it == r_native_c.end())
 850     PB_DS_THROW_IF_FAILED(false,
 851                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 852                           "it: " + test_traits::val_to_string(*it) + "\n\n",
 853                           &r_c, &r_native_c);
 854
 855   if (it != r_c.end() && !test_traits::cmp(*it, * native_it))
 856     PB_DS_THROW_IF_FAILED(false,
 857                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 858                           "it: " + test_traits::val_to_string(*it) + "\n\n" +
 859                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 860                           &r_c, &r_native_c);
 861
 862   PB_DS_CANCEL_DESTRUCT_PRINT
 863 }
 864
 865 // Operators.
 866 PB_DS_CLASS_T_DEC
 867 void
 868 PB_DS_CLASS_C_DEC::
 869 operator()()
 870 {
 871   typedef xml_result_set_regression_formatter formatter_type;
 872   formatter_type* p_fmt = 0;
 873
 874   if (m_disp)
 875     p_fmt = new formatter_type(string_form<Cntnr>::name(),
 876                                string_form<Cntnr>::desc());
 877
 878   m_g.init(m_seed);
 879
 880   // Track allocation from this point only.
 881   const size_t memory_label = 775;
 882   m_alloc.seed(m_seed);
 883   m_alloc.set_label(memory_label);
 884
 885   prog_bar pb(m_n, std::cout, m_disp);
 886   m_i = 0;
 887
 888   try
 889     {
 890       for (m_i = 0; m_i < m_n; ++m_i)
 891         {
 892           PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i));
 893           allocator_type::set_label(m_i);
 894           switch (m_i)
 895             {
 896             case 0:
 897               PB_DS_RUN_MTHD(default_constructor);
 898               break;
 899             case 1:
 900               defs();
 901               break;
 902             case 2:
 903               policy_access();
 904               break;
 905             case 3:
 906               it_copy();
 907               break;
 908             case 4:
 909               it_assign();
 910               break;
 911             case 5:
 912               rev_it_copy();
 913               break;
 914             case 6:
 915               rev_it_assign();
 916               break;
 917             default:
 918               switch(get_next_op())
 919                 {
 920                 case insert_op:
 921                   switch(get_next_sub_op(2))
 922                     {
 923                     case 0:
 924                       PB_DS_RUN_MTHD(insert)
 925                         break;
 926                     case 1:
 927                       PB_DS_RUN_MTHD(subscript)
 928                         break;
 929                     default:
 930                       PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 931                     }
 932                   break;
 933                 case erase_op:
 934                   switch(get_next_sub_op(4))
 935                     {
 936                     case 0:
 937                       PB_DS_RUN_MTHD(erase)
 938                         break;
 939                     case 1:
 940                       PB_DS_RUN_MTHD(erase_if)
 941                         break;
 942                     case 2:
 943                       PB_DS_RUN_MTHD(erase_it)
 944                         break;
 945                     case 3:
 946                       PB_DS_RUN_MTHD(erase_rev_it)
 947                         break;
 948                     default:
 949                       PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 950                     }
 951                   break;
 952                 case clear_op:
 953                   PB_DS_RUN_MTHD(clear)
 954                     break;
 955                 case other_op:
 956                   switch(get_next_sub_op(8))
 957                     {
 958                     case 0:
 959                       swap();
 960                       break;
 961                     case 1:
 962                       PB_DS_RUN_MTHD(copy_constructor)
 963                       break;
 964                     case 2:
 965                       PB_DS_RUN_MTHD(it_constructor)
 966                       break;
 967                     case 3:
 968                       PB_DS_RUN_MTHD(assignment_operator)
 969                       break;
 970                     case 4:
 971                       PB_DS_RUN_MTHD(split_join)
 972                       break;
 973                     case 5:
 974                       resize();
 975                       break;
 976                     case 6:
 977                       get_set_load();
 978                       break;
 979                     case 7:
 980                       get_set_loads();
 981                       break;
 982                     default:
 983                       PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 984                     }
 985                   break;
 986                 default:
 987                   PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
 988                 };
 989             }
 990
 991           pb.inc();
 992         }
 993     }
 994   catch (...)
 995     {
 996       std::cerr << "Failed at index " << static_cast<unsigned long>(m_i)
 997                 << std::endl;
 998       delete m_p_c;
 999       throw;
1000     }
1001
1002   // Clean up, then check for allocation by special label, set above.
1003   delete m_p_c;
1004
1005   try
1006     { m_alloc.check(memory_label); }
1007   catch (...)
1008     {
1009       std::cerr << "detected leaks!" << std::endl;
1010       std::cerr << m_alloc << std::endl;
1011       PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
1012     }
1013
1014   // Reset throw probability.
1015   m_alloc.set_probability(0);
1016
1017   if (m_disp)
1018     {
1019       std::cout << std::endl;
1020       delete p_fmt;
1021     }
1022 }
1023
1024 PB_DS_CLASS_T_DEC
1025 typename PB_DS_CLASS_C_DEC::op
1026 PB_DS_CLASS_C_DEC::
1027 get_next_op()
1028 {
1029   const double prob = m_g.get_prob();
1030   if (prob < m_ip)
1031     return insert_op;
1032
1033   if (prob < m_ip + m_ep)
1034     return erase_op;
1035
1036   if (prob < m_ip + m_ep + m_cp)
1037     return clear_op;
1038
1039   PB_DS_THROW_IF_FAILED(prob <= 1, prob, m_p_c, &m_native_c);
1040   return other_op;
1041 }
1042
1043 PB_DS_CLASS_T_DEC
1044 size_t
1045 PB_DS_CLASS_C_DEC::
1046 get_next_sub_op(size_t max)
1047 {
1048   const double p = m_g.get_prob();
1049   const double delta = 1 / static_cast<double>(max);
1050   size_t i = 0;
1051   while (true)
1052     if (p <= (i + 1) * delta)
1053       {
1054         PB_DS_THROW_IF_FAILED(i < max, i << " " << max, m_p_c, &m_native_c);
1055         return i;
1056       }
1057     else
1058       ++i;
1059 }
1060
1061 // Insert.
1062 PB_DS_CLASS_T_DEC
1063 bool
1064 PB_DS_CLASS_C_DEC::
1065 insert()
1066 {
1067   PB_DS_TRACE("insert");
1068   bool done = true;
1069   PB_DS_SET_DESTRUCT_PRINT
1070   try
1071     {
1072       m_alloc.set_probability(0);
1073       value_type v = test_traits::generate_value(m_g, m_m);
1074       m_alloc.set_probability(m_tp);
1075       key_const_reference r_k = test_traits::extract_key(v);
1076       typename cntnr::point_const_iterator found_it = m_p_c->find(r_k);
1077       const bool existed = (found_it != m_p_c->end());
1078       const std::pair<typename cntnr::point_iterator, bool> ins_ret = m_p_c->insert(v);
1079
1080       if (ins_ret.second)
1081         {
1082           PB_DS_THROW_IF_FAILED(!existed, "", m_p_c, &m_native_c);
1083         }
1084       else
1085         {
1086           PB_DS_THROW_IF_FAILED(existed, "", m_p_c, &m_native_c);
1087           PB_DS_THROW_IF_FAILED(found_it == ins_ret.first, "", m_p_c, &m_native_c);
1088         }
1089       m_native_c.insert(test_traits::native_value(v));
1090     }
1091   catch(__gnu_cxx::forced_error&)
1092     {
1093       done = false;
1094     }
1095   catch(__gnu_pbds::insert_error&)
1096     {
1097       PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
1098     }
1099
1100   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1101   PB_DS_CANCEL_DESTRUCT_PRINT
1102   return done;
1103 }
1104
1105 // Subscript.
1106 PB_DS_CLASS_T_DEC
1107 bool
1108 PB_DS_CLASS_C_DEC::
1109 subscript()
1110 {
1111   PB_DS_TRACE("subscript");
1112
1113   enum
1114     {
1115       no_data = __gnu_pbds::detail::is_same<
1116       typename Cntnr::key_const_reference,
1117       typename Cntnr::const_reference>::value
1118     };
1119
1120   return (subscript_imp(__gnu_pbds::detail::integral_constant<int,no_data>()));
1121 }
1122
1123 PB_DS_CLASS_T_DEC
1124 bool
1125 PB_DS_CLASS_C_DEC::
1126 subscript_imp(__gnu_pbds::detail::false_type)
1127 {
1128   bool done = true;
1129   PB_DS_SET_DESTRUCT_PRINT
1130
1131   try
1132     {
1133       m_alloc.set_probability(0);
1134       value_type v = test_traits::generate_value(m_g, m_m);
1135
1136       m_alloc.set_probability(m_tp);
1137       (*m_p_c)[v.first] = v.second;
1138
1139       m_native_c[test_traits::native_value(v).first] =
1140         test_traits::native_value(v).second;
1141     }
1142   catch(__gnu_cxx::forced_error&)
1143     {
1144       done = false;
1145     }
1146
1147   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1148   PB_DS_CANCEL_DESTRUCT_PRINT
1149   return done;
1150 }
1151
1152 PB_DS_CLASS_T_DEC
1153 bool
1154 PB_DS_CLASS_C_DEC::
1155 subscript_imp(__gnu_pbds::detail::true_type)
1156 {
1157   bool done = true;
1158   PB_DS_SET_DESTRUCT_PRINT
1159   try
1160     {
1161       m_alloc.set_probability(0);
1162       value_type v = test_traits::generate_value(m_g, m_m);
1163       m_alloc.set_probability(m_tp);
1164       (*m_p_c)[v] = __gnu_pbds::null_type();
1165       m_native_c.insert(test_traits::native_value(v));
1166     }
1167   catch(__gnu_cxx::forced_error&)
1168     {
1169       done = false;
1170     }
1171
1172   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1173   PB_DS_CANCEL_DESTRUCT_PRINT
1174   return done;
1175 }
1176
1177 // Clear.
1178 PB_DS_CLASS_T_DEC
1179 bool
1180 PB_DS_CLASS_C_DEC::
1181 clear()
1182 {
1183   m_p_c->clear();
1184   m_native_c.clear();
1185   return true;
1186 }
1187
1188
1189 // Erase.
1190 PB_DS_CLASS_T_DEC
1191 bool
1192 PB_DS_CLASS_C_DEC::
1193 erase()
1194 {
1195   PB_DS_TRACE("erase");
1196   bool done = true;
1197   PB_DS_SET_DESTRUCT_PRINT
1198   m_alloc.set_probability(0);
1199   const key_type k = test_traits::generate_key(m_g, m_m);
1200   m_alloc.set_probability(m_tp);
1201
1202   try
1203     {
1204       const bool cntnd = m_p_c->find(k) != m_p_c->end();
1205       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);
1206
1207       const bool ersd = m_p_c->erase(k);
1208       const bool native_ersd = m_native_c.erase(test_traits::native_key(k)) != 0;
1209
1210       PB_DS_THROW_IF_FAILED(ersd == native_ersd, ersd << " " << native_ersd,
1211                             m_p_c, &m_native_c);
1212
1213       PB_DS_THROW_IF_FAILED(m_p_c->find(k) == m_p_c->end(), "",
1214                             m_p_c, &m_native_c);
1215     }
1216   catch(__gnu_cxx::forced_error&)
1217     {
1218       done = false;
1219
1220       PB_DS_THROW_IF_FAILED(            container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c);
1221     }
1222
1223   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1224   PB_DS_CANCEL_DESTRUCT_PRINT
1225   return done;
1226 }
1227
1228 PB_DS_CLASS_T_DEC
1229 bool
1230 PB_DS_CLASS_C_DEC::
1231 erase_if()
1232 {
1233   PB_DS_TRACE("erase_if");
1234   bool done = true;
1235   PB_DS_SET_DESTRUCT_PRINT
1236
1237   try
1238     {
1239       typedef
1240         typename std::iterator_traits<typename cntnr::iterator>::reference
1241         it_const_reference;
1242
1243       typedef
1244         typename test_traits::template erase_if_fn<value_type>
1245         erase_if_fn_t;
1246
1247       m_alloc.set_probability(m_tp);
1248
1249       const size_t ersd = m_p_c->erase_if(erase_if_fn_t());
1250       const size_t native_ersd = test_traits::erase_if(m_native_c);
1251       PB_DS_THROW_IF_FAILED(ersd == native_ersd,
1252                             ersd << " " << native_ersd, m_p_c, &m_native_c);
1253     }
1254   catch(__gnu_cxx::forced_error&)
1255     {
1256       done = false;
1257       PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw,
1258                             container_traits::erase_can_throw,
1259                             m_p_c, &m_native_c);
1260     }
1261
1262   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1263   PB_DS_CANCEL_DESTRUCT_PRINT
1264   return done;
1265 }
1266
1267 PB_DS_CLASS_T_DEC
1268 bool
1269 PB_DS_CLASS_C_DEC::
1270 erase_it()
1271 {
1272   enum
1273     {
1274       erase_iterators = container_traits::order_preserving
1275     };
1276
1277   return (erase_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>()));
1278 }
1279
1280 PB_DS_CLASS_T_DEC
1281 bool
1282 PB_DS_CLASS_C_DEC::
1283 erase_it_imp(__gnu_pbds::detail::false_type)
1284 {
1285   return true;
1286 }
1287
1288 PB_DS_CLASS_T_DEC
1289 bool
1290 PB_DS_CLASS_C_DEC::
1291 erase_it_imp(__gnu_pbds::detail::true_type)
1292 {
1293   PB_DS_TRACE("erase_it");
1294   bool done = true;
1295   PB_DS_SET_DESTRUCT_PRINT
1296
1297   try
1298     {
1299       m_alloc.set_probability(0);
1300       const key_type k = test_traits::generate_key(m_g, m_m);
1301       m_alloc.set_probability(m_tp);
1302
1303       typename cntnr::iterator found_it = m_p_c->find(k);
1304
1305       typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k));
1306
1307       const bool found = found_it != m_p_c->end();
1308       const bool native_found = native_it != m_native_c.end();
1309
1310       PB_DS_THROW_IF_FAILED(
1311                             found == native_found,
1312                             found << " " <<    native_found,
1313                             m_p_c,
1314                             &m_native_c);
1315
1316       typename cntnr::const_iterator next_it = found_it;
1317       if (next_it != m_p_c->end())
1318         ++next_it;
1319
1320       typename cntnr::iterator next_ers_it = m_p_c->erase(found_it);
1321
1322       if (native_it != m_native_c.end())
1323         m_native_c.erase(native_it);
1324
1325       bool range_guarantee = __gnu_pbds::detail::is_same<
1326       typename container_traits::invalidation_guarantee,
1327         __gnu_pbds::range_invalidation_guarantee>::value ;
1328
1329       if (range_guarantee)
1330         PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c);
1331     }
1332   catch(__gnu_cxx::forced_error&)
1333     {
1334       done = false;
1335       PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw, container_traits::erase_can_throw, m_p_c, &m_native_c);
1336     }
1337
1338   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1339   PB_DS_CANCEL_DESTRUCT_PRINT
1340   return done;
1341 }
1342
1343 PB_DS_CLASS_T_DEC
1344 bool
1345 PB_DS_CLASS_C_DEC::
1346 erase_rev_it()
1347 {
1348   enum
1349     {
1350       erase_iterators = container_traits::order_preserving
1351                         && container_traits::reverse_iteration
1352     };
1353
1354   return (erase_rev_it_imp(__gnu_pbds::detail::integral_constant<int,erase_iterators>()));
1355 }
1356
1357 PB_DS_CLASS_T_DEC
1358 bool
1359 PB_DS_CLASS_C_DEC::
1360 erase_rev_it_imp(__gnu_pbds::detail::false_type)
1361 {
1362   return true;
1363 }
1364
1365 PB_DS_CLASS_T_DEC
1366 bool
1367 PB_DS_CLASS_C_DEC::
1368 erase_rev_it_imp(__gnu_pbds::detail::true_type)
1369 {
1370   PB_DS_TRACE("erase_rev_it");
1371   bool done = true;
1372   PB_DS_SET_DESTRUCT_PRINT
1373
1374   try
1375     {
1376       m_alloc.set_probability(0);
1377       const key_type k = test_traits::generate_key(m_g, m_m);
1378       m_alloc.set_probability(m_tp);
1379
1380       typename cntnr::iterator found_it = m_p_c->find(k);
1381       typename native_type::iterator native_it = m_native_c.find(test_traits::native_key(k));
1382
1383       typename cntnr::const_reverse_iterator next_it = found_it;
1384       if (next_it != m_p_c->end())
1385         ++next_it;
1386
1387       typename cntnr::reverse_iterator next_ers_it =
1388         m_p_c->erase((typename cntnr::reverse_iterator)found_it);
1389
1390       PB_DS_THROW_IF_FAILED(next_ers_it == next_it, "", m_p_c, &m_native_c);
1391
1392       if (native_it != m_native_c.end())
1393         m_native_c.erase(native_it);
1394     }
1395   catch(__gnu_cxx::forced_error&)
1396     {
1397       done = false;
1398       PB_DS_THROW_IF_FAILED(container_traits::erase_can_throw,
1399                             container_traits::erase_can_throw,
1400                             m_p_c, &m_native_c);
1401     }
1402
1403   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1404   PB_DS_CANCEL_DESTRUCT_PRINT
1405   return done;
1406 }
1407
1408 // Defs.
1409 PB_DS_CLASS_T_DEC
1410 void
1411 PB_DS_CLASS_C_DEC::
1412 defs()
1413 {
1414   // General container types.
1415   typedef typename Cntnr::size_type test_size_type;
1416   typedef typename Cntnr::difference_type difference_type;
1417
1418   key_defs();
1419   mapped_defs();
1420   value_defs();
1421   iterator_defs();
1422   node_iterator_defs(__gnu_pbds::detail::integral_constant<int,
1423                      container_traits::order_preserving>());
1424   policy_defs();
1425 }
1426
1427 PB_DS_CLASS_T_DEC
1428 void
1429 PB_DS_CLASS_C_DEC::
1430 key_defs()
1431 {
1432   typedef typename Cntnr::key_type test_key_type;
1433   typedef typename Cntnr::key_reference test_key_reference;
1434   typedef typename Cntnr::key_const_reference test_key_const_reference;
1435   typedef typename Cntnr::key_pointer test_key_pointer;
1436   typedef typename Cntnr::key_const_pointer test_key_const_pointer;
1437 }
1438
1439 PB_DS_CLASS_T_DEC
1440 void
1441 PB_DS_CLASS_C_DEC::
1442 mapped_defs()
1443 {
1444   typedef typename Cntnr::mapped_type test_mapped_type;
1445   typedef typename Cntnr::mapped_reference test_mapped_reference;
1446   typedef typename Cntnr::mapped_const_reference test_mapped_const_reference;
1447   typedef typename Cntnr::mapped_pointer test_mapped_pointer;
1448   typedef typename Cntnr::mapped_const_pointer test_mapped_const_pointer;
1449 }
1450
1451 PB_DS_CLASS_T_DEC
1452 void
1453 PB_DS_CLASS_C_DEC::
1454 value_defs()
1455 {
1456   typedef typename Cntnr::value_type test_value_type;
1457   typedef typename Cntnr::reference test_reference;
1458   typedef typename Cntnr::const_reference test_const_reference;
1459   typedef typename Cntnr::pointer test_pointer;
1460   typedef typename Cntnr::const_pointer test_const_pointer;
1461 }
1462
1463 PB_DS_CLASS_T_DEC
1464 void
1465 PB_DS_CLASS_C_DEC::
1466 ds_defs()
1467 {
1468   typedef __gnu_pbds::container_traits< Cntnr> test_container_traits;
1469
1470   typedef typename test_container_traits::container_category test_container_category;
1471
1472   typedef
1473     typename test_container_traits::invalidation_guarantee
1474     test_invalidation_guarantee;
1475
1476   enum
1477     {
1478       test_order_preserving = test_container_traits::order_preserving
1479     };
1480
1481   enum
1482     {
1483       test_erase_can_throw = test_container_traits::erase_can_throw
1484     };
1485 }
1486
1487 PB_DS_CLASS_T_DEC
1488 void
1489 PB_DS_CLASS_C_DEC::
1490 iterator_defs()
1491 {
1492   typedef typename Cntnr::point_iterator test_point_iterator;
1493   typedef typename Cntnr::point_const_iterator const_test_point_iterator;
1494   typedef typename Cntnr::iterator test_iterator;
1495   typedef typename Cntnr::const_iterator const_test_iterator;
1496 }
1497
1498 PB_DS_CLASS_T_DEC
1499 void
1500 PB_DS_CLASS_C_DEC::
1501 node_iterator_defs(__gnu_pbds::detail::false_type)
1502 { }
1503
1504 PB_DS_CLASS_T_DEC
1505 void
1506 PB_DS_CLASS_C_DEC::
1507 node_iterator_defs(__gnu_pbds::detail::true_type)
1508 {
1509   typedef typename Cntnr::node_iterator test_node_iterator;
1510   typedef typename Cntnr::node_const_iterator test_node_const_iterator;
1511 }
1512
1513 PB_DS_CLASS_T_DEC
1514 void
1515 PB_DS_CLASS_C_DEC::
1516 policy_defs()
1517 {
1518   typedef typename Cntnr::allocator_type test_allocator;
1519   policy_defs(typename Cntnr::container_category());
1520 }
1521
1522 PB_DS_CLASS_T_DEC
1523 void
1524 PB_DS_CLASS_C_DEC::
1525 policy_defs(__gnu_pbds::basic_hash_tag)
1526 {
1527   typedef typename Cntnr::hash_fn test_hash_fn;
1528   typedef typename Cntnr::eq_fn test_eq_fn;
1529   typedef typename Cntnr::resize_policy test_resize_policy;
1530 }
1531
1532 PB_DS_CLASS_T_DEC
1533 void
1534 PB_DS_CLASS_C_DEC::
1535 policy_defs(__gnu_pbds::cc_hash_tag)
1536 {
1537   policy_defs(__gnu_pbds::basic_hash_tag());
1538   typedef typename Cntnr::comb_hash_fn test_comb_hash_fn;
1539 }
1540
1541 PB_DS_CLASS_T_DEC
1542 void
1543 PB_DS_CLASS_C_DEC::
1544 policy_defs(__gnu_pbds::gp_hash_tag)
1545 {
1546   policy_defs(__gnu_pbds::basic_hash_tag());
1547   typedef typename Cntnr::comb_probe_fn test_comb_probe_fn;
1548   typedef typename Cntnr::probe_fn test_probe_fn;
1549 }
1550
1551 PB_DS_CLASS_T_DEC
1552 void
1553 PB_DS_CLASS_C_DEC::
1554 policy_defs(__gnu_pbds::tree_tag)
1555 {
1556   typedef typename Cntnr::cmp_fn test_cmp_fn;
1557   typedef typename Cntnr::node_update test_node_update;
1558 }
1559
1560 PB_DS_CLASS_T_DEC
1561 void
1562 PB_DS_CLASS_C_DEC::
1563 policy_defs(__gnu_pbds::list_update_tag)
1564 {
1565   typedef typename Cntnr::eq_fn test_eq_fn;
1566   typedef typename Cntnr::update_policy test_update_policy;
1567 }
1568
1569 PB_DS_CLASS_T_DEC
1570 void
1571 PB_DS_CLASS_C_DEC::
1572 policy_defs(__gnu_pbds::pat_trie_tag)
1573 {
1574   typedef typename Cntnr::access_traits access_traits;
1575 }
1576
1577
1578 // Policy Access.
1579 PB_DS_CLASS_T_DEC
1580 void
1581 PB_DS_CLASS_C_DEC::
1582 policy_access()
1583 {
1584   policy_access(typename Cntnr::container_category());
1585 }
1586
1587 PB_DS_CLASS_T_DEC
1588 void
1589 PB_DS_CLASS_C_DEC::
1590 policy_access(__gnu_pbds::basic_hash_tag)
1591 {
1592   {
1593     typename Cntnr::hash_fn& r_t = m_p_c->get_hash_fn();
1594     assert(&r_t);
1595   }
1596   {
1597     const typename Cntnr::hash_fn& r_t =((const Cntnr& )*m_p_c).get_hash_fn();
1598     assert(&r_t);
1599   }
1600
1601   {
1602     typename Cntnr::eq_fn& r_t = m_p_c->get_eq_fn();
1603     assert(&r_t);
1604   }
1605   {
1606     const typename Cntnr::eq_fn& r_t =((const Cntnr& )*m_p_c).get_eq_fn();
1607     assert(&r_t);
1608   }
1609
1610   {
1611     typename Cntnr::resize_policy& r_t = m_p_c->get_resize_policy();
1612     assert(&r_t);
1613   }
1614   {
1615     const typename Cntnr::resize_policy& r_t =((const Cntnr& )*m_p_c).get_resize_policy();
1616
1617     assert(&r_t);
1618   }
1619 }
1620
1621 PB_DS_CLASS_T_DEC
1622 void
1623 PB_DS_CLASS_C_DEC::
1624 policy_access(__gnu_pbds::cc_hash_tag)
1625 {
1626   policy_access(__gnu_pbds::basic_hash_tag());
1627
1628   {
1629     typename Cntnr::comb_hash_fn& r_t = m_p_c->get_comb_hash_fn();
1630     assert(&r_t);
1631   }
1632   {
1633     const typename Cntnr::comb_hash_fn& r_t =((const Cntnr& )*m_p_c).get_comb_hash_fn();
1634
1635     assert(&r_t);
1636   }
1637 }
1638
1639 PB_DS_CLASS_T_DEC
1640 void
1641 PB_DS_CLASS_C_DEC::
1642 policy_access(__gnu_pbds::gp_hash_tag)
1643 {
1644   policy_access(__gnu_pbds::basic_hash_tag());
1645
1646   {
1647     typename Cntnr::comb_probe_fn& r_t = m_p_c->get_comb_probe_fn();
1648     assert(&r_t);
1649   }
1650   {
1651     const typename Cntnr::comb_probe_fn& r_t =((const Cntnr& )*m_p_c).get_comb_probe_fn();
1652
1653     assert(&r_t);
1654   }
1655
1656   {
1657     typename Cntnr::probe_fn& r_t = m_p_c->get_probe_fn();
1658     assert(&r_t);
1659   }
1660   {
1661     const typename Cntnr::probe_fn& r_t =((const Cntnr& )*m_p_c).get_probe_fn();
1662     assert(&r_t);
1663   }
1664 }
1665
1666 PB_DS_CLASS_T_DEC
1667 void
1668 PB_DS_CLASS_C_DEC::
1669 policy_access(__gnu_pbds::tree_tag)
1670 {
1671   {
1672     typename Cntnr::cmp_fn& r_t = m_p_c->get_cmp_fn();
1673     assert(&r_t);
1674   }
1675
1676   {
1677     const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn();
1678     assert(&r_t);
1679   }
1680 }
1681
1682 PB_DS_CLASS_T_DEC
1683 void
1684 PB_DS_CLASS_C_DEC::
1685 policy_access(__gnu_pbds::list_update_tag)
1686 { }
1687
1688 PB_DS_CLASS_T_DEC
1689 void
1690 PB_DS_CLASS_C_DEC::
1691 policy_access(__gnu_pbds::pat_trie_tag)
1692 {
1693   typename Cntnr::access_traits& r_t = m_p_c->get_access_traits();
1694   assert(&r_t);
1695 }
1696
1697
1698 // Split/Join.
1699 PB_DS_CLASS_T_DEC
1700 bool
1701 PB_DS_CLASS_C_DEC::
1702 split_join()
1703 {
1704   enum
1705     {
1706       split_join = container_traits::order_preserving
1707     };
1708
1709   typedef __gnu_pbds::detail::integral_constant<int, split_join> __true_type;
1710   return split_join_imp(__true_type());
1711 }
1712
1713 PB_DS_CLASS_T_DEC
1714 bool
1715 PB_DS_CLASS_C_DEC::
1716 split_join_imp(__gnu_pbds::detail::false_type)
1717 {
1718   return true;
1719 }
1720
1721 PB_DS_CLASS_T_DEC
1722 bool
1723 PB_DS_CLASS_C_DEC::
1724 split_join_imp(__gnu_pbds::detail::true_type)
1725 {
1726   PB_DS_TRACE("split_join");
1727   bool done = true;
1728   PB_DS_SET_DESTRUCT_PRINT
1729
1730   try
1731     {
1732       m_alloc.set_probability(0);
1733       Cntnr lhs(*m_p_c);
1734       Cntnr rhs;
1735       native_type native_lhs(m_native_c);
1736       native_type native_rhs;
1737       const key_type k = test_traits::generate_key(m_g, m_m);
1738
1739       m_alloc.set_probability(m_tp);
1740       lhs.split(k, rhs);
1741
1742       typename native_type::const_iterator it =
1743         native_lhs.upper_bound(test_traits::native_key(k));
1744
1745       while (!native_lhs.empty()&&  it != native_lhs.end())
1746         {
1747           native_rhs.insert(*it);
1748           typename native_type::const_iterator next_it = it;
1749           ++next_it;
1750           native_lhs.erase(test_traits::extract_native_key(*it));
1751           it = next_it;
1752         }
1753
1754       PB_DS_COND_COMPARE(lhs, native_lhs);
1755       PB_DS_COND_COMPARE(rhs, native_rhs);
1756
1757       m_alloc.set_probability(m_tp);
1758
1759       if (m_g.get_prob() < 0.5)
1760         lhs.swap(rhs);
1761
1762       lhs.join(rhs);
1763       PB_DS_THROW_IF_FAILED(rhs.size() == 0, rhs.size(), m_p_c, &m_native_c);
1764       PB_DS_THROW_IF_FAILED(rhs.empty(), rhs.size(), m_p_c, &m_native_c);
1765       m_p_c->swap(lhs);
1766     }
1767   catch(__gnu_cxx::forced_error&)
1768     {
1769       done = false;
1770       PB_DS_THROW_IF_FAILED(container_traits::split_join_can_throw,
1771                             container_traits::split_join_can_throw,
1772                             m_p_c, &m_native_c);
1773     }
1774
1775   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1776   PB_DS_CANCEL_DESTRUCT_PRINT
1777   return done;
1778 }
1779
1780 // Iterator conversions.
1781 PB_DS_CLASS_T_DEC
1782 void
1783 PB_DS_CLASS_C_DEC::
1784 it_copy()
1785 {
1786   {
1787     typename cntnr::iterator it = m_p_c->end();
1788     typename cntnr::const_iterator const_it(it);
1789     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1790     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1791
1792     typename cntnr::point_const_iterator const_find_it(it);
1793     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1794     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1795
1796     typename cntnr::point_iterator find_it(it);
1797     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1798     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1799   }
1800
1801   {
1802     typename cntnr::const_iterator const_it = m_p_c->end();
1803     typename cntnr::point_const_iterator const_find_it(const_it);
1804     PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
1805     PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
1806   }
1807
1808   {
1809     typename cntnr::point_iterator find_it = m_p_c->end();
1810     typename cntnr::point_const_iterator const_find_it(find_it);
1811     PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
1812     PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
1813   }
1814 }
1815
1816 PB_DS_CLASS_T_DEC
1817 void
1818 PB_DS_CLASS_C_DEC::
1819 it_assign()
1820 {
1821   {
1822     typename cntnr::iterator it = m_p_c->end();
1823     typename cntnr::const_iterator const_it;
1824     const_it = it;
1825     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1826     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1827
1828     typename cntnr::point_const_iterator const_find_it;
1829     const_find_it = it;
1830     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1831     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1832
1833     typename cntnr::point_iterator find_it;
1834     find_it = it;
1835     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1836     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1837   }
1838
1839   {
1840     typename cntnr::const_iterator const_it = m_p_c->end();
1841     typename cntnr::point_const_iterator const_find_it;
1842     const_find_it = const_it;
1843     PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
1844     PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
1845   }
1846
1847   {
1848     typename cntnr::point_iterator find_it = m_p_c->end();
1849     typename cntnr::point_const_iterator const_find_it;
1850     const_find_it = find_it;
1851     PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
1852     PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
1853   }
1854 }
1855
1856 PB_DS_CLASS_T_DEC
1857 void
1858 PB_DS_CLASS_C_DEC::
1859 rev_it_copy()
1860 {
1861   enum
1862     {
1863       reverse_iteration = container_traits::reverse_iteration
1864     };
1865
1866   rev_it_copy_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
1867 }
1868
1869 PB_DS_CLASS_T_DEC
1870 void
1871 PB_DS_CLASS_C_DEC::
1872 rev_it_assign()
1873 {
1874   enum
1875     {
1876       reverse_iteration = container_traits::reverse_iteration
1877     };
1878
1879   rev_it_assign_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
1880 }
1881
1882 PB_DS_CLASS_T_DEC
1883 void
1884 PB_DS_CLASS_C_DEC::
1885 rev_it_copy_imp(__gnu_pbds::detail::false_type)
1886 { }
1887
1888 PB_DS_CLASS_T_DEC
1889 void
1890 PB_DS_CLASS_C_DEC::
1891 rev_it_copy_imp(__gnu_pbds::detail::true_type)
1892 {
1893   {
1894     typename cntnr::iterator it = m_p_c->end();
1895     typename cntnr::const_reverse_iterator const_it(it);
1896     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1897     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1898
1899     typename cntnr::point_const_iterator const_find_it(it);
1900     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1901     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1902
1903     typename cntnr::point_iterator find_it(it);
1904     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1905     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1906   }
1907 }
1908
1909 PB_DS_CLASS_T_DEC
1910 void
1911 PB_DS_CLASS_C_DEC::
1912 rev_it_assign_imp(__gnu_pbds::detail::false_type)
1913 { }
1914
1915 PB_DS_CLASS_T_DEC
1916 void
1917 PB_DS_CLASS_C_DEC::
1918 rev_it_assign_imp(__gnu_pbds::detail::true_type)
1919 {
1920   {
1921     typename cntnr::iterator it = m_p_c->end();
1922     typename cntnr::const_reverse_iterator const_it;
1923     const_it = it;
1924     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1925     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1926
1927     typename cntnr::point_const_iterator const_find_it;
1928     const_find_it = it;
1929     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1930     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1931
1932     typename cntnr::point_iterator find_it;
1933     find_it = it;
1934     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1935     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1936   }
1937 }
1938
1939 // Resize.
1940 PB_DS_CLASS_T_DEC
1941 bool
1942 PB_DS_CLASS_C_DEC::
1943 resize()
1944 {
1945   typedef __gnu_pbds::detail::integral_constant<int, test_traits::resize> resize_ind;
1946
1947   return resize_imp(resize_ind());
1948 }
1949
1950 PB_DS_CLASS_T_DEC
1951 bool
1952 PB_DS_CLASS_C_DEC::
1953 resize_imp(__gnu_pbds::detail::false_type)
1954 {
1955   return true;
1956 }
1957
1958 PB_DS_CLASS_T_DEC
1959 bool
1960 PB_DS_CLASS_C_DEC::
1961 resize_imp(__gnu_pbds::detail::true_type)
1962 {
1963   PB_DS_TRACE("resize");
1964   bool done = true;
1965   PB_DS_SET_DESTRUCT_PRINT
1966   const size_t old_size = m_p_c->get_actual_size();
1967
1968   try
1969     {
1970       enum
1971         {
1972           min_new_size = 200,
1973           max_new_size = 2000
1974         };
1975
1976       m_alloc.set_probability(m_tp);
1977       typename alloc_t::group_adjustor adjust(m_p_c->size());
1978       const size_t new_size = m_g.get_unsigned_long(min_new_size, max_new_size);
1979       m_p_c->resize(new_size);
1980       const size_t actual_new_size = m_p_c->get_actual_size();
1981       PB_DS_THROW_IF_FAILED(actual_new_size >= new_size,
1982                             actual_new_size << " " << new_size,
1983                             m_p_c, &m_native_c);
1984     }
1985   catch(...)
1986     {
1987       PB_DS_THROW_IF_FAILED(m_p_c->get_actual_size() == old_size,
1988                             m_p_c->get_actual_size() << " " << old_size,
1989                             m_p_c, &m_native_c);
1990
1991       done = false;
1992     }
1993
1994   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1995   PB_DS_CANCEL_DESTRUCT_PRINT
1996   return done;
1997 }
1998
1999
2000 // Get/Set load.
2001 PB_DS_CLASS_T_DEC
2002 void
2003 PB_DS_CLASS_C_DEC::
2004 get_set_load()
2005 {
2006   typedef
2007     __gnu_pbds::detail::integral_constant<int, test_traits::get_set_load>
2008     get_set_load_ind;
2009
2010   get_set_load_imp(get_set_load_ind());
2011 }
2012
2013 PB_DS_CLASS_T_DEC
2014 void
2015 PB_DS_CLASS_C_DEC::
2016 get_set_load_imp(__gnu_pbds::detail::false_type)
2017 { }
2018
2019 PB_DS_CLASS_T_DEC
2020 void
2021 PB_DS_CLASS_C_DEC::
2022 get_set_load_imp(__gnu_pbds::detail::true_type)
2023 {
2024   PB_DS_TRACE("get_set_load");
2025   PB_DS_SET_DESTRUCT_PRINT
2026   m_p_c->get_load();
2027   m_alloc.set_probability(1);
2028   typename alloc_t::group_adjustor adjust(m_p_c->size());
2029   const float min_load = static_cast<float>(0.05);
2030   const float max_load = static_cast<float>(0.9);
2031
2032   const float new_load = static_cast<float>(m_g.get_prob() * (max_load - min_load) + min_load);
2033
2034   m_p_c->set_load(new_load);
2035   PB_DS_THROW_IF_FAILED(m_p_c->get_load() == new_load, "", m_p_c, &m_native_c);
2036   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
2037   PB_DS_CANCEL_DESTRUCT_PRINT
2038 }
2039
2040
2041 // Get/Set loads.
2042 PB_DS_CLASS_T_DEC
2043 bool
2044 PB_DS_CLASS_C_DEC::
2045 get_set_loads()
2046 {
2047   typedef
2048     __gnu_pbds::detail::integral_constant<int, test_traits::get_set_loads>
2049     get_set_loads_ind;
2050
2051   return get_set_loads_imp(get_set_loads_ind());
2052 }
2053
2054 PB_DS_CLASS_T_DEC
2055 bool
2056 PB_DS_CLASS_C_DEC::
2057 get_set_loads_imp(__gnu_pbds::detail::false_type)
2058 {
2059   return true;
2060 }
2061
2062 PB_DS_CLASS_T_DEC
2063 bool
2064 PB_DS_CLASS_C_DEC::
2065 get_set_loads_imp(__gnu_pbds::detail::true_type)
2066 {
2067   PB_DS_TRACE("get_set_loads");
2068   bool done = true;
2069   PB_DS_SET_DESTRUCT_PRINT
2070   const std::pair<float, float> old_loads = m_p_c->get_loads();
2071
2072   try
2073     {
2074       m_alloc.set_probability(m_tp);
2075
2076       typename alloc_t::group_adjustor adjust(m_p_c->size());
2077
2078       const float min_min_load = static_cast<float>(0.05);
2079       const float max_min_load = static_cast<float>(0.2);
2080
2081       const float new_min_load =
2082         static_cast<float>(m_g.get_prob()*  (max_min_load - min_min_load) +
2083                            min_min_load);
2084
2085       const float new_max_load = static_cast<float>(new_min_load*  2.5);
2086       PB_DS_THROW_IF_FAILED(new_max_load < 1, new_max_load, m_p_c, &m_native_c);
2087       m_p_c->set_loads(std::make_pair(new_min_load, new_max_load));
2088     }
2089   catch(...)
2090     {
2091       PB_DS_THROW_IF_FAILED(old_loads == m_p_c->get_loads(),
2092                             old_loads.first << " " << old_loads.second << " " <<
2093                             m_p_c->get_loads().first << " " <<
2094                             m_p_c->get_loads().second,
2095                             m_p_c, &m_native_c);
2096
2097       done = false;
2098     }
2099
2100   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
2101   PB_DS_CANCEL_DESTRUCT_PRINT
2102   return done;
2103 }
2104
2105 // Diagnostics.
2106 PB_DS_CLASS_T_DEC
2107 void
2108 PB_DS_CLASS_C_DEC::
2109 print_container(const native_type& r_cnt, std::ostream& r_os) const
2110 {
2111   m_alloc.set_probability(0);
2112   typename native_type::const_iterator it = r_cnt.begin();
2113   while (it != r_cnt.end())
2114     {
2115       r_os << test_traits::val_to_string(*it) + "\n";
2116       ++it;
2117     }
2118 }
2119
2120 PB_DS_CLASS_T_DEC
2121 void
2122 PB_DS_CLASS_C_DEC::
2123 print_container(const cntnr& r_cnt, std::ostream& r_os) const
2124 {
2125   m_alloc.set_probability(0);
2126   typename cntnr::const_iterator it = r_cnt.begin();
2127   while (it != r_cnt.end())
2128     {
2129       r_os << test_traits::val_to_string(*it) + "\n";
2130       ++it;
2131     }
2132 }
2133
2134 #endif