erase_fn_imps.hpp revision 169691
1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file erase_fn_imps.hpp 44169691Skan * Contains an implementation for rb_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skaninline bool 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skanerase(const_key_reference r_key) 51169691Skan{ 52169691Skan point_iterator it = find(r_key); 53169691Skan if (it == base_type::end()) 54169691Skan return false; 55169691Skan erase(it); 56169691Skan return true; 57169691Skan} 58169691Skan 59169691SkanPB_DS_CLASS_T_DEC 60169691Skaninline typename PB_DS_CLASS_C_DEC::iterator 61169691SkanPB_DS_CLASS_C_DEC:: 62169691Skanerase(iterator it) 63169691Skan{ 64169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 65169691Skan if (it == base_type::end()) 66169691Skan return it; 67169691Skan 68169691Skan iterator ret_it = it; 69169691Skan ++ret_it; 70169691Skan erase_node(it.m_p_nd); 71169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 72169691Skan return ret_it; 73169691Skan} 74169691Skan 75169691SkanPB_DS_CLASS_T_DEC 76169691Skaninline typename PB_DS_CLASS_C_DEC::reverse_iterator 77169691SkanPB_DS_CLASS_C_DEC:: 78169691Skanerase(reverse_iterator it) 79169691Skan{ 80169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 81169691Skan if (it.m_p_nd == base_type::m_p_head) 82169691Skan return it; 83169691Skan 84169691Skan reverse_iterator ret_it = it; 85169691Skan ++ret_it; 86169691Skan erase_node(it.m_p_nd); 87169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 88169691Skan return ret_it; 89169691Skan} 90169691Skan 91169691SkanPB_DS_CLASS_T_DEC 92169691Skantemplate<typename Pred> 93169691Skaninline typename PB_DS_CLASS_C_DEC::size_type 94169691SkanPB_DS_CLASS_C_DEC:: 95169691Skanerase_if(Pred pred) 96169691Skan{ 97169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 98169691Skan size_type num_ersd = 0; 99169691Skan iterator it = base_type::begin(); 100169691Skan while (it != base_type::end()) 101169691Skan { 102169691Skan if (pred(*it)) 103169691Skan { 104169691Skan ++num_ersd; 105169691Skan it = erase(it); 106169691Skan } 107169691Skan else 108169691Skan ++it; 109169691Skan } 110169691Skan 111169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 112169691Skan return num_ersd; 113169691Skan} 114169691Skan 115169691SkanPB_DS_CLASS_T_DEC 116169691Skanvoid 117169691SkanPB_DS_CLASS_C_DEC:: 118169691Skanerase_node(node_pointer p_nd) 119169691Skan{ 120169691Skan remove_node(p_nd); 121169691Skan base_type::actual_erase_node(p_nd); 122169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 123169691Skan} 124169691Skan 125169691SkanPB_DS_CLASS_T_DEC 126169691Skanvoid 127169691SkanPB_DS_CLASS_C_DEC:: 128169691Skanremove_node(node_pointer p_z) 129169691Skan{ 130169691Skan update_min_max_for_erased_node(p_z); 131169691Skan node_pointer p_y = p_z; 132169691Skan node_pointer p_x = NULL; 133169691Skan node_pointer p_new_x_parent = NULL; 134169691Skan 135169691Skan if (p_y->m_p_left == NULL) 136169691Skan p_x = p_y->m_p_right; 137169691Skan else if (p_y->m_p_right == NULL) 138169691Skan p_x = p_y->m_p_left; 139169691Skan else 140169691Skan { 141169691Skan p_y = p_y->m_p_right; 142169691Skan while (p_y->m_p_left != NULL) 143169691Skan p_y = p_y->m_p_left; 144169691Skan p_x = p_y->m_p_right; 145169691Skan } 146169691Skan 147169691Skan if (p_y == p_z) 148169691Skan { 149169691Skan p_new_x_parent = p_y->m_p_parent; 150169691Skan if (p_x != NULL) 151169691Skan p_x->m_p_parent = p_y->m_p_parent; 152169691Skan 153169691Skan if (base_type::m_p_head->m_p_parent == p_z) 154169691Skan base_type::m_p_head->m_p_parent = p_x; 155169691Skan else if (p_z->m_p_parent->m_p_left == p_z) 156169691Skan { 157169691Skan p_y->m_p_left = p_z->m_p_parent; 158169691Skan p_z->m_p_parent->m_p_left = p_x; 159169691Skan } 160169691Skan else 161169691Skan { 162169691Skan p_y->m_p_left = NULL; 163169691Skan p_z->m_p_parent->m_p_right = p_x; 164169691Skan } 165169691Skan } 166169691Skan else 167169691Skan { 168169691Skan p_z->m_p_left->m_p_parent = p_y; 169169691Skan p_y->m_p_left = p_z->m_p_left; 170169691Skan if (p_y != p_z->m_p_right) 171169691Skan { 172169691Skan p_new_x_parent = p_y->m_p_parent; 173169691Skan if (p_x != NULL) 174169691Skan p_x->m_p_parent = p_y->m_p_parent; 175169691Skan p_y->m_p_parent->m_p_left = p_x; 176169691Skan p_y->m_p_right = p_z->m_p_right; 177169691Skan p_z->m_p_right->m_p_parent = p_y; 178169691Skan } 179169691Skan else 180169691Skan p_new_x_parent = p_y; 181169691Skan 182169691Skan if (base_type::m_p_head->m_p_parent == p_z) 183169691Skan base_type::m_p_head->m_p_parent = p_y; 184169691Skan else if (p_z->m_p_parent->m_p_left == p_z) 185169691Skan p_z->m_p_parent->m_p_left = p_y; 186169691Skan else 187169691Skan p_z->m_p_parent->m_p_right = p_y; 188169691Skan 189169691Skan p_y->m_p_parent = p_z->m_p_parent; 190169691Skan std::swap(p_y->m_red, p_z->m_red); 191169691Skan p_y = p_z; 192169691Skan } 193169691Skan 194169691Skan update_to_top(p_new_x_parent, (node_update* )this); 195169691Skan 196169691Skan if (p_y->m_red) 197169691Skan return; 198169691Skan 199169691Skan remove_fixup(p_x, p_new_x_parent); 200169691Skan} 201169691Skan 202169691SkanPB_DS_CLASS_T_DEC 203169691Skanvoid 204169691SkanPB_DS_CLASS_C_DEC:: 205169691Skanremove_fixup(node_pointer p_x, node_pointer p_new_x_parent) 206169691Skan{ 207169691Skan _GLIBCXX_DEBUG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent); 208169691Skan 209169691Skan while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x)) 210169691Skan if (p_x == p_new_x_parent->m_p_left) 211169691Skan { 212169691Skan node_pointer p_w = p_new_x_parent->m_p_right; 213169691Skan if (p_w->m_red) 214169691Skan { 215169691Skan p_w->m_red = false; 216169691Skan p_new_x_parent->m_red = true; 217169691Skan base_type::rotate_left(p_new_x_parent); 218169691Skan p_w = p_new_x_parent->m_p_right; 219169691Skan } 220169691Skan 221169691Skan if (is_effectively_black(p_w->m_p_left) 222169691Skan && is_effectively_black(p_w->m_p_right)) 223169691Skan { 224169691Skan p_w->m_red = true; 225169691Skan p_x = p_new_x_parent; 226169691Skan p_new_x_parent = p_new_x_parent->m_p_parent; 227169691Skan } 228169691Skan else 229169691Skan { 230169691Skan if (is_effectively_black(p_w->m_p_right)) 231169691Skan { 232169691Skan if (p_w->m_p_left != NULL) 233169691Skan p_w->m_p_left->m_red = false; 234169691Skan 235169691Skan p_w->m_red = true; 236169691Skan base_type::rotate_right(p_w); 237169691Skan p_w = p_new_x_parent->m_p_right; 238169691Skan } 239169691Skan 240169691Skan p_w->m_red = p_new_x_parent->m_red; 241169691Skan p_new_x_parent->m_red = false; 242169691Skan 243169691Skan if (p_w->m_p_right != NULL) 244169691Skan p_w->m_p_right->m_red = false; 245169691Skan 246169691Skan base_type::rotate_left(p_new_x_parent); 247169691Skan update_to_top(p_new_x_parent, (node_update* )this); 248169691Skan break; 249169691Skan } 250169691Skan } 251169691Skan else 252169691Skan { 253169691Skan node_pointer p_w = p_new_x_parent->m_p_left; 254169691Skan if (p_w->m_red == true) 255169691Skan { 256169691Skan p_w->m_red = false; 257169691Skan p_new_x_parent->m_red = true; 258169691Skan base_type::rotate_right(p_new_x_parent); 259169691Skan p_w = p_new_x_parent->m_p_left; 260169691Skan } 261169691Skan 262169691Skan if (is_effectively_black(p_w->m_p_right) 263169691Skan && is_effectively_black(p_w->m_p_left)) 264169691Skan { 265169691Skan p_w->m_red = true; 266169691Skan p_x = p_new_x_parent; 267169691Skan p_new_x_parent = p_new_x_parent->m_p_parent; 268169691Skan } 269169691Skan else 270169691Skan { 271169691Skan if (is_effectively_black(p_w->m_p_left)) 272169691Skan { 273169691Skan if (p_w->m_p_right != NULL) 274169691Skan p_w->m_p_right->m_red = false; 275169691Skan 276169691Skan p_w->m_red = true; 277169691Skan base_type::rotate_left(p_w); 278169691Skan p_w = p_new_x_parent->m_p_left; 279169691Skan } 280169691Skan 281169691Skan p_w->m_red = p_new_x_parent->m_red; 282169691Skan p_new_x_parent->m_red = false; 283169691Skan 284169691Skan if (p_w->m_p_left != NULL) 285169691Skan p_w->m_p_left->m_red = false; 286169691Skan 287169691Skan base_type::rotate_right(p_new_x_parent); 288169691Skan update_to_top(p_new_x_parent, (node_update* )this); 289169691Skan break; 290169691Skan } 291169691Skan } 292169691Skan 293169691Skan if (p_x != NULL) 294169691Skan p_x->m_red = false; 295169691Skan} 296