libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2010, 2011 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 PB_DS_CLASS_T_DEC
  42 inline bool
  43 PB_DS_CLASS_C_DEC::
  44 erase(key_const_reference r_key)
  45 {
  46   point_iterator it = this->find(r_key);
  47   if (it == base_type::end())
  48     return false;
  49   erase(it);
  50   return true;
  51 }
  52
  53 PB_DS_CLASS_T_DEC
  54 inline typename PB_DS_CLASS_C_DEC::iterator
  55 PB_DS_CLASS_C_DEC::
  56 erase(iterator it)
  57 {
  58   PB_DS_ASSERT_VALID((*this))
  59   if (it == base_type::end())
  60     return it;
  61
  62   iterator ret_it = it;
  63   ++ret_it;
  64   erase_node(it.m_p_nd);
  65   PB_DS_ASSERT_VALID((*this))
  66   return ret_it;
  67 }
  68
  69 PB_DS_CLASS_T_DEC
  70 inline typename PB_DS_CLASS_C_DEC::reverse_iterator
  71 PB_DS_CLASS_C_DEC::
  72 erase(reverse_iterator it)
  73 {
  74   PB_DS_ASSERT_VALID((*this))
  75   if (it.m_p_nd == base_type::m_p_head)
  76     return it;
  77
  78   reverse_iterator ret_it = it;
  79   ++ret_it;
  80   erase_node(it.m_p_nd);
  81   PB_DS_ASSERT_VALID((*this))
  82   return ret_it;
  83 }
  84
  85 PB_DS_CLASS_T_DEC
  86 template<typename Pred>
  87 inline typename PB_DS_CLASS_C_DEC::size_type
  88 PB_DS_CLASS_C_DEC::
  89 erase_if(Pred pred)
  90 {
  91   PB_DS_ASSERT_VALID((*this))
  92   size_type num_ersd = 0;
  93   iterator it = base_type::begin();
  94   while (it != base_type::end())
  95     {
  96       if (pred(*it))
  97         {
  98           ++num_ersd;
  99           it = erase(it);
 100         }
 101       else
 102         ++it;
 103     }
 104
 105   PB_DS_ASSERT_VALID((*this))
 106   return num_ersd;
 107 }
 108
 109 PB_DS_CLASS_T_DEC
 110 void
 111 PB_DS_CLASS_C_DEC::
 112 erase_node(node_pointer p_nd)
 113 {
 114   remove_node(p_nd);
 115   base_type::actual_erase_node(p_nd);
 116   PB_DS_ASSERT_VALID((*this))
 117 }
 118
 119 PB_DS_CLASS_T_DEC
 120 void
 121 PB_DS_CLASS_C_DEC::
 122 remove_node(node_pointer p_z)
 123 {
 124   this->update_min_max_for_erased_node(p_z);
 125   node_pointer p_y = p_z;
 126   node_pointer p_x = 0;
 127   node_pointer p_new_x_parent = 0;
 128
 129   if (p_y->m_p_left == 0)
 130     p_x = p_y->m_p_right;
 131   else if (p_y->m_p_right == 0)
 132     p_x = p_y->m_p_left;
 133   else
 134     {
 135       p_y = p_y->m_p_right;
 136       while (p_y->m_p_left != 0)
 137         p_y = p_y->m_p_left;
 138       p_x = p_y->m_p_right;
 139     }
 140
 141   if (p_y == p_z)
 142     {
 143       p_new_x_parent = p_y->m_p_parent;
 144       if (p_x != 0)
 145         p_x->m_p_parent = p_y->m_p_parent;
 146
 147       if (base_type::m_p_head->m_p_parent == p_z)
 148         base_type::m_p_head->m_p_parent = p_x;
 149       else if (p_z->m_p_parent->m_p_left == p_z)
 150         {
 151           p_y->m_p_left = p_z->m_p_parent;
 152           p_z->m_p_parent->m_p_left = p_x;
 153         }
 154       else
 155         {
 156           p_y->m_p_left = 0;
 157           p_z->m_p_parent->m_p_right = p_x;
 158         }
 159     }
 160   else
 161     {
 162       p_z->m_p_left->m_p_parent = p_y;
 163       p_y->m_p_left = p_z->m_p_left;
 164       if (p_y != p_z->m_p_right)
 165         {
 166           p_new_x_parent = p_y->m_p_parent;
 167           if (p_x != 0)
 168             p_x->m_p_parent = p_y->m_p_parent;
 169           p_y->m_p_parent->m_p_left = p_x;
 170           p_y->m_p_right = p_z->m_p_right;
 171           p_z->m_p_right->m_p_parent = p_y;
 172         }
 173       else
 174         p_new_x_parent = p_y;
 175
 176       if (base_type::m_p_head->m_p_parent == p_z)
 177         base_type::m_p_head->m_p_parent = p_y;
 178       else if (p_z->m_p_parent->m_p_left == p_z)
 179         p_z->m_p_parent->m_p_left = p_y;
 180       else
 181         p_z->m_p_parent->m_p_right = p_y;
 182
 183       p_y->m_p_parent = p_z->m_p_parent;
 184       std::swap(p_y->m_red, p_z->m_red);
 185       p_y = p_z;
 186     }
 187
 188   this->update_to_top(p_new_x_parent, (node_update* )this);
 189
 190   if (p_y->m_red)
 191     return;
 192
 193   remove_fixup(p_x, p_new_x_parent);
 194 }
 195
 196 PB_DS_CLASS_T_DEC
 197 void
 198 PB_DS_CLASS_C_DEC::
 199 remove_fixup(node_pointer p_x, node_pointer p_new_x_parent)
 200 {
 201   _GLIBCXX_DEBUG_ASSERT(p_x == 0 || p_x->m_p_parent == p_new_x_parent);
 202
 203   while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x))
 204     if (p_x == p_new_x_parent->m_p_left)
 205       {
 206         node_pointer p_w = p_new_x_parent->m_p_right;
 207         if (p_w->m_red)
 208           {
 209             p_w->m_red = false;
 210             p_new_x_parent->m_red = true;
 211             base_type::rotate_left(p_new_x_parent);
 212             p_w = p_new_x_parent->m_p_right;
 213           }
 214
 215         if (is_effectively_black(p_w->m_p_left)
 216             && is_effectively_black(p_w->m_p_right))
 217           {
 218             p_w->m_red = true;
 219             p_x = p_new_x_parent;
 220             p_new_x_parent = p_new_x_parent->m_p_parent;
 221           }
 222         else
 223           {
 224             if (is_effectively_black(p_w->m_p_right))
 225               {
 226                 if (p_w->m_p_left != 0)
 227                   p_w->m_p_left->m_red = false;
 228
 229                 p_w->m_red = true;
 230                 base_type::rotate_right(p_w);
 231                 p_w = p_new_x_parent->m_p_right;
 232               }
 233
 234             p_w->m_red = p_new_x_parent->m_red;
 235             p_new_x_parent->m_red = false;
 236
 237             if (p_w->m_p_right != 0)
 238               p_w->m_p_right->m_red = false;
 239
 240             base_type::rotate_left(p_new_x_parent);
 241             this->update_to_top(p_new_x_parent, (node_update* )this);
 242             break;
 243           }
 244       }
 245     else
 246       {
 247         node_pointer p_w = p_new_x_parent->m_p_left;
 248         if (p_w->m_red == true)
 249           {
 250             p_w->m_red = false;
 251             p_new_x_parent->m_red = true;
 252             base_type::rotate_right(p_new_x_parent);
 253             p_w = p_new_x_parent->m_p_left;
 254           }
 255
 256         if (is_effectively_black(p_w->m_p_right)
 257             && is_effectively_black(p_w->m_p_left))
 258           {
 259             p_w->m_red = true;
 260             p_x = p_new_x_parent;
 261             p_new_x_parent = p_new_x_parent->m_p_parent;
 262           }
 263         else
 264           {
 265             if (is_effectively_black(p_w->m_p_left))
 266               {
 267                 if (p_w->m_p_right != 0)
 268                   p_w->m_p_right->m_red = false;
 269
 270                 p_w->m_red = true;
 271                 base_type::rotate_left(p_w);
 272                 p_w = p_new_x_parent->m_p_left;
 273               }
 274
 275             p_w->m_red = p_new_x_parent->m_red;
 276             p_new_x_parent->m_red = false;
 277
 278             if (p_w->m_p_left != 0)
 279               p_w->m_p_left->m_red = false;
 280
 281             base_type::rotate_right(p_new_x_parent);
 282             this->update_to_top(p_new_x_parent, (node_update* )this);
 283             break;
 284           }
 285       }
 286
 287   if (p_x != 0)
 288     p_x->m_red = false;
 289 }