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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2008, 2009 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(NULL)
  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_exception_error&)
  70     {
  71       done = false;
  72     }
  73
  74   if (m_p_c != NULL)
  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 = NULL;
 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_exception_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 = NULL;
 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_exception_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 = NULL;
 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_exception_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 = NULL;
 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_exception_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 = NULL;
 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_exception_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 = NULL;
 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_exception_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 = NULL;
 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_e_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_e_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_exception_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::const_point_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_mapped_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 = NULL;
 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_allocated(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       const_key_reference r_k = test_traits::extract_key(v);
1076       typename cntnr::const_point_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_exception_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::const_key_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_exception_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_mapped_type();
1165       m_native_c.insert(test_traits::native_value(v));
1166     }
1167   catch(__gnu_cxx::forced_exception_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_exception_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_exception_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_exception_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_exception_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::const_key_reference test_const_key_reference;
1435   typedef typename Cntnr::key_pointer test_key_pointer;
1436   typedef typename Cntnr::const_key_pointer test_const_key_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::const_mapped_reference test_const_mapped_reference;
1447   typedef typename Cntnr::mapped_pointer test_mapped_pointer;
1448   typedef typename Cntnr::const_mapped_pointer test_const_mapped_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::const_point_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::const_node_iterator test_const_node_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::e_access_traits e_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 != NULL);
1595   }
1596   {
1597     const typename Cntnr::hash_fn& r_t =((const Cntnr& )*m_p_c).get_hash_fn();
1598     assert(&r_t != NULL);
1599   }
1600
1601   {
1602     typename Cntnr::eq_fn& r_t = m_p_c->get_eq_fn();
1603     assert(&r_t != NULL);
1604   }
1605   {
1606     const typename Cntnr::eq_fn& r_t =((const Cntnr& )*m_p_c).get_eq_fn();
1607     assert(&r_t != NULL);
1608   }
1609
1610   {
1611     typename Cntnr::resize_policy& r_t = m_p_c->get_resize_policy();
1612     assert(&r_t != NULL);
1613   }
1614   {
1615     const typename Cntnr::resize_policy& r_t =((const Cntnr& )*m_p_c).get_resize_policy();
1616
1617     assert(&r_t != NULL);
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 != NULL);
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 != NULL);
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 != NULL);
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 != NULL);
1654   }
1655
1656   {
1657     typename Cntnr::probe_fn& r_t = m_p_c->get_probe_fn();
1658     assert(&r_t != NULL);
1659   }
1660   {
1661     const typename Cntnr::probe_fn& r_t =((const Cntnr& )*m_p_c).get_probe_fn();
1662     assert(&r_t != NULL);
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 != NULL);
1674   }
1675
1676   {
1677     const typename Cntnr::cmp_fn& r_t =((const Cntnr& )*m_p_c).get_cmp_fn();
1678     assert(&r_t != NULL);
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::e_access_traits& r_t = m_p_c->get_e_access_traits();
1694   assert(&r_t != NULL);
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   return (split_join_imp(__gnu_pbds::detail::integral_constant<int,split_join>()));
1710 }
1711
1712 PB_DS_CLASS_T_DEC
1713 bool
1714 PB_DS_CLASS_C_DEC::
1715 split_join_imp(__gnu_pbds::detail::false_type)
1716 {
1717   return true;
1718 }
1719
1720 PB_DS_CLASS_T_DEC
1721 bool
1722 PB_DS_CLASS_C_DEC::
1723 split_join_imp(__gnu_pbds::detail::true_type)
1724 {
1725   PB_DS_TRACE("split_join");
1726   bool done = true;
1727   PB_DS_SET_DESTRUCT_PRINT
1728
1729   try
1730     {
1731       m_alloc.set_probability(0);
1732       Cntnr lhs(*m_p_c);
1733       Cntnr rhs;
1734       native_type native_lhs(m_native_c);
1735       native_type native_rhs;
1736       const key_type k = test_traits::generate_key(m_g, m_m);
1737
1738       m_alloc.set_probability(m_tp);
1739       lhs.split(k, rhs);
1740
1741       typename native_type::const_iterator it =
1742         native_lhs.upper_bound(test_traits::native_key(k));
1743
1744       while (!native_lhs.empty()&&  it != native_lhs.end())
1745         {
1746           native_rhs.insert(*it);
1747           typename native_type::const_iterator next_it = it;
1748           ++next_it;
1749           native_lhs.erase(test_traits::extract_native_key(*it));
1750           it = next_it;
1751         }
1752
1753       PB_DS_COND_COMPARE(lhs, native_lhs);
1754       PB_DS_COND_COMPARE(rhs, native_rhs);
1755
1756       m_alloc.set_probability(m_tp);
1757
1758       if (m_g.get_prob() < 0.5)
1759         lhs.swap(rhs);
1760
1761       lhs.join(rhs);
1762       PB_DS_THROW_IF_FAILED(rhs.size() == 0, rhs.size(), m_p_c, &m_native_c);
1763       PB_DS_THROW_IF_FAILED(rhs.empty(), rhs.size(), m_p_c, &m_native_c);
1764       m_p_c->swap(lhs);
1765     }
1766   catch(__gnu_cxx::forced_exception_error& )
1767     {
1768       done = false;
1769       PB_DS_THROW_IF_FAILED(container_traits::split_join_can_throw,
1770                             container_traits::split_join_can_throw,
1771                             m_p_c, &m_native_c);
1772     }
1773
1774   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1775   PB_DS_CANCEL_DESTRUCT_PRINT
1776   return done;
1777 }
1778
1779 // Iterator conversions.
1780 PB_DS_CLASS_T_DEC
1781 void
1782 PB_DS_CLASS_C_DEC::
1783 it_copy()
1784 {
1785   {
1786     typename cntnr::iterator it = m_p_c->end();
1787     typename cntnr::const_iterator const_it(it);
1788     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1789     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1790
1791     typename cntnr::const_point_iterator const_find_it(it);
1792     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1793     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1794
1795     typename cntnr::point_iterator find_it(it);
1796     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1797     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1798   }
1799
1800   {
1801     typename cntnr::const_iterator const_it = m_p_c->end();
1802     typename cntnr::const_point_iterator const_find_it(const_it);
1803     PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
1804     PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
1805   }
1806
1807   {
1808     typename cntnr::point_iterator find_it = m_p_c->end();
1809     typename cntnr::const_point_iterator const_find_it(find_it);
1810     PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
1811     PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
1812   }
1813 }
1814
1815 PB_DS_CLASS_T_DEC
1816 void
1817 PB_DS_CLASS_C_DEC::
1818 it_assign()
1819 {
1820   {
1821     typename cntnr::iterator it = m_p_c->end();
1822     typename cntnr::const_iterator const_it;
1823     const_it = it;
1824     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1825     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1826
1827     typename cntnr::const_point_iterator const_find_it;
1828     const_find_it = it;
1829     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1830     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1831
1832     typename cntnr::point_iterator find_it;
1833     find_it = it;
1834     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1835     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1836   }
1837
1838   {
1839     typename cntnr::const_iterator const_it = m_p_c->end();
1840     typename cntnr::const_point_iterator const_find_it;
1841     const_find_it = const_it;
1842     PB_DS_THROW_IF_FAILED(const_find_it == const_it, "", m_p_c, &m_native_c);
1843     PB_DS_THROW_IF_FAILED(!(const_find_it != const_it), "", m_p_c, &m_native_c);
1844   }
1845
1846   {
1847     typename cntnr::point_iterator find_it = m_p_c->end();
1848     typename cntnr::const_point_iterator const_find_it;
1849     const_find_it = find_it;
1850     PB_DS_THROW_IF_FAILED(find_it == const_find_it, "", m_p_c, &m_native_c);
1851     PB_DS_THROW_IF_FAILED(!(find_it != const_find_it), "", m_p_c, &m_native_c);
1852   }
1853 }
1854
1855 PB_DS_CLASS_T_DEC
1856 void
1857 PB_DS_CLASS_C_DEC::
1858 rev_it_copy()
1859 {
1860   enum
1861     {
1862       reverse_iteration = container_traits::reverse_iteration
1863     };
1864
1865   rev_it_copy_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
1866 }
1867
1868 PB_DS_CLASS_T_DEC
1869 void
1870 PB_DS_CLASS_C_DEC::
1871 rev_it_assign()
1872 {
1873   enum
1874     {
1875       reverse_iteration = container_traits::reverse_iteration
1876     };
1877
1878   rev_it_assign_imp(__gnu_pbds::detail::integral_constant<int,reverse_iteration>());
1879 }
1880
1881 PB_DS_CLASS_T_DEC
1882 void
1883 PB_DS_CLASS_C_DEC::
1884 rev_it_copy_imp(__gnu_pbds::detail::false_type)
1885 { }
1886
1887 PB_DS_CLASS_T_DEC
1888 void
1889 PB_DS_CLASS_C_DEC::
1890 rev_it_copy_imp(__gnu_pbds::detail::true_type)
1891 {
1892   {
1893     typename cntnr::iterator it = m_p_c->end();
1894     typename cntnr::const_reverse_iterator const_it(it);
1895     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1896     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1897
1898     typename cntnr::const_point_iterator const_find_it(it);
1899     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1900     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1901
1902     typename cntnr::point_iterator find_it(it);
1903     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1904     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1905   }
1906 }
1907
1908 PB_DS_CLASS_T_DEC
1909 void
1910 PB_DS_CLASS_C_DEC::
1911 rev_it_assign_imp(__gnu_pbds::detail::false_type)
1912 { }
1913
1914 PB_DS_CLASS_T_DEC
1915 void
1916 PB_DS_CLASS_C_DEC::
1917 rev_it_assign_imp(__gnu_pbds::detail::true_type)
1918 {
1919   {
1920     typename cntnr::iterator it = m_p_c->end();
1921     typename cntnr::const_reverse_iterator const_it;
1922     const_it = it;
1923     PB_DS_THROW_IF_FAILED(const_it == it, "", m_p_c, &m_native_c);
1924     PB_DS_THROW_IF_FAILED(!(const_it != it), "", m_p_c, &m_native_c);
1925
1926     typename cntnr::const_point_iterator const_find_it;
1927     const_find_it = it;
1928     PB_DS_THROW_IF_FAILED(const_find_it == it, "", m_p_c, &m_native_c);
1929     PB_DS_THROW_IF_FAILED(!(const_find_it != it), "", m_p_c, &m_native_c);
1930
1931     typename cntnr::point_iterator find_it;
1932     find_it = it;
1933     PB_DS_THROW_IF_FAILED(find_it == it, "", m_p_c, &m_native_c);
1934     PB_DS_THROW_IF_FAILED(!(find_it != it), "", m_p_c, &m_native_c);
1935   }
1936 }
1937
1938 // Resize.
1939 PB_DS_CLASS_T_DEC
1940 bool
1941 PB_DS_CLASS_C_DEC::
1942 resize()
1943 {
1944   typedef __gnu_pbds::detail::integral_constant<int, test_traits::resize> resize_ind;
1945
1946   return resize_imp(resize_ind());
1947 }
1948
1949 PB_DS_CLASS_T_DEC
1950 bool
1951 PB_DS_CLASS_C_DEC::
1952 resize_imp(__gnu_pbds::detail::false_type)
1953 {
1954   return true;
1955 }
1956
1957 PB_DS_CLASS_T_DEC
1958 bool
1959 PB_DS_CLASS_C_DEC::
1960 resize_imp(__gnu_pbds::detail::true_type)
1961 {
1962   PB_DS_TRACE("resize");
1963   bool done = true;
1964   PB_DS_SET_DESTRUCT_PRINT
1965   const size_t old_size = m_p_c->get_actual_size();
1966
1967   try
1968     {
1969       enum
1970         {
1971           min_new_size = 200,
1972           max_new_size = 2000
1973         };
1974
1975       m_alloc.set_probability(m_tp);
1976       typename alloc_t::group_adjustor adjust(m_p_c->size());
1977       const size_t new_size = m_g.get_unsigned_long(min_new_size, max_new_size);
1978       m_p_c->resize(new_size);
1979       const size_t actual_new_size = m_p_c->get_actual_size();
1980       PB_DS_THROW_IF_FAILED(actual_new_size >= new_size,
1981                             actual_new_size << " " << new_size,
1982                             m_p_c, &m_native_c);
1983     }
1984   catch(...)
1985     {
1986       PB_DS_THROW_IF_FAILED(m_p_c->get_actual_size() == old_size,
1987                             m_p_c->get_actual_size() << " " << old_size,
1988                             m_p_c, &m_native_c);
1989
1990       done = false;
1991     }
1992
1993   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
1994   PB_DS_CANCEL_DESTRUCT_PRINT
1995   return done;
1996 }
1997
1998
1999 // Get/Set load.
2000 PB_DS_CLASS_T_DEC
2001 void
2002 PB_DS_CLASS_C_DEC::
2003 get_set_load()
2004 {
2005   typedef
2006     __gnu_pbds::detail::integral_constant<int, test_traits::get_set_load>
2007     get_set_load_ind;
2008
2009   get_set_load_imp(get_set_load_ind());
2010 }
2011
2012 PB_DS_CLASS_T_DEC
2013 void
2014 PB_DS_CLASS_C_DEC::
2015 get_set_load_imp(__gnu_pbds::detail::false_type)
2016 { }
2017
2018 PB_DS_CLASS_T_DEC
2019 void
2020 PB_DS_CLASS_C_DEC::
2021 get_set_load_imp(__gnu_pbds::detail::true_type)
2022 {
2023   PB_DS_TRACE("get_set_load");
2024   PB_DS_SET_DESTRUCT_PRINT
2025   m_p_c->get_load();
2026   m_alloc.set_probability(1);
2027   typename alloc_t::group_adjustor adjust(m_p_c->size());
2028   const float min_load = static_cast<float>(0.05);
2029   const float max_load = static_cast<float>(0.9);
2030
2031   const float new_load = static_cast<float>(m_g.get_prob() * (max_load - min_load) + min_load);
2032
2033   m_p_c->set_load(new_load);
2034   PB_DS_THROW_IF_FAILED(m_p_c->get_load() == new_load, "", m_p_c, &m_native_c);
2035   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
2036   PB_DS_CANCEL_DESTRUCT_PRINT
2037 }
2038
2039
2040 // Get/Set loads.
2041 PB_DS_CLASS_T_DEC
2042 bool
2043 PB_DS_CLASS_C_DEC::
2044 get_set_loads()
2045 {
2046   typedef
2047     __gnu_pbds::detail::integral_constant<int, test_traits::get_set_loads>
2048     get_set_loads_ind;
2049
2050   return get_set_loads_imp(get_set_loads_ind());
2051 }
2052
2053 PB_DS_CLASS_T_DEC
2054 bool
2055 PB_DS_CLASS_C_DEC::
2056 get_set_loads_imp(__gnu_pbds::detail::false_type)
2057 {
2058   return true;
2059 }
2060
2061 PB_DS_CLASS_T_DEC
2062 bool
2063 PB_DS_CLASS_C_DEC::
2064 get_set_loads_imp(__gnu_pbds::detail::true_type)
2065 {
2066   PB_DS_TRACE("get_set_loads");
2067   bool done = true;
2068   PB_DS_SET_DESTRUCT_PRINT
2069   const std::pair<float, float> old_loads = m_p_c->get_loads();
2070
2071   try
2072     {
2073       m_alloc.set_probability(m_tp);
2074
2075       typename alloc_t::group_adjustor adjust(m_p_c->size());
2076
2077       const float min_min_load = static_cast<float>(0.05);
2078       const float max_min_load = static_cast<float>(0.2);
2079
2080       const float new_min_load =
2081         static_cast<float>(m_g.get_prob()*  (max_min_load - min_min_load) +
2082                            min_min_load);
2083
2084       const float new_max_load = static_cast<float>(new_min_load*  2.5);
2085       PB_DS_THROW_IF_FAILED(new_max_load < 1, new_max_load, m_p_c, &m_native_c);
2086       m_p_c->set_loads(std::make_pair(new_min_load, new_max_load));
2087     }
2088   catch(...)
2089     {
2090       PB_DS_THROW_IF_FAILED(old_loads == m_p_c->get_loads(),
2091                             old_loads.first << " " << old_loads.second << " " <<
2092                             m_p_c->get_loads().first << " " <<
2093                             m_p_c->get_loads().second,
2094                             m_p_c, &m_native_c);
2095
2096       done = false;
2097     }
2098
2099   PB_DS_COND_COMPARE(*m_p_c, m_native_c);
2100   PB_DS_CANCEL_DESTRUCT_PRINT
2101   return done;
2102 }
2103
2104 // Diagnostics.
2105 PB_DS_CLASS_T_DEC
2106 void
2107 PB_DS_CLASS_C_DEC::
2108 print_container(const native_type& r_cnt, std::ostream& r_os) const
2109 {
2110   m_alloc.set_probability(0);
2111   typename native_type::const_iterator it = r_cnt.begin();
2112   while (it != r_cnt.end())
2113     {
2114       r_os << test_traits::val_to_string(*it) + "\n";
2115       ++it;
2116     }
2117 }
2118
2119 PB_DS_CLASS_T_DEC
2120 void
2121 PB_DS_CLASS_C_DEC::
2122 print_container(const cntnr& r_cnt, std::ostream& r_os) const
2123 {
2124   m_alloc.set_probability(0);
2125   typename cntnr::const_iterator it = r_cnt.begin();
2126   while (it != r_cnt.end())
2127     {
2128       r_os << test_traits::val_to_string(*it) + "\n";
2129       ++it;
2130     }
2131 }
2132
2133 #endif