OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /openrisc/tags/gnu-src/gcc-4.5.1/gcc-4.5.1-or32-1.0rc4/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_
    from Rev 424 to Rev 519
    ↔ Reverse comparison
  •

Rev 424 → Rev 519

/find_fn_imps.hpp
0,0 → 1,182
// -*- 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 find_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
lower_bound(const_key_reference r_key) const
{
node_pointer p_pot = m_p_head;
node_pointer p_nd = m_p_head->m_p_parent;
 
while (p_nd != NULL)
if (Cmp_Fn::operator()(
PB_DS_V2F(p_nd->m_value),
r_key))
p_nd = p_nd->m_p_right;
else
{
p_pot = p_nd;
 
p_nd = p_nd->m_p_left;
}
 
return (iterator(p_pot));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
lower_bound(const_key_reference r_key)
{
node_pointer p_pot = m_p_head;
node_pointer p_nd = m_p_head->m_p_parent;
 
while (p_nd != NULL)
if (Cmp_Fn::operator()(
PB_DS_V2F(p_nd->m_value),
r_key))
p_nd = p_nd->m_p_right;
else
{
p_pot = p_nd;
 
p_nd = p_nd->m_p_left;
}
 
return (iterator(p_pot));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
upper_bound(const_key_reference r_key) const
{
node_pointer p_pot = m_p_head;
node_pointer p_nd = m_p_head->m_p_parent;
 
while (p_nd != NULL)
if (Cmp_Fn::operator()(r_key,
PB_DS_V2F(p_nd->m_value)))
{
p_pot = p_nd,
 
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
 
return (const_iterator(p_pot));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
upper_bound(const_key_reference r_key)
{
node_pointer p_pot = m_p_head;
node_pointer p_nd = m_p_head->m_p_parent;
 
while (p_nd != NULL)
if (Cmp_Fn::operator()(r_key,
PB_DS_V2F(p_nd->m_value)))
{
p_pot = p_nd,
 
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
 
return (point_iterator(p_pot));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
find(const_key_reference r_key)
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
 
node_pointer p_pot = m_p_head;
node_pointer p_nd = m_p_head->m_p_parent;
 
while (p_nd != NULL)
if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
{
p_pot = p_nd;
 
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
 
return point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()(
r_key,
PB_DS_V2F(p_pot->m_value)))?
m_p_head : p_pot);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
find(const_key_reference r_key) const
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
 
node_pointer p_pot = m_p_head;
node_pointer p_nd = m_p_head->m_p_parent;
 
while (p_nd != NULL)
if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
{
p_pot = p_nd;
 
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
 
return const_point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()(
r_key,
PB_DS_V2F(p_pot->m_value)))?
m_p_head : p_pot);
}
 
/policy_access_fn_imps.hpp
0,0 → 1,56
// -*- 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 policy_access_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
Cmp_Fn&
PB_DS_CLASS_C_DEC::
get_cmp_fn()
{
return (*this);
}
 
PB_DS_CLASS_T_DEC
const Cmp_Fn&
PB_DS_CLASS_C_DEC::
get_cmp_fn() const
{
return (*this);
}
 
/r_erase_fn_imps.hpp
0,0 → 1,120
// -*- 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 r_erase_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
actual_erase_node(node_pointer p_z)
{
_GLIBCXX_DEBUG_ASSERT(m_size > 0);
--m_size;
 
_GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value)));
 
p_z->~node();
 
s_node_allocator.deallocate(p_z, 1);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
update_min_max_for_erased_node(node_pointer p_z)
{
if (m_size == 1)
{
m_p_head->m_p_left = m_p_head->m_p_right = m_p_head;
 
return;
}
 
if (m_p_head->m_p_left == p_z)
{
iterator it(p_z);
 
++it;
 
m_p_head->m_p_left = it.m_p_nd;
}
else if (m_p_head->m_p_right == p_z)
{
iterator it(p_z);
 
--it;
 
m_p_head->m_p_right = it.m_p_nd;
}
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
 
clear_imp(m_p_head->m_p_parent);
 
m_size = 0;
 
initialize();
 
_GLIBCXX_DEBUG_ONLY(debug_base::clear();)
 
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear_imp(node_pointer p_nd)
{
if (p_nd == NULL)
return;
 
clear_imp(p_nd->m_p_left);
 
clear_imp(p_nd->m_p_right);
 
p_nd->~Node();
 
s_node_allocator.deallocate(p_nd, 1);
}
 
/constructors_destructor_fn_imps.hpp
0,0 → 1,218
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2007, 2008, 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 constructors_destructor_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_allocator
PB_DS_CLASS_C_DEC::s_node_allocator;
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0)
{
initialize();
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
Cmp_Fn(r_cmp_fn), m_p_head(s_node_allocator.allocate(1)), m_size(0)
{
initialize();
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
Cmp_Fn(r_cmp_fn),
node_update(r_node_update),
m_p_head(s_node_allocator.allocate(1)),
m_size(0)
{
initialize();
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) :
#ifdef _GLIBCXX_DEBUG
debug_base(other),
#endif
#ifdef PB_DS_TREE_TRACE
PB_DS_TREE_TRACE_BASE_C_DEC(other),
#endif
Cmp_Fn(other),
node_update(other),
m_p_head(s_node_allocator.allocate(1)),
m_size(0)
{
initialize();
m_size = other.m_size;
_GLIBCXX_DEBUG_ONLY(other.structure_only_assert_valid();)
 
__try
{
m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent);
if (m_p_head->m_p_parent != NULL)
m_p_head->m_p_parent->m_p_parent = m_p_head;
m_size = other.m_size;
initialize_min_max();
}
__catch(...)
{
_GLIBCXX_DEBUG_ONLY(debug_base::clear();)
s_node_allocator.deallocate(m_p_head, 1);
__throw_exception_again;
}
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.structure_only_assert_valid();)
value_swap(other);
std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other);
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
value_swap(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(debug_base::swap(other);)
std::swap(m_p_head, other.m_p_head);
std::swap(m_size, other.m_size);
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~PB_DS_CLASS_NAME()
{
clear();
s_node_allocator.deallocate(m_p_head, 1);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
initialize()
{
m_p_head->m_p_parent = NULL;
m_p_head->m_p_left = m_p_head;
m_p_head->m_p_right = m_p_head;
m_size = 0;
}
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
recursive_copy_node(const node_pointer p_nd)
{
if (p_nd == NULL)
return (NULL);
 
node_pointer p_ret = s_node_allocator.allocate(1);
__try
{
new (p_ret) node(*p_nd);
}
__catch(...)
{
s_node_allocator.deallocate(p_ret, 1);
__throw_exception_again;
}
 
p_ret->m_p_left = p_ret->m_p_right = NULL;
 
__try
{
p_ret->m_p_left = recursive_copy_node(p_nd->m_p_left);
p_ret->m_p_right = recursive_copy_node(p_nd->m_p_right);
}
__catch(...)
{
clear_imp(p_ret);
__throw_exception_again;
}
 
if (p_ret->m_p_left != NULL)
p_ret->m_p_left->m_p_parent = p_ret;
 
if (p_ret->m_p_right != NULL)
p_ret->m_p_right->m_p_parent = p_ret;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_ret);)
return p_ret;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
initialize_min_max()
{
if (m_p_head->m_p_parent == NULL)
{
m_p_head->m_p_left = m_p_head->m_p_right = m_p_head;
return;
}
 
{
node_pointer p_min = m_p_head->m_p_parent;
while (p_min->m_p_left != NULL)
p_min = p_min->m_p_left;
m_p_head->m_p_left = p_min;
}
 
{
node_pointer p_max = m_p_head->m_p_parent;
while (p_max->m_p_right != NULL)
p_max = p_max->m_p_right;
m_p_head->m_p_right = p_max;
}
}
 
/debug_fn_imps.hpp
0,0 → 1,272
// -*- 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 debug_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
#ifdef _GLIBCXX_DEBUG
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
structure_only_assert_valid();
assert_consistent_with_debug_base();
assert_size();
assert_iterators();
if (m_p_head->m_p_parent == NULL)
{
_GLIBCXX_DEBUG_ASSERT(m_size == 0);
}
else
{
_GLIBCXX_DEBUG_ASSERT(m_size > 0);
}
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
structure_only_assert_valid() const
{
_GLIBCXX_DEBUG_ASSERT(m_p_head != NULL);
if (m_p_head->m_p_parent == NULL)
{
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head);
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head);
}
else
{
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head);
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head);
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head);
}
 
