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/splay_tree_
    from Rev 424 to Rev 519
    ↔ Reverse comparison
  •

Rev 424 → Rev 519

/erase_fn_imps.hpp
0,0 → 1,157
// -*- 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 splay_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
erase(const_key_reference r_key)
{
point_iterator it = find(r_key);
if (it == base_type::end())
return false;
erase(it);
return true;
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
erase(iterator it)
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
if (it == base_type::end())
return it;
iterator ret_it = it;
++ret_it;
erase_node(it.m_p_nd);
_GLIBCXX_DEBUG_ONLY(assert_valid());
return ret_it;
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::reverse_iterator
PB_DS_CLASS_C_DEC::
erase(reverse_iterator it)
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
if (it.m_p_nd == base_type::m_p_head)
return (it);
reverse_iterator ret_it = it;
++ret_it;
erase_node(it.m_p_nd);
_GLIBCXX_DEBUG_ONLY(assert_valid());
return ret_it;
}
 
PB_DS_CLASS_T_DEC
template<typename Pred>
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
erase_if(Pred pred)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
size_type num_ersd = 0;
iterator it = base_type::begin();
while (it != base_type::end())
{
if (pred(*it))
{
++num_ersd;
it = erase(it);
}
else
++it;
}
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return num_ersd;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase_node(node_pointer p_nd)
{
_GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
splay(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent);
 
node_pointer p_l = p_nd->m_p_left;
node_pointer p_r = p_nd->m_p_right;
 
base_type::update_min_max_for_erased_node(p_nd);
base_type::actual_erase_node(p_nd);
if (p_r == NULL)
{
base_type::m_p_head->m_p_parent = p_l;
if (p_l != NULL)
p_l->m_p_parent = base_type::m_p_head;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return;
}
 
node_pointer p_target_r = leftmost(p_r);
_GLIBCXX_DEBUG_ASSERT(p_target_r != NULL);
p_r->m_p_parent = base_type::m_p_head;
base_type::m_p_head->m_p_parent = p_r;
splay(p_target_r);
 
_GLIBCXX_DEBUG_ONLY(p_target_r->m_p_left = NULL);
_GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_parent == this->m_p_head);
_GLIBCXX_DEBUG_ASSERT(this->m_p_head->m_p_parent == p_target_r);
 
p_target_r->m_p_left = p_l;
if (p_l != NULL)
p_l->m_p_parent = p_target_r;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
apply_update(p_target_r, (node_update* )this);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
leftmost(node_pointer p_nd)
{
_GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
while (p_nd->m_p_left != NULL)
p_nd = p_nd->m_p_left;
return p_nd;
}
/find_fn_imps.hpp
0,0 → 1,99
// -*- 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 splay_tree_.
*/
 
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)
{
node_pointer p_found = find_imp(r_key);
if (p_found != base_type::m_p_head)
splay(p_found);
return point_iterator(p_found);
}
 
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
{
const node_pointer p_found = find_imp(r_key);
if (p_found != base_type::m_p_head)
const_cast<PB_DS_CLASS_C_DEC* >(this)->splay(p_found);
return point_iterator(p_found);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
find_imp(const_key_reference r_key)
{
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
node_pointer p_nd = base_type::m_p_head->m_p_parent;
while (p_nd != NULL)
if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
{
if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
return p_nd;
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
return base_type::m_p_head;
}
 
PB_DS_CLASS_T_DEC
inline const typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
find_imp(const_key_reference r_key) const
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
node_pointer p_nd = base_type::m_p_head->m_p_parent;
while (p_nd != NULL)
if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
{
if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
return p_nd;
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
return base_type::m_p_head;
}
/insert_fn_imps.hpp
0,0 → 1,93
// -*- 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 splay_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool>
PB_DS_CLASS_C_DEC::
insert(const_reference r_value)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
std::pair<point_iterator, bool> ins_pair = insert_leaf_imp(r_value);
ins_pair.first.m_p_nd->m_special = false;
_GLIBCXX_DEBUG_ONLY(assert_valid());
splay(ins_pair.first.m_p_nd);
_GLIBCXX_DEBUG_ONLY(assert_valid());
return ins_pair;
}
 
PB_DS_CLASS_T_DEC
inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool>
PB_DS_CLASS_C_DEC::
insert_leaf_imp(const_reference r_value)
{
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
if (base_type::m_size == 0)
return std::make_pair(base_type::insert_imp_empty(r_value), true);
 
node_pointer p_nd = base_type::m_p_head->m_p_parent;
node_pointer p_pot = base_type::m_p_head;
 
while (p_nd != NULL)
if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), PB_DS_V2F(r_value)))
{
if (!Cmp_Fn::operator()(PB_DS_V2F(r_value), PB_DS_V2F(p_nd->m_value)))
{
return std::make_pair(point_iterator(p_nd), false);
}
p_pot = p_nd;
p_nd = p_nd->m_p_left;
}
else
p_nd = p_nd->m_p_right;
 
