libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file pat_trie_/erase_fn_imps.hpp 00038 * Contains an implementation class for pat_trie. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 inline bool 00043 PB_DS_CLASS_C_DEC:: 00044 erase(key_const_reference r_key) 00045 { 00046 node_pointer p_nd = find_imp(r_key); 00047 if (p_nd == 0 || p_nd->m_type == i_node) 00048 { 00049 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 00050 return false; 00051 } 00052 00053 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); 00054 if (!synth_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) 00055 { 00056 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 00057 return false; 00058 } 00059 00060 PB_DS_CHECK_KEY_EXISTS(r_key) 00061 erase_leaf(static_cast<leaf_pointer>(p_nd)); 00062 PB_DS_ASSERT_VALID((*this)) 00063 return true; 00064 } 00065 00066 PB_DS_CLASS_T_DEC 00067 void 00068 PB_DS_CLASS_C_DEC:: 00069 erase_fixup(inode_pointer p_nd) 00070 { 00071 _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); 00072 if (std::distance(p_nd->begin(), p_nd->end()) == 1) 00073 { 00074 node_pointer p_parent = p_nd->m_p_parent; 00075 if (p_parent == m_p_head) 00076 m_p_head->m_p_parent = *p_nd->begin(); 00077 else 00078 { 00079 _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == i_node); 00080 node_pointer p_new_child = *p_nd->begin(); 00081 00082 typedef inode_pointer inode_ptr; 00083 inode_ptr p_internal = static_cast<inode_ptr>(p_parent); 00084 p_internal->replace_child(p_new_child, pref_begin(p_new_child), 00085 pref_end(p_new_child), this); 00086 } 00087 (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; 00088 p_nd->~inode(); 00089 s_inode_allocator.deallocate(p_nd, 1); 00090 00091 if (p_parent == m_p_head) 00092 return; 00093 00094 _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == i_node); 00095 p_nd = static_cast<inode_pointer>(p_parent); 00096 } 00097 00098 while (true) 00099 { 00100 _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); 00101 p_nd->update_prefixes(this); 00102 apply_update(p_nd, (node_update*)this); 00103 PB_DS_ASSERT_NODE_VALID(p_nd) 00104 if (p_nd->m_p_parent->m_type == head_node) 00105 return; 00106 00107 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == i_node); 00108 00109 p_nd = static_cast<inode_pointer>(p_nd->m_p_parent); 00110 } 00111 } 00112 00113 PB_DS_CLASS_T_DEC 00114 inline void 00115 PB_DS_CLASS_C_DEC:: 00116 actual_erase_leaf(leaf_pointer p_l) 00117 { 00118 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00119 --m_size; 00120 _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(p_l->value()))); 00121 p_l->~leaf(); 00122 s_leaf_allocator.deallocate(p_l, 1); 00123 } 00124 00125 PB_DS_CLASS_T_DEC 00126 void 00127 PB_DS_CLASS_C_DEC:: 00128 clear() 00129 { 00130 if (!empty()) 00131 { 00132 clear_imp(m_p_head->m_p_parent); 00133 m_size = 0; 00134 initialize(); 00135 _GLIBCXX_DEBUG_ONLY(debug_base::clear();) 00136 PB_DS_ASSERT_VALID((*this)) 00137 } 00138 } 00139 00140 PB_DS_CLASS_T_DEC 00141 void 00142 PB_DS_CLASS_C_DEC:: 00143 clear_imp(node_pointer p_nd) 00144 { 00145 if (p_nd->m_type == i_node) 00146 { 00147 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 00148 for (typename inode::iterator it = 00149 static_cast<inode_pointer>(p_nd)->begin(); 00150 it != static_cast<inode_pointer>(p_nd)->end(); 00151 ++it) 00152 { 00153 node_pointer p_child =* it; 00154 clear_imp(p_child); 00155 } 00156 s_inode_allocator.deallocate(static_cast<inode_pointer>(p_nd), 1); 00157 return; 00158 } 00159 00160 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); 00161 static_cast<leaf_pointer>(p_nd)->~leaf(); 00162 s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1); 00163 } 00164 00165 PB_DS_CLASS_T_DEC 00166 inline typename PB_DS_CLASS_C_DEC::const_iterator 00167 PB_DS_CLASS_C_DEC:: 00168 erase(const_iterator it) 00169 { 00170 PB_DS_ASSERT_VALID((*this)) 00171 00172 if (it == end()) 00173 return it; 00174 00175 const_iterator ret_it = it; 00176 ++ret_it; 00177 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 00178 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 00179 PB_DS_ASSERT_VALID((*this)) 00180 return ret_it; 00181 } 00182 00183 #ifdef PB_DS_DATA_TRUE_INDICATOR 00184 PB_DS_CLASS_T_DEC 00185 inline typename PB_DS_CLASS_C_DEC::iterator 00186 PB_DS_CLASS_C_DEC:: 00187 erase(iterator it) 00188 { 00189 PB_DS_ASSERT_VALID((*this)) 00190 00191 if (it == end()) 00192 return it; 00193 iterator ret_it = it; 00194 ++ret_it; 00195 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 00196 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 00197 PB_DS_ASSERT_VALID((*this)) 00198 return ret_it; 00199 } 00200 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 00201 00202 PB_DS_CLASS_T_DEC 00203 inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator 00204 PB_DS_CLASS_C_DEC:: 00205 erase(const_reverse_iterator it) 00206 { 00207 PB_DS_ASSERT_VALID((*this)) 00208 00209 if (it.m_p_nd == m_p_head) 00210 return it; 00211 const_reverse_iterator ret_it = it; 00212 ++ret_it; 00213 00214 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 00215 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 00216 PB_DS_ASSERT_VALID((*this)) 00217 return ret_it; 00218 } 00219 00220 #ifdef PB_DS_DATA_TRUE_INDICATOR 00221 PB_DS_CLASS_T_DEC 00222 inline typename PB_DS_CLASS_C_DEC::reverse_iterator 00223 PB_DS_CLASS_C_DEC:: 00224 erase(reverse_iterator it) 00225 { 00226 PB_DS_ASSERT_VALID((*this)) 00227 00228 if (it.m_p_nd == m_p_head) 00229 return it; 00230 reverse_iterator ret_it = it; 00231 ++ret_it; 00232 00233 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 00234 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 00235 PB_DS_ASSERT_VALID((*this)) 00236 return ret_it; 00237 } 00238 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 00239 00240 PB_DS_CLASS_T_DEC 00241 template<typename Pred> 00242 inline typename PB_DS_CLASS_C_DEC::size_type 00243 PB_DS_CLASS_C_DEC:: 00244 erase_if(Pred pred) 00245 { 00246 size_type num_ersd = 0; 00247 PB_DS_ASSERT_VALID((*this)) 00248 00249 iterator it = begin(); 00250 while (it != end()) 00251 { 00252 PB_DS_ASSERT_VALID((*this)) 00253 if (pred(*it)) 00254 { 00255 ++num_ersd; 00256 it = erase(it); 00257 } 00258 else 00259 ++it; 00260 } 00261 00262 PB_DS_ASSERT_VALID((*this)) 00263 return num_ersd; 00264 } 00265 00266 PB_DS_CLASS_T_DEC 00267 void 00268 PB_DS_CLASS_C_DEC:: 00269 erase_leaf(leaf_pointer p_l) 00270 { 00271 update_min_max_for_erased_leaf(p_l); 00272 if (p_l->m_p_parent->m_type == head_node) 00273 { 00274 _GLIBCXX_DEBUG_ASSERT(size() == 1); 00275 clear(); 00276 return; 00277 } 00278 00279 _GLIBCXX_DEBUG_ASSERT(size() > 1); 00280 _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == i_node); 00281 00282 inode_pointer p_parent = static_cast<inode_pointer>(p_l->m_p_parent); 00283 00284 p_parent->remove_child(p_l); 00285 erase_fixup(p_parent); 00286 actual_erase_leaf(p_l); 00287 } 00288 00289 PB_DS_CLASS_T_DEC 00290 void 00291 PB_DS_CLASS_C_DEC:: 00292 update_min_max_for_erased_leaf(leaf_pointer p_l) 00293 { 00294 if (m_size == 1) 00295 { 00296 m_p_head->m_p_min = m_p_head; 00297 m_p_head->m_p_max = m_p_head; 00298 return; 00299 } 00300 00301 if (p_l == static_cast<leaf_const_pointer>(m_p_head->m_p_min)) 00302 { 00303 iterator it(p_l); 00304 ++it; 00305 m_p_head->m_p_min = it.m_p_nd; 00306 return; 00307 } 00308 00309 if (p_l == static_cast<leaf_const_pointer>(m_p_head->m_p_max)) 00310 { 00311 iterator it(p_l); 00312 --it; 00313 m_p_head->m_p_max = it.m_p_nd; 00314 } 00315 }