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 class for a pairing 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  node_pointer p_new_root = join_node_children(base_type::m_p_root);
56  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_new_root, false);)
57  if (p_new_root != NULL)
58    p_new_root->m_p_prev_or_parent = NULL;
59
60  base_type::actual_erase_node(base_type::m_p_root);
61  base_type::m_p_root = p_new_root;
62  _GLIBCXX_DEBUG_ONLY(assert_valid();)
63}
64
65PB_DS_CLASS_T_DEC
66void
67PB_DS_CLASS_C_DEC::
68erase(point_iterator it)
69{
70  _GLIBCXX_DEBUG_ONLY(assert_valid();)
71  _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
72  remove_node(it.m_p_nd);
73  base_type::actual_erase_node(it.m_p_nd);
74  _GLIBCXX_DEBUG_ONLY(assert_valid();)
75}
76
77PB_DS_CLASS_T_DEC
78void
79PB_DS_CLASS_C_DEC::
80remove_node(node_pointer p_nd)
81{
82  _GLIBCXX_DEBUG_ONLY(assert_valid();)
83  _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
84  node_pointer p_new_child = join_node_children(p_nd);
85
86#ifdef _GLIBCXX_DEBUG
87  if (p_new_child != NULL)
88    base_type::assert_node_consistent(p_new_child, false);
89#endif
90
91  if (p_nd == base_type::m_p_root)
92    {
93      if (p_new_child != NULL)
94	p_new_child->m_p_prev_or_parent = NULL;
95      base_type::m_p_root = p_new_child;
96      _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(base_type::m_p_root, false);)
97      return;
98    }
99
100  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_prev_or_parent != NULL);
101  if (p_nd->m_p_prev_or_parent->m_p_l_child == p_nd)
102    {
103      if (p_new_child != NULL)
104        {
105	  p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
106	  p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling;
107	  if (p_new_child->m_p_next_sibling != NULL)
108	    p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child;
109	  p_nd->m_p_prev_or_parent->m_p_l_child = p_new_child;
110	  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd->m_p_prev_or_parent, false);)
111          return;
112        }
113
114      p_nd->m_p_prev_or_parent->m_p_l_child = p_nd->m_p_next_sibling;
115      if (p_nd->m_p_next_sibling != NULL)
116	p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
117      _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd->m_p_prev_or_parent, false);)
118      return;
119    }
120
121  if (p_new_child != NULL)
122    {
123      p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
124      p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling;
125      if (p_new_child->m_p_next_sibling != NULL)
126	p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child;
127      p_new_child->m_p_prev_or_parent->m_p_next_sibling = p_new_child;
128      _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd->m_p_prev_or_parent, false);)
129      return;
130    }
131
132  p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling;
133  if (p_nd->m_p_next_sibling != NULL)
134    p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
135  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd->m_p_prev_or_parent, false);)
136}
137
138PB_DS_CLASS_T_DEC
139typename PB_DS_CLASS_C_DEC::node_pointer
140PB_DS_CLASS_C_DEC::
141join_node_children(node_pointer p_nd)
142{
143  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
144  node_pointer p_ret = p_nd->m_p_l_child;
145  if (p_ret == NULL)
146    return NULL;
147  while (p_ret->m_p_next_sibling != NULL)
148    p_ret = forward_join(p_ret, p_ret->m_p_next_sibling);
149  while (p_ret->m_p_prev_or_parent != p_nd)
150    p_ret = back_join(p_ret->m_p_prev_or_parent, p_ret);
151  _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_ret, false);)
152  return p_ret;
153}
154
155PB_DS_CLASS_T_DEC
156typename PB_DS_CLASS_C_DEC::node_pointer
157PB_DS_CLASS_C_DEC::
158forward_join(node_pointer p_nd, node_pointer p_next)
159{
160  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
161  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling == p_next);
162  if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
163    {
164      p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
165      base_type::make_child_of(p_nd, p_next);
166      return p_next->m_p_next_sibling == NULL
167	? p_next : p_next->m_p_next_sibling;
168    }
169
170  if (p_next->m_p_next_sibling != NULL)
171    {
172      p_next->m_p_next_sibling->m_p_prev_or_parent = p_nd;
173      p_nd->m_p_next_sibling = p_next->m_p_next_sibling;
174      base_type::make_child_of(p_next, p_nd);
175      return p_nd->m_p_next_sibling;
176    }
177
178  p_nd->m_p_next_sibling = NULL;
179  base_type::make_child_of(p_next, p_nd);
180  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd, false));
181  return p_nd;
182}
183
184PB_DS_CLASS_T_DEC
185typename PB_DS_CLASS_C_DEC::node_pointer
186PB_DS_CLASS_C_DEC::
187back_join(node_pointer p_nd, node_pointer p_next)
188{
189  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
190  _GLIBCXX_DEBUG_ASSERT(p_next->m_p_next_sibling == NULL);
191
192  if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
193    {
194      p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;
195      base_type::make_child_of(p_nd, p_next);
196      _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_next, false));
197      return p_next;
198    }
199
200  p_nd->m_p_next_sibling = NULL;
201  base_type::make_child_of(p_next, p_nd);
202  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd, false));
203  return p_nd;
204}
205
206PB_DS_CLASS_T_DEC
207template<typename Pred>
208typename PB_DS_CLASS_C_DEC::size_type
209PB_DS_CLASS_C_DEC::
210erase_if(Pred pred)
211{
212  _GLIBCXX_DEBUG_ONLY(assert_valid();)
213    if (base_type::empty())
214      {
215        _GLIBCXX_DEBUG_ONLY(assert_valid();)
216	return 0;
217      }
218  base_type::to_linked_list();
219  node_pointer p_out = base_type::prune(pred);
220  size_type ersd = 0;
221  while (p_out != NULL)
222    {
223      ++ersd;
224      node_pointer p_next = p_out->m_p_next_sibling;
225      base_type::actual_erase_node(p_out);
226      p_out = p_next;
227    }
228
229  node_pointer p_cur = base_type::m_p_root;
230  base_type::m_p_root = NULL;
231  while (p_cur != NULL)
232    {
233      node_pointer p_next = p_cur->m_p_next_sibling;
234      p_cur->m_p_l_child = p_cur->m_p_next_sibling = p_cur->m_p_prev_or_parent = NULL;
235
236      push_imp(p_cur);
237      p_cur = p_next;
238    }
239  _GLIBCXX_DEBUG_ONLY(assert_valid();)
240  return ersd;
241}
242
243