libstdc++
|
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_/constructors_destructor_fn_imps.hpp 00038 * Contains an implementation class for binary_heap_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 typename PB_DS_CLASS_C_DEC::entry_allocator 00043 PB_DS_CLASS_C_DEC::s_entry_allocator; 00044 00045 PB_DS_CLASS_T_DEC 00046 typename PB_DS_CLASS_C_DEC::value_allocator 00047 PB_DS_CLASS_C_DEC::s_value_allocator; 00048 00049 PB_DS_CLASS_T_DEC 00050 typename PB_DS_CLASS_C_DEC::no_throw_copies_t 00051 PB_DS_CLASS_C_DEC::s_no_throw_copies_ind; 00052 00053 PB_DS_CLASS_T_DEC 00054 template<typename It> 00055 void 00056 PB_DS_CLASS_C_DEC:: 00057 copy_from_range(It first_it, It last_it) 00058 { 00059 while (first_it != last_it) 00060 { 00061 insert_value(*first_it, s_no_throw_copies_ind); 00062 ++first_it; 00063 } 00064 make_heap(); 00065 PB_DS_ASSERT_VALID((*this)) 00066 } 00067 00068 PB_DS_CLASS_T_DEC 00069 PB_DS_CLASS_C_DEC:: 00070 binary_heap() 00071 : m_size(0), m_actual_size(resize_policy::min_size), 00072 m_a_entries(s_entry_allocator.allocate(m_actual_size)) 00073 { PB_DS_ASSERT_VALID((*this)) } 00074 00075 PB_DS_CLASS_T_DEC 00076 PB_DS_CLASS_C_DEC:: 00077 binary_heap(const Cmp_Fn& r_cmp_fn) 00078 : entry_cmp(r_cmp_fn), m_size(0), m_actual_size(resize_policy::min_size), 00079 m_a_entries(s_entry_allocator.allocate(m_actual_size)) 00080 { PB_DS_ASSERT_VALID((*this)) } 00081 00082 PB_DS_CLASS_T_DEC 00083 PB_DS_CLASS_C_DEC:: 00084 binary_heap(const PB_DS_CLASS_C_DEC& other) 00085 : entry_cmp(other), resize_policy(other), m_size(0), 00086 m_actual_size(other.m_actual_size), 00087 m_a_entries(s_entry_allocator.allocate(m_actual_size)) 00088 { 00089 PB_DS_ASSERT_VALID(other) 00090 _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); 00091 00092 __try 00093 { 00094 copy_from_range(other.begin(), other.end()); 00095 } 00096 __catch(...) 00097 { 00098 for (size_type i = 0; i < m_size; ++i) 00099 erase_at(m_a_entries, i, s_no_throw_copies_ind); 00100 00101 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00102 __throw_exception_again; 00103 } 00104 PB_DS_ASSERT_VALID((*this)) 00105 } 00106 00107 PB_DS_CLASS_T_DEC 00108 void 00109 PB_DS_CLASS_C_DEC:: 00110 swap(PB_DS_CLASS_C_DEC& other) 00111 { 00112 PB_DS_ASSERT_VALID((*this)) 00113 PB_DS_ASSERT_VALID(other) 00114 _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); 00115 value_swap(other); 00116 std::swap((entry_cmp&)(*this), (entry_cmp&)other); 00117 PB_DS_ASSERT_VALID((*this)) 00118 PB_DS_ASSERT_VALID(other) 00119 } 00120 00121 PB_DS_CLASS_T_DEC 00122 void 00123 PB_DS_CLASS_C_DEC:: 00124 value_swap(PB_DS_CLASS_C_DEC& other) 00125 { 00126 std::swap(m_a_entries, other.m_a_entries); 00127 std::swap(m_size, other.m_size); 00128 std::swap(m_actual_size, other.m_actual_size); 00129 static_cast<resize_policy*>(this)->swap(other); 00130 } 00131 00132 PB_DS_CLASS_T_DEC 00133 PB_DS_CLASS_C_DEC:: 00134 ~binary_heap() 00135 { 00136 for (size_type i = 0; i < m_size; ++i) 00137 erase_at(m_a_entries, i, s_no_throw_copies_ind); 00138 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 00139 }