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