libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file binomial_heap_base_/insert_fn_imps.hpp 00038 * Contains an implementation class for a base of binomial heaps. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 inline typename PB_DS_CLASS_C_DEC::point_iterator 00043 PB_DS_CLASS_C_DEC:: 00044 push(const_reference r_val) 00045 { 00046 PB_DS_ASSERT_VALID_COND((*this),true) 00047 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 00048 insert_node(p_nd); 00049 m_p_max = 0; 00050 PB_DS_ASSERT_VALID_COND((*this),true) 00051 return point_iterator(p_nd); 00052 } 00053 00054 PB_DS_CLASS_T_DEC 00055 inline void 00056 PB_DS_CLASS_C_DEC:: 00057 insert_node(node_pointer p_nd) 00058 { 00059 if (base_type::m_p_root == 0) 00060 { 00061 p_nd->m_p_next_sibling = 0; 00062 p_nd->m_p_prev_or_parent = 0; 00063 p_nd->m_p_l_child = 0; 00064 p_nd->m_metadata = 0; 00065 base_type::m_p_root = p_nd; 00066 return; 00067 } 00068 00069 if (base_type::m_p_root->m_metadata > 0) 00070 { 00071 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0; 00072 p_nd->m_p_next_sibling = base_type::m_p_root; 00073 base_type::m_p_root->m_p_prev_or_parent = p_nd; 00074 base_type::m_p_root = p_nd; 00075 p_nd->m_metadata = 0; 00076 return; 00077 } 00078 00079 if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value)) 00080 { 00081 p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling; 00082 p_nd->m_p_prev_or_parent = 0; 00083 p_nd->m_metadata = 1; 00084 p_nd->m_p_l_child = base_type::m_p_root; 00085 base_type::m_p_root->m_p_prev_or_parent = p_nd; 00086 base_type::m_p_root->m_p_next_sibling = 0; 00087 base_type::m_p_root = p_nd; 00088 } 00089 else 00090 { 00091 p_nd->m_p_next_sibling = 0; 00092 p_nd->m_p_l_child = 0; 00093 p_nd->m_p_prev_or_parent = base_type::m_p_root; 00094 p_nd->m_metadata = 0; 00095 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0); 00096 base_type::m_p_root->m_p_l_child = p_nd; 00097 base_type::m_p_root->m_metadata = 1; 00098 } 00099 00100 base_type::m_p_root = fix(base_type::m_p_root); 00101 } 00102 00103 PB_DS_CLASS_T_DEC 00104 inline typename PB_DS_CLASS_C_DEC::node_pointer 00105 PB_DS_CLASS_C_DEC:: 00106 fix(node_pointer p_nd) const 00107 { 00108 while (p_nd->m_p_next_sibling != 0 && 00109 p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata) 00110 { 00111 node_pointer p_next = p_nd->m_p_next_sibling; 00112 if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) 00113 { 00114 p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 00115 00116 if (p_nd->m_p_prev_or_parent != 0) 00117 p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next; 00118 00119 base_type::make_child_of(p_nd, p_next); 00120 ++p_next->m_metadata; 00121 p_nd = p_next; 00122 } 00123 else 00124 { 00125 p_nd->m_p_next_sibling = p_next->m_p_next_sibling; 00126 00127 if (p_nd->m_p_next_sibling != 0) 00128 p_next->m_p_next_sibling = 0; 00129 00130 base_type::make_child_of(p_next, p_nd); 00131 ++p_nd->m_metadata; 00132 } 00133 } 00134 00135 if (p_nd->m_p_next_sibling != 0) 00136 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd; 00137 00138 return p_nd; 00139 } 00140 00141 PB_DS_CLASS_T_DEC 00142 void 00143 PB_DS_CLASS_C_DEC:: 00144 modify(point_iterator it, const_reference r_new_val) 00145 { 00146 PB_DS_ASSERT_VALID_COND((*this),true) 00147 node_pointer p_nd = it.m_p_nd; 00148 00149 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 00150 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd, false) 00151 00152 const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val); 00153 p_nd->m_value = r_new_val; 00154 00155 if (bubble_up) 00156 { 00157 node_pointer p_parent = base_type::parent(p_nd); 00158 while (p_parent != 0 && 00159 Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value)) 00160 { 00161 base_type::swap_with_parent(p_nd, p_parent); 00162 p_parent = base_type::parent(p_nd); 00163 } 00164 00165 if (p_nd->m_p_prev_or_parent == 0) 00166 base_type::m_p_root = p_nd; 00167 00168 m_p_max = 0; 00169 PB_DS_ASSERT_VALID_COND((*this),true) 00170 return; 00171 } 00172 00173 base_type::bubble_to_top(p_nd); 00174 remove_parentless_node(p_nd); 00175 insert_node(p_nd); 00176 m_p_max = 0; 00177 PB_DS_ASSERT_VALID_COND((*this),true) 00178 }