The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2005-2021 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 detail::rebind_traits<_Alloc, Metadata>::const_reference
    72		    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 detail::rebind_traits<_Alloc, _Node_base>::pointer
   103		  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 detail::rebind_traits<_Alloc, _ATraits>::const_pointer
   112		  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 detail::rebind_traits<_Alloc, base_type>::const_pointer
   228		node_const_pointer;
   229	
   230	      typedef _Leaf<_ATraits, Metadata>	 		leaf;
   231	      typedef typename detail::rebind_traits<_Alloc, leaf>	__rebind_l;
   232	      typedef typename __rebind_l::pointer 		leaf_pointer;
   233	      typedef typename __rebind_l::const_pointer 	leaf_const_pointer;
   234	
   235	      typedef detail::rebind_traits<_Alloc, _Inode>	__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 detail::rebind_traits<_Alloc, node_pointer>	__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 rebind_traits<_Alloc, Node>::pointer	node_pointer;
   504	      typedef typename rebind_traits<_Alloc, Leaf>::pointer	leaf_pointer;
   505	      typedef typename rebind_traits<_Alloc, Leaf>::const_pointer	leaf_const_pointer;
   506	      typedef typename rebind_traits<_Alloc, Head>::pointer	head_pointer;
   507	
   508	      typedef typename rebind_traits<_Alloc, Inode>::pointer 	inode_pointer;
   509	      typedef typename Inode::iterator			inode_iterator;
   510	
   511	      node_pointer 					m_p_nd;
   512	
   513	      _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd)
   514	      { }
   515	
   516	      _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other)
   517	      : m_p_nd(other.m_p_nd)
   518	      { }
   519	
   520	      _CIter&
   521	      operator=(const _CIter& other)
   522	      {
   523		m_p_nd = other.m_p_nd;
   524		return *this;
   525	      }
   526	
   527	      _CIter&
   528	      operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
   529	      {
   530		m_p_nd = other.m_p_nd;
   531		return *this;
   532	      }
   533	
   534	      const_pointer
   535	      operator->() const
   536	      {
   537		_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
   538		return &static_cast<leaf_pointer>(m_p_nd)->value();
   539	      }
   540	
   541	      const_reference
   542	      operator*() const
   543	      {
   544		_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
   545		return static_cast<leaf_pointer>(m_p_nd)->value();
   546	      }
   547	
   548	      bool
   549	      operator==(const _CIter& other) const
   550	      { return m_p_nd == other.m_p_nd; }
   551	
   552	      bool
   553	      operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
   554	      { return m_p_nd == other.m_p_nd; }
   555	
   556	      bool
   557	      operator!=(const _CIter& other) const
   558	      { return m_p_nd != other.m_p_nd; }
   559	
   560	      bool
   561	      operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
   562	      { return m_p_nd != other.m_p_nd; }
   563	
   564	      _CIter&
   565	      operator++()
   566	      {
   567		inc(integral_constant<int, Is_Forward_Iterator>());
   568		return *this;
   569	      }
   570	
   571	      _CIter
   572	      operator++(int)
   573	      {
   574		_CIter ret_it(m_p_nd);
   575		operator++();
   576		return ret_it;
   577	      }
   578	
   579	      _CIter&
   580	      operator--()
   581	      {
   582		dec(integral_constant<int, Is_Forward_Iterator>());
   583		return *this;
   584	      }
   585	
   586	      _CIter
   587	      operator--(int)
   588	      {
   589		_CIter ret_it(m_p_nd);
   590		operator--();
   591		return ret_it;
   592	      }
   593	
   594	    protected:
   595	      void
   596	      inc(false_type)
   597	      { dec(true_type()); }
   598	
   599	      void
   600	      inc(true_type)
   601	      {
   602		if (m_p_nd->m_type == head_node)
   603		  {
   604		    m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
   605		    return;
   606		  }
   607	
   608		node_pointer p_y = m_p_nd->m_p_parent;
   609		while (p_y->m_type != head_node && get_larger_sibling(m_p_nd) == 0)
   610		  {
   611		    m_p_nd = p_y;
   612		    p_y = p_y->m_p_parent;
   613		  }
   614	
   615		if (p_y->m_type == head_node)
   616		  {
   617		    m_p_nd = p_y;
   618		    return;
   619		  }
   620		m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
   621	      }
   622	
   623	      void
   624	      dec(false_type)
   625	      { inc(true_type()); }
   626	
   627	      void
   628	      dec(true_type)
   629	      {
   630		if (m_p_nd->m_type == head_node)
   631		  {
   632		    m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
   633		    return;
   634		  }
   635	
   636		node_pointer p_y = m_p_nd->m_p_parent;
   637		while (p_y->m_type != head_node && get_smaller_sibling(m_p_nd) == 0)
   638		  {
   639		    m_p_nd = p_y;
   640		    p_y = p_y->m_p_parent;
   641		  }
   642	
   643		if (p_y->m_type == head_node)
   644		  {
   645		    m_p_nd = p_y;
   646		    return;
   647		  }
   648		m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
   649	      }
   650	
   651	      static node_pointer
   652	      get_larger_sibling(node_pointer p_nd)
   653	      {
   654		inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent);
   655	
   656		inode_iterator it = p_parent->begin();
   657		while (*it != p_nd)
   658		  ++it;
   659	
   660		inode_iterator next_it = it;
   661		++next_it;
   662		return (next_it == p_parent->end())? 0 : *next_it;
   663	      }
   664	
   665	      static node_pointer
   666	      get_smaller_sibling(node_pointer p_nd)
   667	      {
   668		inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent);
   669	
   670		inode_iterator it = p_parent->begin();
   671		if (*it == p_nd)
   672		  return 0;
   673	
   674		inode_iterator prev_it;
   675		do
   676		  {
   677		    prev_it = it;
   678		    ++it;
   679		    if (*it == p_nd)
   680		      return *prev_it;
   681		  }
   682		while (true);
   683	
   684		_GLIBCXX_DEBUG_ASSERT(false);
   685		return 0;
   686	      }
   687	
   688	      static leaf_pointer
   689	      leftmost_descendant(node_pointer p_nd)
   690	      {
   691		if (p_nd->m_type == leaf_node)
   692		  return static_cast<leaf_pointer>(p_nd);
   693		return static_cast<inode_pointer>(p_nd)->leftmost_descendant();
   694	      }
   695	
   696	      static leaf_pointer
   697	      rightmost_descendant(node_pointer p_nd)
   698	      {
   699		if (p_nd->m_type == leaf_node)
   700		  return static_cast<leaf_pointer>(p_nd);
   701		return static_cast<inode_pointer>(p_nd)->rightmost_descendant();
   702	      }
   703	    };
   704	
   705	
   706	    /// Iterator.
   707	    template<typename Node, typename Leaf, typename Head, typename Inode,
   708		     bool Is_Forward_Iterator>
   709	    class _Iter
   710	    : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
   711	    {
   712	    public:
   713	      typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
   714	      							base_type;
   715	      typedef typename base_type::allocator_type	allocator_type;
   716	      typedef typename base_type::type_traits		type_traits;
   717	      typedef typename type_traits::value_type		value_type;
   718	      typedef typename type_traits::pointer 		pointer;
   719	      typedef typename type_traits::reference 		reference;
   720	
   721	      typedef typename base_type::node_pointer		node_pointer;
   722	      typedef typename base_type::leaf_pointer		leaf_pointer;
   723	      typedef typename base_type::leaf_const_pointer	leaf_const_pointer;
   724	      typedef typename base_type::head_pointer		head_pointer;
   725	      typedef typename base_type::inode_pointer 	inode_pointer;
   726	
   727	      _Iter(node_pointer p_nd = 0)
   728	      : base_type(p_nd) { }
   729	
   730	      _Iter(const PB_DS_ODIR_IT_C_DEC& other)
   731	      : base_type(other.m_p_nd) { }
   732	
   733	      _Iter&
   734	      operator=(const _Iter& other)
   735	      {
   736		base_type::m_p_nd = other.m_p_nd;
   737		return *this;
   738	      }
   739	
   740	      _Iter&
   741	      operator=(const PB_DS_ODIR_IT_C_DEC& other)
   742	      {
   743		base_type::m_p_nd = other.m_p_nd;
   744		return *this;
   745	      }
   746	
   747	      pointer
   748	      operator->() const
   749	      {
   750		_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
   751		return &static_cast<leaf_pointer>(base_type::m_p_nd)->value();
   752	      }
   753	
   754	      reference
   755	      operator*() const
   756	      {
   757		_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
   758		return static_cast<leaf_pointer>(base_type::m_p_nd)->value();
   759	      }
   760	
   761	      _Iter&
   762	      operator++()
   763	      {
   764		base_type::operator++();
   765		return *this;
   766	      }
   767	
   768	      _Iter
   769	      operator++(int)
   770	      {
   771		_Iter ret(base_type::m_p_nd);
   772		operator++();
   773		return ret;
   774	      }
   775	
   776	      _Iter&
   777	      operator--()
   778	      {
   779		base_type::operator--();
   780		return *this;
   781	      }
   782	
   783	      _Iter
   784	      operator--(int)
   785	      {
   786		_Iter ret(base_type::m_p_nd);
   787		operator--();
   788		return ret;
   789	      }
   790	    };
   791	
   792	#undef PB_DS_CONST_ODIR_IT_C_DEC
   793	#undef PB_DS_ODIR_IT_C_DEC
   794	
   795	
   796	#define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \
   797	    _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
   798	
   799	#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \
   800	    _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
   801	
   802	    /// Node const iterator.
   803	    template<typename Node,
   804		     typename Leaf,
   805		     typename Head,
   806		     typename Inode,
   807		     typename _CIterator,
   808		     typename Iterator,
   809		     typename _Alloc>
   810	    class _Node_citer
   811	    {
   812	    protected:
   813	      typedef typename rebind_traits<_Alloc, Node>::pointer	node_pointer;
   814	
   815	      typedef typename rebind_traits<_Alloc, Leaf>::pointer	leaf_pointer;
   816	      typedef typename rebind_traits<_Alloc, Leaf>::const_pointer	leaf_const_pointer;
   817	
   818	      typedef typename rebind_traits<_Alloc, Inode>::pointer 	inode_pointer;
   819	      typedef typename rebind_traits<_Alloc, Inode>::const_pointer inode_const_pointer;
   820	
   821	      typedef typename Node::a_const_pointer		a_const_pointer;
   822	      typedef typename Node::a_const_iterator		a_const_iterator;
   823	
   824	    private:
   825	      a_const_iterator
   826	      pref_begin() const
   827	      {
   828		if (m_p_nd->m_type == leaf_node)
   829		  {
   830		    leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd);
   831		    return m_p_traits->begin(m_p_traits->extract_key(lcp->value()));
   832		  }
   833		_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
   834		return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it();
   835	      }
   836	
   837	      a_const_iterator
   838	      pref_end() const
   839	      {
   840		if (m_p_nd->m_type == leaf_node)
   841		  {
   842		    leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd);
   843		    return m_p_traits->end(m_p_traits->extract_key(lcp->value()));
   844		  }
   845		_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
   846		return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it();
   847	      }
   848	
   849	    public:
   850	      typedef trivial_iterator_tag 			iterator_category;
   851	      typedef trivial_iterator_difference_type 		difference_type;
   852	      typedef typename _Alloc::size_type 		size_type;
   853	
   854	      typedef _CIterator 		       		value_type;
   855	      typedef value_type 				reference;
   856	      typedef value_type 				const_reference;
   857	
   858	      /// Metadata type.
   859	      typedef typename Node::metadata_type 		metadata_type;
   860	
   861	      /// Const metadata reference type.
   862	      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference    metadata_const_reference;
   863	
   864	      inline
   865	      _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
   866	      : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
   867	      { }
   868	
   869	      /// Subtree valid prefix.
   870	      std::pair<a_const_iterator, a_const_iterator>
   871	      valid_prefix() const
   872	      { return std::make_pair(pref_begin(), pref_end()); }
   873	
   874	      /// Const access; returns the __const iterator* associated with
   875	      /// the current leaf.
   876	      const_reference
   877	      operator*() const
   878	      {
   879		_GLIBCXX_DEBUG_ASSERT(num_children() == 0);
   880		return _CIterator(m_p_nd);
   881	      }
   882	
   883	      /// Metadata access.
   884	      metadata_const_reference
   885	      get_metadata() const
   886	      { return m_p_nd->get_metadata(); }
   887	
   888	      /// Returns the number of children in the corresponding node.
   889	      size_type
   890	      num_children() const
   891	      {
   892		if (m_p_nd->m_type == leaf_node)
   893		  return 0;
   894		_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
   895		inode_pointer inp = static_cast<inode_pointer>(m_p_nd);
   896		return std::distance(inp->begin(), inp->end());
   897	      }
   898	
   899	      /// Returns a __const node __iterator to the corresponding node's
   900	      /// i-th child.
   901	      _Node_citer
   902	      get_child(size_type i) const
   903	      {
   904		_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
   905		inode_pointer inp = static_cast<inode_pointer>(m_p_nd);
   906		typename Inode::iterator it = inp->begin();
   907		std::advance(it, i);
   908		return _Node_citer(*it, m_p_traits);
   909	      }
   910	
   911	      /// Compares content to a different iterator object.
   912	      bool
   913	      operator==(const _Node_citer& other) const
   914	      { return m_p_nd == other.m_p_nd; }
   915	
   916	      /// Compares content (negatively) to a different iterator object.
   917	      bool
   918	      operator!=(const _Node_citer& other) const
   919	      { return m_p_nd != other.m_p_nd; }
   920	
   921	      node_pointer 			m_p_nd;
   922	      a_const_pointer 			m_p_traits;
   923	    };
   924	
   925	
   926	    /// Node iterator.
   927	    template<typename Node,
   928		     typename Leaf,
   929		     typename Head,
   930		     typename Inode,
   931		     typename _CIterator,
   932		     typename Iterator,
   933		     typename _Alloc>
   934	    class _Node_iter
   935	    : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc>
   936	    {
   937	    private:
   938	      typedef _Node_citer<Node, Leaf, Head, Inode,
   939				  _CIterator, Iterator, _Alloc>	base_type;
   940	      typedef typename rebind_traits<_Alloc, Node>::pointer	node_pointer;
   941	      typedef typename base_type::inode_pointer 	inode_pointer;
   942	      typedef typename base_type::a_const_pointer 	a_const_pointer;
   943	      typedef Iterator 					iterator;
   944	
   945	    public:
   946	      typedef typename base_type::size_type 		size_type;
   947	
   948	      typedef Iterator 					value_type;
   949	      typedef value_type 				reference;
   950	      typedef value_type 				const_reference;
   951	
   952	      _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
   953	      : base_type(p_nd, p_traits)
   954	      { }
   955	
   956	      /// Access; returns the iterator*  associated with the current leaf.
   957	      reference
   958	      operator*() const
   959	      {
   960		_GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
   961		return iterator(base_type::m_p_nd);
   962	      }
   963	
   964	      /// Returns a node __iterator to the corresponding node's i-th child.
   965	      _Node_iter
   966	      get_child(size_type i) const
   967	      {
   968		_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node);
   969	
   970		typename Inode::iterator it =
   971		  static_cast<inode_pointer>(base_type::m_p_nd)->begin();
   972	
   973		std::advance(it, i);
   974		return _Node_iter(*it, base_type::m_p_traits);
   975	      }
   976	    };
   977	    };
   978	
   979	
   980	#define PB_DS_CLASS_T_DEC \
   981	    template<typename _ATraits, typename Metadata>
   982	
   983	#define PB_DS_CLASS_C_DEC \
   984	    pat_trie_base::_Inode<_ATraits, Metadata>
   985	
   986	    PB_DS_CLASS_T_DEC
   987	    typename PB_DS_CLASS_C_DEC::__rebind_l
   988	    PB_DS_CLASS_C_DEC::s_leaf_alloc;
   989	
   990	    PB_DS_CLASS_T_DEC
   991	    typename PB_DS_CLASS_C_DEC::__rebind_in
   992	    PB_DS_CLASS_C_DEC::s_inode_alloc;
   993	
   994	    PB_DS_CLASS_T_DEC
   995	    inline typename PB_DS_CLASS_C_DEC::size_type
   996	    PB_DS_CLASS_C_DEC::
   997	    get_pref_pos(a_const_iterator b_it, a_const_iterator e_it,
   998			 a_const_pointer p_traits) const
   999	    {
  1000	      if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind)
  1001		return 0;
  1002	      std::advance(b_it, m_e_ind);
  1003	      return 1 + p_traits->e_pos(*b_it);
  1004	    }
  1005	
  1006	    PB_DS_CLASS_T_DEC
  1007	    PB_DS_CLASS_C_DEC::
  1008	    _Inode(size_type len, const a_const_iterator it)
  1009	    : base_type(i_node), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it)
  1010	    {
  1011	      std::advance(m_pref_e_it, m_e_ind);
  1012	      std::fill(m_a_p_children, m_a_p_children + arr_size,
  1013			static_cast<node_pointer>(0));
  1014	    }
  1015	
  1016	    PB_DS_CLASS_T_DEC
  1017	    void
  1018	    PB_DS_CLASS_C_DEC::
  1019	    update_prefixes(a_const_pointer p_traits)
  1020	    {
  1021	      node_pointer p_first = *begin();
  1022	      if (p_first->m_type == leaf_node)
  1023		{
  1024		  leaf_const_pointer p = static_cast<leaf_const_pointer>(p_first);
  1025		  m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value()));
  1026		}
  1027	      else
  1028		{
  1029		  inode_pointer p = static_cast<inode_pointer>(p_first);
  1030		  _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node);
  1031		  m_pref_b_it = p->pref_b_it();
  1032		}
  1033	      m_pref_e_it = m_pref_b_it;
  1034	      std::advance(m_pref_e_it, m_e_ind);
  1035	    }
  1036	
  1037	    PB_DS_CLASS_T_DEC
  1038	    typename PB_DS_CLASS_C_DEC::const_iterator
  1039	    PB_DS_CLASS_C_DEC::
  1040	    begin() const
  1041	    {
  1042	      typedef node_pointer_pointer pointer_type;
  1043	      pointer_type p = const_cast<pointer_type>(m_a_p_children);
  1044	      return const_iterator(p + get_begin_pos(), p + arr_size);
  1045	    }
  1046	
  1047	    PB_DS_CLASS_T_DEC
  1048	    typename PB_DS_CLASS_C_DEC::iterator
  1049	    PB_DS_CLASS_C_DEC::
  1050	    begin()
  1051	    {
  1052	      return iterator(m_a_p_children + get_begin_pos(),
  1053			      m_a_p_children + arr_size);
  1054	    }
  1055	
  1056	    PB_DS_CLASS_T_DEC
  1057	    typename PB_DS_CLASS_C_DEC::const_iterator
  1058	    PB_DS_CLASS_C_DEC::
  1059	    end() const
  1060	    {
  1061	      typedef node_pointer_pointer pointer_type;
  1062	      pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size;
  1063	      return const_iterator(p, p);
  1064	    }
  1065	
  1066	    PB_DS_CLASS_T_DEC
  1067	    typename PB_DS_CLASS_C_DEC::iterator
  1068	    PB_DS_CLASS_C_DEC::
  1069	    end()
  1070	    { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }
  1071	
  1072	    PB_DS_CLASS_T_DEC
  1073	    inline typename PB_DS_CLASS_C_DEC::node_pointer
  1074	    PB_DS_CLASS_C_DEC::
  1075	    get_child_node(a_const_iterator b_it, a_const_iterator e_it,
  1076			   a_const_pointer p_traits)
  1077	    {
  1078	      const size_type i = get_pref_pos(b_it, e_it, p_traits);
  1079	      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
  1080	      return m_a_p_children[i];
  1081	    }
  1082	
  1083	    PB_DS_CLASS_T_DEC
  1084	    inline typename PB_DS_CLASS_C_DEC::iterator
  1085	    PB_DS_CLASS_C_DEC::
  1086	    get_child_it(a_const_iterator b_it, a_const_iterator e_it,
  1087			 a_const_pointer p_traits)
  1088	    {
  1089	      const size_type i = get_pref_pos(b_it, e_it, p_traits);
  1090	      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
  1091	      _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0);
  1092	      return iterator(m_a_p_children + i, m_a_p_children + i);
  1093	    }
  1094	
  1095	    PB_DS_CLASS_T_DEC
  1096	    inline typename PB_DS_CLASS_C_DEC::node_const_pointer
  1097	    PB_DS_CLASS_C_DEC::
  1098	    get_child_node(a_const_iterator b_it, a_const_iterator e_it,
  1099			   a_const_pointer p_traits) const
  1100	    { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); }
  1101	
  1102	    PB_DS_CLASS_T_DEC
  1103	    typename PB_DS_CLASS_C_DEC::node_pointer
  1104	    PB_DS_CLASS_C_DEC::
  1105	    get_lower_bound_child_node(a_const_iterator b_it, a_const_iterator e_it,
  1106				       size_type checked_ind,
  1107				       a_const_pointer p_traits)
  1108	    {
  1109	      if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
  1110		{
  1111		  if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it,
  1112					     m_pref_e_it, true))
  1113		    return leftmost_descendant();
  1114		  return rightmost_descendant();
  1115		}
  1116	
  1117	      size_type i = get_pref_pos(b_it, e_it, p_traits);
  1118	      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
  1119	
  1120	      if (m_a_p_children[i] != 0)
  1121		return m_a_p_children[i];
  1122	
  1123	      while (++i < arr_size)
  1124		if (m_a_p_children[i] != 0)
  1125		  {
  1126		    const node_type& __nt = m_a_p_children[i]->m_type;
  1127		    node_pointer ret = m_a_p_children[i];
  1128	
  1129		    if (__nt == leaf_node)
  1130		      return ret;
  1131	
  1132		    _GLIBCXX_DEBUG_ASSERT(__nt == i_node);
  1133		    inode_pointer inp = static_cast<inode_pointer>(ret);
  1134		    return inp->leftmost_descendant();
  1135		  }
  1136	
  1137	      return rightmost_descendant();
  1138	    }
  1139	
  1140	    PB_DS_CLASS_T_DEC
  1141	    inline typename PB_DS_CLASS_C_DEC::node_pointer
  1142	    PB_DS_CLASS_C_DEC::
  1143	    add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it,
  1144		      a_const_pointer p_traits)
  1145	    {
  1146	      const size_type i = get_pref_pos(b_it, e_it, p_traits);
  1147	      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
  1148	      if (m_a_p_children[i] == 0)
  1149		{
  1150		  m_a_p_children[i] = p_nd;
  1151		  p_nd->m_p_parent = this;
  1152		  return p_nd;
  1153		}
  1154	      return m_a_p_children[i];
  1155	    }
  1156	
  1157	    PB_DS_CLASS_T_DEC
  1158	    typename PB_DS_CLASS_C_DEC::node_const_pointer
  1159	    PB_DS_CLASS_C_DEC::
  1160	    get_join_child(node_const_pointer p_nd,
  1161			   a_const_pointer p_tr) const
  1162	    {
  1163	      node_pointer p = const_cast<node_pointer>(p_nd);
  1164	      return const_cast<inode_pointer>(this)->get_join_child(p, p_tr);
  1165	    }
  1166	
  1167	    PB_DS_CLASS_T_DEC
  1168	    typename PB_DS_CLASS_C_DEC::node_pointer
  1169	    PB_DS_CLASS_C_DEC::
  1170	    get_join_child(node_pointer p_nd, a_const_pointer p_traits)
  1171	    {
  1172	      size_type i;
  1173	      a_const_iterator b_it;
  1174	      a_const_iterator e_it;
  1175	      if (p_nd->m_type == leaf_node)
  1176		{
  1177		  leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd);
  1178	
  1179		  typedef typename type_traits::key_const_reference kcr;
  1180		  kcr r_key = access_traits::extract_key(p->value());
  1181		  b_it = p_traits->begin(r_key);
  1182		  e_it = p_traits->end(r_key);
  1183		}
  1184	      else
  1185		{
  1186		  b_it = static_cast<inode_pointer>(p_nd)->pref_b_it();
  1187		  e_it = static_cast<inode_pointer>(p_nd)->pref_e_it();
  1188		}
  1189	      i = get_pref_pos(b_it, e_it, p_traits);
  1190	      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
  1191	      return m_a_p_children[i];
  1192	    }
  1193	
  1194	    PB_DS_CLASS_T_DEC
  1195	    void
  1196	    PB_DS_CLASS_C_DEC::
  1197	    remove_child(node_pointer p_nd)
  1198	    {
  1199	      size_type i = 0;
  1200	      for (; i < arr_size; ++i)
  1201		if (m_a_p_children[i] == p_nd)
  1202		  {
  1203		    m_a_p_children[i] = 0;
  1204		    return;
  1205		  }
  1206	      _GLIBCXX_DEBUG_ASSERT(i != arr_size);
  1207	    }
  1208	
  1209	    PB_DS_CLASS_T_DEC
  1210	    void
  1211	    PB_DS_CLASS_C_DEC::
  1212	    remove_child(iterator it)
  1213	    { *it.m_p_p_cur = 0; }
  1214	
  1215	    PB_DS_CLASS_T_DEC
  1216	    void
  1217	    PB_DS_CLASS_C_DEC::
  1218	    replace_child(node_pointer p_nd, a_const_iterator b_it,
  1219			  a_const_iterator e_it,
  1220			  a_const_pointer p_traits)
  1221	    {
  1222	      const size_type i = get_pref_pos(b_it, e_it, p_traits);
  1223	      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
  1224	      m_a_p_children[i] = p_nd;
  1225	      p_nd->m_p_parent = this;
  1226	    }
  1227	
  1228	    PB_DS_CLASS_T_DEC
  1229	    inline typename PB_DS_CLASS_C_DEC::a_const_iterator
  1230	    PB_DS_CLASS_C_DEC::
  1231	    pref_b_it() const
  1232	    { return m_pref_b_it; }
  1233	
  1234	    PB_DS_CLASS_T_DEC
  1235	    inline typename PB_DS_CLASS_C_DEC::a_const_iterator
  1236	    PB_DS_CLASS_C_DEC::
  1237	    pref_e_it() const
  1238	    { return m_pref_e_it; }
  1239	
  1240	    PB_DS_CLASS_T_DEC
  1241	    bool
  1242	    PB_DS_CLASS_C_DEC::
  1243	    should_be_mine(a_const_iterator b_it, a_const_iterator e_it,
  1244			   size_type checked_ind,
  1245			   a_const_pointer p_traits) const
  1246	    {
  1247	      if (m_e_ind == 0)
  1248		return true;
  1249	
  1250	      const size_type num_es = std::distance(b_it, e_it);
  1251	      if (num_es < m_e_ind)
  1252		return false;
  1253	
  1254	      a_const_iterator key_b_it = b_it;
  1255	      std::advance(key_b_it, checked_ind);
  1256	      a_const_iterator key_e_it = b_it;
  1257	      std::advance(key_e_it, m_e_ind);
  1258	
  1259	      a_const_iterator value_b_it = m_pref_b_it;
  1260	      std::advance(value_b_it, checked_ind);
  1261	      a_const_iterator value_e_it = m_pref_b_it;
  1262	      std::advance(value_e_it, m_e_ind);
  1263	
  1264	      return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it,
  1265					      value_e_it);
  1266	    }
  1267	
  1268	    PB_DS_CLASS_T_DEC
  1269	    typename PB_DS_CLASS_C_DEC::leaf_pointer
  1270	    PB_DS_CLASS_C_DEC::
  1271	    leftmost_descendant()
  1272	    {
  1273	      node_pointer p_pot = *begin();
  1274	      if (p_pot->m_type == leaf_node)
  1275		return (static_cast<leaf_pointer>(p_pot));
  1276	      _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
  1277	      return static_cast<inode_pointer>(p_pot)->leftmost_descendant();
  1278	    }
  1279	
  1280	    PB_DS_CLASS_T_DEC
  1281	    typename PB_DS_CLASS_C_DEC::leaf_const_pointer
  1282	    PB_DS_CLASS_C_DEC::
  1283	    leftmost_descendant() const
  1284	    { return const_cast<inode_pointer>(this)->leftmost_descendant(); }
  1285	
  1286	    PB_DS_CLASS_T_DEC
  1287	    typename PB_DS_CLASS_C_DEC::leaf_pointer
  1288	    PB_DS_CLASS_C_DEC::
  1289	    rightmost_descendant()
  1290	    {
  1291	      const size_type num_children = std::distance(begin(), end());
  1292	      _GLIBCXX_DEBUG_ASSERT(num_children >= 2);
  1293	
  1294	      iterator it = begin();
  1295	      std::advance(it, num_children - 1);
  1296	      node_pointer p_pot =* it;
  1297	      if (p_pot->m_type == leaf_node)
  1298		return static_cast<leaf_pointer>(p_pot);
  1299	      _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
  1300	      return static_cast<inode_pointer>(p_pot)->rightmost_descendant();
  1301	    }
  1302	
  1303	    PB_DS_CLASS_T_DEC
  1304	    typename PB_DS_CLASS_C_DEC::leaf_const_pointer
  1305	    PB_DS_CLASS_C_DEC::
  1306	    rightmost_descendant() const
  1307	    { return const_cast<inode_pointer>(this)->rightmost_descendant(); }
  1308	
  1309	    PB_DS_CLASS_T_DEC
  1310	    typename PB_DS_CLASS_C_DEC::size_type
  1311	    PB_DS_CLASS_C_DEC::
  1312	    get_begin_pos() const
  1313	    {
  1314	      size_type i = 0;
  1315	      for (; i < arr_size && m_a_p_children[i] == 0; ++i)
  1316		;
  1317	      return i;
  1318	    }
  1319	
  1320	#ifdef _GLIBCXX_DEBUG
  1321	    PB_DS_CLASS_T_DEC
  1322	    typename PB_DS_CLASS_C_DEC::node_debug_info
  1323	    PB_DS_CLASS_C_DEC::
  1324	    assert_valid_imp(a_const_pointer p_traits,
  1325			     const char* __file, int __line) const
  1326	    {
  1327	      PB_DS_DEBUG_VERIFY(base_type::m_type == i_node);
  1328	      PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind);
  1329	      PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2);
  1330	
  1331	      for (typename _Inode::const_iterator it = begin(); it != end(); ++it)
  1332		{
  1333		  node_const_pointer p_nd = *it;
  1334		  PB_DS_DEBUG_VERIFY(p_nd->m_p_parent == this);
  1335		  node_debug_info child_ret = p_nd->assert_valid_imp(p_traits,
  1336								     __file, __line);
  1337	
  1338		  PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind);
  1339		  PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
  1340		  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));
  1341		}
  1342	      return std::make_pair(pref_b_it(), pref_e_it());
  1343	    }
  1344	#endif
  1345	
  1346	#undef PB_DS_CLASS_T_DEC
  1347	#undef PB_DS_CLASS_C_DEC
  1348	  } // namespace detail
  1349	} // namespace __gnu_pbds
  1350	
  1351	#endif