libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2011 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 pat_trie_/pat_trie_base.hpp
  38  * Contains the base class for a patricia tree.
  39  */
  40
  41 #ifndef PB_DS_PAT_TRIE_BASE
  42 #define PB_DS_PAT_TRIE_BASE
  43
  44 #include <debug/debug.h>
  45
  46 namespace __gnu_pbds
  47 {
  48   namespace detail
  49   {
  50     /// Base type for PATRICIA trees.
  51     struct pat_trie_base
  52     {
  53       /// Three types of nodes.
  54       enum node_type
  55         {
  56           i_node,
  57           leaf_node,
  58           head_node
  59         };
  60
  61       /// Metadata base primary template.
  62       template<typename Metadata, typename _Alloc>
  63         struct _Metadata
  64         {
  65           typedef Metadata                                      metadata_type;
  66           typedef _Alloc                                        allocator_type;
  67           typedef typename _Alloc::template rebind<Metadata>    __rebind_m;
  68           typedef typename __rebind_m::other::const_reference  const_reference;
  69
  70           const_reference
  71           get_metadata() const
  72           { return m_metadata; }
  73
  74           metadata_type                                         m_metadata;
  75         };
  76
  77       /// Specialization for null metadata.
  78       template<typename _Alloc>
  79         struct _Metadata<null_type, _Alloc>
  80         {
  81           typedef null_type                                     metadata_type;
  82           typedef _Alloc                                        allocator_type;
  83         };
  84
  85
  86       /// Node base.
  87       template<typename _ATraits, typename Metadata>
  88       struct _Node_base
  89       : public Metadata
  90       {
  91       private:
  92         typedef typename Metadata::allocator_type               _Alloc;
  93
  94       public:
  95         typedef _Alloc                                          allocator_type;
  96         typedef _ATraits                                        access_traits;
  97         typedef typename _ATraits::type_traits                  type_traits;
  98         typedef typename _Alloc::template rebind<_Node_base>    __rebind_n;
  99         typedef typename __rebind_n::other::pointer             node_pointer;
 100
 101         node_pointer                                            m_p_parent;
 102         const node_type                                         m_type;
 103
 104         _Node_base(node_type type) : m_type(type)
 105         { }
 106
 107         typedef typename _Alloc::template rebind<_ATraits>    __rebind_at;
 108         typedef typename __rebind_at::other::const_pointer    a_const_pointer;
 109         typedef typename _ATraits::const_iterator             a_const_iterator;
 110
 111 #ifdef _GLIBCXX_DEBUG
 112         typedef std::pair<a_const_iterator, a_const_iterator> node_debug_info;
 113
 114         void
 115         assert_valid(a_const_pointer p_traits,
 116                      const char* __file, int __line) const
 117         { assert_valid_imp(p_traits, __file, __line); }
 118
 119         virtual node_debug_info
 120         assert_valid_imp(a_const_pointer, const char*, int) const = 0;
 121 #endif
 122       };
 123
 124
 125     /// Head node for PATRICIA tree.
 126     template<typename _ATraits, typename Metadata>
 127     struct _Head
 128     : public _Node_base<_ATraits, Metadata>
 129     {
 130       typedef _Node_base<_ATraits, Metadata>                    base_type;
 131       typedef typename base_type::type_traits                   type_traits;
 132       typedef typename base_type::node_pointer                  node_pointer;
 133
 134       node_pointer                                              m_p_min;
 135       node_pointer                                              m_p_max;
 136
 137       _Head() : base_type(head_node) { }
 138
 139 #ifdef _GLIBCXX_DEBUG
 140       typedef typename base_type::node_debug_info              node_debug_info;
 141       typedef typename base_type::a_const_pointer              a_const_pointer;
 142
 143       virtual node_debug_info
 144       assert_valid_imp(a_const_pointer, const char* __file, int __line) const
 145       {
 146         _GLIBCXX_DEBUG_VERIFY_AT(false,
 147                                  _M_message("Assertion from %1;:%2;")
 148                                  ._M_string(__FILE__)._M_integer(__LINE__),
 149                                  __file, __line);
 150         return node_debug_info();
 151       }
 152 #endif
 153     };
 154
 155
 156     /// Leaf node for PATRICIA tree.
 157     template<typename _ATraits, typename Metadata>
 158     struct _Leaf
 159     : public _Node_base<_ATraits, Metadata>
 160     {
 161       typedef _Node_base<_ATraits, Metadata>                    base_type;
 162       typedef typename base_type::type_traits                   type_traits;
 163       typedef typename type_traits::value_type                  value_type;
 164       typedef typename type_traits::reference                   reference;
 165       typedef typename type_traits::const_reference             const_reference;
 166
 167     private:
 168       value_type                                                m_value;
 169
 170       _Leaf(const _Leaf&);
 171
 172     public:
 173       _Leaf(const_reference other)
 174       : base_type(leaf_node), m_value(other) { }
 175
 176       reference
 177       value()
 178       { return m_value; }
 179
 180       const_reference
 181       value() const
 182       { return m_value; }
 183
 184 #ifdef _GLIBCXX_DEBUG
 185       typedef typename base_type::node_debug_info               node_debug_info;
 186       typedef typename base_type::a_const_pointer               a_const_pointer;
 187
 188       virtual node_debug_info
 189       assert_valid_imp(a_const_pointer p_traits,
 190                        const char* __file, int __line) const
 191       {
 192         PB_DS_DEBUG_VERIFY(base_type::m_type == leaf_node);
 193         node_debug_info ret;
 194         const_reference r_val = value();
 195         return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)),
 196                               p_traits->end(p_traits->extract_key(r_val)));
 197       }
 198
 199       virtual
 200       ~_Leaf() { }
 201 #endif
 202     };
 203
 204
 205     /// Internal node type, PATRICIA tree.
 206     template<typename _ATraits, typename Metadata>
 207     struct _Inode
 208     : public _Node_base<_ATraits, Metadata>
 209     {
 210       typedef _Node_base<_ATraits, Metadata>                    base_type;
 211       typedef typename base_type::type_traits                   type_traits;
 212       typedef typename base_type::access_traits                 access_traits;
 213       typedef typename type_traits::value_type                  value_type;
 214       typedef typename base_type::allocator_type                _Alloc;
 215       typedef _Alloc                                            allocator_type;
 216       typedef typename _Alloc::size_type                        size_type;
 217
 218     private:
 219       typedef typename base_type::a_const_pointer              a_const_pointer;
 220       typedef typename base_type::a_const_iterator            a_const_iterator;
 221
 222       typedef typename base_type::node_pointer                  node_pointer;
 223       typedef typename _Alloc::template rebind<base_type>       __rebind_n;
 224       typedef typename __rebind_n::other::const_pointer      node_const_pointer;
 225
 226       typedef _Leaf<_ATraits, Metadata>                         leaf;
 227       typedef typename _Alloc::template rebind<leaf>::other     __rebind_l;
 228       typedef typename __rebind_l::pointer                      leaf_pointer;
 229       typedef typename __rebind_l::const_pointer            leaf_const_pointer;
 230
 231       typedef typename _Alloc::template rebind<_Inode>::other   __rebind_in;
 232       typedef typename __rebind_in::pointer                     inode_pointer;
 233       typedef typename __rebind_in::const_pointer           inode_const_pointer;
 234
 235       inline size_type
 236       get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer) const;
 237
 238     public:
 239       typedef typename _Alloc::template rebind<node_pointer>::other __rebind_np;
 240       typedef typename __rebind_np::pointer             node_pointer_pointer;
 241       typedef typename __rebind_np::reference           node_pointer_reference;
 242
 243       enum
 244         {
 245           arr_size = _ATraits::max_size + 1
 246         };
 247       PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2);
 248
 249
 250       /// Constant child iterator.
 251       struct const_iterator
 252       {
 253         node_pointer_pointer                            m_p_p_cur;
 254         node_pointer_pointer                            m_p_p_end;
 255
 256         typedef std::forward_iterator_tag               iterator_category;
 257         typedef typename _Alloc::difference_type        difference_type;
 258         typedef node_pointer                            value_type;
 259         typedef node_pointer_pointer                    pointer;
 260         typedef node_pointer_reference                  reference;
 261
 262         const_iterator(node_pointer_pointer p_p_cur = 0,
 263                        node_pointer_pointer p_p_end = 0)
 264         : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end)
 265         { }
 266
 267         bool
 268         operator==(const const_iterator& other) const
 269         { return m_p_p_cur == other.m_p_p_cur; }
 270
 271         bool
 272         operator!=(const const_iterator& other) const
 273         { return m_p_p_cur != other.m_p_p_cur; }
 274
 275         const_iterator&
 276         operator++()
 277         {
 278           do
 279             ++m_p_p_cur;
 280           while (m_p_p_cur != m_p_p_end && *m_p_p_cur == 0);
 281           return *this;
 282         }
 283
 284         const_iterator
 285         operator++(int)
 286         {
 287           const_iterator ret_it(*this);
 288           operator++();
 289           return ret_it;
 290         }
 291
 292         const node_pointer_pointer
 293         operator->() const
 294         {
 295           _GLIBCXX_DEBUG_ONLY(assert_referencible();)
 296           return m_p_p_cur;
 297         }
 298
 299         node_const_pointer
 300         operator*() const
 301         {
 302           _GLIBCXX_DEBUG_ONLY(assert_referencible();)
 303           return *m_p_p_cur;
 304         }
 305
 306       protected:
 307 #ifdef _GLIBCXX_DEBUG
 308         void
 309         assert_referencible() const
 310         { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end && *m_p_p_cur != 0); }
 311 #endif
 312       };
 313
 314
 315       /// Child iterator.
 316       struct iterator : public const_iterator
 317       {
 318       public:
 319         typedef std::forward_iterator_tag               iterator_category;
 320         typedef typename _Alloc::difference_type        difference_type;
 321         typedef node_pointer                            value_type;
 322         typedef node_pointer_pointer                    pointer;
 323         typedef node_pointer_reference                  reference;
 324
 325         inline
 326         iterator(node_pointer_pointer p_p_cur = 0,
 327                  node_pointer_pointer p_p_end = 0)
 328         : const_iterator(p_p_cur, p_p_end) { }
 329
 330         bool
 331         operator==(const iterator& other) const
 332         { return const_iterator::m_p_p_cur == other.m_p_p_cur; }
 333
 334         bool
 335         operator!=(const iterator& other) const
 336         { return const_iterator::m_p_p_cur != other.m_p_p_cur; }
 337
 338         iterator&
 339         operator++()
 340         {
 341           const_iterator::operator++();
 342           return *this;
 343         }
 344
 345         iterator
 346         operator++(int)
 347         {
 348           iterator ret_it(*this);
 349           operator++();
 350           return ret_it;
 351         }
 352
 353         node_pointer_pointer
 354         operator->()
 355         {
 356           _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();)
 357           return const_iterator::m_p_p_cur;
 358         }
 359
 360         node_pointer
 361         operator*()
 362         {
 363           _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();)
 364           return *const_iterator::m_p_p_cur;
 365         }
 366       };
 367
 368
 369       _Inode(size_type, const a_const_iterator);
 370
 371       void
 372       update_prefixes(a_const_pointer);
 373
 374       const_iterator
 375       begin() const;
 376
 377       iterator
 378       begin();
 379
 380       const_iterator
 381       end() const;
 382
 383       iterator
 384       end();
 385
 386       inline node_pointer
 387       get_child_node(a_const_iterator, a_const_iterator, a_const_pointer);
 388
 389       inline node_const_pointer
 390       get_child_node(a_const_iterator, a_const_iterator, a_const_pointer) const;
 391
 392       inline iterator
 393       get_child_it(a_const_iterator, a_const_iterator, a_const_pointer);
 394
 395       inline node_pointer
 396       get_lower_bound_child_node(a_const_iterator, a_const_iterator,
 397                                  size_type, a_const_pointer);
 398
 399       inline node_pointer
 400       add_child(node_pointer, a_const_iterator, a_const_iterator,
 401                 a_const_pointer);
 402
 403       inline node_const_pointer
 404       get_join_child(node_const_pointer, a_const_pointer) const;
 405
 406       inline node_pointer
 407       get_join_child(node_pointer, a_const_pointer);
 408
 409       void
 410       remove_child(node_pointer);
 411
 412       void
 413       remove_child(iterator);
 414
 415       void
 416       replace_child(node_pointer, a_const_iterator, a_const_iterator,
 417                     a_const_pointer);
 418
 419       inline a_const_iterator
 420       pref_b_it() const;
 421
 422       inline a_const_iterator
 423       pref_e_it() const;
 424
 425       bool
 426       should_be_mine(a_const_iterator, a_const_iterator, size_type,
 427                      a_const_pointer) const;
 428
 429       leaf_pointer
 430       leftmost_descendant();
 431
 432       leaf_const_pointer
 433       leftmost_descendant() const;
 434
 435       leaf_pointer
 436       rightmost_descendant();
 437
 438       leaf_const_pointer
 439       rightmost_descendant() const;
 440
 441 #ifdef _GLIBCXX_DEBUG
 442       typedef typename base_type::node_debug_info              node_debug_info;
 443
 444       virtual node_debug_info
 445       assert_valid_imp(a_const_pointer, const char*, int) const;
 446 #endif
 447
 448       size_type
 449       get_e_ind() const
 450       { return m_e_ind; }
 451
 452     private:
 453       _Inode(const _Inode&);
 454
 455       size_type
 456       get_begin_pos() const;
 457
 458       static __rebind_l                 s_leaf_alloc;
 459       static __rebind_in                s_inode_alloc;
 460
 461       const size_type                   m_e_ind;
 462       a_const_iterator                  m_pref_b_it;
 463       a_const_iterator                  m_pref_e_it;
 464       node_pointer                      m_a_p_children[arr_size];
 465     };
 466
 467 #define PB_DS_CONST_IT_C_DEC \
 468     _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
 469
 470 #define PB_DS_CONST_ODIR_IT_C_DEC \
 471     _CIter<Node, Leaf, Head, Inode, !Is_Forward_Iterator>
 472
 473 #define PB_DS_IT_C_DEC \
 474     _Iter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
 475
 476 #define PB_DS_ODIR_IT_C_DEC \
 477     _Iter<Node, Leaf, Head, Inode, !Is_Forward_Iterator>
 478
 479
 480     /// Const iterator.
 481     template<typename Node, typename Leaf, typename Head, typename Inode,
 482              bool Is_Forward_Iterator>
 483     class _CIter
 484     {
 485     public:
 486       // These types are all the same for the first four template arguments.
 487       typedef typename Node::allocator_type             allocator_type;
 488       typedef typename Node::type_traits                type_traits;
 489
 490       typedef std::bidirectional_iterator_tag           iterator_category;
 491       typedef typename allocator_type::difference_type  difference_type;
 492       typedef typename type_traits::value_type          value_type;
 493       typedef typename type_traits::pointer             pointer;
 494       typedef typename type_traits::reference           reference;
 495       typedef typename type_traits::const_pointer       const_pointer;
 496       typedef typename type_traits::const_reference     const_reference;
 497
 498       typedef allocator_type                            _Alloc;
 499       typedef typename _Alloc::template rebind<Node>    __rebind_n;
 500       typedef typename __rebind_n::other::pointer       node_pointer;
 501       typedef typename _Alloc::template rebind<Leaf>    __rebind_l;
 502       typedef typename __rebind_l::other::pointer       leaf_pointer;
 503       typedef typename __rebind_l::other::const_pointer leaf_const_pointer;
 504       typedef typename _Alloc::template rebind<Head>    __rebind_h;
 505       typedef typename __rebind_h::other::pointer       head_pointer;
 506
 507       typedef typename _Alloc::template rebind<Inode> __rebind_in;
 508       typedef typename __rebind_in::other::pointer      inode_pointer;
 509       typedef typename Inode::iterator                  inode_iterator;
 510
 511       node_pointer                                      m_p_nd;
 512
 513       _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd)
 514       { }
 515
 516       _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other)
 517       : m_p_nd(other.m_p_nd)
 518       { }
 519
 520       _CIter&
 521       operator=(const _CIter& other)
 522       {
 523         m_p_nd = other.m_p_nd;
 524         return *this;
 525       }
 526
 527       _CIter&
 528       operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
 529       {
 530         m_p_nd = other.m_p_nd;
 531         return *this;
 532       }
 533
 534       const_pointer
 535       operator->() const
 536       {
 537         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
 538         return &static_cast<leaf_pointer>(m_p_nd)->value();
 539       }
 540
 541       const_reference
 542       operator*() const
 543       {
 544         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
 545         return static_cast<leaf_pointer>(m_p_nd)->value();
 546       }
 547
 548       bool
 549       operator==(const _CIter& other) const
 550       { return m_p_nd == other.m_p_nd; }
 551
 552       bool
 553       operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
 554       { return m_p_nd == other.m_p_nd; }
 555
 556       bool
 557       operator!=(const _CIter& other) const
 558       { return m_p_nd != other.m_p_nd; }
 559
 560       bool
 561       operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
 562       { return m_p_nd != other.m_p_nd; }
 563
 564       _CIter&
 565       operator++()
 566       {
 567         inc(integral_constant<int, Is_Forward_Iterator>());
 568         return *this;
 569       }
 570
 571       _CIter
 572       operator++(int)
 573       {
 574         _CIter ret_it(m_p_nd);
 575         operator++();
 576         return ret_it;
 577       }
 578
 579       _CIter&
 580       operator--()
 581       {
 582         dec(integral_constant<int, Is_Forward_Iterator>());
 583         return *this;
 584       }
 585
 586       _CIter
 587       operator--(int)
 588       {
 589         _CIter ret_it(m_p_nd);
 590         operator--();
 591         return ret_it;
 592       }
 593
 594     protected:
 595       void
 596       inc(false_type)
 597       { dec(true_type()); }
 598
 599       void
 600       inc(true_type)
 601       {
 602         if (m_p_nd->m_type == head_node)
 603           {
 604             m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
 605             return;
 606           }
 607
 608         node_pointer p_y = m_p_nd->m_p_parent;
 609         while (p_y->m_type != head_node && get_larger_sibling(m_p_nd) == 0)
 610           {
 611             m_p_nd = p_y;
 612             p_y = p_y->m_p_parent;
 613           }
 614
 615         if (p_y->m_type == head_node)
 616           {
 617             m_p_nd = p_y;
 618             return;
 619           }
 620         m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
 621       }
 622
 623       void
 624       dec(false_type)
 625       { inc(true_type()); }
 626
 627       void
 628       dec(true_type)
 629       {
 630         if (m_p_nd->m_type == head_node)
 631           {
 632             m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
 633             return;
 634           }
 635
 636         node_pointer p_y = m_p_nd->m_p_parent;
 637         while (p_y->m_type != head_node && get_smaller_sibling(m_p_nd) == 0)
 638           {
 639             m_p_nd = p_y;
 640             p_y = p_y->m_p_parent;
 641           }
 642
 643         if (p_y->m_type == head_node)
 644           {
 645             m_p_nd = p_y;
 646             return;
 647           }
 648         m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
 649       }
 650
 651       static node_pointer
 652       get_larger_sibling(node_pointer p_nd)
 653       {
 654         inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent);
 655
 656         inode_iterator it = p_parent->begin();
 657         while (*it != p_nd)
 658           ++it;
 659
 660         inode_iterator next_it = it;
 661         ++next_it;
 662         return (next_it == p_parent->end())? 0 : *next_it;
 663       }
 664
 665       static node_pointer
 666       get_smaller_sibling(node_pointer p_nd)
 667       {
 668         inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent);
 669
 670         inode_iterator it = p_parent->begin();
 671         if (*it == p_nd)
 672           return 0;
 673
 674         inode_iterator prev_it;
 675         do
 676           {
 677             prev_it = it;
 678             ++it;
 679             if (*it == p_nd)
 680               return *prev_it;
 681           }
 682         while (true);
 683
 684         _GLIBCXX_DEBUG_ASSERT(false);
 685         return 0;
 686       }
 687
 688       static leaf_pointer
 689       leftmost_descendant(node_pointer p_nd)
 690       {
 691         if (p_nd->m_type == leaf_node)
 692           return static_cast<leaf_pointer>(p_nd);
 693         return static_cast<inode_pointer>(p_nd)->leftmost_descendant();
 694       }
 695
 696       static leaf_pointer
 697       rightmost_descendant(node_pointer p_nd)
 698       {
 699         if (p_nd->m_type == leaf_node)
 700           return static_cast<leaf_pointer>(p_nd);
 701         return static_cast<inode_pointer>(p_nd)->rightmost_descendant();
 702       }
 703     };
 704
 705
 706     /// Iterator.
 707     template<typename Node, typename Leaf, typename Head, typename Inode,
 708              bool Is_Forward_Iterator>
 709     class _Iter
 710     : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
 711     {
 712     public:
 713       typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
 714                                                         base_type;
 715       typedef typename base_type::allocator_type        allocator_type;
 716       typedef typename base_type::type_traits           type_traits;
 717       typedef typename type_traits::value_type          value_type;
 718       typedef typename type_traits::pointer             pointer;
 719       typedef typename type_traits::reference           reference;
 720
 721       typedef typename base_type::node_pointer          node_pointer;
 722       typedef typename base_type::leaf_pointer          leaf_pointer;
 723       typedef typename base_type::leaf_const_pointer    leaf_const_pointer;
 724       typedef typename base_type::head_pointer          head_pointer;
 725       typedef typename base_type::inode_pointer         inode_pointer;
 726
 727       _Iter(node_pointer p_nd = 0)
 728       : base_type(p_nd) { }
 729
 730       _Iter(const PB_DS_ODIR_IT_C_DEC& other)
 731       : base_type(other.m_p_nd) { }
 732
 733       _Iter&
 734       operator=(const _Iter& other)
 735       {
 736         base_type::m_p_nd = other.m_p_nd;
 737         return *this;
 738       }
 739
 740       _Iter&
 741       operator=(const PB_DS_ODIR_IT_C_DEC& other)
 742       {
 743         base_type::m_p_nd = other.m_p_nd;
 744         return *this;
 745       }
 746
 747       pointer
 748       operator->() const
 749       {
 750         _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
 751         return &static_cast<leaf_pointer>(base_type::m_p_nd)->value();
 752       }
 753
 754       reference
 755       operator*() const
 756       {
 757         _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
 758         return static_cast<leaf_pointer>(base_type::m_p_nd)->value();
 759       }
 760
 761       _Iter&
 762       operator++()
 763       {
 764         base_type::operator++();
 765         return *this;
 766       }
 767
 768       _Iter
 769       operator++(int)
 770       {
 771         _Iter ret(base_type::m_p_nd);
 772         operator++();
 773         return ret;
 774       }
 775
 776       _Iter&
 777       operator--()
 778       {
 779         base_type::operator--();
 780         return *this;
 781       }
 782
 783       _Iter
 784       operator--(int)
 785       {
 786         _Iter ret(base_type::m_p_nd);
 787         operator--();
 788         return ret;
 789       }
 790     };
 791
 792 #undef PB_DS_CONST_ODIR_IT_C_DEC
 793 #undef PB_DS_ODIR_IT_C_DEC
 794
 795
 796 #define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \
 797     _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
 798
 799 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \
 800     _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
 801
 802     /// Node const iterator.
 803     template<typename Node,
 804              typename Leaf,
 805              typename Head,
 806              typename Inode,
 807              typename _CIterator,
 808              typename Iterator,
 809              typename _Alloc>
 810     class _Node_citer
 811     {
 812     protected:
 813       typedef typename _Alloc::template rebind<Node>    __rebind_n;
 814       typedef typename __rebind_n::other::pointer       node_pointer;
 815
 816       typedef typename _Alloc::template rebind<Leaf>    __rebind_l;
 817       typedef typename __rebind_l::other::pointer       leaf_pointer;
 818       typedef typename __rebind_l::other::const_pointer leaf_const_pointer;
 819
 820       typedef typename _Alloc::template rebind<Inode>   __rebind_in;
 821       typedef typename __rebind_in::other::pointer      inode_pointer;
 822       typedef typename __rebind_in::other::const_pointer inode_const_pointer;
 823
 824       typedef typename Node::a_const_pointer            a_const_pointer;
 825       typedef typename Node::a_const_iterator           a_const_iterator;
 826
 827     private:
 828       a_const_iterator
 829       pref_begin() const
 830       {
 831         if (m_p_nd->m_type == leaf_node)
 832           {
 833             leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd);
 834             return m_p_traits->begin(m_p_traits->extract_key(lcp->value()));
 835           }
 836         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
 837         return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it();
 838       }
 839
 840       a_const_iterator
 841       pref_end() const
 842       {
 843         if (m_p_nd->m_type == leaf_node)
 844           {
 845             leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd);
 846             return m_p_traits->end(m_p_traits->extract_key(lcp->value()));
 847           }
 848         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
 849         return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it();
 850       }
 851
 852     public:
 853       typedef trivial_iterator_tag                      iterator_category;
 854       typedef trivial_iterator_difference_type          difference_type;
 855       typedef typename _Alloc::size_type                size_type;
 856
 857       typedef _CIterator                                value_type;
 858       typedef value_type                                reference;
 859       typedef value_type                                const_reference;
 860
 861       /// Metadata type.
 862       typedef typename Node::metadata_type              metadata_type;
 863
 864       /// Const metadata reference type.
 865       typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
 866       typedef typename __rebind_m::other                __rebind_ma;
 867       typedef typename __rebind_ma::const_reference    metadata_const_reference;
 868
 869       inline
 870       _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
 871       : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
 872       { }
 873
 874       /// Subtree valid prefix.
 875       std::pair<a_const_iterator, a_const_iterator>
 876       valid_prefix() const
 877       { return std::make_pair(pref_begin(), pref_end()); }
 878
 879       /// Const access; returns the __const iterator* associated with
 880       /// the current leaf.
 881       const_reference
 882       operator*() const
 883       {
 884         _GLIBCXX_DEBUG_ASSERT(num_children() == 0);
 885         return _CIterator(m_p_nd);
 886       }
 887
 888       /// Metadata access.
 889       metadata_const_reference
 890       get_metadata() const
 891       { return m_p_nd->get_metadata(); }
 892
 893       /// Returns the number of children in the corresponding node.
 894       size_type
 895       num_children() const
 896       {
 897         if (m_p_nd->m_type == leaf_node)
 898           return 0;
 899         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
 900         inode_pointer inp = static_cast<inode_pointer>(m_p_nd);
 901         return std::distance(inp->begin(), inp->end());
 902       }
 903
 904       /// Returns a __const node __iterator to the corresponding node's
 905       /// i-th child.
 906       _Node_citer
 907       get_child(size_type i) const
 908       {
 909         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
 910         inode_pointer inp = static_cast<inode_pointer>(m_p_nd);
 911         typename Inode::iterator it = inp->begin();
 912         std::advance(it, i);
 913         return _Node_citer(*it, m_p_traits);
 914       }
 915
 916       /// Compares content to a different iterator object.
 917       bool
 918       operator==(const _Node_citer& other) const
 919       { return m_p_nd == other.m_p_nd; }
 920
 921       /// Compares content (negatively) to a different iterator object.
 922       bool
 923       operator!=(const _Node_citer& other) const
 924       { return m_p_nd != other.m_p_nd; }
 925
 926       node_pointer                      m_p_nd;
 927       a_const_pointer                   m_p_traits;
 928     };
 929
 930
 931     /// Node iterator.
 932     template<typename Node,
 933              typename Leaf,
 934              typename Head,
 935              typename Inode,
 936              typename _CIterator,
 937              typename Iterator,
 938              typename _Alloc>
 939     class _Node_iter
 940     : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc>
 941     {
 942     private:
 943       typedef _Node_citer<Node, Leaf, Head, Inode,
 944                           _CIterator, Iterator, _Alloc> base_type;
 945       typedef typename _Alloc::template rebind<Node>    __rebind_n;
 946       typedef typename __rebind_n::other::pointer       node_pointer;
 947       typedef typename base_type::inode_pointer         inode_pointer;
 948       typedef typename base_type::a_const_pointer       a_const_pointer;
 949       typedef Iterator                                  iterator;
 950
 951     public:
 952       typedef typename base_type::size_type             size_type;
 953
 954       typedef Iterator                                  value_type;
 955       typedef value_type                                reference;
 956       typedef value_type                                const_reference;
 957
 958       _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
 959       : base_type(p_nd, p_traits)
 960       { }
 961
 962       /// Access; returns the iterator*  associated with the current leaf.
 963       reference
 964       operator*() const
 965       {
 966         _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
 967         return iterator(base_type::m_p_nd);
 968       }
 969
 970       /// Returns a node __iterator to the corresponding node's i-th child.
 971       _Node_iter
 972       get_child(size_type i) const
 973       {
 974         _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node);
 975
 976         typename Inode::iterator it =
 977           static_cast<inode_pointer>(base_type::m_p_nd)->begin();
 978
 979         std::advance(it, i);
 980         return _Node_iter(*it, base_type::m_p_traits);
 981       }
 982     };
 983     };
 984
 985
 986 #define PB_DS_CLASS_T_DEC \
 987     template<typename _ATraits, typename Metadata>
 988
 989 #define PB_DS_CLASS_C_DEC \
 990     pat_trie_base::_Inode<_ATraits, Metadata>
 991
 992     PB_DS_CLASS_T_DEC
 993     typename PB_DS_CLASS_C_DEC::__rebind_l
 994     PB_DS_CLASS_C_DEC::s_leaf_alloc;
 995
 996     PB_DS_CLASS_T_DEC
 997     typename PB_DS_CLASS_C_DEC::__rebind_in
 998     PB_DS_CLASS_C_DEC::s_inode_alloc;
 999