if (p_pot == base_type::m_p_head)
return std::make_pair(base_type::insert_leaf_new(r_value, base_type::m_p_head->m_p_right, false), true);
 
_GLIBCXX_DEBUG_ONLY(base_type::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(base_type::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);
}
/constructors_destructor_fn_imps.hpp
0,0 → 1,102
// -*- 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 constructors_destructor_fn_imps.hpp
* Contains an implementation class for splay_tree_.
*/
 
PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_range(It first_it, It last_it)
{
while (first_it != last_it)
insert(*(first_it++));
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME()
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
base_type(r_cmp_fn)
{
initialize();
_GLIBCXX_DEBUG_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) :
base_type(r_cmp_fn, r_node_update)
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) :
base_type(other)
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
base_type::swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
initialize()
{ base_type::m_p_head->m_special = true; }
/debug_fn_imps.hpp
0,0 → 1,74
// -*- 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 splay_tree_.
*/
 
#ifdef _GLIBCXX_DEBUG
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
base_type::assert_valid();
const node_pointer p_head = base_type::m_p_head;
assert_special_imp(p_head);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_special_imp(const node_pointer p_nd) const
{
if (p_nd == NULL)
return;
 
if (p_nd == base_type::m_p_head)
{
_GLIBCXX_DEBUG_ASSERT(p_nd->m_special);
assert_special_imp(p_nd->m_p_parent);
return;
}
 
_GLIBCXX_DEBUG_ASSERT(!p_nd->m_special);
assert_special_imp(p_nd->m_p_left);
assert_special_imp(p_nd->m_p_right);
}
 
#endif
 
/splay_fn_imps.hpp
0,0 → 1,283
// -*- 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 splay_fn_imps.hpp
* Contains an implementation class for splay_tree_.
*/
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
splay(node_pointer p_nd)
{
while (p_nd->m_p_parent != base_type::m_p_head)
{
#ifdef _GLIBCXX_DEBUG
{
node_pointer p_head = base_type::m_p_head;
assert_special_imp(p_head);
}
#endif
 
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);)
 
if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head)
{
base_type::rotate_parent(p_nd);
_GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent);
}
else
{
const node_pointer p_parent = p_nd->m_p_parent;
const node_pointer p_grandparent = p_parent->m_p_parent;
 
#ifdef _GLIBCXX_DEBUG
const size_type total =
base_type::recursive_count(p_grandparent);
_GLIBCXX_DEBUG_ASSERT(total >= 3);
#endif
 
if (p_parent->m_p_left == p_nd &&
p_grandparent->m_p_right == p_parent)
splay_zig_zag_left(p_nd, p_parent, p_grandparent);
else if (p_parent->m_p_right == p_nd &&
p_grandparent->m_p_left == p_parent)
splay_zig_zag_right(p_nd, p_parent, p_grandparent);
else if (p_parent->m_p_left == p_nd &&
p_grandparent->m_p_left == p_parent)
splay_zig_zig_left(p_nd, p_parent, p_grandparent);
else
splay_zig_zig_right(p_nd, p_parent, p_grandparent);
_GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd));
}
 
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);)
}
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent,
node_pointer p_grandparent)
{
_GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
_GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
 
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
 
_GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
p_grandparent->m_p_right == p_parent);
 
splay_zz_start(p_nd, p_parent, p_grandparent);
 
node_pointer p_b = p_nd->m_p_right;
node_pointer p_c = p_nd->m_p_left;
 
p_nd->m_p_right = p_parent;
p_parent->m_p_parent = p_nd;
 
p_nd->m_p_left = p_grandparent;
p_grandparent->m_p_parent = p_nd;
 
p_parent->m_p_left = p_b;
if (p_b != NULL)
p_b->m_p_parent = p_parent;
 
p_grandparent->m_p_right = p_c;
if (p_c != NULL)
p_c->m_p_parent = p_grandparent;
 
splay_zz_end(p_nd, p_parent, p_grandparent);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent,
node_pointer p_grandparent)
{
_GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
_GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
 
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
 
_GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
p_grandparent->m_p_left == p_parent);
 
splay_zz_start(p_nd, p_parent, p_grandparent);
 
node_pointer p_b = p_nd->m_p_left;
node_pointer p_c = p_nd->m_p_right;
 