if (m_p_head->m_p_parent != NULL)
assert_node_consistent(m_p_head->m_p_parent);
assert_min();
assert_max();
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_node_consistent(const node_pointer p_nd) const
{
assert_node_consistent_(p_nd);
}
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_consistent_t
PB_DS_CLASS_C_DEC::
assert_node_consistent_(const node_pointer p_nd) const
{
if (p_nd == NULL)
return (std::make_pair((const_pointer)NULL,(const_pointer)NULL));
 
assert_node_consistent_with_left(p_nd);
assert_node_consistent_with_right(p_nd);
 
const std::pair<const_pointer, const_pointer>
l_range = assert_node_consistent_(p_nd->m_p_left);
 
if (l_range.second != NULL)
_GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second),
PB_DS_V2F(p_nd->m_value)));
 
const std::pair<const_pointer, const_pointer>
r_range = assert_node_consistent_(p_nd->m_p_right);
 
if (r_range.first != NULL)
_GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value),
PB_DS_V2F(*r_range.first)));
 
return (std::make_pair((l_range.first != NULL)? l_range.first :& p_nd->m_value,(r_range.second != NULL)? r_range.second :& p_nd->m_value));
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_node_consistent_with_left(const node_pointer p_nd) const
{
if (p_nd->m_p_left == NULL)
return;
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd);
_GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value),
PB_DS_V2F(p_nd->m_p_left->m_value)));
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_node_consistent_with_right(const node_pointer p_nd) const
{
if (p_nd->m_p_right == NULL)
return;
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd);
_GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value),
PB_DS_V2F(p_nd->m_value)));
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_min() const
{
assert_min_imp(m_p_head->m_p_parent);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_min_imp(const node_pointer p_nd) const
{
if (p_nd == NULL)
{
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head);
return;
}
 
if (p_nd->m_p_left == NULL)
{
_GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left);
return;
}
assert_min_imp(p_nd->m_p_left);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_max() const
{
assert_max_imp(m_p_head->m_p_parent);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_max_imp(const node_pointer p_nd) const
{
if (p_nd == NULL)
{
_GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head);
return;
}
 
if (p_nd->m_p_right == NULL)
{
_GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right);
return;
}
 
assert_max_imp(p_nd->m_p_right);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_iterators() const
{
size_type iterated_num = 0;
const_iterator prev_it = end();
for (const_iterator it = begin(); it != end(); ++it)
{
++iterated_num;
_GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd);
const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it));
--upper_bound_it;
_GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd);
 
if (prev_it != end())
_GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it),
PB_DS_V2F(*it)));
prev_it = it;
}
 
_GLIBCXX_DEBUG_ASSERT(iterated_num == m_size);
size_type reverse_iterated_num = 0;
const_reverse_iterator reverse_prev_it = rend();
for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend();
++reverse_it)
{
++reverse_iterated_num;
_GLIBCXX_DEBUG_ASSERT(lower_bound(
PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd);
 
const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it));
--upper_bound_it;
_GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd);
if (reverse_prev_it != rend())
_GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it),
PB_DS_V2F(*reverse_it)));
reverse_prev_it = reverse_it;
}
_GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_consistent_with_debug_base() const
{
debug_base::check_size(m_size);
assert_consistent_with_debug_base(m_p_head->m_p_parent);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_consistent_with_debug_base(const node_pointer p_nd) const
{
if (p_nd == NULL)
return;
debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value));
assert_consistent_with_debug_base(p_nd->m_p_left);
assert_consistent_with_debug_base(p_nd->m_p_right);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_size() const
{
_GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size);
}
 
