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 splay_tree_/erase_fn_imps.hpp 00038 * Contains an implementation class for splay_tree_. 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 point_iterator it = find(r_key); 00047 if (it == base_type::end()) 00048 return false; 00049 erase(it); 00050 return true; 00051 } 00052 00053 PB_DS_CLASS_T_DEC 00054 inline typename PB_DS_CLASS_C_DEC::iterator 00055 PB_DS_CLASS_C_DEC:: 00056 erase(iterator it) 00057 { 00058 PB_DS_ASSERT_VALID((*this)) 00059 if (it == base_type::end()) 00060 return it; 00061 iterator ret_it = it; 00062 ++ret_it; 00063 erase_node(it.m_p_nd); 00064 PB_DS_ASSERT_VALID((*this)) 00065 return ret_it; 00066 } 00067 00068 PB_DS_CLASS_T_DEC 00069 inline typename PB_DS_CLASS_C_DEC::reverse_iterator 00070 PB_DS_CLASS_C_DEC:: 00071 erase(reverse_iterator it) 00072 { 00073 PB_DS_ASSERT_VALID((*this)) 00074 if (it.m_p_nd == base_type::m_p_head) 00075 return (it); 00076 reverse_iterator ret_it = it; 00077 ++ret_it; 00078 erase_node(it.m_p_nd); 00079 PB_DS_ASSERT_VALID((*this)) 00080 return ret_it; 00081 } 00082 00083 PB_DS_CLASS_T_DEC 00084 template<typename Pred> 00085 inline typename PB_DS_CLASS_C_DEC::size_type 00086 PB_DS_CLASS_C_DEC:: 00087 erase_if(Pred pred) 00088 { 00089 PB_DS_ASSERT_VALID((*this)) 00090 size_type num_ersd = 0; 00091 iterator it = base_type::begin(); 00092 while (it != base_type::end()) 00093 { 00094 if (pred(*it)) 00095 { 00096 ++num_ersd; 00097 it = erase(it); 00098 } 00099 else 00100 ++it; 00101 } 00102 PB_DS_ASSERT_VALID((*this)) 00103 return num_ersd; 00104 } 00105 00106 PB_DS_CLASS_T_DEC 00107 void 00108 PB_DS_CLASS_C_DEC:: 00109 erase_node(node_pointer p_nd) 00110 { 00111 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 00112 splay(p_nd); 00113 00114 PB_DS_ASSERT_VALID((*this)) 00115 _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); 00116 00117 node_pointer p_l = p_nd->m_p_left; 00118 node_pointer p_r = p_nd->m_p_right; 00119 00120 base_type::update_min_max_for_erased_node(p_nd); 00121 base_type::actual_erase_node(p_nd); 00122 if (p_r == 0) 00123 { 00124 base_type::m_p_head->m_p_parent = p_l; 00125 if (p_l != 0) 00126 p_l->m_p_parent = base_type::m_p_head; 00127 PB_DS_ASSERT_VALID((*this)) 00128 return; 00129 } 00130 00131 node_pointer p_target_r = leftmost(p_r); 00132 _GLIBCXX_DEBUG_ASSERT(p_target_r != 0); 00133 p_r->m_p_parent = base_type::m_p_head; 00134 base_type::m_p_head->m_p_parent = p_r; 00135 splay(p_target_r); 00136 00137 _GLIBCXX_DEBUG_ONLY(p_target_r->m_p_left = 0); 00138 _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_parent == this->m_p_head); 00139 _GLIBCXX_DEBUG_ASSERT(this->m_p_head->m_p_parent == p_target_r); 00140 00141 p_target_r->m_p_left = p_l; 00142 if (p_l != 0) 00143 p_l->m_p_parent = p_target_r; 00144 PB_DS_ASSERT_VALID((*this)) 00145 this->apply_update(p_target_r, (node_update*)this); 00146 } 00147 00148 PB_DS_CLASS_T_DEC 00149 inline typename PB_DS_CLASS_C_DEC::node_pointer 00150 PB_DS_CLASS_C_DEC:: 00151 leftmost(node_pointer p_nd) 00152 { 00153 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 00154 while (p_nd->m_p_left != 0) 00155 p_nd = p_nd->m_p_left; 00156 return p_nd; 00157 }