release/src-rt-6.x.4708/toolchains/hndtools-arm-linux-2.6.36-uclibc-4.5.3/arm-brcm-linux-uclibcgnueabi/include/c++/4.5.3/ext/pb_ds/detail/pat_trie_/internal_node.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file internal_node.hpp
  38  * Contains an internal PB_DS_BASE_C_DEC for a patricia tree.
  39  */
  40
  41 #ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP
  42 #define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP
  43
  44 #include <debug/debug.h>
  45
  46 namespace __gnu_pbds
  47 {
  48   namespace detail
  49   {
  50 #define PB_DS_CLASS_T_DEC \
  51     template<typename Type_Traits, typename E_Access_Traits,  \
  52              typename Metadata, typename Allocator>
  53
  54 #define PB_DS_CLASS_C_DEC \
  55     pat_trie_internal_node<Type_Traits, E_Access_Traits, Metadata, Allocator>
  56
  57 #define PB_DS_BASE_C_DEC \
  58     pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator>
  59
  60 #define PB_DS_LEAF_C_DEC \
  61     pat_trie_leaf<Type_Traits, E_Access_Traits, Metadata, Allocator>
  62
  63     template<typename Type_Traits,
  64              typename E_Access_Traits,
  65              typename Metadata,
  66              typename Allocator>
  67     struct pat_trie_internal_node : public PB_DS_BASE_C_DEC
  68     {
  69     private:
  70       typedef PB_DS_BASE_C_DEC                  base_type;
  71       typedef Type_Traits                       type_traits;
  72       typedef typename type_traits::value_type  value_type;
  73       typedef typename Allocator::size_type     size_type;
  74
  75       typedef E_Access_Traits e_access_traits;
  76       typedef typename e_access_traits::const_iterator const_e_iterator;
  77       typedef typename Allocator::template rebind<e_access_traits>::other access_rebind;
  78       typedef typename access_rebind::const_pointer const_e_access_traits_pointer;
  79
  80       typedef typename Allocator::template rebind<base_type>::other base_rebind;
  81       typedef typename base_rebind::pointer node_pointer;
  82       typedef typename base_rebind::const_pointer const_node_pointer;
  83
  84       typedef PB_DS_LEAF_C_DEC leaf;
  85       typedef typename Allocator::template rebind<leaf>::other leaf_rebind;
  86       typedef typename leaf_rebind::pointer leaf_pointer;
  87       typedef typename leaf_rebind::const_pointer const_leaf_pointer;
  88
  89       typedef typename Allocator::template rebind<pat_trie_internal_node>::other internal_node_rebind;
  90       typedef typename internal_node_rebind::pointer internal_node_pointer;
  91       typedef typename internal_node_rebind::const_pointer const_internal_node_pointer;
  92
  93 #ifdef _GLIBCXX_DEBUG
  94       typedef typename base_type::subtree_debug_info subtree_debug_info;
  95
  96       virtual subtree_debug_info
  97       assert_valid_imp(const_e_access_traits_pointer) const;
  98 #endif
  99
 100       inline size_type
 101       get_pref_pos(const_e_iterator, const_e_iterator,
 102                    const_e_access_traits_pointer) const;
 103
 104     public:
 105       typedef typename Allocator::template rebind<node_pointer>::other node_pointer_rebind;
 106       typedef typename node_pointer_rebind::pointer node_pointer_pointer;
 107       typedef typename node_pointer_rebind::reference node_pointer_reference;
 108
 109       enum
 110         {
 111           arr_size = E_Access_Traits::max_size + 1
 112         };
 113       PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2);
 114
 115 #include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp>
 116 #include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp>
 117
 118       pat_trie_internal_node(size_type, const const_e_iterator);
 119
 120       void
 121       update_prefixes(const_e_access_traits_pointer);
 122
 123       const_iterator
 124       begin() const;
 125
 126       iterator
 127       begin();
 128
 129       const_iterator
 130       end() const;
 131
 132       iterator
 133       end();
 134
 135       inline node_pointer
 136       get_child_node(const_e_iterator, const_e_iterator,
 137                      const_e_access_traits_pointer);
 138
 139       inline const_node_pointer
 140       get_child_node(const_e_iterator, const_e_iterator,
 141                      const_e_access_traits_pointer) const;
 142
 143       inline iterator
 144       get_child_it(const_e_iterator, const_e_iterator,
 145                    const_e_access_traits_pointer);
 146
 147       inline node_pointer
 148       get_lower_bound_child_node(const_e_iterator, const_e_iterator,
 149                                  size_type, const_e_access_traits_pointer);
 150
 151       inline node_pointer
 152       add_child(node_pointer, const_e_iterator, const_e_iterator,
 153                 const_e_access_traits_pointer);
 154
 155       inline const_node_pointer
 156       get_join_child(const_node_pointer, const_e_access_traits_pointer) const;
 157
 158       inline node_pointer
 159       get_join_child(node_pointer, const_e_access_traits_pointer);
 160
 161       void
 162       remove_child(node_pointer p_nd);
 163
 164       iterator
 165       remove_child(iterator it);
 166
 167       void
 168       replace_child(node_pointer, const_e_iterator, const_e_iterator,
 169                     const_e_access_traits_pointer);
 170
 171       inline const_e_iterator
 172       pref_b_it() const;
 173
 174       inline const_e_iterator
 175       pref_e_it() const;
 176
 177       inline size_type
 178       get_e_ind() const;
 179
 180       bool
 181       should_be_mine(const_e_iterator, const_e_iterator, size_type,
 182                      const_e_access_traits_pointer) const;
 183
 184       leaf_pointer
 185       leftmost_descendant();
 186
 187       const_leaf_pointer
 188       leftmost_descendant() const;
 189
 190       leaf_pointer
 191       rightmost_descendant();
 192
 193       const_leaf_pointer
 194       rightmost_descendant() const;
 195
 196 #ifdef _GLIBCXX_DEBUG
 197       size_type
 198       e_ind() const;
 199 #endif
 200
 201     private:
 202       pat_trie_internal_node(const pat_trie_internal_node&);
 203
 204       size_type
 205       get_begin_pos() const;
 206
 207       const size_type m_e_ind;
 208       const_e_iterator m_pref_b_it;
 209       const_e_iterator m_pref_e_it;
 210       node_pointer m_a_p_children[arr_size];
 211       static leaf_rebind s_leaf_alloc;
 212       static internal_node_rebind s_internal_node_alloc;
 213     };
 214
 215     PB_DS_CLASS_T_DEC
 216     typename PB_DS_CLASS_C_DEC::leaf_rebind
 217     PB_DS_CLASS_C_DEC::s_leaf_alloc;
 218
 219     PB_DS_CLASS_T_DEC
 220     typename PB_DS_CLASS_C_DEC::internal_node_rebind
 221     PB_DS_CLASS_C_DEC::s_internal_node_alloc;
 222
 223     PB_DS_CLASS_T_DEC
 224     inline typename PB_DS_CLASS_C_DEC::size_type
 225     PB_DS_CLASS_C_DEC::
 226     get_pref_pos(const_e_iterator b_it, const_e_iterator e_it,
 227                  const_e_access_traits_pointer p_traits) const
 228     {
 229       if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind)
 230         return 0;
 231       std::advance(b_it, m_e_ind);
 232       return 1 + p_traits->e_pos(*b_it);
 233     }
 234
 235     PB_DS_CLASS_T_DEC
 236     PB_DS_CLASS_C_DEC::
 237     pat_trie_internal_node(size_type len, const const_e_iterator it) :
 238       PB_DS_BASE_C_DEC(pat_trie_internal_node_type),
 239       m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it)
 240     {
 241       std::advance(m_pref_e_it, m_e_ind);
 242       std::fill(m_a_p_children, m_a_p_children + arr_size,
 243                 static_cast<node_pointer>(NULL));
 244     }
 245
 246     PB_DS_CLASS_T_DEC
 247     void
 248     PB_DS_CLASS_C_DEC::
 249     update_prefixes(const_e_access_traits_pointer p_traits)
 250     {
 251       node_pointer p_first = *begin();
 252       if (p_first->m_type == pat_trie_leaf_node_type)
 253         {
 254           const_leaf_pointer p = static_cast<const_leaf_pointer>(p_first);
 255           m_pref_b_it = p_traits->begin(e_access_traits::extract_key(p->value()));
 256         }
 257       else
 258         {
 259           _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type);
 260           m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it();
 261         }
 262       m_pref_e_it = m_pref_b_it;
 263       std::advance(m_pref_e_it, m_e_ind);
 264     }
 265
 266     PB_DS_CLASS_T_DEC
 267     typename PB_DS_CLASS_C_DEC::const_iterator
 268     PB_DS_CLASS_C_DEC::
 269     begin() const
 270     {
 271       typedef node_pointer_pointer pointer_type;
 272       pointer_type p = const_cast<pointer_type>(m_a_p_children);
 273       return const_iterator(p + get_begin_pos(), p + arr_size);
 274     }
 275
 276     PB_DS_CLASS_T_DEC
 277     typename PB_DS_CLASS_C_DEC::iterator
 278     PB_DS_CLASS_C_DEC::
 279     begin()
 280     {
 281       return iterator(m_a_p_children + get_begin_pos(),
 282                       m_a_p_children + arr_size);
 283     }
 284
 285     PB_DS_CLASS_T_DEC
 286     typename PB_DS_CLASS_C_DEC::const_iterator
 287     PB_DS_CLASS_C_DEC::
 288     end() const
 289     {
 290       typedef node_pointer_pointer pointer_type;
 291       pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size;
 292       return const_iterator(p, p);
 293     }
 294
 295     PB_DS_CLASS_T_DEC
 296     typename PB_DS_CLASS_C_DEC::iterator
 297     PB_DS_CLASS_C_DEC::
 298     end()
 299     { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }
 300
 301     PB_DS_CLASS_T_DEC
 302     inline typename PB_DS_CLASS_C_DEC::node_pointer
 303     PB_DS_CLASS_C_DEC::
 304     get_child_node(const_e_iterator b_it, const_e_iterator e_it,
 305                    const_e_access_traits_pointer p_traits)
 306     {
 307       const size_type i = get_pref_pos(b_it, e_it, p_traits);
 308       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
 309       return m_a_p_children[i];
 310     }
 311
 312     PB_DS_CLASS_T_DEC
 313     inline typename PB_DS_CLASS_C_DEC::iterator
 314     PB_DS_CLASS_C_DEC::
 315     get_child_it(const_e_iterator b_it, const_e_iterator e_it,
 316                  const_e_access_traits_pointer p_traits)
 317     {
 318       const size_type i = get_pref_pos(b_it, e_it, p_traits);
 319       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
 320       _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL);
 321       return iterator(m_a_p_children + i, m_a_p_children + i);
 322     }
 323
 324     PB_DS_CLASS_T_DEC
 325     inline typename PB_DS_CLASS_C_DEC::const_node_pointer
 326     PB_DS_CLASS_C_DEC::
 327     get_child_node(const_e_iterator b_it, const_e_iterator e_it,
 328                    const_e_access_traits_pointer p_traits) const
 329     { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); }
 330
 331     PB_DS_CLASS_T_DEC
 332     typename PB_DS_CLASS_C_DEC::node_pointer
 333     PB_DS_CLASS_C_DEC::
 334     get_lower_bound_child_node(const_e_iterator b_it, const_e_iterator e_it,
 335                                size_type checked_ind,
 336                                const_e_access_traits_pointer p_traits)
 337     {
 338       if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
 339         {
 340           if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true))
 341             return leftmost_descendant();
 342           return rightmost_descendant();
 343         }
 344
 345       size_type i = get_pref_pos(b_it, e_it, p_traits);
 346       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
 347
 348       if (m_a_p_children[i] != NULL)
 349         return m_a_p_children[i];
 350
 351       while (++i < arr_size)
 352         if (m_a_p_children[i] != NULL)
 353           {
 354             if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type)
 355               return m_a_p_children[i];
 356
 357             _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type);
 358
 359             return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant();
 360           }
 361
 362       return rightmost_descendant();
 363     }
 364
 365     PB_DS_CLASS_T_DEC
 366     inline typename PB_DS_CLASS_C_DEC::node_pointer
 367     PB_DS_CLASS_C_DEC::
 368     add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it,
 369               const_e_access_traits_pointer p_traits)
 370     {
 371       const size_type i = get_pref_pos(b_it, e_it, p_traits);
 372       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
 373       if (m_a_p_children[i] == NULL)
 374         {
 375           m_a_p_children[i] = p_nd;
 376           p_nd->m_p_parent = this;
 377           return p_nd;
 378         }
 379       return m_a_p_children[i];
 380     }
 381
 382     PB_DS_CLASS_T_DEC
 383     typename PB_DS_CLASS_C_DEC::const_node_pointer
 384     PB_DS_CLASS_C_DEC::
 385     get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const
 386     {
 387       node_pointer p = const_cast<node_pointer>(p_nd);
 388       return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits);
 389     }
 390
 391     PB_DS_CLASS_T_DEC
 392     typename PB_DS_CLASS_C_DEC::node_pointer
 393     PB_DS_CLASS_C_DEC::
 394     get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits)
 395     {
 396       size_type i;
 397       const_e_iterator b_it;
 398       const_e_iterator e_it;
 399       if (p_nd->m_type == pat_trie_leaf_node_type)
 400         {
 401           typename Type_Traits::const_key_reference r_key =
 402             e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value());
 403
 404           b_it = p_traits->begin(r_key);
 405           e_it = p_traits->end(r_key);
 406         }
 407       else
 408         {
 409           b_it = static_cast<internal_node_pointer>(p_nd)->pref_b_it();
 410           e_it = static_cast<internal_node_pointer>(p_nd)->pref_e_it();
 411         }
 412       i = get_pref_pos(b_it, e_it, p_traits);
 413       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
 414       return m_a_p_children[i];
 415     }
 416
 417     PB_DS_CLASS_T_DEC
 418     void
 419     PB_DS_CLASS_C_DEC::
 420     remove_child(node_pointer p_nd)
 421     {
 422       size_type i = 0;
 423       for (; i < arr_size; ++i)
 424         if (m_a_p_children[i] == p_nd)
 425           {
 426             m_a_p_children[i] = NULL;
 427             return;
 428           }
 429       _GLIBCXX_DEBUG_ASSERT(i != arr_size);
 430     }
 431
 432     PB_DS_CLASS_T_DEC
 433     typename PB_DS_CLASS_C_DEC::iterator
 434     PB_DS_CLASS_C_DEC::
 435     remove_child(iterator it)
 436     {
 437       iterator ret = it;
 438       ++ret;
 439       * it.m_p_p_cur = NULL;
 440       return ret;
 441     }
 442
 443     PB_DS_CLASS_T_DEC
 444     void
 445     PB_DS_CLASS_C_DEC::
 446     replace_child(node_pointer p_nd, const_e_iterator b_it,
 447                   const_e_iterator e_it,
 448                   const_e_access_traits_pointer p_traits)
 449     {
 450       const size_type i = get_pref_pos(b_it, e_it, p_traits);
 451       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
 452       m_a_p_children[i] = p_nd;
 453       p_nd->m_p_parent = this;
 454     }
 455
 456     PB_DS_CLASS_T_DEC
 457     inline typename PB_DS_CLASS_C_DEC::const_e_iterator
 458     PB_DS_CLASS_C_DEC::
 459     pref_b_it() const
 460     { return m_pref_b_it; }
 461
 462     PB_DS_CLASS_T_DEC
 463     inline typename PB_DS_CLASS_C_DEC::const_e_iterator
 464     PB_DS_CLASS_C_DEC::
 465     pref_e_it() const
 466     { return m_pref_e_it; }
 467
 468     PB_DS_CLASS_T_DEC
 469     inline typename PB_DS_CLASS_C_DEC::size_type
 470     PB_DS_CLASS_C_DEC::
 471     get_e_ind() const
 472     { return m_e_ind; }
 473
 474     PB_DS_CLASS_T_DEC
 475     bool
 476     PB_DS_CLASS_C_DEC::
 477     should_be_mine(const_e_iterator b_it, const_e_iterator e_it,
 478                    size_type checked_ind,
 479                    const_e_access_traits_pointer p_traits) const
 480     {
 481       if (m_e_ind == 0)
 482         return true;
 483
 484       const size_type num_es = std::distance(b_it, e_it);
 485       if (num_es < m_e_ind)
 486         return false;
 487
 488       const_e_iterator key_b_it = b_it;
 489       std::advance(key_b_it, checked_ind);
 490       const_e_iterator key_e_it = b_it;
 491       std::advance(key_e_it, m_e_ind);
 492
 493       const_e_iterator value_b_it = m_pref_b_it;
 494       std::advance(value_b_it, checked_ind);
 495       const_e_iterator value_e_it = m_pref_b_it;
 496       std::advance(value_e_it, m_e_ind);
 497
 498       return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it,
 499                                       value_e_it);
 500     }
 501
 502     PB_DS_CLASS_T_DEC
 503     typename PB_DS_CLASS_C_DEC::leaf_pointer
 504     PB_DS_CLASS_C_DEC::
 505     leftmost_descendant()
 506     {
 507       node_pointer p_pot =* begin();
 508       if (p_pot->m_type == pat_trie_leaf_node_type)
 509         return (static_cast<leaf_pointer>(p_pot));
 510       _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type);
 511       return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant();
 512     }
 513
 514     PB_DS_CLASS_T_DEC
 515     typename PB_DS_CLASS_C_DEC::const_leaf_pointer
 516     PB_DS_CLASS_C_DEC::
 517     leftmost_descendant() const
 518     {
 519       return const_cast<internal_node_pointer>(this)->leftmost_descendant();
 520     }
 521
 522     PB_DS_CLASS_T_DEC
 523     typename PB_DS_CLASS_C_DEC::leaf_pointer
 524     PB_DS_CLASS_C_DEC::
 525     rightmost_descendant()
 526     {
 527       const size_type num_children = std::distance(begin(), end());
 528       _GLIBCXX_DEBUG_ASSERT(num_children >= 2);
 529
 530       iterator it = begin();
 531       std::advance(it, num_children - 1);
 532       node_pointer p_pot =* it;
 533       if (p_pot->m_type == pat_trie_leaf_node_type)
 534         return static_cast<leaf_pointer>(p_pot);
 535       _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type);
 536       return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant();
 537     }
 538
 539     PB_DS_CLASS_T_DEC
 540     typename PB_DS_CLASS_C_DEC::const_leaf_pointer
 541     PB_DS_CLASS_C_DEC::
 542     rightmost_descendant() const
 543     {
 544       return const_cast<internal_node_pointer>(this)->rightmost_descendant();
 545     }
 546
 547 #ifdef _GLIBCXX_DEBUG
 548     PB_DS_CLASS_T_DEC
 549     typename PB_DS_CLASS_C_DEC::size_type
 550     PB_DS_CLASS_C_DEC::
 551     e_ind() const
 552     { return m_e_ind; }
 553 #endif
 554
 555     PB_DS_CLASS_T_DEC
 556     typename PB_DS_CLASS_C_DEC::size_type
 557     PB_DS_CLASS_C_DEC::
 558     get_begin_pos() const
 559     {
 560       size_type i;
 561       for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i)
 562         ;
 563       return i;
 564     }
 565
 566 #ifdef _GLIBCXX_DEBUG
 567     PB_DS_CLASS_T_DEC
 568     typename PB_DS_CLASS_C_DEC::subtree_debug_info
 569     PB_DS_CLASS_C_DEC::
 570     assert_valid_imp(const_e_access_traits_pointer p_traits) const
 571     {
 572       _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_internal_node_type);
 573       _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind);
 574       _GLIBCXX_DEBUG_ASSERT(std::distance(begin(), end()) >= 2);
 575
 576       for (typename pat_trie_internal_node::const_iterator it = begin();
 577            it != end(); ++it)
 578         {
 579           const_node_pointer p_nd =* it;
 580           _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this);
 581           subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits);
 582
 583           _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind);
 584           _GLIBCXX_DEBUG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
 585           _GLIBCXX_DEBUG_ASSERT(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast<size_type>(it.m_p_p_cur - m_a_p_children));
 586         }
 587       return std::make_pair(pref_b_it(), pref_e_it());
 588     }
 589 #endif
 590
 591 #undef PB_DS_CLASS_T_DEC
 592 #undef PB_DS_CLASS_C_DEC
 593 #undef PB_DS_BASE_C_DEC
 594 #undef PB_DS_LEAF_C_DEC
 595
 596   } // namespace detail
 597 } // namespace __gnu_pbds
 598
 599 #endif