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

// -*- C++ -*-

// Copyright (C) 2005, 2006, 2009 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 3, 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.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

// 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++ --
4569a895 AT	2
748086b7	3	// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
4569a895 AT	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
748086b7	8	// Foundation; either version 3, or (at your option) any later
4569a895 AT	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
748086b7 JJ	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.
4569a895	19
748086b7 JJ	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/>.
4569a895 AT	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 point_iterators.hpp
	38	* Contains an implementation class for bin_search_tree_.
	39	*/
	40
	41	#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
	42	#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
	43
47bea7b8	44	#include <debug/debug.h>
4569a895	45
5e11f978	46	namespace __gnu_pbds
4569a895 AT	47	{
	48	namespace detail
	49	{
	50
	51	#define PB_DS_CONST_IT_C_DEC \
	52	pat_trie_const_it_< \
	53	Type_Traits, \
	54	Node, \
	55	Leaf, \
	56	Head, \
	57	Internal_Node, \
	58	Is_Forward_Iterator, \
	59	Allocator>
	60
	61	#define PB_DS_CONST_ODIR_IT_C_DEC \
	62	pat_trie_const_it_< \
	63	Type_Traits, \
	64	Node, \
	65	Leaf, \
	66	Head, \
	67	Internal_Node, \
	68	!Is_Forward_Iterator, \
	69	Allocator>
	70
	71	#define PB_DS_IT_C_DEC \
	72	pat_trie_it_< \
	73	Type_Traits, \
	74	Node, \
	75	Leaf, \
	76	Head, \
	77	Internal_Node, \
	78	Is_Forward_Iterator, \
	79	Allocator>
	80
	81	#define PB_DS_ODIR_IT_C_DEC \
	82	pat_trie_it_< \
	83	Type_Traits, \
	84	Node, \
	85	Leaf, \
	86	Head, \
	87	Internal_Node, \
	88	!Is_Forward_Iterator, \
	89	Allocator>
	90
4569a895 AT	91
	92	// Const iterator.
	93	template<typename Type_Traits,
	94	class Node,
	95	class Leaf,
	96	class Head,
	97	class Internal_Node,
	98	bool Is_Forward_Iterator,
	99	class Allocator>
	100	class pat_trie_const_it_
	101	{
	102
	103	private:
	104	typedef
	105	typename Allocator::template rebind<
	106	Node>::other::pointer
	107	node_pointer;
	108
	109	typedef
	110	typename Allocator::template rebind<
	111	Leaf>::other::const_pointer
	112	const_leaf_pointer;
	113
	114	typedef
	115	typename Allocator::template rebind<
	116	Leaf>::other::pointer
	117	leaf_pointer;
	118
	119	typedef
	120	typename Allocator::template rebind<
	121	Head>::other::pointer
	122	head_pointer;
	123
	124	typedef
	125	typename Allocator::template rebind<
	126	Internal_Node>::other::pointer
	127	internal_node_pointer;
	128
	129	public:
	130
	131	typedef std::bidirectional_iterator_tag iterator_category;
	132
	133	typedef typename Allocator::difference_type difference_type;
	134
	135	typedef typename Type_Traits::value_type value_type;
	136
	137	typedef typename Type_Traits::pointer pointer;
	138
	139	typedef typename Type_Traits::const_pointer const_pointer;
	140
	141	typedef typename Type_Traits::reference reference;
	142
	143	typedef typename Type_Traits::const_reference const_reference;
	144
	145	public:
	146
	147	inline
	148	pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
	149	{ }
	150
	151	inline
47bea7b8 BK	152	pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
47bea7b8 BK	153	: m_p_nd(other.m_p_nd)
4569a895 AT	154	{ }
	155
	156	inline
	157	PB_DS_CONST_IT_C_DEC&
47bea7b8	158	operator=(const PB_DS_CONST_IT_C_DEC& other)
4569a895 AT	159	{
4569a895 AT	160	m_p_nd = other.m_p_nd;
1b24692f	161	return *this;
4569a895 AT	162	}
	163
	164	inline
	165	PB_DS_CONST_IT_C_DEC&
47bea7b8	166	operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
4569a895 AT	167	{
4569a895 AT	168	m_p_nd = other.m_p_nd;
1b24692f	169	return *this;
4569a895 AT	170	}
	171
	172	inline const_pointer
	173	operator->() const
	174	{
47bea7b8	175	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
1b24692f	176	return &static_cast<leaf_pointer>(m_p_nd)->value();
4569a895 AT	177	}
	178
	179	inline const_reference
	180	operator*() const
	181	{
47bea7b8	182	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
1b24692f	183	return static_cast<leaf_pointer>(m_p_nd)->value();
4569a895 AT	184	}
	185
	186	inline bool
47bea7b8	187	operator==(const PB_DS_CONST_IT_C_DEC& other) const
1b24692f	188	{ return (m_p_nd == other.m_p_nd); }
4569a895 AT	189
4569a895 AT	190	inline bool
47bea7b8	191	operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
1b24692f	192	{ return (m_p_nd == other.m_p_nd); }
4569a895 AT	193
4569a895 AT	194	inline bool
47bea7b8	195	operator!=(const PB_DS_CONST_IT_C_DEC& other) const
1b24692f	196	{ return (m_p_nd != other.m_p_nd); }
4569a895 AT	197
4569a895 AT	198	inline bool
47bea7b8	199	operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
1b24692f	200	{ return (m_p_nd != other.m_p_nd); }
4569a895 AT	201
	202	inline PB_DS_CONST_IT_C_DEC&
	203	operator++()
	204	{
	205	inc(integral_constant<int,Is_Forward_Iterator>());
1b24692f	206	return *this;
4569a895 AT	207	}
	208
	209	inline PB_DS_CONST_IT_C_DEC
	210	operator++(int)
	211	{
47bea7b8	212	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
4569a895	213	operator++();
1b24692f	214	return ret_it;
4569a895 AT	215	}
	216
	217	inline PB_DS_CONST_IT_C_DEC&
	218	operator--()
	219	{
	220	dec(integral_constant<int,Is_Forward_Iterator>());
1b24692f	221	return *this;
4569a895 AT	222	}
	223
	224	inline PB_DS_CONST_IT_C_DEC
	225	operator--(int)
	226	{
47bea7b8	227	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
4569a895	228	operator--();
1b24692f	229	return ret_it;
4569a895 AT	230	}
	231
	232	protected:
	233	inline void
	234	inc(false_type)
47bea7b8	235	{ dec(true_type()); }
4569a895 AT	236
	237	void
	238	inc(true_type)
	239	{
	240	if (m_p_nd->m_type == pat_trie_head_node_type)
	241	{
	242	m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
4569a895 AT	243	return;
	244	}
	245
	246	node_pointer p_y = m_p_nd->m_p_parent;
47bea7b8	247	while (p_y->m_type != pat_trie_head_node_type &&
4569a895 AT	248	get_larger_sibling(m_p_nd) == NULL)
	249	{
	250	m_p_nd = p_y;
4569a895 AT	251	p_y = p_y->m_p_parent;
	252	}
	253
	254	if (p_y->m_type == pat_trie_head_node_type)
	255	{
	256	m_p_nd = p_y;
4569a895 AT	257	return;
4569a895 AT	258	}
4569a895 AT	259	m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
	260	}
	261
	262	inline void
	263	dec(false_type)
47bea7b8	264	{ inc(true_type()); }
4569a895 AT	265
	266	void
	267	dec(true_type)
	268	{
	269	if (m_p_nd->m_type == pat_trie_head_node_type)
	270	{
	271	m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
4569a895 AT	272	return;
	273	}
	274
	275	node_pointer p_y = m_p_nd->m_p_parent;
47bea7b8	276	while (p_y->m_type != pat_trie_head_node_type &&
4569a895 AT	277	get_smaller_sibling(m_p_nd) == NULL)
	278	{
	279	m_p_nd = p_y;
4569a895 AT	280	p_y = p_y->m_p_parent;
	281	}
	282
	283	if (p_y->m_type == pat_trie_head_node_type)
	284	{
	285	m_p_nd = p_y;
4569a895 AT	286	return;
4569a895 AT	287	}
4569a895 AT	288	m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
	289	}
	290
	291	inline static node_pointer
	292	get_larger_sibling(node_pointer p_nd)
	293	{
	294	internal_node_pointer p_parent =
	295	static_cast<internal_node_pointer>(p_nd->m_p_parent);
	296
	297	typename Internal_Node::iterator it = p_parent->begin();
4569a895 AT	298	while (*it != p_nd)
	299	++it;
	300
	301	typename Internal_Node::iterator next_it = it;
	302	++next_it;
4569a895 AT	303	return ((next_it == p_parent->end())? NULL :* next_it);
	304	}
	305
	306	inline static node_pointer
	307	get_smaller_sibling(node_pointer p_nd)
	308	{
	309	internal_node_pointer p_parent =
	310	static_cast<internal_node_pointer>(p_nd->m_p_parent);
	311
	312	typename Internal_Node::iterator it = p_parent->begin();
	313
	314	if (*it == p_nd)
	315	return (NULL);
4569a895	316	typename Internal_Node::iterator prev_it;
4569a895 AT	317	do
	318	{
	319	prev_it = it;
4569a895	320	++it;
4569a895 AT	321	if (*it == p_nd)
	322	return (*prev_it);
	323	}
	324	while (true);
	325
47bea7b8	326	_GLIBCXX_DEBUG_ASSERT(false);
4569a895 AT	327	return (NULL);
	328	}
	329
	330	inline static leaf_pointer
	331	leftmost_descendant(node_pointer p_nd)
	332	{
	333	if (p_nd->m_type == pat_trie_leaf_node_type)
1b24692f BK	334	return static_cast<leaf_pointer>(p_nd);
1b24692f BK	335	return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
4569a895 AT	336	}
	337
	338	inline static leaf_pointer
	339	rightmost_descendant(node_pointer p_nd)
	340	{
	341	if (p_nd->m_type == pat_trie_leaf_node_type)
1b24692f BK	342	return static_cast<leaf_pointer>(p_nd);
1b24692f BK	343	return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
4569a895 AT	344	}
	345
	346	public:
	347	node_pointer m_p_nd;
	348	};
	349
	350	// Iterator.
	351	template<typename Type_Traits,
	352	class Node,
	353	class Leaf,
	354	class Head,
	355	class Internal_Node,
	356	bool Is_Forward_Iterator,
	357	class Allocator>
	358	class pat_trie_it_ :
	359	public PB_DS_CONST_IT_C_DEC
	360
	361	{
4569a895 AT	362	private:
	363	typedef
	364	typename Allocator::template rebind<
	365	Node>::other::pointer
	366	node_pointer;
	367
	368	typedef
	369	typename Allocator::template rebind<
	370	Leaf>::other::const_pointer
	371	const_leaf_pointer;
	372
	373	typedef
	374	typename Allocator::template rebind<
	375	Leaf>::other::pointer
	376	leaf_pointer;
	377
	378	typedef
	379	typename Allocator::template rebind<
	380	Head>::other::pointer
	381	head_pointer;
	382
	383	typedef
	384	typename Allocator::template rebind<
	385	Internal_Node>::other::pointer
	386	internal_node_pointer;
	387
	388	public:
	389	typedef typename Type_Traits::value_type value_type;
	390
	391	typedef typename Type_Traits::const_pointer const_pointer;
	392
	393	typedef typename Type_Traits::pointer pointer;
	394
	395	typedef typename Type_Traits::const_reference const_reference;
	396
	397	typedef typename Type_Traits::reference reference;
	398
4569a895 AT	399	inline
	400	pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
	401	{ }
	402
	403	inline
	404	pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
	405	{ }
	406
	407	inline
	408	PB_DS_IT_C_DEC&
	409	operator=(const PB_DS_IT_C_DEC& other)
	410	{
	411	base_it_type::m_p_nd = other.m_p_nd;
1b24692f	412	return *this;
4569a895 AT	413	}
	414
	415	inline
	416	PB_DS_IT_C_DEC&
	417	operator=(const PB_DS_ODIR_IT_C_DEC& other)
	418	{
	419	base_it_type::m_p_nd = other.m_p_nd;
1b24692f	420	return *this;
4569a895 AT	421	}
	422
	423	inline pointer
	424	operator->() const
	425	{
1b24692f	426	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
4569a895	427
1b24692f	428	return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
4569a895 AT	429	}
	430
	431	inline reference
	432	operator*() const
	433	{
47bea7b8	434	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
1b24692f	435	return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
4569a895 AT	436	}
	437
	438	inline PB_DS_IT_C_DEC&
	439	operator++()
	440	{
	441	PB_DS_CONST_IT_C_DEC::
	442	operator++();
1b24692f	443	return *this;
4569a895 AT	444	}
	445
	446	inline PB_DS_IT_C_DEC
	447	operator++(int)
	448	{
47bea7b8	449	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
4569a895	450	operator++();
1b24692f	451	return ret_it;
4569a895 AT	452	}
	453
	454	inline PB_DS_IT_C_DEC&
	455	operator--()
	456	{
47bea7b8	457	PB_DS_CONST_IT_C_DEC::operator--();
1b24692f	458	return *this;
4569a895 AT	459	}
	460
	461	inline PB_DS_IT_C_DEC
	462	operator--(int)
	463	{
47bea7b8	464	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
4569a895	465	operator--();
1b24692f	466	return ret_it;
4569a895 AT	467	}
	468
	469	protected:
	470	typedef PB_DS_CONST_IT_C_DEC base_it_type;
	471
	472	friend class PB_DS_CLASS_C_DEC;
	473	};
	474
	475	#undef PB_DS_CONST_IT_C_DEC
4569a895	476	#undef PB_DS_CONST_ODIR_IT_C_DEC
4569a895	477	#undef PB_DS_IT_C_DEC
4569a895 AT	478	#undef PB_DS_ODIR_IT_C_DEC
4569a895 AT	479
4569a895	480	} // namespace detail
5e11f978	481	} // namespace __gnu_pbds
4569a895	482
47bea7b8	483	#endif
4569a895	484