p_nd->m_p_left = p_parent;
p_parent->m_p_parent = p_nd;
 
p_nd->m_p_right = p_grandparent;
p_grandparent->m_p_parent = p_nd;
 
p_parent->m_p_right = p_b;
if (p_b != NULL)
p_b->m_p_parent = p_parent;
 
p_grandparent->m_p_left = p_c;
if (p_c != NULL)
p_c->m_p_parent = p_grandparent;
 
splay_zz_end(p_nd, p_parent, p_grandparent);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent,
node_pointer p_grandparent)
{
_GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
_GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
 
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
 
_GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent);
 
splay_zz_start(p_nd, p_parent, p_grandparent);
 
node_pointer p_b = p_nd->m_p_right;
node_pointer p_c = p_parent->m_p_right;
 
p_nd->m_p_right = p_parent;
p_parent->m_p_parent = p_nd;
 
p_parent->m_p_right = p_grandparent;
p_grandparent->m_p_parent = p_parent;
 
p_parent->m_p_left = p_b;
if (p_b != NULL)
p_b->m_p_parent = p_parent;
 
p_grandparent->m_p_left = p_c;
if (p_c != NULL)
p_c->m_p_parent = p_grandparent;
 
splay_zz_end(p_nd, p_parent, p_grandparent);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent,
node_pointer p_grandparent)
{
_GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
_GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
_GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent);
 
splay_zz_start(p_nd, p_parent, p_grandparent);
 
node_pointer p_b = p_nd->m_p_left;
node_pointer p_c = p_parent->m_p_left;
 
p_nd->m_p_left = p_parent;
p_parent->m_p_parent = p_nd;
 
p_parent->m_p_left = p_grandparent;
p_grandparent->m_p_parent = p_parent;
 
p_parent->m_p_right = p_b;
if (p_b != NULL)
p_b->m_p_parent = p_parent;
 
p_grandparent->m_p_right = p_c;
if (p_c != NULL)
p_c->m_p_parent = p_grandparent;
 
base_type::update_to_top(p_grandparent, (node_update* )this);
splay_zz_end(p_nd, p_parent, p_grandparent);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
splay_zz_start(node_pointer p_nd,
#ifdef _GLIBCXX_DEBUG
node_pointer p_parent,
#else
node_pointer /*p_parent*/,
#endif
node_pointer p_grandparent)
{
_GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
_GLIBCXX_DEBUG_ASSERT(p_parent != NULL);
_GLIBCXX_DEBUG_ASSERT(p_grandparent != NULL);
 
const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head;
 
if (grandparent_head)
{
base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent;
p_nd->m_p_parent = base_type::m_p_head;
return;
}
 
node_pointer p_greatgrandparent = p_grandparent->m_p_parent;
 
p_nd->m_p_parent = p_greatgrandparent;
 
if (p_grandparent == p_greatgrandparent->m_p_left)
p_greatgrandparent->m_p_left = p_nd;
else
p_greatgrandparent->m_p_right = p_nd;
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
splay_zz_end(node_pointer p_nd, node_pointer p_parent,
node_pointer p_grandparent)
{
if (p_nd->m_p_parent == base_type::m_p_head)
base_type::m_p_head->m_p_parent = p_nd;
 
apply_update(p_grandparent, (node_update* )this);
apply_update(p_parent, (node_update* )this);
apply_update(p_nd, (node_update* )this);
 
_GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);)
}
 
/node.hpp
0,0 → 1,125
// -*- 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.hpp
* Contains an implementation struct for splay_tree_'s node.
*/
 
#ifndef PB_DS_SPLAY_TREE_NODE_HPP
#define PB_DS_SPLAY_TREE_NODE_HPP
 
namespace __gnu_pbds
{
namespace detail
{
template<typename Value_Type, class Metadata, class Allocator>
struct splay_tree_node_
{
public:
typedef Value_Type value_type;
typedef Metadata metadata_type;
 
typedef
typename Allocator::template rebind<
splay_tree_node_<Value_Type, Metadata, Allocator> >::other::pointer
node_pointer;
 
typedef
typename Allocator::template rebind<metadata_type>::other::reference
metadata_reference;
 
typedef
typename Allocator::template rebind<metadata_type>::other::const_reference
const_metadata_reference;
 
#ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
void
trace() const
{ std::cout << PB_DS_V2F(m_value) << "(" << m_metadata << ")"; }
#endif
 
inline bool
special() const
{ return m_special; }
 
inline const_metadata_reference
get_metadata() const
{ return m_metadata; }
 
inline metadata_reference
get_metadata()
{ return m_metadata; }
 
value_type m_value;
bool m_special;
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
metadata_type m_metadata;
};
 
template<typename Value_Type, typename Allocator>
struct splay_tree_node_<Value_Type, null_node_metadata, Allocator>
{
public:
typedef Value_Type value_type;
typedef null_node_metadata metadata_type;
 
typedef
typename Allocator::template rebind<
splay_tree_node_<Value_Type, null_node_metadata, Allocator> >::other::pointer
node_pointer;
 
inline bool
special() const
{ return m_special; }
 
#ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
void
trace() const
{ std::cout << PB_DS_V2F(m_value); }
#endif
 
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
value_type m_value;
bool m_special;
};
} // namespace detail
} // namespace __gnu_pbds
 
