libstdc++
rb_tree_map_/erase_fn_imps.hpp
Go to the documentation of this file.
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 }