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 binomial_heap_base_/insert_fn_imps.hpp 38 * Contains an implementation class for a base of binomial heaps. 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_COND((*this),true) 49 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 50 insert_node(p_nd); 51 m_p_max = 0; 52 PB_DS_ASSERT_VALID_COND((*this),true) 53 return point_iterator(p_nd); 54} 55 56PB_DS_CLASS_T_DEC 57inline void 58PB_DS_CLASS_C_DEC:: 59insert_node(node_pointer p_nd) 60{ 61 if (base_type::m_p_root == 0) 62 { 63 p_nd->m_p_next_sibling = 0; 64 p_nd->m_p_prev_or_parent = 0; 65 p_nd->m_p_l_child = 0; 66 p_nd->m_metadata = 0; 67 base_type::m_p_root = p_nd; 68 return; 69 } 70 71 if (base_type::m_p_root->m_metadata > 0) 72 { 73 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0; 74 p_nd->m_p_next_sibling = base_type::m_p_root; 75 base_type::m_p_root->m_p_prev_or_parent = p_nd; 76 base_type::m_p_root = p_nd; 77 p_nd->m_metadata = 0; 78 return; 79 } 80 81 if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value)) 82 { 83 p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling; 84 p_nd->m_p_prev_or_parent = 0; 85 p_nd->m_metadata = 1; 86 p_nd->m_p_l_child = base_type::m_p_root; 87 base_type::m_p_root->m_p_prev_or_parent = p_nd; 88 base_type::m_p_root->m_p_next_sibling = 0; 89 base_type::m_p_root = p_nd; 90 } 91 else 92 { 93 p_nd->m_p_next_sibling = 0; 94 p_nd->m_p_l_child = 0; 95 p_nd->m_p_prev_or_parent = base_type::m_p_root; 96 p_nd->m_metadata = 0; 97 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0); 98 base_type::m_p_root->m_p_l_child = p_nd; 99 base_type::m_p_root->m_metadata = 1; 100 } 101 102 base_type::m_p_root = fix(base_type::m_p_root); 103} 104 105PB_DS_CLASS_T_DEC 106inline typename PB_DS_CLASS_C_DEC::node_pointer 107PB_DS_CLASS_C_DEC:: 108fix(node_pointer p_nd) const 109{ 110 while (p_nd->m_p_next_sibling != 0 && 111 p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata) 112 { 113 node_pointer p_next = p_nd->m_p_next_sibling; 114 if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) 115 { 116 p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 117 118 if (p_nd->m_p_prev_or_parent != 0) 119 p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next; 120 121 base_type::make_child_of(p_nd, p_next); 122 ++p_next->m_metadata; 123 p_nd = p_next; 124 } 125 else 126 { 127 p_nd->m_p_next_sibling = p_next->m_p_next_sibling; 128 129 if (p_nd->m_p_next_sibling != 0) 130 p_next->m_p_next_sibling = 0; 131 132 base_type::make_child_of(p_next, p_nd); 133 ++p_nd->m_metadata; 134 } 135 } 136 137 if (p_nd->m_p_next_sibling != 0) 138 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd; 139 140 return p_nd; 141} 142 143PB_DS_CLASS_T_DEC 144void 145PB_DS_CLASS_C_DEC:: 146modify(point_iterator it, const_reference r_new_val) 147{ 148 PB_DS_ASSERT_VALID_COND((*this),true) 149 node_pointer p_nd = it.m_p_nd; 150 151 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 152 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd, false) 153 154 const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val); 155 p_nd->m_value = r_new_val; 156 157 if (bubble_up) 158 { 159 node_pointer p_parent = base_type::parent(p_nd); 160 while (p_parent != 0 && 161 Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value)) 162 { 163 base_type::swap_with_parent(p_nd, p_parent); 164 p_parent = base_type::parent(p_nd); 165 } 166 167 if (p_nd->m_p_prev_or_parent == 0) 168 base_type::m_p_root = p_nd; 169 170 m_p_max = 0; 171 PB_DS_ASSERT_VALID_COND((*this),true) 172 return; 173 } 174 175 base_type::bubble_to_top(p_nd); 176 remove_parentless_node(p_nd); 177 insert_node(p_nd); 178 m_p_max = 0; 179 PB_DS_ASSERT_VALID_COND((*this),true) 180} 181#endif 182