// -*- C++ -*-
|
// -*- C++ -*-
|
|
|
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
|
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
|
//
|
//
|
// This file is part of the GNU ISO C++ Library. This library is free
|
// 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
|
// software; you can redistribute it and/or modify it under the terms
|
// of the GNU General Public License as published by the Free Software
|
// of the GNU General Public License as published by the Free Software
|
// Foundation; either version 3, or (at your option) any later
|
// Foundation; either version 3, or (at your option) any later
|
// version.
|
// version.
|
|
|
// This library is distributed in the hope that it will be useful, but
|
// This library is distributed in the hope that it will be useful, but
|
// WITHOUT ANY WARRANTY; without even the implied warranty of
|
// WITHOUT ANY WARRANTY; without even the implied warranty of
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
// General Public License for more details.
|
// General Public License for more details.
|
|
|
// Under Section 7 of GPL version 3, you are granted additional
|
// Under Section 7 of GPL version 3, you are granted additional
|
// permissions described in the GCC Runtime Library Exception, version
|
// permissions described in the GCC Runtime Library Exception, version
|
// 3.1, as published by the Free Software Foundation.
|
// 3.1, as published by the Free Software Foundation.
|
|
|
// You should have received a copy of the GNU General Public License and
|
// 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;
|
// a copy of the GCC Runtime Library Exception along with this program;
|
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
// <http://www.gnu.org/licenses/>.
|
// <http://www.gnu.org/licenses/>.
|
|
|
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
|
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
|
|
|
// Permission to use, copy, modify, sell, and distribute this software
|
// Permission to use, copy, modify, sell, and distribute this software
|
// is hereby granted without fee, provided that the above copyright
|
// is hereby granted without fee, provided that the above copyright
|
// notice appears in all copies, and that both that copyright notice
|
// notice appears in all copies, and that both that copyright notice
|
// and this permission notice appear in supporting documentation. None
|
// and this permission notice appear in supporting documentation. None
|
// of the above authors, nor IBM Haifa Research Laboratories, make any
|
// of the above authors, nor IBM Haifa Research Laboratories, make any
|
// representation about the suitability of this software for any
|
// representation about the suitability of this software for any
|
// purpose. It is provided "as is" without express or implied
|
// purpose. It is provided "as is" without express or implied
|
// warranty.
|
// warranty.
|
|
|
/**
|
/**
|
* @file point_iterators.hpp
|
* @file point_iterators.hpp
|
* Contains an implementation class for bin_search_tree_.
|
* Contains an implementation class for bin_search_tree_.
|
*/
|
*/
|
|
|
#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
|
#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
|
#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
|
#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
|
|
|
#include <debug/debug.h>
|
#include <debug/debug.h>
|
|
|
namespace __gnu_pbds
|
namespace __gnu_pbds
|
{
|
{
|
namespace detail
|
namespace detail
|
{
|
{
|
|
|
#define PB_DS_CONST_IT_C_DEC \
|
#define PB_DS_CONST_IT_C_DEC \
|
pat_trie_const_it_< \
|
pat_trie_const_it_< \
|
Type_Traits, \
|
Type_Traits, \
|
Node, \
|
Node, \
|
Leaf, \
|
Leaf, \
|
Head, \
|
Head, \
|
Internal_Node, \
|
Internal_Node, \
|
Is_Forward_Iterator, \
|
Is_Forward_Iterator, \
|
Allocator>
|
Allocator>
|
|
|
#define PB_DS_CONST_ODIR_IT_C_DEC \
|
#define PB_DS_CONST_ODIR_IT_C_DEC \
|
pat_trie_const_it_< \
|
pat_trie_const_it_< \
|
Type_Traits, \
|
Type_Traits, \
|
Node, \
|
Node, \
|
Leaf, \
|
Leaf, \
|
Head, \
|
Head, \
|
Internal_Node, \
|
Internal_Node, \
|
!Is_Forward_Iterator, \
|
!Is_Forward_Iterator, \
|
Allocator>
|
Allocator>
|
|
|
#define PB_DS_IT_C_DEC \
|
#define PB_DS_IT_C_DEC \
|
pat_trie_it_< \
|
pat_trie_it_< \
|
Type_Traits, \
|
Type_Traits, \
|
Node, \
|
Node, \
|
Leaf, \
|
Leaf, \
|
Head, \
|
Head, \
|
Internal_Node, \
|
Internal_Node, \
|
Is_Forward_Iterator, \
|
Is_Forward_Iterator, \
|
Allocator>
|
Allocator>
|
|
|
#define PB_DS_ODIR_IT_C_DEC \
|
#define PB_DS_ODIR_IT_C_DEC \
|
pat_trie_it_< \
|
pat_trie_it_< \
|
Type_Traits, \
|
Type_Traits, \
|
Node, \
|
Node, \
|
Leaf, \
|
Leaf, \
|
Head, \
|
Head, \
|
Internal_Node, \
|
Internal_Node, \
|
!Is_Forward_Iterator, \
|
!Is_Forward_Iterator, \
|
Allocator>
|
Allocator>
|
|
|
|
|
// Const iterator.
|
// Const iterator.
|
template<typename Type_Traits,
|
template<typename Type_Traits,
|
class Node,
|
class Node,
|
class Leaf,
|
class Leaf,
|
class Head,
|
class Head,
|
class Internal_Node,
|
class Internal_Node,
|
bool Is_Forward_Iterator,
|
bool Is_Forward_Iterator,
|
class Allocator>
|
class Allocator>
|
class pat_trie_const_it_
|
class pat_trie_const_it_
|
{
|
{
|
|
|
private:
|
private:
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Node>::other::pointer
|
Node>::other::pointer
|
node_pointer;
|
node_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Leaf>::other::const_pointer
|
Leaf>::other::const_pointer
|
const_leaf_pointer;
|
const_leaf_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Leaf>::other::pointer
|
Leaf>::other::pointer
|
leaf_pointer;
|
leaf_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Head>::other::pointer
|
Head>::other::pointer
|
head_pointer;
|
head_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Internal_Node>::other::pointer
|
Internal_Node>::other::pointer
|
internal_node_pointer;
|
internal_node_pointer;
|
|
|
public:
|
public:
|
|
|
typedef std::bidirectional_iterator_tag iterator_category;
|
typedef std::bidirectional_iterator_tag iterator_category;
|
|
|
typedef typename Allocator::difference_type difference_type;
|
typedef typename Allocator::difference_type difference_type;
|
|
|
typedef typename Type_Traits::value_type value_type;
|
typedef typename Type_Traits::value_type value_type;
|
|
|
typedef typename Type_Traits::pointer pointer;
|
typedef typename Type_Traits::pointer pointer;
|
|
|
typedef typename Type_Traits::const_pointer const_pointer;
|
typedef typename Type_Traits::const_pointer const_pointer;
|
|
|
typedef typename Type_Traits::reference reference;
|
typedef typename Type_Traits::reference reference;
|
|
|
typedef typename Type_Traits::const_reference const_reference;
|
typedef typename Type_Traits::const_reference const_reference;
|
|
|
public:
|
public:
|
|
|
inline
|
inline
|
pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
|
pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
|
{ }
|
{ }
|
|
|
inline
|
inline
|
pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
|
pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
|
: m_p_nd(other.m_p_nd)
|
: m_p_nd(other.m_p_nd)
|
{ }
|
{ }
|
|
|
inline
|
inline
|
PB_DS_CONST_IT_C_DEC&
|
PB_DS_CONST_IT_C_DEC&
|
operator=(const PB_DS_CONST_IT_C_DEC& other)
|
operator=(const PB_DS_CONST_IT_C_DEC& other)
|
{
|
{
|
m_p_nd = other.m_p_nd;
|
m_p_nd = other.m_p_nd;
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline
|
inline
|
PB_DS_CONST_IT_C_DEC&
|
PB_DS_CONST_IT_C_DEC&
|
operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
|
operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
|
{
|
{
|
m_p_nd = other.m_p_nd;
|
m_p_nd = other.m_p_nd;
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline const_pointer
|
inline const_pointer
|
operator->() const
|
operator->() const
|
{
|
{
|
_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
|
_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
|
return &static_cast<leaf_pointer>(m_p_nd)->value();
|
return &static_cast<leaf_pointer>(m_p_nd)->value();
|
}
|
}
|
|
|
inline const_reference
|
inline const_reference
|
operator*() const
|
operator*() const
|
{
|
{
|
_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
|
_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
|
return static_cast<leaf_pointer>(m_p_nd)->value();
|
return static_cast<leaf_pointer>(m_p_nd)->value();
|
}
|
}
|
|
|
inline bool
|
inline bool
|
operator==(const PB_DS_CONST_IT_C_DEC& other) const
|
operator==(const PB_DS_CONST_IT_C_DEC& other) const
|
{ return (m_p_nd == other.m_p_nd); }
|
{ return (m_p_nd == other.m_p_nd); }
|
|
|
inline bool
|
inline bool
|
operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
|
operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
|
{ return (m_p_nd == other.m_p_nd); }
|
{ return (m_p_nd == other.m_p_nd); }
|
|
|
inline bool
|
inline bool
|
operator!=(const PB_DS_CONST_IT_C_DEC& other) const
|
operator!=(const PB_DS_CONST_IT_C_DEC& other) const
|
{ return (m_p_nd != other.m_p_nd); }
|
{ return (m_p_nd != other.m_p_nd); }
|
|
|
inline bool
|
inline bool
|
operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
|
operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
|
{ return (m_p_nd != other.m_p_nd); }
|
{ return (m_p_nd != other.m_p_nd); }
|
|
|
inline PB_DS_CONST_IT_C_DEC&
|
inline PB_DS_CONST_IT_C_DEC&
|
operator++()
|
operator++()
|
{
|
{
|
inc(integral_constant<int,Is_Forward_Iterator>());
|
inc(integral_constant<int,Is_Forward_Iterator>());
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline PB_DS_CONST_IT_C_DEC
|
inline PB_DS_CONST_IT_C_DEC
|
operator++(int)
|
operator++(int)
|
{
|
{
|
PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
|
PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
|
operator++();
|
operator++();
|
return ret_it;
|
return ret_it;
|
}
|
}
|
|
|
inline PB_DS_CONST_IT_C_DEC&
|
inline PB_DS_CONST_IT_C_DEC&
|
operator--()
|
operator--()
|
{
|
{
|
dec(integral_constant<int,Is_Forward_Iterator>());
|
dec(integral_constant<int,Is_Forward_Iterator>());
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline PB_DS_CONST_IT_C_DEC
|
inline PB_DS_CONST_IT_C_DEC
|
operator--(int)
|
operator--(int)
|
{
|
{
|
PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
|
PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
|
operator--();
|
operator--();
|
return ret_it;
|
return ret_it;
|
}
|
}
|
|
|
protected:
|
protected:
|
inline void
|
inline void
|
inc(false_type)
|
inc(false_type)
|
{ dec(true_type()); }
|
{ dec(true_type()); }
|
|
|
void
|
void
|
inc(true_type)
|
inc(true_type)
|
{
|
{
|
if (m_p_nd->m_type == pat_trie_head_node_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;
|
m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
|
return;
|
return;
|
}
|
}
|
|
|
node_pointer p_y = m_p_nd->m_p_parent;
|
node_pointer p_y = m_p_nd->m_p_parent;
|
while (p_y->m_type != pat_trie_head_node_type &&
|
while (p_y->m_type != pat_trie_head_node_type &&
|
get_larger_sibling(m_p_nd) == NULL)
|
get_larger_sibling(m_p_nd) == NULL)
|
{
|
{
|
m_p_nd = p_y;
|
m_p_nd = p_y;
|
p_y = p_y->m_p_parent;
|
p_y = p_y->m_p_parent;
|
}
|
}
|
|
|
if (p_y->m_type == pat_trie_head_node_type)
|
if (p_y->m_type == pat_trie_head_node_type)
|
{
|
{
|
m_p_nd = p_y;
|
m_p_nd = p_y;
|
return;
|
return;
|
}
|
}
|
m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
|
m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
|
}
|
}
|
|
|
inline void
|
inline void
|
dec(false_type)
|
dec(false_type)
|
{ inc(true_type()); }
|
{ inc(true_type()); }
|
|
|
void
|
void
|
dec(true_type)
|
dec(true_type)
|
{
|
{
|
if (m_p_nd->m_type == pat_trie_head_node_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;
|
m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
|
return;
|
return;
|
}
|
}
|
|
|
node_pointer p_y = m_p_nd->m_p_parent;
|
node_pointer p_y = m_p_nd->m_p_parent;
|
while (p_y->m_type != pat_trie_head_node_type &&
|
while (p_y->m_type != pat_trie_head_node_type &&
|
get_smaller_sibling(m_p_nd) == NULL)
|
get_smaller_sibling(m_p_nd) == NULL)
|
{
|
{
|
m_p_nd = p_y;
|
m_p_nd = p_y;
|
p_y = p_y->m_p_parent;
|
p_y = p_y->m_p_parent;
|
}
|
}
|
|
|
if (p_y->m_type == pat_trie_head_node_type)
|
if (p_y->m_type == pat_trie_head_node_type)
|
{
|
{
|
m_p_nd = p_y;
|
m_p_nd = p_y;
|
return;
|
return;
|
}
|
}
|
m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
|
m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
|
}
|
}
|
|
|
inline static node_pointer
|
inline static node_pointer
|
get_larger_sibling(node_pointer p_nd)
|
get_larger_sibling(node_pointer p_nd)
|
{
|
{
|
internal_node_pointer p_parent =
|
internal_node_pointer p_parent =
|
static_cast<internal_node_pointer>(p_nd->m_p_parent);
|
static_cast<internal_node_pointer>(p_nd->m_p_parent);
|
|
|
typename Internal_Node::iterator it = p_parent->begin();
|
typename Internal_Node::iterator it = p_parent->begin();
|
while (*it != p_nd)
|
while (*it != p_nd)
|
++it;
|
++it;
|
|
|
typename Internal_Node::iterator next_it = it;
|
typename Internal_Node::iterator next_it = it;
|
++next_it;
|
++next_it;
|
return ((next_it == p_parent->end())? NULL :* next_it);
|
return ((next_it == p_parent->end())? NULL :* next_it);
|
}
|
}
|
|
|
inline static node_pointer
|
inline static node_pointer
|
get_smaller_sibling(node_pointer p_nd)
|
get_smaller_sibling(node_pointer p_nd)
|
{
|
{
|
internal_node_pointer p_parent =
|
internal_node_pointer p_parent =
|
static_cast<internal_node_pointer>(p_nd->m_p_parent);
|
static_cast<internal_node_pointer>(p_nd->m_p_parent);
|
|
|
typename Internal_Node::iterator it = p_parent->begin();
|
typename Internal_Node::iterator it = p_parent->begin();
|
|
|
if (*it == p_nd)
|
if (*it == p_nd)
|
return (NULL);
|
return (NULL);
|
typename Internal_Node::iterator prev_it;
|
typename Internal_Node::iterator prev_it;
|
do
|
do
|
{
|
{
|
prev_it = it;
|
prev_it = it;
|
++it;
|
++it;
|
if (*it == p_nd)
|
if (*it == p_nd)
|
return (*prev_it);
|
return (*prev_it);
|
}
|
}
|
while (true);
|
while (true);
|
|
|
_GLIBCXX_DEBUG_ASSERT(false);
|
_GLIBCXX_DEBUG_ASSERT(false);
|
return (NULL);
|
return (NULL);
|
}
|
}
|
|
|
inline static leaf_pointer
|
inline static leaf_pointer
|
leftmost_descendant(node_pointer p_nd)
|
leftmost_descendant(node_pointer p_nd)
|
{
|
{
|
if (p_nd->m_type == pat_trie_leaf_node_type)
|
if (p_nd->m_type == pat_trie_leaf_node_type)
|
return static_cast<leaf_pointer>(p_nd);
|
return static_cast<leaf_pointer>(p_nd);
|
return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
|
return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
|
}
|
}
|
|
|
inline static leaf_pointer
|
inline static leaf_pointer
|
rightmost_descendant(node_pointer p_nd)
|
rightmost_descendant(node_pointer p_nd)
|
{
|
{
|
if (p_nd->m_type == pat_trie_leaf_node_type)
|
if (p_nd->m_type == pat_trie_leaf_node_type)
|
return static_cast<leaf_pointer>(p_nd);
|
return static_cast<leaf_pointer>(p_nd);
|
return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
|
return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
|
}
|
}
|
|
|
public:
|
public:
|
node_pointer m_p_nd;
|
node_pointer m_p_nd;
|
};
|
};
|
|
|
// Iterator.
|
// Iterator.
|
template<typename Type_Traits,
|
template<typename Type_Traits,
|
class Node,
|
class Node,
|
class Leaf,
|
class Leaf,
|
class Head,
|
class Head,
|
class Internal_Node,
|
class Internal_Node,
|
bool Is_Forward_Iterator,
|
bool Is_Forward_Iterator,
|
class Allocator>
|
class Allocator>
|
class pat_trie_it_ :
|
class pat_trie_it_ :
|
public PB_DS_CONST_IT_C_DEC
|
public PB_DS_CONST_IT_C_DEC
|
|
|
{
|
{
|
private:
|
private:
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Node>::other::pointer
|
Node>::other::pointer
|
node_pointer;
|
node_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Leaf>::other::const_pointer
|
Leaf>::other::const_pointer
|
const_leaf_pointer;
|
const_leaf_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Leaf>::other::pointer
|
Leaf>::other::pointer
|
leaf_pointer;
|
leaf_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Head>::other::pointer
|
Head>::other::pointer
|
head_pointer;
|
head_pointer;
|
|
|
typedef
|
typedef
|
typename Allocator::template rebind<
|
typename Allocator::template rebind<
|
Internal_Node>::other::pointer
|
Internal_Node>::other::pointer
|
internal_node_pointer;
|
internal_node_pointer;
|
|
|
public:
|
public:
|
typedef typename Type_Traits::value_type value_type;
|
typedef typename Type_Traits::value_type value_type;
|
|
|
typedef typename Type_Traits::const_pointer const_pointer;
|
typedef typename Type_Traits::const_pointer const_pointer;
|
|
|
typedef typename Type_Traits::pointer pointer;
|
typedef typename Type_Traits::pointer pointer;
|
|
|
typedef typename Type_Traits::const_reference const_reference;
|
typedef typename Type_Traits::const_reference const_reference;
|
|
|
typedef typename Type_Traits::reference reference;
|
typedef typename Type_Traits::reference reference;
|
|
|
inline
|
inline
|
pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
|
pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
|
{ }
|
{ }
|
|
|
inline
|
inline
|
pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
|
pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
|
{ }
|
{ }
|
|
|
inline
|
inline
|
PB_DS_IT_C_DEC&
|
PB_DS_IT_C_DEC&
|
operator=(const PB_DS_IT_C_DEC& other)
|
operator=(const PB_DS_IT_C_DEC& other)
|
{
|
{
|
base_it_type::m_p_nd = other.m_p_nd;
|
base_it_type::m_p_nd = other.m_p_nd;
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline
|
inline
|
PB_DS_IT_C_DEC&
|
PB_DS_IT_C_DEC&
|
operator=(const PB_DS_ODIR_IT_C_DEC& other)
|
operator=(const PB_DS_ODIR_IT_C_DEC& other)
|
{
|
{
|
base_it_type::m_p_nd = other.m_p_nd;
|
base_it_type::m_p_nd = other.m_p_nd;
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline pointer
|
inline pointer
|
operator->() const
|
operator->() const
|
{
|
{
|
_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
|
_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();
|
return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
|
}
|
}
|
|
|
inline reference
|
inline reference
|
operator*() const
|
operator*() const
|
{
|
{
|
_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
|
_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();
|
return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
|
}
|
}
|
|
|
inline PB_DS_IT_C_DEC&
|
inline PB_DS_IT_C_DEC&
|
operator++()
|
operator++()
|
{
|
{
|
PB_DS_CONST_IT_C_DEC::
|
PB_DS_CONST_IT_C_DEC::
|
operator++();
|
operator++();
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline PB_DS_IT_C_DEC
|
inline PB_DS_IT_C_DEC
|
operator++(int)
|
operator++(int)
|
{
|
{
|
PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
|
PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
|
operator++();
|
operator++();
|
return ret_it;
|
return ret_it;
|
}
|
}
|
|
|
inline PB_DS_IT_C_DEC&
|
inline PB_DS_IT_C_DEC&
|
operator--()
|
operator--()
|
{
|
{
|
PB_DS_CONST_IT_C_DEC::operator--();
|
PB_DS_CONST_IT_C_DEC::operator--();
|
return *this;
|
return *this;
|
}
|
}
|
|
|
inline PB_DS_IT_C_DEC
|
inline PB_DS_IT_C_DEC
|
operator--(int)
|
operator--(int)
|
{
|
{
|
PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
|
PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
|
operator--();
|
operator--();
|
return ret_it;
|
return ret_it;
|
}
|
}
|
|
|
protected:
|
protected:
|
typedef PB_DS_CONST_IT_C_DEC base_it_type;
|
typedef PB_DS_CONST_IT_C_DEC base_it_type;
|
|
|
friend class PB_DS_CLASS_C_DEC;
|
friend class PB_DS_CLASS_C_DEC;
|
};
|
};
|
|
|
#undef PB_DS_CONST_IT_C_DEC
|
#undef PB_DS_CONST_IT_C_DEC
|
#undef PB_DS_CONST_ODIR_IT_C_DEC
|
#undef PB_DS_CONST_ODIR_IT_C_DEC
|
#undef PB_DS_IT_C_DEC
|
#undef PB_DS_IT_C_DEC
|
#undef PB_DS_ODIR_IT_C_DEC
|
#undef PB_DS_ODIR_IT_C_DEC
|
|
|
} // namespace detail
|
} // namespace detail
|
} // namespace __gnu_pbds
|
} // namespace __gnu_pbds
|
|
|
#endif
|
#endif
|
|
|
|
|