#endif
/traits.hpp
0,0 → 1,250
// -*- 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 traits.hpp
* Contains an implementation for bin_search_tree_.
*/
 
#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
 
#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
 
namespace __gnu_pbds
{
namespace detail
{
 
template<typename Key,
typename Mapped,
class Cmp_Fn,
template<typename Const_Node_Iterator,
class Node_Iterator,
class Cmp_Fn,
class Allocator>
class Node_Update,
class Node,
class Allocator>
struct bin_search_tree_traits
{
private:
typedef
types_traits<
Key,
Mapped,
Allocator,
false>
type_traits;
 
public:
typedef Node node;
 
typedef
bin_search_tree_const_it_<
typename Allocator::template rebind<
node>::other::pointer,
typename type_traits::value_type,
typename type_traits::pointer,
typename type_traits::const_pointer,
typename type_traits::reference,
typename type_traits::const_reference,
true,
Allocator>
const_point_iterator;
 
typedef
bin_search_tree_it_<
typename Allocator::template rebind<
node>::other::pointer,
typename type_traits::value_type,
typename type_traits::pointer,
typename type_traits::const_pointer,
typename type_traits::reference,
typename type_traits::const_reference,
true,
Allocator>
point_iterator;
 
typedef
bin_search_tree_const_it_<
typename Allocator::template rebind<
node>::other::pointer,
typename type_traits::value_type,
typename type_traits::pointer,
typename type_traits::const_pointer,
typename type_traits::reference,
typename type_traits::const_reference,
false,
Allocator>
const_reverse_iterator;
 
typedef
bin_search_tree_it_<
typename Allocator::template rebind<
node>::other::pointer,
typename type_traits::value_type,
typename type_traits::pointer,
typename type_traits::const_pointer,
typename type_traits::reference,
typename type_traits::const_reference,
false,
Allocator>
reverse_iterator;
 
typedef
bin_search_tree_const_node_it_<
Node,
const_point_iterator,
point_iterator,
Allocator>
const_node_iterator;
 
typedef
bin_search_tree_node_it_<
Node,
const_point_iterator,
point_iterator,
Allocator>
node_iterator;
 
typedef
Node_Update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>
node_update;
 
typedef
__gnu_pbds::null_tree_node_update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>*
null_node_update_pointer;
};
 
template<typename Key,
class Cmp_Fn,
template<typename Const_Node_Iterator,
class Node_Iterator,
class Cmp_Fn,
class Allocator>
class Node_Update,
class Node,
class Allocator>
struct bin_search_tree_traits<
Key,
null_mapped_type,
Cmp_Fn,
Node_Update,
Node,
Allocator>
{
private:
typedef
types_traits<
Key,
null_mapped_type,
Allocator,
false>
type_traits;
 
public:
typedef Node node;
 
typedef
bin_search_tree_const_it_<
typename Allocator::template rebind<
node>::other::pointer,
typename type_traits::value_type,
typename type_traits::pointer,
typename type_traits::const_pointer,
typename type_traits::reference,
typename type_traits::const_reference,
true,
Allocator>
const_point_iterator;
 
typedef const_point_iterator point_iterator;
 
typedef
bin_search_tree_const_it_<
typename Allocator::template rebind<
node>::other::pointer,
typename type_traits::value_type,
typename type_traits::pointer,
typename type_traits::const_pointer,
typename type_traits::reference,
typename type_traits::const_reference,
false,
Allocator>
const_reverse_iterator;
 
typedef const_reverse_iterator reverse_iterator;
 
typedef
bin_search_tree_const_node_it_<
Node,
const_point_iterator,
point_iterator,
Allocator>
const_node_iterator;
 
typedef const_node_iterator node_iterator;
 
typedef
Node_Update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>
node_update;
 
typedef
__gnu_pbds::null_tree_node_update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>*
null_node_update_pointer;
};
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
/cond_dtor_entry_dealtor.hpp
0,0 → 1,70
// -*- 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 cond_dtor_entry_dealtor.hpp
* Contains a binary tree container conditional deallocator
*/
 
class bin_search_tree_cond_dtor_entry_dealtor_
{
public:
inline
bin_search_tree_cond_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd),
m_no_action_dtor(false)
{ }
 
inline void
set_no_action_dtor()
{
m_no_action_dtor = true;
}
 
inline
~bin_search_tree_cond_dtor_entry_dealtor_()
{
if (m_no_action_dtor)
return;
 
typename Allocator::template rebind<Node>::other().
deallocate(m_p_nd, 1);
}
 
protected:
node_pointer m_p_nd;
 
bool m_no_action_dtor;
};
 
/info_fn_imps.hpp
0,0 → 1,64
// -*- 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 info_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
empty() const
{
return (m_size == 0);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
size() const
{
return (m_size);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
max_size() const
{
return (s_node_allocator.max_size());
}
 
/rotate_fn_imps.hpp
0,0 → 1,156
// -*- 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 rotate_fn_imps.hpp
* Contains imps for rotating nodes.
*/
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
rotate_left(node_pointer p_x)
{
node_pointer p_y = p_x->m_p_right;
 
p_x->m_p_right = p_y->m_p_left;
 
if (p_y->m_p_left != NULL)
p_y->m_p_left->m_p_parent = p_x;
 
p_y->m_p_parent = p_x->m_p_parent;
 
if (p_x == m_p_head->m_p_parent)
m_p_head->m_p_parent = p_y;
else if (p_x == p_x->m_p_parent->m_p_left)
p_x->m_p_parent->m_p_left = p_y;
else
p_x->m_p_parent->m_p_right = p_y;
 
p_y->m_p_left = p_x;
p_x->m_p_parent = p_y;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);)
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);)
 
