Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp
1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2025 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 pairing_heap_/erase_fn_imps.hpp 38 * Contains an implementation class for a pairing heap. 39 */ 40 41 #ifdef PB_DS_CLASS_C_DEC 42 43 PB_DS_CLASS_T_DEC 44 void 45 PB_DS_CLASS_C_DEC:: 46 pop() 47 { 48 PB_DS_ASSERT_VALID((*this)) 49 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 50 51 node_pointer p_new_root = join_node_children(base_type::m_p_root); 52 PB_DS_ASSERT_NODE_CONSISTENT(p_new_root, false) 53 if (p_new_root != 0) 54 p_new_root->m_p_prev_or_parent = 0; 55 56 base_type::actual_erase_node(base_type::m_p_root); 57 base_type::m_p_root = p_new_root; 58 PB_DS_ASSERT_VALID((*this)) 59 } 60 61 PB_DS_CLASS_T_DEC 62 void 63 PB_DS_CLASS_C_DEC:: 64 erase(point_iterator it) 65 { 66 PB_DS_ASSERT_VALID((*this)) 67 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 68 remove_node(it.m_p_nd); 69 base_type::actual_erase_node(it.m_p_nd); 70 PB_DS_ASSERT_VALID((*this)) 71 } 72 73 PB_DS_CLASS_T_DEC 74 void 75 PB_DS_CLASS_C_DEC:: 76 remove_node(node_pointer p_nd) 77 { 78 PB_DS_ASSERT_VALID((*this)) 79 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 80 node_pointer p_new_child = join_node_children(p_nd); 81 82 PB_DS_ASSERT_NODE_CONSISTENT(p_new_child, false) 83 84 if (p_nd == base_type::m_p_root) 85 { 86 if (p_new_child != 0) 87 p_new_child->m_p_prev_or_parent = 0; 88 base_type::m_p_root = p_new_child; 89 PB_DS_ASSERT_NODE_CONSISTENT(base_type::m_p_root, false) 90 return; 91 } 92 93 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_prev_or_parent != 0); 94 if (p_nd->m_p_prev_or_parent->m_p_l_child == p_nd) 95 { 96 if (p_new_child != 0) 97 { 98 p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 99 p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling; 100 if (p_new_child->m_p_next_sibling != 0) 101 p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child; 102 p_nd->m_p_prev_or_parent->m_p_l_child = p_new_child; 103 PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) 104 return; 105 } 106 107 p_nd->m_p_prev_or_parent->m_p_l_child = p_nd->m_p_next_sibling; 108 if (p_nd->m_p_next_sibling != 0) 109 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 110 PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) 111 return; 112 } 113 114 if (p_new_child != 0) 115 { 116 p_new_child->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 117 p_new_child->m_p_next_sibling = p_nd->m_p_next_sibling; 118 if (p_new_child->m_p_next_sibling != 0) 119 p_new_child->m_p_next_sibling->m_p_prev_or_parent = p_new_child; 120 p_new_child->m_p_prev_or_parent->m_p_next_sibling = p_new_child; 121 PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) 122 return; 123 } 124 125 p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling; 126 if (p_nd->m_p_next_sibling != 0) 127 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 128 PB_DS_ASSERT_NODE_CONSISTENT(p_nd->m_p_prev_or_parent, false) 129 } 130 131 PB_DS_CLASS_T_DEC 132 typename PB_DS_CLASS_C_DEC::node_pointer 133 PB_DS_CLASS_C_DEC:: 134 join_node_children(node_pointer p_nd) 135 { 136 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 137 node_pointer p_ret = p_nd->m_p_l_child; 138 if (p_ret == 0) 139 return 0; 140 while (p_ret->m_p_next_sibling != 0) 141 p_ret = forward_join(p_ret, p_ret->m_p_next_sibling); 142 while (p_ret->m_p_prev_or_parent != p_nd) 143 p_ret = back_join(p_ret->m_p_prev_or_parent, p_ret); 144 PB_DS_ASSERT_NODE_CONSISTENT(p_ret, false) 145 return p_ret; 146 } 147 148 PB_DS_CLASS_T_DEC 149 typename PB_DS_CLASS_C_DEC::node_pointer 150 PB_DS_CLASS_C_DEC:: 151 forward_join(node_pointer p_nd, node_pointer p_next) 152 { 153 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 154 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling == p_next); 155 if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) 156 { 157 p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 158 base_type::make_child_of(p_nd, p_next); 159 return p_next->m_p_next_sibling == 0 160 ? p_next : p_next->m_p_next_sibling; 161 } 162 163 if (p_next->m_p_next_sibling != 0) 164 { 165 p_next->m_p_next_sibling->m_p_prev_or_parent = p_nd; 166 p_nd->m_p_next_sibling = p_next->m_p_next_sibling; 167 base_type::make_child_of(p_next, p_nd); 168 return p_nd->m_p_next_sibling; 169 } 170 171 p_nd->m_p_next_sibling = 0; 172 base_type::make_child_of(p_next, p_nd); 173 PB_DS_ASSERT_NODE_CONSISTENT(p_nd, false) 174 return p_nd; 175 } 176 177 PB_DS_CLASS_T_DEC 178 typename PB_DS_CLASS_C_DEC::node_pointer 179 PB_DS_CLASS_C_DEC:: 180 back_join(node_pointer p_nd, node_pointer p_next) 181 { 182 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 183 _GLIBCXX_DEBUG_ASSERT(p_next->m_p_next_sibling == 0); 184 185 if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value)) 186 { 187 p_next->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 188 base_type::make_child_of(p_nd, p_next); 189 PB_DS_ASSERT_NODE_CONSISTENT(p_next, false) 190 return p_next; 191 } 192 193 p_nd->m_p_next_sibling = 0; 194 base_type::make_child_of(p_next, p_nd); 195 PB_DS_ASSERT_NODE_CONSISTENT(p_nd, false) 196 return p_nd; 197 } 198 199 PB_DS_CLASS_T_DEC 200 template<typename Pred> 201 typename PB_DS_CLASS_C_DEC::size_type 202 PB_DS_CLASS_C_DEC:: 203 erase_if(Pred pred) 204 { 205 PB_DS_ASSERT_VALID((*this)) 206 if (base_type::empty()) 207 { 208 PB_DS_ASSERT_VALID((*this)) 209 return 0; 210 } 211 base_type::to_linked_list(); 212 node_pointer p_out = base_type::prune(pred); 213 size_type ersd = 0; 214 while (p_out != 0) 215 { 216 ++ersd; 217 node_pointer p_next = p_out->m_p_next_sibling; 218 base_type::actual_erase_node(p_out); 219 p_out = p_next; 220 } 221 222 node_pointer p_cur = base_type::m_p_root; 223 base_type::m_p_root = 0; 224 while (p_cur != 0) 225 { 226 node_pointer p_next = p_cur->m_p_next_sibling; 227 p_cur->m_p_l_child = p_cur->m_p_next_sibling = p_cur->m_p_prev_or_parent = 0; 228 229 push_imp(p_cur); 230 p_cur = p_next; 231 } 232 PB_DS_ASSERT_VALID((*this)) 233 return ersd; 234 } 235 236 #endif
