]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
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 bin_search_tree_. | |
45 | */ | |
46 | ||
47 | PB_DS_CLASS_T_DEC | |
48 | inline bool | |
49 | PB_DS_CLASS_C_DEC:: | |
50 | erase(const_key_reference r_key) | |
51 | { | |
52 | node_pointer p_nd = find_imp(r_key); | |
53 | ||
54 | if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type) | |
55 | { | |
56 | PB_DS_DBG_ONLY(map_debug_base::check_key_does_not_exist( | |
57 | r_key)); | |
58 | ||
59 | return (false); | |
60 | } | |
61 | ||
62 | PB_DS_DBG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); | |
63 | ||
64 | if (!synth_e_access_traits::equal_keys( | |
65 | PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), | |
66 | r_key)) | |
67 | { | |
68 | PB_DS_DBG_ONLY(map_debug_base::check_key_does_not_exist( | |
69 | r_key)); | |
70 | ||
71 | return (false); | |
72 | } | |
73 | ||
74 | PB_DS_DBG_ONLY(map_debug_base::check_key_exists(r_key)); | |
75 | ||
76 | erase_leaf(static_cast<leaf_pointer>(p_nd)); | |
77 | ||
78 | PB_DS_DBG_ONLY(assert_valid();) | |
79 | ||
80 | return (true); | |
81 | } | |
82 | ||
83 | PB_DS_CLASS_T_DEC | |
84 | void | |
85 | PB_DS_CLASS_C_DEC:: | |
86 | erase_fixup(internal_node_pointer p_nd) | |
87 | { | |
88 | PB_DS_DBG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); | |
89 | ||
90 | if (std::distance(p_nd->begin(), p_nd->end()) == 1) | |
91 | { | |
92 | node_pointer p_parent = p_nd->m_p_parent; | |
93 | ||
94 | if (p_parent == m_p_head) | |
95 | m_p_head->m_p_parent =* p_nd->begin(); | |
96 | else | |
97 | { | |
98 | PB_DS_DBG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); | |
99 | ||
100 | node_pointer p_new_child =* p_nd->begin(); | |
101 | ||
102 | static_cast<internal_node_pointer>(p_parent)->replace_child( | |
103 | p_new_child, | |
104 | pref_begin(p_new_child), | |
105 | pref_end(p_new_child), | |
106 | this); | |
107 | } | |
108 | (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; | |
109 | ||
110 | p_nd->~internal_node(); | |
111 | ||
112 | s_internal_node_allocator.deallocate(p_nd, 1); | |
113 | ||
114 | if (p_parent == m_p_head) | |
115 | return; | |
116 | ||
117 | PB_DS_DBG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); | |
118 | ||
119 | p_nd = static_cast<internal_node_pointer>(p_parent); | |
120 | } | |
121 | ||
122 | while (true) | |
123 | { | |
124 | PB_DS_DBG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); | |
125 | ||
126 | p_nd->update_prefixes(this); | |
127 | ||
128 | apply_update(p_nd, (node_update* )this); | |
129 | ||
130 | PB_DS_DBG_ONLY(p_nd->assert_valid(this);) | |
131 | ||
132 | if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) | |
133 | return; | |
134 | ||
135 | PB_DS_DBG_ASSERT(p_nd->m_p_parent->m_type == | |
136 | pat_trie_internal_node_type); | |
137 | ||
138 | p_nd = static_cast<internal_node_pointer>(p_nd->m_p_parent); | |
139 | } | |
140 | } | |
141 | ||
142 | PB_DS_CLASS_T_DEC | |
143 | inline void | |
144 | PB_DS_CLASS_C_DEC:: | |
145 | actual_erase_leaf(leaf_pointer p_l) | |
146 | { | |
147 | PB_DS_DBG_ASSERT(m_size > 0); | |
148 | --m_size; | |
149 | ||
150 | PB_DS_DBG_ONLY(erase_existing(PB_DS_V2F(p_l->value()))); | |
151 | ||
152 | p_l->~leaf(); | |
153 | ||
154 | s_leaf_allocator.deallocate(p_l, 1); | |
155 | } | |
156 | ||
157 | PB_DS_CLASS_T_DEC | |
158 | void | |
159 | PB_DS_CLASS_C_DEC:: | |
160 | clear() | |
161 | { | |
162 | PB_DS_DBG_ONLY(assert_valid();) | |
163 | ||
164 | if (empty()) | |
165 | return; | |
166 | ||
167 | clear_imp(m_p_head->m_p_parent); | |
168 | ||
169 | m_size = 0; | |
170 | ||
171 | initialize(); | |
172 | ||
173 | PB_DS_DBG_ONLY(map_debug_base::clear();) | |
174 | ||
175 | PB_DS_DBG_ONLY(assert_valid();) | |
176 | } | |
177 | ||
178 | PB_DS_CLASS_T_DEC | |
179 | void | |
180 | PB_DS_CLASS_C_DEC:: | |
181 | clear_imp(node_pointer p_nd) | |
182 | { | |
183 | if (p_nd->m_type == pat_trie_internal_node_type) | |
184 | { | |
185 | PB_DS_DBG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); | |
186 | ||
187 | for (typename internal_node::iterator it = | |
188 | static_cast<internal_node_pointer>(p_nd)->begin(); | |
189 | it != static_cast<internal_node_pointer>(p_nd)->end(); | |
190 | ++it) | |
191 | { | |
192 | node_pointer p_child =* it; | |
193 | ||
194 | clear_imp(p_child); | |
195 | } | |
196 | ||
197 | s_internal_node_allocator.deallocate( | |
198 | static_cast<internal_node_pointer>(p_nd), 1); | |
199 | ||
200 | return; | |
201 | } | |
202 | ||
203 | PB_DS_DBG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); | |
204 | ||
205 | static_cast<leaf_pointer>(p_nd)->~leaf(); | |
206 | ||
207 | s_leaf_allocator.deallocate( | |
208 | static_cast<leaf_pointer>(p_nd), 1); | |
209 | } | |
210 | ||
211 | PB_DS_CLASS_T_DEC | |
212 | inline typename PB_DS_CLASS_C_DEC::const_iterator | |
213 | PB_DS_CLASS_C_DEC:: | |
214 | erase(const_iterator it) | |
215 | { | |
216 | PB_DS_DBG_ONLY(assert_valid()); | |
217 | ||
218 | if (it == end()) | |
219 | return (it); | |
220 | ||
221 | const_iterator ret_it = it; | |
222 | ||
223 | ++ret_it; | |
224 | ||
225 | PB_DS_DBG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); | |
226 | ||
227 | erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); | |
228 | ||
229 | PB_DS_DBG_ONLY(assert_valid()); | |
230 | ||
231 | return (ret_it); | |
232 | } | |
233 | ||
234 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
235 | PB_DS_CLASS_T_DEC | |
236 | inline typename PB_DS_CLASS_C_DEC::iterator | |
237 | PB_DS_CLASS_C_DEC:: | |
238 | erase(iterator it) | |
239 | { | |
240 | PB_DS_DBG_ONLY(assert_valid()); | |
241 | ||
242 | if (it == end()) | |
243 | return (it); | |
244 | ||
245 | iterator ret_it = it; | |
246 | ||
247 | ++ret_it; | |
248 | ||
249 | PB_DS_DBG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); | |
250 | ||
251 | erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); | |
252 | ||
253 | PB_DS_DBG_ONLY(assert_valid()); | |
254 | ||
255 | return (ret_it); | |
256 | } | |
257 | #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR | |
258 | ||
259 | PB_DS_CLASS_T_DEC | |
260 | inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator | |
261 | PB_DS_CLASS_C_DEC:: | |
262 | erase(const_reverse_iterator it) | |
263 | { | |
264 | PB_DS_DBG_ONLY(assert_valid()); | |
265 | ||
266 | if (it.m_p_nd == m_p_head) | |
267 | return (it); | |
268 | ||
269 | const_reverse_iterator ret_it = it; | |
270 | ||
271 | ++ret_it; | |
272 | ||
273 | PB_DS_DBG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); | |
274 | ||
275 | erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); | |
276 | ||
277 | PB_DS_DBG_ONLY(assert_valid()); | |
278 | ||
279 | return (ret_it); | |
280 | } | |
281 | ||
282 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
283 | PB_DS_CLASS_T_DEC | |
284 | inline typename PB_DS_CLASS_C_DEC::reverse_iterator | |
285 | PB_DS_CLASS_C_DEC:: | |
286 | erase(reverse_iterator it) | |
287 | { | |
288 | PB_DS_DBG_ONLY(assert_valid()); | |
289 | ||
290 | if (it.m_p_nd == m_p_head) | |
291 | return (it); | |
292 | ||
293 | reverse_iterator ret_it = it; | |
294 | ||
295 | ++ret_it; | |
296 | ||
297 | PB_DS_DBG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); | |
298 | ||
299 | erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); | |
300 | ||
301 | PB_DS_DBG_ONLY(assert_valid()); | |
302 | ||
303 | return (ret_it); | |
304 | } | |
305 | #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR | |
306 | ||
307 | PB_DS_CLASS_T_DEC | |
308 | template<typename Pred> | |
309 | inline typename PB_DS_CLASS_C_DEC::size_type | |
310 | PB_DS_CLASS_C_DEC:: | |
311 | erase_if(Pred pred) | |
312 | { | |
313 | size_type num_ersd = 0; | |
314 | ||
315 | PB_DS_DBG_ONLY(assert_valid();) | |
316 | ||
317 | iterator it = begin(); | |
318 | ||
319 | while (it != end()) | |
320 | { | |
321 | PB_DS_DBG_ONLY(assert_valid();) | |
322 | ||
323 | if (pred(*it)) | |
324 | { | |
325 | ++num_ersd; | |
326 | ||
327 | it = erase(it); | |
328 | } | |
329 | else | |
330 | ++it; | |
331 | } | |
332 | ||
333 | PB_DS_DBG_ONLY(assert_valid();) | |
334 | ||
335 | return (num_ersd); | |
336 | } | |
337 | ||
338 | PB_DS_CLASS_T_DEC | |
339 | void | |
340 | PB_DS_CLASS_C_DEC:: | |
341 | erase_leaf(leaf_pointer p_l) | |
342 | { | |
343 | update_min_max_for_erased_leaf(p_l); | |
344 | ||
345 | if (p_l->m_p_parent->m_type == pat_trie_head_node_type) | |
346 | { | |
347 | PB_DS_DBG_ASSERT(size() == 1); | |
348 | ||
349 | clear(); | |
350 | ||
351 | return; | |
352 | } | |
353 | ||
354 | PB_DS_DBG_ASSERT(size() > 1); | |
355 | ||
356 | PB_DS_DBG_ASSERT(p_l->m_p_parent->m_type == | |
357 | pat_trie_internal_node_type); | |
358 | ||
359 | internal_node_pointer p_parent = | |
360 | static_cast<internal_node_pointer>(p_l->m_p_parent); | |
361 | ||
362 | p_parent->remove_child(p_l); | |
363 | ||
364 | erase_fixup(p_parent); | |
365 | ||
366 | actual_erase_leaf(p_l); | |
367 | } | |
368 | ||
369 | PB_DS_CLASS_T_DEC | |
370 | void | |
371 | PB_DS_CLASS_C_DEC:: | |
372 | update_min_max_for_erased_leaf(leaf_pointer p_l) | |
373 | { | |
374 | if (m_size == 1) | |
375 | { | |
376 | m_p_head->m_p_min = m_p_head; | |
377 | m_p_head->m_p_max = m_p_head; | |
378 | ||
379 | return; | |
380 | } | |
381 | ||
382 | if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min)) | |
383 | { | |
384 | iterator it(p_l); | |
385 | ||
386 | ++it; | |
387 | ||
388 | m_p_head->m_p_min = it.m_p_nd; | |
389 | ||
390 | return; | |
391 | } | |
392 | ||
393 | if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max)) | |
394 | { | |
395 | iterator it(p_l); | |
396 | ||
397 | --it; | |
398 | ||
399 | m_p_head->m_p_max = it.m_p_nd; | |
400 | } | |
401 | } |