diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_')
11 files changed, 0 insertions, 1495 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp deleted file mode 100644 index 222589532..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/constructors_destructor_fn_imps.hpp +++ /dev/null @@ -1,102 +0,0 @@ -// -*- 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; } diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp deleted file mode 100644 index 084e25d26..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/debug_fn_imps.hpp +++ /dev/null @@ -1,74 +0,0 @@ -// -*- 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 - diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp deleted file mode 100644 index 508f586d7..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/erase_fn_imps.hpp +++ /dev/null @@ -1,157 +0,0 @@ -// -*- 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; -} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp deleted file mode 100644 index 182425a8f..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/find_fn_imps.hpp +++ /dev/null @@ -1,99 +0,0 @@ -// -*- 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; -} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp deleted file mode 100644 index 636b9ab25..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/info_fn_imps.hpp +++ /dev/null @@ -1,39 +0,0 @@ -// -*- 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. - */ diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp deleted file mode 100644 index e9ae987b0..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/insert_fn_imps.hpp +++ /dev/null @@ -1,93 +0,0 @@ -// -*- 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); -} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp deleted file mode 100644 index fbf398d04..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp +++ /dev/null @@ -1,125 +0,0 @@ -// -*- 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 diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp deleted file mode 100644 index e4f3556a5..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp +++ /dev/null @@ -1,283 +0,0 @@ -// -*- 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);) -} - diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp deleted file mode 100644 index 959893ec7..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp +++ /dev/null @@ -1,298 +0,0 @@ -// -*- 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 "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 - diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp deleted file mode 100644 index 7f0b2cb20..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/split_join_fn_imps.hpp +++ /dev/null @@ -1,112 +0,0 @@ -// -*- 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()); -} - diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp deleted file mode 100644 index cfedc35c8..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp +++ /dev/null @@ -1,113 +0,0 @@ -// -*- 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 |