1// -*- C++ -*- 2 3// Copyright (C) 2005 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 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 31 32// Permission to use, copy, modify, sell, and distribute this software 33// is hereby granted without fee, provided that the above copyright 34// notice appears in all copies, and that both that copyright notice and 35// this permission notice appear in supporting documentation. None of 36// the above authors, nor IBM Haifa Research Laboratories, make any 37// representation about the suitability of this software for any 38// purpose. It is provided "as is" without express or implied warranty. 39 40/** 41 * @file erase_fn_imps.hpp 42 * Contains an implementation class for splay_tree_. 43 */ 44 45PB_ASSOC_CLASS_T_DEC 46inline typename PB_ASSOC_CLASS_C_DEC::size_type 47PB_ASSOC_CLASS_C_DEC:: 48erase(const_key_reference r_key) 49{ 50 iterator it = find(r_key); 51 52 if (it == PB_ASSOC_BASE_C_DEC::find_end()) 53 return (0); 54 55 erase(it); 56 57 return (1); 58} 59 60PB_ASSOC_CLASS_T_DEC 61inline typename PB_ASSOC_CLASS_C_DEC::const_iterator 62PB_ASSOC_CLASS_C_DEC:: 63erase(const_iterator it) 64{ 65 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 66 67 if (it == PB_ASSOC_BASE_C_DEC::find_end()) 68 return (it); 69 70 const_iterator ret_it = it; 71 72 ++ret_it; 73 74 erase_node(it.m_p_nd); 75 76 return (ret_it); 77} 78 79#ifdef PB_ASSOC_DATA_TRUE_INDICATOR 80PB_ASSOC_CLASS_T_DEC 81inline typename PB_ASSOC_CLASS_C_DEC::iterator 82PB_ASSOC_CLASS_C_DEC:: 83erase(iterator it) 84{ 85 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 86 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();) 87 88 if (it == PB_ASSOC_BASE_C_DEC::find_end()) 89 return (it); 90 91 iterator ret_it = it; 92 93 ++ret_it; 94 95 erase_node(it.m_p_nd); 96 97 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 98 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();) 99 100 return (ret_it); 101} 102#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR 103 104PB_ASSOC_CLASS_T_DEC 105inline typename PB_ASSOC_CLASS_C_DEC::const_reverse_iterator 106PB_ASSOC_CLASS_C_DEC:: 107erase(const_reverse_iterator it) 108{ 109 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 110 111 if (it == PB_ASSOC_BASE_C_DEC::find_rend()) 112 return (it); 113 114 const_reverse_iterator ret_it = it; 115 116 ++ret_it; 117 118 erase_node(it.m_p_nd); 119 120 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 121 122 return (ret_it); 123} 124 125#ifdef PB_ASSOC_DATA_TRUE_INDICATOR 126PB_ASSOC_CLASS_T_DEC 127inline typename PB_ASSOC_CLASS_C_DEC::reverse_iterator 128PB_ASSOC_CLASS_C_DEC:: 129erase(reverse_iterator it) 130{ 131 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 132 133 if (it == PB_ASSOC_BASE_C_DEC::find_rend()) 134 return (it); 135 136 reverse_iterator ret_it = it; 137 138 ++ret_it; 139 140 erase_node(it.m_p_nd); 141 142 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid()); 143 144 return (ret_it); 145} 146#endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR 147 148PB_ASSOC_CLASS_T_DEC 149template<class Pred> 150inline typename PB_ASSOC_CLASS_C_DEC::size_type 151PB_ASSOC_CLASS_C_DEC:: 152erase_if(Pred pred) 153{ 154 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) 155 156 size_type num_ersd = 0; 157 158 iterator it = PB_ASSOC_BASE_C_DEC::begin(); 159 160 while (it != PB_ASSOC_BASE_C_DEC::end()) 161 if (pred(*it)) 162 { 163 ++num_ersd; 164 165 it = erase(it); 166 } 167 else 168 ++it; 169 170 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();) 171 172 return (num_ersd); 173} 174 175PB_ASSOC_CLASS_T_DEC 176void 177PB_ASSOC_CLASS_C_DEC:: 178erase_node(node_pointer p_nd) 179{ 180 PB_ASSOC_DBG_ASSERT(p_nd != NULL); 181 182 splay(p_nd); 183 184 PB_ASSOC_DBG_ONLY(assert_valid();) 185 PB_ASSOC_DBG_ASSERT(p_nd == PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent); 186 187 node_pointer p_l = p_nd->m_p_left; 188 node_pointer p_r = p_nd->m_p_right; 189 190 PB_ASSOC_BASE_C_DEC::update_min_max_for_erased_node(p_nd); 191 192 PB_ASSOC_BASE_C_DEC::actual_erase_node(p_nd); 193 194 if (p_r == NULL) 195 { 196 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_l; 197 198 if (p_l != NULL) 199 p_l->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head; 200 201 PB_ASSOC_DBG_ONLY(assert_valid();) 202 203 return; 204 } 205 206 node_pointer p_target_r = leftmost(p_r); 207 208 PB_ASSOC_DBG_ASSERT(p_target_r != NULL); 209 210 p_r->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head; 211 212 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_r; 213 214 splay(p_target_r); 215 216 PB_ASSOC_DBG_ONLY(p_target_r->m_p_left = NULL); 217 218 PB_ASSOC_DBG_ASSERT(p_target_r->m_p_parent == 219 PB_ASSOC_BASE_C_DEC::m_p_head); 220 221 PB_ASSOC_DBG_ASSERT(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == 222 p_target_r); 223 224 p_target_r->m_p_left = p_l; 225 226 if (p_l != NULL) 227 p_l->m_p_parent = p_target_r; 228 229 PB_ASSOC_DBG_ONLY(assert_valid();) 230 231 apply_update(p_target_r, (Node_Updator* )this); 232} 233 234PB_ASSOC_CLASS_T_DEC 235inline typename PB_ASSOC_CLASS_C_DEC::node_pointer 236PB_ASSOC_CLASS_C_DEC:: 237leftmost(node_pointer p_nd) 238{ 239 PB_ASSOC_DBG_ASSERT(p_nd != NULL); 240 241 while (p_nd->m_p_left != NULL) 242 p_nd = p_nd->m_p_left; 243 244 return (p_nd); 245} 246