Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

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