apply_update(p_x, (node_update* )this);
apply_update(p_x->m_p_parent, (node_update* )this);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
rotate_right(node_pointer p_x)
{
node_pointer p_y = p_x->m_p_left;
 
p_x->m_p_left = p_y->m_p_right;
 
if (p_y->m_p_right != NULL)
p_y->m_p_right->m_p_parent = p_x;
 
p_y->m_p_parent = p_x->m_p_parent;
 
if (p_x == m_p_head->m_p_parent)
m_p_head->m_p_parent = p_y;
else if (p_x == p_x->m_p_parent->m_p_right)
p_x->m_p_parent->m_p_right = p_y;
else
p_x->m_p_parent->m_p_left = p_y;
 
p_y->m_p_right = p_x;
p_x->m_p_parent = p_y;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);)
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);)
 
apply_update(p_x, (node_update* )this);
apply_update(p_x->m_p_parent, (node_update* )this);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
rotate_parent(node_pointer p_nd)
{
node_pointer p_parent = p_nd->m_p_parent;
 
if (p_nd == p_parent->m_p_left)
rotate_right(p_parent);
else
rotate_left(p_parent);
 
_GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd);
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent ||
p_nd->m_p_right == p_parent);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/)
{ }
 
PB_DS_CLASS_T_DEC
template<typename Node_Update_>
inline void
PB_DS_CLASS_C_DEC::
apply_update(node_pointer p_nd, Node_Update_* /*p_update*/)
{
node_update::operator()(
node_iterator(p_nd),
const_node_iterator(static_cast<node_pointer>(NULL)));
}
 
PB_DS_CLASS_T_DEC
template<typename Node_Update_>
inline void
PB_DS_CLASS_C_DEC::
update_to_top(node_pointer p_nd, Node_Update_* p_update)
{
while (p_nd != m_p_head)
{
apply_update(p_nd, p_update);
 
p_nd = p_nd->m_p_parent;
}
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/)
{ }
 
/erase_fn_imps.hpp
0,0 → 1,120
// -*- 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 erase_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
actual_erase_node(node_pointer p_z)
{
_GLIBCXX_DEBUG_ASSERT(m_size > 0);
--m_size;
 
_GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value)));
 
p_z->~node();
 
