[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / detail / pat_trie_ / point_iterators.hpp

// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file point_iterators.hpp
 * Contains an implementation class for bin_search_tree_.
 */

#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP

#include <debug/debug.h>

namespace __gnu_pbds
{
  namespace detail
  {

#define PB_DS_CONST_IT_C_DEC					\
    pat_trie_const_it_<						\
					Type_Traits,		\
					Node,			\
					Leaf,			\
					Head,			\
					Internal_Node,		\
					Is_Forward_Iterator,	\
					Allocator>

#define PB_DS_CONST_ODIR_IT_C_DEC				\
    pat_trie_const_it_<						\
					Type_Traits,		\
					Node,			\
					Leaf,			\
					Head,			\
					Internal_Node,		\
					!Is_Forward_Iterator,	\
					Allocator>

#define PB_DS_IT_C_DEC							\
    pat_trie_it_<							\
						Type_Traits,		\
						Node,			\
						Leaf,			\
						Head,			\
						Internal_Node,		\
						Is_Forward_Iterator,	\
						Allocator>

#define PB_DS_ODIR_IT_C_DEC						\
    pat_trie_it_<							\
						Type_Traits,		\
						Node,			\
						Leaf,			\
						Head,			\
						Internal_Node,		\
						!Is_Forward_Iterator,	\
						Allocator>


    // Const iterator.
    template<typename Type_Traits,
	     class Node,
	     class Leaf,
	     class Head,
	     class Internal_Node,
	     bool Is_Forward_Iterator,
	     class Allocator>
    class pat_trie_const_it_
    {

    private:
      typedef
      typename Allocator::template rebind<
      Node>::other::pointer
      node_pointer;

      typedef
      typename Allocator::template rebind<
	Leaf>::other::const_pointer
      const_leaf_pointer;

      typedef
      typename Allocator::template rebind<
	Leaf>::other::pointer
      leaf_pointer;

      typedef
      typename Allocator::template rebind<
	Head>::other::pointer
      head_pointer;

      typedef
      typename Allocator::template rebind<
	Internal_Node>::other::pointer
      internal_node_pointer;

    public:

      typedef std::bidirectional_iterator_tag iterator_category;

      typedef typename Allocator::difference_type difference_type;

      typedef typename Type_Traits::value_type value_type;

      typedef typename Type_Traits::pointer pointer;

      typedef typename Type_Traits::const_pointer const_pointer;

      typedef typename Type_Traits::reference reference;

      typedef typename Type_Traits::const_reference const_reference;

    public:

      inline
      pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
      { }

      inline
      pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other) 
      : m_p_nd(other.m_p_nd)
      { }

      inline
      PB_DS_CONST_IT_C_DEC& 
      operator=(const PB_DS_CONST_IT_C_DEC& other)
      {
	m_p_nd = other.m_p_nd;
	return *this;
      }

      inline
      PB_DS_CONST_IT_C_DEC& 
      operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
      {
	m_p_nd = other.m_p_nd;
	return *this;
      }

      inline const_pointer
      operator->() const
      {
	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
	return &static_cast<leaf_pointer>(m_p_nd)->value();
      }

      inline const_reference
      operator*() const
      {
	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
	return static_cast<leaf_pointer>(m_p_nd)->value();
      }

      inline bool
      operator==(const PB_DS_CONST_IT_C_DEC& other) const
      { return (m_p_nd == other.m_p_nd); }

      inline bool
      operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
      { return (m_p_nd == other.m_p_nd); }

      inline bool
      operator!=(const PB_DS_CONST_IT_C_DEC& other) const
      { return (m_p_nd != other.m_p_nd); }

      inline bool
      operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
      { return (m_p_nd != other.m_p_nd); }

      inline PB_DS_CONST_IT_C_DEC& 
      operator++()
      {
	inc(integral_constant<int,Is_Forward_Iterator>());
	return *this;
      }

      inline PB_DS_CONST_IT_C_DEC
      operator++(int)
      {
	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
	operator++();
	return ret_it;
      }

      inline PB_DS_CONST_IT_C_DEC& 
      operator--()
      {
	dec(integral_constant<int,Is_Forward_Iterator>());
	return *this;
      }

      inline PB_DS_CONST_IT_C_DEC
      operator--(int)
      {
	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
	operator--();
	return ret_it;
      }

    protected:
      inline void
      inc(false_type)
      { dec(true_type()); }

      void
      inc(true_type)
      {
	if (m_p_nd->m_type == pat_trie_head_node_type)
	  {
	    m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
	    return;
	  }

	node_pointer p_y = m_p_nd->m_p_parent;
	while (p_y->m_type != pat_trie_head_node_type && 
	       get_larger_sibling(m_p_nd) == NULL)
	  {
	    m_p_nd = p_y;
	    p_y = p_y->m_p_parent;
	  }

	if (p_y->m_type == pat_trie_head_node_type)
	  {
	    m_p_nd = p_y;
	    return;
	  }
	m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
      }

      inline void
      dec(false_type)
      { inc(true_type()); }

      void
      dec(true_type)
      {
	if (m_p_nd->m_type == pat_trie_head_node_type)
	  {
	    m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
	    return;
	  }

	node_pointer p_y = m_p_nd->m_p_parent;
	while (p_y->m_type != pat_trie_head_node_type && 
	       get_smaller_sibling(m_p_nd) == NULL)
	  {
	    m_p_nd = p_y;
	    p_y = p_y->m_p_parent;
	  }

	if (p_y->m_type == pat_trie_head_node_type)
	  {
	    m_p_nd = p_y;
	    return;
	  }
	m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
      }

      inline static node_pointer
      get_larger_sibling(node_pointer p_nd)
      {
	internal_node_pointer p_parent =
	  static_cast<internal_node_pointer>(p_nd->m_p_parent);

	typename Internal_Node::iterator it = p_parent->begin();
	while (*it != p_nd)
	  ++it;

	typename Internal_Node::iterator next_it = it;
	++next_it;
	return ((next_it == p_parent->end())? NULL :* next_it);
      }

      inline static node_pointer
      get_smaller_sibling(node_pointer p_nd)
      {
	internal_node_pointer p_parent =
	  static_cast<internal_node_pointer>(p_nd->m_p_parent);

	typename Internal_Node::iterator it = p_parent->begin();

	if (*it == p_nd)
	  return (NULL);
	typename Internal_Node::iterator prev_it;
	do
	  {
	    prev_it = it;
	    ++it;
	    if (*it == p_nd)
	      return (*prev_it);
	  }
	while (true);

	_GLIBCXX_DEBUG_ASSERT(false);
	return (NULL);
      }

      inline static leaf_pointer
      leftmost_descendant(node_pointer p_nd)
      {
	if (p_nd->m_type == pat_trie_leaf_node_type)
	  return static_cast<leaf_pointer>(p_nd);
	return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
      }

      inline static leaf_pointer
      rightmost_descendant(node_pointer p_nd)
      {
	if (p_nd->m_type == pat_trie_leaf_node_type)
	  return static_cast<leaf_pointer>(p_nd);
	return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
      }

    public:
      node_pointer m_p_nd;
    };

    // Iterator.
    template<typename Type_Traits,
	     class Node,
	     class Leaf,
	     class Head,
	     class Internal_Node,
	     bool Is_Forward_Iterator,
	     class Allocator>
    class pat_trie_it_ : 
      public PB_DS_CONST_IT_C_DEC

    {
    private:
      typedef
      typename Allocator::template rebind<
      Node>::other::pointer
      node_pointer;

      typedef
      typename Allocator::template rebind<
	Leaf>::other::const_pointer
      const_leaf_pointer;

      typedef
      typename Allocator::template rebind<
	Leaf>::other::pointer
      leaf_pointer;

      typedef
      typename Allocator::template rebind<
	Head>::other::pointer
      head_pointer;

      typedef
      typename Allocator::template rebind<
	Internal_Node>::other::pointer
      internal_node_pointer;

    public:
      typedef typename Type_Traits::value_type value_type;

      typedef typename Type_Traits::const_pointer const_pointer;

      typedef typename Type_Traits::pointer pointer;

      typedef typename Type_Traits::const_reference const_reference;

      typedef typename Type_Traits::reference reference;

      inline
      pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
      { }

      inline
      pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
      { }

      inline
      PB_DS_IT_C_DEC& 
      operator=(const PB_DS_IT_C_DEC& other)
      {
	base_it_type::m_p_nd = other.m_p_nd;
	return *this;
      }

      inline
      PB_DS_IT_C_DEC& 
      operator=(const PB_DS_ODIR_IT_C_DEC& other)
      {
	base_it_type::m_p_nd = other.m_p_nd;
	return *this;
      }

      inline pointer
      operator->() const
      {
	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);

	return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
      }

      inline reference
      operator*() const
      {
	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
	return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
      }

      inline PB_DS_IT_C_DEC& 
      operator++()
      {
	PB_DS_CONST_IT_C_DEC::
	  operator++();
	return *this;
      }

      inline PB_DS_IT_C_DEC
      operator++(int)
      {
	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
	operator++();
	return ret_it;
      }

      inline PB_DS_IT_C_DEC& 
      operator--()
      {
	PB_DS_CONST_IT_C_DEC::operator--();
	return *this;
      }

      inline PB_DS_IT_C_DEC
      operator--(int)
      {
	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
	operator--();
	return ret_it;
      }

    protected:
      typedef PB_DS_CONST_IT_C_DEC base_it_type;

      friend class PB_DS_CLASS_C_DEC;
    };

#undef PB_DS_CONST_IT_C_DEC
#undef PB_DS_CONST_ODIR_IT_C_DEC
#undef PB_DS_IT_C_DEC
#undef PB_DS_ODIR_IT_C_DEC

  } // namespace detail
} // namespace __gnu_pbds

