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 41PB_DS_CLASS_T_DEC 42void 43PB_DS_CLASS_C_DEC:: 44clear() 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 65PB_DS_CLASS_T_DEC 66void 67PB_DS_CLASS_C_DEC:: 68erase_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 74PB_DS_CLASS_T_DEC 75void 76PB_DS_CLASS_C_DEC:: 77erase_at(entry_pointer, size_type, true_type) 78{ } 79 80PB_DS_CLASS_T_DEC 81inline void 82PB_DS_CLASS_C_DEC:: 83pop() 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 97PB_DS_CLASS_T_DEC 98template<typename Pred> 99typename PB_DS_CLASS_C_DEC::size_type 100PB_DS_CLASS_C_DEC:: 101erase_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 134PB_DS_CLASS_T_DEC 135inline void 136PB_DS_CLASS_C_DEC:: 137erase(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 157PB_DS_CLASS_T_DEC 158inline void 159PB_DS_CLASS_C_DEC:: 160resize_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 181PB_DS_CLASS_T_DEC 182template<typename Pred> 183typename PB_DS_CLASS_C_DEC::size_type 184PB_DS_CLASS_C_DEC:: 185partition(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