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 #include <map>
00046 #include <set>
00047 #include <ext/pb_assoc/trivial_iterator_def.hpp>
00048 #include <ext/pb_assoc/tree_policy.hpp>
00049 #include <ext/pb_assoc/detail/eq_fn/eq_by_less.hpp>
00050 #include <ext/pb_assoc/detail/types_traits.hpp>
00051 #include <ext/pb_assoc/detail/map_debug_base.hpp>
00052 #include <ext/pb_assoc/detail/type_utils.hpp>
00053 #include <ext/pb_assoc/exception.hpp>
00054 #include <utility>
00055 #include <functional>
00056 #include <algorithm>
00057 #include <vector>
00058 #include <cassert>
00059 #ifdef PB_ASSOC_BASIC_REGRESSION
00060 #include <pb_assoc/testsuite/regression/basic_test/throw_prob_adjustor.hpp>
00061 #endif // #ifdef PB_ASSOC_BASIC_REGRESSION
00062
00063 namespace pb_assoc
00064 {
00065
00066 namespace detail
00067 {
00068
00069 #ifdef PB_ASSOC_OV_TREE_DEBUG_
00070 #define PB_ASSOC_DBG_ASSERT(X) assert(X);
00071 #define PB_ASSOC_DBG_VERIFY(X) PB_ASSOC_DBG_ASSERT(X)
00072 #define PB_ASSOC_DBG_ONLY(X) X
00073 #else // #ifdef PB_ASSOC_OV_TREE_DEBUG_
00074 #define PB_ASSOC_DBG_ASSERT(X) ((void)0)
00075 #define PB_ASSOC_DBG_VERIFY(X) X
00076 #define PB_ASSOC_DBG_ONLY(X) ;
00077 #endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_
00078
00079 #define PB_ASSOC_CLASS_T_DEC \
00080 template< \
00081 typename Key, \
00082 typename Data, \
00083 class Cmp_Fn, \
00084 class Allocator, \
00085 class Node_Updator>
00086
00087 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00088 #define PB_ASSOC_OV_TREE_CLASS_NAME \
00089 ov_tree_data_
00090 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00091
00092 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00093 #define PB_ASSOC_OV_TREE_CLASS_NAME \
00094 ov_tree_no_data_
00095 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00096
00097 #define PB_ASSOC_CLASS_C_DEC \
00098 PB_ASSOC_OV_TREE_CLASS_NAME< \
00099 Key, \
00100 Data, \
00101 Cmp_Fn, \
00102 Allocator, \
00103 Node_Updator>
00104
00105 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00106 types_traits< \
00107 Key, \
00108 Data, \
00109 Allocator>
00110
00111 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00112 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
00113 pb_assoc::detail::map_debug_base< \
00114 Key, \
00115 eq_by_less<Key, Cmp_Fn> >
00116 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00117
00118 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00119 #define PB_ASSOC_V2F(X) (X).first
00120 #define PB_ASSOC_V2S(X) (X).second
00121 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
00122 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00123
00124 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00125 #define PB_ASSOC_V2F(X) (X)
00126 #define PB_ASSOC_V2S(X) Mapped_Data()
00127 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
00128 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00129
00130 template<typename Key,
00131 typename Data,
00132 class Cmp_Fn,
00133 class Allocator,
00134 class Node_Updator>
00135 class PB_ASSOC_OV_TREE_CLASS_NAME :
00136 #ifdef PB_ASSOC_OV_TREE_DEBUG_
00137 protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
00138 #endif
00139 public 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 typename Allocator::difference_type difference_type;
00149
00150 typedef
00151 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00152 const_key_reference;
00153
00154 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00155
00156 typedef
00157 typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00158 data_reference;
00159
00160 typedef
00161 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00162 const_data_reference;
00163
00164 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00165
00166 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00167
00168 typedef
00169 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00170 const_pointer;
00171
00172 typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00173
00174 typedef
00175 typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00176 const_reference;
00177
00178 typedef const_pointer const_find_iterator;
00179
00180 typedef pointer find_iterator;
00181
00182 typedef const_find_iterator const_iterator;
00183
00184 typedef find_iterator iterator;
00185
00186 typedef pointer value_pointer;
00187
00188 #include <ext/pb_assoc/detail/ov_tree_map_/node_iterators.hpp>
00189
00190 #include <ext/pb_assoc/detail/ov_tree_map_/cond_dtor.hpp>
00191
00192 typedef Cmp_Fn cmp_fn;
00193
00194 typedef Allocator allocator;
00195
00196 typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
00197
00198 typedef cmp_fn my_cmp_fn_base;
00199
00200 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00201 typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
00202 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
00203
00204 protected:
00205
00206 PB_ASSOC_OV_TREE_CLASS_NAME();
00207
00208 PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
00209
00210 PB_ASSOC_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator);
00211
00212 PB_ASSOC_OV_TREE_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00213
00214 ~PB_ASSOC_OV_TREE_CLASS_NAME();
00215
00216 void
00217 swap(PB_ASSOC_CLASS_C_DEC& r_other);
00218
00219 template<class It>
00220 void
00221 copy_from_range(It first_it, It last_it);
00222
00223 template<class Node_Updator_>
00224 void
00225 update(node_iterator it, Node_Updator_* p_updator)
00226 {
00227 if (it == node_end())
00228 return;
00229
00230 update(it.l_child(), p_updator);
00231 update(it.r_child(), p_updator);
00232
00233 p_updator->operator()(it.m_p_value,(it.l_child() == node_end())? NULL : it.l_child().m_p_value,(it.r_child() == node_end())? NULL : it.r_child().m_p_value);
00234 }
00235
00236 inline void
00237 update(node_iterator , pb_assoc::null_node_updator* )
00238 { }
00239
00240 bool
00241 cmp_with_other(const PB_ASSOC_CLASS_C_DEC& r_other) const;
00242
00243 inline size_type
00244 max_size() const;
00245
00246 inline bool
00247 empty() const;
00248
00249 inline size_type
00250 size() const;
00251
00252 Cmp_Fn&
00253 get_cmp_fn();
00254
00255 const Cmp_Fn&
00256 get_cmp_fn() const;
00257
00258 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00259 inline data_reference
00260 subscript_imp(const_key_reference r_key)
00261 {
00262 PB_ASSOC_DBG_ONLY(assert_valid();)
00263
00264 find_iterator it = lower_bound(r_key);
00265
00266 if (it != find_end()&& !Cmp_Fn::operator()(
00267 r_key,
00268 PB_ASSOC_V2F(*it)))
00269 {
00270 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
00271
00272 PB_ASSOC_DBG_ONLY(assert_valid();)
00273
00274 return (it->second);
00275 }
00276
00277 PB_ASSOC_DBG_ONLY(assert_valid();)
00278
00279 return (insert_new_val(it,
00280 std::make_pair(r_key, data_type()))->second);
00281 }
00282
00283 inline const_data_reference
00284 subscript_imp(const_key_reference r_key) const
00285 {
00286 PB_ASSOC_DBG_ONLY(assert_valid();)
00287
00288 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
00289
00290 find_iterator it = lower_bound(r_key);
00291
00292 PB_ASSOC_DBG_ASSERT(it != find_end());
00293
00294 return (it->second);
00295 }
00296 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00297
00298 inline std::pair<find_iterator, bool>
00299 insert(const_reference r_value)
00300 {
00301 PB_ASSOC_DBG_ONLY(assert_valid();)
00302
00303 const_key_reference r_key = PB_ASSOC_V2F(r_value);
00304
00305 find_iterator it = lower_bound(r_key);
00306
00307 if (it != find_end()&& !Cmp_Fn::operator()(
00308 r_key,
00309 PB_ASSOC_V2F(*it)))
00310 {
00311 PB_ASSOC_DBG_ONLY(assert_valid();)
00312
00313 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
00314
00315 return (std::make_pair(it, false));
00316 }
00317
00318 PB_ASSOC_DBG_ONLY(assert_valid();)
00319
00320 return (std::make_pair(insert_new_val(it, r_value), true));
00321 }
00322
00323 inline static pointer
00324 mid_pointer(pointer p_begin, pointer p_end)
00325 {
00326 PB_ASSOC_DBG_ASSERT(p_end >= p_begin);
00327
00328 return (p_begin + (p_end - p_begin) / 2);
00329 }
00330
00331 inline find_iterator
00332 lower_bound(const_key_reference r_key)
00333 {
00334 pointer it = m_a_values;
00335
00336 difference_type dist = m_size;
00337
00338 while (dist > 0)
00339 {
00340 const difference_type mid_dist = dist >> 1;
00341
00342 pointer mid_it = it + mid_dist;
00343
00344 if (my_cmp_fn_base::operator()(
00345 PB_ASSOC_V2F(*(it + mid_dist)),
00346 r_key))
00347 {
00348 it = ++mid_it;
00349
00350 dist -= mid_dist + 1;
00351 }
00352 else
00353 dist = mid_dist;
00354 }
00355
00356 return (it);
00357 }
00358
00359 inline const_find_iterator
00360 lower_bound(const_key_reference r_key) const
00361 {
00362 return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).lower_bound(r_key));
00363 }
00364
00365 inline find_iterator
00366 upper_bound(const_key_reference r_key)
00367 {
00368 iterator pot_it = lower_bound(r_key);
00369
00370 if (pot_it != find_end()&& !Cmp_Fn::operator()(
00371 r_key,
00372 PB_ASSOC_V2F(*pot_it)))
00373 {
00374 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
00375
00376 return (++pot_it);
00377 }
00378
00379 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key));
00380
00381 return (pot_it);
00382 }
00383
00384 inline const_find_iterator
00385 upper_bound(const_key_reference r_key) const
00386 {
00387 return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).upper_bound(r_key));
00388 }
00389
00390 inline find_iterator
00391 find(const_key_reference r_key)
00392 {
00393 PB_ASSOC_DBG_ONLY(assert_valid();)
00394
00395 iterator pot_it = lower_bound(r_key);
00396
00397 if (pot_it != find_end()&& !Cmp_Fn::operator()(
00398 r_key,
00399 PB_ASSOC_V2F(*pot_it)))
00400 {
00401 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_exists(r_key));
00402
00403 return (pot_it);
00404 }
00405
00406 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(r_key));
00407
00408 return (find_end());
00409 }
00410
00411 inline const_find_iterator
00412 find(const_key_reference r_key) const
00413 {
00414 return (const_cast<PB_ASSOC_CLASS_C_DEC& >(*this).find(r_key));
00415 }
00416
00417 inline size_type
00418 erase(const_key_reference r_key);
00419
00420 template<class Pred>
00421 inline size_type
00422 erase_if(Pred pred);
00423
00424 template<class It>
00425 inline It
00426 erase(It it);
00427
00428 void
00429 clear();
00430
00431 void
00432 join(PB_ASSOC_CLASS_C_DEC& r_other);
00433
00434 void
00435 split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
00436
00437 inline iterator
00438 begin()
00439 {
00440 return (m_a_values);
00441 }
00442
00443 inline const_iterator
00444 begin() const
00445 {
00446 return (m_a_values);
00447 }
00448
00449 inline iterator
00450 find_end()
00451 {
00452 return (end());
00453 }
00454
00455 inline const_iterator
00456 find_end() const
00457 {
00458 return (end());
00459 }
00460
00461 inline iterator
00462 end()
00463 {
00464 return (m_end_it);
00465 }
00466
00467 inline const_iterator
00468 end() const
00469 {
00470 return (m_end_it);
00471 }
00472
00473 inline const_node_iterator
00474 node_begin() const
00475 {
00476 return (const_node_iterator(mid_pointer(begin(), end()), begin(), end()));
00477 }
00478
00479 inline node_iterator
00480 node_begin()
00481 {
00482 return (node_iterator(mid_pointer(begin(), end()), begin(), end()));
00483 }
00484
00485 inline const_node_iterator
00486 node_end() const
00487 {
00488 return (const_node_iterator(end(), end(), end()));
00489 }
00490
00491 inline node_iterator
00492 node_end()
00493 {
00494 return (node_iterator(end(), end(), end()));
00495 }
00496
00497 private:
00498
00499 inline pointer
00500 insert_new_val(iterator it, const_reference r_value)
00501 {
00502 PB_ASSOC_DBG_ONLY(assert_valid();)
00503
00504 #ifdef PB_ASSOC_BASIC_REGRESSION
00505 throw_prob_adjustor adjust(m_size);
00506 #endif // #ifdef PB_ASSOC_BASIC_REGRESSION
00507
00508 PB_ASSOC_DBG_ONLY(my_map_debug_base::check_key_does_not_exist(
00509 PB_ASSOC_V2F(r_value)));
00510
00511 pointer a_values = s_alloc.allocate(m_size + 1);
00512
00513 iterator source_it = begin();
00514 iterator source_end_it = end();
00515 iterator target_it = a_values;
00516 iterator ret_it;
00517
00518 cond_dtor cd(a_values, target_it, m_size + 1);
00519
00520 while (source_it != it)
00521 {
00522 new (const_cast<void* >(
00523 static_cast<const void* >(target_it)))
00524 value_type(*source_it++);
00525
00526 ++target_it;
00527 }
00528
00529 new (const_cast<void* >(
00530 static_cast<const void* >(ret_it = target_it)))
00531 value_type(r_value);
00532
00533 ++target_it;
00534
00535 while (source_it != source_end_it)
00536 {
00537 new (const_cast<void* >(
00538 static_cast<const void* >(target_it)))
00539 value_type(*source_it++);
00540
00541 ++target_it;
00542 }
00543
00544 cd.set_no_action();
00545
00546 if (m_size != 0)
00547 {
00548 cond_dtor cd1(m_a_values, m_end_it, m_size);
00549 }
00550
00551 ++m_size;
00552
00553 m_a_values = a_values;
00554
00555 m_end_it = m_a_values + m_size;
00556
00557 PB_ASSOC_DBG_ONLY(my_map_debug_base::insert_new(
00558 PB_ASSOC_V2F(r_value)));
00559
00560 update(node_begin(), (Node_Updator* )this);
00561
00562 PB_ASSOC_DBG_ONLY(PB_ASSOC_CLASS_C_DEC::assert_valid();)
00563
00564 return (ret_it);
00565 }
00566
00567 #ifdef PB_ASSOC_OV_TREE_DEBUG_
00568
00569 virtual void
00570 assert_valid() const;
00571
00572 void
00573 assert_iterators() const;
00574
00575 #endif // #ifdef PB_ASSOC_OV_TREE_DEBUG_
00576
00577 template<class It>
00578 void
00579 copy_from_ordered_range(It first_it, It last_it);
00580
00581 template<class It>
00582 void
00583 copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it);
00584
00585 private:
00586 typedef
00587 typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type_allocator
00588 value_allocator;
00589
00590 pointer m_a_values;
00591
00592 static value_allocator s_alloc;
00593
00594 pointer m_end_it;
00595
00596 size_type m_size;
00597 };
00598
00599 #include <ext/pb_assoc/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
00600 #include <ext/pb_assoc/detail/ov_tree_map_/iterators_fn_imps.hpp>
00601 #include <ext/pb_assoc/detail/ov_tree_map_/debug_fn_imps.hpp>
00602 #include <ext/pb_assoc/detail/ov_tree_map_/erase_fn_imps.hpp>
00603 #include <ext/pb_assoc/detail/ov_tree_map_/insert_fn_imps.hpp>
00604 #include <ext/pb_assoc/detail/ov_tree_map_/find_fn_imps.hpp>
00605 #include <ext/pb_assoc/detail/ov_tree_map_/info_fn_imps.hpp>
00606 #include <ext/pb_assoc/detail/ov_tree_map_/split_join_fn_imps.hpp>
00607
00608 #undef PB_ASSOC_CLASS_C_DEC
00609
00610 #undef PB_ASSOC_CLASS_T_DEC
00611
00612 #undef PB_ASSOC_OV_TREE_CLASS_NAME
00613
00614 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00615
00616 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
00617
00618 #undef PB_ASSOC_V2F
00619 #undef PB_ASSOC_EP2VP
00620 #undef PB_ASSOC_V2S
00621
00622 #undef PB_ASSOC_DBG_ASSERT
00623 #undef PB_ASSOC_DBG_VERIFY
00624 #undef PB_ASSOC_DBG_ONLY
00625
00626 }
00627
00628 }