]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2005-2022 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 thin_heap_/erase_fn_imps.hpp |
4569a895 AT |
38 | * Contains an implementation for thin_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 FD |
48 | PB_DS_ASSERT_VALID((*this)) |
49 | _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); | |
8fc81078 | 50 | _GLIBCXX_DEBUG_ASSERT(m_p_max != 0); |
4569a895 AT |
51 | |
52 | node_pointer p_nd = m_p_max; | |
4569a895 | 53 | remove_max_node(); |
4569a895 | 54 | base_type::actual_erase_node(p_nd); |
f5886803 FD |
55 | PB_DS_ASSERT_VALID((*this)) |
56 | } | |
4569a895 AT |
57 | |
58 | PB_DS_CLASS_T_DEC | |
59 | inline void | |
60 | PB_DS_CLASS_C_DEC:: | |
61 | remove_max_node() | |
62 | { | |
63 | to_aux_except_max(); | |
4569a895 AT |
64 | make_from_aux(); |
65 | } | |
66 | ||
67 | PB_DS_CLASS_T_DEC | |
68 | void | |
69 | PB_DS_CLASS_C_DEC:: | |
70 | to_aux_except_max() | |
71 | { | |
72 | node_pointer p_add = base_type::m_p_root; | |
4569a895 AT |
73 | while (p_add != m_p_max) |
74 | { | |
75 | node_pointer p_next_add = p_add->m_p_next_sibling; | |
4569a895 | 76 | add_to_aux(p_add); |
4569a895 AT |
77 | p_add = p_next_add; |
78 | } | |
79 | ||
80 | p_add = m_p_max->m_p_l_child; | |
8fc81078 | 81 | while (p_add != 0) |
4569a895 AT |
82 | { |
83 | node_pointer p_next_add = p_add->m_p_next_sibling; | |
a345e45d BK |
84 | p_add->m_metadata = p_add->m_p_l_child == 0 ? |
85 | 0 : p_add->m_p_l_child->m_metadata + 1; | |
4569a895 AT |
86 | |
87 | add_to_aux(p_add); | |
4569a895 AT |
88 | p_add = p_next_add; |
89 | } | |
90 | ||
91 | p_add = m_p_max->m_p_next_sibling; | |
8fc81078 | 92 | while (p_add != 0) |
4569a895 AT |
93 | { |
94 | node_pointer p_next_add = p_add->m_p_next_sibling; | |
4569a895 | 95 | add_to_aux(p_add); |
4569a895 AT |
96 | p_add = p_next_add; |
97 | } | |
98 | } | |
99 | ||
100 | PB_DS_CLASS_T_DEC | |
101 | inline void | |
102 | PB_DS_CLASS_C_DEC:: | |
103 | add_to_aux(node_pointer p_nd) | |
104 | { | |
105 | size_type r = p_nd->m_metadata; | |
8fc81078 | 106 | while (m_a_aux[r] != 0) |
4569a895 | 107 | { |
47bea7b8 | 108 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); |
4569a895 AT |
109 | if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value)) |
110 | make_child_of(m_a_aux[r], p_nd); | |
111 | else | |
a345e45d | 112 | { |
4569a895 | 113 | make_child_of(p_nd, m_a_aux[r]); |
4569a895 | 114 | p_nd = m_a_aux[r]; |
a345e45d | 115 | } |
4569a895 | 116 | |
8fc81078 | 117 | m_a_aux[r] = 0; |
4569a895 AT |
118 | ++r; |
119 | } | |
120 | ||
47bea7b8 | 121 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); |
4569a895 AT |
122 | |
123 | m_a_aux[r] = p_nd; | |
124 | } | |
125 | ||
126 | PB_DS_CLASS_T_DEC | |
127 | inline void | |
128 | PB_DS_CLASS_C_DEC:: | |
129 | make_child_of(node_pointer p_nd, node_pointer p_new_parent) | |
130 | { | |
47bea7b8 BK |
131 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata); |
132 | _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd || | |
4569a895 AT |
133 | m_a_aux[p_nd->m_metadata] == p_new_parent); |
134 | ||
135 | ++p_new_parent->m_metadata; | |
4569a895 AT |
136 | base_type::make_child_of(p_nd, p_new_parent); |
137 | } | |
138 | ||
139 | PB_DS_CLASS_T_DEC | |
140 | inline void | |
141 | PB_DS_CLASS_C_DEC:: | |
142 | make_from_aux() | |
143 | { | |
8fc81078 | 144 | base_type::m_p_root = m_p_max = 0; |
4569a895 | 145 | const size_type rnk_bnd = rank_bound(); |
4569a895 | 146 | size_type i = 0; |
4569a895 AT |
147 | while (i < rnk_bnd) |
148 | { | |
8fc81078 | 149 | if (m_a_aux[i] != 0) |
a345e45d | 150 | { |
4569a895 | 151 | make_root_and_link(m_a_aux[i]); |
8fc81078 | 152 | m_a_aux[i] = 0; |
a345e45d | 153 | } |
4569a895 AT |
154 | ++i; |
155 | } | |
156 | ||
f5886803 FD |
157 | PB_DS_ASSERT_AUX_NULL((*this)) |
158 | } | |
4569a895 AT |
159 | |
160 | PB_DS_CLASS_T_DEC | |
161 | inline void | |
162 | PB_DS_CLASS_C_DEC:: | |
163 | remove_node(node_pointer p_nd) | |
164 | { | |
165 | node_pointer p_parent = p_nd; | |
8fc81078 | 166 | while (base_type::parent(p_parent) != 0) |
4569a895 AT |
167 | p_parent = base_type::parent(p_parent); |
168 | ||
169 | base_type::bubble_to_top(p_nd); | |
4569a895 AT |
170 | m_p_max = p_nd; |
171 | ||
172 | node_pointer p_fix = base_type::m_p_root; | |
8fc81078 | 173 | while (p_fix != 0&& p_fix->m_p_next_sibling != p_parent) |
4569a895 AT |
174 | p_fix = p_fix->m_p_next_sibling; |
175 | ||
8fc81078 | 176 | if (p_fix != 0) |
4569a895 AT |
177 | p_fix->m_p_next_sibling = p_nd; |
178 | ||
179 | remove_max_node(); | |
180 | } | |
181 | ||
182 | PB_DS_CLASS_T_DEC | |
183 | inline void | |
184 | PB_DS_CLASS_C_DEC:: | |
185 | clear() | |
186 | { | |
187 | base_type::clear(); | |
8fc81078 | 188 | m_p_max = 0; |
4569a895 AT |
189 | } |
190 | ||
191 | PB_DS_CLASS_T_DEC | |
192 | void | |
193 | PB_DS_CLASS_C_DEC:: | |
194 | erase(point_iterator it) | |
195 | { | |
f5886803 FD |
196 | PB_DS_ASSERT_VALID((*this)) |
197 | _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); | |
4569a895 AT |
198 | |
199 | node_pointer p_nd = it.m_p_nd; | |
4569a895 | 200 | remove_node(p_nd); |
4569a895 | 201 | base_type::actual_erase_node(p_nd); |
f5886803 FD |
202 | PB_DS_ASSERT_VALID((*this)) |
203 | } | |
4569a895 AT |
204 | |
205 | PB_DS_CLASS_T_DEC | |
206 | template<typename Pred> | |
207 | typename PB_DS_CLASS_C_DEC::size_type | |
208 | PB_DS_CLASS_C_DEC:: | |
209 | erase_if(Pred pred) | |
210 | { | |
f5886803 | 211 | PB_DS_ASSERT_VALID((*this)) |
f5886803 FD |
212 | if (base_type::empty()) |
213 | { | |
214 | PB_DS_ASSERT_VALID((*this)) | |
f5886803 FD |
215 | return 0; |
216 | } | |
4569a895 AT |
217 | |
218 | base_type::to_linked_list(); | |
4569a895 | 219 | node_pointer p_out = base_type::prune(pred); |
4569a895 | 220 | size_type ersd = 0; |
8fc81078 | 221 | while (p_out != 0) |
4569a895 AT |
222 | { |
223 | ++ersd; | |
4569a895 | 224 | node_pointer p_next = p_out->m_p_next_sibling; |
4569a895 | 225 | base_type::actual_erase_node(p_out); |
4569a895 AT |
226 | p_out = p_next; |
227 | } | |
228 | ||
229 | node_pointer p_cur = base_type::m_p_root; | |
8fc81078 | 230 | m_p_max = base_type::m_p_root = 0; |
8fc81078 | 231 | while (p_cur != 0) |
4569a895 AT |
232 | { |
233 | node_pointer p_next = p_cur->m_p_next_sibling; | |
4569a895 | 234 | make_root_and_link(p_cur); |
4569a895 AT |
235 | p_cur = p_next; |
236 | } | |
237 | ||
f5886803 | 238 | PB_DS_ASSERT_VALID((*this)) |
f5886803 | 239 | return ersd; |
4569a895 AT |
240 | } |
241 | ||
242 | PB_DS_CLASS_T_DEC | |
243 | inline typename PB_DS_CLASS_C_DEC::size_type | |
244 | PB_DS_CLASS_C_DEC:: | |
245 | rank_bound() | |
246 | { | |
f5886803 FD |
247 | using namespace std; |
248 | const size_t* const p_upper = | |
e330aa5b PC |
249 | std::upper_bound(g_a_rank_bounds, |
250 | g_a_rank_bounds + num_distinct_rank_bounds, | |
251 | base_type::m_size); | |
4569a895 AT |
252 | |
253 | if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds) | |
254 | return max_rank; | |
255 | ||
256 | return (p_upper - g_a_rank_bounds); | |
257 | } | |
574dfb67 | 258 | #endif |