1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file erase_fn_imps.hpp 44 * Contains an implementation class for a base of binomial heaps. 45 */ 46 47PB_DS_CLASS_T_DEC 48void 49PB_DS_CLASS_C_DEC:: 50pop() 51{ 52 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 53 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 54 55 if (m_p_max == NULL) 56 find_max(); 57 58 _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL); 59 60 node_pointer p_nd = m_p_max; 61 62 remove_parentless_node(m_p_max); 63 64 base_type::actual_erase_node(p_nd); 65 66 m_p_max = NULL; 67 68 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 69 } 70 71PB_DS_CLASS_T_DEC 72void 73PB_DS_CLASS_C_DEC:: 74remove_parentless_node(node_pointer p_nd) 75{ 76 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 77 _GLIBCXX_DEBUG_ASSERT(base_type::parent(p_nd) == NULL); 78 79 node_pointer p_cur_root = p_nd == base_type::m_p_root? 80 p_nd->m_p_next_sibling : 81 base_type::m_p_root; 82 83 if (p_cur_root != NULL) 84 p_cur_root->m_p_prev_or_parent = NULL; 85 86 if (p_nd->m_p_prev_or_parent != NULL) 87 p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling; 88 89 if (p_nd->m_p_next_sibling != NULL) 90 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent; 91 92 node_pointer p_child = p_nd->m_p_l_child; 93 94 if (p_child != NULL) 95 { 96 p_child->m_p_prev_or_parent = NULL; 97 98 while (p_child->m_p_next_sibling != NULL) 99 p_child = p_child->m_p_next_sibling; 100 } 101 102 m_p_max = NULL; 103 104 base_type::m_p_root = join(p_cur_root, p_child); 105} 106 107PB_DS_CLASS_T_DEC 108inline void 109PB_DS_CLASS_C_DEC:: 110clear() 111{ 112 base_type::clear(); 113 114 m_p_max = NULL; 115} 116 117PB_DS_CLASS_T_DEC 118void 119PB_DS_CLASS_C_DEC:: 120erase(point_iterator it) 121{ 122 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 123 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 124 125 base_type::bubble_to_top(it.m_p_nd); 126 127 remove_parentless_node(it.m_p_nd); 128 129 base_type::actual_erase_node(it.m_p_nd); 130 131 m_p_max = NULL; 132 133 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 134 } 135 136PB_DS_CLASS_T_DEC 137template<typename Pred> 138typename PB_DS_CLASS_C_DEC::size_type 139PB_DS_CLASS_C_DEC:: 140erase_if(Pred pred) 141{ 142 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 143 144 if (base_type::empty()) 145 { 146 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 147 148 return 0; 149 } 150 151 base_type::to_linked_list(); 152 153 node_pointer p_out = base_type::prune(pred); 154 155 size_type ersd = 0; 156 157 while (p_out != NULL) 158 { 159 ++ersd; 160 161 node_pointer p_next = p_out->m_p_next_sibling; 162 163 base_type::actual_erase_node(p_out); 164 165 p_out = p_next; 166 } 167 168 node_pointer p_cur = base_type::m_p_root; 169 170 base_type::m_p_root = NULL; 171 172 while (p_cur != NULL) 173 { 174 node_pointer p_next = p_cur->m_p_next_sibling; 175 176 p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = NULL; 177 178 p_cur->m_metadata = 0; 179 180 p_cur->m_p_next_sibling = base_type::m_p_root; 181 182 if (base_type::m_p_root != NULL) 183 base_type::m_p_root->m_p_prev_or_parent = p_cur; 184 185 base_type::m_p_root = p_cur; 186 187 base_type::m_p_root = fix(base_type::m_p_root); 188 189 p_cur = p_next; 190 } 191 192 m_p_max = NULL; 193 194 _GLIBCXX_DEBUG_ONLY(assert_valid(true);) 195 196 return ersd; 197} 198 199