Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/11/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp
$ cat -n /usr/include/c++/11/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp 1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2021 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** 37 * @file rb_tree_map_/erase_fn_imps.hpp 38 * Contains an implementation for rb_tree_. 39 */ 40 41 #ifdef PB_DS_CLASS_C_DEC 42 43 PB_DS_CLASS_T_DEC 44 inline bool 45 PB_DS_CLASS_C_DEC:: 46 erase(key_const_reference r_key) 47 { 48 point_iterator it = this->find(r_key); 49 if (it == base_type::end()) 50 return false; 51 erase(it); 52 return true; 53 } 54 55 PB_DS_CLASS_T_DEC 56 inline typename PB_DS_CLASS_C_DEC::iterator 57 PB_DS_CLASS_C_DEC:: 58 erase(iterator it) 59 { 60 PB_DS_ASSERT_VALID((*this)) 61 if (it == base_type::end()) 62 return it; 63 64 iterator ret_it = it; 65 ++ret_it; 66 erase_node(it.m_p_nd); 67 PB_DS_ASSERT_VALID((*this)) 68 return ret_it; 69 } 70 71 PB_DS_CLASS_T_DEC 72 inline typename PB_DS_CLASS_C_DEC::reverse_iterator 73 PB_DS_CLASS_C_DEC:: 74 erase(reverse_iterator it) 75 { 76 PB_DS_ASSERT_VALID((*this)) 77 if (it.m_p_nd == base_type::m_p_head) 78 return it; 79 80 reverse_iterator ret_it = it; 81 ++ret_it; 82 erase_node(it.m_p_nd); 83 PB_DS_ASSERT_VALID((*this)) 84 return ret_it; 85 } 86 87 PB_DS_CLASS_T_DEC 88 template<typename Pred> 89 inline typename PB_DS_CLASS_C_DEC::size_type 90 PB_DS_CLASS_C_DEC:: 91 erase_if(Pred pred) 92 { 93 PB_DS_ASSERT_VALID((*this)) 94 size_type num_ersd = 0; 95 iterator it = base_type::begin(); 96 while (it != base_type::end()) 97 { 98 if (pred(*it)) 99 { 100 ++num_ersd; 101 it = erase(it); 102 } 103 else 104 ++it; 105 } 106 107 PB_DS_ASSERT_VALID((*this)) 108 return num_ersd; 109 } 110 111 PB_DS_CLASS_T_DEC 112 void 113 PB_DS_CLASS_C_DEC:: 114 erase_node(node_pointer p_nd) 115 { 116 remove_node(p_nd); 117 base_type::actual_erase_node(p_nd); 118 PB_DS_ASSERT_VALID((*this)) 119 } 120 121 PB_DS_CLASS_T_DEC 122 void 123 PB_DS_CLASS_C_DEC:: 124 remove_node(node_pointer p_z) 125 { 126 this->update_min_max_for_erased_node(p_z); 127 node_pointer p_y = p_z; 128 node_pointer p_x = 0; 129 node_pointer p_new_x_parent = 0; 130 131 if (p_y->m_p_left == 0) 132 p_x = p_y->m_p_right; 133 else if (p_y->m_p_right == 0) 134 p_x = p_y->m_p_left; 135 else 136 { 137 p_y = p_y->m_p_right; 138 while (p_y->m_p_left != 0) 139 p_y = p_y->m_p_left; 140 p_x = p_y->m_p_right; 141 } 142 143 if (p_y == p_z) 144 { 145 p_new_x_parent = p_y->m_p_parent; 146 if (p_x != 0) 147 p_x->m_p_parent = p_y->m_p_parent; 148 149 if (base_type::m_p_head->m_p_parent == p_z) 150 base_type::m_p_head->m_p_parent = p_x; 151 else if (p_z->m_p_parent->m_p_left == p_z) 152 { 153 p_y->m_p_left = p_z->m_p_parent; 154 p_z->m_p_parent->m_p_left = p_x; 155 } 156 else 157 { 158 p_y->m_p_left = 0; 159 p_z->m_p_parent->m_p_right = p_x; 160 } 161 } 162 else 163 { 164 p_z->m_p_left->m_p_parent = p_y; 165 p_y->m_p_left = p_z->m_p_left; 166 if (p_y != p_z->m_p_right) 167 { 168 p_new_x_parent = p_y->m_p_parent; 169 if (p_x != 0) 170 p_x->m_p_parent = p_y->m_p_parent; 171 p_y->m_p_parent->m_p_left = p_x; 172 p_y->m_p_right = p_z->m_p_right; 173 p_z->m_p_right->m_p_parent = p_y; 174 } 175 else 176 p_new_x_parent = p_y; 177 178 if (base_type::m_p_head->m_p_parent == p_z) 179 base_type::m_p_head->m_p_parent = p_y; 180 else if (p_z->m_p_parent->m_p_left == p_z) 181 p_z->m_p_parent->m_p_left = p_y; 182 else 183 p_z->m_p_parent->m_p_right = p_y; 184 185 p_y->m_p_parent = p_z->m_p_parent; 186 std::swap(p_y->m_red, p_z->m_red); 187 p_y = p_z; 188 } 189 190 this->update_to_top(p_new_x_parent, (node_update* )this); 191 192 if (p_y->m_red) 193 return; 194 195 remove_fixup(p_x, p_new_x_parent); 196 } 197 198 PB_DS_CLASS_T_DEC 199 void 200 PB_DS_CLASS_C_DEC:: 201 remove_fixup(node_pointer p_x, node_pointer p_new_x_parent) 202 { 203 _GLIBCXX_DEBUG_ASSERT(p_x == 0 || p_x->m_p_parent == p_new_x_parent); 204 205 while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x)) 206 if (p_x == p_new_x_parent->m_p_left) 207 { 208 node_pointer p_w = p_new_x_parent->m_p_right; 209 if (p_w->m_red) 210 { 211 p_w->m_red = false; 212 p_new_x_parent->m_red = true; 213 base_type::rotate_left(p_new_x_parent); 214 p_w = p_new_x_parent->m_p_right; 215 } 216 217 if (is_effectively_black(p_w->m_p_left) 218 && is_effectively_black(p_w->m_p_right)) 219 { 220 p_w->m_red = true; 221 p_x = p_new_x_parent; 222 p_new_x_parent = p_new_x_parent->m_p_parent; 223 } 224 else 225 { 226 if (is_effectively_black(p_w->m_p_right)) 227 { 228 if (p_w->m_p_left != 0) 229 p_w->m_p_left->m_red = false; 230 231 p_w->m_red = true; 232 base_type::rotate_right(p_w); 233 p_w = p_new_x_parent->m_p_right; 234 } 235 236 p_w->m_red = p_new_x_parent->m_red; 237 p_new_x_parent->m_red = false; 238 239 if (p_w->m_p_right != 0) 240 p_w->m_p_right->m_red = false; 241 242 base_type::rotate_left(p_new_x_parent); 243 this->update_to_top(p_new_x_parent, (node_update* )this); 244 break; 245 } 246 } 247 else 248 { 249 node_pointer p_w = p_new_x_parent->m_p_left; 250 if (p_w->m_red == true) 251 { 252 p_w->m_red = false; 253 p_new_x_parent->m_red = true; 254 base_type::rotate_right(p_new_x_parent); 255 p_w = p_new_x_parent->m_p_left; 256 } 257 258 if (is_effectively_black(p_w->m_p_right) 259 && is_effectively_black(p_w->m_p_left)) 260 { 261 p_w->m_red = true; 262 p_x = p_new_x_parent; 263 p_new_x_parent = p_new_x_parent->m_p_parent; 264 } 265 else 266 { 267 if (is_effectively_black(p_w->m_p_left)) 268 { 269 if (p_w->m_p_right != 0) 270 p_w->m_p_right->m_red = false; 271 272 p_w->m_red = true; 273 base_type::rotate_left(p_w); 274 p_w = p_new_x_parent->m_p_left; 275 } 276 277 p_w->m_red = p_new_x_parent->m_red; 278 p_new_x_parent->m_red = false; 279 280 if (p_w->m_p_left != 0) 281 p_w->m_p_left->m_red = false; 282 283 base_type::rotate_right(p_new_x_parent); 284 this->update_to_top(p_new_x_parent, (node_update* )this); 285 break; 286 } 287 } 288 289 if (p_x != 0) 290 p_x->m_red = false; 291 } 292 #endif
Welcome to MyWebUniversity on April 15, 2025.
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
