Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/11/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp
$ cat -n /usr/include/c++/11/ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp 1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2021 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 thin_heap_/insert_fn_imps.hpp 38 * Contains an implementation for thin_heap_. 39 */ 40 41 #ifdef PB_DS_CLASS_C_DEC 42 43 PB_DS_CLASS_T_DEC 44 inline typename PB_DS_CLASS_C_DEC::point_iterator 45 PB_DS_CLASS_C_DEC:: 46 push(const_reference r_val) 47 { 48 PB_DS_ASSERT_VALID((*this)) 49 node_pointer p_nd = base_type::get_new_node_for_insert(r_val); 50 p_nd->m_metadata = 0; 51 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0; 52 if (base_type::m_p_root == 0) 53 { 54 p_nd->m_p_next_sibling = 0; 55 m_p_max = base_type::m_p_root = p_nd; 56 PB_DS_ASSERT_VALID((*this)) 57 return point_iterator(p_nd); 58 } 59 60 p_nd->m_p_next_sibling = base_type::m_p_root; 61 base_type::m_p_root->m_p_prev_or_parent = 0; 62 base_type::m_p_root = p_nd; 63 update_max(p_nd); 64 PB_DS_ASSERT_VALID((*this)) 65 return point_iterator(p_nd); 66 } 67 68 PB_DS_CLASS_T_DEC 69 inline void 70 PB_DS_CLASS_C_DEC:: 71 make_root(node_pointer p_nd) 72 { 73 p_nd->m_metadata = p_nd->m_p_l_child == 0 74 ? 0 : 1 + p_nd->m_p_l_child->m_metadata; 75 } 76 77 PB_DS_CLASS_T_DEC 78 inline void 79 PB_DS_CLASS_C_DEC:: 80 make_root_and_link(node_pointer p_nd) 81 { 82 make_root(p_nd); 83 p_nd->m_p_prev_or_parent = 0; 84 p_nd->m_p_next_sibling = base_type::m_p_root; 85 if (base_type::m_p_root != 0) 86 base_type::m_p_root->m_p_prev_or_parent = 0; 87 88 base_type::m_p_root = p_nd; 89 update_max(p_nd); 90 } 91 92 PB_DS_CLASS_T_DEC 93 inline void 94 PB_DS_CLASS_C_DEC:: 95 fix(node_pointer p_y) 96 { 97 while (true) 98 { 99 if (p_y->m_p_prev_or_parent == 0) 100 { 101 fix_root(p_y); 102 return; 103 } 104 else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == 0) 105 { 106 if (p_y->m_p_l_child != 0) 107 { 108 fix_sibling_rank_1_unmarked(p_y); 109 return; 110 } 111 112 fix_sibling_rank_1_marked(p_y); 113 p_y = p_y->m_p_prev_or_parent; 114 } 115 else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1) 116 { 117 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != 0); 118 if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2) 119 { 120 fix_sibling_general_unmarked(p_y); 121 return; 122 } 123 124 fix_sibling_general_marked(p_y); 125 p_y = p_y->m_p_prev_or_parent; 126 } 127 else if ((p_y->m_p_l_child == 0&& 128 p_y->m_metadata == 2) ||(p_y->m_p_l_child != 0&& 129 p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3)) 130 { 131 node_pointer p_z = p_y->m_p_prev_or_parent; 132 fix_child(p_y); 133 p_y = p_z; 134 } 135 else 136 return; 137 } 138 } 139 140 PB_DS_CLASS_T_DEC 141 inline void 142 PB_DS_CLASS_C_DEC:: 143 fix_root(node_pointer p_y) 144 { 145 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == 0); 146 make_root(p_y); 147 PB_DS_ASSERT_NODE_CONSISTENT(p_y, true) 148 } 149 150 PB_DS_CLASS_T_DEC 151 inline void 152 PB_DS_CLASS_C_DEC:: 153 fix_sibling_rank_1_unmarked(node_pointer p_y) 154 { 155 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 156 157 _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;) 158 _GLIBCXX_DEBUG_ASSERT(p_w != 0); 159 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == 0); 160 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == 0); 161 162 p_y->m_p_next_sibling = p_y->m_p_l_child; 163 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y; 164 p_y->m_p_l_child = 0; 165 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 166 } 167 168 PB_DS_CLASS_T_DEC 169 inline void 170 PB_DS_CLASS_C_DEC:: 171 fix_sibling_rank_1_marked(node_pointer p_y) 172 { 173 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 174 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == 0); 175 p_y->m_metadata = 0; 176 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 177 } 178 179 PB_DS_CLASS_T_DEC 180 inline void 181 PB_DS_CLASS_C_DEC:: 182 fix_sibling_general_unmarked(node_pointer p_y) 183 { 184 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 185 186 node_pointer p_w = p_y->m_p_l_child; 187 _GLIBCXX_DEBUG_ASSERT(p_w != 0); 188 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0); 189 190 p_y->m_p_l_child = p_w->m_p_next_sibling; 191 p_w->m_p_next_sibling->m_p_prev_or_parent = p_y; 192 193 p_w->m_p_next_sibling = p_y->m_p_next_sibling; 194 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0); 195 p_w->m_p_next_sibling->m_p_prev_or_parent = p_w; 196 197 p_y->m_p_next_sibling = p_w; 198 p_w->m_p_prev_or_parent = p_y; 199 200 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 201 } 202 203 PB_DS_CLASS_T_DEC 204 inline void 205 PB_DS_CLASS_C_DEC:: 206 fix_sibling_general_marked(node_pointer p_y) 207 { 208 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 209 --p_y->m_metadata; 210 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false) 211 } 212 213 PB_DS_CLASS_T_DEC 214 inline void 215 PB_DS_CLASS_C_DEC:: 216 fix_child(node_pointer p_y) 217 { 218 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0); 219 220 if (p_y->m_p_next_sibling != 0) 221 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent; 222 223 if (p_y->m_p_prev_or_parent->m_p_l_child == p_y) 224 p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling; 225 else 226 p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling; 227 228 make_root_and_link(p_y); 229 } 230 231 PB_DS_CLASS_T_DEC 232 void 233 PB_DS_CLASS_C_DEC:: 234 modify(point_iterator it, const_reference r_new_val) 235 { 236 PB_DS_ASSERT_VALID((*this)) 237 node_pointer p_nd = it.m_p_nd; 238 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 239 240 const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value); 241 p_nd->m_value = r_new_val; 242 if (smaller) 243 { 244 remove_node(p_nd); 245 p_nd->m_p_l_child = 0; 246 make_root_and_link(p_nd); 247 PB_DS_ASSERT_VALID((*this)) 248 return; 249 } 250 251 if (p_nd->m_p_prev_or_parent == 0) 252 { 253 update_max(p_nd); 254 PB_DS_ASSERT_VALID((*this)) 255 return; 256 } 257 258 node_pointer p_y = p_nd->m_p_prev_or_parent; 259 _GLIBCXX_DEBUG_ASSERT(p_y != 0); 260 261 if (p_nd->m_p_next_sibling != 0) 262 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y; 263 264 if (p_y->m_p_l_child == p_nd) 265 p_y->m_p_l_child = p_nd->m_p_next_sibling; 266 else 267 p_y->m_p_next_sibling = p_nd->m_p_next_sibling; 268 269 fix(p_y); 270 make_root_and_link(p_nd); 271 PB_DS_ASSERT_VALID((*this)) 272 } 273 274 PB_DS_CLASS_T_DEC 275 inline void 276 PB_DS_CLASS_C_DEC:: 277 update_max(node_pointer p_nd) 278 { 279 if (m_p_max == 0 || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value)) 280 m_p_max = p_nd; 281 } 282 283 #endif
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