1000     PB_DS_CLASS_T_DEC
1001     inline typename PB_DS_CLASS_C_DEC::size_type
1002     PB_DS_CLASS_C_DEC::
1003     get_pref_pos(a_const_iterator b_it, a_const_iterator e_it,
1004                  a_const_pointer p_traits) const
1005     {
1006       if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind)
1007         return 0;
1008       std::advance(b_it, m_e_ind);
1009       return 1 + p_traits->e_pos(*b_it);
1010     }
1011
1012     PB_DS_CLASS_T_DEC
1013     PB_DS_CLASS_C_DEC::
1014     _Inode(size_type len, const a_const_iterator it)
1015     : base_type(i_node), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it)
1016     {
1017       std::advance(m_pref_e_it, m_e_ind);
1018       std::fill(m_a_p_children, m_a_p_children + arr_size,
1019                 static_cast<node_pointer>(0));
1020     }
1021
1022     PB_DS_CLASS_T_DEC
1023     void
1024     PB_DS_CLASS_C_DEC::
1025     update_prefixes(a_const_pointer p_traits)
1026     {
1027       node_pointer p_first = *begin();
1028       if (p_first->m_type == leaf_node)
1029         {
1030           leaf_const_pointer p = static_cast<leaf_const_pointer>(p_first);
1031           m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value()));
1032         }
1033       else
1034         {
1035           inode_pointer p = static_cast<inode_pointer>(p_first);
1036           _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node);
1037           m_pref_b_it = p->pref_b_it();
1038         }
1039       m_pref_e_it = m_pref_b_it;
1040       std::advance(m_pref_e_it, m_e_ind);
1041     }
1042
1043     PB_DS_CLASS_T_DEC
1044     typename PB_DS_CLASS_C_DEC::const_iterator
1045     PB_DS_CLASS_C_DEC::
1046     begin() const
1047     {
1048       typedef node_pointer_pointer pointer_type;
1049       pointer_type p = const_cast<pointer_type>(m_a_p_children);
1050       return const_iterator(p + get_begin_pos(), p + arr_size);
1051     }
1052
1053     PB_DS_CLASS_T_DEC
1054     typename PB_DS_CLASS_C_DEC::iterator
1055     PB_DS_CLASS_C_DEC::
1056     begin()
1057     {
1058       return iterator(m_a_p_children + get_begin_pos(),
1059                       m_a_p_children + arr_size);
1060     }
1061
1062     PB_DS_CLASS_T_DEC
1063     typename PB_DS_CLASS_C_DEC::const_iterator
1064     PB_DS_CLASS_C_DEC::
1065     end() const
1066     {
1067       typedef node_pointer_pointer pointer_type;
1068       pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size;
1069       return const_iterator(p, p);
1070     }
1071
1072     PB_DS_CLASS_T_DEC
1073     typename PB_DS_CLASS_C_DEC::iterator
1074     PB_DS_CLASS_C_DEC::
1075     end()
1076     { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }
1077
1078     PB_DS_CLASS_T_DEC
1079     inline typename PB_DS_CLASS_C_DEC::node_pointer
1080     PB_DS_CLASS_C_DEC::
1081     get_child_node(a_const_iterator b_it, a_const_iterator e_it,
1082                    a_const_pointer p_traits)
1083     {
1084       const size_type i = get_pref_pos(b_it, e_it, p_traits);
1085       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1086       return m_a_p_children[i];
1087     }
1088
1089     PB_DS_CLASS_T_DEC
1090     inline typename PB_DS_CLASS_C_DEC::iterator
1091     PB_DS_CLASS_C_DEC::
1092     get_child_it(a_const_iterator b_it, a_const_iterator e_it,
1093                  a_const_pointer p_traits)
1094     {
1095       const size_type i = get_pref_pos(b_it, e_it, p_traits);
1096       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1097       _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0);
1098       return iterator(m_a_p_children + i, m_a_p_children + i);
1099     }
1100
1101     PB_DS_CLASS_T_DEC
1102     inline typename PB_DS_CLASS_C_DEC::node_const_pointer
1103     PB_DS_CLASS_C_DEC::
1104     get_child_node(a_const_iterator b_it, a_const_iterator e_it,
1105                    a_const_pointer p_traits) const
1106     { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); }
1107
1108     PB_DS_CLASS_T_DEC
1109     typename PB_DS_CLASS_C_DEC::node_pointer
1110     PB_DS_CLASS_C_DEC::
1111     get_lower_bound_child_node(a_const_iterator b_it, a_const_iterator e_it,
1112                                size_type checked_ind,
1113                                a_const_pointer p_traits)
1114     {
1115       if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
1116         {
1117           if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it,
1118                                      m_pref_e_it, true))
1119             return leftmost_descendant();
1120           return rightmost_descendant();
1121         }
1122
1123       size_type i = get_pref_pos(b_it, e_it, p_traits);
1124       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1125
1126       if (m_a_p_children[i] != 0)
1127         return m_a_p_children[i];
1128
1129       while (++i < arr_size)
1130         if (m_a_p_children[i] != 0)
1131           {
1132             const node_type& __nt = m_a_p_children[i]->m_type;
1133             node_pointer ret = m_a_p_children[i];
1134
1135             if (__nt == leaf_node)
1136               return ret;
1137
1138             _GLIBCXX_DEBUG_ASSERT(__nt == i_node);
1139             inode_pointer inp = static_cast<inode_pointer>(ret);
1140             return inp->leftmost_descendant();
1141           }
1142
1143       return rightmost_descendant();
1144     }
1145
1146     PB_DS_CLASS_T_DEC
1147     inline typename PB_DS_CLASS_C_DEC::node_pointer
1148     PB_DS_CLASS_C_DEC::
1149     add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it,
1150               a_const_pointer p_traits)
1151     {
1152       const size_type i = get_pref_pos(b_it, e_it, p_traits);
1153       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1154       if (m_a_p_children[i] == 0)
1155         {
1156           m_a_p_children[i] = p_nd;
1157           p_nd->m_p_parent = this;
1158           return p_nd;
1159         }
1160       return m_a_p_children[i];
1161     }
1162
1163     PB_DS_CLASS_T_DEC
1164     typename PB_DS_CLASS_C_DEC::node_const_pointer
1165     PB_DS_CLASS_C_DEC::
1166     get_join_child(node_const_pointer p_nd,
1167                    a_const_pointer p_tr) const
1168     {
1169       node_pointer p = const_cast<node_pointer>(p_nd);
1170       return const_cast<inode_pointer>(this)->get_join_child(p, p_tr);
1171     }
1172
1173     PB_DS_CLASS_T_DEC
1174     typename PB_DS_CLASS_C_DEC::node_pointer
1175     PB_DS_CLASS_C_DEC::
1176     get_join_child(node_pointer p_nd, a_const_pointer p_traits)
1177     {
1178       size_type i;
1179       a_const_iterator b_it;
1180       a_const_iterator e_it;
1181       if (p_nd->m_type == leaf_node)
1182         {
1183           leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd);
1184
1185           typedef typename type_traits::key_const_reference kcr;
1186           kcr r_key = access_traits::extract_key(p->value());
1187           b_it = p_traits->begin(r_key);
1188           e_it = p_traits->end(r_key);
1189         }
1190       else
1191         {
1192           b_it = static_cast<inode_pointer>(p_nd)->pref_b_it();
1193           e_it = static_cast<inode_pointer>(p_nd)->pref_e_it();
1194         }
1195       i = get_pref_pos(b_it, e_it, p_traits);
1196       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1197       return m_a_p_children[i];
1198     }
1199
1200     PB_DS_CLASS_T_DEC
1201     void
1202     PB_DS_CLASS_C_DEC::
1203     remove_child(node_pointer p_nd)
1204     {
1205       size_type i = 0;
1206       for (; i < arr_size; ++i)
1207         if (m_a_p_children[i] == p_nd)
1208           {
1209             m_a_p_children[i] = 0;
1210             return;
1211           }
1212       _GLIBCXX_DEBUG_ASSERT(i != arr_size);
1213     }
1214
1215     PB_DS_CLASS_T_DEC
1216     void
1217     PB_DS_CLASS_C_DEC::
1218     remove_child(iterator it)
1219     { *it.m_p_p_cur = 0; }
1220
1221     PB_DS_CLASS_T_DEC
1222     void
1223     PB_DS_CLASS_C_DEC::
1224     replace_child(node_pointer p_nd, a_const_iterator b_it,
1225                   a_const_iterator e_it,
1226                   a_const_pointer p_traits)
1227     {
1228       const size_type i = get_pref_pos(b_it, e_it, p_traits);
1229       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1230       m_a_p_children[i] = p_nd;
1231       p_nd->m_p_parent = this;
1232     }
1233
1234     PB_DS_CLASS_T_DEC
1235     inline typename PB_DS_CLASS_C_DEC::a_const_iterator
1236     PB_DS_CLASS_C_DEC::
1237     pref_b_it() const
1238     { return m_pref_b_it; }
1239
1240     PB_DS_CLASS_T_DEC
1241     inline typename PB_DS_CLASS_C_DEC::a_const_iterator
1242     PB_DS_CLASS_C_DEC::
1243     pref_e_it() const
1244     { return m_pref_e_it; }
1245
1246     PB_DS_CLASS_T_DEC
1247     bool
1248     PB_DS_CLASS_C_DEC::
1249     should_be_mine(a_const_iterator b_it, a_const_iterator e_it,
1250                    size_type checked_ind,
1251                    a_const_pointer p_traits) const
1252     {
1253       if (m_e_ind == 0)
1254         return true;
1255
1256       const size_type num_es = std::distance(b_it, e_it);
1257       if (num_es < m_e_ind)
1258         return false;
1259
1260       a_const_iterator key_b_it = b_it;
1261       std::advance(key_b_it, checked_ind);
1262       a_const_iterator key_e_it = b_it;
1263       std::advance(key_e_it, m_e_ind);
1264
1265       a_const_iterator value_b_it = m_pref_b_it;
1266       std::advance(value_b_it, checked_ind);
1267       a_const_iterator value_e_it = m_pref_b_it;
1268       std::advance(value_e_it, m_e_ind);
1269
1270       return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it,
1271                                       value_e_it);
1272     }
1273
1274     PB_DS_CLASS_T_DEC
1275     typename PB_DS_CLASS_C_DEC::leaf_pointer
1276     PB_DS_CLASS_C_DEC::
1277     leftmost_descendant()
1278     {
1279       node_pointer p_pot = *begin();
1280       if (p_pot->m_type == leaf_node)
1281         return (static_cast<leaf_pointer>(p_pot));
1282       _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
1283       return static_cast<inode_pointer>(p_pot)->leftmost_descendant();
1284     }
1285
1286     PB_DS_CLASS_T_DEC
1287     typename PB_DS_CLASS_C_DEC::leaf_const_pointer
1288     PB_DS_CLASS_C_DEC::
1289     leftmost_descendant() const
1290     { return const_cast<inode_pointer>(this)->leftmost_descendant(); }
1291
1292     PB_DS_CLASS_T_DEC
1293     typename PB_DS_CLASS_C_DEC::leaf_pointer
1294     PB_DS_CLASS_C_DEC::
1295     rightmost_descendant()
1296     {
1297       const size_type num_children = std::distance(begin(), end());
1298       _GLIBCXX_DEBUG_ASSERT(num_children >= 2);
1299
1300       iterator it = begin();
1301       std::advance(it, num_children - 1);
1302       node_pointer p_pot =* it;
1303       if (p_pot->m_type == leaf_node)
1304         return static_cast<leaf_pointer>(p_pot);
1305       _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
1306       return static_cast<inode_pointer>(p_pot)->rightmost_descendant();
1307     }
1308
1309     PB_DS_CLASS_T_DEC
1310     typename PB_DS_CLASS_C_DEC::leaf_const_pointer
1311     PB_DS_CLASS_C_DEC::
1312     rightmost_descendant() const
1313     { return const_cast<inode_pointer>(this)->rightmost_descendant(); }
1314
1315     PB_DS_CLASS_T_DEC
1316     typename PB_DS_CLASS_C_DEC::size_type
1317     PB_DS_CLASS_C_DEC::
1318     get_begin_pos() const
1319     {
1320       size_type i = 0;
1321       for (; i < arr_size && m_a_p_children[i] == 0; ++i)
1322         ;
1323       return i;
1324     }
1325
1326 #ifdef _GLIBCXX_DEBUG
1327     PB_DS_CLASS_T_DEC
1328     typename PB_DS_CLASS_C_DEC::node_debug_info
1329     PB_DS_CLASS_C_DEC::
1330     assert_valid_imp(a_const_pointer p_traits,
1331                      const char* __file, int __line) const
1332     {
1333       PB_DS_DEBUG_VERIFY(base_type::m_type == i_node);
1334       PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind);
1335       PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2);
1336
1337       for (typename _Inode::const_iterator it = begin(); it != end(); ++it)
1338         {
1339           node_const_pointer p_nd = *it;
1340           PB_DS_DEBUG_VERIFY(p_nd->m_p_parent == this);
1341           node_debug_info child_ret = p_nd->assert_valid_imp(p_traits,
1342                                                              __file, __line);
1343
1344           PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind);
1345           PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
1346           PB_DS_DEBUG_VERIFY(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast<size_type>(it.m_p_p_cur - m_a_p_children));
1347         }
1348       return std::make_pair(pref_b_it(), pref_e_it());
1349     }
1350 #endif
1351
1352 #undef PB_DS_CLASS_T_DEC
1353 #undef PB_DS_CLASS_C_DEC
1354   } // namespace detail
1355 } // namespace __gnu_pbds
1356
1357 #endif