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 #ifndef PB_DS_ASSOC_CNTNR_HPP
00048 #define PB_DS_ASSOC_CNTNR_HPP
00049
00050 #include <ext/typelist.h>
00051 #include <ext/pb_ds/tag_and_trait.hpp>
00052 #include <ext/pb_ds/detail/standard_policies.hpp>
00053 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
00054 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
00055
00056 namespace __gnu_pbds
00057 {
00058 #define PB_DS_BASE_C_DEC \
00059 detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
00060
00061
00062 template<typename Key,
00063 typename Mapped,
00064 typename Tag,
00065 typename Policy_Tl,
00066 typename Allocator>
00067 class container_base : public PB_DS_BASE_C_DEC
00068 {
00069 private:
00070 typedef typename PB_DS_BASE_C_DEC base_type;
00071
00072 public:
00073 typedef Tag container_category;
00074 typedef Allocator allocator;
00075 typedef typename allocator::size_type size_type;
00076 typedef typename allocator::difference_type difference_type;
00077
00078
00079 typedef typename allocator::template rebind<Key>::other::value_type key_type;
00080 typedef typename allocator::template rebind<key_type>::other key_rebind;
00081 typedef typename key_rebind::reference key_reference;
00082 typedef typename key_rebind::const_reference const_key_reference;
00083 typedef typename key_rebind::pointer key_pointer;
00084 typedef typename key_rebind::const_pointer const_key_pointer;
00085
00086
00087 typedef Mapped mapped_type;
00088 typedef typename allocator::template rebind<mapped_type>::other mapped_rebind;
00089 typedef typename mapped_rebind::reference mapped_reference;
00090 typedef typename mapped_rebind::const_reference const_mapped_reference;
00091 typedef typename mapped_rebind::pointer mapped_pointer;
00092 typedef typename mapped_rebind::const_pointer const_mapped_pointer;
00093
00094
00095 typedef typename base_type::value_type value_type;
00096 typedef typename allocator::template rebind<value_type>::other value_rebind;
00097 typedef typename value_rebind::reference reference;
00098 typedef typename value_rebind::const_reference const_reference;
00099 typedef typename value_rebind::pointer pointer;
00100 typedef typename value_rebind::const_pointer const_pointer;
00101
00102
00103 typedef typename base_type::iterator iterator;
00104 typedef typename base_type::const_iterator const_iterator;
00105 typedef typename base_type::point_iterator point_iterator;
00106 typedef typename base_type::const_point_iterator const_point_iterator;
00107
00108 virtual
00109 ~container_base() { }
00110
00111 protected:
00112 #define PB_DS_CLASS_NAME container_base
00113 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
00114 #undef PB_DS_CLASS_NAME
00115 };
00116
00117 #undef PB_DS_BASE_C_DEC
00118
00119
00120 #define PB_DS_BASE_C_DEC \
00121 container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
00122 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
00123
00124
00125 template<typename Key,
00126 typename Mapped,
00127 typename Hash_Fn,
00128 typename Eq_Fn,
00129 typename Resize_Policy,
00130 bool Store_Hash,
00131 typename Tag,
00132 typename Policy_TL,
00133 typename Allocator>
00134 class basic_hash_table : public PB_DS_BASE_C_DEC
00135 {
00136 private:
00137 typedef PB_DS_BASE_C_DEC base_type;
00138
00139 public:
00140 virtual
00141 ~basic_hash_table() { }
00142
00143 protected:
00144 #define PB_DS_CLASS_NAME basic_hash_table
00145 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
00146 #undef PB_DS_CLASS_NAME
00147
00148 private:
00149 basic_hash_table&
00150 operator=(const base_type&);
00151 };
00152
00153 #undef PB_DS_BASE_C_DEC
00154
00155
00156 #define PB_DS_BASE_C_DEC \
00157 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
00158 cc_hash_tag, \
00159 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
00160
00161
00162 template<typename Key,
00163 typename Mapped,
00164 typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
00165 typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
00166 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
00167 typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
00168 bool Store_Hash = detail::default_store_hash,
00169 typename Allocator = std::allocator<char> >
00170 class cc_hash_table : public PB_DS_BASE_C_DEC
00171 {
00172 private:
00173 typedef PB_DS_BASE_C_DEC base_type;
00174
00175 public:
00176 typedef Hash_Fn hash_fn;
00177 typedef Eq_Fn eq_fn;
00178 typedef Resize_Policy resize_policy;
00179 typedef Comb_Hash_Fn comb_hash_fn;
00180
00181
00182 cc_hash_table() { }
00183
00184
00185
00186 cc_hash_table(const hash_fn& h)
00187 : base_type(h) { }
00188
00189
00190
00191
00192
00193 cc_hash_table(const hash_fn& h, const eq_fn& e)
00194 : base_type(h, e) { }
00195
00196
00197
00198
00199
00200
00201 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
00202 : base_type(h, e, ch) { }
00203
00204
00205
00206
00207
00208
00209
00210 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
00211 const resize_policy& rp)
00212 : base_type(h, e, ch, rp) { }
00213
00214
00215
00216
00217 template<typename It>
00218 cc_hash_table(It first, It last)
00219 { base_type::copy_from_range(first, last); }
00220
00221
00222
00223
00224 template<typename It>
00225 cc_hash_table(It first, It last, const hash_fn& h)
00226 : base_type(h)
00227 { copy_from_range(first, last); }
00228
00229
00230
00231
00232
00233
00234
00235 template<typename It>
00236 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
00237 : base_type(h, e)
00238 { copy_from_range(first, last); }
00239
00240
00241
00242
00243
00244
00245
00246
00247 template<typename It>
00248 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00249 const comb_hash_fn& ch)
00250 : base_type(h, e, ch)
00251 { copy_from_range(first, last); }
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261 template<typename It>
00262 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00263 const comb_hash_fn& ch, const resize_policy& rp)
00264 : base_type(h, e, ch, rp)
00265 { copy_from_range(first, last); }
00266
00267 cc_hash_table(const cc_hash_table& other)
00268 : base_type((const base_type&)other)
00269 { }
00270
00271 virtual
00272 ~cc_hash_table() { }
00273
00274 cc_hash_table&
00275 operator=(const cc_hash_table& other)
00276 {
00277 if (this != &other)
00278 {
00279 cc_hash_table tmp(other);
00280 swap(tmp);
00281 }
00282 return *this;
00283 }
00284
00285 void
00286 swap(cc_hash_table& other)
00287 { base_type::swap(other); }
00288 };
00289
00290 #undef PB_DS_BASE_C_DEC
00291
00292
00293 #define PB_DS_BASE_C_DEC \
00294 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
00295 gp_hash_tag, \
00296 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
00297
00298
00299 template<typename Key,
00300 typename Mapped,
00301 typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
00302 typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
00303 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
00304 typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
00305 typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
00306 bool Store_Hash = detail::default_store_hash,
00307 typename Allocator = std::allocator<char> >
00308 class gp_hash_table : public PB_DS_BASE_C_DEC
00309 {
00310 private:
00311 typedef PB_DS_BASE_C_DEC base_type;
00312
00313 public:
00314 typedef Hash_Fn hash_fn;
00315 typedef Eq_Fn eq_fn;
00316 typedef Comb_Probe_Fn comb_probe_fn;
00317 typedef Probe_Fn probe_fn;
00318 typedef Resize_Policy resize_policy;
00319
00320
00321 gp_hash_table() { }
00322
00323
00324
00325 gp_hash_table(const hash_fn& h)
00326 : base_type(h) { }
00327
00328
00329
00330
00331
00332 gp_hash_table(const hash_fn& h, const eq_fn& e)
00333 : base_type(h, e) { }
00334
00335
00336
00337
00338
00339
00340 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
00341 : base_type(h, e, cp) { }
00342
00343
00344
00345
00346
00347
00348
00349 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
00350 const probe_fn& p)
00351 : base_type(h, e, cp, p) { }
00352
00353
00354
00355
00356
00357
00358
00359
00360 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
00361 const probe_fn& p, const resize_policy& rp)
00362 : base_type(h, e, cp, p, rp) { }
00363
00364
00365
00366
00367 template<typename It>
00368 gp_hash_table(It first, It last)
00369 { base_type::copy_from_range(first, last); }
00370
00371
00372
00373
00374
00375 template<typename It>
00376 gp_hash_table(It first, It last, const hash_fn& h)
00377 : base_type(h)
00378 { base_type::copy_from_range(first, last); }
00379
00380
00381
00382
00383
00384
00385
00386 template<typename It>
00387 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
00388 : base_type(h, e)
00389 { base_type::copy_from_range(first, last); }
00390
00391
00392
00393
00394
00395
00396
00397
00398 template<typename It>
00399 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00400 const comb_probe_fn& cp)
00401 : base_type(h, e, cp)
00402 { base_type::copy_from_range(first, last); }
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412 template<typename It>
00413 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00414 const comb_probe_fn& cp, const probe_fn& p)
00415 : base_type(h, e, cp, p)
00416 { base_type::copy_from_range(first, last); }
00417
00418
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428 template<typename It>
00429 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00430 const comb_probe_fn& cp, const probe_fn& p,
00431 const resize_policy& rp)
00432 : base_type(h, e, cp, p, rp)
00433 { base_type::copy_from_range(first, last); }
00434
00435 gp_hash_table(const gp_hash_table& other)
00436 : base_type((const base_type&)other)
00437 { }
00438
00439 virtual
00440 ~gp_hash_table() { }
00441
00442 gp_hash_table&
00443 operator=(const gp_hash_table& other)
00444 {
00445 if (this != &other)
00446 {
00447 gp_hash_table tmp(other);
00448 swap(tmp);
00449 }
00450 return *this;
00451 }
00452
00453 void
00454 swap(gp_hash_table& other)
00455 { base_type::swap(other); }
00456 };
00457
00458 #undef PB_DS_BASE_C_DEC
00459
00460
00461 #define PB_DS_BASE_C_DEC \
00462 container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
00463
00464
00465 template<typename Key, typename Mapped, typename Tag,
00466 typename Node_Update, typename Policy_Tl, typename Allocator>
00467 class basic_tree : public PB_DS_BASE_C_DEC
00468 {
00469 private:
00470 typedef PB_DS_BASE_C_DEC base_type;
00471
00472 public:
00473 typedef Node_Update node_update;
00474
00475 virtual
00476 ~basic_tree() { }
00477
00478 protected:
00479 #define PB_DS_CLASS_NAME basic_tree
00480 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
00481 #undef PB_DS_CLASS_NAME
00482 };
00483
00484 #undef PB_DS_BASE_C_DEC
00485
00486
00487 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
00488 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
00489
00490 #define PB_DS_BASE_C_DEC \
00491 basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
00492 typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
00493
00494
00495 template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
00496 typename Tag = rb_tree_tag,
00497 template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
00498 class Node_Update = __gnu_pbds::null_tree_node_update,
00499 typename Allocator = std::allocator<char> >
00500 class tree : public PB_DS_BASE_C_DEC
00501 {
00502 private:
00503 typedef PB_DS_BASE_C_DEC base_type;
00504
00505 public:
00506
00507 typedef Cmp_Fn cmp_fn;
00508
00509 tree() { }
00510
00511
00512
00513 tree(const cmp_fn& c)
00514 : base_type(c) { }
00515
00516
00517
00518
00519 template<typename It>
00520 tree(It first, It last)
00521 { base_type::copy_from_range(first, last); }
00522
00523
00524
00525
00526
00527 template<typename It>
00528 tree(It first, It last, const cmp_fn& c)
00529 : base_type(c)
00530 { base_type::copy_from_range(first, last); }
00531
00532 tree(const tree& other)
00533 : base_type((const base_type&)other) { }
00534
00535 virtual
00536 ~tree() { }
00537
00538 tree&
00539 operator=(const tree& other)
00540 {
00541 if (this != &other)
00542 {
00543 tree tmp(other);
00544 swap(tmp);
00545 }
00546 return *this;
00547 }
00548
00549 void
00550 swap(tree& other)
00551 { base_type::swap(other); }
00552 };
00553
00554 #undef PB_DS_BASE_C_DEC
00555 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
00556
00557
00558 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
00559 detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
00560
00561 #define PB_DS_BASE_C_DEC \
00562 basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
00563 typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
00564
00565
00566 template<typename Key,
00567 typename Mapped,
00568 typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
00569 typename Tag = pat_trie_tag,
00570 template<typename Const_Node_Iterator,
00571 typename Node_Iterator,
00572 typename E_Access_Traits_,
00573 typename Allocator_>
00574 class Node_Update = null_trie_node_update,
00575 typename Allocator = std::allocator<char> >
00576 class trie : public PB_DS_BASE_C_DEC
00577 {
00578 private:
00579 typedef PB_DS_BASE_C_DEC base_type;
00580
00581 public:
00582
00583 typedef E_Access_Traits e_access_traits;
00584
00585 trie() { }
00586
00587
00588
00589
00590 trie(const e_access_traits& t)
00591 : base_type(t) { }
00592
00593
00594
00595
00596 template<typename It>
00597 trie(It first, It last)
00598 { base_type::copy_from_range(first, last); }
00599
00600
00601
00602
00603 template<typename It>
00604 trie(It first, It last, const e_access_traits& t)
00605 : base_type(t)
00606 { base_type::copy_from_range(first, last); }
00607
00608 trie(const trie& other)
00609 : base_type((const base_type&)other) { }
00610
00611 virtual
00612 ~trie() { }
00613
00614 trie&
00615 operator=(const trie& other)
00616 {
00617 if (this != &other)
00618 {
00619 trie tmp(other);
00620 swap(tmp);
00621 }
00622 return *this;
00623 }
00624
00625 void
00626 swap(trie& other)
00627 { base_type::swap(other); }
00628 };
00629
00630 #undef PB_DS_BASE_C_DEC
00631 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
00632
00633
00634 #define PB_DS_BASE_C_DEC \
00635 container_base<Key, Mapped, list_update_tag, \
00636 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
00637
00638
00639 template<typename Key,
00640 typename Mapped,
00641 class Eq_Fn = typename detail::default_eq_fn<Key>::type,
00642 class Update_Policy = detail::default_update_policy::type,
00643 class Allocator = std::allocator<char> >
00644 class list_update : public PB_DS_BASE_C_DEC
00645 {
00646 private:
00647 typedef PB_DS_BASE_C_DEC base_type;
00648
00649 public:
00650 typedef Eq_Fn eq_fn;
00651 typedef Update_Policy update_policy;
00652 typedef Allocator allocator;
00653
00654 list_update() { }
00655
00656
00657
00658
00659 template<typename It>
00660 list_update(It first, It last)
00661 { base_type::copy_from_range(first, last); }
00662
00663 list_update(const list_update& other)
00664 : base_type((const base_type&)other) { }
00665
00666 virtual
00667 ~list_update() { }
00668
00669 list_update&
00670 operator=(const list_update& other)
00671 {
00672 if (this !=& other)
00673 {
00674 list_update tmp(other);
00675 swap(tmp);
00676 }
00677 return *this;
00678 }
00679
00680 void
00681 swap(list_update& other)
00682 { base_type::swap(other); }
00683 };
00684
00685 #undef PB_DS_BASE_C_DEC
00686
00687 }
00688
00689 #endif