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