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
00040
00041
00042
00043
00044
00045 PB_ASSOC_CLASS_T_DEC
00046 inline std::pair<typename PB_ASSOC_CLASS_C_DEC::find_iterator, bool>
00047 PB_ASSOC_CLASS_C_DEC::
00048 insert(const_reference r_value)
00049 {
00050 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00051
00052 std::pair<find_iterator, bool> ins_pair =
00053 PB_ASSOC_BASE_C_DEC::insert_leaf(r_value);
00054
00055 if (ins_pair.second == true)
00056 {
00057 ins_pair.first.m_p_nd->m_red = true;
00058
00059 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(false, true);)
00060
00061 insert_fixup(ins_pair.first.m_p_nd);
00062 }
00063
00064 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
00065 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00066
00067 return (ins_pair);
00068 }
00069
00070 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00071 PB_ASSOC_CLASS_T_DEC
00072 inline typename PB_ASSOC_CLASS_C_DEC::data_reference
00073 PB_ASSOC_CLASS_C_DEC::
00074 subscript_imp(const_key_reference r_key)
00075 {
00076 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00077
00078 std::pair<find_iterator, bool> ins_pair =
00079 PB_ASSOC_BASE_C_DEC::insert_leaf(
00080 value_type(r_key, data_type()));
00081
00082 if (ins_pair.second == true)
00083 {
00084 ins_pair.first.m_p_nd->m_red = true;
00085
00086 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid());
00087
00088 insert_fixup(ins_pair.first.m_p_nd);
00089 }
00090
00091 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00092 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00093
00094 return (ins_pair.first.m_p_nd->m_value.second);
00095 }
00096 #endif // #ifdef PB_ASSOC_DATA_TRUE
00097
00098 PB_ASSOC_CLASS_T_DEC
00099 inline void
00100 PB_ASSOC_CLASS_C_DEC::
00101 insert_fixup(node_pointer p_nd)
00102 {
00103 PB_ASSOC_DBG_ASSERT(p_nd->m_red == true);
00104
00105 while (p_nd != PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent&&
00106 p_nd->m_p_parent->m_red)
00107 {
00108 if (p_nd->m_p_parent == p_nd->m_p_parent->m_p_parent->m_p_left)
00109 {
00110 node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_right;
00111
00112 if (p_y != NULL&& p_y->m_red)
00113 {
00114 p_nd->m_p_parent->m_red = false;
00115
00116 p_y->m_red = false;
00117
00118 p_nd->m_p_parent->m_p_parent->m_red = true;
00119
00120 p_nd = p_nd->m_p_parent->m_p_parent;
00121 }
00122 else
00123 {
00124 if (p_nd == p_nd->m_p_parent->m_p_right)
00125 {
00126 p_nd = p_nd->m_p_parent;
00127
00128 PB_ASSOC_BASE_C_DEC::rotate_left(p_nd);
00129 }
00130
00131 p_nd->m_p_parent->m_red = false;
00132
00133 p_nd->m_p_parent->m_p_parent->m_red = true;
00134
00135 PB_ASSOC_BASE_C_DEC::rotate_right(
00136 p_nd->m_p_parent->m_p_parent);
00137 }
00138 }
00139 else
00140 {
00141 node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_left;
00142
00143 if (p_y != NULL&& p_y->m_red)
00144 {
00145 p_nd->m_p_parent->m_red = false;
00146
00147 p_y->m_red = false;
00148
00149 p_nd->m_p_parent->m_p_parent->m_red = true;
00150
00151 p_nd = p_nd->m_p_parent->m_p_parent;
00152 }
00153 else
00154 {
00155 if (p_nd == p_nd->m_p_parent->m_p_left)
00156 {
00157 p_nd = p_nd->m_p_parent;
00158
00159 PB_ASSOC_BASE_C_DEC::rotate_right(p_nd);
00160 }
00161
00162 p_nd->m_p_parent->m_red = false;
00163
00164 p_nd->m_p_parent->m_p_parent->m_red = true;
00165
00166 PB_ASSOC_BASE_C_DEC::rotate_left(
00167 p_nd->m_p_parent->m_p_parent);
00168 }
00169 }
00170 }
00171
00172 PB_ASSOC_BASE_C_DEC::update_to_top(p_nd, (Node_Updator* )this);
00173
00174 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent->m_red = false;
00175 }
00176