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 void
00047 PB_ASSOC_CLASS_C_DEC::
00048 join(PB_ASSOC_CLASS_C_DEC& r_other)
00049 {
00050 PB_ASSOC_DBG_ONLY(assert_valid();)
00051 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00052
00053 PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
00054 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00055
00056 if (PB_ASSOC_BASE_C_DEC::join_prep(r_other) == false)
00057 {
00058 PB_ASSOC_DBG_ONLY(assert_valid();)
00059 PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
00060
00061 return;
00062 }
00063
00064 const node_pointer p_x = r_other.split_min();
00065
00066 join_imp(p_x, r_other.m_p_head->m_p_parent);
00067
00068 PB_ASSOC_BASE_C_DEC::join_finish(r_other);
00069
00070 PB_ASSOC_DBG_ONLY(assert_valid();)
00071 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00072
00073 PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
00074 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00075 }
00076
00077 PB_ASSOC_CLASS_T_DEC
00078 void
00079 PB_ASSOC_CLASS_C_DEC::
00080 join_imp(node_pointer p_x, node_pointer p_r)
00081 {
00082 PB_ASSOC_DBG_ASSERT(p_x != NULL);
00083
00084 if (p_r != NULL)
00085 p_r->m_red = false;
00086
00087 const size_type h =
00088 black_height(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent);
00089 const size_type other_h = black_height(p_r);
00090
00091 node_pointer p_x_l;
00092 node_pointer p_x_r;
00093
00094 std::pair<node_pointer, node_pointer> join_pos;
00095
00096 const bool right_join = h >= other_h;
00097
00098 if (right_join)
00099 {
00100 join_pos = find_join_pos_right(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent, h, other_h);
00101
00102 p_x_l = join_pos.first;
00103 p_x_r = p_r;
00104 }
00105 else
00106 {
00107 p_x_l = PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent;
00108
00109 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_r;
00110 if (p_r != NULL)
00111 p_r->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00112
00113 join_pos = find_join_pos_left(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent, h, other_h);
00114
00115 p_x_r = join_pos.first;
00116 }
00117
00118 node_pointer p_parent = join_pos.second;
00119
00120 if (p_parent == PB_ASSOC_BASE_C_DEC::m_p_head)
00121 {
00122 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_x;
00123
00124 p_x->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00125 }
00126 else
00127 {
00128 p_x->m_p_parent = p_parent;
00129
00130 if (right_join)
00131 p_x->m_p_parent->m_p_right = p_x;
00132 else
00133 p_x->m_p_parent->m_p_left = p_x;
00134 }
00135
00136 p_x->m_p_left = p_x_l;
00137 if (p_x_l != NULL)
00138 p_x_l->m_p_parent = p_x;
00139
00140 p_x->m_p_right = p_x_r;
00141 if (p_x_r != NULL)
00142 p_x_r->m_p_parent = p_x;
00143
00144 p_x->m_red = true;
00145
00146 PB_ASSOC_BASE_C_DEC::initialize_min_max();
00147
00148 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00149
00150 PB_ASSOC_BASE_C_DEC::update_to_top(p_x, (Node_Updator* )this);
00151
00152 insert_fixup(p_x);
00153
00154 PB_ASSOC_DBG_ONLY(assert_valid());
00155 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00156 }
00157
00158 PB_ASSOC_CLASS_T_DEC
00159 inline typename PB_ASSOC_CLASS_C_DEC::node_pointer
00160 PB_ASSOC_CLASS_C_DEC::
00161 split_min()
00162 {
00163 PB_ASSOC_DBG_ASSERT(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_left !=
00164 PB_ASSOC_BASE_C_DEC::m_p_head);
00165
00166 node_pointer p_min = PB_ASSOC_BASE_C_DEC::m_p_head->m_p_left;
00167
00168 remove_node(p_min);
00169
00170 return (p_min);
00171 }
00172
00173 PB_ASSOC_CLASS_T_DEC
00174 std::pair<
00175 typename PB_ASSOC_CLASS_C_DEC::node_pointer,
00176 typename PB_ASSOC_CLASS_C_DEC::node_pointer>
00177 PB_ASSOC_CLASS_C_DEC::
00178 find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
00179 {
00180 PB_ASSOC_DBG_ASSERT(h_l >= h_r);
00181
00182 if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == NULL)
00183 return (std::make_pair((node_pointer)NULL,
00184 PB_ASSOC_BASE_C_DEC::m_p_head));
00185
00186 node_pointer p_l_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00187
00188 while (h_l > h_r)
00189 {
00190 if (p_l->m_red == false)
00191 {
00192 PB_ASSOC_DBG_ASSERT(h_l > 0);
00193
00194 --h_l;
00195 }
00196
00197 p_l_parent = p_l;
00198
00199 p_l = p_l->m_p_right;
00200 }
00201
00202 if (!is_effectively_black(p_l))
00203 {
00204 p_l_parent = p_l;
00205
00206 p_l = p_l->m_p_right;
00207 }
00208
00209 PB_ASSOC_DBG_ASSERT(is_effectively_black(p_l));
00210 PB_ASSOC_DBG_ASSERT(black_height(p_l) == h_r);
00211 PB_ASSOC_DBG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent);
00212
00213 return (std::make_pair(p_l, p_l_parent));
00214 }
00215
00216 PB_ASSOC_CLASS_T_DEC
00217 std::pair<
00218 typename PB_ASSOC_CLASS_C_DEC::node_pointer,
00219 typename PB_ASSOC_CLASS_C_DEC::node_pointer>
00220 PB_ASSOC_CLASS_C_DEC::
00221 find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
00222 {
00223 PB_ASSOC_DBG_ASSERT(h_r > h_l);
00224
00225 if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == NULL)
00226 return (std::make_pair((node_pointer)NULL,
00227 PB_ASSOC_BASE_C_DEC::m_p_head));
00228
00229 node_pointer p_r_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00230
00231 while (h_r > h_l)
00232 {
00233 if (p_r->m_red == false)
00234 {
00235 PB_ASSOC_DBG_ASSERT(h_r > 0);
00236
00237 --h_r;
00238 }
00239
00240 p_r_parent = p_r;
00241
00242 p_r = p_r->m_p_left;
00243 }
00244
00245 if (!is_effectively_black(p_r))
00246 {
00247 p_r_parent = p_r;
00248
00249 p_r = p_r->m_p_left;
00250 }
00251
00252 PB_ASSOC_DBG_ASSERT(is_effectively_black(p_r));
00253 PB_ASSOC_DBG_ASSERT(black_height(p_r) == h_l);
00254 PB_ASSOC_DBG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent);
00255
00256 return (std::make_pair(p_r, p_r_parent));
00257 }
00258
00259 PB_ASSOC_CLASS_T_DEC
00260 inline typename PB_ASSOC_CLASS_C_DEC::size_type
00261 PB_ASSOC_CLASS_C_DEC::
00262 black_height(node_pointer p_nd)
00263 {
00264 size_type h = 1;
00265
00266 while (p_nd != NULL)
00267 {
00268 if (p_nd->m_red == false)
00269 ++h;
00270
00271 p_nd = p_nd->m_p_left;
00272 }
00273
00274 return (h);
00275 }
00276
00277 PB_ASSOC_CLASS_T_DEC
00278 void
00279 PB_ASSOC_CLASS_C_DEC::
00280 split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other)
00281 {
00282 PB_ASSOC_DBG_ONLY(assert_valid());
00283 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00284
00285 PB_ASSOC_DBG_ONLY(r_other.assert_valid());
00286 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00287
00288 if (PB_ASSOC_BASE_C_DEC::split_prep(r_key, r_other) == false)
00289 {
00290 PB_ASSOC_DBG_ONLY(assert_valid());
00291 PB_ASSOC_DBG_ONLY(r_other.assert_valid());
00292
00293 return;
00294 }
00295
00296 PB_ASSOC_DBG_ONLY(assert_valid());
00297 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00298
00299 PB_ASSOC_DBG_ONLY(r_other.assert_valid());
00300 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00301
00302 node_pointer p_nd = upper_bound(r_key).m_p_nd;
00303
00304 do
00305 {
00306 node_pointer p_next_nd = p_nd->m_p_parent;
00307
00308 if (Cmp_Fn::operator()(
00309 r_key,
00310 PB_ASSOC_V2F(p_nd->m_value)))
00311 split_at_node(p_nd, r_other);
00312
00313 PB_ASSOC_DBG_ONLY(assert_valid());
00314 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00315
00316 PB_ASSOC_DBG_ONLY(r_other.assert_valid());
00317 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00318
00319 p_nd = p_next_nd;
00320 }
00321 while (p_nd != PB_ASSOC_BASE_C_DEC::m_p_head);
00322
00323 PB_ASSOC_BASE_C_DEC::split_finish(r_other);
00324
00325 PB_ASSOC_DBG_ONLY(assert_valid());
00326 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00327
00328 PB_ASSOC_DBG_ONLY(r_other.assert_valid());
00329 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00330 }
00331
00332 PB_ASSOC_CLASS_T_DEC
00333 void
00334 PB_ASSOC_CLASS_C_DEC::
00335 split_at_node(node_pointer p_nd, PB_ASSOC_CLASS_C_DEC& r_other)
00336 {
00337 PB_ASSOC_DBG_ASSERT(p_nd != NULL);
00338
00339 node_pointer p_l = p_nd->m_p_left;
00340 node_pointer p_r = p_nd->m_p_right;
00341
00342 node_pointer p_parent = p_nd->m_p_parent;
00343
00344 if (p_parent == PB_ASSOC_BASE_C_DEC::m_p_head)
00345 {
00346 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_l;
00347
00348 if (p_l != NULL)
00349 {
00350 p_l->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00351
00352 p_l->m_red = false;
00353 }
00354 }
00355 else
00356 {
00357 if (p_parent->m_p_left == p_nd)
00358 p_parent->m_p_left = p_l;
00359 else
00360 p_parent->m_p_right = p_l;
00361
00362 if (p_l != NULL)
00363 p_l->m_p_parent = p_parent;
00364
00365 update_to_top(p_parent, (Node_Updator* )this);
00366
00367 if (!p_nd->m_red)
00368 remove_fixup(p_l, p_parent);
00369 }
00370
00371 PB_ASSOC_BASE_C_DEC::initialize_min_max();
00372
00373 PB_ASSOC_DBG_ONLY(assert_valid());
00374 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00375
00376 PB_ASSOC_DBG_ONLY(r_other.assert_valid());
00377 PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
00378
00379 r_other.join_imp(p_nd, p_r);
00380 }
00381