s_node_allocator.deallocate(p_z, 1);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
update_min_max_for_erased_node(node_pointer p_z)
{
if (m_size == 1)
{
m_p_head->m_p_left = m_p_head->m_p_right = m_p_head;
 
return;
}
 
if (m_p_head->m_p_left == p_z)
{
iterator it(p_z);
 
++it;
 
m_p_head->m_p_left = it.m_p_nd;
}
else if (m_p_head->m_p_right == p_z)
{
iterator it(p_z);
 
--it;
 
m_p_head->m_p_right = it.m_p_nd;
}
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
 
clear_imp(m_p_head->m_p_parent);
 
m_size = 0;
 
initialize();
 
_GLIBCXX_DEBUG_ONLY(debug_base::clear();)
 
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear_imp(node_pointer p_nd)
{
if (p_nd == NULL)
return;
 
clear_imp(p_nd->m_p_left);
 
clear_imp(p_nd->m_p_right);
 
p_nd->~node();
 
s_node_allocator.deallocate(p_nd, 1);
}
 
/bin_search_tree_.hpp
0,0 → 1,497
// -*- 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 bin_search_tree_.hpp
* Contains an implementation class for bin_search_tree_.
*/
/*
* This implementation uses an idea from the SGI STL (using a @a header node
* which is needed for efficient iteration).
*/
 
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
#include <ext/pb_ds/detail/types_traits.hpp>
#include <ext/pb_ds/detail/debug_map_base.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/tree_trace_base.hpp>
#include <utility>
#include <functional>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
namespace detail
{
 
#define PB_DS_CLASS_T_DEC \
template<typename Key, typename Mapped, class Cmp_Fn, \
class Node_And_It_Traits, class Allocator>
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME \
bin_search_tree_data_
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_CLASS_NAME \
bin_search_tree_no_data_
#endif
 
#define PB_DS_CLASS_C_DEC \
PB_DS_CLASS_NAME< \
Key, \
Mapped, \
Cmp_Fn, \
Node_And_It_Traits, \
Allocator>
 
#define PB_DS_TYPES_TRAITS_C_DEC \
types_traits< \
Key, \
Mapped, \
Allocator, \
false>
 
#ifdef _GLIBCXX_DEBUG
#define PB_DS_DEBUG_MAP_BASE_C_DEC \
debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
typename Allocator::template rebind<Key>::other::const_reference>
#endif
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_V2F(X) (X).first
#define PB_DS_V2S(X) (X).second
#define PB_DS_EP2VP(X)& ((X)->m_value)
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_V2F(X) (X)
#define PB_DS_V2S(X) Mapped_Data()
#define PB_DS_EP2VP(X)& ((X)->m_value.first)
#endif
 
#ifdef PB_DS_TREE_TRACE
#define PB_DS_TREE_TRACE_BASE_C_DEC \
tree_trace_base< \
typename Node_And_It_Traits::const_node_iterator, \
typename Node_And_It_Traits::node_iterator, \
Cmp_Fn, \
true, \
Allocator>
#endif
 
/**
* class description = "8i|\|4ree $34rc|-| 7r33 74813.">
**/
template<typename Key,
typename Mapped,
class Cmp_Fn,
class Node_And_It_Traits,
class Allocator>
class PB_DS_CLASS_NAME :
#ifdef _GLIBCXX_DEBUG
public PB_DS_DEBUG_MAP_BASE_C_DEC,
#endif
#ifdef PB_DS_TREE_TRACE
public PB_DS_TREE_TRACE_BASE_C_DEC,
#endif
public Cmp_Fn,
public PB_DS_TYPES_TRAITS_C_DEC,
public Node_And_It_Traits::node_update
{
 
protected:
typedef
typename Allocator::template rebind<
typename Node_And_It_Traits::node>::other
node_allocator;
 
typedef typename node_allocator::value_type node;
 
typedef typename node_allocator::pointer node_pointer;
 
typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 
typedef
typename Node_And_It_Traits::null_node_update_pointer
null_node_update_pointer;
 
private:
typedef cond_dealtor< node, Allocator> cond_dealtor_t;
 
#ifdef _GLIBCXX_DEBUG
typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
#endif
 
public:
 
typedef typename Allocator::size_type size_type;
 
typedef typename Allocator::difference_type difference_type;
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
const_key_pointer;
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
const_key_reference;
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
mapped_pointer;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
const_mapped_pointer;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
mapped_reference;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
const_mapped_reference;
#endif
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
 
typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
 
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
const_reference;
 
typedef
typename Node_And_It_Traits::const_point_iterator
const_point_iterator;
 
typedef const_point_iterator const_iterator;
 
typedef typename Node_And_It_Traits::point_iterator point_iterator;
 
typedef point_iterator iterator;
 
typedef
typename Node_And_It_Traits::const_reverse_iterator
const_reverse_iterator;
 
typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
 
typedef
typename Node_And_It_Traits::const_node_iterator
const_node_iterator;
 
typedef typename Node_And_It_Traits::node_iterator node_iterator;
 
typedef Cmp_Fn cmp_fn;
 
typedef Allocator allocator_type;
 
typedef typename Node_And_It_Traits::node_update node_update;
 
public:
 
PB_DS_CLASS_NAME();
 
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
 
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);
 
PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
 
void
swap(PB_DS_CLASS_C_DEC& other);
 
~PB_DS_CLASS_NAME();
 
inline bool
empty() const;
 
inline size_type
size() const;
 
inline size_type
max_size() const;
 
Cmp_Fn&
get_cmp_fn();
 
const Cmp_Fn&
get_cmp_fn() const;
 
inline point_iterator
lower_bound(const_key_reference r_key);
 
inline const_point_iterator
lower_bound(const_key_reference r_key) const;
 
inline point_iterator
upper_bound(const_key_reference r_key);
 
inline const_point_iterator
upper_bound(const_key_reference r_key) const;
 
inline point_iterator
find(const_key_reference r_key);
 
inline const_point_iterator
find(const_key_reference r_key) const;
 
inline iterator
begin();
 
inline const_iterator
begin() const;
 
inline iterator
end();
 
inline const_iterator
end() const;
 
inline reverse_iterator
rbegin();
 
inline const_reverse_iterator
rbegin() const;
 
inline reverse_iterator
rend();
 
inline const_reverse_iterator
rend() const;
 
inline const_node_iterator
node_begin() const;
 
inline node_iterator
node_begin();
 
inline const_node_iterator
node_end() const;
 
inline node_iterator
node_end();
 
void
clear();
 
protected:
 
void
value_swap(PB_DS_CLASS_C_DEC& other);
 
void
initialize_min_max();
 
inline iterator
insert_imp_empty(const_reference r_value);
 
inline iterator
insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
 
inline node_pointer
get_new_node_for_leaf_insert(const_reference r_val, false_type);
 
inline node_pointer
get_new_node_for_leaf_insert(const_reference r_val, true_type);
 
inline void
actual_erase_node(node_pointer p_nd);
 
inline std::pair<node_pointer, bool>
erase(node_pointer p_nd);
 
inline void
update_min_max_for_erased_node(node_pointer p_nd);
 
static void
clear_imp(node_pointer p_nd);
 
inline std::pair<
point_iterator,
bool>
insert_leaf(const_reference r_value);
 
inline void
rotate_left(node_pointer p_x);
 
inline void
rotate_right(node_pointer p_y);
 
inline void
rotate_parent(node_pointer p_nd);
 
inline void
apply_update(node_pointer p_nd, null_node_update_pointer);
 
template<typename Node_Update_>
inline void
apply_update(node_pointer p_nd, Node_Update_* p_update);
 
inline void
update_to_top(node_pointer p_nd, null_node_update_pointer);
 
template<typename Node_Update_>
inline void
update_to_top(node_pointer p_nd, Node_Update_* p_update);
 
bool
join_prep(PB_DS_CLASS_C_DEC& other);
 
void
join_finish(PB_DS_CLASS_C_DEC& other);
 
bool
split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
 
void
split_finish(PB_DS_CLASS_C_DEC& other);
 
size_type
recursive_count(node_pointer p_nd) const;
 
#ifdef _GLIBCXX_DEBUG
void
assert_valid() const;
 
void
structure_only_assert_valid() const;
 
void
assert_node_consistent(const node_pointer p_nd) const;
#endif
 
private:
#ifdef _GLIBCXX_DEBUG
void
assert_iterators() const;
 
void
assert_consistent_with_debug_base() const;
 
void
assert_node_consistent_with_left(const node_pointer p_nd) const;
 
void
assert_node_consistent_with_right(const node_pointer p_nd) const;
 
void
assert_consistent_with_debug_base(const node_pointer p_nd) const;
 
void
assert_min() const;
 
void
assert_min_imp(const node_pointer p_nd) const;
 
void
assert_max() const;
 
void
assert_max_imp(const node_pointer p_nd) const;
 
void
assert_size() const;
 
typedef std::pair< const_pointer, const_pointer> node_consistent_t;
 
node_consistent_t
assert_node_consistent_(const node_pointer p_nd) const;
#endif
 
void
initialize();
 
node_pointer
recursive_copy_node(const node_pointer p_nd);
 
protected:
node_pointer m_p_head;
 
size_type m_size;
 
static node_allocator s_node_allocator;
};
 
#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 
#undef PB_DS_CLASS_C_DEC
 
#undef PB_DS_CLASS_T_DEC
 
#undef PB_DS_CLASS_NAME
 
#undef PB_DS_TYPES_TRAITS_C_DEC
 
#undef PB_DS_DEBUG_MAP_BASE_C_DEC
 
#ifdef PB_DS_TREE_TRACE
#undef PB_DS_TREE_TRACE_BASE_C_DEC
#endif
 
#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S
 
} // namespace detail
} // namespace __gnu_pbds
/cond_key_dtor_entry_dealtor.hpp
0,0 → 1,81
// -*- 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 cond_key_dtor_entry_dealtor.hpp
* Contains a binary tree container conditional deallocator
*/
 
