1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 2, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file constructors_destructor_fn_imps.hpp 44 * Contains an implementation class for binary_heap_. 45 */ 46 47PB_DS_CLASS_T_DEC 48typename PB_DS_CLASS_C_DEC::entry_allocator 49PB_DS_CLASS_C_DEC::s_entry_allocator; 50 51PB_DS_CLASS_T_DEC 52typename PB_DS_CLASS_C_DEC::value_allocator 53PB_DS_CLASS_C_DEC::s_value_allocator; 54 55PB_DS_CLASS_T_DEC 56typename PB_DS_CLASS_C_DEC::no_throw_copies_t 57PB_DS_CLASS_C_DEC::s_no_throw_copies_ind; 58 59PB_DS_CLASS_T_DEC 60template<typename It> 61void 62PB_DS_CLASS_C_DEC:: 63copy_from_range(It first_it, It last_it) 64{ 65 while (first_it != last_it) 66 { 67 insert_value(*first_it, s_no_throw_copies_ind); 68 ++first_it; 69 } 70 71 std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 72 73 _GLIBCXX_DEBUG_ONLY(assert_valid();) 74} 75 76PB_DS_CLASS_T_DEC 77PB_DS_CLASS_C_DEC:: 78binary_heap_() : 79 m_size(0), 80 m_actual_size(resize_policy::min_size), 81 m_a_entries(s_entry_allocator.allocate(m_actual_size)) 82{ 83 _GLIBCXX_DEBUG_ONLY(assert_valid();) 84} 85 86PB_DS_CLASS_T_DEC 87PB_DS_CLASS_C_DEC:: 88binary_heap_(const Cmp_Fn& r_cmp_fn) : 89 entry_cmp(r_cmp_fn), 90 m_size(0), 91 m_actual_size(resize_policy::min_size), 92 m_a_entries(s_entry_allocator.allocate(m_actual_size)) 93{ 94 _GLIBCXX_DEBUG_ONLY(assert_valid();) 95} 96 97PB_DS_CLASS_T_DEC 98PB_DS_CLASS_C_DEC:: 99binary_heap_(const PB_DS_CLASS_C_DEC& other) : 100 entry_cmp(other), 101 resize_policy(other), 102 m_size(0), 103 m_actual_size(other.m_actual_size), 104 m_a_entries(s_entry_allocator.allocate(m_actual_size)) 105{ 106 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 107 _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); 108 109 const_iterator first_it = other.begin(); 110 const_iterator last_it = other.end(); 111 112 try 113 { 114 while (first_it != last_it) 115 { 116 insert_value(*first_it, s_no_throw_copies_ind); 117 ++first_it; 118 } 119 } 120 catch(...) 121 { 122 for (size_type i = 0; i < m_size; ++i) 123 erase_at(m_a_entries, i, s_no_throw_copies_ind); 124 125 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 126 __throw_exception_again; 127 } 128 _GLIBCXX_DEBUG_ONLY(assert_valid();) 129} 130 131PB_DS_CLASS_T_DEC 132void 133PB_DS_CLASS_C_DEC:: 134swap(PB_DS_CLASS_C_DEC& other) 135{ 136 _GLIBCXX_DEBUG_ONLY(assert_valid();) 137 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 138 _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries); 139 140 value_swap(other); 141 std::swap((entry_cmp& )(*this), (entry_cmp& )other); 142 _GLIBCXX_DEBUG_ONLY(assert_valid();) 143 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 144} 145 146PB_DS_CLASS_T_DEC 147void 148PB_DS_CLASS_C_DEC:: 149value_swap(PB_DS_CLASS_C_DEC& other) 150{ 151 std::swap(m_a_entries, other.m_a_entries); 152 std::swap(m_size, other.m_size); 153 std::swap(m_actual_size, other.m_actual_size); 154 static_cast<resize_policy*>(this)->swap(other); 155} 156 157PB_DS_CLASS_T_DEC 158PB_DS_CLASS_C_DEC:: 159~binary_heap_() 160{ 161 for (size_type i = 0; i < m_size; ++i) 162 erase_at(m_a_entries, i, s_no_throw_copies_ind); 163 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 164} 165 166