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 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00046
00047 PB_ASSOC_CLASS_T_DEC
00048 void
00049 PB_ASSOC_CLASS_C_DEC::
00050 assert_valid(bool check_iterators, bool check_metadata) const
00051 {
00052 PB_ASSOC_DBG_ASSERT(m_p_head != NULL);
00053
00054 if (m_p_head->m_p_parent == NULL)
00055 {
00056 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_left == m_p_head);
00057 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_right == m_p_head);
00058
00059 if (check_metadata)
00060 PB_ASSOC_DBG_ASSERT(m_size == 0);
00061 }
00062 else
00063 {
00064 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head);
00065
00066 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_left != m_p_head);
00067 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_right != m_p_head);
00068
00069 if (check_metadata)
00070 PB_ASSOC_DBG_ASSERT(m_size > 0);
00071 }
00072
00073 if (check_metadata)
00074 assert_size();
00075
00076 if (m_p_head->m_p_parent != NULL)
00077 assert_node_consistent(m_p_head->m_p_parent);
00078
00079 assert_min();
00080 assert_max();
00081
00082 if (check_metadata)
00083 assert_consistent_with_debug_base();
00084
00085 if (check_iterators&& check_metadata)
00086 assert_iterators();
00087 }
00088
00089 PB_ASSOC_CLASS_T_DEC
00090 void
00091 PB_ASSOC_CLASS_C_DEC::
00092 assert_node_consistent_with_left(const node_pointer p_nd) const
00093 {
00094 if (p_nd->m_p_left == NULL)
00095 return;
00096
00097 PB_ASSOC_DBG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd);
00098
00099 PB_ASSOC_DBG_ASSERT(!Cmp_Fn::operator()(
00100 PB_ASSOC_V2F(p_nd->m_value),
00101 PB_ASSOC_V2F(p_nd->m_p_left->m_value)));
00102 }
00103
00104 PB_ASSOC_CLASS_T_DEC
00105 void
00106 PB_ASSOC_CLASS_C_DEC::
00107 assert_node_consistent_with_right(const node_pointer p_nd) const
00108 {
00109 if (p_nd->m_p_right == NULL)
00110 return;
00111
00112 PB_ASSOC_DBG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd);
00113
00114 PB_ASSOC_DBG_ASSERT(!Cmp_Fn::operator()(
00115 PB_ASSOC_V2F(p_nd->m_p_right->m_value),
00116 PB_ASSOC_V2F(p_nd->m_value)));
00117 }
00118
00119 PB_ASSOC_CLASS_T_DEC
00120 void
00121 PB_ASSOC_CLASS_C_DEC::
00122 assert_min() const
00123 {
00124 assert_min_imp(m_p_head->m_p_parent);
00125 }
00126
00127 PB_ASSOC_CLASS_T_DEC
00128 void
00129 PB_ASSOC_CLASS_C_DEC::
00130 assert_min_imp(const node_pointer p_nd) const
00131 {
00132 if (p_nd == NULL)
00133 {
00134 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_left == m_p_head);
00135
00136 return;
00137 }
00138
00139 if (p_nd->m_p_left == NULL)
00140 {
00141 PB_ASSOC_DBG_ASSERT(p_nd == m_p_head->m_p_left);
00142
00143 return;
00144 }
00145
00146 assert_min_imp(p_nd->m_p_left);
00147 }
00148
00149 PB_ASSOC_CLASS_T_DEC
00150 void
00151 PB_ASSOC_CLASS_C_DEC::
00152 assert_max() const
00153 {
00154 assert_max_imp(m_p_head->m_p_parent);
00155 }
00156
00157 PB_ASSOC_CLASS_T_DEC
00158 void
00159 PB_ASSOC_CLASS_C_DEC::
00160 assert_max_imp(const node_pointer p_nd) const
00161 {
00162 if (p_nd == NULL)
00163 {
00164 PB_ASSOC_DBG_ASSERT(m_p_head->m_p_right == m_p_head);
00165
00166 return;
00167 }
00168
00169 if (p_nd->m_p_right == NULL)
00170 {
00171 PB_ASSOC_DBG_ASSERT(p_nd == m_p_head->m_p_right);
00172
00173 return;
00174 }
00175
00176 assert_max_imp(p_nd->m_p_right);
00177 }
00178
00179 PB_ASSOC_CLASS_T_DEC
00180 void
00181 PB_ASSOC_CLASS_C_DEC::
00182 assert_iterators() const
00183 {
00184 PB_ASSOC_DBG_ASSERT(m_end_it.m_p_nd == m_p_head);
00185 PB_ASSOC_DBG_ASSERT(m_rend_it.m_p_nd == m_p_head);
00186
00187 size_type iterated_num = 0;
00188
00189 const_iterator prev_it = end();
00190
00191 for (const_iterator it = begin(); it != end(); ++it)
00192 {
00193 ++iterated_num;
00194
00195 PB_ASSOC_DBG_ASSERT(lower_bound(
00196 PB_ASSOC_V2F(*it)).m_p_nd == it.m_p_nd);
00197
00198 const_iterator upper_bound_it = upper_bound(
00199 PB_ASSOC_V2F(*it));
00200
00201 --upper_bound_it;
00202
00203 PB_ASSOC_DBG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd);
00204
00205 if (prev_it != end())
00206 PB_ASSOC_DBG_ASSERT(Cmp_Fn::operator()(
00207 PB_ASSOC_V2F(*prev_it),
00208 PB_ASSOC_V2F(*it)));
00209
00210 prev_it = it;
00211 }
00212
00213 PB_ASSOC_DBG_ASSERT(iterated_num == m_size);
00214
00215 size_type reverse_iterated_num = 0;
00216
00217 const_reverse_iterator reverse_prev_it = rend();
00218
00219 for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend();
00220 ++reverse_it)
00221 {
00222 ++reverse_iterated_num;
00223
00224 PB_ASSOC_DBG_ASSERT(lower_bound(
00225 PB_ASSOC_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd);
00226
00227 const_iterator upper_bound_it = upper_bound(
00228 PB_ASSOC_V2F(*reverse_it));
00229
00230 --upper_bound_it;
00231
00232 PB_ASSOC_DBG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd);
00233
00234 if (reverse_prev_it != rend())
00235 PB_ASSOC_DBG_ASSERT(!Cmp_Fn::operator()(
00236 PB_ASSOC_V2F(*reverse_prev_it),
00237 PB_ASSOC_V2F(*reverse_it)));
00238
00239 reverse_prev_it = reverse_it;
00240 }
00241
00242 PB_ASSOC_DBG_ASSERT(reverse_iterated_num == m_size);
00243 }
00244
00245 PB_ASSOC_CLASS_T_DEC
00246 void
00247 PB_ASSOC_CLASS_C_DEC::
00248 assert_consistent_with_debug_base() const
00249 {
00250 my_map_debug_base::check_size(m_size);
00251
00252 assert_consistent_with_debug_base(m_p_head->m_p_parent);
00253 }
00254
00255 PB_ASSOC_CLASS_T_DEC
00256 void
00257 PB_ASSOC_CLASS_C_DEC::
00258 assert_consistent_with_debug_base(const node_pointer p_nd) const
00259 {
00260 if (p_nd == NULL)
00261 return;
00262
00263 my_map_debug_base::check_key_exists(
00264 PB_ASSOC_V2F(p_nd->m_value));
00265
00266 assert_consistent_with_debug_base(p_nd->m_p_left);
00267 assert_consistent_with_debug_base(p_nd->m_p_right);
00268 }
00269
00270 PB_ASSOC_CLASS_T_DEC
00271 void
00272 PB_ASSOC_CLASS_C_DEC::
00273 assert_size() const
00274 {
00275 PB_ASSOC_DBG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size);
00276 }
00277
00278 #endif // #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_