libstdc++
pat_trie_base.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2015 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