#endif
Commit	Line	Data
4569a895 AT	1	// -- C++ --
	2
	3	// Copyright (C) 2005, 2006 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 2, 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	// You should have received a copy of the GNU General Public License
	17	// along with this library; see the file COPYING. If not, write to
	18	// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
	19	// MA 02111-1307, USA.
	20
	21	// As a special exception, you may use this file as part of a free
	22	// software library without restriction. Specifically, if other files
	23	// instantiate templates or use macros or inline functions from this
	24	// file, or you compile this file and link it with other files to
	25	// produce an executable, this file does not by itself cause the
	26	// resulting executable to be covered by the GNU General Public
	27	// License. This exception does not however invalidate any other
	28	// reasons why the executable file might be covered by the GNU General
	29	// Public License.
	30
	31	// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
	32
	33	// Permission to use, copy, modify, sell, and distribute this software
	34	// is hereby granted without fee, provided that the above copyright
	35	// notice appears in all copies, and that both that copyright notice
	36	// and this permission notice appear in supporting documentation. None
	37	// of the above authors, nor IBM Haifa Research Laboratories, make any
	38	// representation about the suitability of this software for any
	39	// purpose. It is provided "as is" without express or implied
	40	// warranty.
	41
	42	/**
	43	* @file point_iterators.hpp
	44	* Contains an implementation class for bin_search_tree_.
	45	*/
	46
	47	#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
	48	#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
	49
