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