libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2011 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the terms 00008 // of the GNU General Public License as published by the Free Software 00009 // Foundation; either version 3, or (at your option) any later 00010 // version. 00011 00012 // This library is distributed in the hope that it will be useful, but 00013 // WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 // General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00027 00028 // Permission to use, copy, modify, sell, and distribute this software 00029 // is hereby granted without fee, provided that the above copyright 00030 // notice appears in all copies, and that both that copyright notice 00031 // and this permission notice appear in supporting documentation. None 00032 // of the above authors, nor IBM Haifa Research Laboratories, make any 00033 // representation about the suitability of this software for any 00034 // purpose. It is provided "as is" without express or implied 00035 // warranty. 00036 00037 /** 00038 * @file binary_heap_/erase_fn_imps.hpp 00039 * Contains an implementation class for a binary_heap. 00040 */ 00041 00042 PB_DS_CLASS_T_DEC 00043 void 00044 PB_DS_CLASS_C_DEC:: 00045 clear() 00046 { 00047 for (size_type i = 0; i < m_size; ++i) 00048 erase_at(m_a_entries, i, s_no_throw_copies_ind); 00049 00050 __try 00051 { 00052 const size_type new_size = resize_policy::get_new_size_for_arbitrary(0); 00053 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 00054 resize_policy::notify_arbitrary(new_size); 00055 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00056 m_actual_size = new_size; 00057 m_a_entries = new_entries; 00058 } 00059 __catch(...) 00060 { } 00061 00062 m_size = 0; 00063 PB_DS_ASSERT_VALID((*this)) 00064 } 00065 00066 PB_DS_CLASS_T_DEC 00067 void 00068 PB_DS_CLASS_C_DEC:: 00069 erase_at(entry_pointer a_entries, size_type i, false_type) 00070 { 00071 a_entries[i]->~value_type(); 00072 s_value_allocator.deallocate(a_entries[i], 1); 00073 } 00074 00075 PB_DS_CLASS_T_DEC 00076 void 00077 PB_DS_CLASS_C_DEC:: 00078 erase_at(entry_pointer, size_type, true_type) 00079 { } 00080 00081 PB_DS_CLASS_T_DEC 00082 inline void 00083 PB_DS_CLASS_C_DEC:: 00084 pop() 00085 { 00086 PB_DS_ASSERT_VALID((*this)) 00087 _GLIBCXX_DEBUG_ASSERT(!empty()); 00088 00089 pop_heap(); 00090 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 00091 resize_for_erase_if_needed(); 00092 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00093 --m_size; 00094 00095 PB_DS_ASSERT_VALID((*this)) 00096 } 00097 00098 PB_DS_CLASS_T_DEC 00099 template<typename Pred> 00100 typename PB_DS_CLASS_C_DEC::size_type 00101 PB_DS_CLASS_C_DEC:: 00102 erase_if(Pred pred) 00103 { 00104 PB_DS_ASSERT_VALID((*this)) 00105 00106 typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::type 00107 pred_t; 00108 00109 const size_type left = partition(pred_t(pred)); 00110 _GLIBCXX_DEBUG_ASSERT(m_size >= left); 00111 const size_type ersd = m_size - left; 00112 for (size_type i = left; i < m_size; ++i) 00113 erase_at(m_a_entries, i, s_no_throw_copies_ind); 00114 00115 __try 00116 { 00117 const size_type new_size = 00118 resize_policy::get_new_size_for_arbitrary(left); 00119 00120 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 00121 std::copy(m_a_entries, m_a_entries + left, new_entries); 00122 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00123 m_actual_size = new_size; 00124 resize_policy::notify_arbitrary(m_actual_size); 00125 } 00126 __catch(...) 00127 { }; 00128 00129 m_size = left; 00130 make_heap(); 00131 PB_DS_ASSERT_VALID((*this)) 00132 return ersd; 00133 } 00134 00135 PB_DS_CLASS_T_DEC 00136 inline void 00137 PB_DS_CLASS_C_DEC:: 00138 erase(point_iterator it) 00139 { 00140 PB_DS_ASSERT_VALID((*this)) 00141 _GLIBCXX_DEBUG_ASSERT(!empty()); 00142 00143 const size_type fix_pos = it.m_p_e - m_a_entries; 00144 std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 00145 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 00146 resize_for_erase_if_needed(); 00147 00148 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00149 --m_size; 00150 _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 00151 00152 if (fix_pos != m_size) 00153 fix(m_a_entries + fix_pos); 00154 00155 PB_DS_ASSERT_VALID((*this)) 00156 } 00157 00158 PB_DS_CLASS_T_DEC 00159 inline void 00160 PB_DS_CLASS_C_DEC:: 00161 resize_for_erase_if_needed() 00162 { 00163 if (!resize_policy::resize_needed_for_shrink(m_size)) 00164 return; 00165 00166 __try 00167 { 00168 const size_type new_size = resize_policy::get_new_size_for_shrink(); 00169 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 00170 resize_policy::notify_shrink_resize(); 00171 00172 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00173 std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries); 00174 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00175 m_actual_size = new_size; 00176 m_a_entries = new_entries; 00177 } 00178 __catch(...) 00179 { } 00180 } 00181 00182 PB_DS_CLASS_T_DEC 00183 template<typename Pred> 00184 typename PB_DS_CLASS_C_DEC::size_type 00185 PB_DS_CLASS_C_DEC:: 00186 partition(Pred pred) 00187 { 00188 size_type left = 0; 00189 size_type right = m_size - 1; 00190 00191 while (right + 1 != left) 00192 { 00193 _GLIBCXX_DEBUG_ASSERT(left <= m_size); 00194 00195 if (!pred(m_a_entries[left])) 00196 ++left; 00197 else if (pred(m_a_entries[right])) 00198 --right; 00199 else 00200 { 00201 _GLIBCXX_DEBUG_ASSERT(left < right); 00202 std::swap(m_a_entries[left], m_a_entries[right]); 00203 ++left; 00204 --right; 00205 } 00206 } 00207 00208 return left; 00209 }