class bin_seach_tree_cond_key_dtor_entry_dealtor_
{
public:
inline
bin_seach_tree_cond_key_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd),
m_no_action_dtor(false),
m_key_destruct(false)
{ }
 
inline void
set_no_action_dtor()
{
m_no_action_dtor = true;
}
 
inline void
set_key_destruct()
{
m_key_destruct = true;
}
 
inline
~bin_seach_tree_cond_key_dtor_entry_dealtor_()
{
if (m_no_action_dtor)
return;
 
if (m_key_destruct)
m_p_nd->m_value.first.~Key();
 
bin_tree_base::s_alloc.deallocate(m_p_nd, 1);
}
 
protected:
node_pointer m_p_nd;
 
bool m_no_action_dtor;
 
bool m_key_destruct;
};
 
/insert_fn_imps.hpp
0,0 → 1,211
// -*- 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 insert_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool>
PB_DS_CLASS_C_DEC::
insert_leaf(const_reference r_value)
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
 
if (m_size == 0)
return (std::make_pair(
insert_imp_empty(r_value),
true));
 
node_pointer p_nd = m_p_head->m_p_parent;
node_pointer p_pot = m_p_head;
 
while (p_nd != NULL)
if (!Cmp_Fn::operator()(
PB_DS_V2F(p_nd->m_value),
PB_DS_V2F(r_value)))
{
p_pot = p_nd;
 
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
 
if (p_pot == m_p_head)
return (std::make_pair(
insert_leaf_new(r_value, m_p_head->m_p_right, false),
true));
 
if (!Cmp_Fn::operator()(
PB_DS_V2F(r_value),
PB_DS_V2F(p_pot->m_value)))
{
_GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
 
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(
PB_DS_V2F(r_value)));
 
return (std::make_pair(p_pot, false));
}
 
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(
PB_DS_V2F(r_value)));
 
p_nd = p_pot->m_p_left;
if (p_nd == NULL)
return (std::make_pair(
insert_leaf_new(r_value, p_pot, true),
true));
 
while (p_nd->m_p_right != NULL)
p_nd = p_nd->m_p_right;
 
return (std::make_pair(
insert_leaf_new(r_value, p_nd, false),
true));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd)
{
node_pointer p_new_nd =
get_new_node_for_leaf_insert( r_value, traits_base::m_no_throw_copies_indicator);
 
if (left_nd)
{
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == NULL);
_GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(
PB_DS_V2F(r_value),
PB_DS_V2F(p_nd->m_value)));
 
p_nd->m_p_left = p_new_nd;
 
if (m_p_head->m_p_left == p_nd)
m_p_head->m_p_left = p_new_nd;
}
else
{
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right == NULL);
_GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(
PB_DS_V2F(p_nd->m_value),
PB_DS_V2F(r_value)));
 
p_nd->m_p_right = p_new_nd;
 
if (m_p_head->m_p_right == p_nd)
m_p_head->m_p_right = p_new_nd;
}
 
p_new_nd->m_p_parent = p_nd;
 
p_new_nd->m_p_left = p_new_nd->m_p_right = NULL;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_nd));
 
update_to_top(p_new_nd, (node_update* )this);
 
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(
PB_DS_V2F(r_value)));
 
return (iterator(p_new_nd));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
insert_imp_empty(const_reference r_value)
{
node_pointer p_new_node =
get_new_node_for_leaf_insert( r_value, traits_base::m_no_throw_copies_indicator);
 
m_p_head->m_p_left = m_p_head->m_p_right =
m_p_head->m_p_parent = p_new_node;
 
p_new_node->m_p_parent = m_p_head;
 
p_new_node->m_p_left = p_new_node->m_p_right = NULL;
 
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(
PB_DS_V2F(r_value)));
 
update_to_top(m_p_head->m_p_parent, (node_update* )this);
 
return (iterator(p_new_node));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
get_new_node_for_leaf_insert(const_reference r_val, false_type)
{
node_pointer p_new_nd = s_node_allocator.allocate(1);
 
cond_dealtor_t cond(p_new_nd);
 
new (const_cast<void* >(
static_cast<const void* >(&p_new_nd->m_value)))
typename node::value_type(r_val);
 
cond.set_no_action();
 
p_new_nd->m_p_left = p_new_nd->m_p_right = NULL;
 
++m_size;
 
return (p_new_nd);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
get_new_node_for_leaf_insert(const_reference r_val, true_type)
{
node_pointer p_new_nd = s_node_allocator.allocate(1);
 
new (const_cast<void* >(
static_cast<const void* >(&p_new_nd->m_value)))
typename node::value_type(r_val);
 
p_new_nd->m_p_left = p_new_nd->m_p_right = NULL;
 
++m_size;
 
return (p_new_nd);
}
 
/node_iterators.hpp
0,0 → 1,237
// -*- 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 node_iterators.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
#ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
#define PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
 
#include <ext/pb_ds/tag_and_trait.hpp>
 
namespace __gnu_pbds
{
namespace detail
{
 
#define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \
bin_search_tree_const_node_it_< \
Node, \
Const_Iterator, \
Iterator, \
Allocator>
 
// Const node iterator.
template<typename Node,
class Const_Iterator,
class Iterator,
class Allocator>
class bin_search_tree_const_node_it_
{
private:
 
private:
typedef
typename Allocator::template rebind<
Node>::other::pointer
node_pointer;
 
public:
 
// Category.
typedef trivial_iterator_tag iterator_category;
 
// Difference type.
typedef trivial_iterator_difference_type difference_type;
 
// __Iterator's value type.
typedef Const_Iterator value_type;
 
// __Iterator's reference type.
typedef Const_Iterator reference;
 
// __Iterator's __const reference type.
typedef Const_Iterator const_reference;
 
// Metadata type.
typedef typename Node::metadata_type metadata_type;
 
// Const metadata reference type.
typedef
typename Allocator::template rebind<
metadata_type>::other::const_reference
const_metadata_reference;
 
public:
 
// Default constructor.
/*
inline
bin_search_tree_const_node_it_()
*/
 
inline
bin_search_tree_const_node_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd))
{ }
 
// Access.
inline const_reference
operator*() const
{
return (Const_Iterator(m_p_nd));
}
 
// Metadata access.
inline const_metadata_reference
get_metadata() const
{
return (m_p_nd->get_metadata());
}
 
// Returns the __const node iterator associated with the left node.
inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
get_l_child() const
{
return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left));
}
 
