Home | History | Annotate | Download | only in pat_trie_
      1 // -*- C++ -*-
      2 
      3 // Copyright (C) 2005, 2006, 2009, 2011, 2012 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