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

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