1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file erase_fn_imps.hpp 44169691Skan * Contains an implementation class for bin_search_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skaninline bool 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skanerase(const_key_reference r_key) 51169691Skan{ 52169691Skan node_pointer p_nd = find_imp(r_key); 53169691Skan if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type) 54169691Skan { 55169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 56169691Skan return false; 57169691Skan } 58169691Skan 59169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); 60169691Skan if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) 61169691Skan { 62169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 63169691Skan return false; 64169691Skan } 65169691Skan 66169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 67169691Skan erase_leaf(static_cast<leaf_pointer>(p_nd)); 68169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 69169691Skan return true; 70169691Skan} 71169691Skan 72169691SkanPB_DS_CLASS_T_DEC 73169691Skanvoid 74169691SkanPB_DS_CLASS_C_DEC:: 75169691Skanerase_fixup(internal_node_pointer p_nd) 76169691Skan{ 77169691Skan _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); 78169691Skan if (std::distance(p_nd->begin(), p_nd->end()) == 1) 79169691Skan { 80169691Skan node_pointer p_parent = p_nd->m_p_parent; 81169691Skan if (p_parent == m_p_head) 82169691Skan m_p_head->m_p_parent =* p_nd->begin(); 83169691Skan else 84169691Skan { 85169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); 86169691Skan node_pointer p_new_child =* p_nd->begin(); 87169691Skan static_cast<internal_node_pointer>(p_parent)->replace_child( 88169691Skan p_new_child, 89169691Skan pref_begin(p_new_child), 90169691Skan pref_end(p_new_child), 91169691Skan this); 92169691Skan } 93169691Skan (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; 94169691Skan p_nd->~internal_node(); 95169691Skan s_internal_node_allocator.deallocate(p_nd, 1); 96169691Skan 97169691Skan if (p_parent == m_p_head) 98169691Skan return; 99169691Skan 100169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); 101169691Skan p_nd = static_cast<internal_node_pointer>(p_parent); 102169691Skan } 103169691Skan 104169691Skan while (true) 105169691Skan { 106169691Skan _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); 107169691Skan p_nd->update_prefixes(this); 108169691Skan apply_update(p_nd, (node_update* )this); 109169691Skan _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);) 110169691Skan if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) 111169691Skan return; 112169691Skan 113169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == 114169691Skan pat_trie_internal_node_type); 115169691Skan 116169691Skan p_nd = static_cast<internal_node_pointer>(p_nd->m_p_parent); 117169691Skan } 118169691Skan} 119169691Skan 120169691SkanPB_DS_CLASS_T_DEC 121169691Skaninline void 122169691SkanPB_DS_CLASS_C_DEC:: 123169691Skanactual_erase_leaf(leaf_pointer p_l) 124169691Skan{ 125169691Skan _GLIBCXX_DEBUG_ASSERT(m_size > 0); 126169691Skan --m_size; 127169691Skan _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value()))); 128169691Skan p_l->~leaf(); 129169691Skan s_leaf_allocator.deallocate(p_l, 1); 130169691Skan} 131169691Skan 132169691SkanPB_DS_CLASS_T_DEC 133169691Skanvoid 134169691SkanPB_DS_CLASS_C_DEC:: 135169691Skanclear() 136169691Skan{ 137169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 138169691Skan if (empty()) 139169691Skan return; 140169691Skan 141169691Skan clear_imp(m_p_head->m_p_parent); 142169691Skan m_size = 0; 143169691Skan initialize(); 144169691Skan _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();) 145169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 146169691Skan} 147169691Skan 148169691SkanPB_DS_CLASS_T_DEC 149169691Skanvoid 150169691SkanPB_DS_CLASS_C_DEC:: 151169691Skanclear_imp(node_pointer p_nd) 152169691Skan{ 153169691Skan if (p_nd->m_type == pat_trie_internal_node_type) 154169691Skan { 155169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 156169691Skan for (typename internal_node::iterator it = 157169691Skan static_cast<internal_node_pointer>(p_nd)->begin(); 158169691Skan it != static_cast<internal_node_pointer>(p_nd)->end(); 159169691Skan ++it) 160169691Skan { 161169691Skan node_pointer p_child =* it; 162169691Skan clear_imp(p_child); 163169691Skan } 164169691Skan s_internal_node_allocator.deallocate(static_cast<internal_node_pointer>(p_nd), 1); 165169691Skan return; 166169691Skan } 167169691Skan 168169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); 169169691Skan static_cast<leaf_pointer>(p_nd)->~leaf(); 170169691Skan s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1); 171169691Skan} 172169691Skan 173169691SkanPB_DS_CLASS_T_DEC 174169691Skaninline typename PB_DS_CLASS_C_DEC::const_iterator 175169691SkanPB_DS_CLASS_C_DEC:: 176169691Skanerase(const_iterator it) 177169691Skan{ 178169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 179169691Skan 180169691Skan if (it == end()) 181169691Skan return it; 182169691Skan 183169691Skan const_iterator ret_it = it; 184169691Skan ++ret_it; 185169691Skan _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 186169691Skan erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 187169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 188169691Skan return ret_it; 189169691Skan} 190169691Skan 191169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 192169691SkanPB_DS_CLASS_T_DEC 193169691Skaninline typename PB_DS_CLASS_C_DEC::iterator 194169691SkanPB_DS_CLASS_C_DEC:: 195169691Skanerase(iterator it) 196169691Skan{ 197169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 198169691Skan 199169691Skan if (it == end()) 200169691Skan return it; 201169691Skan iterator ret_it = it; 202169691Skan ++ret_it; 203169691Skan _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 204169691Skan erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 205169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 206169691Skan return ret_it; 207169691Skan} 208169691Skan#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 209169691Skan 210169691SkanPB_DS_CLASS_T_DEC 211169691Skaninline typename PB_DS_CLASS_C_DEC::const_reverse_iterator 212169691SkanPB_DS_CLASS_C_DEC:: 213169691Skanerase(const_reverse_iterator it) 214169691Skan{ 215169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 216169691Skan 217169691Skan if (it.m_p_nd == m_p_head) 218169691Skan return it; 219169691Skan const_reverse_iterator ret_it = it; 220169691Skan ++ret_it; 221169691Skan 222169691Skan _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 223169691Skan erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 224169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 225169691Skan return ret_it; 226169691Skan} 227169691Skan 228169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 229169691SkanPB_DS_CLASS_T_DEC 230169691Skaninline typename PB_DS_CLASS_C_DEC::reverse_iterator 231169691SkanPB_DS_CLASS_C_DEC:: 232169691Skanerase(reverse_iterator it) 233169691Skan{ 234169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 235169691Skan 236169691Skan if (it.m_p_nd == m_p_head) 237169691Skan return it; 238169691Skan reverse_iterator ret_it = it; 239169691Skan ++ret_it; 240169691Skan 241169691Skan _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 242169691Skan erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 243169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 244169691Skan return ret_it; 245169691Skan} 246169691Skan#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 247169691Skan 248169691SkanPB_DS_CLASS_T_DEC 249169691Skantemplate<typename Pred> 250169691Skaninline typename PB_DS_CLASS_C_DEC::size_type 251169691SkanPB_DS_CLASS_C_DEC:: 252169691Skanerase_if(Pred pred) 253169691Skan{ 254169691Skan size_type num_ersd = 0; 255169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 256169691Skan 257169691Skan iterator it = begin(); 258169691Skan while (it != end()) 259169691Skan { 260169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 261169691Skan if (pred(*it)) 262169691Skan { 263169691Skan ++num_ersd; 264169691Skan it = erase(it); 265169691Skan } 266169691Skan else 267169691Skan ++it; 268169691Skan } 269169691Skan 270169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 271169691Skan return num_ersd; 272169691Skan} 273169691Skan 274169691SkanPB_DS_CLASS_T_DEC 275169691Skanvoid 276169691SkanPB_DS_CLASS_C_DEC:: 277169691Skanerase_leaf(leaf_pointer p_l) 278169691Skan{ 279169691Skan update_min_max_for_erased_leaf(p_l); 280169691Skan if (p_l->m_p_parent->m_type == pat_trie_head_node_type) 281169691Skan { 282169691Skan _GLIBCXX_DEBUG_ASSERT(size() == 1); 283169691Skan clear(); 284169691Skan return; 285169691Skan } 286169691Skan 287169691Skan _GLIBCXX_DEBUG_ASSERT(size() > 1); 288169691Skan _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == 289169691Skan pat_trie_internal_node_type); 290169691Skan 291169691Skan internal_node_pointer p_parent = 292169691Skan static_cast<internal_node_pointer>(p_l->m_p_parent); 293169691Skan 294169691Skan p_parent->remove_child(p_l); 295169691Skan erase_fixup(p_parent); 296169691Skan actual_erase_leaf(p_l); 297169691Skan} 298169691Skan 299169691SkanPB_DS_CLASS_T_DEC 300169691Skanvoid 301169691SkanPB_DS_CLASS_C_DEC:: 302169691Skanupdate_min_max_for_erased_leaf(leaf_pointer p_l) 303169691Skan{ 304169691Skan if (m_size == 1) 305169691Skan { 306169691Skan m_p_head->m_p_min = m_p_head; 307169691Skan m_p_head->m_p_max = m_p_head; 308169691Skan return; 309169691Skan } 310169691Skan 311169691Skan if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min)) 312169691Skan { 313169691Skan iterator it(p_l); 314169691Skan ++it; 315169691Skan m_p_head->m_p_min = it.m_p_nd; 316169691Skan return; 317169691Skan } 318169691Skan 319169691Skan if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max)) 320169691Skan { 321169691Skan iterator it(p_l); 322169691Skan --it; 323169691Skan m_p_head->m_p_max = it.m_p_nd; 324169691Skan } 325169691Skan} 326