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 rotate_left(node_pointer p_x)
00049 {
00050 node_pointer p_y = p_x->m_p_right;
00051
00052 p_x->m_p_right = p_y->m_p_left;
00053
00054 if (p_y->m_p_left != NULL)
00055 p_y->m_p_left->m_p_parent = p_x;
00056
00057 p_y->m_p_parent = p_x->m_p_parent;
00058
00059 if (p_x == m_p_head->m_p_parent)
00060 m_p_head->m_p_parent = p_y;
00061 else if (p_x == p_x->m_p_parent->m_p_left)
00062 p_x->m_p_parent->m_p_left = p_y;
00063 else
00064 p_x->m_p_parent->m_p_right = p_y;
00065
00066 p_y->m_p_left = p_x;
00067 p_x->m_p_parent = p_y;
00068
00069 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_x);)
00070 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_y);)
00071
00072 apply_update(p_x, (Node_Updator* )this);
00073 apply_update(p_x->m_p_parent, (Node_Updator* )this);
00074 }
00075
00076 PB_ASSOC_CLASS_T_DEC
00077 inline void
00078 PB_ASSOC_CLASS_C_DEC::
00079 rotate_right(node_pointer p_x)
00080 {
00081 node_pointer p_y = p_x->m_p_left;
00082
00083 p_x->m_p_left = p_y->m_p_right;
00084
00085 if (p_y->m_p_right != NULL)
00086 p_y->m_p_right->m_p_parent = p_x;
00087
00088 p_y->m_p_parent = p_x->m_p_parent;
00089
00090 if (p_x == m_p_head->m_p_parent)
00091 m_p_head->m_p_parent = p_y;
00092 else if (p_x == p_x->m_p_parent->m_p_right)
00093 p_x->m_p_parent->m_p_right = p_y;
00094 else
00095 p_x->m_p_parent->m_p_left = p_y;
00096
00097 p_y->m_p_right = p_x;
00098 p_x->m_p_parent = p_y;
00099
00100 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_x);)
00101 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_y);)
00102
00103 apply_update(p_x, (Node_Updator* )this);
00104 apply_update(p_x->m_p_parent, (Node_Updator* )this);
00105 }
00106
00107 PB_ASSOC_CLASS_T_DEC
00108 inline void
00109 PB_ASSOC_CLASS_C_DEC::
00110 rotate_parent(node_pointer p_nd)
00111 {
00112 node_pointer p_parent = p_nd->m_p_parent;
00113
00114 if (p_nd == p_parent->m_p_left)
00115 rotate_right(p_parent);
00116 else
00117 rotate_left(p_parent);
00118
00119 PB_ASSOC_DBG_ASSERT(p_parent->m_p_parent = p_nd);
00120 PB_ASSOC_DBG_ASSERT(p_nd->m_p_left == p_parent ||
00121 p_nd->m_p_right == p_parent);
00122 }
00123
00124 PB_ASSOC_CLASS_T_DEC
00125 inline void
00126 PB_ASSOC_CLASS_C_DEC::
00127 apply_update(node_pointer , pb_assoc::null_node_updator* )
00128 { }
00129
00130 PB_ASSOC_CLASS_T_DEC
00131 template<class Node_Updator_>
00132 inline void
00133 PB_ASSOC_CLASS_C_DEC::
00134 apply_update(node_pointer p_nd, Node_Updator_* p_updator)
00135 {
00136 p_updator->operator()(
00137 &PB_ASSOC_V2F(p_nd->m_value),(p_nd->m_p_left == NULL)?
00138 NULL :
00139 &PB_ASSOC_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == NULL)?
00140 NULL :
00141 &PB_ASSOC_V2F(p_nd->m_p_right->m_value));
00142 }
00143
00144 PB_ASSOC_CLASS_T_DEC
00145 template<class Node_Updator_>
00146 inline void
00147 PB_ASSOC_CLASS_C_DEC::
00148 update_to_top(node_pointer p_nd, Node_Updator_* p_updator)
00149 {
00150 while (p_nd != m_p_head)
00151 {
00152 apply_update(p_nd, p_updator);
00153
00154 p_nd = p_nd->m_p_parent;
00155 }
00156 }
00157
00158 PB_ASSOC_CLASS_T_DEC
00159 inline void
00160 PB_ASSOC_CLASS_C_DEC::
00161 update_to_top(node_pointer , pb_assoc::null_node_updator* )
00162 { }
00163