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 insert_fn_imps.hpp 44 * Contains an implementation class for a binary_heap. 45 */ 46 47PB_DS_CLASS_T_DEC 48inline typename PB_DS_CLASS_C_DEC::point_iterator 49PB_DS_CLASS_C_DEC:: 50push(const_reference r_val) 51{ 52 _GLIBCXX_DEBUG_ONLY(assert_valid();) 53 54 insert_value(r_val, s_no_throw_copies_ind); 55 56 std::push_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this)); 57 58 _GLIBCXX_DEBUG_ONLY(assert_valid();) 59 60 return point_iterator(m_a_entries); 61} 62 63PB_DS_CLASS_T_DEC 64inline void 65PB_DS_CLASS_C_DEC:: 66insert_value(value_type val, true_type) 67{ 68 resize_for_insert_if_needed(); 69 70 m_a_entries[m_size++] = val; 71} 72 73PB_DS_CLASS_T_DEC 74inline void 75PB_DS_CLASS_C_DEC:: 76insert_value(const_reference r_val, false_type) 77{ 78 resize_for_insert_if_needed(); 79 80 pointer p_new = s_value_allocator.allocate(1); 81 82 cond_dealtor_t cond(p_new); 83 84 new (p_new) value_type(r_val); 85 86 cond.set_no_action(); 87 88 m_a_entries[m_size++] = p_new; 89} 90 91PB_DS_CLASS_T_DEC 92inline void 93PB_DS_CLASS_C_DEC:: 94insert_entry(entry e) 95{ 96 resize_for_insert_if_needed(); 97 98 m_a_entries[m_size++] = e; 99} 100 101PB_DS_CLASS_T_DEC 102inline void 103PB_DS_CLASS_C_DEC:: 104resize_for_insert_if_needed() 105{ 106 if (!resize_policy::resize_needed_for_grow(m_size)) 107 { 108 _GLIBCXX_DEBUG_ASSERT(m_size < m_actual_size); 109 110 return; 111 } 112 113 const size_type new_actual_size = 114 resize_policy::get_new_size_for_grow(); 115 116 entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size); 117 118 resize_policy::notify_grow_resize(); 119 120 std::copy(m_a_entries, m_a_entries + m_size, a_new_entries); 121 122 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 123 124 m_actual_size = new_actual_size; 125 126 m_a_entries = a_new_entries; 127} 128 129PB_DS_CLASS_T_DEC 130void 131PB_DS_CLASS_C_DEC:: 132modify(point_iterator it, const_reference r_new_val) 133{ 134 _GLIBCXX_DEBUG_ONLY(assert_valid();) 135 136 swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind); 137 138 fix(it.m_p_e); 139 140 _GLIBCXX_DEBUG_ONLY(assert_valid();) 141 } 142 143PB_DS_CLASS_T_DEC 144void 145PB_DS_CLASS_C_DEC:: 146fix(entry_pointer p_e) 147{ 148 size_type i = p_e - m_a_entries; 149 150 if (i > 0&& entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i])) 151 { 152 size_type parent_i = parent(i); 153 154 while (i > 0&& entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i])) 155 { 156 std::swap(m_a_entries[i], m_a_entries[parent_i]); 157 158 i = parent_i; 159 160 parent_i = parent(i); 161 } 162 163 _GLIBCXX_DEBUG_ONLY(assert_valid();) 164 165 return; 166 } 167 168 while (i < m_size) 169 { 170 const size_type left_child_i = left_child(i); 171 const size_type right_child_i = right_child(i); 172 173 _GLIBCXX_DEBUG_ASSERT(right_child_i > left_child_i); 174 175 const bool smaller_than_left_child = 176 left_child_i < m_size&& 177 entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child_i]); 178 179 const bool smaller_than_right_child = 180 right_child_i < m_size&& 181 entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child_i]); 182 183 const bool swap_with_r_child = smaller_than_right_child&& (!smaller_than_left_child || 184 entry_cmp::operator()(m_a_entries[left_child_i], m_a_entries[right_child_i])); 185 186 const bool swap_with_l_child = !swap_with_r_child&& smaller_than_left_child; 187 188 if (swap_with_l_child) 189 { 190 std::swap(m_a_entries[i], m_a_entries[left_child_i]); 191 192 i = left_child_i; 193 } 194 else if (swap_with_r_child) 195 { 196 std::swap(m_a_entries[i], m_a_entries[right_child_i]); 197 198 i = right_child_i; 199 } 200 else 201 i = m_size; 202 } 203} 204 205PB_DS_CLASS_T_DEC 206inline void 207PB_DS_CLASS_C_DEC:: 208swap_value_imp(entry_pointer p_e, value_type new_val, true_type) 209{ 210 * p_e = new_val; 211} 212 213PB_DS_CLASS_T_DEC 214inline void 215PB_DS_CLASS_C_DEC:: 216swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type) 217{ 218 value_type tmp(r_new_val); 219 (*p_e)->swap(tmp); 220} 221