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 typename PB_ASSOC_CLASS_C_DEC::node_allocator
00047 PB_ASSOC_CLASS_C_DEC::s_node_allocator;
00048
00049 PB_ASSOC_CLASS_T_DEC
00050 PB_ASSOC_CLASS_C_DEC::
00051 PB_ASSOC_CLASS_NAME() :
00052 m_p_head(s_node_allocator.allocate(1)),
00053 m_end_it(m_p_head),
00054 m_rend_it(m_p_head),
00055 m_size(0)
00056 {
00057 initialize();
00058
00059 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00060 }
00061
00062 PB_ASSOC_CLASS_T_DEC
00063 PB_ASSOC_CLASS_C_DEC::
00064 PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
00065 Cmp_Fn(r_cmp_fn),
00066 m_p_head(s_node_allocator.allocate(1)),
00067 m_end_it(m_p_head),
00068 m_rend_it(m_p_head),
00069 m_size(0)
00070 {
00071 initialize();
00072
00073 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00074 }
00075
00076 PB_ASSOC_CLASS_T_DEC
00077 PB_ASSOC_CLASS_C_DEC::
00078 PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator) :
00079 Cmp_Fn(r_cmp_fn),
00080 Node_Updator(r_node_updator),
00081 m_p_head(s_node_allocator.allocate(1)),
00082 m_end_it(m_p_head),
00083 m_rend_it(m_p_head),
00084 m_size(0)
00085 {
00086 initialize();
00087
00088 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00089 }
00090
00091 PB_ASSOC_CLASS_T_DEC
00092 PB_ASSOC_CLASS_C_DEC::
00093 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other) :
00094 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00095 my_map_debug_base(r_other),
00096 #endif
00097 Cmp_Fn(r_other),
00098 Node_Updator(r_other),
00099 m_p_head(s_node_allocator.allocate(1)),
00100 m_end_it(m_p_head),
00101 m_rend_it(m_p_head),
00102 m_size(0)
00103 {
00104 initialize();
00105
00106 m_size = r_other.m_size;
00107
00108 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00109
00110 try
00111 {
00112 m_p_head->m_p_parent =
00113 recursive_copy_node(r_other.m_p_head->m_p_parent);
00114
00115 if (m_p_head->m_p_parent != NULL)
00116 m_p_head->m_p_parent->m_p_parent = m_p_head;
00117
00118 m_size = r_other.m_size;
00119
00120 initialize_min_max();
00121 }
00122 catch(...)
00123 {
00124 PB_ASSOC_DBG_ONLY(my_map_debug_base::clear();)
00125
00126 s_node_allocator.deallocate(m_p_head, 1);
00127
00128 throw;
00129 }
00130
00131 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00132 }
00133
00134 PB_ASSOC_CLASS_T_DEC
00135 void
00136 PB_ASSOC_CLASS_C_DEC::
00137 swap(PB_ASSOC_CLASS_C_DEC& r_other)
00138 {
00139 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00140 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00141
00142 PB_ASSOC_DBG_ONLY(my_map_debug_base::swap(r_other);)
00143
00144 std::swap(m_p_head, r_other.m_p_head);
00145
00146 std::swap(m_size, r_other.m_size);
00147
00148 std::swap(m_end_it, r_other.m_end_it);
00149
00150 std::swap(m_rend_it, r_other.m_rend_it);
00151
00152 std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )r_other);
00153
00154 Node_Updator::swap(r_other);
00155
00156 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00157 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00158 }
00159
00160 PB_ASSOC_CLASS_T_DEC
00161 PB_ASSOC_CLASS_C_DEC::
00162 ~PB_ASSOC_CLASS_NAME()
00163 {
00164 clear();
00165
00166 s_node_allocator.deallocate(m_p_head, 1);
00167 }
00168
00169 PB_ASSOC_CLASS_T_DEC
00170 void
00171 PB_ASSOC_CLASS_C_DEC::
00172 initialize()
00173 {
00174 m_p_head->m_p_parent = NULL;
00175 m_p_head->m_p_left = m_p_head;
00176 m_p_head->m_p_right = m_p_head;
00177
00178 m_size = 0;
00179 }
00180
00181 PB_ASSOC_CLASS_T_DEC
00182 typename PB_ASSOC_CLASS_C_DEC::node_pointer
00183 PB_ASSOC_CLASS_C_DEC::
00184 recursive_copy_node(const node_pointer p_nd)
00185 {
00186 if (p_nd == NULL)
00187 return (NULL);
00188
00189 node_pointer p_ret = s_node_allocator.allocate(1);
00190
00191 try
00192 {
00193 new (p_ret) node(*p_nd);
00194 }
00195 catch(...)
00196 {
00197 s_node_allocator.deallocate(p_ret, 1);
00198
00199 throw;
00200 }
00201
00202 p_ret->m_p_left = p_ret->m_p_right = NULL;
00203
00204 try
00205 {
00206 p_ret->m_p_left = recursive_copy_node(p_nd->m_p_left);
00207
00208 p_ret->m_p_right = recursive_copy_node(p_nd->m_p_right);
00209 }
00210 catch(...)
00211 {
00212 clear_imp(p_ret);
00213
00214 throw;
00215 }
00216
00217 if (p_ret->m_p_left != NULL)
00218 p_ret->m_p_left->m_p_parent = p_ret;
00219
00220 if (p_ret->m_p_right != NULL)
00221 p_ret->m_p_right->m_p_parent = p_ret;
00222
00223 PB_ASSOC_DBG_ONLY(assert_node_consistent(p_ret);)
00224
00225 return (p_ret);
00226 }
00227
00228 PB_ASSOC_CLASS_T_DEC
00229 void
00230 PB_ASSOC_CLASS_C_DEC::
00231 initialize_min_max()
00232 {
00233 if (m_p_head->m_p_parent == NULL)
00234 {
00235 m_p_head->m_p_left = m_p_head->m_p_right = m_p_head;
00236
00237 return;
00238 }
00239
00240 {
00241 node_pointer p_min = m_p_head->m_p_parent;
00242
00243 while (p_min->m_p_left != NULL)
00244 p_min = p_min->m_p_left;
00245
00246 m_p_head->m_p_left = p_min;
00247 }
00248
00249 {
00250 node_pointer p_max = m_p_head->m_p_parent;
00251
00252 while (p_max->m_p_right != NULL)
00253 p_max = p_max->m_p_right;
00254
00255 m_p_head->m_p_right = p_max;
00256 }
00257 }
00258