libstdc++
pat_trie_base.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file pat_trie_/pat_trie_base.hpp
00038  * Contains the base class for a patricia tree.
00039  */
00040 
00041 #ifndef PB_DS_PAT_TRIE_BASE
00042 #define PB_DS_PAT_TRIE_BASE
00043 
00044 #include <debug/debug.h>
00045 
00046 namespace __gnu_pbds
00047 {
00048   namespace detail
00049   {
00050     /// Base type for PATRICIA trees.
00051     struct pat_trie_base
00052     {
00053       /// Three types of nodes.
00054       enum node_type
00055     {
00056       i_node,
00057       leaf_node,
00058       head_node
00059     };
00060 
00061       /// Metadata base primary template.
00062       template<typename Metadata, typename _Alloc>
00063     struct _Metadata
00064     {
00065       typedef Metadata                      metadata_type;
00066       typedef _Alloc                        allocator_type;
00067       typedef typename _Alloc::template rebind<Metadata>    __rebind_m;
00068       typedef typename __rebind_m::other::const_reference  const_reference;
00069 
00070       const_reference
00071       get_metadata() const
00072       { return m_metadata; }
00073 
00074       metadata_type                     m_metadata;
00075     };
00076 
00077       /// Specialization for null metadata.
00078       template<typename _Alloc>
00079     struct _Metadata<null_type, _Alloc>
00080     {
00081       typedef null_type                     metadata_type;
00082       typedef _Alloc                        allocator_type;
00083     };
00084 
00085 
00086       /// Node base.
00087       template<typename _ATraits, typename Metadata>
00088       struct _Node_base
00089       : public Metadata
00090       {
00091       private:
00092     typedef typename Metadata::allocator_type       _Alloc;
00093 
00094       public:
00095     typedef _Alloc                      allocator_type;
00096     typedef _ATraits                    access_traits;
00097     typedef typename _ATraits::type_traits          type_traits;
00098     typedef typename _Alloc::template rebind<_Node_base>    __rebind_n;
00099     typedef typename __rebind_n::other::pointer         node_pointer;
00100 
00101     node_pointer                        m_p_parent;
00102     const node_type                         m_type;
00103 
00104     _Node_base(node_type type) : m_type(type)
00105     { }
00106 
00107     typedef typename _Alloc::template rebind<_ATraits>    __rebind_at;
00108     typedef typename __rebind_at::other::const_pointer    a_const_pointer;
00109     typedef typename _ATraits::const_iterator         a_const_iterator;
00110 
00111 #ifdef _GLIBCXX_DEBUG
00112     typedef std::pair<a_const_iterator, a_const_iterator> node_debug_info;
00113 
00114     void
00115     assert_valid(a_const_pointer p_traits,
00116              const char* __file, int __line) const
00117     { assert_valid_imp(p_traits, __file, __line); }
00118 
00119     virtual node_debug_info
00120     assert_valid_imp(a_const_pointer, const char*, int) const = 0;
00121 #endif
00122       };
00123 
00124 
00125     /// Head node for PATRICIA tree.
00126     template<typename _ATraits, typename Metadata>
00127     struct _Head
00128     : public _Node_base<_ATraits, Metadata>
00129     {
00130       typedef _Node_base<_ATraits, Metadata>            base_type;
00131       typedef typename base_type::type_traits           type_traits;
00132       typedef typename base_type::node_pointer          node_pointer;
00133 
00134       node_pointer                      m_p_min;
00135       node_pointer                      m_p_max;
00136 
00137       _Head() : base_type(head_node) { }
00138 
00139 #ifdef _GLIBCXX_DEBUG
00140       typedef typename base_type::node_debug_info              node_debug_info;
00141       typedef typename base_type::a_const_pointer          a_const_pointer;
00142 
00143       virtual node_debug_info
00144       assert_valid_imp(a_const_pointer, const char* __file, int __line) const
00145       {
00146     _GLIBCXX_DEBUG_VERIFY_AT(false,
00147                  _M_message("Assertion from %1;:%2;")
00148                  ._M_string(__FILE__)._M_integer(__LINE__),
00149                  __file, __line);
00150     return node_debug_info();
00151       }
00152 #endif
00153     };
00154 
00155 
00156     /// Leaf node for PATRICIA tree.
00157     template<typename _ATraits, typename Metadata>
00158     struct _Leaf
00159     : public _Node_base<_ATraits, Metadata>
00160     {
00161       typedef _Node_base<_ATraits, Metadata>                base_type;
00162       typedef typename base_type::type_traits           type_traits;
00163       typedef typename type_traits::value_type          value_type;
00164       typedef typename type_traits::reference           reference;
00165       typedef typename type_traits::const_reference         const_reference;
00166 
00167     private:
00168       value_type                        m_value;
00169 
00170       _Leaf(const _Leaf&);
00171 
00172     public:
00173       _Leaf(const_reference other)
00174       : base_type(leaf_node), m_value(other) { }
00175 
00176       reference
00177       value()
00178       { return m_value; }
00179 
00180       const_reference
00181       value() const
00182       { return m_value; }
00183 
00184 #ifdef _GLIBCXX_DEBUG
00185       typedef typename base_type::node_debug_info           node_debug_info;
00186       typedef typename base_type::a_const_pointer           a_const_pointer;
00187 
00188       virtual node_debug_info
00189       assert_valid_imp(a_const_pointer p_traits,
00190                const char* __file, int __line) const
00191       {
00192     PB_DS_DEBUG_VERIFY(base_type::m_type == leaf_node);
00193     node_debug_info ret;
00194     const_reference r_val = value();
00195     return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)),
00196                   p_traits->end(p_traits->extract_key(r_val)));
00197       }
00198 
00199       virtual
00200       ~_Leaf() { }
00201 #endif
00202     };
00203 
00204 
00205     /// Internal node type, PATRICIA tree.
00206     template<typename _ATraits, typename Metadata>
00207     struct _Inode
00208     : public _Node_base<_ATraits, Metadata>
00209     {
00210       typedef _Node_base<_ATraits, Metadata>            base_type;
00211       typedef typename base_type::type_traits           type_traits;
00212       typedef typename base_type::access_traits             access_traits;
00213       typedef typename type_traits::value_type          value_type;
00214       typedef typename base_type::allocator_type        _Alloc;
00215       typedef _Alloc                        allocator_type;
00216       typedef typename _Alloc::size_type            size_type;
00217 
00218     private:
00219       typedef typename base_type::a_const_pointer              a_const_pointer;
00220       typedef typename base_type::a_const_iterator            a_const_iterator;
00221 
00222       typedef typename base_type::node_pointer          node_pointer;
00223       typedef typename _Alloc::template rebind<base_type>   __rebind_n;
00224       typedef typename __rebind_n::other::const_pointer      node_const_pointer;
00225 
00226       typedef _Leaf<_ATraits, Metadata>             leaf;
00227       typedef typename _Alloc::template rebind<leaf>::other     __rebind_l;
00228       typedef typename __rebind_l::pointer          leaf_pointer;
00229       typedef typename __rebind_l::const_pointer        leaf_const_pointer;
00230 
00231       typedef typename _Alloc::template rebind<_Inode>::other   __rebind_in;
00232       typedef typename __rebind_in::pointer             inode_pointer;
00233       typedef typename __rebind_in::const_pointer       inode_const_pointer;
00234 
00235       inline size_type
00236       get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer) const;
00237 
00238     public:
00239       typedef typename _Alloc::template rebind<node_pointer>::other __rebind_np;
00240       typedef typename __rebind_np::pointer         node_pointer_pointer;
00241       typedef typename __rebind_np::reference       node_pointer_reference;
00242 
00243       enum
00244     {
00245       arr_size = _ATraits::max_size + 1
00246     };
00247       PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2);
00248 
00249 
00250       /// Constant child iterator.
00251       struct const_iterator
00252       {
00253     node_pointer_pointer                m_p_p_cur;
00254     node_pointer_pointer                m_p_p_end;
00255 
00256     typedef std::forward_iterator_tag       iterator_category;
00257     typedef typename _Alloc::difference_type    difference_type;
00258     typedef node_pointer                value_type;
00259     typedef node_pointer_pointer            pointer;
00260     typedef node_pointer_reference          reference;
00261 
00262     const_iterator(node_pointer_pointer p_p_cur = 0,
00263                node_pointer_pointer p_p_end = 0)
00264     : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end)
00265     { }
00266 
00267     bool
00268     operator==(const const_iterator& other) const
00269     { return m_p_p_cur == other.m_p_p_cur; }
00270 
00271     bool
00272     operator!=(const const_iterator& other) const
00273     { return m_p_p_cur != other.m_p_p_cur; }
00274 
00275     const_iterator&
00276     operator++()
00277     {
00278       do
00279         ++m_p_p_cur;
00280       while (m_p_p_cur != m_p_p_end && *m_p_p_cur == 0);
00281       return *this;
00282     }
00283 
00284     const_iterator
00285     operator++(int)
00286     {
00287       const_iterator ret_it(*this);
00288       operator++();
00289       return ret_it;
00290     }
00291 
00292     const node_pointer_pointer
00293     operator->() const
00294     {
00295       _GLIBCXX_DEBUG_ONLY(assert_referencible();)
00296       return m_p_p_cur;
00297     }
00298 
00299     node_const_pointer
00300     operator*() const
00301     {
00302       _GLIBCXX_DEBUG_ONLY(assert_referencible();)
00303       return *m_p_p_cur;
00304     }
00305 
00306       protected:
00307 #ifdef _GLIBCXX_DEBUG
00308     void
00309     assert_referencible() const
00310     { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end && *m_p_p_cur != 0); }
00311 #endif
00312       };
00313 
00314 
00315       /// Child iterator.
00316       struct iterator : public const_iterator
00317       {
00318       public:
00319     typedef std::forward_iterator_tag       iterator_category;
00320     typedef typename _Alloc::difference_type    difference_type;
00321     typedef node_pointer                value_type;
00322     typedef node_pointer_pointer            pointer;
00323     typedef node_pointer_reference          reference;
00324 
00325     inline
00326     iterator(node_pointer_pointer p_p_cur = 0,
00327          node_pointer_pointer p_p_end = 0)
00328     : const_iterator(p_p_cur, p_p_end) { }
00329 
00330     bool
00331     operator==(const iterator& other) const
00332     { return const_iterator::m_p_p_cur == other.m_p_p_cur; }
00333 
00334     bool
00335     operator!=(const iterator& other) const
00336     { return const_iterator::m_p_p_cur != other.m_p_p_cur; }
00337 
00338     iterator&
00339     operator++()
00340     {
00341       const_iterator::operator++();
00342       return *this;
00343     }
00344 
00345     iterator
00346     operator++(int)
00347     {
00348       iterator ret_it(*this);
00349       operator++();
00350       return ret_it;
00351     }
00352 
00353     node_pointer_pointer
00354     operator->()
00355     {
00356       _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();)
00357       return const_iterator::m_p_p_cur;
00358     }
00359 
00360     node_pointer
00361     operator*()
00362     {
00363       _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();)
00364       return *const_iterator::m_p_p_cur;
00365     }
00366       };
00367 
00368 
00369       _Inode(size_type, const a_const_iterator);
00370 
00371       void
00372       update_prefixes(a_const_pointer);
00373 
00374       const_iterator
00375       begin() const;
00376 
00377       iterator
00378       begin();
00379 
00380       const_iterator
00381       end() const;
00382 
00383       iterator
00384       end();
00385 
00386       inline node_pointer
00387       get_child_node(a_const_iterator, a_const_iterator, a_const_pointer);
00388 
00389       inline node_const_pointer
00390       get_child_node(a_const_iterator, a_const_iterator, a_const_pointer) const;
00391 
00392       inline iterator
00393       get_child_it(a_const_iterator, a_const_iterator, a_const_pointer);
00394 
00395       inline node_pointer
00396       get_lower_bound_child_node(a_const_iterator, a_const_iterator,
00397                  size_type, a_const_pointer);
00398 
00399       inline node_pointer
00400       add_child(node_pointer, a_const_iterator, a_const_iterator,
00401         a_const_pointer);
00402 
00403       inline node_const_pointer
00404       get_join_child(node_const_pointer, a_const_pointer) const;
00405 
00406       inline node_pointer
00407       get_join_child(node_pointer, a_const_pointer);
00408 
00409       void
00410       remove_child(node_pointer);
00411 
00412       void
00413       remove_child(iterator);
00414 
00415       void
00416       replace_child(node_pointer, a_const_iterator, a_const_iterator,
00417             a_const_pointer);
00418 
00419       inline a_const_iterator
00420       pref_b_it() const;
00421 
00422       inline a_const_iterator
00423       pref_e_it() const;
00424 
00425       bool
00426       should_be_mine(a_const_iterator, a_const_iterator, size_type,
00427              a_const_pointer) const;
00428 
00429       leaf_pointer
00430       leftmost_descendant();
00431 
00432       leaf_const_pointer
00433       leftmost_descendant() const;
00434 
00435       leaf_pointer
00436       rightmost_descendant();
00437 
00438       leaf_const_pointer
00439       rightmost_descendant() const;
00440 
00441 #ifdef _GLIBCXX_DEBUG
00442       typedef typename base_type::node_debug_info          node_debug_info;
00443 
00444       virtual node_debug_info
00445       assert_valid_imp(a_const_pointer, const char*, int) const;
00446 #endif
00447 
00448       size_type
00449       get_e_ind() const
00450       { return m_e_ind; }
00451 
00452     private:
00453       _Inode(const _Inode&);
00454 
00455       size_type
00456       get_begin_pos() const;
00457 
00458       static __rebind_l         s_leaf_alloc;
00459       static __rebind_in        s_inode_alloc;
00460 
00461       const size_type           m_e_ind;
00462       a_const_iterator          m_pref_b_it;
00463       a_const_iterator          m_pref_e_it;
00464       node_pointer          m_a_p_children[arr_size];
00465     };
00466 
00467 #define PB_DS_CONST_IT_C_DEC \
00468     _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
00469 
00470 #define PB_DS_CONST_ODIR_IT_C_DEC \
00471     _CIter<Node, Leaf, Head, Inode, !Is_Forward_Iterator>
00472 
00473 #define PB_DS_IT_C_DEC \
00474     _Iter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
00475 
00476 #define PB_DS_ODIR_IT_C_DEC \
00477     _Iter<Node, Leaf, Head, Inode, !Is_Forward_Iterator>
00478 
00479 
00480     /// Const iterator.
00481     template<typename Node, typename Leaf, typename Head, typename Inode,
00482          bool Is_Forward_Iterator>
00483     class _CIter
00484     {
00485     public:
00486       // These types are all the same for the first four template arguments.
00487       typedef typename Node::allocator_type     allocator_type;
00488       typedef typename Node::type_traits        type_traits;
00489 
00490       typedef std::bidirectional_iterator_tag       iterator_category;
00491       typedef typename allocator_type::difference_type  difference_type;
00492       typedef typename type_traits::value_type      value_type;
00493       typedef typename type_traits::pointer         pointer;
00494       typedef typename type_traits::reference       reference;
00495       typedef typename type_traits::const_pointer   const_pointer;
00496       typedef typename type_traits::const_reference     const_reference;
00497 
00498       typedef allocator_type                _Alloc;
00499       typedef typename _Alloc::template rebind<Node>    __rebind_n;
00500       typedef typename __rebind_n::other::pointer   node_pointer;
00501       typedef typename _Alloc::template rebind<Leaf>    __rebind_l;
00502       typedef typename __rebind_l::other::pointer   leaf_pointer;
00503       typedef typename __rebind_l::other::const_pointer leaf_const_pointer;
00504       typedef typename _Alloc::template rebind<Head>    __rebind_h;
00505       typedef typename __rebind_h::other::pointer   head_pointer;
00506 
00507       typedef typename _Alloc::template rebind<Inode> __rebind_in;
00508       typedef typename __rebind_in::other::pointer  inode_pointer;
00509       typedef typename Inode::iterator          inode_iterator;
00510 
00511       node_pointer                  m_p_nd;
00512 
00513       _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd)
00514       { }
00515 
00516       _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other)
00517       : m_p_nd(other.m_p_nd)
00518       { }
00519 
00520       _CIter&
00521       operator=(const _CIter& other)
00522       {
00523     m_p_nd = other.m_p_nd;
00524     return *this;
00525       }
00526 
00527       _CIter&
00528       operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
00529       {
00530     m_p_nd = other.m_p_nd;
00531     return *this;
00532       }
00533 
00534       const_pointer
00535       operator->() const
00536       {
00537     _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
00538     return &static_cast<leaf_pointer>(m_p_nd)->value();
00539       }
00540 
00541       const_reference
00542       operator*() const
00543       {
00544     _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
00545     return static_cast<leaf_pointer>(m_p_nd)->value();
00546       }
00547 
00548       bool
00549       operator==(const _CIter& other) const
00550       { return m_p_nd == other.m_p_nd; }
00551 
00552       bool
00553       operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
00554       { return m_p_nd == other.m_p_nd; }
00555 
00556       bool
00557       operator!=(const _CIter& other) const
00558       { return m_p_nd != other.m_p_nd; }
00559 
00560       bool
00561       operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
00562       { return m_p_nd != other.m_p_nd; }
00563 
00564       _CIter&
00565       operator++()
00566       {
00567     inc(integral_constant<int, Is_Forward_Iterator>());
00568     return *this;
00569       }
00570 
00571       _CIter
00572       operator++(int)
00573       {
00574     _CIter ret_it(m_p_nd);
00575     operator++();
00576     return ret_it;
00577       }
00578 
00579       _CIter&
00580       operator--()
00581       {
00582     dec(integral_constant<int, Is_Forward_Iterator>());
00583     return *this;
00584       }
00585 
00586       _CIter
00587       operator--(int)
00588       {
00589     _CIter ret_it(m_p_nd);
00590     operator--();
00591     return ret_it;
00592       }
00593 
00594     protected:
00595       void
00596       inc(false_type)
00597       { dec(true_type()); }
00598 
00599       void
00600       inc(true_type)
00601       {
00602     if (m_p_nd->m_type == head_node)
00603       {
00604         m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
00605         return;
00606       }
00607 
00608     node_pointer p_y = m_p_nd->m_p_parent;
00609     while (p_y->m_type != head_node && get_larger_sibling(m_p_nd) == 0)
00610       {
00611         m_p_nd = p_y;
00612         p_y = p_y->m_p_parent;
00613       }
00614 
00615     if (p_y->m_type == head_node)
00616       {
00617         m_p_nd = p_y;
00618         return;
00619       }
00620     m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
00621       }
00622 
00623       void
00624       dec(false_type)
00625       { inc(true_type()); }
00626 
00627       void
00628       dec(true_type)
00629       {
00630     if (m_p_nd->m_type == head_node)
00631       {
00632         m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
00633         return;
00634       }
00635 
00636     node_pointer p_y = m_p_nd->m_p_parent;
00637     while (p_y->m_type != head_node && get_smaller_sibling(m_p_nd) == 0)
00638       {
00639         m_p_nd = p_y;
00640         p_y = p_y->m_p_parent;
00641       }
00642 
00643     if (p_y->m_type == head_node)
00644       {
00645         m_p_nd = p_y;
00646         return;
00647       }
00648     m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
00649       }
00650 
00651       static node_pointer
00652       get_larger_sibling(node_pointer p_nd)
00653       {
00654     inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent);
00655 
00656     inode_iterator it = p_parent->begin();
00657     while (*it != p_nd)
00658       ++it;
00659 
00660     inode_iterator next_it = it;
00661     ++next_it;
00662     return (next_it == p_parent->end())? 0 : *next_it;
00663       }
00664 
00665       static node_pointer
00666       get_smaller_sibling(node_pointer p_nd)
00667       {
00668     inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent);
00669 
00670     inode_iterator it = p_parent->begin();
00671     if (*it == p_nd)
00672       return 0;
00673 
00674     inode_iterator prev_it;
00675     do
00676       {
00677         prev_it = it;
00678         ++it;
00679         if (*it == p_nd)
00680           return *prev_it;
00681       }
00682     while (true);
00683 
00684     _GLIBCXX_DEBUG_ASSERT(false);
00685     return 0;
00686       }
00687 
00688       static leaf_pointer
00689       leftmost_descendant(node_pointer p_nd)
00690       {
00691     if (p_nd->m_type == leaf_node)
00692       return static_cast<leaf_pointer>(p_nd);
00693     return static_cast<inode_pointer>(p_nd)->leftmost_descendant();
00694       }
00695 
00696       static leaf_pointer
00697       rightmost_descendant(node_pointer p_nd)
00698       {
00699     if (p_nd->m_type == leaf_node)
00700       return static_cast<leaf_pointer>(p_nd);
00701     return static_cast<inode_pointer>(p_nd)->rightmost_descendant();
00702       }
00703     };
00704 
00705 
00706     /// Iterator.
00707     template<typename Node, typename Leaf, typename Head, typename Inode,
00708          bool Is_Forward_Iterator>
00709     class _Iter
00710     : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
00711     {
00712     public:
00713       typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
00714                                 base_type;
00715       typedef typename base_type::allocator_type    allocator_type;
00716       typedef typename base_type::type_traits       type_traits;
00717       typedef typename type_traits::value_type      value_type;
00718       typedef typename type_traits::pointer         pointer;
00719       typedef typename type_traits::reference       reference;
00720 
00721       typedef typename base_type::node_pointer      node_pointer;
00722       typedef typename base_type::leaf_pointer      leaf_pointer;
00723       typedef typename base_type::leaf_const_pointer    leaf_const_pointer;
00724       typedef typename base_type::head_pointer      head_pointer;
00725       typedef typename base_type::inode_pointer     inode_pointer;
00726 
00727       _Iter(node_pointer p_nd = 0)
00728       : base_type(p_nd) { }
00729 
00730       _Iter(const PB_DS_ODIR_IT_C_DEC& other)
00731       : base_type(other.m_p_nd) { }
00732 
00733       _Iter&
00734       operator=(const _Iter& other)
00735       {
00736     base_type::m_p_nd = other.m_p_nd;
00737     return *this;
00738       }
00739 
00740       _Iter&
00741       operator=(const PB_DS_ODIR_IT_C_DEC& other)
00742       {
00743     base_type::m_p_nd = other.m_p_nd;
00744     return *this;
00745       }
00746 
00747       pointer
00748       operator->() const
00749       {
00750     _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
00751     return &static_cast<leaf_pointer>(base_type::m_p_nd)->value();
00752       }
00753 
00754       reference
00755       operator*() const
00756       {
00757     _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
00758     return static_cast<leaf_pointer>(base_type::m_p_nd)->value();
00759       }
00760 
00761       _Iter&
00762       operator++()
00763       {
00764     base_type::operator++();
00765     return *this;
00766       }
00767 
00768       _Iter
00769       operator++(int)
00770       {
00771     _Iter ret(base_type::m_p_nd);
00772     operator++();
00773     return ret;
00774       }
00775 
00776       _Iter&
00777       operator--()
00778       {
00779     base_type::operator--();
00780     return *this;
00781       }
00782 
00783       _Iter
00784       operator--(int)
00785       {
00786     _Iter ret(base_type::m_p_nd);
00787     operator--();
00788     return ret;
00789       }
00790     };
00791 
00792 #undef PB_DS_CONST_ODIR_IT_C_DEC
00793 #undef PB_DS_ODIR_IT_C_DEC
00794 
00795 
00796 #define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \
00797     _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
00798 
00799 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \
00800     _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
00801 
00802     /// Node const iterator.
00803     template<typename Node,
00804          typename Leaf,
00805          typename Head,
00806          typename Inode,
00807          typename _CIterator,
00808          typename Iterator,
00809          typename _Alloc>
00810     class _Node_citer
00811     {
00812     protected:
00813       typedef typename _Alloc::template rebind<Node>    __rebind_n;
00814       typedef typename __rebind_n::other::pointer   node_pointer;
00815 
00816       typedef typename _Alloc::template rebind<Leaf>    __rebind_l;
00817       typedef typename __rebind_l::other::pointer   leaf_pointer;
00818       typedef typename __rebind_l::other::const_pointer leaf_const_pointer;
00819 
00820       typedef typename _Alloc::template rebind<Inode>   __rebind_in;
00821       typedef typename __rebind_in::other::pointer  inode_pointer;
00822       typedef typename __rebind_in::other::const_pointer inode_const_pointer;
00823 
00824       typedef typename Node::a_const_pointer        a_const_pointer;
00825       typedef typename Node::a_const_iterator       a_const_iterator;
00826 
00827     private:
00828       a_const_iterator
00829       pref_begin() const
00830       {
00831     if (m_p_nd->m_type == leaf_node)
00832       {
00833         leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd);
00834         return m_p_traits->begin(m_p_traits->extract_key(lcp->value()));
00835       }
00836     _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
00837     return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it();
00838       }
00839 
00840       a_const_iterator
00841       pref_end() const
00842       {
00843     if (m_p_nd->m_type == leaf_node)
00844       {
00845         leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd);
00846         return m_p_traits->end(m_p_traits->extract_key(lcp->value()));
00847       }
00848     _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
00849     return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it();
00850       }
00851 
00852     public:
00853       typedef trivial_iterator_tag          iterator_category;
00854       typedef trivial_iterator_difference_type      difference_type;
00855       typedef typename _Alloc::size_type        size_type;
00856 
00857       typedef _CIterator                    value_type;
00858       typedef value_type                reference;
00859       typedef value_type                const_reference;
00860 
00861       /// Metadata type.
00862       typedef typename Node::metadata_type      metadata_type;
00863 
00864       /// Const metadata reference type.
00865       typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
00866       typedef typename __rebind_m::other        __rebind_ma;
00867       typedef typename __rebind_ma::const_reference    metadata_const_reference;
00868 
00869       inline
00870       _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
00871       : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
00872       { }
00873 
00874       /// Subtree valid prefix.
00875       std::pair<a_const_iterator, a_const_iterator>
00876       valid_prefix() const
00877       { return std::make_pair(pref_begin(), pref_end()); }
00878 
00879       /// Const access; returns the __const iterator* associated with
00880       /// the current leaf.
00881       const_reference
00882       operator*() const
00883       {
00884     _GLIBCXX_DEBUG_ASSERT(num_children() == 0);
00885     return _CIterator(m_p_nd);
00886       }
00887 
00888       /// Metadata access.
00889       metadata_const_reference
00890       get_metadata() const
00891       { return m_p_nd->get_metadata(); }
00892 
00893       /// Returns the number of children in the corresponding node.
00894       size_type
00895       num_children() const
00896       {
00897     if (m_p_nd->m_type == leaf_node)
00898       return 0;
00899     _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
00900     inode_pointer inp = static_cast<inode_pointer>(m_p_nd);
00901     return std::distance(inp->begin(), inp->end());
00902       }
00903 
00904       /// Returns a __const node __iterator to the corresponding node's
00905       /// i-th child.
00906       _Node_citer
00907       get_child(size_type i) const
00908       {
00909     _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
00910     inode_pointer inp = static_cast<inode_pointer>(m_p_nd);
00911     typename Inode::iterator it = inp->begin();
00912     std::advance(it, i);
00913     return _Node_citer(*it, m_p_traits);
00914       }
00915 
00916       /// Compares content to a different iterator object.
00917       bool
00918       operator==(const _Node_citer& other) const
00919       { return m_p_nd == other.m_p_nd; }
00920 
00921       /// Compares content (negatively) to a different iterator object.
00922       bool
00923       operator!=(const _Node_citer& other) const
00924       { return m_p_nd != other.m_p_nd; }
00925 
00926       node_pointer          m_p_nd;
00927       a_const_pointer           m_p_traits;
00928     };
00929 
00930 
00931     /// Node iterator.
00932     template<typename Node,
00933          typename Leaf,
00934          typename Head,
00935          typename Inode,
00936          typename _CIterator,
00937          typename Iterator,
00938          typename _Alloc>
00939     class _Node_iter
00940     : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc>
00941     {
00942     private:
00943       typedef _Node_citer<Node, Leaf, Head, Inode,
00944               _CIterator, Iterator, _Alloc> base_type;
00945       typedef typename _Alloc::template rebind<Node>    __rebind_n;
00946       typedef typename __rebind_n::other::pointer   node_pointer;
00947       typedef typename base_type::inode_pointer     inode_pointer;
00948       typedef typename base_type::a_const_pointer   a_const_pointer;
00949       typedef Iterator                  iterator;
00950 
00951     public:
00952       typedef typename base_type::size_type         size_type;
00953 
00954       typedef Iterator                  value_type;
00955       typedef value_type                reference;
00956       typedef value_type                const_reference;
00957 
00958       _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
00959       : base_type(p_nd, p_traits)
00960       { }
00961 
00962       /// Access; returns the iterator*  associated with the current leaf.
00963       reference
00964       operator*() const
00965       {
00966     _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
00967     return iterator(base_type::m_p_nd);
00968       }
00969 
00970       /// Returns a node __iterator to the corresponding node's i-th child.
00971       _Node_iter
00972       get_child(size_type i) const
00973       {
00974     _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node);
00975 
00976     typename Inode::iterator it =
00977       static_cast<inode_pointer>(base_type::m_p_nd)->begin();
00978 
00979     std::advance(it, i);
00980     return _Node_iter(*it, base_type::m_p_traits);
00981       }
00982     };
00983     };
00984 
00985 
00986 #define PB_DS_CLASS_T_DEC \
00987     template<typename _ATraits, typename Metadata>
00988 
00989 #define PB_DS_CLASS_C_DEC \
00990     pat_trie_base::_Inode<_ATraits, Metadata>
00991 
00992     PB_DS_CLASS_T_DEC
00993     typename PB_DS_CLASS_C_DEC::__rebind_l
00994     PB_DS_CLASS_C_DEC::s_leaf_alloc;
00995 
00996     PB_DS_CLASS_T_DEC
00997     typename PB_DS_CLASS_C_DEC::__rebind_in
00998     PB_DS_CLASS_C_DEC::s_inode_alloc;
00999 
01000     PB_DS_CLASS_T_DEC
01001     inline typename PB_DS_CLASS_C_DEC::size_type
01002     PB_DS_CLASS_C_DEC::
01003     get_pref_pos(a_const_iterator b_it, a_const_iterator e_it,
01004          a_const_pointer p_traits) const
01005     {
01006       if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind)
01007     return 0;
01008       std::advance(b_it, m_e_ind);
01009       return 1 + p_traits->e_pos(*b_it);
01010     }
01011 
01012     PB_DS_CLASS_T_DEC
01013     PB_DS_CLASS_C_DEC::
01014     _Inode(size_type len, const a_const_iterator it)
01015     : base_type(i_node), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it)
01016     {
01017       std::advance(m_pref_e_it, m_e_ind);
01018       std::fill(m_a_p_children, m_a_p_children + arr_size,
01019         static_cast<node_pointer>(0));
01020     }
01021 
01022     PB_DS_CLASS_T_DEC
01023     void
01024     PB_DS_CLASS_C_DEC::
01025     update_prefixes(a_const_pointer p_traits)
01026     {
01027       node_pointer p_first = *begin();
01028       if (p_first->m_type == leaf_node)
01029     {
01030       leaf_const_pointer p = static_cast<leaf_const_pointer>(p_first);
01031       m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value()));
01032     }
01033       else
01034     {
01035       inode_pointer p = static_cast<inode_pointer>(p_first);
01036       _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node);
01037       m_pref_b_it = p->pref_b_it();
01038     }
01039       m_pref_e_it = m_pref_b_it;
01040       std::advance(m_pref_e_it, m_e_ind);
01041     }
01042 
01043     PB_DS_CLASS_T_DEC
01044     typename PB_DS_CLASS_C_DEC::const_iterator
01045     PB_DS_CLASS_C_DEC::
01046     begin() const
01047     {
01048       typedef node_pointer_pointer pointer_type;
01049       pointer_type p = const_cast<pointer_type>(m_a_p_children);
01050       return const_iterator(p + get_begin_pos(), p + arr_size);
01051     }
01052 
01053     PB_DS_CLASS_T_DEC
01054     typename PB_DS_CLASS_C_DEC::iterator
01055     PB_DS_CLASS_C_DEC::
01056     begin()
01057     {
01058       return iterator(m_a_p_children + get_begin_pos(),
01059               m_a_p_children + arr_size);
01060     }
01061 
01062     PB_DS_CLASS_T_DEC
01063     typename PB_DS_CLASS_C_DEC::const_iterator
01064     PB_DS_CLASS_C_DEC::
01065     end() const
01066     {
01067       typedef node_pointer_pointer pointer_type;
01068       pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size;
01069       return const_iterator(p, p);
01070     }
01071 
01072     PB_DS_CLASS_T_DEC
01073     typename PB_DS_CLASS_C_DEC::iterator
01074     PB_DS_CLASS_C_DEC::
01075     end()
01076     { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }
01077 
01078     PB_DS_CLASS_T_DEC
01079     inline typename PB_DS_CLASS_C_DEC::node_pointer
01080     PB_DS_CLASS_C_DEC::
01081     get_child_node(a_const_iterator b_it, a_const_iterator e_it,
01082            a_const_pointer p_traits)
01083     {
01084       const size_type i = get_pref_pos(b_it, e_it, p_traits);
01085       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
01086       return m_a_p_children[i];
01087     }
01088 
01089     PB_DS_CLASS_T_DEC
01090     inline typename PB_DS_CLASS_C_DEC::iterator
01091     PB_DS_CLASS_C_DEC::
01092     get_child_it(a_const_iterator b_it, a_const_iterator e_it,
01093          a_const_pointer p_traits)
01094     {
01095       const size_type i = get_pref_pos(b_it, e_it, p_traits);
01096       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
01097       _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0);
01098       return iterator(m_a_p_children + i, m_a_p_children + i);
01099     }
01100 
01101     PB_DS_CLASS_T_DEC
01102     inline typename PB_DS_CLASS_C_DEC::node_const_pointer
01103     PB_DS_CLASS_C_DEC::
01104     get_child_node(a_const_iterator b_it, a_const_iterator e_it,
01105            a_const_pointer p_traits) const
01106     { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); }
01107 
01108     PB_DS_CLASS_T_DEC
01109     typename PB_DS_CLASS_C_DEC::node_pointer
01110     PB_DS_CLASS_C_DEC::
01111     get_lower_bound_child_node(a_const_iterator b_it, a_const_iterator e_it,
01112                    size_type checked_ind,
01113                    a_const_pointer p_traits)
01114     {
01115       if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
01116     {
01117       if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it,
01118                      m_pref_e_it, true))
01119         return leftmost_descendant();
01120       return rightmost_descendant();
01121     }
01122 
01123       size_type i = get_pref_pos(b_it, e_it, p_traits);
01124       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
01125 
01126       if (m_a_p_children[i] != 0)
01127     return m_a_p_children[i];
01128 
01129       while (++i < arr_size)
01130     if (m_a_p_children[i] != 0)
01131       {
01132         const node_type& __nt = m_a_p_children[i]->m_type;
01133         node_pointer ret = m_a_p_children[i];
01134 
01135         if (__nt == leaf_node)
01136           return ret;
01137 
01138         _GLIBCXX_DEBUG_ASSERT(__nt == i_node);
01139         inode_pointer inp = static_cast<inode_pointer>(ret);
01140         return inp->leftmost_descendant();
01141       }
01142 
01143       return rightmost_descendant();
01144     }
01145 
01146     PB_DS_CLASS_T_DEC
01147     inline typename PB_DS_CLASS_C_DEC::node_pointer
01148     PB_DS_CLASS_C_DEC::
01149     add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it,
01150           a_const_pointer p_traits)
01151     {
01152       const size_type i = get_pref_pos(b_it, e_it, p_traits);
01153       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
01154       if (m_a_p_children[i] == 0)
01155     {
01156       m_a_p_children[i] = p_nd;
01157       p_nd->m_p_parent = this;
01158       return p_nd;
01159     }
01160       return m_a_p_children[i];
01161     }
01162 
01163     PB_DS_CLASS_T_DEC
01164     typename PB_DS_CLASS_C_DEC::node_const_pointer
01165     PB_DS_CLASS_C_DEC::
01166     get_join_child(node_const_pointer p_nd,
01167            a_const_pointer p_tr) const
01168     {
01169       node_pointer p = const_cast<node_pointer>(p_nd);
01170       return const_cast<inode_pointer>(this)->get_join_child(p, p_tr);
01171     }
01172 
01173     PB_DS_CLASS_T_DEC
01174     typename PB_DS_CLASS_C_DEC::node_pointer
01175     PB_DS_CLASS_C_DEC::
01176     get_join_child(node_pointer p_nd, a_const_pointer p_traits)
01177     {
01178       size_type i;
01179       a_const_iterator b_it;
01180       a_const_iterator e_it;
01181       if (p_nd->m_type == leaf_node)
01182     {
01183       leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd);
01184 
01185       typedef typename type_traits::key_const_reference kcr;
01186       kcr r_key = access_traits::extract_key(p->value());
01187       b_it = p_traits->begin(r_key);
01188       e_it = p_traits->end(r_key);
01189     }
01190       else
01191     {
01192       b_it = static_cast<inode_pointer>(p_nd)->pref_b_it();
01193       e_it = static_cast<inode_pointer>(p_nd)->pref_e_it();
01194     }
01195       i = get_pref_pos(b_it, e_it, p_traits);
01196       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
01197       return m_a_p_children[i];
01198     }
01199 
01200     PB_DS_CLASS_T_DEC
01201     void
01202     PB_DS_CLASS_C_DEC::
01203     remove_child(node_pointer p_nd)
01204     {
01205       size_type i = 0;
01206       for (; i < arr_size; ++i)
01207     if (m_a_p_children[i] == p_nd)
01208       {
01209         m_a_p_children[i] = 0;
01210         return;
01211       }
01212       _GLIBCXX_DEBUG_ASSERT(i != arr_size);
01213     }
01214 
01215     PB_DS_CLASS_T_DEC
01216     void
01217     PB_DS_CLASS_C_DEC::
01218     remove_child(iterator it)
01219     { *it.m_p_p_cur = 0; }
01220 
01221     PB_DS_CLASS_T_DEC
01222     void
01223     PB_DS_CLASS_C_DEC::
01224     replace_child(node_pointer p_nd, a_const_iterator b_it,
01225           a_const_iterator e_it,
01226           a_const_pointer p_traits)
01227     {
01228       const size_type i = get_pref_pos(b_it, e_it, p_traits);
01229       _GLIBCXX_DEBUG_ASSERT(i < arr_size);
01230       m_a_p_children[i] = p_nd;
01231       p_nd->m_p_parent = this;
01232     }
01233 
01234     PB_DS_CLASS_T_DEC
01235     inline typename PB_DS_CLASS_C_DEC::a_const_iterator
01236     PB_DS_CLASS_C_DEC::
01237     pref_b_it() const
01238     { return m_pref_b_it; }
01239 
01240     PB_DS_CLASS_T_DEC
01241     inline typename PB_DS_CLASS_C_DEC::a_const_iterator
01242     PB_DS_CLASS_C_DEC::
01243     pref_e_it() const
01244     { return m_pref_e_it; }
01245 
01246     PB_DS_CLASS_T_DEC
01247     bool
01248     PB_DS_CLASS_C_DEC::
01249     should_be_mine(a_const_iterator b_it, a_const_iterator e_it,
01250            size_type checked_ind,
01251            a_const_pointer p_traits) const
01252     {
01253       if (m_e_ind == 0)
01254     return true;
01255 
01256       const size_type num_es = std::distance(b_it, e_it);
01257       if (num_es < m_e_ind)
01258     return false;
01259 
01260       a_const_iterator key_b_it = b_it;
01261       std::advance(key_b_it, checked_ind);
01262       a_const_iterator key_e_it = b_it;
01263       std::advance(key_e_it, m_e_ind);
01264 
01265       a_const_iterator value_b_it = m_pref_b_it;
01266       std::advance(value_b_it, checked_ind);
01267       a_const_iterator value_e_it = m_pref_b_it;
01268       std::advance(value_e_it, m_e_ind);
01269 
01270       return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it,
01271                       value_e_it);
01272     }
01273 
01274     PB_DS_CLASS_T_DEC
01275     typename PB_DS_CLASS_C_DEC::leaf_pointer
01276     PB_DS_CLASS_C_DEC::
01277     leftmost_descendant()
01278     {
01279       node_pointer p_pot = *begin();
01280       if (p_pot->m_type == leaf_node)
01281     return (static_cast<leaf_pointer>(p_pot));
01282       _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
01283       return static_cast<inode_pointer>(p_pot)->leftmost_descendant();
01284     }
01285 
01286     PB_DS_CLASS_T_DEC
01287     typename PB_DS_CLASS_C_DEC::leaf_const_pointer
01288     PB_DS_CLASS_C_DEC::
01289     leftmost_descendant() const
01290     { return const_cast<inode_pointer>(this)->leftmost_descendant(); }
01291 
01292     PB_DS_CLASS_T_DEC
01293     typename PB_DS_CLASS_C_DEC::leaf_pointer
01294     PB_DS_CLASS_C_DEC::
01295     rightmost_descendant()
01296     {
01297       const size_type num_children = std::distance(begin(), end());
01298       _GLIBCXX_DEBUG_ASSERT(num_children >= 2);
01299 
01300       iterator it = begin();
01301       std::advance(it, num_children - 1);
01302       node_pointer p_pot =* it;
01303       if (p_pot->m_type == leaf_node)
01304     return static_cast<leaf_pointer>(p_pot);
01305       _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
01306       return static_cast<inode_pointer>(p_pot)->rightmost_descendant();
01307     }
01308 
01309     PB_DS_CLASS_T_DEC
01310     typename PB_DS_CLASS_C_DEC::leaf_const_pointer
01311     PB_DS_CLASS_C_DEC::
01312     rightmost_descendant() const
01313     { return const_cast<inode_pointer>(this)->rightmost_descendant(); }
01314 
01315     PB_DS_CLASS_T_DEC
01316     typename PB_DS_CLASS_C_DEC::size_type
01317     PB_DS_CLASS_C_DEC::
01318     get_begin_pos() const
01319     {
01320       size_type i = 0;
01321       for (; i < arr_size && m_a_p_children[i] == 0; ++i)
01322     ;
01323       return i;
01324     }
01325 
01326 #ifdef _GLIBCXX_DEBUG
01327     PB_DS_CLASS_T_DEC
01328     typename PB_DS_CLASS_C_DEC::node_debug_info
01329     PB_DS_CLASS_C_DEC::
01330     assert_valid_imp(a_const_pointer p_traits,
01331              const char* __file, int __line) const
01332     {
01333       PB_DS_DEBUG_VERIFY(base_type::m_type == i_node);
01334       PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind);
01335       PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2);
01336 
01337       for (typename _Inode::const_iterator it = begin(); it != end(); ++it)
01338     {
01339       node_const_pointer p_nd = *it;
01340       PB_DS_DEBUG_VERIFY(p_nd->m_p_parent == this);
01341       node_debug_info child_ret = p_nd->assert_valid_imp(p_traits,
01342                                  __file, __line);
01343 
01344       PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind);
01345       PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
01346       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));
01347     }
01348       return std::make_pair(pref_b_it(), pref_e_it());
01349     }
01350 #endif
01351 
01352 #undef PB_DS_CLASS_T_DEC
01353 #undef PB_DS_CLASS_C_DEC
01354   } // namespace detail
01355 } // namespace __gnu_pbds
01356 
01357 #endif