libstdc++
erase_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file binary_heap_/erase_fn_imps.hpp
00038  * Contains an implementation class for a binary_heap.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 void
00043 PB_DS_CLASS_C_DEC::
00044 clear()
00045 {
00046   for (size_type i = 0; i < m_size; ++i)
00047     erase_at(m_a_entries, i, s_no_throw_copies_ind);
00048 
00049   __try
00050     {
00051       const size_type new_size = resize_policy::get_new_size_for_arbitrary(0);
00052       entry_pointer new_entries = s_entry_allocator.allocate(new_size);
00053       resize_policy::notify_arbitrary(new_size);
00054       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00055       m_actual_size = new_size;
00056       m_a_entries = new_entries;
00057     }
00058   __catch(...)
00059     { }
00060 
00061   m_size = 0;
00062   PB_DS_ASSERT_VALID((*this))
00063 }
00064 
00065 PB_DS_CLASS_T_DEC
00066 void
00067 PB_DS_CLASS_C_DEC::
00068 erase_at(entry_pointer a_entries, size_type i, false_type)
00069 {
00070   a_entries[i]->~value_type();
00071   s_value_allocator.deallocate(a_entries[i], 1);
00072 }
00073 
00074 PB_DS_CLASS_T_DEC
00075 void
00076 PB_DS_CLASS_C_DEC::
00077 erase_at(entry_pointer, size_type, true_type)
00078 { }
00079 
00080 PB_DS_CLASS_T_DEC
00081 inline void
00082 PB_DS_CLASS_C_DEC::
00083 pop()
00084 {
00085   PB_DS_ASSERT_VALID((*this))
00086   _GLIBCXX_DEBUG_ASSERT(!empty());
00087 
00088   pop_heap();
00089   erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
00090   resize_for_erase_if_needed();
00091   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
00092   --m_size;
00093 
00094   PB_DS_ASSERT_VALID((*this))
00095 }
00096 
00097 PB_DS_CLASS_T_DEC
00098 template<typename Pred>
00099 typename PB_DS_CLASS_C_DEC::size_type
00100 PB_DS_CLASS_C_DEC::
00101 erase_if(Pred pred)
00102 {
00103   PB_DS_ASSERT_VALID((*this))
00104 
00105   typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::type
00106     pred_t;
00107 
00108   const size_type left = partition(pred_t(pred));
00109   _GLIBCXX_DEBUG_ASSERT(m_size >= left);
00110   const size_type ersd = m_size - left;
00111   for (size_type i = left; i < m_size; ++i)
00112     erase_at(m_a_entries, i, s_no_throw_copies_ind);
00113 
00114   __try
00115     {
00116       const size_type new_size =
00117         resize_policy::get_new_size_for_arbitrary(left);
00118 
00119       entry_pointer new_entries = s_entry_allocator.allocate(new_size);
00120       std::copy(m_a_entries, m_a_entries + left, new_entries);
00121       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00122       m_actual_size = new_size;
00123       resize_policy::notify_arbitrary(m_actual_size);
00124     }
00125   __catch(...)
00126     { };
00127 
00128   m_size = left;
00129   make_heap();
00130   PB_DS_ASSERT_VALID((*this))
00131   return ersd;
00132 }
00133 
00134 PB_DS_CLASS_T_DEC
00135 inline void
00136 PB_DS_CLASS_C_DEC::
00137 erase(point_iterator it)
00138 {
00139   PB_DS_ASSERT_VALID((*this))
00140   _GLIBCXX_DEBUG_ASSERT(!empty());
00141 
00142   const size_type fix_pos = it.m_p_e - m_a_entries;
00143   std::swap(*it.m_p_e, m_a_entries[m_size - 1]);
00144   erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
00145   resize_for_erase_if_needed();
00146 
00147   _GLIBCXX_DEBUG_ASSERT(m_size > 0);
00148   --m_size;
00149   _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size);
00150 
00151   if (fix_pos != m_size)
00152     fix(m_a_entries + fix_pos);
00153 
00154   PB_DS_ASSERT_VALID((*this))
00155 }
00156 
00157 PB_DS_CLASS_T_DEC
00158 inline void
00159 PB_DS_CLASS_C_DEC::
00160 resize_for_erase_if_needed()
00161 {
00162   if (!resize_policy::resize_needed_for_shrink(m_size))
00163     return;
00164 
00165   __try
00166     {
00167       const size_type new_size = resize_policy::get_new_size_for_shrink();
00168       entry_pointer new_entries = s_entry_allocator.allocate(new_size);
00169       resize_policy::notify_shrink_resize();
00170 
00171       _GLIBCXX_DEBUG_ASSERT(m_size > 0);
00172       std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries);
00173       s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00174       m_actual_size = new_size;
00175       m_a_entries = new_entries;
00176     }
00177   __catch(...)
00178     { }
00179 }
00180 
00181 PB_DS_CLASS_T_DEC
00182 template<typename Pred>
00183 typename PB_DS_CLASS_C_DEC::size_type
00184 PB_DS_CLASS_C_DEC::
00185 partition(Pred pred)
00186 {
00187   size_type left = 0;
00188   size_type right = m_size - 1;
00189 
00190   while (right + 1 != left)
00191     {
00192       _GLIBCXX_DEBUG_ASSERT(left <= m_size);
00193 
00194       if (!pred(m_a_entries[left]))
00195         ++left;
00196       else if (pred(m_a_entries[right]))
00197         --right;
00198       else
00199         {
00200           _GLIBCXX_DEBUG_ASSERT(left < right);
00201           std::swap(m_a_entries[left], m_a_entries[right]);
00202           ++left;
00203           --right;
00204         }
00205     }
00206 
00207   return left;
00208 }