contrib/libstdc++/include/ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp

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