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