// Returns the __const node iterator associated with the right node.
inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
get_r_child() const
{
return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right));
}
 
// Compares to a different iterator object.
inline bool
operator==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const
{
return (m_p_nd == other.m_p_nd);
}
 
// Compares (negatively) to a different iterator object.
inline bool
operator!=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const
{
return (m_p_nd != other.m_p_nd);
}
 
public:
node_pointer m_p_nd;
};
 
#define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \
bin_search_tree_node_it_< \
Node, \
Const_Iterator, \
Iterator, \
Allocator>
 
// Node iterator.
template<typename Node,
class Const_Iterator,
class Iterator,
class Allocator>
class bin_search_tree_node_it_ :
public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
 
{
 
private:
typedef
typename Allocator::template rebind<
Node>::other::pointer
node_pointer;
 
public:
 
// __Iterator's value type.
typedef Iterator value_type;
 
// __Iterator's reference type.
typedef Iterator reference;
 
// __Iterator's __const reference type.
typedef Iterator const_reference;
 
public:
 
// Default constructor.
/*
inline
bin_search_tree_node_it_();
*/
 
inline
bin_search_tree_node_it_(const node_pointer p_nd = NULL) : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(
const_cast<node_pointer>(p_nd))
{ }
 
// Access.
inline Iterator
operator*() const
{
return (Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd));
}
 
// Returns the node iterator associated with the left node.
inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
get_l_child() const
{
return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC(
PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left));
}
 
// Returns the node iterator associated with the right node.
inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
get_r_child() const
{
return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC(
PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right));
}
 
};
 
#undef PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
 
#undef PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
 
/point_iterators.hpp
0,0 → 1,381
// -*- 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_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
 
#include <ext/pb_ds/tag_and_trait.hpp>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
namespace detail
{
 
#define PB_DS_TREE_CONST_IT_C_DEC \
bin_search_tree_const_it_< \
Node_Pointer, \
Value_Type, \
Pointer, \
Const_Pointer, \
Reference, \
Const_Reference, \
Is_Forward_Iterator, \
Allocator>
 
#define PB_DS_TREE_CONST_ODIR_IT_C_DEC \
bin_search_tree_const_it_< \
Node_Pointer, \
Value_Type, \
Pointer, \
Const_Pointer, \
Reference, \
Const_Reference, \
!Is_Forward_Iterator, \
Allocator>
 
#define PB_DS_TREE_IT_C_DEC \
bin_search_tree_it_< \
Node_Pointer, \
Value_Type, \
Pointer, \
Const_Pointer, \
Reference, \
Const_Reference, \
Is_Forward_Iterator, \
Allocator>
 
#define PB_DS_TREE_ODIR_IT_C_DEC \
bin_search_tree_it_< \
Node_Pointer, \
Value_Type, \
Pointer, \
Const_Pointer, \
Reference, \
Const_Reference, \
!Is_Forward_Iterator, \
Allocator>
 
// Const iterator.
template<typename Node_Pointer,
typename Value_Type,
typename Pointer,
typename Const_Pointer,
typename Reference,
typename Const_Reference,
bool Is_Forward_Iterator,
class Allocator>
class bin_search_tree_const_it_
{
 
public:
 
typedef std::bidirectional_iterator_tag iterator_category;
 
typedef typename Allocator::difference_type difference_type;
 
typedef Value_Type value_type;
 
typedef Pointer pointer;
 
typedef Const_Pointer const_pointer;
 
typedef Reference reference;
 
typedef Const_Reference const_reference;
 
public:
 
inline
bin_search_tree_const_it_(const Node_Pointer p_nd = NULL)
: m_p_nd(const_cast<Node_Pointer>(p_nd))
{ }
 
inline
bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
: m_p_nd(other.m_p_nd)
{ }
 
inline
PB_DS_TREE_CONST_IT_C_DEC&
operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
{
m_p_nd = other.m_p_nd;
return *this;
}
 
inline
PB_DS_TREE_CONST_IT_C_DEC&
operator=(const PB_DS_TREE_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 != NULL);
return &m_p_nd->m_value;
}
 
inline const_reference
operator*() const
{
_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
return m_p_nd->m_value;
}
 
inline bool
operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
{ return m_p_nd == other.m_p_nd; }
 
inline bool
operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
{ return m_p_nd == other.m_p_nd; }
 
inline bool
operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
{ return m_p_nd != other.m_p_nd; }
 
inline bool
operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
{ return m_p_nd != other.m_p_nd; }
 
inline PB_DS_TREE_CONST_IT_C_DEC&
operator++()
{
_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
inc(integral_constant<int,Is_Forward_Iterator>());
return *this;
}
 
inline PB_DS_TREE_CONST_IT_C_DEC
operator++(int)
{
PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
operator++();
return ret_it;
}
 
inline PB_DS_TREE_CONST_IT_C_DEC&
operator--()
{
dec(integral_constant<int,Is_Forward_Iterator>());
return *this;
}
 
inline PB_DS_TREE_CONST_IT_C_DEC
operator--(int)
{
PB_DS_TREE_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->special()&&
m_p_nd->m_p_parent->m_p_parent == m_p_nd)
{
m_p_nd = m_p_nd->m_p_left;
return;
}
 
if (m_p_nd->m_p_right != NULL)
{
m_p_nd = m_p_nd->m_p_right;
while (m_p_nd->m_p_left != NULL)
m_p_nd = m_p_nd->m_p_left;
return;
}
 
Node_Pointer p_y = m_p_nd->m_p_parent;
while (m_p_nd == p_y->m_p_right)
{
m_p_nd = p_y;
p_y = p_y->m_p_parent;
}
 
if (m_p_nd->m_p_right != p_y)
m_p_nd = p_y;
}
 
