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 thin_heap_/insert_fn_imps.hpp 00038 * Contains an implementation for thin_heap_. 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((*this)) 00047 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 00048 p_nd->m_metadata = 0; 00049 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0; 00050 if (base_type::m_p_root == 0) 00051 { 00052 p_nd->m_p_next_sibling = 0; 00053 m_p_max = base_type::m_p_root = p_nd; 00054 PB_DS_ASSERT_VALID((*this)) 00055 return point_iterator(p_nd); 00056 } 00057 00058 p_nd->m_p_next_sibling = base_type::m_p_root; 00059 base_type::m_p_root->m_p_prev_or_parent = 0; 00060 base_type::m_p_root = p_nd; 00061 update_max(p_nd); 00062 PB_DS_ASSERT_VALID((*this)) 00063 return point_iterator(p_nd); 00064 } 00065 00066 PB_DS_CLASS_T_DEC 00067 inline void 00068 PB_DS_CLASS_C_DEC:: 00069 make_root(node_pointer p_nd) 00070 { 00071 p_nd->m_metadata = p_nd->m_p_l_child == 0 00072 ? 0 : 1 + p_nd->m_p_l_child->m_metadata; 00073 } 00074 00075 PB_DS_CLASS_T_DEC 00076 inline void 00077 PB_DS_CLASS_C_DEC:: 00078 make_root_and_link(node_pointer p_nd) 00079 { 00080 make_root(p_nd); 00081 p_nd->m_p_prev_or_parent = 0; 00082 p_nd->m_p_next_sibling = base_type::m_p_root; 00083 if (base_type::m_p_root != 0) 00084 base_type::m_p_root->m_p_prev_or_parent = 0; 00085 00086 base_type::m_p_root = p_nd; 00087 update_max(p_nd); 00088 } 00089 00090 PB_DS_CLASS_T_DEC 00091 inline void 00092 PB_DS_CLASS_C_DEC:: 00093 fix(node_pointer p_y) 00094 { 00095 while (true) 00096 { 00097 if (p_y->m_p_prev_or_parent == 0) 00098 { 00099 fix_root(p_y); 00100 return; 00101 } 00102 else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == 0) 00103 { 00104 if (p_y->m_p_l_child != 0) 00105 { 00106 fix_sibling_rank_1_unmarked(p_y); 00107 return; 00108 } 00109 00110 fix_sibling_rank_1_marked(p_y); 00111 p_y = p_y->m_p_prev_or_parent; 00112 } 00113 else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1) 00114 { 00115 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != 0); 00116 if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2) 00117 { 00118 fix_sibling_general_unmarked(p_y); 00119 return; 00120 } 00121 00122 fix_sibling_general_marked(p_y); 00123 p_y = p_y->m_p_prev_or_parent; 00124 } 00125 else if ((p_y->m_p_l_child == 0&& 00126 p_y->m_metadata == 2) ||(p_y->m_p_l_child != 0&& 00127 p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3)) 00128 { 00129 node_pointer p_z = p_y->m_p_prev_or_parent; 00130 fix_child(p_y); 00131 p_y = p_z; 00132 } 00133 else 00134 return; 00135 } 00136 } 00137 00138 PB_DS_CLASS_T_DEC 00139 inline void 00140 PB_DS_CLASS_C_DEC:: 00141 fix_root(node_pointer p_y) 00142 { 00143 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == 0); 00144 make_root(p_y); 00145 PB_DS_ASSERT_NODE_CONSISTENT(p_y, true) 00146 } 00147 00148 PB_DS_CLASS_T_DEC 00149 inline void 00150 PB_DS_CLASS_C_DEC:: 00151 fix_sibling_rank_1_unmarked(node_pointer p_y) 00152 { 00153 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 00154 00155 _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;) 00156 _GLIBCXX_DEBUG_ASSERT(p_w != 0); 00157 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == 0); 00158 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == 0); 00159 00160 p_y->m_p_next_sibling = p_y->m_p_l_child; 00161 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y; 00162 p_y->m_p_l_child = 0; 00163 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 00164 } 00165 00166 PB_DS_CLASS_T_DEC 00167 inline void 00168 PB_DS_CLASS_C_DEC:: 00169 fix_sibling_rank_1_marked(node_pointer p_y) 00170 { 00171 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 00172 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == 0); 00173 p_y->m_metadata = 0; 00174 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 00175 } 00176 00177 PB_DS_CLASS_T_DEC 00178 inline void 00179 PB_DS_CLASS_C_DEC:: 00180 fix_sibling_general_unmarked(node_pointer p_y) 00181 { 00182 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 00183 00184 node_pointer p_w = p_y->m_p_l_child; 00185 _GLIBCXX_DEBUG_ASSERT(p_w != 0); 00186 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0); 00187 00188 p_y->m_p_l_child = p_w->m_p_next_sibling; 00189 p_w->m_p_next_sibling->m_p_prev_or_parent = p_y; 00190 00191 p_w->m_p_next_sibling = p_y->m_p_next_sibling; 00192 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0); 00193 p_w->m_p_next_sibling->m_p_prev_or_parent = p_w; 00194 00195 p_y->m_p_next_sibling = p_w; 00196 p_w->m_p_prev_or_parent = p_y; 00197 00198 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 00199 } 00200 00201 PB_DS_CLASS_T_DEC 00202 inline void 00203 PB_DS_CLASS_C_DEC:: 00204 fix_sibling_general_marked(node_pointer p_y) 00205 { 00206 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 00207 --p_y->m_metadata; 00208 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 00209 } 00210 00211 PB_DS_CLASS_T_DEC 00212 inline void 00213 PB_DS_CLASS_C_DEC:: 00214 fix_child(node_pointer p_y) 00215 { 00216 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 00217 00218 if (p_y->m_p_next_sibling != 0) 00219 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent; 00220 00221 if (p_y->m_p_prev_or_parent->m_p_l_child == p_y) 00222 p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling; 00223 else 00224 p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling; 00225 00226 make_root_and_link(p_y); 00227 } 00228 00229 PB_DS_CLASS_T_DEC 00230 void 00231 PB_DS_CLASS_C_DEC:: 00232 modify(point_iterator it, const_reference r_new_val) 00233 { 00234 PB_DS_ASSERT_VALID((*this)) 00235 node_pointer p_nd = it.m_p_nd; 00236 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 00237 00238 const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value); 00239 p_nd->m_value = r_new_val; 00240 if (smaller) 00241 { 00242 remove_node(p_nd); 00243 p_nd->m_p_l_child = 0; 00244 make_root_and_link(p_nd); 00245 PB_DS_ASSERT_VALID((*this)) 00246 return; 00247 } 00248 00249 if (p_nd->m_p_prev_or_parent == 0) 00250 { 00251 update_max(p_nd); 00252 PB_DS_ASSERT_VALID((*this)) 00253 return; 00254 } 00255 00256 node_pointer p_y = p_nd->m_p_prev_or_parent; 00257 _GLIBCXX_DEBUG_ASSERT(p_y != 0); 00258 00259 if (p_nd->m_p_next_sibling != 0) 00260 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y; 00261 00262 if (p_y->m_p_l_child == p_nd) 00263 p_y->m_p_l_child = p_nd->m_p_next_sibling; 00264 else 00265 p_y->m_p_next_sibling = p_nd->m_p_next_sibling; 00266 00267 fix(p_y); 00268 make_root_and_link(p_nd); 00269 PB_DS_ASSERT_VALID((*this)) 00270 } 00271 00272 PB_DS_CLASS_T_DEC 00273 inline void 00274 PB_DS_CLASS_C_DEC:: 00275 update_max(node_pointer p_nd) 00276 { 00277 if (m_p_max == 0 || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value)) 00278 m_p_max = p_nd; 00279 } 00280