libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2013 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 binary_heap_/erase_fn_imps.hpp 00038 * Contains an implementation class for a binary_heap. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 void 00043 PB_DS_CLASS_C_DEC:: 00044 clear() 00045 { 00046 for (size_type i = 0; i < m_size; ++i) 00047 erase_at(m_a_entries, i, s_no_throw_copies_ind); 00048 00049 __try 00050 { 00051 const size_type new_size = resize_policy::get_new_size_for_arbitrary(0); 00052 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 00053 resize_policy::notify_arbitrary(new_size); 00054 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00055 m_actual_size = new_size; 00056 m_a_entries = new_entries; 00057 } 00058 __catch(...) 00059 { } 00060 00061 m_size = 0; 00062 PB_DS_ASSERT_VALID((*this)) 00063 } 00064 00065 PB_DS_CLASS_T_DEC 00066 void 00067 PB_DS_CLASS_C_DEC:: 00068 erase_at(entry_pointer a_entries, size_type i, false_type) 00069 { 00070 a_entries[i]->~value_type(); 00071 s_value_allocator.deallocate(a_entries[i], 1); 00072 } 00073 00074 PB_DS_CLASS_T_DEC 00075 void 00076 PB_DS_CLASS_C_DEC:: 00077 erase_at(entry_pointer, size_type, true_type) 00078 { } 00079 00080 PB_DS_CLASS_T_DEC 00081 inline void 00082 PB_DS_CLASS_C_DEC:: 00083 pop() 00084 { 00085 PB_DS_ASSERT_VALID((*this)) 00086 _GLIBCXX_DEBUG_ASSERT(!empty()); 00087 00088 pop_heap(); 00089 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 00090 resize_for_erase_if_needed(); 00091 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00092 --m_size; 00093 00094 PB_DS_ASSERT_VALID((*this)) 00095 } 00096 00097 PB_DS_CLASS_T_DEC 00098 template<typename Pred> 00099 typename PB_DS_CLASS_C_DEC::size_type 00100 PB_DS_CLASS_C_DEC:: 00101 erase_if(Pred pred) 00102 { 00103 PB_DS_ASSERT_VALID((*this)) 00104 00105 typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::type 00106 pred_t; 00107 00108 const size_type left = partition(pred_t(pred)); 00109 _GLIBCXX_DEBUG_ASSERT(m_size >= left); 00110 const size_type ersd = m_size - left; 00111 for (size_type i = left; i < m_size; ++i) 00112 erase_at(m_a_entries, i, s_no_throw_copies_ind); 00113 00114 __try 00115 { 00116 const size_type new_size = 00117 resize_policy::get_new_size_for_arbitrary(left); 00118 00119 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 00120 std::copy(m_a_entries, m_a_entries + left, new_entries); 00121 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00122 m_actual_size = new_size; 00123 resize_policy::notify_arbitrary(m_actual_size); 00124 } 00125 __catch(...) 00126 { }; 00127 00128 m_size = left; 00129 make_heap(); 00130 PB_DS_ASSERT_VALID((*this)) 00131 return ersd; 00132 } 00133 00134 PB_DS_CLASS_T_DEC 00135 inline void 00136 PB_DS_CLASS_C_DEC:: 00137 erase(point_iterator it) 00138 { 00139 PB_DS_ASSERT_VALID((*this)) 00140 _GLIBCXX_DEBUG_ASSERT(!empty()); 00141 00142 const size_type fix_pos = it.m_p_e - m_a_entries; 00143 std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 00144 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 00145 resize_for_erase_if_needed(); 00146 00147 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00148 --m_size; 00149 _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 00150 00151 if (fix_pos != m_size) 00152 fix(m_a_entries + fix_pos); 00153 00154 PB_DS_ASSERT_VALID((*this)) 00155 } 00156 00157 PB_DS_CLASS_T_DEC 00158 inline void 00159 PB_DS_CLASS_C_DEC:: 00160 resize_for_erase_if_needed() 00161 { 00162 if (!resize_policy::resize_needed_for_shrink(m_size)) 00163 return; 00164 00165 __try 00166 { 00167 const size_type new_size = resize_policy::get_new_size_for_shrink(); 00168 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 00169 resize_policy::notify_shrink_resize(); 00170 00171 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00172 std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries); 00173 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00174 m_actual_size = new_size; 00175 m_a_entries = new_entries; 00176 } 00177 __catch(...) 00178 { } 00179 } 00180 00181 PB_DS_CLASS_T_DEC 00182 template<typename Pred> 00183 typename PB_DS_CLASS_C_DEC::size_type 00184 PB_DS_CLASS_C_DEC:: 00185 partition(Pred pred) 00186 { 00187 size_type left = 0; 00188 size_type right = m_size - 1; 00189 00190 while (right + 1 != left) 00191 { 00192 _GLIBCXX_DEBUG_ASSERT(left <= m_size); 00193 00194 if (!pred(m_a_entries[left])) 00195 ++left; 00196 else if (pred(m_a_entries[right])) 00197 --right; 00198 else 00199 { 00200 _GLIBCXX_DEBUG_ASSERT(left < right); 00201 std::swap(m_a_entries[left], m_a_entries[right]); 00202 ++left; 00203 --right; 00204 } 00205 } 00206 00207 return left; 00208 }