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