libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file rb_tree_map_/erase_fn_imps.hpp 00038 * Contains an implementation for rb_tree_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 inline bool 00043 PB_DS_CLASS_C_DEC:: 00044 erase(key_const_reference r_key) 00045 { 00046 point_iterator it = this->find(r_key); 00047 if (it == base_type::end()) 00048 return false; 00049 erase(it); 00050 return true; 00051 } 00052 00053 PB_DS_CLASS_T_DEC 00054 inline typename PB_DS_CLASS_C_DEC::iterator 00055 PB_DS_CLASS_C_DEC:: 00056 erase(iterator it) 00057 { 00058 PB_DS_ASSERT_VALID((*this)) 00059 if (it == base_type::end()) 00060 return it; 00061 00062 iterator ret_it = it; 00063 ++ret_it; 00064 erase_node(it.m_p_nd); 00065 PB_DS_ASSERT_VALID((*this)) 00066 return ret_it; 00067 } 00068 00069 PB_DS_CLASS_T_DEC 00070 inline typename PB_DS_CLASS_C_DEC::reverse_iterator 00071 PB_DS_CLASS_C_DEC:: 00072 erase(reverse_iterator it) 00073 { 00074 PB_DS_ASSERT_VALID((*this)) 00075 if (it.m_p_nd == base_type::m_p_head) 00076 return it; 00077 00078 reverse_iterator ret_it = it; 00079 ++ret_it; 00080 erase_node(it.m_p_nd); 00081 PB_DS_ASSERT_VALID((*this)) 00082 return ret_it; 00083 } 00084 00085 PB_DS_CLASS_T_DEC 00086 template<typename Pred> 00087 inline typename PB_DS_CLASS_C_DEC::size_type 00088 PB_DS_CLASS_C_DEC:: 00089 erase_if(Pred pred) 00090 { 00091 PB_DS_ASSERT_VALID((*this)) 00092 size_type num_ersd = 0; 00093 iterator it = base_type::begin(); 00094 while (it != base_type::end()) 00095 { 00096 if (pred(*it)) 00097 { 00098 ++num_ersd; 00099 it = erase(it); 00100 } 00101 else 00102 ++it; 00103 } 00104 00105 PB_DS_ASSERT_VALID((*this)) 00106 return num_ersd; 00107 } 00108 00109 PB_DS_CLASS_T_DEC 00110 void 00111 PB_DS_CLASS_C_DEC:: 00112 erase_node(node_pointer p_nd) 00113 { 00114 remove_node(p_nd); 00115 base_type::actual_erase_node(p_nd); 00116 PB_DS_ASSERT_VALID((*this)) 00117 } 00118 00119 PB_DS_CLASS_T_DEC 00120 void 00121 PB_DS_CLASS_C_DEC:: 00122 remove_node(node_pointer p_z) 00123 { 00124 this->update_min_max_for_erased_node(p_z); 00125 node_pointer p_y = p_z; 00126 node_pointer p_x = 0; 00127 node_pointer p_new_x_parent = 0; 00128 00129 if (p_y->m_p_left == 0) 00130 p_x = p_y->m_p_right; 00131 else if (p_y->m_p_right == 0) 00132 p_x = p_y->m_p_left; 00133 else 00134 { 00135 p_y = p_y->m_p_right; 00136 while (p_y->m_p_left != 0) 00137 p_y = p_y->m_p_left; 00138 p_x = p_y->m_p_right; 00139 } 00140 00141 if (p_y == p_z) 00142 { 00143 p_new_x_parent = p_y->m_p_parent; 00144 if (p_x != 0) 00145 p_x->m_p_parent = p_y->m_p_parent; 00146 00147 if (base_type::m_p_head->m_p_parent == p_z) 00148 base_type::m_p_head->m_p_parent = p_x; 00149 else if (p_z->m_p_parent->m_p_left == p_z) 00150 { 00151 p_y->m_p_left = p_z->m_p_parent; 00152 p_z->m_p_parent->m_p_left = p_x; 00153 } 00154 else 00155 { 00156 p_y->m_p_left = 0; 00157 p_z->m_p_parent->m_p_right = p_x; 00158 } 00159 } 00160 else 00161 { 00162 p_z->m_p_left->m_p_parent = p_y; 00163 p_y->m_p_left = p_z->m_p_left; 00164 if (p_y != p_z->m_p_right) 00165 { 00166 p_new_x_parent = p_y->m_p_parent; 00167 if (p_x != 0) 00168 p_x->m_p_parent = p_y->m_p_parent; 00169 p_y->m_p_parent->m_p_left = p_x; 00170 p_y->m_p_right = p_z->m_p_right; 00171 p_z->m_p_right->m_p_parent = p_y; 00172 } 00173 else 00174 p_new_x_parent = p_y; 00175 00176 if (base_type::m_p_head->m_p_parent == p_z) 00177 base_type::m_p_head->m_p_parent = p_y; 00178 else if (p_z->m_p_parent->m_p_left == p_z) 00179 p_z->m_p_parent->m_p_left = p_y; 00180 else 00181 p_z->m_p_parent->m_p_right = p_y; 00182 00183 p_y->m_p_parent = p_z->m_p_parent; 00184 std::swap(p_y->m_red, p_z->m_red); 00185 p_y = p_z; 00186 } 00187 00188 this->update_to_top(p_new_x_parent, (node_update* )this); 00189 00190 if (p_y->m_red) 00191 return; 00192 00193 remove_fixup(p_x, p_new_x_parent); 00194 } 00195 00196 PB_DS_CLASS_T_DEC 00197 void 00198 PB_DS_CLASS_C_DEC:: 00199 remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) 00200 { 00201 _GLIBCXX_DEBUG_ASSERT(p_x == 0 || p_x->m_p_parent == p_new_x_parent); 00202 00203 while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x)) 00204 if (p_x == p_new_x_parent->m_p_left) 00205 { 00206 node_pointer p_w = p_new_x_parent->m_p_right; 00207 if (p_w->m_red) 00208 { 00209 p_w->m_red = false; 00210 p_new_x_parent->m_red = true; 00211 base_type::rotate_left(p_new_x_parent); 00212 p_w = p_new_x_parent->m_p_right; 00213 } 00214 00215 if (is_effectively_black(p_w->m_p_left) 00216 && is_effectively_black(p_w->m_p_right)) 00217 { 00218 p_w->m_red = true; 00219 p_x = p_new_x_parent; 00220 p_new_x_parent = p_new_x_parent->m_p_parent; 00221 } 00222 else 00223 { 00224 if (is_effectively_black(p_w->m_p_right)) 00225 { 00226 if (p_w->m_p_left != 0) 00227 p_w->m_p_left->m_red = false; 00228 00229 p_w->m_red = true; 00230 base_type::rotate_right(p_w); 00231 p_w = p_new_x_parent->m_p_right; 00232 } 00233 00234 p_w->m_red = p_new_x_parent->m_red; 00235 p_new_x_parent->m_red = false; 00236 00237 if (p_w->m_p_right != 0) 00238 p_w->m_p_right->m_red = false; 00239 00240 base_type::rotate_left(p_new_x_parent); 00241 this->update_to_top(p_new_x_parent, (node_update* )this); 00242 break; 00243 } 00244 } 00245 else 00246 { 00247 node_pointer p_w = p_new_x_parent->m_p_left; 00248 if (p_w->m_red == true) 00249 { 00250 p_w->m_red = false; 00251 p_new_x_parent->m_red = true; 00252 base_type::rotate_right(p_new_x_parent); 00253 p_w = p_new_x_parent->m_p_left; 00254 } 00255 00256 if (is_effectively_black(p_w->m_p_right) 00257 && is_effectively_black(p_w->m_p_left)) 00258 { 00259 p_w->m_red = true; 00260 p_x = p_new_x_parent; 00261 p_new_x_parent = p_new_x_parent->m_p_parent; 00262 } 00263 else 00264 { 00265 if (is_effectively_black(p_w->m_p_left)) 00266 { 00267 if (p_w->m_p_right != 0) 00268 p_w->m_p_right->m_red = false; 00269 00270 p_w->m_red = true; 00271 base_type::rotate_left(p_w); 00272 p_w = p_new_x_parent->m_p_left; 00273 } 00274 00275 p_w->m_red = p_new_x_parent->m_red; 00276 p_new_x_parent->m_red = false; 00277 00278 if (p_w->m_p_left != 0) 00279 p_w->m_p_left->m_red = false; 00280 00281 base_type::rotate_right(p_new_x_parent); 00282 this->update_to_top(p_new_x_parent, (node_update* )this); 00283 break; 00284 } 00285 } 00286 00287 if (p_x != 0) 00288 p_x->m_red = false; 00289 }