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 thin_heap_.
45 */
46
47PB_DS_CLASS_T_DEC
48void
49PB_DS_CLASS_C_DEC::
50pop()
51{
52  _GLIBCXX_DEBUG_ONLY(assert_valid();)
53    _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
54
55  _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);
56
57  node_pointer p_nd = m_p_max;
58
59  remove_max_node();
60
61  base_type::actual_erase_node(p_nd);
62
63  _GLIBCXX_DEBUG_ONLY(assert_valid();)
64    }
65
66PB_DS_CLASS_T_DEC
67inline void
68PB_DS_CLASS_C_DEC::
69remove_max_node()
70{
71  to_aux_except_max();
72
73  make_from_aux();
74}
75
76PB_DS_CLASS_T_DEC
77void
78PB_DS_CLASS_C_DEC::
79to_aux_except_max()
80{
81  node_pointer p_add = base_type::m_p_root;
82
83  while (p_add != m_p_max)
84    {
85      node_pointer p_next_add = p_add->m_p_next_sibling;
86
87      add_to_aux(p_add);
88
89      p_add = p_next_add;
90    }
91
92  p_add = m_p_max->m_p_l_child;
93
94  while (p_add != NULL)
95    {
96      node_pointer p_next_add = p_add->m_p_next_sibling;
97
98      p_add->m_metadata = p_add->m_p_l_child == NULL?
99	0 :
100	p_add->m_p_l_child->m_metadata + 1;
101
102      add_to_aux(p_add);
103
104      p_add = p_next_add;
105    }
106
107  p_add = m_p_max->m_p_next_sibling;
108
109  while (p_add != NULL)
110    {
111      node_pointer p_next_add = p_add->m_p_next_sibling;
112
113      add_to_aux(p_add);
114
115      p_add = p_next_add;
116    }
117}
118
119PB_DS_CLASS_T_DEC
120inline void
121PB_DS_CLASS_C_DEC::
122add_to_aux(node_pointer p_nd)
123{
124  size_type r = p_nd->m_metadata;
125
126  while (m_a_aux[r] != NULL)
127    {
128      _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
129
130      if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value))
131	make_child_of(m_a_aux[r], p_nd);
132      else
133        {
134	  make_child_of(p_nd, m_a_aux[r]);
135
136	  p_nd = m_a_aux[r];
137        }
138
139      m_a_aux[r] = NULL;
140
141      ++r;
142    }
143
144  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
145
146  m_a_aux[r] = p_nd;
147}
148
149PB_DS_CLASS_T_DEC
150inline void
151PB_DS_CLASS_C_DEC::
152make_child_of(node_pointer p_nd, node_pointer p_new_parent)
153{
154  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata);
155  _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd ||
156		   m_a_aux[p_nd->m_metadata] == p_new_parent);
157
158  ++p_new_parent->m_metadata;
159
160  base_type::make_child_of(p_nd, p_new_parent);
161}
162
163PB_DS_CLASS_T_DEC
164inline void
165PB_DS_CLASS_C_DEC::
166make_from_aux()
167{
168  base_type::m_p_root = m_p_max = NULL;
169
170  const size_type rnk_bnd = rank_bound();
171
172  size_type i = 0;
173
174  while (i < rnk_bnd)
175    {
176      if (m_a_aux[i] != NULL)
177        {
178	  make_root_and_link(m_a_aux[i]);
179
180	  m_a_aux[i] = NULL;
181        }
182
183      ++i;
184    }
185
186  _GLIBCXX_DEBUG_ONLY(assert_aux_null();)
187    }
188
189PB_DS_CLASS_T_DEC
190inline void
191PB_DS_CLASS_C_DEC::
192remove_node(node_pointer p_nd)
193{
194  node_pointer p_parent = p_nd;
195  while (base_type::parent(p_parent) != NULL)
196    p_parent = base_type::parent(p_parent);
197
198  base_type::bubble_to_top(p_nd);
199
200  m_p_max = p_nd;
201
202  node_pointer p_fix = base_type::m_p_root;
203  while (p_fix != NULL&&  p_fix->m_p_next_sibling != p_parent)
204    p_fix = p_fix->m_p_next_sibling;
205
206  if (p_fix != NULL)
207    p_fix->m_p_next_sibling = p_nd;
208
209  remove_max_node();
210}
211
212PB_DS_CLASS_T_DEC
213inline void
214PB_DS_CLASS_C_DEC::
215clear()
216{
217  base_type::clear();
218
219  m_p_max = NULL;
220}
221
222PB_DS_CLASS_T_DEC
223void
224PB_DS_CLASS_C_DEC::
225erase(point_iterator it)
226{
227  _GLIBCXX_DEBUG_ONLY(assert_valid();)
228    _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
229
230  node_pointer p_nd = it.m_p_nd;
231
232  remove_node(p_nd);
233
234  base_type::actual_erase_node(p_nd);
235
236  _GLIBCXX_DEBUG_ONLY(assert_valid();)
237    }
238
239PB_DS_CLASS_T_DEC
240template<typename Pred>
241typename PB_DS_CLASS_C_DEC::size_type
242PB_DS_CLASS_C_DEC::
243erase_if(Pred pred)
244{
245  _GLIBCXX_DEBUG_ONLY(assert_valid();)
246
247    if (base_type::empty())
248      {
249        _GLIBCXX_DEBUG_ONLY(assert_valid();)
250
251	  return 0;
252      }
253
254  base_type::to_linked_list();
255
256  node_pointer p_out = base_type::prune(pred);
257
258  size_type ersd = 0;
259
260  while (p_out != NULL)
261    {
262      ++ersd;
263
264      node_pointer p_next = p_out->m_p_next_sibling;
265
266      base_type::actual_erase_node(p_out);
267
268      p_out = p_next;
269    }
270
271  node_pointer p_cur = base_type::m_p_root;
272
273  m_p_max = base_type::m_p_root = NULL;
274
275  while (p_cur != NULL)
276    {
277      node_pointer p_next = p_cur->m_p_next_sibling;
278
279      make_root_and_link(p_cur);
280
281      p_cur = p_next;
282    }
283
284  _GLIBCXX_DEBUG_ONLY(assert_valid();)
285
286    return ersd;
287}
288
289PB_DS_CLASS_T_DEC
290inline typename PB_DS_CLASS_C_DEC::size_type
291PB_DS_CLASS_C_DEC::
292rank_bound()
293{
294  const std::size_t* const p_upper =
295    std::upper_bound(            g_a_rank_bounds, g_a_rank_bounds + num_distinct_rank_bounds, base_type::m_size);
296
297  if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds)
298    return max_rank;
299
300  return (p_upper - g_a_rank_bounds);
301}
302
303