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 base of binomial heaps. 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(true);) 53 54 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 55 56 insert_node(p_nd); 57 58 m_p_max = NULL; 59 60 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 61 62 return point_iterator(p_nd); 63} 64 65PB_DS_CLASS_T_DEC 66inline void 67PB_DS_CLASS_C_DEC:: 68insert_node(node_pointer p_nd) 69{ 70 if (base_type::m_p_root == NULL) 71 { 72 p_nd->m_p_next_sibling = p_nd->m_p_prev_or_parent = 73 p_nd->m_p_l_child = NULL; 74 75 p_nd->m_metadata = 0; 76 77 base_type::m_p_root = p_nd; 78 79 return; 80 } 81 82 if (base_type::m_p_root->m_metadata > 0) 83 { 84 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL; 85 86 p_nd->m_p_next_sibling = base_type::m_p_root; 87 88 base_type::m_p_root->m_p_prev_or_parent = p_nd; 89 90 base_type::m_p_root = p_nd; 91 92 p_nd->m_metadata = 0; 93 94 return; 95 } 96 97 if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value)) 98 { 99 p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling; 100 101 p_nd->m_p_prev_or_parent = NULL; 102 103 p_nd->m_metadata = 1; 104 105 p_nd->m_p_l_child = base_type::m_p_root; 106 107 base_type::m_p_root->m_p_prev_or_parent = p_nd; 108 109 base_type::m_p_root->m_p_next_sibling = NULL; 110 111 base_type::m_p_root = p_nd; 112 } 113 else 114 { 115 p_nd->m_p_next_sibling = NULL; 116 117 p_nd->m_p_l_child = NULL; 118 119 p_nd->m_p_prev_or_parent = base_type::m_p_root; 120 121 p_nd->m_metadata = 0; 122 123 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0); 124 base_type::m_p_root->m_p_l_child = p_nd; 125 126 base_type::m_p_root->m_metadata = 1; 127 } 128 129 base_type::m_p_root = fix(base_type::m_p_root); 130} 131 132PB_DS_CLASS_T_DEC 133inline typename PB_DS_CLASS_C_DEC::node_pointer 134PB_DS_CLASS_C_DEC:: 135fix(node_pointer p_nd) const 136{ 137 while (p_nd->m_p_next_sibling != NULL&& 138 p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata) 139 { 140 node_pointer p_next = p_nd->m_p_next_sibling; 141 142 if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) 143 { 144 p_next->m_p_prev_or_parent = 145 p_nd->m_p_prev_or_parent; 146 147 if (p_nd->m_p_prev_or_parent != NULL) 148 p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next; 149 150 base_type::make_child_of(p_nd, p_next); 151 152 ++p_next->m_metadata; 153 154 p_nd = p_next; 155 } 156 else 157 { 158 p_nd->m_p_next_sibling = p_next->m_p_next_sibling; 159 160 if (p_nd->m_p_next_sibling != NULL) 161 p_next->m_p_next_sibling = NULL; 162 163 base_type::make_child_of(p_next, p_nd); 164 165 ++p_nd->m_metadata; 166 } 167 } 168 169 if (p_nd->m_p_next_sibling != NULL) 170 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd; 171 172 return p_nd; 173} 174 175PB_DS_CLASS_T_DEC 176void 177PB_DS_CLASS_C_DEC:: 178modify(point_iterator it, const_reference r_new_val) 179{ 180 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 181 node_pointer p_nd = it.m_p_nd; 182 183 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 184 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd, false);) 185 186 const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val); 187 188 p_nd->m_value = r_new_val; 189 190 if (bubble_up) 191 { 192 node_pointer p_parent = base_type::parent(p_nd); 193 194 while (p_parent != NULL&& 195 Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value)) 196 { 197 base_type::swap_with_parent(p_nd, p_parent); 198 199 p_parent = base_type::parent(p_nd); 200 } 201 202 if (p_nd->m_p_prev_or_parent == NULL) 203 base_type::m_p_root = p_nd; 204 205 m_p_max = NULL; 206 207 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 208 209 return; 210 } 211 212 base_type::bubble_to_top(p_nd); 213 214 remove_parentless_node(p_nd); 215 216 insert_node(p_nd); 217 218 m_p_max = NULL; 219 220 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 221 } 222 223