]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
83ffe9cd | 3 | // Copyright (C) 2005-2023 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 | /** | |
a345e45d | 37 | * @file pairing_heap_/erase_fn_imps.hpp |
4569a895 AT |
38 | * Contains an implementation class for a pairing heap. |
39 | */ | |
40 | ||
574dfb67 JW |
41 | #ifdef PB_DS_CLASS_C_DEC |
42 | ||
4569a895 AT |
43 | PB_DS_CLASS_T_DEC |
44 | void | |
45 | PB_DS_CLASS_C_DEC:: | |
46 | pop() | |
47 | { | |
f5886803 | 48 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 49 | _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); |
4569a895 AT |
50 | |
51 | node_pointer p_new_root = join_node_children(base_type::m_p_root); | |
f5886803 | 52 | PB_DS_ASSERT_NODE_CONSISTENT(p_new_root, false) |
8fc81078 PC |
53 | if (p_new_root != 0) |
54 | p_new_root->m_p_prev_or_parent = 0; | |
4569a895 AT |
55 | |
56 | base_type::actual_erase_node(base_type::m_p_root); | |
4569a895 | 57 | base_type::m_p_root = p_new_root; |
f5886803 | 58 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 59 | } |
4569a895 AT |
60 | |
61 | PB_DS_CLASS_T_DEC | |
62 | void | |
63 | PB_DS_CLASS_C_DEC:: | |
64 | erase(point_iterator it) | |
65 | { | |
f5886803 | 66 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 67 | _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); |
4569a895 | 68 | remove_node(it.m_p_nd); |
4569a895 | 69 | base_type::actual_erase_node(it.m_p_nd); |
f5886803 | 70 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 71 | } |
4569a895 AT |
72 | |
73 | PB_DS_CLASS_T_DEC | |
74 | void | |
75 | PB_DS_CLASS_C_DEC:: | |
76 | remove_node(node_pointer p_nd) | |
77 | { | |
f5886803 | 78 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 79 | _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); |
4569a895 AT |
80 | node_pointer p_new_child = join_node_children(p_nd); |
81 | ||
f5886803 | 82 | PB_DS_ASSERT_NODE_CONSISTENT(p_new_child, false) |
4569a895 AT |
83 | |
84 | if (p_nd == base_type::m_p_root) | |
85 | { | |
8fc81078 PC |
86 | if (p_new_child != 0) |
87 | p_new_child->m_p_prev_or_parent = 0; | |
4569a895 | 88 | base_type::m_p_root = p_new_child; |
f5886803 | 89 | PB_DS_ASSERT_NODE_CONSISTENT(base_type::m_p_root, false) |
47bea7b8 | 90 | return; |
4569a895 AT |
91 | } |
92 | ||
8fc81078 | 93 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_prev_or_parent != 0); |
4569a895 AT |
94 | if (p_nd->m_p_prev_or_parent->m_p_l_child == p_nd) |
95 | { | |
8fc81078 | 96 | if (p_new_child != 0) |
4569a895 AT |
97 | { |
98 | p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; | |
4569a895 | 99 | p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling; |
8fc81078 | 100 | if (p_new_child->m_p_next_sibling != 0) |
4569a895 | 101 | p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child; |
4569a895 | 102 | p_nd->m_p_prev_or_parent->m_p_l_child = p_new_child; |
f5886803 | 103 | PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) |
47bea7b8 | 104 | return; |
4569a895 AT |
105 | } |
106 | ||
107 | p_nd->m_p_prev_or_parent->m_p_l_child = p_nd->m_p_next_sibling; | |
8fc81078 | 108 | if (p_nd->m_p_next_sibling != 0) |
4569a895 | 109 | p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; |
f5886803 | 110 | PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) |
47bea7b8 | 111 | return; |
4569a895 AT |
112 | } |
113 | ||
8fc81078 | 114 | if (p_new_child != 0) |
4569a895 AT |
115 | { |
116 | p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; | |
4569a895 | 117 | p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling; |
8fc81078 | 118 | if (p_new_child->m_p_next_sibling != 0) |
4569a895 | 119 | p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child; |
4569a895 | 120 | p_new_child->m_p_prev_or_parent->m_p_next_sibling = p_new_child; |
f5886803 | 121 | PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) |
47bea7b8 | 122 | return; |
4569a895 AT |
123 | } |
124 | ||
125 | p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling; | |
8fc81078 | 126 | if (p_nd->m_p_next_sibling != 0) |
4569a895 | 127 | p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; |
f5886803 | 128 | PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) |
47bea7b8 | 129 | } |
4569a895 AT |
130 | |
131 | PB_DS_CLASS_T_DEC | |
132 | typename PB_DS_CLASS_C_DEC::node_pointer | |
133 | PB_DS_CLASS_C_DEC:: | |
134 | join_node_children(node_pointer p_nd) | |
135 | { | |
8fc81078 | 136 | _GLIBCXX_DEBUG_ASSERT(p_nd != 0); |
4569a895 | 137 | node_pointer p_ret = p_nd->m_p_l_child; |
8fc81078 PC |
138 | if (p_ret == 0) |
139 | return 0; | |
140 | while (p_ret->m_p_next_sibling != 0) | |
4569a895 | 141 | p_ret = forward_join(p_ret, p_ret->m_p_next_sibling); |
4569a895 AT |
142 | while (p_ret->m_p_prev_or_parent != p_nd) |
143 | p_ret = back_join(p_ret->m_p_prev_or_parent, p_ret); | |
f5886803 | 144 | PB_DS_ASSERT_NODE_CONSISTENT(p_ret, false) |
47bea7b8 | 145 | return p_ret; |
4569a895 AT |
146 | } |
147 | ||
148 | PB_DS_CLASS_T_DEC | |
149 | typename PB_DS_CLASS_C_DEC::node_pointer | |
150 | PB_DS_CLASS_C_DEC:: | |
151 | forward_join(node_pointer p_nd, node_pointer p_next) | |
152 | { | |
8fc81078 | 153 | _GLIBCXX_DEBUG_ASSERT(p_nd != 0); |
47bea7b8 | 154 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling == p_next); |
4569a895 AT |
155 | if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) |
156 | { | |
157 | p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; | |
4569a895 | 158 | base_type::make_child_of(p_nd, p_next); |
8fc81078 | 159 | return p_next->m_p_next_sibling == 0 |
47bea7b8 | 160 | ? p_next : p_next->m_p_next_sibling; |
4569a895 AT |
161 | } |
162 | ||
8fc81078 | 163 | if (p_next->m_p_next_sibling != 0) |
4569a895 AT |
164 | { |
165 | p_next->m_p_next_sibling->m_p_prev_or_parent = p_nd; | |
4569a895 | 166 | p_nd->m_p_next_sibling = p_next->m_p_next_sibling; |
4569a895 | 167 | base_type::make_child_of(p_next, p_nd); |
4569a895 AT |
168 | return p_nd->m_p_next_sibling; |
169 | } | |
170 | ||
8fc81078 | 171 | p_nd->m_p_next_sibling = 0; |
4569a895 | 172 | base_type::make_child_of(p_next, p_nd); |
f5886803 | 173 | PB_DS_ASSERT_NODE_CONSISTENT(p_nd, false) |
4569a895 AT |
174 | return p_nd; |
175 | } | |
176 | ||
177 | PB_DS_CLASS_T_DEC | |
178 | typename PB_DS_CLASS_C_DEC::node_pointer | |
179 | PB_DS_CLASS_C_DEC:: | |
180 | back_join(node_pointer p_nd, node_pointer p_next) | |
181 | { | |
8fc81078 PC |
182 | _GLIBCXX_DEBUG_ASSERT(p_nd != 0); |
183 | _GLIBCXX_DEBUG_ASSERT(p_next->m_p_next_sibling == 0); | |
4569a895 AT |
184 | |
185 | if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) | |
186 | { | |
187 | p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; | |
4569a895 | 188 | base_type::make_child_of(p_nd, p_next); |
f5886803 | 189 | PB_DS_ASSERT_NODE_CONSISTENT(p_next, false) |
4569a895 AT |
190 | return p_next; |
191 | } | |
192 | ||
8fc81078 | 193 | p_nd->m_p_next_sibling = 0; |
4569a895 | 194 | base_type::make_child_of(p_next, p_nd); |
f5886803 | 195 | PB_DS_ASSERT_NODE_CONSISTENT(p_nd, false) |
4569a895 AT |
196 | return p_nd; |
197 | } | |
198 | ||
199 | PB_DS_CLASS_T_DEC | |
200 | template<typename Pred> | |
201 | typename PB_DS_CLASS_C_DEC::size_type | |
202 | PB_DS_CLASS_C_DEC:: | |
203 | erase_if(Pred pred) | |
204 | { | |
f5886803 | 205 | PB_DS_ASSERT_VALID((*this)) |
4569a895 AT |
206 | if (base_type::empty()) |
207 | { | |
f5886803 | 208 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 209 | return 0; |
4569a895 | 210 | } |
4569a895 | 211 | base_type::to_linked_list(); |
4569a895 | 212 | node_pointer p_out = base_type::prune(pred); |
4569a895 | 213 | size_type ersd = 0; |
8fc81078 | 214 | while (p_out != 0) |
4569a895 AT |
215 | { |
216 | ++ersd; | |
4569a895 | 217 | node_pointer p_next = p_out->m_p_next_sibling; |
4569a895 | 218 | base_type::actual_erase_node(p_out); |
4569a895 AT |
219 | p_out = p_next; |
220 | } | |
221 | ||
222 | node_pointer p_cur = base_type::m_p_root; | |
8fc81078 PC |
223 | base_type::m_p_root = 0; |
224 | while (p_cur != 0) | |
4569a895 AT |
225 | { |
226 | node_pointer p_next = p_cur->m_p_next_sibling; | |
8fc81078 | 227 | p_cur->m_p_l_child = p_cur->m_p_next_sibling = p_cur->m_p_prev_or_parent = 0; |
4569a895 AT |
228 | |
229 | push_imp(p_cur); | |
4569a895 AT |
230 | p_cur = p_next; |
231 | } | |
f5886803 | 232 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 233 | return ersd; |
4569a895 AT |
234 | } |
235 | ||
574dfb67 | 236 | #endif |