1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file erase_fn_imps.hpp 44169691Skan * Contains an implementation class for a binary_heap. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skanvoid 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skanclear() 51169691Skan{ 52169691Skan for (size_type i = 0; i < m_size; ++i) 53169691Skan erase_at(m_a_entries, i, s_no_throw_copies_ind); 54169691Skan 55169691Skan try 56169691Skan { 57169691Skan const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0); 58169691Skan 59169691Skan entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 60169691Skan 61169691Skan resize_policy::notify_arbitrary(actual_size); 62169691Skan 63169691Skan s_entry_allocator.deallocate(m_a_entries, m_actual_size); 64169691Skan 65169691Skan m_actual_size = actual_size; 66169691Skan 67169691Skan m_a_entries = a_entries; 68169691Skan } 69169691Skan catch(...) 70169691Skan { } 71169691Skan 72169691Skan m_size = 0; 73169691Skan 74169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 75169691Skan } 76169691Skan 77169691SkanPB_DS_CLASS_T_DEC 78169691Skanvoid 79169691SkanPB_DS_CLASS_C_DEC:: 80169691Skanerase_at(entry_pointer a_entries, size_type i, false_type) 81169691Skan{ 82169691Skan a_entries[i]->~value_type(); 83169691Skan 84169691Skan s_value_allocator.deallocate(a_entries[i], 1); 85169691Skan} 86169691Skan 87169691SkanPB_DS_CLASS_T_DEC 88169691Skanvoid 89169691SkanPB_DS_CLASS_C_DEC:: 90169691Skanerase_at(entry_pointer, size_type, true_type) 91169691Skan{ } 92169691Skan 93169691SkanPB_DS_CLASS_T_DEC 94169691Skaninline void 95169691SkanPB_DS_CLASS_C_DEC:: 96169691Skanpop() 97169691Skan{ 98169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 99169691Skan _GLIBCXX_DEBUG_ASSERT(!empty()); 100169691Skan 101169691Skan erase_at(m_a_entries, 0, s_no_throw_copies_ind); 102169691Skan 103169691Skan std::pop_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 104169691Skan 105169691Skan resize_for_erase_if_needed(); 106169691Skan 107169691Skan _GLIBCXX_DEBUG_ASSERT(m_size > 0); 108169691Skan --m_size; 109169691Skan 110169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 111169691Skan } 112169691Skan 113169691SkanPB_DS_CLASS_T_DEC 114169691Skantemplate<typename Pred> 115169691Skantypename PB_DS_CLASS_C_DEC::size_type 116169691SkanPB_DS_CLASS_C_DEC:: 117169691Skanerase_if(Pred pred) 118169691Skan{ 119169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 120169691Skan 121169691Skan typedef 122169691Skan typename entry_pred< 123169691Skan value_type, 124169691Skan Pred, 125169691Skan simple_value, 126169691Skan Allocator>::type 127169691Skan pred_t; 128169691Skan 129169691Skan const size_type left = partition(pred_t(pred)); 130169691Skan 131169691Skan _GLIBCXX_DEBUG_ASSERT(m_size >= left); 132169691Skan 133169691Skan const size_type ersd = m_size - left; 134169691Skan 135169691Skan for (size_type i = left; i < m_size; ++i) 136169691Skan erase_at(m_a_entries, i, s_no_throw_copies_ind); 137169691Skan 138169691Skan try 139169691Skan { 140169691Skan const size_type actual_size = 141169691Skan resize_policy::get_new_size_for_arbitrary(left); 142169691Skan 143169691Skan entry_pointer a_entries = s_entry_allocator.allocate(actual_size); 144169691Skan 145169691Skan std::copy(m_a_entries, m_a_entries + left, a_entries); 146169691Skan 147169691Skan s_entry_allocator.deallocate(m_a_entries, m_actual_size); 148169691Skan 149169691Skan m_actual_size = actual_size; 150169691Skan 151169691Skan resize_policy::notify_arbitrary(m_actual_size); 152169691Skan } 153169691Skan catch(...) 154169691Skan { }; 155169691Skan 156169691Skan m_size = left; 157169691Skan 158169691Skan std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 159169691Skan 160169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 161169691Skan 162169691Skan return ersd; 163169691Skan} 164169691Skan 165169691SkanPB_DS_CLASS_T_DEC 166169691Skaninline void 167169691SkanPB_DS_CLASS_C_DEC:: 168169691Skanerase(point_iterator it) 169169691Skan{ 170169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 171169691Skan _GLIBCXX_DEBUG_ASSERT(!empty()); 172169691Skan 173169691Skan const size_type fix_pos = it.m_p_e - m_a_entries; 174169691Skan 175169691Skan std::swap(*it.m_p_e, m_a_entries[m_size - 1]); 176169691Skan 177169691Skan erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind); 178169691Skan 179169691Skan resize_for_erase_if_needed(); 180169691Skan 181169691Skan _GLIBCXX_DEBUG_ASSERT(m_size > 0); 182169691Skan --m_size; 183169691Skan 184169691Skan _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size); 185169691Skan 186169691Skan if (fix_pos != m_size) 187169691Skan fix(m_a_entries + fix_pos); 188169691Skan 189169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 190169691Skan } 191169691Skan 192169691SkanPB_DS_CLASS_T_DEC 193169691Skaninline void 194169691SkanPB_DS_CLASS_C_DEC:: 195169691Skanresize_for_erase_if_needed() 196169691Skan{ 197169691Skan if (!resize_policy::resize_needed_for_shrink(m_size)) 198169691Skan return; 199169691Skan 200169691Skan try 201169691Skan { 202169691Skan const size_type new_actual_size = 203169691Skan resize_policy::get_new_size_for_shrink(); 204169691Skan 205169691Skan entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); 206169691Skan 207169691Skan resize_policy::notify_shrink_resize(); 208169691Skan 209169691Skan _GLIBCXX_DEBUG_ASSERT(m_size > 0); 210169691Skan std::copy(m_a_entries, m_a_entries + m_size - 1, a_new_entries); 211169691Skan 212169691Skan s_entry_allocator.deallocate(m_a_entries, m_actual_size); 213169691Skan 214169691Skan m_actual_size = new_actual_size; 215169691Skan 216169691Skan m_a_entries = a_new_entries; 217169691Skan } 218169691Skan catch(...) 219169691Skan { } 220169691Skan} 221169691Skan 222169691SkanPB_DS_CLASS_T_DEC 223169691Skantemplate<typename Pred> 224169691Skantypename PB_DS_CLASS_C_DEC::size_type 225169691SkanPB_DS_CLASS_C_DEC:: 226169691Skanpartition(Pred pred) 227169691Skan{ 228169691Skan size_type left = 0; 229169691Skan size_type right = m_size - 1; 230169691Skan 231169691Skan while (right + 1 != left) 232169691Skan { 233169691Skan _GLIBCXX_DEBUG_ASSERT(left <= m_size); 234169691Skan 235169691Skan if (!pred(m_a_entries[left])) 236169691Skan ++left; 237169691Skan else if (pred(m_a_entries[right])) 238169691Skan --right; 239169691Skan else 240169691Skan { 241169691Skan _GLIBCXX_DEBUG_ASSERT(left < right); 242169691Skan 243169691Skan std::swap(m_a_entries[left], m_a_entries[right]); 244169691Skan 245169691Skan ++left; 246169691Skan --right; 247169691Skan } 248169691Skan } 249169691Skan 250169691Skan return left; 251169691Skan} 252169691Skan 253