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 bool
00047 PB_ASSOC_CLASS_C_DEC::
00048 join_prep(PB_ASSOC_CLASS_C_DEC& r_other)
00049 {
00050 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00051 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00052
00053 if (r_other.m_size == 0)
00054 return (false);
00055
00056 if (m_size == 0)
00057 {
00058 swap(r_other);
00059
00060 return (false);
00061 }
00062
00063 const bool greater = Cmp_Fn::operator()(
00064 PB_ASSOC_V2F(m_p_head->m_p_right->m_value),
00065 PB_ASSOC_V2F(r_other.m_p_head->m_p_left->m_value));
00066
00067 const bool lesser = Cmp_Fn::operator()(
00068 PB_ASSOC_V2F(r_other.m_p_head->m_p_right->m_value),
00069 PB_ASSOC_V2F(m_p_head->m_p_left->m_value));
00070
00071 if (!greater&& !lesser)
00072 throw cannot_join();
00073
00074 if (lesser)
00075 swap(r_other);
00076
00077 m_size += r_other.m_size;
00078
00079 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00080 for (const_iterator other_it = r_other.begin(); other_it != r_other.end();
00081 ++other_it)
00082 {
00083 my_map_debug_base::insert_new(PB_ASSOC_V2F(*other_it));
00084 r_other.my_map_debug_base::erase_existing(PB_ASSOC_V2F(*other_it));
00085 }
00086 #endif // PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00087
00088 return (true);
00089 }
00090
00091 PB_ASSOC_CLASS_T_DEC
00092 void
00093 PB_ASSOC_CLASS_C_DEC::
00094 join_finish(PB_ASSOC_CLASS_C_DEC& r_other)
00095 {
00096 initialize_min_max();
00097
00098 r_other.initialize();
00099 }
00100
00101 PB_ASSOC_CLASS_T_DEC
00102 bool
00103 PB_ASSOC_CLASS_C_DEC::
00104 split_prep(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other)
00105 {
00106 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00107 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00108
00109 r_other.clear();
00110
00111 if (m_size == 0)
00112 {
00113 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00114 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00115
00116 return (false);
00117 }
00118
00119 if (Cmp_Fn::operator()(r_key, PB_ASSOC_V2F(m_p_head->m_p_left->m_value)))
00120 {
00121 swap(r_other);
00122
00123 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00124 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00125
00126 return (false);
00127 }
00128
00129 if (!Cmp_Fn::operator()(
00130 r_key,
00131 PB_ASSOC_V2F(m_p_head->m_p_right->m_value)))
00132 {
00133 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00134 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00135
00136 return (false);
00137 }
00138
00139 if (m_size == 1)
00140 {
00141 swap(r_other);
00142
00143 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00144 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00145
00146 return (false);
00147 }
00148
00149 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00150 for (const_iterator it = begin(); it != end(); ++it)
00151 if (Cmp_Fn::operator()(
00152 r_key,
00153 PB_ASSOC_V2F(*it)))
00154 {
00155 my_map_debug_base::erase_existing(PB_ASSOC_V2F(*it));
00156 r_other.my_map_debug_base::insert_new(PB_ASSOC_V2F(*it));
00157 }
00158 #endif // PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00159
00160 return (true);
00161 }
00162
00163 PB_ASSOC_CLASS_T_DEC
00164 void
00165 PB_ASSOC_CLASS_C_DEC::
00166 split_finish(PB_ASSOC_CLASS_C_DEC& r_other)
00167 {
00168 r_other.m_size = r_other.recursive_count(r_other.m_p_head->m_p_parent);
00169
00170 r_other.initialize_min_max();
00171
00172 m_size -= r_other.m_size;
00173
00174 initialize_min_max();
00175
00176 PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
00177 PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
00178 }
00179
00180 PB_ASSOC_CLASS_T_DEC
00181 typename PB_ASSOC_CLASS_C_DEC::size_type
00182 PB_ASSOC_CLASS_C_DEC::
00183 recursive_count(node_pointer p_nd) const
00184 {
00185 if (p_nd == NULL)
00186 return (0);
00187
00188 return (1 +
00189 recursive_count(p_nd->m_p_left) +
00190 recursive_count(p_nd->m_p_right));
00191 }
00192