1// -*- C++ -*- 2 3// Copyright (C) 2005-2014 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 41PB_DS_CLASS_T_DEC 42void 43PB_DS_CLASS_C_DEC:: 44pop() 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 59PB_DS_CLASS_T_DEC 60void 61PB_DS_CLASS_C_DEC:: 62erase(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 71PB_DS_CLASS_T_DEC 72void 73PB_DS_CLASS_C_DEC:: 74remove_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 129PB_DS_CLASS_T_DEC 130typename PB_DS_CLASS_C_DEC::node_pointer 131PB_DS_CLASS_C_DEC:: 132join_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 146PB_DS_CLASS_T_DEC 147typename PB_DS_CLASS_C_DEC::node_pointer 148PB_DS_CLASS_C_DEC:: 149forward_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 175PB_DS_CLASS_T_DEC 176typename PB_DS_CLASS_C_DEC::node_pointer 177PB_DS_CLASS_C_DEC:: 178back_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 197PB_DS_CLASS_T_DEC 198template<typename Pred> 199typename PB_DS_CLASS_C_DEC::size_type 200PB_DS_CLASS_C_DEC:: 201erase_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