libstdc++
erase_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2015 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 }