libstdc++
pat_trie_/erase_fn_imps.hpp
Go to the documentation of this file.
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 }