libstdc++
binary_heap_/split_join_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 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_/split_join_fn_imps.hpp
00039  * Contains an implementation class for a binary_heap.
00040  */
00041 
00042 PB_DS_CLASS_T_DEC
00043 template<typename Pred>
00044 void
00045 PB_DS_CLASS_C_DEC::
00046 split(Pred pred, PB_DS_CLASS_C_DEC& other)
00047 {
00048   PB_DS_ASSERT_VALID((*this))
00049 
00050   typedef
00051     typename entry_pred<value_type, Pred, _Alloc, simple_value>::type
00052     pred_t;
00053 
00054   const size_type left = partition(pred_t(pred));
00055   _GLIBCXX_DEBUG_ASSERT(m_size >= left);
00056 
00057   const size_type ersd = m_size - left;
00058   _GLIBCXX_DEBUG_ASSERT(m_size >= ersd);
00059 
00060   const size_type new_size = resize_policy::get_new_size_for_arbitrary(left);
00061   const size_type other_actual_size = other.get_new_size_for_arbitrary(ersd);
00062 
00063   entry_pointer a_entries = 0;
00064   entry_pointer a_other_entries = 0;
00065 
00066   __try
00067     {
00068       a_entries = s_entry_allocator.allocate(new_size);
00069       a_other_entries = s_entry_allocator.allocate(other_actual_size);
00070     }
00071   __catch(...)
00072     {
00073       if (a_entries != 0)
00074     s_entry_allocator.deallocate(a_entries, new_size);
00075 
00076       if (a_other_entries != 0)
00077     s_entry_allocator.deallocate(a_other_entries, other_actual_size);
00078 
00079       __throw_exception_again;
00080     };
00081 
00082   for (size_type i = 0; i < other.m_size; ++i)
00083     erase_at(other.m_a_entries, i, s_no_throw_copies_ind);
00084 
00085   _GLIBCXX_DEBUG_ASSERT(new_size >= left);
00086   std::copy(m_a_entries, m_a_entries + left, a_entries);
00087   std::copy(m_a_entries + left, m_a_entries + m_size, a_other_entries);
00088 
00089   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00090   s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
00091 
00092   m_actual_size = new_size;
00093   other.m_actual_size = other_actual_size;
00094 
00095   m_size = left;
00096   other.m_size = ersd;
00097 
00098   m_a_entries = a_entries;
00099   other.m_a_entries = a_other_entries;
00100 
00101   make_heap();
00102   other.make_heap();
00103 
00104   resize_policy::notify_arbitrary(m_actual_size);
00105   other.notify_arbitrary(other.m_actual_size);
00106 
00107   PB_DS_ASSERT_VALID((*this))
00108   PB_DS_ASSERT_VALID(other)
00109 }
00110 
00111 PB_DS_CLASS_T_DEC
00112 inline void
00113 PB_DS_CLASS_C_DEC::
00114 join(PB_DS_CLASS_C_DEC& other)
00115 {
00116   PB_DS_ASSERT_VALID((*this))
00117   PB_DS_ASSERT_VALID(other)
00118 
00119   const size_type len = m_size + other.m_size;
00120   const size_type new_size = resize_policy::get_new_size_for_arbitrary(len);
00121 
00122   entry_pointer a_entries = 0;
00123   entry_pointer a_other_entries = 0;
00124 
00125   __try
00126     {
00127       a_entries = s_entry_allocator.allocate(new_size);
00128       a_other_entries = s_entry_allocator.allocate(resize_policy::min_size);
00129     }
00130   __catch(...)
00131     {
00132       if (a_entries != 0)
00133     s_entry_allocator.deallocate(a_entries, new_size);
00134 
00135       if (a_other_entries != 0)
00136     s_entry_allocator.deallocate(a_other_entries, resize_policy::min_size);
00137 
00138       __throw_exception_again;
00139     }
00140 
00141   std::copy(m_a_entries, m_a_entries + m_size, a_entries);
00142   std::copy(other.m_a_entries, other.m_a_entries + other.m_size,
00143         a_entries + m_size);
00144 
00145   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00146   m_a_entries = a_entries;
00147   m_size = len;
00148   m_actual_size = new_size;
00149   resize_policy::notify_arbitrary(new_size);
00150   make_heap();
00151 
00152   s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
00153   other.m_a_entries = a_other_entries;
00154   other.m_size = 0;
00155   other.m_actual_size = resize_policy::min_size;
00156   other.notify_arbitrary(resize_policy::min_size);
00157   other.make_heap();
00158   
00159   PB_DS_ASSERT_VALID((*this))
00160   PB_DS_ASSERT_VALID(other)
00161 }