#endif
/split_join_fn_imps.hpp
0,0 → 1,112
// -*- 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 splay_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
if (base_type::join_prep(other) == false)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
 
node_pointer p_target_r = other.leftmost(other.m_p_head);
_GLIBCXX_DEBUG_ASSERT(p_target_r != NULL);
other.splay(p_target_r);
 
_GLIBCXX_DEBUG_ASSERT(p_target_r == other.m_p_head->m_p_parent);
_GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_left == NULL);
 
p_target_r->m_p_left = base_type::m_p_head->m_p_parent;
 
_GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_left != NULL);
p_target_r->m_p_left->m_p_parent = p_target_r;
 
base_type::m_p_head->m_p_parent = p_target_r;
p_target_r->m_p_parent = base_type::m_p_head;
apply_update(p_target_r, (node_update* )this);
 
base_type::join_finish(other);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
 
if (base_type::split_prep(r_key, other) == false)
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
return;
}
 
node_pointer p_upper_bound = upper_bound(r_key).m_p_nd;
_GLIBCXX_DEBUG_ASSERT(p_upper_bound != NULL);
 
splay(p_upper_bound);
_GLIBCXX_DEBUG_ASSERT(p_upper_bound->m_p_parent == this->m_p_head);
 
node_pointer p_new_root = p_upper_bound->m_p_left;
_GLIBCXX_DEBUG_ASSERT(p_new_root != NULL);
 
base_type::m_p_head->m_p_parent = p_new_root;
p_new_root->m_p_parent = base_type::m_p_head;
other.m_p_head->m_p_parent = p_upper_bound;
p_upper_bound->m_p_parent = other.m_p_head;
p_upper_bound->m_p_left = NULL;
apply_update(p_upper_bound, (node_update* )this);
base_type::split_finish(other);
 
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
}
 
/info_fn_imps.hpp
0,0 → 1,39
// -*- 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.
*/
/splay_tree_.hpp
0,0 → 1,298
// -*- 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 splay_tree_.hpp
* Contains an implementation class for splay_tree_.
*/
/*
* This implementation uses an idea from the SGI STL (using a @a header node
* which is needed for efficient iteration). Following is the SGI STL
* copyright.
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
*/
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
#endif
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
#endif
#endif
 
#include <utility>
#include <vector>
#include <assert.h>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
namespace detail
{
#define PB_DS_CLASS_T_DEC \
template<typename Key, typename Mapped, typename Cmp_Fn, \
typename Node_And_It_Traits, typename Allocator>
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME splay_tree_data_
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_CLASS_NAME splay_tree_no_data_
#endif
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_BASE_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_BASE_C_DEC \
PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
 
#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
 
// $p14y 7r33 7481.
template<typename Key, typename Mapped, typename Cmp_Fn,
typename Node_And_It_Traits, typename Allocator>
class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC
{
private:
typedef PB_DS_BASE_C_DEC base_type;
typedef typename base_type::node_pointer node_pointer;
 
public:
typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef Cmp_Fn cmp_fn;
typedef typename base_type::key_type key_type;
typedef typename base_type::key_pointer key_pointer;
typedef typename base_type::const_key_pointer const_key_pointer;
typedef typename base_type::key_reference key_reference;
typedef typename base_type::const_key_reference const_key_reference;
typedef typename base_type::mapped_type mapped_type;
typedef typename base_type::mapped_pointer mapped_pointer;
typedef typename base_type::const_mapped_pointer const_mapped_pointer;
typedef typename base_type::mapped_reference mapped_reference;
typedef typename base_type::const_mapped_reference const_mapped_reference;
typedef typename base_type::value_type value_type;
typedef typename base_type::pointer pointer;
typedef typename base_type::const_pointer const_pointer;
typedef typename base_type::reference reference;
typedef typename base_type::const_reference const_reference;
typedef typename base_type::point_iterator point_iterator;
typedef typename base_type::const_iterator const_point_iterator;
typedef typename base_type::iterator iterator;
typedef typename base_type::const_iterator const_iterator;
typedef typename base_type::reverse_iterator reverse_iterator;
typedef typename base_type::const_reverse_iterator const_reverse_iterator;
typedef typename base_type::node_update node_update;
 
PB_DS_CLASS_NAME();
 
PB_DS_CLASS_NAME(const Cmp_Fn&);
 
PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&);
 
PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 
void
swap(PB_DS_CLASS_C_DEC&);
 
template<typename It>
void
copy_from_range(It, It);
 
void
initialize();
 
inline std::pair<point_iterator, bool>
insert(const_reference r_value);
 
inline mapped_reference
operator[](const_key_reference r_key)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
std::pair<point_iterator, bool> ins_pair =
insert_leaf_imp(value_type(r_key, mapped_type()));
 
ins_pair.first.m_p_nd->m_special = false;
_GLIBCXX_DEBUG_ONLY(base_type::assert_valid());
splay(ins_pair.first.m_p_nd);
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
return ins_pair.first.m_p_nd->m_value.second;
#else
insert(r_key);
return base_type::s_null_mapped;
#endif
}
 
