erase_fn_imps.hpp revision 169692
1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 2, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file erase_fn_imps.hpp 44 * Contains an implementation class for splay_tree_. 45 */ 46 47PB_DS_CLASS_T_DEC 48inline bool 49PB_DS_CLASS_C_DEC:: 50erase(const_key_reference r_key) 51{ 52 point_iterator it = find(r_key); 53 if (it == base_type::end()) 54 return false; 55 erase(it); 56 return true; 57} 58 59PB_DS_CLASS_T_DEC 60inline typename PB_DS_CLASS_C_DEC::iterator 61PB_DS_CLASS_C_DEC:: 62erase(iterator it) 63{ 64 _GLIBCXX_DEBUG_ONLY(assert_valid()); 65 if (it == base_type::end()) 66 return it; 67 iterator ret_it = it; 68 ++ret_it; 69 erase_node(it.m_p_nd); 70 _GLIBCXX_DEBUG_ONLY(assert_valid()); 71 return ret_it; 72} 73 74PB_DS_CLASS_T_DEC 75inline typename PB_DS_CLASS_C_DEC::reverse_iterator 76PB_DS_CLASS_C_DEC:: 77erase(reverse_iterator it) 78{ 79 _GLIBCXX_DEBUG_ONLY(assert_valid()); 80 if (it.m_p_nd == base_type::m_p_head) 81 return (it); 82 reverse_iterator ret_it = it; 83 ++ret_it; 84 erase_node(it.m_p_nd); 85 _GLIBCXX_DEBUG_ONLY(assert_valid()); 86 return ret_it; 87} 88 89PB_DS_CLASS_T_DEC 90template<typename Pred> 91inline typename PB_DS_CLASS_C_DEC::size_type 92PB_DS_CLASS_C_DEC:: 93erase_if(Pred pred) 94{ 95 _GLIBCXX_DEBUG_ONLY(assert_valid();) 96 size_type num_ersd = 0; 97 iterator it = base_type::begin(); 98 while (it != base_type::end()) 99 { 100 if (pred(*it)) 101 { 102 ++num_ersd; 103 it = erase(it); 104 } 105 else 106 ++it; 107 } 108 _GLIBCXX_DEBUG_ONLY(assert_valid();) 109 return num_ersd; 110} 111 112PB_DS_CLASS_T_DEC 113void 114PB_DS_CLASS_C_DEC:: 115erase_node(node_pointer p_nd) 116{ 117 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 118 splay(p_nd); 119 120 _GLIBCXX_DEBUG_ONLY(assert_valid();) 121 _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); 122 123 node_pointer p_l = p_nd->m_p_left; 124 node_pointer p_r = p_nd->m_p_right; 125 126 base_type::update_min_max_for_erased_node(p_nd); 127 base_type::actual_erase_node(p_nd); 128 if (p_r == NULL) 129 { 130 base_type::m_p_head->m_p_parent = p_l; 131 if (p_l != NULL) 132 p_l->m_p_parent = base_type::m_p_head; 133 _GLIBCXX_DEBUG_ONLY(assert_valid();) 134 return; 135 } 136 137 node_pointer p_target_r = leftmost(p_r); 138 _GLIBCXX_DEBUG_ASSERT(p_target_r != NULL); 139 p_r->m_p_parent = base_type::m_p_head; 140 base_type::m_p_head->m_p_parent = p_r; 141 splay(p_target_r); 142 143 _GLIBCXX_DEBUG_ONLY(p_target_r->m_p_left = NULL); 144 _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_parent == this->m_p_head); 145 _GLIBCXX_DEBUG_ASSERT(this->m_p_head->m_p_parent == p_target_r); 146 147 p_target_r->m_p_left = p_l; 148 if (p_l != NULL) 149 p_l->m_p_parent = p_target_r; 150 _GLIBCXX_DEBUG_ONLY(assert_valid();) 151 apply_update(p_target_r, (node_update* )this); 152} 153 154PB_DS_CLASS_T_DEC 155inline typename PB_DS_CLASS_C_DEC::node_pointer 156PB_DS_CLASS_C_DEC:: 157leftmost(node_pointer p_nd) 158{ 159 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 160 while (p_nd->m_p_left != NULL) 161 p_nd = p_nd->m_p_left; 162 return p_nd; 163} 164