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 void
00047 PB_ASSOC_CLASS_C_DEC::
00048 splay(node_pointer p_nd)
00049 {
00050 while (p_nd->m_p_parent != PB_ASSOC_BASE_C_DEC::m_p_head)
00051 {
00052 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_node_consistent(p_nd);)
00053
00054 if (p_nd->m_p_parent->m_p_parent ==
00055 PB_ASSOC_BASE_C_DEC::m_p_head)
00056 {
00057 PB_ASSOC_BASE_C_DEC::rotate_parent(p_nd);
00058
00059 PB_ASSOC_DBG_ASSERT(p_nd ==
00060 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent);
00061 }
00062 else
00063 {
00064 const node_pointer p_parent = p_nd->m_p_parent;
00065 const node_pointer p_grandparent = p_parent->m_p_parent;
00066
00067 #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00068 const size_type total =
00069 PB_ASSOC_BASE_C_DEC::recursive_count(p_grandparent);
00070
00071 PB_ASSOC_DBG_ASSERT(total >= 3);
00072 #endif // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00073
00074 if (p_parent->m_p_left == p_nd&&
00075 p_grandparent->m_p_right == p_parent)
00076 splay_zig_zag_left(p_nd, p_parent, p_grandparent);
00077 else if (p_parent->m_p_right == p_nd&&
00078 p_grandparent->m_p_left == p_parent)
00079 splay_zig_zag_right(p_nd, p_parent, p_grandparent);
00080 else if (p_parent->m_p_left == p_nd&&
00081 p_grandparent->m_p_left == p_parent)
00082 splay_zig_zig_left(p_nd, p_parent, p_grandparent);
00083 else
00084 splay_zig_zig_right(p_nd, p_parent, p_grandparent);
00085
00086 PB_ASSOC_DBG_ASSERT(total ==
00087 PB_ASSOC_BASE_C_DEC::recursive_count(p_nd));
00088 }
00089
00090 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_nd);)
00091 }
00092 }
00093
00094 PB_ASSOC_CLASS_T_DEC
00095 inline void
00096 PB_ASSOC_CLASS_C_DEC::
00097 splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
00098 {
00099 PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
00100 PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
00101
00102 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_grandparent);)
00103
00104 PB_ASSOC_DBG_ASSERT(p_parent->m_p_left == p_nd&&
00105 p_grandparent->m_p_right == p_parent);
00106
00107 splay_zz_start(p_nd, p_parent, p_grandparent);
00108
00109 node_pointer p_b = p_nd->m_p_right;
00110 node_pointer p_c = p_nd->m_p_left;
00111
00112 p_nd->m_p_right = p_parent;
00113 p_parent->m_p_parent = p_nd;
00114
00115 p_nd->m_p_left = p_grandparent;
00116 p_grandparent->m_p_parent = p_nd;
00117
00118 p_parent->m_p_left = p_b;
00119 if (p_b != NULL)
00120 p_b->m_p_parent = p_parent;
00121
00122 p_grandparent->m_p_right = p_c;
00123 if (p_c != NULL)
00124 p_c->m_p_parent = p_grandparent;
00125
00126 splay_zz_end(p_nd, p_parent, p_grandparent);
00127 }
00128
00129 PB_ASSOC_CLASS_T_DEC
00130 inline void
00131 PB_ASSOC_CLASS_C_DEC::
00132 splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
00133 {
00134 PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
00135 PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
00136
00137 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_grandparent);)
00138
00139 PB_ASSOC_DBG_ASSERT(p_parent->m_p_right == p_nd&&
00140 p_grandparent->m_p_left == p_parent);
00141
00142 splay_zz_start(p_nd, p_parent, p_grandparent);
00143
00144 node_pointer p_b = p_nd->m_p_left;
00145 node_pointer p_c = p_nd->m_p_right;
00146
00147 p_nd->m_p_left = p_parent;
00148 p_parent->m_p_parent = p_nd;
00149
00150 p_nd->m_p_right = p_grandparent;
00151 p_grandparent->m_p_parent = p_nd;
00152
00153 p_parent->m_p_right = p_b;
00154 if (p_b != NULL)
00155 p_b->m_p_parent = p_parent;
00156
00157 p_grandparent->m_p_left = p_c;
00158 if (p_c != NULL)
00159 p_c->m_p_parent = p_grandparent;
00160
00161 splay_zz_end(p_nd, p_parent, p_grandparent);
00162 }
00163
00164 PB_ASSOC_CLASS_T_DEC
00165 inline void
00166 PB_ASSOC_CLASS_C_DEC::
00167 splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
00168 {
00169 PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
00170 PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
00171
00172 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_grandparent);)
00173
00174 PB_ASSOC_DBG_ASSERT(p_parent->m_p_left == p_nd&&
00175 p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent);
00176
00177 splay_zz_start(p_nd, p_parent, p_grandparent);
00178
00179 node_pointer p_b = p_nd->m_p_right;
00180 node_pointer p_c = p_parent->m_p_right;
00181
00182 p_nd->m_p_right = p_parent;
00183 p_parent->m_p_parent = p_nd;
00184
00185 p_parent->m_p_right = p_grandparent;
00186 p_grandparent->m_p_parent = p_parent;
00187
00188 p_parent->m_p_left = p_b;
00189 if (p_b != NULL)
00190 p_b->m_p_parent = p_parent;
00191
00192 p_grandparent->m_p_left = p_c;
00193 if (p_c != NULL)
00194 p_c->m_p_parent = p_grandparent;
00195
00196 splay_zz_end(p_nd, p_parent, p_grandparent);
00197 }
00198
00199 PB_ASSOC_CLASS_T_DEC
00200 inline void
00201 PB_ASSOC_CLASS_C_DEC::
00202 splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
00203 {
00204 PB_ASSOC_DBG_ASSERT(p_parent == p_nd->m_p_parent);
00205 PB_ASSOC_DBG_ASSERT(p_grandparent == p_parent->m_p_parent);
00206
00207 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_grandparent);)
00208
00209 PB_ASSOC_DBG_ASSERT(p_parent->m_p_right == p_nd&&
00210 p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent);
00211
00212 splay_zz_start(p_nd, p_parent, p_grandparent);
00213
00214 node_pointer p_b = p_nd->m_p_left;
00215 node_pointer p_c = p_parent->m_p_left;
00216
00217 p_nd->m_p_left = p_parent;
00218 p_parent->m_p_parent = p_nd;
00219
00220 p_parent->m_p_left = p_grandparent;
00221 p_grandparent->m_p_parent = p_parent;
00222
00223 p_parent->m_p_right = p_b;
00224 if (p_b != NULL)
00225 p_b->m_p_parent = p_parent;
00226
00227 p_grandparent->m_p_right = p_c;
00228 if (p_c != NULL)
00229 p_c->m_p_parent = p_grandparent;
00230
00231 PB_ASSOC_BASE_C_DEC::update_to_top(
00232 p_grandparent, (Node_Updator* )this);
00233
00234 splay_zz_end(p_nd, p_parent, p_grandparent);
00235 }
00236
00237 PB_ASSOC_CLASS_T_DEC
00238 inline void
00239 PB_ASSOC_CLASS_C_DEC::
00240 splay_zz_start(node_pointer p_nd,
00241 #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00242 node_pointer p_parent,
00243 #else
00244 node_pointer ,
00245 #endif
00246 node_pointer p_grandparent)
00247 {
00248 PB_ASSOC_DBG_ASSERT(p_nd != NULL);
00249 PB_ASSOC_DBG_ASSERT(p_parent != NULL);
00250 PB_ASSOC_DBG_ASSERT(p_grandparent != NULL);
00251
00252 const bool grandparent_head =
00253 p_grandparent->m_p_parent == PB_ASSOC_BASE_C_DEC::m_p_head;
00254
00255 if (grandparent_head)
00256 {
00257 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent =
00258 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent;
00259
00260 p_nd->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00261
00262 return;
00263 }
00264
00265 node_pointer p_greatgrandparent = p_grandparent->m_p_parent;
00266
00267 p_nd->m_p_parent = p_greatgrandparent;
00268
00269 if (p_grandparent == p_greatgrandparent->m_p_left)
00270 p_greatgrandparent->m_p_left = p_nd;
00271 else
00272 p_greatgrandparent->m_p_right = p_nd;
00273 }
00274
00275 PB_ASSOC_CLASS_T_DEC
00276 inline void
00277 PB_ASSOC_CLASS_C_DEC::
00278 splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent)
00279 {
00280 if (p_nd->m_p_parent == PB_ASSOC_BASE_C_DEC::m_p_head)
00281 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_nd;
00282
00283 apply_update(p_grandparent, (Node_Updator* )this);
00284 apply_update(p_parent, (Node_Updator* )this);
00285 apply_update(p_nd, (Node_Updator* )this);
00286
00287 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_nd);)
00288 }
00289