inline void
dec(false_type)
{ inc(true_type()); }
 
void
dec(true_type)
{
if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
{
m_p_nd = m_p_nd->m_p_right;
return;
}
 
if (m_p_nd->m_p_left != NULL)
{
Node_Pointer p_y = m_p_nd->m_p_left;
while (p_y->m_p_right != NULL)
p_y = p_y->m_p_right;
m_p_nd = p_y;
return;
}
 
Node_Pointer p_y = m_p_nd->m_p_parent;
while (m_p_nd == p_y->m_p_left)
{
m_p_nd = p_y;
p_y = p_y->m_p_parent;
}
if (m_p_nd->m_p_left != p_y)
m_p_nd = p_y;
}
 
public:
Node_Pointer m_p_nd;
};
 
// Iterator.
template<typename Node_Pointer,
typename Value_Type,
typename Pointer,
typename Const_Pointer,
typename Reference,
typename Const_Reference,
bool Is_Forward_Iterator,
class Allocator>
class bin_search_tree_it_ :
public PB_DS_TREE_CONST_IT_C_DEC
 
{
 
public:
 
inline
bin_search_tree_it_(const Node_Pointer p_nd = NULL)
: PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
{ }
 
inline
bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other)
: PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd)
{ }
 
inline
PB_DS_TREE_IT_C_DEC&
operator=(const PB_DS_TREE_IT_C_DEC& other)
{
base_it_type::m_p_nd = other.m_p_nd;
return *this;
}
 
inline
PB_DS_TREE_IT_C_DEC&
operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
{
base_it_type::m_p_nd = other.m_p_nd;
return *this;
}
 
inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
operator->() const
{
_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL);
return &base_it_type::m_p_nd->m_value;
}
 
inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
operator*() const
{
_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL);
return base_it_type::m_p_nd->m_value;
}
 
inline PB_DS_TREE_IT_C_DEC&
operator++()
{
PB_DS_TREE_CONST_IT_C_DEC:: operator++();
return *this;
}
 
inline PB_DS_TREE_IT_C_DEC
operator++(int)
{
PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
operator++();
return ret_it;
}
 
inline PB_DS_TREE_IT_C_DEC&
operator--()
{
PB_DS_TREE_CONST_IT_C_DEC:: operator--();
return *this;
}
 
inline PB_DS_TREE_IT_C_DEC
operator--(int)
{
PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
operator--();
return ret_it;
}
 
protected:
typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
};
 
#undef PB_DS_TREE_CONST_IT_C_DEC
#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
#undef PB_DS_TREE_IT_C_DEC
#undef PB_DS_TREE_ODIR_IT_C_DEC
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif
/split_join_fn_imps.hpp
0,0 → 1,146
// -*- 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 split_join_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
bool
PB_DS_CLASS_C_DEC::
join_prep(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
if (other.m_size == 0)
return false;
 
if (m_size == 0)
{
value_swap(other);
return false;
}
 
const bool greater = Cmp_Fn::operator()(PB_DS_V2F(m_p_head->m_p_right->m_value), PB_DS_V2F(other.m_p_head->m_p_left->m_value));
 
const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(other.m_p_head->m_p_right->m_value), PB_DS_V2F(m_p_head->m_p_left->m_value));
 
if (!greater && !lesser)
__throw_join_error();
 
if (lesser)
value_swap(other);
 
m_size += other.m_size;
_GLIBCXX_DEBUG_ONLY(debug_base::join(other);)
return true;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
join_finish(PB_DS_CLASS_C_DEC& other)
{
initialize_min_max();
other.initialize();
}
 
PB_DS_CLASS_T_DEC
bool
PB_DS_CLASS_C_DEC::
split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
other.clear();
 
if (m_size == 0)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return false;
}
 
if (Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_left->m_value)))
{
value_swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return false;
}
 
if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_right->m_value)))
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return false;
}
 
if (m_size == 1)
{
value_swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return false;
}
 
_GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(Cmp_Fn& )(*this), other);)
return true;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split_finish(PB_DS_CLASS_C_DEC& other)
{
other.initialize_min_max();
other.m_size = std::distance(other.begin(), other.end());
m_size -= other.m_size;
initialize_min_max();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
recursive_count(node_pointer p) const
{
if (p == NULL)
return 0;
return 1 + recursive_count(p->m_p_left) + recursive_count(p->m_p_right);
}
 
/iterators_fn_imps.hpp
0,0 → 1,136
// -*- 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 iterators_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
begin()
{
return (iterator(m_p_head->m_p_left));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
begin() const
{
return (const_iterator(m_p_head->m_p_left));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
end()
{
return (iterator(m_p_head));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
end() const
{
return (const_iterator(m_p_head));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator
PB_DS_CLASS_C_DEC::
rbegin() const
{
return (const_reverse_iterator(m_p_head->m_p_right));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::reverse_iterator
PB_DS_CLASS_C_DEC::
rbegin()
{
return (reverse_iterator(m_p_head->m_p_right));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::reverse_iterator
PB_DS_CLASS_C_DEC::
rend()
{
return (reverse_iterator(m_p_head));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator
PB_DS_CLASS_C_DEC::
rend() const
{
return (const_reverse_iterator(m_p_head));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
node_begin() const
{
return (const_node_iterator(m_p_head->m_p_parent));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
node_begin()
{
return (node_iterator(m_p_head->m_p_parent));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
node_end() const
{
return (const_node_iterator(NULL));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
node_end()
{
return (node_iterator(NULL));
}
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.