inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 for rb_tree_. */ #ifndef PB_DS_RB_TREE_NODE_HPP #define PB_DS_RB_TREE_NODE_HPP #include namespace __gnu_pbds { namespace detail { template struct rb_tree_node_ { public: typedef Value_Type value_type; typedef Metadata metadata_type; typedef typename Allocator::template rebind< rb_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; inline bool special() const { return m_red; } inline const_metadata_reference get_metadata() const { return m_metadata; } inline metadata_reference get_metadata() { return m_metadata; } #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ void trace() const { std::cout << PB_DS_V2F(m_value) <<(m_red? " " : " ") << "(" << m_metadata << ")"; } #endif node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; value_type m_value; bool m_red; metadata_type m_metadata; }; template struct rb_tree_node_ { public: typedef Value_Type value_type; typedef null_node_metadata metadata_type; typedef typename Allocator::template rebind< rb_tree_node_< Value_Type, null_node_metadata, Allocator> >::other::pointer node_pointer; inline bool special() const { return m_red; } #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_ void trace() const { std::cout << PB_DS_V2F(m_value) <<(m_red? " " : " "); } #endif node_pointer m_p_left; node_pointer m_p_right; node_pointer m_p_parent; value_type m_value; bool m_red; }; } // namespace detail } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 for rb_tree_. */ // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 for rb_tree_. */ PB_DS_CLASS_T_DEC template 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();) base_type::swap(other); _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() { base_type::m_p_head->m_red = true; } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 rb_tree_.hpp * Contains an implementation for rb_tree_. */ /* * This implementation uses an idea from the SGI STL (using a "header" node * which is needed for efficient iteration). */ #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 #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 #endif #endif #include #include #include #include #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CLASS_NAME rb_tree_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_CLASS_NAME rb_tree_no_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 #define PB_DS_BASE_C_DEC \ PB_DS_BASE_CLASS_NAME #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 template 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 Cmp_Fn cmp_fn; typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; 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 void copy_from_range(It, It); inline std::pair insert(const_reference); inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR _GLIBCXX_DEBUG_ONLY(assert_valid();) std::pair ins_pair = base_type::insert_leaf(value_type(r_key, mapped_type())); if (ins_pair.second == true) { ins_pair.first.m_p_nd->m_red = true; _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();) insert_fixup(ins_pair.first.m_p_nd); } _GLIBCXX_DEBUG_ONLY(assert_valid();) return ins_pair.first.m_p_nd->m_value.second; #else insert(r_key); return base_type::s_null_mapped; #endif } inline bool erase(const_key_reference); inline iterator erase(iterator); inline reverse_iterator erase(reverse_iterator); template inline size_type erase_if(Pred); void join(PB_DS_CLASS_C_DEC&); void split(const_key_reference, PB_DS_CLASS_C_DEC&); protected: private: #ifdef _GLIBCXX_DEBUG void assert_valid() const; size_type assert_node_consistent(const node_pointer) const; #endif inline static bool is_effectively_black(const node_pointer); void initialize(); void insert_fixup(node_pointer); void erase_node(node_pointer); void remove_node(node_pointer); void remove_fixup(node_pointer, node_pointer); void split_imp(node_pointer, PB_DS_CLASS_C_DEC&); inline node_pointer split_min(); std::pair split_min_imp(); void join_imp(node_pointer, node_pointer); std::pair find_join_pos_right(node_pointer, size_type, size_type); std::pair find_join_pos_left(node_pointer, size_type, size_type); inline size_type black_height(node_pointer); void split_at_node(node_pointer, PB_DS_CLASS_C_DEC&); }; #include #include #include #include #include #include #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 // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 for rb_tree_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: assert_node_consistent(const node_pointer p_nd) const { if (p_nd == NULL) return 1; const size_type l_height = assert_node_consistent(p_nd->m_p_left); const size_type r_height = assert_node_consistent(p_nd->m_p_right); if (p_nd->m_red) { _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_left)); _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_right)); } _GLIBCXX_DEBUG_ASSERT(l_height == r_height); return (p_nd->m_red ? 0 : 1) + l_height; } 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; _GLIBCXX_DEBUG_ASSERT(p_head->m_red); if (p_head->m_p_parent != NULL) { _GLIBCXX_DEBUG_ASSERT(!p_head->m_p_parent->m_red); assert_node_consistent(p_head->m_p_parent); } } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 for rb_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 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) { remove_node(p_nd); base_type::actual_erase_node(p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid()); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: remove_node(node_pointer p_z) { update_min_max_for_erased_node(p_z); node_pointer p_y = p_z; node_pointer p_x = NULL; node_pointer p_new_x_parent = NULL; if (p_y->m_p_left == NULL) p_x = p_y->m_p_right; else if (p_y->m_p_right == NULL) p_x = p_y->m_p_left; else { p_y = p_y->m_p_right; while (p_y->m_p_left != NULL) p_y = p_y->m_p_left; p_x = p_y->m_p_right; } if (p_y == p_z) { p_new_x_parent = p_y->m_p_parent; if (p_x != NULL) p_x->m_p_parent = p_y->m_p_parent; if (base_type::m_p_head->m_p_parent == p_z) base_type::m_p_head->m_p_parent = p_x; else if (p_z->m_p_parent->m_p_left == p_z) { p_y->m_p_left = p_z->m_p_parent; p_z->m_p_parent->m_p_left = p_x; } else { p_y->m_p_left = NULL; p_z->m_p_parent->m_p_right = p_x; } } else { p_z->m_p_left->m_p_parent = p_y; p_y->m_p_left = p_z->m_p_left; if (p_y != p_z->m_p_right) { p_new_x_parent = p_y->m_p_parent; if (p_x != NULL) p_x->m_p_parent = p_y->m_p_parent; p_y->m_p_parent->m_p_left = p_x; p_y->m_p_right = p_z->m_p_right; p_z->m_p_right->m_p_parent = p_y; } else p_new_x_parent = p_y; if (base_type::m_p_head->m_p_parent == p_z) base_type::m_p_head->m_p_parent = p_y; else if (p_z->m_p_parent->m_p_left == p_z) p_z->m_p_parent->m_p_left = p_y; else p_z->m_p_parent->m_p_right = p_y; p_y->m_p_parent = p_z->m_p_parent; std::swap(p_y->m_red, p_z->m_red); p_y = p_z; } update_to_top(p_new_x_parent, (node_update* )this); if (p_y->m_red) return; remove_fixup(p_x, p_new_x_parent); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) { _GLIBCXX_DEBUG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent); while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x)) if (p_x == p_new_x_parent->m_p_left) { node_pointer p_w = p_new_x_parent->m_p_right; if (p_w->m_red) { p_w->m_red = false; p_new_x_parent->m_red = true; base_type::rotate_left(p_new_x_parent); p_w = p_new_x_parent->m_p_right; } if (is_effectively_black(p_w->m_p_left) && is_effectively_black(p_w->m_p_right)) { p_w->m_red = true; p_x = p_new_x_parent; p_new_x_parent = p_new_x_parent->m_p_parent; } else { if (is_effectively_black(p_w->m_p_right)) { if (p_w->m_p_left != NULL) p_w->m_p_left->m_red = false; p_w->m_red = true; base_type::rotate_right(p_w); p_w = p_new_x_parent->m_p_right; } p_w->m_red = p_new_x_parent->m_red; p_new_x_parent->m_red = false; if (p_w->m_p_right != NULL) p_w->m_p_right->m_red = false; base_type::rotate_left(p_new_x_parent); update_to_top(p_new_x_parent, (node_update* )this); break; } } else { node_pointer p_w = p_new_x_parent->m_p_left; if (p_w->m_red == true) { p_w->m_red = false; p_new_x_parent->m_red = true; base_type::rotate_right(p_new_x_parent); p_w = p_new_x_parent->m_p_left; } if (is_effectively_black(p_w->m_p_right) && is_effectively_black(p_w->m_p_left)) { p_w->m_red = true; p_x = p_new_x_parent; p_new_x_parent = p_new_x_parent->m_p_parent; } else { if (is_effectively_black(p_w->m_p_left)) { if (p_w->m_p_right != NULL) p_w->m_p_right->m_red = false; p_w->m_red = true; base_type::rotate_left(p_w); p_w = p_new_x_parent->m_p_left; } p_w->m_red = p_new_x_parent->m_red; p_new_x_parent->m_red = false; if (p_w->m_p_left != NULL) p_w->m_p_left->m_red = false; base_type::rotate_right(p_new_x_parent); update_to_top(p_new_x_parent, (node_update* )this); break; } } if (p_x != NULL) p_x->m_red = false; } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 rb_tree_. */ #ifndef PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP #define PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP #include namespace __gnu_pbds { namespace detail { template class Node_Update, typename Allocator> struct tree_traits< Key, Mapped, Cmp_Fn, Node_Update, rb_tree_tag, Allocator> : public bin_search_tree_traits< Key, Mapped, Cmp_Fn, Node_Update, rb_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 class Node_Update, class Allocator> struct tree_traits< Key, null_mapped_type, Cmp_Fn, Node_Update, rb_tree_tag, Allocator> : public bin_search_tree_traits< Key, null_mapped_type, Cmp_Fn, Node_Update, rb_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 Å .X ..Æ split_join_fn_imps.hppÇinsert_fn_imps.hppÈfind_fn_imps.hppÉ,#constructors_destructor_fn_imps.hppÊdebug_fn_imps.hppËerase_fn_imps.hppÌ0binomial_heap_base_.hpp// -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 a base of binomial heaps. */ PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: split(Pred pred, PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);) other.clear(); if (base_type::empty()) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);) return; } base_type::to_linked_list(); node_pointer p_out = base_type::prune(pred); while (p_out != NULL) { _GLIBCXX_DEBUG_ASSERT(base_type::m_size > 0); --base_type::m_size; ++other.m_size; node_pointer p_next = p_out->m_p_next_sibling; p_out->m_p_l_child = p_out->m_p_prev_or_parent = NULL; p_out->m_metadata = 0; p_out->m_p_next_sibling = other.m_p_root; if (other.m_p_root != NULL) other.m_p_root->m_p_prev_or_parent = p_out; other.m_p_root = p_out; other.m_p_root = other.fix(other.m_p_root); p_out = p_next; } _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);) node_pointer p_cur = base_type::m_p_root; base_type::m_p_root = NULL; while (p_cur != NULL) { node_pointer p_next = p_cur->m_p_next_sibling; p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = NULL; p_cur->m_metadata = 0; p_cur->m_p_next_sibling = base_type::m_p_root; if (base_type::m_p_root != NULL) base_type::m_p_root->m_p_prev_or_parent = p_cur; base_type::m_p_root = p_cur; base_type::m_p_root = fix(base_type::m_p_root); p_cur = p_next; } m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);) } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: join(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);) node_pointer p_other = other.m_p_root; if (p_other != NULL) do { node_pointer p_next = p_other->m_p_next_sibling; std::swap(p_other->m_p_next_sibling, p_other->m_p_prev_or_parent); p_other = p_next; } while (p_other != NULL); base_type::m_p_root = join(base_type::m_p_root, other.m_p_root); base_type::m_size += other.m_size; m_p_max = NULL; other.m_p_root = NULL; other.m_size = 0; other.m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);) } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: join(node_pointer p_lhs, node_pointer p_rhs) const { node_pointer p_ret = NULL; node_pointer p_cur = NULL; while (p_lhs != NULL || p_rhs != NULL) { if (p_rhs == NULL) { if (p_cur == NULL) p_ret = p_cur = p_lhs; else { p_cur->m_p_next_sibling = p_lhs; p_lhs->m_p_prev_or_parent = p_cur; } p_cur = p_lhs = NULL; } else if (p_lhs == NULL || p_rhs->m_metadata < p_lhs->m_metadata) { if (p_cur == NULL) { p_ret = p_cur = p_rhs; p_rhs = p_rhs->m_p_prev_or_parent; } else { p_cur->m_p_next_sibling = p_rhs; p_rhs = p_rhs->m_p_prev_or_parent; p_cur->m_p_next_sibling->m_p_prev_or_parent = p_cur; p_cur = p_cur->m_p_next_sibling; } } else if (p_lhs->m_metadata < p_rhs->m_metadata) { if (p_cur == NULL) p_ret = p_cur = p_lhs; else { p_cur->m_p_next_sibling = p_lhs; p_lhs->m_p_prev_or_parent = p_cur; p_cur = p_cur->m_p_next_sibling; } p_lhs = p_cur->m_p_next_sibling; } else { node_pointer p_next_rhs = p_rhs->m_p_prev_or_parent; p_rhs->m_p_next_sibling = p_lhs; p_lhs = fix(p_rhs); p_rhs = p_next_rhs; } } if (p_cur != NULL) p_cur->m_p_next_sibling = NULL; if (p_ret != NULL) p_ret->m_p_prev_or_parent = NULL; return p_ret; } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 a base of binomial heaps. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: push(const_reference r_val) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) node_pointer p_nd = base_type::get_new_node_for_insert(r_val); insert_node(p_nd); m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) return point_iterator(p_nd); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: insert_node(node_pointer p_nd) { if (base_type::m_p_root == NULL) { p_nd->m_p_next_sibling = p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL; p_nd->m_metadata = 0; base_type::m_p_root = p_nd; return; } if (base_type::m_p_root->m_metadata > 0) { p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL; p_nd->m_p_next_sibling = base_type::m_p_root; base_type::m_p_root->m_p_prev_or_parent = p_nd; base_type::m_p_root = p_nd; p_nd->m_metadata = 0; return; } if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value)) { p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling; p_nd->m_p_prev_or_parent = NULL; p_nd->m_metadata = 1; p_nd->m_p_l_child = base_type::m_p_root; base_type::m_p_root->m_p_prev_or_parent = p_nd; base_type::m_p_root->m_p_next_sibling = NULL; base_type::m_p_root = p_nd; } else { p_nd->m_p_next_sibling = NULL; p_nd->m_p_l_child = NULL; p_nd->m_p_prev_or_parent = base_type::m_p_root; p_nd->m_metadata = 0; _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0); base_type::m_p_root->m_p_l_child = p_nd; base_type::m_p_root->m_metadata = 1; } base_type::m_p_root = fix(base_type::m_p_root); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: fix(node_pointer p_nd) const { while (p_nd->m_p_next_sibling != NULL&& p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata) { node_pointer p_next = p_nd->m_p_next_sibling; if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) { p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; if (p_nd->m_p_prev_or_parent != NULL) p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next; base_type::make_child_of(p_nd, p_next); ++p_next->m_metadata; p_nd = p_next; } else { p_nd->m_p_next_sibling = p_next->m_p_next_sibling; if (p_nd->m_p_next_sibling != NULL) p_next->m_p_next_sibling = NULL; base_type::make_child_of(p_next, p_nd); ++p_nd->m_metadata; } } if (p_nd->m_p_next_sibling != NULL) p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd; return p_nd; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: modify(point_iterator it, const_reference r_new_val) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) node_pointer p_nd = it.m_p_nd; _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd, false);) const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val); p_nd->m_value = r_new_val; if (bubble_up) { node_pointer p_parent = base_type::parent(p_nd); while (p_parent != NULL&& Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value)) { base_type::swap_with_parent(p_nd, p_parent); p_parent = base_type::parent(p_nd); } if (p_nd->m_p_prev_or_parent == NULL) base_type::m_p_root = p_nd; m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) return; } base_type::bubble_to_top(p_nd); remove_parentless_node(p_nd); insert_node(p_nd); m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 a base of binomial heaps. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_reference PB_DS_CLASS_C_DEC:: top() const { _GLIBCXX_DEBUG_ONLY(assert_valid(false);) _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); if (m_p_max == NULL) const_cast(this)->find_max(); _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL); return m_p_max->m_value; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: find_max() { node_pointer p_cur = base_type::m_p_root; m_p_max = p_cur; while (p_cur != NULL) { if (Cmp_Fn::operator()(m_p_max->m_value, p_cur->m_value)) m_p_max = p_cur; p_cur = p_cur->m_p_next_sibling; } } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 a base of binomial heaps. */ PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: copy_from_range(It first_it, It last_it) { while (first_it != last_it) push(*(first_it++)); _GLIBCXX_DEBUG_ONLY(assert_valid(false);) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binomial_heap_base_() : m_p_max(NULL) { _GLIBCXX_DEBUG_ONLY(assert_valid(false);) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binomial_heap_base_(const Cmp_Fn& r_cmp_fn) : PB_DS_BASE_C_DEC(r_cmp_fn), m_p_max(NULL) { _GLIBCXX_DEBUG_ONLY(assert_valid(false);) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binomial_heap_base_(const PB_DS_CLASS_C_DEC& other) : PB_DS_BASE_C_DEC(other), m_p_max(NULL) { _GLIBCXX_DEBUG_ONLY(assert_valid(false);) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid(false);) base_type::swap(other); std::swap(m_p_max, other.m_p_max); _GLIBCXX_DEBUG_ONLY(assert_valid(false);) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~binomial_heap_base_() { } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 a base of binomial heaps. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid(bool strictly_binomial) const { base_type::assert_valid(); assert_node_consistent(base_type::m_p_root, strictly_binomial, true); assert_max(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_max() const { if (m_p_max == NULL) return; _GLIBCXX_DEBUG_ASSERT(base_type::parent(m_p_max) == NULL); for (const_iterator it = base_type::begin(); it != base_type::end(); ++it) _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(m_p_max->m_value, it.m_p_nd->m_value)); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_node_consistent(const_node_pointer p_nd, bool strictly_binomial, bool increasing) const { _GLIBCXX_DEBUG_ASSERT(increasing || strictly_binomial); base_type::assert_node_consistent(p_nd, false); if (p_nd == NULL) return; _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == base_type::degree(p_nd)); _GLIBCXX_DEBUG_ASSERT(base_type::size_under_node(p_nd) == static_cast(1 << p_nd->m_metadata)); assert_node_consistent(p_nd->m_p_next_sibling, strictly_binomial, increasing); assert_node_consistent(p_nd->m_p_l_child, true, false); if (p_nd->m_p_next_sibling != NULL) if (increasing) { if (strictly_binomial) _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < p_nd->m_p_next_sibling->m_metadata); else _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata <= p_nd->m_p_next_sibling->m_metadata); } else _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata > p_nd->m_p_next_sibling->m_metadata); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // 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 a base of binomial heaps. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: pop() { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); if (m_p_max == NULL) find_max(); _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL); node_pointer p_nd = m_p_max; remove_parentless_node(m_p_max); base_type::actual_erase_node(p_nd); m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: remove_parentless_node(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); _GLIBCXX_DEBUG_ASSERT(base_type::parent(p_nd) == NULL); node_pointer p_cur_root = p_nd == base_type::m_p_root? p_nd->m_p_next_sibling : base_type::m_p_root; if (p_cur_root != NULL) p_cur_root->m_p_prev_or_parent = NULL; if (p_nd->m_p_prev_or_parent != NULL) p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling; if (p_nd->m_p_next_sibling != NULL) p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; node_pointer p_child = p_nd->m_p_l_child; if (p_child != NULL) { p_child->m_p_prev_or_parent = NULL; while (p_child->m_p_next_sibling != NULL) p_child = p_child->m_p_next_sibling; } m_p_max = NULL; base_type::m_p_root = join(p_cur_root, p_child); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: clear() { base_type::clear(); m_p_max = NULL; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase(point_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); base_type::bubble_to_top(it.m_p_nd); remove_parentless_node(it.m_p_nd); base_type::actual_erase_node(it.m_p_nd); m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) } PB_DS_CLASS_T_DEC template typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) if (base_type::empty()) { _GLIBCXX_DEBUG_ONLY(assert_valid(true);) return 0; } base_type::to_linked_list(); node_pointer p_out = base_type::prune(pred); size_type ersd = 0; while (p_out != NULL) { ++ersd; node_pointer p_next = p_out->m_p_next_sibling; base_type::actual_erase_node(p_out); p_out = p_next; } node_pointer p_cur = base_type::m_p_root; base_type::m_p_root = NULL; while (p_cur != NULL) { node_pointer p_next = p_cur->m_p_next_sibling; p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = NULL; p_cur->m_metadata = 0; p_cur->m_p_next_sibling = base_type::m_p_root; if (base_type::m_p_root != NULL) base_type::m_p_root->m_p_prev_or_parent = p_cur; base_type::m_p_root = p_cur; base_type::m_p_root = fix(base_type::m_p_root); p_cur = p_next; } m_p_max = NULL; _GLIBCXX_DEBUG_ONLY(assert_valid(true);) return ersd; } // -*- C++ -*- // Copyright (C) 2005, 2006 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or