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