1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file erase_fn_imps.hpp 44 * Contains an implementation class for a binary_heap. 45 */ 46 47PB_DS_CLASS_T_DEC 48void 49PB_DS_CLASS_C_DEC:: 50clear() 51{ 52 for (size_type i = 0; i < m_size; ++i) 53 erase_at(m_a_entries, i, s_no_throw_copies_ind); 54 55 try 56 { 57 const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0); 58 59 entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 60 61 resize_policy::notify_arbitrary(actual_size); 62 63 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 64 65 m_actual_size = actual_size; 66 67 m_a_entries = a_entries; 68 } 69 catch(...) 70 { } 71 72 m_size = 0; 73 74 _GLIBCXX_DEBUG_ONLY(assert_valid();) 75 } 76 77PB_DS_CLASS_T_DEC 78void 79PB_DS_CLASS_C_DEC:: 80erase_at(entry_pointer a_entries, size_type i, false_type) 81{ 82 a_entries[i]->~value_type(); 83 84 s_value_allocator.deallocate(a_entries[i], 1); 85} 86 87PB_DS_CLASS_T_DEC 88void 89PB_DS_CLASS_C_DEC:: 90erase_at(entry_pointer, size_type, true_type) 91{ } 92 93PB_DS_CLASS_T_DEC 94inline void 95PB_DS_CLASS_C_DEC:: 96pop() 97{ 98 _GLIBCXX_DEBUG_ONLY(assert_valid();) 99 _GLIBCXX_DEBUG_ASSERT(!empty()); 100 101 erase_at(m_a_entries, 0, s_no_throw_copies_ind); 102 103 std::pop_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 104 105 resize_for_erase_if_needed(); 106 107 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 108 --m_size; 109 110 _GLIBCXX_DEBUG_ONLY(assert_valid();) 111 } 112 113PB_DS_CLASS_T_DEC 114template<typename Pred> 115typename PB_DS_CLASS_C_DEC::size_type 116PB_DS_CLASS_C_DEC:: 117erase_if(Pred pred) 118{ 119 _GLIBCXX_DEBUG_ONLY(assert_valid();) 120 121 typedef 122 typename entry_pred< 123 value_type, 124 Pred, 125 simple_value, 126 Allocator>::type 127 pred_t; 128 129 const size_type left = partition(pred_t(pred)); 130 131 _GLIBCXX_DEBUG_ASSERT(m_size >= left); 132 133 const size_type ersd = m_size - left; 134 135 for (size_type i = left; i < m_size; ++i) 136 erase_at(m_a_entries, i, s_no_throw_copies_ind); 137 138 try 139 { 140 const size_type actual_size = 141 resize_policy::get_new_size_for_arbitrary(left); 142 143 entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 144 145 std::copy(m_a_entries, m_a_entries + left, a_entries); 146 147 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 148 149 m_actual_size = actual_size; 150 151 resize_policy::notify_arbitrary(m_actual_size); 152 } 153 catch(...) 154 { }; 155 156 m_size = left; 157 158 std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 159 160 _GLIBCXX_DEBUG_ONLY(assert_valid();) 161 162 return ersd; 163} 164 165PB_DS_CLASS_T_DEC 166inline void 167PB_DS_CLASS_C_DEC:: 168erase(point_iterator it) 169{ 170 _GLIBCXX_DEBUG_ONLY(assert_valid();) 171 _GLIBCXX_DEBUG_ASSERT(!empty()); 172 173 const size_type fix_pos = it.m_p_e - m_a_entries; 174 175 std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 176 177 erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 178 179 resize_for_erase_if_needed(); 180 181 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 182 --m_size; 183 184 _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 185 186 if (fix_pos != m_size) 187 fix(m_a_entries + fix_pos); 188 189 _GLIBCXX_DEBUG_ONLY(assert_valid();) 190 } 191 192PB_DS_CLASS_T_DEC 193inline void 194PB_DS_CLASS_C_DEC:: 195resize_for_erase_if_needed() 196{ 197 if (!resize_policy::resize_needed_for_shrink(m_size)) 198 return; 199 200 try 201 { 202 const size_type new_actual_size = 203 resize_policy::get_new_size_for_shrink(); 204 205 entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); 206 207 resize_policy::notify_shrink_resize(); 208 209 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 210 std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries); 211 212 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 213 214 m_actual_size = new_actual_size; 215 216 m_a_entries = a_new_entries; 217 } 218 catch(...) 219 { } 220} 221 222PB_DS_CLASS_T_DEC 223template<typename Pred> 224typename PB_DS_CLASS_C_DEC::size_type 225PB_DS_CLASS_C_DEC:: 226partition(Pred pred) 227{ 228 size_type left = 0; 229 size_type right = m_size - 1; 230 231 while (right + 1 != left) 232 { 233 _GLIBCXX_DEBUG_ASSERT(left <= m_size); 234 235 if (!pred(m_a_entries[left])) 236 ++left; 237 else if (pred(m_a_entries[right])) 238 --right; 239 else 240 { 241 _GLIBCXX_DEBUG_ASSERT(left < right); 242 243 std::swap(m_a_entries[left], m_a_entries[right]); 244 245 ++left; 246 --right; 247 } 248 } 249 250 return left; 251} 252 253