insert_fn_imps.hpp revision 1.1.1.11
1// -*- C++ -*- 2 3// Copyright (C) 2005-2020 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 3, 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// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file binary_heap_/insert_fn_imps.hpp 38 * Contains an implementation class for a binary_heap. 39 */ 40 41#ifdef PB_DS_CLASS_C_DEC 42 43PB_DS_CLASS_T_DEC 44inline typename PB_DS_CLASS_C_DEC::point_iterator 45PB_DS_CLASS_C_DEC:: 46push(const_reference r_val) 47{ 48 PB_DS_ASSERT_VALID((*this)) 49 insert_value(r_val, s_no_throw_copies_ind); 50 push_heap(); 51 PB_DS_ASSERT_VALID((*this)) 52 return point_iterator(m_a_entries); 53} 54 55PB_DS_CLASS_T_DEC 56inline void 57PB_DS_CLASS_C_DEC:: 58insert_value(value_type val, true_type) 59{ 60 resize_for_insert_if_needed(); 61 m_a_entries[m_size++] = val; 62} 63 64PB_DS_CLASS_T_DEC 65inline void 66PB_DS_CLASS_C_DEC:: 67insert_value(const_reference r_val, false_type) 68{ 69 resize_for_insert_if_needed(); 70 pointer p_new = s_value_allocator.allocate(1); 71 cond_dealtor_t cond(p_new); 72 new (p_new) value_type(r_val); 73 cond.set_no_action(); 74 m_a_entries[m_size++] = p_new; 75} 76 77PB_DS_CLASS_T_DEC 78inline void 79PB_DS_CLASS_C_DEC:: 80resize_for_insert_if_needed() 81{ 82 if (!resize_policy::resize_needed_for_grow(m_size)) 83 { 84 _GLIBCXX_DEBUG_ASSERT(m_size < m_actual_size); 85 return; 86 } 87 88 const size_type new_size = resize_policy::get_new_size_for_grow(); 89 entry_pointer new_entries = s_entry_allocator.allocate(new_size); 90 resize_policy::notify_grow_resize(); 91 92 std::copy(m_a_entries, m_a_entries + m_size, new_entries); 93 s_entry_allocator.deallocate(m_a_entries, m_actual_size); 94 m_actual_size = new_size; 95 m_a_entries = new_entries; 96 make_heap(); 97} 98 99PB_DS_CLASS_T_DEC 100void 101PB_DS_CLASS_C_DEC:: 102modify(point_iterator it, const_reference r_new_val) 103{ 104 PB_DS_ASSERT_VALID((*this)) 105 swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind); 106 fix(it.m_p_e); 107 PB_DS_ASSERT_VALID((*this)) 108} 109 110PB_DS_CLASS_T_DEC 111void 112PB_DS_CLASS_C_DEC:: 113fix(entry_pointer p_e) 114{ 115 size_type i = p_e - m_a_entries; 116 if (i > 0 && entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i])) 117 { 118 size_type parent_i = parent(i); 119 while (i > 0 120 && entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i])) 121 { 122 std::swap(m_a_entries[i], m_a_entries[parent_i]); 123 i = parent_i; 124 parent_i = parent(i); 125 } 126 127 PB_DS_ASSERT_VALID((*this)) 128 return; 129 } 130 131 while (i < m_size) 132 { 133 const size_type lchild_i = left_child(i); 134 const size_type rchild_i = right_child(i); 135 _GLIBCXX_DEBUG_ASSERT(rchild_i > lchild_i); 136 137 const bool smaller_than_lchild = lchild_i < m_size && 138 entry_cmp::operator()(m_a_entries[i], m_a_entries[lchild_i]); 139 140 const bool smaller_than_rchild = rchild_i < m_size && 141 entry_cmp::operator()(m_a_entries[i], m_a_entries[rchild_i]); 142 143 const bool swap_with_rchild = smaller_than_rchild && (!smaller_than_lchild || entry_cmp::operator()(m_a_entries[lchild_i], m_a_entries[rchild_i])); 144 145 const bool swap_with_lchild = !swap_with_rchild && smaller_than_lchild; 146 147 if (swap_with_lchild) 148 { 149 std::swap(m_a_entries[i], m_a_entries[lchild_i]); 150 i = lchild_i; 151 } 152 else if (swap_with_rchild) 153 { 154 std::swap(m_a_entries[i], m_a_entries[rchild_i]); 155 i = rchild_i; 156 } 157 else 158 i = m_size; 159 } 160} 161 162PB_DS_CLASS_T_DEC 163inline void 164PB_DS_CLASS_C_DEC:: 165swap_value_imp(entry_pointer p_e, value_type new_val, true_type) 166{ *p_e = new_val; } 167 168PB_DS_CLASS_T_DEC 169inline void 170PB_DS_CLASS_C_DEC:: 171swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type) 172{ 173 value_type tmp(r_new_val); 174 (*p_e)->swap(tmp); 175} 176#endif 177