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