libstdc++-v3/testsuite/util/regression/rand/assoc/detail/cmp_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file cmp_fn_imps.hpp
  44  * Containsert a random regression test for a specific container type.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 void
  49 PB_DS_CLASS_C_DEC::
  50 cmp(const Cntnr& r_c, const native_type& r_native_c, const std::string& r_call_fn)
  51 {
  52   m_alloc.set_throw_prob(1);
  53
  54   const size_t size = r_c.size();
  55   const size_t native_size = r_native_c.size();
  56
  57   PB_DS_THROW_IF_FAILED(
  58                         size == native_size,
  59                         static_cast<unsigned long>(size) << " " <<
  60                         static_cast<unsigned long>(native_size),
  61                         & r_c,
  62                         & r_native_c);
  63
  64   const bool empty = r_c.empty();
  65   const bool native_empty = r_native_c.empty();
  66
  67   PB_DS_THROW_IF_FAILED(
  68                         empty == native_empty,
  69                         empty << " " << native_empty,
  70                         & r_c,
  71                         & r_native_c);
  72
  73   try
  74     {
  75       basic_cmp_(r_c, r_native_c);
  76
  77       cmp_(r_c, r_native_c);
  78     }
  79   catch(...)
  80     {
  81       PB_DS_THROW_IF_FAILED(            false, "call-fn: " + r_call_fn, & r_c, & r_native_c);
  82     }
  83 }
  84
  85 PB_DS_CLASS_T_DEC
  86 void
  87 PB_DS_CLASS_C_DEC::
  88 basic_cmp_(const Cntnr& r_c, const native_type& r_native_c)
  89 {
  90   PB_DS_SET_DESTRUCT_PRINT
  91
  92     if (static_cast<size_t>(std::distance(r_c.begin(), r_c.end())) !=
  93         r_c.size())
  94       PB_DS_THROW_IF_FAILED(
  95                             false,
  96                             static_cast<unsigned long>(
  97                                                        std::distance(r_c.begin(), r_c.end())) <<
  98                             " " << static_cast<unsigned long>(r_c.size()),
  99                             & r_c,
 100                             & r_native_c);
 101
 102   typename native_type::const_iterator it = r_native_c.begin();
 103
 104   while (it != r_native_c.end())
 105     {
 106       typename native_type::key_type native_key =
 107         test_traits::extract_native_key(*it);
 108
 109       m_alloc.set_throw_prob(0);
 110
 111       const key_type k = native_key;
 112
 113       m_alloc.set_throw_prob(1);
 114
 115       typename cntnr::const_point_iterator found_it = r_c.find(k);
 116
 117       PB_DS_THROW_IF_FAILED(
 118                             found_it != r_c.end(),
 119                             test_traits::native_val_to_string(*it),
 120                             & r_c,
 121                             & r_native_c);
 122
 123       if (!test_traits::cmp(*found_it, * it))
 124         PB_DS_THROW_IF_FAILED(                false,  "", & r_c, & r_native_c);
 125
 126       ++it;
 127     }
 128
 129   PB_DS_CANCEL_DESTRUCT_PRINT
 130     }
 131
 132 PB_DS_CLASS_T_DEC
 133 void
 134 PB_DS_CLASS_C_DEC::
 135 cmp_(const Cntnr& r_c, const native_type& r_native_c)
 136 {
 137   enum
 138     {
 139       order_preserving =
 140       container_traits::order_preserving,
 141       back_order_preserving =
 142       container_traits::order_preserving&&
 143       !__gnu_pbds::detail::is_same<
 144       typename std::iterator_traits<
 145       typename cntnr::const_iterator>::iterator_category,
 146       std::forward_iterator_tag>::value,
 147       reverse_iteration = container_traits::reverse_iteration,
 148       order_statistics = test_traits::order_statistics,
 149       prefix_search = test_traits::prefix_search,
 150       has_mapped = !__gnu_pbds::detail::is_same<
 151       typename Cntnr::mapped_type,
 152       __gnu_pbds::null_mapped_type>::value
 153     };
 154
 155   order_preserving_cmp_imp(r_c, r_native_c,
 156                            __gnu_pbds::detail::integral_constant<int,order_preserving>());
 157
 158   back_order_preserving_cmp_imp(r_c, r_native_c,
 159                                 __gnu_pbds::detail::integral_constant<int,back_order_preserving>());
 160
 161   order_statistics_cmp_imp(r_c, r_native_c,
 162                            __gnu_pbds::detail::integral_constant<int,order_statistics>());
 163
 164   prefix_search_cmp_imp(r_c, r_native_c,
 165                         __gnu_pbds::detail::integral_constant<int,prefix_search>());
 166
 167   reverse_iteration_cmp_imp(r_c, r_native_c,
 168                             __gnu_pbds::detail::integral_constant<int,reverse_iteration>());
 169
 170   lower_bound_cmp_imp(r_c, r_native_c,
 171                       __gnu_pbds::detail::integral_constant<int,order_preserving>());
 172
 173   upper_bound_cmp_imp(r_c, r_native_c,
 174                       __gnu_pbds::detail::integral_constant<int,order_preserving>());
 175 }
 176
 177 PB_DS_CLASS_T_DEC
 178 void
 179 PB_DS_CLASS_C_DEC::
 180 order_preserving_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 181 { }
 182
 183 PB_DS_CLASS_T_DEC
 184 void
 185 PB_DS_CLASS_C_DEC::
 186 order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 187 {
 188   PB_DS_SET_DESTRUCT_PRINT
 189
 190     typename cntnr::const_iterator b = r_c.begin();
 191   typename cntnr::const_iterator e = r_c.end();
 192
 193   typename native_type::const_iterator native_b = r_native_c.begin();
 194   typename native_type::const_iterator native_e = r_native_c.end();
 195
 196   try
 197     {
 198       it_cmp_imp(b, e, native_b, native_e);
 199     }
 200   catch(...)
 201     {
 202       PB_DS_THROW_IF_FAILED(            false, "", & r_c, & r_native_c)
 203         }
 204
 205   try
 206     {
 207       back_it_cmp_imp(b, e, native_b, native_e);
 208     }
 209   catch(...)
 210     {
 211       PB_DS_THROW_IF_FAILED(            false, "", & r_c, & r_native_c)
 212         }
 213
 214   PB_DS_CANCEL_DESTRUCT_PRINT
 215     }
 216
 217 PB_DS_CLASS_T_DEC
 218 void
 219 PB_DS_CLASS_C_DEC::
 220 back_order_preserving_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 221 { }
 222
 223 PB_DS_CLASS_T_DEC
 224 void
 225 PB_DS_CLASS_C_DEC::
 226 back_order_preserving_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 227 {
 228   PB_DS_SET_DESTRUCT_PRINT
 229
 230     typename cntnr::const_iterator b = r_c.begin();
 231   typename cntnr::const_iterator e = r_c.end();
 232
 233   typename native_type::const_iterator native_b = r_native_c.begin();
 234   typename native_type::const_iterator native_e = r_native_c.end();
 235
 236   it_cmp_imp(b, e, native_b, native_e);
 237
 238   PB_DS_CANCEL_DESTRUCT_PRINT
 239     }
 240
 241 PB_DS_CLASS_T_DEC
 242 void
 243 PB_DS_CLASS_C_DEC::
 244 reverse_iteration_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 245 { }
 246
 247 PB_DS_CLASS_T_DEC
 248 void
 249 PB_DS_CLASS_C_DEC::
 250 reverse_iteration_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 251 {
 252   PB_DS_SET_DESTRUCT_PRINT
 253
 254     typename cntnr::const_reverse_iterator b = r_c.rbegin();
 255   typename cntnr::const_reverse_iterator e = r_c.rend();
 256
 257   typename native_type::const_reverse_iterator native_b = r_native_c.rbegin();
 258   typename native_type::const_reverse_iterator native_e = r_native_c.rend();
 259
 260   try
 261     {
 262       it_cmp_imp(b, e, native_b, native_e);
 263     }
 264   catch(...)
 265     {
 266       PB_DS_THROW_IF_FAILED(            false, "", & r_c, & r_native_c)
 267         }
 268
 269   try
 270     {
 271       back_it_cmp_imp(b, e, native_b, native_e);
 272     }
 273   catch(...)
 274     {
 275       PB_DS_THROW_IF_FAILED(            false, "", & r_c, & r_native_c)
 276         }
 277
 278   PB_DS_CANCEL_DESTRUCT_PRINT
 279     }
 280
 281 PB_DS_CLASS_T_DEC
 282 void
 283 PB_DS_CLASS_C_DEC::
 284 order_statistics_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 285 { }
 286
 287 PB_DS_CLASS_T_DEC
 288 void
 289 PB_DS_CLASS_C_DEC::
 290 order_statistics_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 291 {
 292   {
 293     m_alloc.set_throw_prob(0);
 294
 295     const key_type k =
 296       test_traits::generate_key(m_g, m_m);
 297
 298     m_alloc.set_throw_prob(1);
 299
 300     const size_type order = r_c.order_of_key(k);
 301
 302     const size_type native_order = std::distance(
 303                                                  r_native_c.begin(),
 304                                                  r_native_c.lower_bound(test_traits::native_key(k)));
 305
 306     PB_DS_THROW_IF_FAILED(
 307                           order == native_order,
 308                           test_traits::key_to_string(k) << " " <<
 309                           static_cast<unsigned long>(order) << " " <<
 310                           static_cast<unsigned long>(native_order),
 311                           & r_c,
 312                           & r_native_c);
 313   }
 314
 315   const size_type rand_ord =
 316     static_cast<size_t>(m_g.get_unsigned_long(
 317                                               0,
 318                                               2*  static_cast<unsigned long>(m_m)));
 319
 320   typename cntnr::const_iterator it =
 321     r_c.find_by_order(rand_ord);
 322
 323   typename native_type::const_iterator native_it =
 324     r_native_c.begin();
 325
 326   std::advance(native_it, std::min(rand_ord, r_native_c.size()));
 327
 328   if (it == r_c.end()&&  native_it != r_native_c.end())
 329     PB_DS_THROW_IF_FAILED(
 330                           false,
 331                           static_cast<unsigned long>(rand_ord),
 332                           m_p_c,
 333                           & m_native_c);
 334
 335   if (it != r_c.end()&&  native_it == r_native_c.end())
 336     PB_DS_THROW_IF_FAILED(
 337                           false,
 338                           static_cast<unsigned long>(rand_ord),
 339                           m_p_c,
 340                           & m_native_c);
 341
 342   if (it != r_c.end()&&     native_it != r_native_c.end())
 343     PB_DS_THROW_IF_FAILED(
 344                           test_traits::cmp(*it, * native_it),
 345                           static_cast<unsigned long>(rand_ord),
 346                           m_p_c,
 347                           & m_native_c);
 348 }
 349
 350 PB_DS_CLASS_T_DEC
 351 void
 352 PB_DS_CLASS_C_DEC::
 353 prefix_search_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 354 { }
 355
 356 PB_DS_CLASS_T_DEC
 357 void
 358 PB_DS_CLASS_C_DEC::
 359 prefix_search_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 360 {
 361   PB_DS_SET_DESTRUCT_PRINT
 362
 363     m_alloc.set_throw_prob(0);
 364
 365   const key_type k =
 366     test_traits::generate_key(m_g, m_m);
 367
 368   m_alloc.set_throw_prob(1);
 369
 370   try
 371     {
 372       typedef
 373         std::pair<
 374         typename Cntnr::const_iterator,
 375         typename Cntnr::const_iterator>
 376         pref_ret_t;
 377
 378       const pref_ret_t pref_ret = r_c.prefix_range(k);
 379
 380       typename native_type::const_iterator native_start_it =
 381         r_native_c.begin();
 382
 383       while (native_start_it != r_native_c.end()&&
 384              !test_traits::prefix_match(
 385                                         k,
 386                                         test_traits::extract_native_key(*native_start_it)))
 387         ++native_start_it;
 388
 389       typename native_type::const_iterator native_end_it =
 390         native_start_it;
 391
 392       do
 393         {
 394           if (native_end_it != r_native_c.end())
 395             ++native_end_it;
 396         }
 397       while (native_end_it != r_native_c.end()&&
 398              test_traits::prefix_match(
 399                                        k,
 400                                        test_traits::extract_native_key(*native_end_it)));
 401
 402       it_cmp_imp(            pref_ret.first, pref_ret.second, native_start_it, native_end_it);
 403     }
 404   catch(...)
 405     {
 406       PB_DS_THROW_IF_FAILED(
 407                             false,
 408                             "prefix key " << k,
 409                             & r_c,
 410                             & r_native_c);
 411     }
 412
 413   PB_DS_CANCEL_DESTRUCT_PRINT
 414     }
 415
 416 PB_DS_CLASS_T_DEC
 417 template<typename Const_It, class Const_Native_It>
 418 void
 419 PB_DS_CLASS_C_DEC::
 420 it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b, Const_Native_It native_e)
 421 {
 422   PB_DS_SET_DESTRUCT_PRINT
 423
 424     if (std::distance(b, e) != std::distance(native_b, native_e))
 425       {
 426         const size_t dist = std::distance(b, e);
 427
 428         const size_t native_dist = std::distance(native_b, native_e);
 429
 430         PB_DS_THROW_IF_FAILED(
 431                               false,
 432                               static_cast<unsigned long>(dist) << " "
 433                               << static_cast<unsigned long>(native_dist),
 434                               m_p_c,
 435                               & m_native_c);
 436       }
 437
 438   while (b != e)
 439     {
 440       PB_DS_THROW_IF_FAILED(            native_b != native_e, "", m_p_c, & m_native_c);
 441
 442       if (!test_traits::cmp(*b, * native_b))
 443         PB_DS_THROW_IF_FAILED(
 444                               false,
 445                               test_traits::val_to_string(*b) << " " <<
 446                               test_traits::val_to_string(*native_b),
 447                               m_p_c,
 448                               & m_native_c);
 449
 450       ++b;
 451       ++native_b;
 452     }
 453
 454   PB_DS_THROW_IF_FAILED(        native_b == native_e, "", m_p_c,    & m_native_c);
 455
 456   PB_DS_CANCEL_DESTRUCT_PRINT
 457     }
 458
 459 PB_DS_CLASS_T_DEC
 460 template<typename Const_It, class Const_Native_It>
 461 void
 462 PB_DS_CLASS_C_DEC::
 463 back_it_cmp_imp(Const_It b, Const_It e, Const_Native_It native_b, Const_Native_It native_e)
 464 {
 465   PB_DS_SET_DESTRUCT_PRINT
 466
 467     while (b != e)
 468       {
 469         PB_DS_THROW_IF_FAILED(
 470                               native_b != native_e,
 471                               test_traits::val_to_string(*native_e),
 472                               m_p_c,
 473                               & m_native_c);
 474
 475         --e;
 476         --native_e;
 477
 478         PB_DS_THROW_IF_FAILED(
 479                               test_traits::cmp(*e, * native_e),
 480                               test_traits::val_to_string(*e) <<
 481                               test_traits::val_to_string(*native_e),
 482                               m_p_c,
 483                               & m_native_c);
 484       }
 485
 486   PB_DS_THROW_IF_FAILED(
 487                         native_b == native_e,
 488                         test_traits::val_to_string(*native_e),
 489                         m_p_c,
 490                         & m_native_c);
 491
 492   PB_DS_CANCEL_DESTRUCT_PRINT
 493     }
 494
 495 PB_DS_CLASS_T_DEC
 496 void
 497 PB_DS_CLASS_C_DEC::
 498 lower_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 499 { }
 500
 501 PB_DS_CLASS_T_DEC
 502 void
 503 PB_DS_CLASS_C_DEC::
 504 lower_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 505 {
 506   PB_DS_SET_DESTRUCT_PRINT
 507
 508     m_alloc.set_throw_prob(0);
 509
 510   const key_type k =
 511     test_traits::generate_key(m_g, m_m);
 512
 513   m_alloc.set_throw_prob(1);
 514
 515   typename cntnr::const_iterator it =    r_c.lower_bound(k);
 516
 517   typename native_type::key_type native_k = test_traits::native_key(k);
 518
 519   typename native_type::const_iterator native_it =
 520     r_native_c.lower_bound(native_k);
 521
 522   if (it != r_c.end()&&  native_it == r_native_c.end())
 523     PB_DS_THROW_IF_FAILED(
 524                           "",
 525                           "it: " + test_traits::val_to_string(*it) + "\n\n",
 526                           & r_c,
 527                           & r_native_c);
 528
 529   if (it == r_c.end()&&  native_it != r_native_c.end())
 530     PB_DS_THROW_IF_FAILED(
 531                           "",
 532                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 533                           & r_c,
 534                           & r_native_c);
 535
 536   if (it != r_c.end()&&  !test_traits::cmp(*it, * native_it))
 537     PB_DS_THROW_IF_FAILED(
 538                           false,
 539                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 540                           "it: " + test_traits::val_to_string(*it) + "\n\n" +
 541                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 542                           & r_c,
 543                           & r_native_c);
 544
 545   PB_DS_CANCEL_DESTRUCT_PRINT
 546     }
 547
 548 PB_DS_CLASS_T_DEC
 549 void
 550 PB_DS_CLASS_C_DEC::
 551 upper_bound_cmp_imp(const Cntnr& /*r_c*/, const native_type& /*r_native_c*/, __gnu_pbds::detail::false_type)
 552 { }
 553
 554 PB_DS_CLASS_T_DEC
 555 void
 556 PB_DS_CLASS_C_DEC::
 557 upper_bound_cmp_imp(const Cntnr& r_c, const native_type& r_native_c, __gnu_pbds::detail::true_type)
 558 {
 559   PB_DS_SET_DESTRUCT_PRINT
 560
 561     m_alloc.set_throw_prob(0);
 562
 563   const key_type k =
 564     test_traits::generate_key(m_g, m_m);
 565
 566   m_alloc.set_throw_prob(1);
 567
 568   typename cntnr::const_iterator it =    r_c.upper_bound(k);
 569
 570   typename native_type::key_type native_k = test_traits::native_key(k);
 571
 572   typename native_type::const_iterator native_it =
 573     r_native_c.upper_bound(native_k);
 574
 575   if (it == r_c.end()&&  native_it != r_native_c.end())
 576     PB_DS_THROW_IF_FAILED(
 577                           false,
 578                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 579                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 580                           & r_c,
 581                           & r_native_c);
 582
 583   if (it != r_c.end()&&  native_it == r_native_c.end())
 584     PB_DS_THROW_IF_FAILED(
 585                           false,
 586                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 587                           "it: " + test_traits::val_to_string(*it) + "\n\n",
 588                           & r_c,
 589                           & r_native_c);
 590
 591   if (it != r_c.end()&&  !test_traits::cmp(*it, * native_it))
 592     PB_DS_THROW_IF_FAILED(
 593                           false,
 594                           "key: " + test_traits::key_to_string(k) + "\n\n" +
 595                           "it: " + test_traits::val_to_string(*it) + "\n\n" +
 596                           "native_it: " + test_traits::val_to_string(*native_it) + "\n\n",
 597                           & r_c,
 598                           & r_native_c);
 599
 600   PB_DS_CANCEL_DESTRUCT_PRINT
 601     }