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
00046
00047
00048
00049 #include <ext/pb_assoc/exception.hpp>
00050 #include <ext/pb_assoc/detail/eq_fn/eq_by_less.hpp>
00051 #include <ext/pb_assoc/detail/types_traits.hpp>
00052 #include <ext/pb_assoc/detail/map_debug_base.hpp>
00053 #include <ext/pb_assoc/tree_policy.hpp>
00054 #include <ext/pb_assoc/detail/cond_dealtor.hpp>
00055 #include <ext/pb_assoc/detail/type_utils.hpp>
00056 #include <utility>
00057 #include <functional>
00058 #include <assert.h>
00059
00060 namespace pb_assoc
00061 {
00062
00063 namespace detail
00064 {
00065
00066 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00067 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00068 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00069 #define PB_ASSOC_DBG_ONLY(X) X
00070 #else // #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00071 #define PB_ASSOC_DBG_ASSERT(X)
00072 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00073 #define PB_ASSOC_DBG_ONLY(X) ;
00074 #endif // #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00075
00076 #define PB_ASSOC_CLASS_T_DEC \
00077 template< \
00078 typename Key, \
00079 typename Data, \
00080 class Node, \
00081 class Cmp_Fn, \
00082 class Allocator, \
00083 class Node_Updator>
00084
00085 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00086 #define PB_ASSOC_CLASS_NAME \
00087 bin_search_tree_data_
00088 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00089
00090 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00091 #define PB_ASSOC_CLASS_NAME \
00092 bin_search_tree_no_data_
00093 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00094
00095 #define PB_ASSOC_CLASS_C_DEC \
00096 PB_ASSOC_CLASS_NAME< \
00097 Key, \
00098 Data, \
00099 Node, \
00100 Cmp_Fn, \
00101 Allocator, \
00102 Node_Updator>
00103
00104 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00105 pb_assoc::detail::types_traits< \
00106 Key, \
00107 Data, \
00108 Allocator>
00109
00110 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00111 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
00112 pb_assoc::detail::map_debug_base< \
00113 Key, \
00114 eq_by_less<Key, Cmp_Fn> >
00115 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00116
00117 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00118 #define PB_ASSOC_V2F(X) (X).first
00119 #define PB_ASSOC_V2S(X) (X).second
00120 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
00121 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00122
00123 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00124 #define PB_ASSOC_V2F(X) (X)
00125 #define PB_ASSOC_V2S(X) Mapped_Data()
00126 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
00127 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00128
00129 template<typename Key,
00130 typename Data,
00131 class Node,
00132 class Cmp_Fn,
00133 class Allocator,
00134 class Node_Updator>
00135 class PB_ASSOC_CLASS_NAME :
00136 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00137 protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
00138 #endif
00139 protected Cmp_Fn,
00140 public PB_ASSOC_TYPES_TRAITS_C_DEC,
00141 public Node_Updator
00142 {
00143
00144 protected:
00145
00146 typedef typename Allocator::size_type size_type;
00147
00148 typedef
00149 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00150 const_key_reference;
00151
00152 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00153
00154 typedef
00155 typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00156 data_reference;
00157
00158 typedef
00159 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00160 const_data_reference;
00161
00162 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00163
00164 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00165
00166 typedef
00167 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00168 const_pointer;
00169
00170 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00171
00172 typedef
00173 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00174 const_reference;
00175
00176 typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
00177
00178 typedef Node node;
00179
00180 typedef
00181 pb_assoc::detail::cond_dealtor<
00182 node,
00183 Allocator>
00184 cond_dealtor_t;
00185
00186 typedef
00187 typename Allocator::template rebind<node>::other
00188 node_allocator;
00189
00190 typedef typename node_allocator::value_type node_type;
00191
00192 typedef typename node_allocator::pointer node_pointer;
00193
00194 typedef value_type mapped_value_type;
00195
00196 typedef reference mapped_reference;
00197
00198 typedef const_reference const_mapped_reference;
00199
00200 typedef pointer mapped_pointer;
00201
00202 typedef const_pointer const_mapped_pointer;
00203
00204 #include <ext/pb_assoc/detail/bin_search_tree_/find_iterators.hpp>
00205
00206 typedef const_it_<true> const_find_iterator;
00207
00208 typedef it_<true> find_iterator;
00209
00210 typedef const_find_iterator const_iterator;
00211
00212 typedef find_iterator iterator;
00213
00214 typedef const_it_<false> const_reverse_iterator;
00215
00216 typedef it_<false> reverse_iterator;
00217
00218 #include <ext/pb_assoc/detail/bin_search_tree_/node_iterators.hpp>
00219
00220 typedef const_node_it_ const_node_iterator;
00221
00222 typedef node_it_ node_iterator;
00223
00224 typedef Cmp_Fn cmp_fn;
00225
00226 typedef Allocator allocator;
00227
00228 private:
00229
00230 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00231 typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
00232 #endif // #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00233
00234 protected:
00235
00236 PB_ASSOC_CLASS_NAME();
00237
00238 PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
00239
00240 PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_updator);
00241
00242 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00243
00244 void
00245 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00246
00247 ~PB_ASSOC_CLASS_NAME();
00248
00249 void
00250 initialize_min_max();
00251
00252 template<class Other_Map_Type>
00253 bool
00254 cmp_with_other(const Other_Map_Type& r_other) const;
00255
00256 inline bool
00257 empty() const;
00258
00259 inline size_type
00260 size() const;
00261
00262 inline size_type
00263 max_size() const;
00264
00265 Cmp_Fn&
00266 get_cmp_fn();
00267
00268 const Cmp_Fn&
00269 get_cmp_fn() const;
00270
00271 inline std::pair<find_iterator, bool>
00272 insert_leaf(const_reference r_value);
00273
00274 inline find_iterator
00275 lower_bound(const_key_reference r_key);
00276
00277 inline const_find_iterator
00278 lower_bound(const_key_reference r_key) const;
00279
00280 inline find_iterator
00281 upper_bound(const_key_reference r_key);
00282
00283 inline const_find_iterator
00284 upper_bound(const_key_reference r_key) const;
00285
00286 inline find_iterator
00287 find(const_key_reference r_key);
00288
00289 inline const_find_iterator
00290 find(const_key_reference r_key) const;
00291
00292 inline void
00293 update_min_max_for_erased_node(node_pointer p_nd);
00294
00295 inline void
00296 actual_erase_node(node_pointer p_nd);
00297
00298 void
00299 clear();
00300
00301 inline void
00302 rotate_left(node_pointer p_x);
00303
00304 inline void
00305 rotate_right(node_pointer p_y);
00306
00307 inline void
00308 rotate_parent(node_pointer p_nd);
00309
00310 inline void
00311 apply_update(node_pointer p_nd, pb_assoc::null_node_updator* );
00312
00313 template<class Node_Updator_>
00314 inline void
00315 apply_update(node_pointer p_nd, Node_Updator_* p_updator);
00316
00317 template<class Node_Updator_>
00318 inline void
00319 update_to_top(node_pointer p_nd, Node_Updator_* p_updator);
00320
00321 inline void
00322 update_to_top(node_pointer p_nd, pb_assoc::null_node_updator* );
00323
00324 inline iterator
00325 begin();
00326
00327 inline const_iterator
00328 begin() const;
00329
00330 inline iterator
00331 find_end();
00332
00333 inline const_iterator
00334 find_end() const;
00335
00336 inline iterator
00337 end();
00338
00339 inline const_iterator
00340 end() const;
00341
00342 inline reverse_iterator
00343 rbegin()
00344 {
00345 return (reverse_iterator(m_p_head->m_p_right));
00346 }
00347
00348 inline const_reverse_iterator
00349 rbegin() const;
00350
00351 inline reverse_iterator
00352 find_rend();
00353
00354 inline const_reverse_iterator
00355 find_rend() const;
00356
00357 inline reverse_iterator
00358 rend();
00359
00360 inline const_reverse_iterator
00361 rend() const;
00362
00363 bool
00364 join_prep(PB_ASSOC_CLASS_C_DEC& r_other);
00365
00366 void
00367 join_finish(PB_ASSOC_CLASS_C_DEC& r_other);
00368
00369 bool
00370 split_prep(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
00371
00372 void
00373 split_finish(PB_ASSOC_CLASS_C_DEC& r_other);
00374
00375 size_type
00376 recursive_count(node_pointer p_nd) const;
00377
00378 inline const_node_iterator
00379 node_begin() const;
00380
00381 inline node_iterator
00382 node_begin();
00383
00384 inline const_node_iterator
00385 node_end() const;
00386
00387 inline node_iterator
00388 node_end();
00389
00390 private:
00391
00392 inline std::pair<node_pointer, bool>
00393 erase(node_pointer p_nd);
00394
00395 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00396
00397 void
00398 assert_valid(bool check_iterators, bool check_metadata) const;
00399
00400 std::pair<const_pointer, const_pointer>
00401 assert_node_consistent(const node_pointer p_nd) const
00402 {
00403 if (p_nd == NULL)
00404 return (std::make_pair((const_pointer)NULL,(const_pointer)NULL));
00405
00406 assert_node_consistent_with_left(p_nd);
00407 assert_node_consistent_with_right(p_nd);
00408
00409 const std::pair<const_pointer, const_pointer>
00410 l_range =
00411 assert_node_consistent(p_nd->m_p_left);
00412
00413 if (l_range.second != NULL)
00414 PB_ASSOC_DBG_ASSERT(Cmp_Fn::operator()(
00415 PB_ASSOC_V2F(*l_range.second),
00416 PB_ASSOC_V2F(p_nd->m_value)));
00417
00418 const std::pair<const_pointer, const_pointer>
00419 r_range =
00420 assert_node_consistent(p_nd->m_p_right);
00421
00422 if (r_range.first != NULL)
00423 PB_ASSOC_DBG_ASSERT(Cmp_Fn::operator()(
00424 PB_ASSOC_V2F(p_nd->m_value),
00425 PB_ASSOC_V2F(*r_range.first)));
00426
00427 return (std::make_pair((l_range.first != NULL)? l_range.first :& p_nd->m_value,(r_range.second != NULL)? r_range.second :& p_nd->m_value));
00428 }
00429
00430 void
00431 assert_consistent_with_debug_base() const;
00432
00433 void
00434 assert_node_consistent_with_left(const node_pointer p_nd) const;
00435
00436 void
00437 assert_node_consistent_with_right(const node_pointer p_nd) const;
00438
00439 void
00440 assert_consistent_with_debug_base(const node_pointer p_nd) const;
00441
00442 void
00443 assert_min() const;
00444
00445 void
00446 assert_min_imp(const node_pointer p_nd) const;
00447
00448 void
00449 assert_max() const;
00450
00451 void
00452 assert_max_imp(const node_pointer p_nd) const;
00453
00454 void
00455 assert_iterators() const;
00456
00457 void
00458 assert_size() const;
00459
00460 #endif // #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
00461
00462 void
00463 initialize();
00464
00465 node_pointer
00466 recursive_copy_node(const node_pointer p_nd);
00467
00468 inline node_pointer
00469 get_new_node_for_leaf_insert(const_reference r_val, pb_assoc::detail::int_to_type<false>);
00470
00471 inline node_pointer
00472 get_new_node_for_leaf_insert(const_reference r_val, pb_assoc::detail::int_to_type<true>);
00473
00474 inline iterator
00475 insert_imp_empty(const_reference r_value);
00476
00477 inline iterator
00478 insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
00479
00480 static void
00481 clear_imp(node_pointer p_nd);
00482
00483 protected:
00484 node_pointer m_p_head;
00485
00486 iterator m_end_it;
00487
00488 reverse_iterator m_rend_it;
00489
00490 size_type m_size;
00491
00492 static node_allocator s_node_allocator;
00493 };
00494
00495 #include <ext/pb_assoc/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
00496 #include <ext/pb_assoc/detail/bin_search_tree_/iterators_fn_imps.hpp>
00497 #include <ext/pb_assoc/detail/bin_search_tree_/debug_fn_imps.hpp>
00498 #include <ext/pb_assoc/detail/bin_search_tree_/insert_fn_imps.hpp>
00499 #include <ext/pb_assoc/detail/bin_search_tree_/erase_fn_imps.hpp>
00500 #include <ext/pb_assoc/detail/bin_search_tree_/find_fn_imps.hpp>
00501 #include <ext/pb_assoc/detail/bin_search_tree_/info_fn_imps.hpp>
00502 #include <ext/pb_assoc/detail/bin_search_tree_/split_join_fn_imps.hpp>
00503 #include <ext/pb_assoc/detail/bin_search_tree_/rotate_fn_imps.hpp>
00504
00505 #undef PB_ASSOC_CLASS_C_DEC
00506
00507 #undef PB_ASSOC_CLASS_T_DEC
00508
00509 #undef PB_ASSOC_CLASS_NAME
00510
00511 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00512
00513 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
00514
00515 #undef PB_ASSOC_V2F
00516 #undef PB_ASSOC_EP2VP
00517 #undef PB_ASSOC_V2S
00518
00519 #undef PB_ASSOC_DBG_ASSERT
00520 #undef PB_ASSOC_DBG_VERIFY
00521 #undef PB_ASSOC_DBG_ONLY
00522
00523 }
00524
00525 }