OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [testsuite/] [util/] [regression/] [rand/] [assoc/] [container_rand_regression_test.tcc] - Blame information for rev 742

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 742 jeremybenn 
// -*- C++ -*-
2 
 
3 
// Copyright (C) 2005, 2006, 2008, 2009, 2010 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 
// .
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(std::distance(r_c.begin(), r_c.end())) != r_c.size())
442 
    PB_DS_THROW_IF_FAILED(false,
443 
                          static_cast(std::distance(r_c.begin(), r_c.end())) << " " << static_cast(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());
490 
 
491 
  back_order_preserving_cmp_imp(r_c, r_native_c,
492 
                                __gnu_pbds::detail::integral_constant());
493 
 
494 
  order_statistics_cmp_imp(r_c, r_native_c,
495 
                           __gnu_pbds::detail::integral_constant());
496 
 
497 
  prefix_search_cmp_imp(r_c, r_native_c,
498 
                        __gnu_pbds::detail::integral_constant());
499 
 
500 
  reverse_iteration_cmp_imp(r_c, r_native_c,
501 
                            __gnu_pbds::detail::integral_constant());
502 
 
503 
  lower_bound_cmp_imp(r_c, r_native_c,
504 
                      __gnu_pbds::detail::integral_constant());
505 
 
506 
  upper_bound_cmp_imp(r_c, r_native_c,
507 
                      __gnu_pbds::detail::integral_constant());
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(order) << " " <<
635 
                          static_cast(native_order),
636 
                          &r_c,
637 
                          &r_native_c);
638 
  }
639 
 
640 
  const size_type rand_ord =
641 
    static_cast(m_g.get_unsigned_long(0,
642 
                                              2 * static_cast(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(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(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(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
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
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(dist) << " "
733 
                            << static_cast(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
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::name(),
876 
                               string_form::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(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(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(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 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()));
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::reference
1241 
        it_const_reference;
1242 
 
1243 
      typedef
1244 
        typename test_traits::template erase_if_fn
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()));
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()));
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
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 __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());
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());
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 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
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(0.05);
2030 
  const float max_load = static_cast(0.9);
2031 
 
2032 
  const float new_load = static_cast(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
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 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(0.05);
2079 
      const float max_min_load = static_cast(0.2);
2080 
 
2081 
      const float new_min_load =
2082 
        static_cast(m_g.get_prob()*  (max_min_load - min_min_load) +
2083 
                           min_min_load);
2084 
 
2085 
      const float new_max_load = static_cast(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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.