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