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 thin_heap_/erase_fn_imps.hpp 38 * Contains an implementation for thin_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 _GLIBCXX_DEBUG_ASSERT(m_p_max != 0); 49 50 node_pointer p_nd = m_p_max; 51 remove_max_node(); 52 base_type::actual_erase_node(p_nd); 53 PB_DS_ASSERT_VALID((*this)) 54 } 55 56 PB_DS_CLASS_T_DEC 57 inline void 58 PB_DS_CLASS_C_DEC:: 59 remove_max_node() 60 { 61 to_aux_except_max(); 62 make_from_aux(); 63 } 64 65 PB_DS_CLASS_T_DEC 66 void 67 PB_DS_CLASS_C_DEC:: 68 to_aux_except_max() 69 { 70 node_pointer p_add = base_type::m_p_root; 71 while (p_add != m_p_max) 72 { 73 node_pointer p_next_add = p_add->m_p_next_sibling; 74 add_to_aux(p_add); 75 p_add = p_next_add; 76 } 77 78 p_add = m_p_max->m_p_l_child; 79 while (p_add != 0) 80 { 81 node_pointer p_next_add = p_add->m_p_next_sibling; 82 p_add->m_metadata = p_add->m_p_l_child == 0 ? 83 0 : p_add->m_p_l_child->m_metadata + 1; 84 85 add_to_aux(p_add); 86 p_add = p_next_add; 87 } 88 89 p_add = m_p_max->m_p_next_sibling; 90 while (p_add != 0) 91 { 92 node_pointer p_next_add = p_add->m_p_next_sibling; 93 add_to_aux(p_add); 94 p_add = p_next_add; 95 } 96 } 97 98 PB_DS_CLASS_T_DEC 99 inline void 100 PB_DS_CLASS_C_DEC:: 101 add_to_aux(node_pointer p_nd) 102 { 103 size_type r = p_nd->m_metadata; 104 while (m_a_aux[r] != 0) 105 { 106 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); 107 if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value)) 108 make_child_of(m_a_aux[r], p_nd); 109 else 110 { 111 make_child_of(p_nd, m_a_aux[r]); 112 p_nd = m_a_aux[r]; 113 } 114 115 m_a_aux[r] = 0; 116 ++r; 117 } 118 119 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound()); 120 121 m_a_aux[r] = p_nd; 122 } 123 124 PB_DS_CLASS_T_DEC 125 inline void 126 PB_DS_CLASS_C_DEC:: 127 make_child_of(node_pointer p_nd, node_pointer p_new_parent) 128 { 129 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata); 130 _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd || 131 m_a_aux[p_nd->m_metadata] == p_new_parent); 132 133 ++p_new_parent->m_metadata; 134 base_type::make_child_of(p_nd, p_new_parent); 135 } 136 137 PB_DS_CLASS_T_DEC 138 inline void 139 PB_DS_CLASS_C_DEC:: 140 make_from_aux() 141 { 142 base_type::m_p_root = m_p_max = 0; 143 const size_type rnk_bnd = rank_bound(); 144 size_type i = 0; 145 while (i < rnk_bnd) 146 { 147 if (m_a_aux[i] != 0) 148 { 149 make_root_and_link(m_a_aux[i]); 150 m_a_aux[i] = 0; 151 } 152 ++i; 153 } 154 155 PB_DS_ASSERT_AUX_NULL((*this)) 156 } 157 158 PB_DS_CLASS_T_DEC 159 inline void 160 PB_DS_CLASS_C_DEC:: 161 remove_node(node_pointer p_nd) 162 { 163 node_pointer p_parent = p_nd; 164 while (base_type::parent(p_parent) != 0) 165 p_parent = base_type::parent(p_parent); 166 167 base_type::bubble_to_top(p_nd); 168 m_p_max = p_nd; 169 170 node_pointer p_fix = base_type::m_p_root; 171 while (p_fix != 0&& p_fix->m_p_next_sibling != p_parent) 172 p_fix = p_fix->m_p_next_sibling; 173 174 if (p_fix != 0) 175 p_fix->m_p_next_sibling = p_nd; 176 177 remove_max_node(); 178 } 179 180 PB_DS_CLASS_T_DEC 181 inline void 182 PB_DS_CLASS_C_DEC:: 183 clear() 184 { 185 base_type::clear(); 186 m_p_max = 0; 187 } 188 189 PB_DS_CLASS_T_DEC 190 void 191 PB_DS_CLASS_C_DEC:: 192 erase(point_iterator it) 193 { 194 PB_DS_ASSERT_VALID((*this)) 195 _GLIBCXX_DEBUG_ASSERT(!base_type::empty()); 196 197 node_pointer p_nd = it.m_p_nd; 198 remove_node(p_nd); 199 base_type::actual_erase_node(p_nd); 200 PB_DS_ASSERT_VALID((*this)) 201 } 202 203 PB_DS_CLASS_T_DEC 204 template<typename Pred> 205 typename PB_DS_CLASS_C_DEC::size_type 206 PB_DS_CLASS_C_DEC:: 207 erase_if(Pred pred) 208 { 209 PB_DS_ASSERT_VALID((*this)) 210 if (base_type::empty()) 211 { 212 PB_DS_ASSERT_VALID((*this)) 213 return 0; 214 } 215 216 base_type::to_linked_list(); 217 node_pointer p_out = base_type::prune(pred); 218 size_type ersd = 0; 219 while (p_out != 0) 220 { 221 ++ersd; 222 node_pointer p_next = p_out->m_p_next_sibling; 223 base_type::actual_erase_node(p_out); 224 p_out = p_next; 225 } 226 227 node_pointer p_cur = base_type::m_p_root; 228 m_p_max = base_type::m_p_root = 0; 229 while (p_cur != 0) 230 { 231 node_pointer p_next = p_cur->m_p_next_sibling; 232 make_root_and_link(p_cur); 233 p_cur = p_next; 234 } 235 236 PB_DS_ASSERT_VALID((*this)) 237 return ersd; 238 } 239 240 PB_DS_CLASS_T_DEC 241 inline typename PB_DS_CLASS_C_DEC::size_type 242 PB_DS_CLASS_C_DEC:: 243 rank_bound() 244 { 245 using namespace std; 246 const size_t* const p_upper = 247 std::upper_bound(g_a_rank_bounds, 248 g_a_rank_bounds + num_distinct_rank_bounds, 249 base_type::m_size); 250 251 if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds) 252 return max_rank; 253 254 return (p_upper - g_a_rank_bounds); 255 } 256
