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 for rc_binomial_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 make_0_exposed(); 55 56 _GLIBCXX_DEBUG_ONLY(assert_valid();) 57 58 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 59 60 p_nd->m_p_l_child = p_nd->m_p_prev_or_parent = NULL; 61 p_nd->m_metadata = 0; 62 63 if (base_type::m_p_max == NULL || Cmp_Fn::operator()(base_type::m_p_max->m_value, r_val)) 64 base_type::m_p_max = p_nd; 65 66 p_nd->m_p_next_sibling = base_type::m_p_root; 67 68 if (base_type::m_p_root != NULL) 69 base_type::m_p_root->m_p_prev_or_parent = p_nd; 70 71 base_type::m_p_root = p_nd; 72 73 if (p_nd->m_p_next_sibling != NULL&& p_nd->m_p_next_sibling->m_metadata == 0) 74 m_rc.push(p_nd); 75 76 _GLIBCXX_DEBUG_ONLY(assert_valid();) 77 78 return point_iterator(p_nd); 79} 80 81PB_DS_CLASS_T_DEC 82void 83PB_DS_CLASS_C_DEC:: 84modify(point_iterator it, const_reference r_new_val) 85{ 86 _GLIBCXX_DEBUG_ONLY(assert_valid();) 87 88 make_binomial_heap(); 89 90 base_type::modify(it, r_new_val); 91 92 base_type::find_max(); 93 94 _GLIBCXX_DEBUG_ONLY(assert_valid();) 95 } 96 97PB_DS_CLASS_T_DEC 98inline typename PB_DS_CLASS_C_DEC::node_pointer 99PB_DS_CLASS_C_DEC:: 100link_with_next_sibling(node_pointer p_nd) 101{ 102 node_pointer p_next = p_nd->m_p_next_sibling; 103 104 _GLIBCXX_DEBUG_ASSERT(p_next != NULL); 105 _GLIBCXX_DEBUG_ASSERT(p_next->m_p_prev_or_parent == p_nd); 106 107 if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) 108 { 109 p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 110 111 if (p_next->m_p_prev_or_parent == NULL) 112 base_type::m_p_root = p_next; 113 else 114 p_next->m_p_prev_or_parent->m_p_next_sibling = p_next; 115 116 if (base_type::m_p_max == p_nd) 117 base_type::m_p_max = p_next; 118 119 base_type::make_child_of(p_nd, p_next); 120 121 ++p_next->m_metadata; 122 123 return p_next; 124 } 125 126 p_nd->m_p_next_sibling = p_next->m_p_next_sibling; 127 128 if (p_nd->m_p_next_sibling != NULL) 129 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd; 130 131 if (base_type::m_p_max == p_next) 132 base_type::m_p_max = p_nd; 133 134 base_type::make_child_of(p_next, p_nd); 135 136 ++p_nd->m_metadata; 137 138 return p_nd; 139} 140 141PB_DS_CLASS_T_DEC 142void 143PB_DS_CLASS_C_DEC:: 144make_0_exposed() 145{ 146 if (m_rc.empty()) 147 return; 148 149 node_pointer p_nd = m_rc.top(); 150 151 m_rc.pop(); 152 153 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling != NULL); 154 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata); 155 156 node_pointer p_res = link_with_next_sibling(p_nd); 157 158 if (p_res->m_p_next_sibling != NULL&& p_res->m_metadata == p_res->m_p_next_sibling->m_metadata) 159 m_rc.push(p_res); 160} 161