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(PB_ASSOC_CLASS_C_DEC::assert_valid());
00066
00067 if (it == PB_ASSOC_BASE_C_DEC::find_end())
00068 return (it);
00069
00070 const_iterator ret_it = it;
00071
00072 ++ret_it;
00073
00074 erase_node(it.m_p_nd);
00075
00076 return (ret_it);
00077 }
00078
00079 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00080 PB_ASSOC_CLASS_T_DEC
00081 inline typename PB_ASSOC_CLASS_C_DEC::iterator
00082 PB_ASSOC_CLASS_C_DEC::
00083 erase(iterator it)
00084 {
00085 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00086 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00087
00088 if (it == PB_ASSOC_BASE_C_DEC::find_end())
00089 return (it);
00090
00091 iterator ret_it = it;
00092
00093 ++ret_it;
00094
00095 erase_node(it.m_p_nd);
00096
00097 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00098 PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_iterators();)
00099
00100 return (ret_it);
00101 }
00102 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00103
00104 PB_ASSOC_CLASS_T_DEC
00105 inline typename PB_ASSOC_CLASS_C_DEC::const_reverse_iterator
00106 PB_ASSOC_CLASS_C_DEC::
00107 erase(const_reverse_iterator it)
00108 {
00109 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00110
00111 if (it == PB_ASSOC_BASE_C_DEC::find_rend())
00112 return (it);
00113
00114 const_reverse_iterator ret_it = it;
00115
00116 ++ret_it;
00117
00118 erase_node(it.m_p_nd);
00119
00120 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00121
00122 return (ret_it);
00123 }
00124
00125 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00126 PB_ASSOC_CLASS_T_DEC
00127 inline typename PB_ASSOC_CLASS_C_DEC::reverse_iterator
00128 PB_ASSOC_CLASS_C_DEC::
00129 erase(reverse_iterator it)
00130 {
00131 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00132
00133 if (it == PB_ASSOC_BASE_C_DEC::find_rend())
00134 return (it);
00135
00136 reverse_iterator ret_it = it;
00137
00138 ++ret_it;
00139
00140 erase_node(it.m_p_nd);
00141
00142 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid());
00143
00144 return (ret_it);
00145 }
00146 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00147
00148 PB_ASSOC_CLASS_T_DEC
00149 template<class Pred>
00150 inline typename PB_ASSOC_CLASS_C_DEC::size_type
00151 PB_ASSOC_CLASS_C_DEC::
00152 erase_if(Pred pred)
00153 {
00154 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00155
00156 size_type num_ersd = 0;
00157
00158 iterator it = PB_ASSOC_BASE_C_DEC::begin();
00159
00160 while (it != PB_ASSOC_BASE_C_DEC::end())
00161 if (pred(*it))
00162 {
00163 ++num_ersd;
00164
00165 it = erase(it);
00166 }
00167 else
00168 ++it;
00169
00170 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00171
00172 return (num_ersd);
00173 }
00174
00175 PB_ASSOC_CLASS_T_DEC
00176 void
00177 PB_ASSOC_CLASS_C_DEC::
00178 erase_node(node_pointer p_nd)
00179 {
00180 PB_ASSOC_DBG_ASSERT(p_nd != NULL);
00181
00182 splay(p_nd);
00183
00184 PB_ASSOC_DBG_ONLY(assert_valid();)
00185 PB_ASSOC_DBG_ASSERT(p_nd == PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent);
00186
00187 node_pointer p_l = p_nd->m_p_left;
00188 node_pointer p_r = p_nd->m_p_right;
00189
00190 PB_ASSOC_BASE_C_DEC::update_min_max_for_erased_node(p_nd);
00191
00192 PB_ASSOC_BASE_C_DEC::actual_erase_node(p_nd);
00193
00194 if (p_r == NULL)
00195 {
00196 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_l;
00197
00198 if (p_l != NULL)
00199 p_l->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00200
00201 PB_ASSOC_DBG_ONLY(assert_valid();)
00202
00203 return;
00204 }
00205
00206 node_pointer p_target_r = leftmost(p_r);
00207
00208 PB_ASSOC_DBG_ASSERT(p_target_r != NULL);
00209
00210 p_r->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
00211
00212 PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_r;
00213
00214 splay(p_target_r);
00215
00216 PB_ASSOC_DBG_ONLY(p_target_r->m_p_left = NULL);
00217
00218 PB_ASSOC_DBG_ASSERT(p_target_r->m_p_parent ==
00219 PB_ASSOC_BASE_C_DEC::m_p_head);
00220
00221 PB_ASSOC_DBG_ASSERT(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent ==
00222 p_target_r);
00223
00224 p_target_r->m_p_left = p_l;
00225
00226 if (p_l != NULL)
00227 p_l->m_p_parent = p_target_r;
00228
00229 PB_ASSOC_DBG_ONLY(assert_valid();)
00230
00231 apply_update(p_target_r, (Node_Updator* )this);
00232 }
00233
00234 PB_ASSOC_CLASS_T_DEC
00235 inline typename PB_ASSOC_CLASS_C_DEC::node_pointer
00236 PB_ASSOC_CLASS_C_DEC::
00237 leftmost(node_pointer p_nd)
00238 {
00239 PB_ASSOC_DBG_ASSERT(p_nd != NULL);
00240
00241 while (p_nd->m_p_left != NULL)
00242 p_nd = p_nd->m_p_left;
00243
00244 return (p_nd);
00245 }