00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00045 PB_ASSOC_CLASS_T_DEC
00046 inline typename PB_ASSOC_CLASS_C_DEC::size_type
00047 PB_ASSOC_CLASS_C_DEC::
00048 erase(const_key_reference r_key)
00049 {
00050 iterator it = find(r_key);
00051
00052 if (it == PB_ASSOC_BASE_C_DEC::find_end())
00053 return (0);
00054
00055 erase(it);
00056
00057 return (1);
00058 }
00059
00060 PB_ASSOC_CLASS_T_DEC
00061 inline typename PB_ASSOC_CLASS_C_DEC::const_iterator
00062 PB_ASSOC_CLASS_C_DEC::
00063 erase(const_iterator it)
00064 {
00065 PB_ASSOC_DBG_ONLY(assert_valid());
00066 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00067
00068 if (it == PB_ASSOC_BASE_C_DEC::find_end())
00069 return (it);
00070
00071 const_iterator ret_it = it;
00072
00073 ++ret_it;
00074
00075 erase_node(it.m_p_nd);
00076
00077 PB_ASSOC_DBG_ONLY(assert_valid());
00078 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00079
00080 return (ret_it);
00081 }
00082
00083 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00084 PB_ASSOC_CLASS_T_DEC
00085 inline typename PB_ASSOC_CLASS_C_DEC::iterator
00086 PB_ASSOC_CLASS_C_DEC::
00087 erase(iterator it)
00088 {
00089 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00090 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00091
00092 if (it == PB_ASSOC_BASE_C_DEC::find_end())
00093 return (it);
00094
00095 iterator ret_it = it;
00096
00097 ++ret_it;
00098
00099 erase_node(it.m_p_nd);
00100
00101 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00102 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00103
00104 return (ret_it);
00105 }
00106 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00107
00108 PB_ASSOC_CLASS_T_DEC
00109 inline typename PB_ASSOC_CLASS_C_DEC::const_reverse_iterator
00110 PB_ASSOC_CLASS_C_DEC::
00111 erase(const_reverse_iterator it)
00112 {
00113 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00114 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00115
00116 if (it == PB_ASSOC_BASE_C_DEC::find_rend())
00117 return (it);
00118
00119 const_reverse_iterator ret_it = it;
00120
00121 ++ret_it;
00122
00123 erase_node(it.m_p_nd);
00124
00125 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00126 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00127
00128 return (ret_it);
00129 }
00130
00131 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00132 PB_ASSOC_CLASS_T_DEC
00133 inline typename PB_ASSOC_CLASS_C_DEC::reverse_iterator
00134 PB_ASSOC_CLASS_C_DEC::
00135 erase(reverse_iterator it)
00136 {
00137 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00138
00139 if (it == PB_ASSOC_BASE_C_DEC::find_rend())
00140 return (it);
00141
00142 reverse_iterator ret_it = it;
00143
00144 ++ret_it;
00145
00146 erase_node(it.m_p_nd);
00147
00148 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00149
00150 return (ret_it);
00151 }
00152 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00153
00154 PB_ASSOC_CLASS_T_DEC
00155 template<class Pred>
00156 inline typename PB_ASSOC_CLASS_C_DEC::size_type
00157 PB_ASSOC_CLASS_C_DEC::
00158 erase_if(Pred pred)
00159 {
00160 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00161
00162 size_type num_ersd = 0;
00163
00164 iterator it = PB_ASSOC_BASE_C_DEC::begin();
00165
00166 while (it != PB_ASSOC_BASE_C_DEC::end())
00167 if (pred(*it))
00168 {
00169 ++num_ersd;
00170
00171 it = erase(it);
00172 }
00173 else
00174 ++it;
00175
00176 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00177
00178 return (num_ersd);
00179 }
00180
00181 PB_ASSOC_CLASS_T_DEC
00182 void
00183 PB_ASSOC_CLASS_C_DEC::
00184 erase_node(node_pointer p_nd)
00185 {
00186 remove_node(p_nd);
00187
00188 PB_ASSOC_BASE_C_DEC::actual_erase_node(p_nd);
00189
00190 PB_ASSOC_DBG_ONLY(assert_valid());
00191 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00192 }
00193
00194 PB_ASSOC_CLASS_T_DEC
00195 void
00196 PB_ASSOC_CLASS_C_DEC::
00197 remove_node(node_pointer p_z)
00198 {
00199 update_min_max_for_erased_node(p_z);
00200
00201 node_pointer p_y = p_z;
00202
00203 node_pointer p_x = NULL;
00204
00205 node_pointer p_new_x_parent = NULL;
00206
00207 if (p_y->m_p_left == NULL)
00208 p_x = p_y->m_p_right;
00209 else if (p_y->m_p_right == NULL)
00210 p_x = p_y->m_p_left;
00211 else
00212 {
00213 p_y = p_y->m_p_right;
00214
00215 while (p_y->m_p_left != NULL)
00216 p_y = p_y->m_p_left;
00217
00218 p_x = p_y->m_p_right;
00219 }
00220
00221 if (p_y == p_z)
00222 {
00223 p_new_x_parent = p_y->m_p_parent;
00224
00225 if (p_x != NULL)
00226 p_x->m_p_parent = p_y->m_p_parent;
00227
00228 if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == p_z)
00229 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_x;
00230 else if (p_z->m_p_parent->m_p_left == p_z)
00231 {
00232 p_y->m_p_left = p_z->m_p_parent;
00233
00234 p_z->m_p_parent->m_p_left = p_x;
00235 }
00236 else
00237 {
00238 p_y->m_p_left = NULL;
00239
00240 p_z->m_p_parent->m_p_right = p_x;
00241 }
00242 }
00243 else
00244 {
00245 p_z->m_p_left->m_p_parent = p_y;
00246
00247 p_y->m_p_left = p_z->m_p_left;
00248
00249 if (p_y != p_z->m_p_right)
00250 {
00251 p_new_x_parent = p_y->m_p_parent;
00252
00253 if (p_x != NULL)
00254 p_x->m_p_parent = p_y->m_p_parent;
00255
00256 p_y->m_p_parent->m_p_left = p_x;
00257
00258 p_y->m_p_right = p_z->m_p_right;
00259
00260 p_z->m_p_right->m_p_parent = p_y;
00261 }
00262 else
00263 p_new_x_parent = p_y;
00264
00265 if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == p_z)
00266 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_y;
00267 else if (p_z->m_p_parent->m_p_left == p_z)
00268 p_z->m_p_parent->m_p_left = p_y;
00269 else
00270 p_z->m_p_parent->m_p_right = p_y;
00271
00272 p_y->m_p_parent = p_z->m_p_parent;
00273
00274 std::swap(p_y->m_red, p_z->m_red);
00275
00276 p_y = p_z;
00277 }
00278
00279 update_to_top(p_new_x_parent, (Node_Updator* )this);
00280
00281 if (p_y->m_red)
00282 return;
00283
00284 remove_fixup(p_x, p_new_x_parent);
00285 }
00286
00287 PB_ASSOC_CLASS_T_DEC
00288 void
00289 PB_ASSOC_CLASS_C_DEC::
00290 remove_fixup(node_pointer p_x, node_pointer p_new_x_parent)
00291 {
00292 PB_ASSOC_DBG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent);
00293
00294 while (p_x != PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent&&
00295 is_effectively_black(p_x))
00296 if (p_x == p_new_x_parent->m_p_left)
00297 {
00298 node_pointer p_w = p_new_x_parent->m_p_right;
00299
00300 if (p_w->m_red)
00301 {
00302 p_w->m_red = false;
00303
00304 p_new_x_parent->m_red = true;
00305
00306 PB_ASSOC_BASE_C_DEC::rotate_left(p_new_x_parent);
00307
00308 p_w = p_new_x_parent->m_p_right;
00309 }
00310
00311 if (is_effectively_black(p_w->m_p_left)&&
00312 is_effectively_black(p_w->m_p_right))
00313 {
00314 p_w->m_red = true;
00315
00316 p_x = p_new_x_parent;
00317
00318 p_new_x_parent = p_new_x_parent->m_p_parent;
00319 }
00320 else
00321 {
00322 if (is_effectively_black(p_w->m_p_right))
00323 {
00324 if (p_w->m_p_left != NULL)
00325 p_w->m_p_left->m_red = false;
00326
00327 p_w->m_red = true;
00328
00329 PB_ASSOC_BASE_C_DEC::rotate_right(p_w);
00330
00331 p_w = p_new_x_parent->m_p_right;
00332 }
00333
00334 p_w->m_red = p_new_x_parent->m_red;
00335
00336 p_new_x_parent->m_red = false;
00337
00338 if (p_w->m_p_right != NULL)
00339 p_w->m_p_right->m_red = false;
00340
00341 PB_ASSOC_BASE_C_DEC::rotate_left(p_new_x_parent);
00342
00343 update_to_top(p_new_x_parent, (Node_Updator* )this);
00344
00345 break;
00346 }
00347 }
00348 else
00349 {
00350 node_pointer p_w = p_new_x_parent->m_p_left;
00351
00352 if (p_w->m_red == true)
00353 {
00354 p_w->m_red = false;
00355
00356 p_new_x_parent->m_red = true;
00357
00358 PB_ASSOC_BASE_C_DEC::rotate_right(p_new_x_parent);
00359
00360 p_w = p_new_x_parent->m_p_left;
00361 }
00362
00363 if (is_effectively_black(p_w->m_p_right)&&
00364 is_effectively_black(p_w->m_p_left))
00365 {
00366 p_w->m_red = true;
00367
00368 p_x = p_new_x_parent;
00369
00370 p_new_x_parent = p_new_x_parent->m_p_parent;
00371 }
00372 else
00373 {
00374 if (is_effectively_black(p_w->m_p_left))
00375 {
00376 if (p_w->m_p_right != NULL)
00377 p_w->m_p_right->m_red = false;
00378
00379 p_w->m_red = true;
00380
00381 PB_ASSOC_BASE_C_DEC::rotate_left(p_w);
00382
00383 p_w = p_new_x_parent->m_p_left;
00384 }
00385
00386 p_w->m_red = p_new_x_parent->m_red;
00387
00388 p_new_x_parent->m_red = false;
00389
00390 if (p_w->m_p_left != NULL)
00391 p_w->m_p_left->m_red = false;
00392
00393 PB_ASSOC_BASE_C_DEC::rotate_right(p_new_x_parent);
00394
00395 update_to_top(p_new_x_parent, (Node_Updator* )this);
00396
00397 break;
00398 }
00399 }
00400
00401 if (p_x != NULL)
00402 p_x->m_red = false;
00403 }