1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2011 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the terms 8 // of the GNU General Public License as published by the Free Software 9 // Foundation; either version 3, or (at your option) any later 10 // version. 11 12 // This library is distributed in the hope that it will be useful, but 13 // WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 // General Public License for more details. 16 17 // Under Section 7 of GPL version 3, you are granted additional 18 // permissions described in the GCC Runtime Library Exception, version 19 // 3.1, as published by the Free Software Foundation. 20 21 // You should have received a copy of the GNU General Public License and 22 // a copy of the GCC Runtime Library Exception along with this program; 23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24 // <http://www.gnu.org/licenses/>. 25 26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 27 28 // Permission to use, copy, modify, sell, and distribute this software 29 // is hereby granted without fee, provided that the above copyright 30 // notice appears in all copies, and that both that copyright notice 31 // and this permission notice appear in supporting documentation. None 32 // of the above authors, nor IBM Haifa Research Laboratories, make any 33 // representation about the suitability of this software for any 34 // purpose. It is provided "as is" without express or implied 35 // warranty. 36 37 /** 38 * @file binary_heap_/erase_fn_imps.hpp 39 * Contains an implementation class for a binary_heap. 40 */ 41 42 PB_DS_CLASS_T_DEC 43 void 44 PB_DS_CLASS_C_DEC:: 45 clear() 46 { 47 for (size_type i = 0; i < m_size; ++i) 48 erase_at(m_a_entries, i, s_no_throw_copies_ind); 49 50 __try 51 { 52 const size_type new_size = resize_policy::get_new_size_for_arbitrary(0); 53 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 54 resize_policy::notify_arbitrary(new_size); 55 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 56 m_actual_size = new_size; 57 m_a_entries = new_entries; 58 } 59 __catch(...) 60 { } 61 62 m_size = 0; 63 PB_DS_ASSERT_VALID((*this)) 64 } 65 66 PB_DS_CLASS_T_DEC 67 void 68 PB_DS_CLASS_C_DEC:: 69 erase_at(entry_pointer a_entries, size_type i, false_type) 70 { 71 a_entries[i]->~value_type(); 72 s_value_allocator.deallocate(a_entries[i], 1); 73 } 74 75 PB_DS_CLASS_T_DEC 76 void 77 PB_DS_CLASS_C_DEC:: 78 erase_at(entry_pointer, size_type, true_type) 79 { } 80 81 PB_DS_CLASS_T_DEC 82 inline void 83 PB_DS_CLASS_C_DEC:: 84 pop() 85 { 86 PB_DS_ASSERT_VALID((*this)) 87 _GLIBCXX_DEBUG_ASSERT(!empty()); 88 89 pop_heap(); 90 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 91 resize_for_erase_if_needed(); 92 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 93 --m_size; 94 95 PB_DS_ASSERT_VALID((*this)) 96 } 97 98 PB_DS_CLASS_T_DEC 99 template<typename Pred> 100 typename PB_DS_CLASS_C_DEC::size_type 101 PB_DS_CLASS_C_DEC:: 102 erase_if(Pred pred) 103 { 104 PB_DS_ASSERT_VALID((*this)) 105 106 typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::type 107 pred_t; 108 109 const size_type left = partition(pred_t(pred)); 110 _GLIBCXX_DEBUG_ASSERT(m_size >= left); 111 const size_type ersd = m_size - left; 112 for (size_type i = left; i < m_size; ++i) 113 erase_at(m_a_entries, i, s_no_throw_copies_ind); 114 115 __try 116 { 117 const size_type new_size = 118 resize_policy::get_new_size_for_arbitrary(left); 119 120 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 121 std::copy(m_a_entries, m_a_entries + left, new_entries); 122 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 123 m_actual_size = new_size; 124 resize_policy::notify_arbitrary(m_actual_size); 125 } 126 __catch(...) 127 { }; 128 129 m_size = left; 130 make_heap(); 131 PB_DS_ASSERT_VALID((*this)) 132 return ersd; 133 } 134 135 PB_DS_CLASS_T_DEC 136 inline void 137 PB_DS_CLASS_C_DEC:: 138 erase(point_iterator it) 139 { 140 PB_DS_ASSERT_VALID((*this)) 141 _GLIBCXX_DEBUG_ASSERT(!empty()); 142 143 const size_type fix_pos = it.m_p_e - m_a_entries; 144 std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 145 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 146 resize_for_erase_if_needed(); 147 148 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 149 --m_size; 150 _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 151 152 if (fix_pos != m_size) 153 fix(m_a_entries + fix_pos); 154 155 PB_DS_ASSERT_VALID((*this)) 156 } 157 158 PB_DS_CLASS_T_DEC 159 inline void 160 PB_DS_CLASS_C_DEC:: 161 resize_for_erase_if_needed() 162 { 163 if (!resize_policy::resize_needed_for_shrink(m_size)) 164 return; 165 166 __try 167 { 168 const size_type new_size = resize_policy::get_new_size_for_shrink(); 169 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 170 resize_policy::notify_shrink_resize(); 171 172 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 173 std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries); 174 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 175 m_actual_size = new_size; 176 m_a_entries = new_entries; 177 } 178 __catch(...) 179 { } 180 } 181 182 PB_DS_CLASS_T_DEC 183 template<typename Pred> 184 typename PB_DS_CLASS_C_DEC::size_type 185 PB_DS_CLASS_C_DEC:: 186 partition(Pred pred) 187 { 188 size_type left = 0; 189 size_type right = m_size - 1; 190 191 while (right + 1 != left) 192 { 193 _GLIBCXX_DEBUG_ASSERT(left <= m_size); 194 195 if (!pred(m_a_entries[left])) 196 ++left; 197 else if (pred(m_a_entries[right])) 198 --right; 199 else 200 { 201 _GLIBCXX_DEBUG_ASSERT(left < right); 202 std::swap(m_a_entries[left], m_a_entries[right]); 203 ++left; 204 --right; 205 } 206 } 207 208 return left; 209 } 210