47bea7b8	50	#include <debug/debug.h>
4569a895	51
5e11f978	52	namespace __gnu_pbds
4569a895 AT	53	{
	54	namespace detail
	55	{
	56
	57	#define PB_DS_CONST_IT_C_DEC \
	58	pat_trie_const_it_< \
	59	Type_Traits, \
	60	Node, \
	61	Leaf, \
	62	Head, \
	63	Internal_Node, \
	64	Is_Forward_Iterator, \
	65	Allocator>
	66
	67	#define PB_DS_CONST_ODIR_IT_C_DEC \
	68	pat_trie_const_it_< \
	69	Type_Traits, \
	70	Node, \
	71	Leaf, \
	72	Head, \
	73	Internal_Node, \
	74	!Is_Forward_Iterator, \
	75	Allocator>
	76
	77	#define PB_DS_IT_C_DEC \
	78	pat_trie_it_< \
	79	Type_Traits, \
	80	Node, \
	81	Leaf, \
	82	Head, \
	83	Internal_Node, \
	84	Is_Forward_Iterator, \
	85	Allocator>
	86
	87	#define PB_DS_ODIR_IT_C_DEC \
	88	pat_trie_it_< \
	89	Type_Traits, \
	90	Node, \
	91	Leaf, \
	92	Head, \
	93	Internal_Node, \
	94	!Is_Forward_Iterator, \
	95	Allocator>
	96
4569a895 AT	97
	98	// Const iterator.
	99	template<typename Type_Traits,
	100	class Node,
	101	class Leaf,
	102	class Head,
	103	class Internal_Node,
	104	bool Is_Forward_Iterator,
	105	class Allocator>
	106	class pat_trie_const_it_
	107	{
	108
	109	private:
	110	typedef
	111	typename Allocator::template rebind<
	112	Node>::other::pointer
	113	node_pointer;
	114
	115	typedef
	116	typename Allocator::template rebind<
	117	Leaf>::other::const_pointer
	118	const_leaf_pointer;
	119
	120	typedef
	121	typename Allocator::template rebind<
	122	Leaf>::other::pointer
	123	leaf_pointer;
	124
	125	typedef
	126	typename Allocator::template rebind<
	127	Head>::other::pointer
	128	head_pointer;
	129
	130	typedef
	131	typename Allocator::template rebind<
	132	Internal_Node>::other::pointer
	133	internal_node_pointer;
	134
	135	public:
	136
	137	typedef std::bidirectional_iterator_tag iterator_category;
	138
	139	typedef typename Allocator::difference_type difference_type;
	140
	141	typedef typename Type_Traits::value_type value_type;
	142
	143	typedef typename Type_Traits::pointer pointer;
	144
	145	typedef typename Type_Traits::const_pointer const_pointer;
	146
	147	typedef typename Type_Traits::reference reference;
	148
	149	typedef typename Type_Traits::const_reference const_reference;
	150
	151	public:
	152
	153	inline
	154	pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
	155	{ }
	156
	157	inline
47bea7b8 BK	158	pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
47bea7b8 BK	159	: m_p_nd(other.m_p_nd)
4569a895 AT	160	{ }
	161
	162	inline
	163	PB_DS_CONST_IT_C_DEC&
47bea7b8	164	operator=(const PB_DS_CONST_IT_C_DEC& other)
4569a895 AT	165	{
4569a895 AT	166	m_p_nd = other.m_p_nd;
1b24692f	167	return *this;
4569a895 AT	168	}
	169
	170	inline
	171	PB_DS_CONST_IT_C_DEC&
47bea7b8	172	operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
4569a895 AT	173	{
4569a895 AT	174	m_p_nd = other.m_p_nd;
1b24692f	175	return *this;
4569a895 AT	176	}
	177
	178	inline const_pointer
	179	operator->() const
	180	{
47bea7b8	181	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
1b24692f	182	return &static_cast<leaf_pointer>(m_p_nd)->value();
4569a895 AT	183	}
	184
	185	inline const_reference
	186	operator*() const
	187	{
47bea7b8	188	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
1b24692f	189	return static_cast<leaf_pointer>(m_p_nd)->value();
4569a895 AT	190	}
	191
	192	inline bool
47bea7b8	193	operator==(const PB_DS_CONST_IT_C_DEC& other) const
1b24692f	194	{ return (m_p_nd == other.m_p_nd); }
4569a895 AT	195
4569a895 AT	196	inline bool
47bea7b8	197	operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
1b24692f	198	{ return (m_p_nd == other.m_p_nd); }
4569a895 AT	199
4569a895 AT	200	inline bool
47bea7b8	201	operator!=(const PB_DS_CONST_IT_C_DEC& other) const
1b24692f	202	{ return (m_p_nd != other.m_p_nd); }
4569a895 AT	203
4569a895 AT	204	inline bool
47bea7b8	205	operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
1b24692f	206	{ return (m_p_nd != other.m_p_nd); }
4569a895 AT	207
	208	inline PB_DS_CONST_IT_C_DEC&
	209	operator++()
	210	{
	211	inc(integral_constant<int,Is_Forward_Iterator>());
1b24692f	212	return *this;
4569a895 AT	213	}
	214
	215	inline PB_DS_CONST_IT_C_DEC
	216	operator++(int)
	217	{
47bea7b8	218	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
4569a895	219	operator++();
1b24692f	220	return ret_it;
4569a895 AT	221	}
	222
	223	inline PB_DS_CONST_IT_C_DEC&
	224	operator--()
	225	{
	226	dec(integral_constant<int,Is_Forward_Iterator>());
1b24692f	227	return *this;
4569a895 AT	228	}
	229
	230	inline PB_DS_CONST_IT_C_DEC
	231	operator--(int)
	232	{
47bea7b8	233	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
4569a895	234	operator--();
1b24692f	235	return ret_it;
4569a895 AT	236	}
	237
	238	protected:
	239	inline void
	240	inc(false_type)
47bea7b8	241	{ dec(true_type()); }
4569a895 AT	242
	243	void
	244	inc(true_type)
	245	{
	246	if (m_p_nd->m_type == pat_trie_head_node_type)
	247	{
	248	m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
4569a895 AT	249	return;
	250	}
	251
	252	node_pointer p_y = m_p_nd->m_p_parent;
47bea7b8	253	while (p_y->m_type != pat_trie_head_node_type &&
4569a895 AT	254	get_larger_sibling(m_p_nd) == NULL)
	255	{
	256	m_p_nd = p_y;
4569a895 AT	257	p_y = p_y->m_p_parent;
	258	}
	259
	260	if (p_y->m_type == pat_trie_head_node_type)
	261	{
	262	m_p_nd = p_y;
4569a895 AT	263	return;
4569a895 AT	264	}
4569a895 AT	265	m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
	266	}
	267
	268	inline void
	269	dec(false_type)
47bea7b8	270	{ inc(true_type()); }
4569a895 AT	271
	272	void
	273	dec(true_type)
	274	{
	275	if (m_p_nd->m_type == pat_trie_head_node_type)
	276	{
	277	m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
4569a895 AT	278	return;
	279	}
	280
	281	node_pointer p_y = m_p_nd->m_p_parent;
47bea7b8	282	while (p_y->m_type != pat_trie_head_node_type &&
4569a895 AT	283	get_smaller_sibling(m_p_nd) == NULL)
	284	{
	285	m_p_nd = p_y;
4569a895 AT	286	p_y = p_y->m_p_parent;
	287	}
	288
	289	if (p_y->m_type == pat_trie_head_node_type)
	290	{
	291	m_p_nd = p_y;
4569a895 AT	292	return;
4569a895 AT	293	}
4569a895 AT	294	m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
	295	}
	296
	297	inline static node_pointer
	298	get_larger_sibling(node_pointer p_nd)
	299	{
	300	internal_node_pointer p_parent =
	301	static_cast<internal_node_pointer>(p_nd->m_p_parent);
	302
	303	typename Internal_Node::iterator it = p_parent->begin();
4569a895 AT	304	while (*it != p_nd)
	305	++it;
	306
	307	typename Internal_Node::iterator next_it = it;
	308	++next_it;
4569a895 AT	309	return ((next_it == p_parent->end())? NULL :* next_it);
	310	}
	311
	312	inline static node_pointer
	313	get_smaller_sibling(node_pointer p_nd)
	314	{
	315	internal_node_pointer p_parent =
	316	static_cast<internal_node_pointer>(p_nd->m_p_parent);
	317
	318	typename Internal_Node::iterator it = p_parent->begin();
	319
	320	if (*it == p_nd)
	321	return (NULL);
4569a895	322	typename Internal_Node::iterator prev_it;
4569a895 AT	323	do
	324	{
	325	prev_it = it;
4569a895	326	++it;
4569a895 AT	327	if (*it == p_nd)
	328	return (*prev_it);
	329	}
	330	while (true);
	331
47bea7b8	332	_GLIBCXX_DEBUG_ASSERT(false);
4569a895 AT	333	return (NULL);
	334	}
	335
	336	inline static leaf_pointer
	337	leftmost_descendant(node_pointer p_nd)
	338	{
	339	if (p_nd->m_type == pat_trie_leaf_node_type)
1b24692f BK	340	return static_cast<leaf_pointer>(p_nd);
1b24692f BK	341	return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
4569a895 AT	342	}
	343
	344	inline static leaf_pointer
	345	rightmost_descendant(node_pointer p_nd)
	346	{
	347	if (p_nd->m_type == pat_trie_leaf_node_type)
1b24692f BK	348	return static_cast<leaf_pointer>(p_nd);
1b24692f BK	349	return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
4569a895 AT	350	}
	351
	352	public:
	353	node_pointer m_p_nd;
	354	};
	355
	356	// Iterator.
	357	template<typename Type_Traits,
	358	class Node,
	359	class Leaf,
	360	class Head,
	361	class Internal_Node,
	362	bool Is_Forward_Iterator,
	363	class Allocator>
	364	class pat_trie_it_ :
	365	public PB_DS_CONST_IT_C_DEC
	366
	367	{
4569a895 AT	368	private:
	369	typedef
	370	typename Allocator::template rebind<
	371	Node>::other::pointer
	372	node_pointer;
	373
	374	typedef
	375	typename Allocator::template rebind<
	376	Leaf>::other::const_pointer
	377	const_leaf_pointer;
	378
	379	typedef
	380	typename Allocator::template rebind<
	381	Leaf>::other::pointer
	382	leaf_pointer;
	383
	384	typedef
	385	typename Allocator::template rebind<
	386	Head>::other::pointer
	387	head_pointer;
	388
	389	typedef
	390	typename Allocator::template rebind<
	391	Internal_Node>::other::pointer
	392	internal_node_pointer;
	393
	394	public:
	395	typedef typename Type_Traits::value_type value_type;
	396
	397	typedef typename Type_Traits::const_pointer const_pointer;
	398
	399	typedef typename Type_Traits::pointer pointer;
	400
	401	typedef typename Type_Traits::const_reference const_reference;
	402
	403	typedef typename Type_Traits::reference reference;
	404
4569a895 AT	405	inline
	406	pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
	407	{ }
	408
	409	inline
	410	pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
	411	{ }
	412
	413	inline
	414	PB_DS_IT_C_DEC&
	415	operator=(const PB_DS_IT_C_DEC& other)
	416	{
	417	base_it_type::m_p_nd = other.m_p_nd;
1b24692f	418	return *this;
4569a895 AT	419	}
	420
	421	inline
	422	PB_DS_IT_C_DEC&
	423	operator=(const PB_DS_ODIR_IT_C_DEC& other)
	424	{
	425	base_it_type::m_p_nd = other.m_p_nd;
1b24692f	426	return *this;
4569a895 AT	427	}
	428
	429	inline pointer
	430	operator->() const
	431	{
1b24692f	432	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
4569a895	433
1b24692f	434	return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
4569a895 AT	435	}
	436
	437	inline reference
	438	operator*() const
	439	{
47bea7b8	440	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
1b24692f	441	return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
4569a895 AT	442	}
	443
	444	inline PB_DS_IT_C_DEC&
	445	operator++()
	446	{
	447	PB_DS_CONST_IT_C_DEC::
	448	operator++();
1b24692f	449	return *this;
4569a895 AT	450	}
	451
	452	inline PB_DS_IT_C_DEC
	453	operator++(int)
	454	{
47bea7b8	455	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
4569a895	456	operator++();
1b24692f	457	return ret_it;
4569a895 AT	458	}
	459
	460	inline PB_DS_IT_C_DEC&
	461	operator--()
	462	{
47bea7b8	463	PB_DS_CONST_IT_C_DEC::operator--();
1b24692f	464	return *this;
4569a895 AT	465	}
	466
	467	inline PB_DS_IT_C_DEC
	468	operator--(int)
	469	{
47bea7b8	470	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
4569a895	471	operator--();
1b24692f	472	return ret_it;
4569a895 AT	473	}
	474
	475	protected:
	476	typedef PB_DS_CONST_IT_C_DEC base_it_type;
	477
	478	friend class PB_DS_CLASS_C_DEC;
	479	};
	480
	481	#undef PB_DS_CONST_IT_C_DEC
4569a895	482	#undef PB_DS_CONST_ODIR_IT_C_DEC
4569a895	483	#undef PB_DS_IT_C_DEC
4569a895 AT	484	#undef PB_DS_ODIR_IT_C_DEC
4569a895 AT	485
4569a895	486	} // namespace detail
5e11f978	487	} // namespace __gnu_pbds
4569a895	488
47bea7b8	489	#endif
4569a895	490