inline point_iterator
find(const_key_reference);
 
inline const_point_iterator
find(const_key_reference) const;
 
inline bool
erase(const_key_reference);
 
inline iterator
erase(iterator it);
 
inline reverse_iterator
erase(reverse_iterator);
 
template<typename Pred>
inline size_type
erase_if(Pred);
 
void
join(PB_DS_CLASS_C_DEC&);
 
void
split(const_key_reference, PB_DS_CLASS_C_DEC&);
 
private:
inline std::pair<point_iterator, bool>
insert_leaf_imp(const_reference);
 
inline node_pointer
find_imp(const_key_reference);
 
inline const node_pointer
find_imp(const_key_reference) const;
 
#ifdef _GLIBCXX_DEBUG
void
assert_valid() const;
 
void
assert_special_imp(const node_pointer) const;
#endif
 
void
splay(node_pointer);
 
inline void
splay_zig_zag_left(node_pointer, node_pointer, node_pointer);
 
inline void
splay_zig_zag_right(node_pointer, node_pointer, node_pointer);
 
inline void
splay_zig_zig_left(node_pointer, node_pointer, node_pointer);
 
inline void
splay_zig_zig_right(node_pointer, node_pointer, node_pointer);
 
inline void
splay_zz_start(node_pointer, node_pointer, node_pointer);
 
inline void
splay_zz_end(node_pointer, node_pointer, node_pointer);
 
inline node_pointer
leftmost(node_pointer);
 
void
erase_node(node_pointer);
};
 
#include <ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp>
#include <ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp>
 
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_NAME
#undef PB_DS_BASE_CLASS_NAME
#undef PB_DS_BASE_C_DEC
#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S
} // namespace detail
} // namespace __gnu_pbds
 
/traits.hpp
0,0 → 1,113
// -*- 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 splay_tree_.
*/
 
#ifndef PB_DS_SPLAY_TREE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_SPLAY_TREE_NODE_AND_IT_TRAITS_HPP
 
#include <ext/pb_ds/detail/splay_tree_/node.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 Allocator>
struct tree_traits<
Key,
Mapped,
Cmp_Fn,
Node_Update,
splay_tree_tag,
Allocator> : public bin_search_tree_traits<
Key,
Mapped,
Cmp_Fn,
Node_Update,
splay_tree_node_<
typename types_traits<
Key,
Mapped,
Allocator,
false>::value_type,
typename tree_node_metadata_selector<
Key,
Mapped,
Cmp_Fn,
Node_Update,
Allocator>::type,
Allocator>,
Allocator>
{ };
 
template<typename Key,
class Cmp_Fn,
template<typename Const_Node_Iterator,
class Node_Iterator,
class Cmp_Fn_,
class Allocator_>
class Node_Update,
class Allocator>
struct tree_traits<Key, null_mapped_type, Cmp_Fn, Node_Update,
splay_tree_tag, Allocator>
: public bin_search_tree_traits<Key, null_mapped_type, Cmp_Fn,
Node_Update,
splay_tree_node_<typename types_traits<Key, null_mapped_type, Allocator, false>::value_type,
typename tree_node_metadata_selector<
Key,
null_mapped_type,
Cmp_Fn,
Node_Update,
Allocator>::type,
Allocator>,
Allocator>
{ };
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif // #ifndef PB_DS_SPLAY_TREE_NODE_AND_IT_TRAITS_HPP

powered by: WebSVN 2.1.0

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