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
47PB_DS_CLASS_T_DEC
48inline bool
49PB_DS_CLASS_C_DEC::
50erase(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
59PB_DS_CLASS_T_DEC
60inline typename PB_DS_CLASS_C_DEC::iterator
61PB_DS_CLASS_C_DEC::
62erase(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
75PB_DS_CLASS_T_DEC
76inline typename PB_DS_CLASS_C_DEC::reverse_iterator
77PB_DS_CLASS_C_DEC::
78erase(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
91PB_DS_CLASS_T_DEC
92template<typename Pred>
93inline typename PB_DS_CLASS_C_DEC::size_type
94PB_DS_CLASS_C_DEC::
95erase_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
115PB_DS_CLASS_T_DEC
116void
117PB_DS_CLASS_C_DEC::
118erase_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
125PB_DS_CLASS_T_DEC
126void
127PB_DS_CLASS_C_DEC::
128remove_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
202PB_DS_CLASS_T_DEC
203void
204PB_DS_CLASS_C_DEC::
205remove_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}
296