contrib/gcc-4.7/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file assoc_container.hpp
  38  * Contains associative containers.
  39  */
  40
  41 #ifndef PB_DS_ASSOC_CNTNR_HPP
  42 #define PB_DS_ASSOC_CNTNR_HPP
  43
  44 #include <bits/c++config.h>
  45 #include <ext/typelist.h>
  46 #include <ext/pb_ds/tag_and_trait.hpp>
  47 #include <ext/pb_ds/detail/standard_policies.hpp>
  48 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
  49 #include <ext/pb_ds/detail/branch_policy/traits.hpp>
  50
  51 namespace __gnu_pbds
  52 {
  53   /**
  54    *  @defgroup containers-pbds Containers
  55    *  @ingroup pbds
  56    *  @{
  57    */
  58
  59   /**
  60    *  @defgroup hash-based
  61    *  @ingroup containers-pbds
  62    *  @{
  63    */
  64 #define PB_DS_HASH_BASE \
  65   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
  66     typename __gnu_cxx::typelist::append< \
  67     typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
  68     detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
  69
  70   /**
  71    *  @defgroup hash-detail Base and Policy Classes
  72    *  @ingroup hash-based
  73    */
  74
  75   /**
  76    *  A hashed container abstraction.
  77    *
  78    *  @tparam Key               Key type.
  79    *  @tparam Mapped            Map type.
  80    *  @tparam Hash_Fn           Hashing functor.
  81    *  @tparam Eq_Fn             Equal functor.
  82    *  @tparam Resize_Policy     Resizes hash.
  83    *  @tparam Store_Hash        Indicates whether the hash value
  84    *                            will be stored along with each key.
  85    *  @tparam Tag               Instantiating data structure type,
  86    *                            see container_tag.
  87    *  @tparam Policy_TL         Policy typelist.
  88    *  @tparam _Alloc            Allocator type.
  89    *
  90    *  Base is dispatched at compile time via Tag, from the following
  91    *  choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
  92    *
  93    *  Base choices are: detail::cc_ht_map, detail::gp_ht_map
  94    */
  95   template<typename Key,
  96            typename Mapped,
  97            typename Hash_Fn,
  98            typename Eq_Fn,
  99            typename Resize_Policy,
 100            bool Store_Hash,
 101            typename Tag,
 102            typename Policy_Tl,
 103            typename _Alloc>
 104   class basic_hash_table : public PB_DS_HASH_BASE
 105   {
 106   private:
 107     typedef typename PB_DS_HASH_BASE            base_type;
 108
 109   public:
 110     virtual
 111     ~basic_hash_table() { }
 112
 113   protected:
 114     basic_hash_table() { }
 115
 116     basic_hash_table(const basic_hash_table& other)
 117     : base_type((const base_type&)other) { }
 118
 119     template<typename T0>
 120       basic_hash_table(T0 t0) : base_type(t0) { }
 121
 122     template<typename T0, typename T1>
 123       basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
 124
 125     template<typename T0, typename T1, typename T2>
 126       basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
 127
 128     template<typename T0, typename T1, typename T2, typename T3>
 129       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
 130       : base_type(t0, t1, t2, t3) { }
 131
 132     template<typename T0, typename T1, typename T2, typename T3, typename T4>
 133       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
 134       : base_type(t0, t1, t2, t3, t4) { }
 135
 136     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 137              typename T5>
 138       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
 139       : base_type(t0, t1, t2, t3, t4, t5) { }
 140
 141     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 142              typename T5, typename T6>
 143       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
 144       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
 145
 146     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 147              typename T5, typename T6, typename T7>
 148       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
 149       : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }
 150
 151     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 152              typename T5, typename T6, typename T7, typename T8>
 153       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
 154                        T7 t7, T8 t8)
 155       : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
 156       { }
 157
 158   private:
 159     basic_hash_table&
 160     operator=(const base_type&);
 161   };
 162
 163 #undef PB_DS_HASH_BASE
 164
 165
 166 #define PB_DS_CC_HASH_BASE \
 167   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
 168                    cc_hash_tag, \
 169           typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
 170
 171
 172   /**
 173    *  A collision-chaining hash-based associative container.
 174    *
 175    *  @tparam Key               Key type.
 176    *  @tparam Mapped            Map type.
 177    *  @tparam Hash_Fn           Hashing functor.
 178    *  @tparam Eq_Fn             Equal functor.
 179    *  @tparam Comb_Hash_Fn      Combining hash functor.
 180    *                            If Hash_Fn is not null_type, then this
 181    *                            is the ranged-hash functor; otherwise,
 182    *                            this is the range-hashing functor.
 183    *                    XXX(See Design::Hash-Based Containers::Hash Policies.)
 184    *  @tparam Resize_Policy     Resizes hash.
 185    *  @tparam Store_Hash        Indicates whether the hash value
 186    *                            will be stored along with each key.
 187    *                            If Hash_Fn is null_type, then the
 188    *                            container will not compile if this
 189    *                            value is true
 190    *  @tparam _Alloc            Allocator type.
 191    *
 192    *  Base tag choices are:     cc_hash_tag.
 193    *
 194    *  Base is basic_hash_table.
 195    */
 196   template<typename Key,
 197            typename Mapped,
 198            typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
 199            typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
 200            typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
 201            typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
 202            bool Store_Hash = detail::default_store_hash,
 203            typename _Alloc = std::allocator<char> >
 204   class cc_hash_table :  public PB_DS_CC_HASH_BASE
 205   {
 206   private:
 207     typedef PB_DS_CC_HASH_BASE                  base_type;
 208
 209   public:
 210     typedef cc_hash_tag                         container_category;
 211     typedef Hash_Fn                             hash_fn;
 212     typedef Eq_Fn                               eq_fn;
 213     typedef Resize_Policy                       resize_policy;
 214     typedef Comb_Hash_Fn                        comb_hash_fn;
 215
 216     /// Default constructor.
 217     cc_hash_table() { }
 218
 219     /// Constructor taking some policy objects. r_hash_fn will be
 220     /// copied by the Hash_Fn object of the container object.
 221     cc_hash_table(const hash_fn& h)
 222     : base_type(h) { }
 223
 224     /// Constructor taking some policy objects. r_hash_fn will be
 225     /// copied by the hash_fn object of the container object, and
 226     /// r_eq_fn will be copied by the eq_fn object of the container
 227     /// object.
 228     cc_hash_table(const hash_fn& h, const eq_fn& e)
 229     : base_type(h, e) { }
 230
 231     /// Constructor taking some policy objects. r_hash_fn will be
 232     /// copied by the hash_fn object of the container object, r_eq_fn
 233     /// will be copied by the eq_fn object of the container object,
 234     /// and r_comb_hash_fn will be copied by the comb_hash_fn object
 235     /// of the container object.
 236     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
 237     : base_type(h, e, ch) { }
 238
 239     /// Constructor taking some policy objects. r_hash_fn will be
 240     /// copied by the hash_fn object of the container object, r_eq_fn
 241     /// will be copied by the eq_fn object of the container object,
 242     /// r_comb_hash_fn will be copied by the comb_hash_fn object of
 243     /// the container object, and r_resize_policy will be copied by
 244     /// the resize_policy object of the container object.
 245     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
 246                   const resize_policy& rp)
 247     : base_type(h, e, ch, rp) { }
 248
 249     /// Constructor taking __iterators to a range of value_types. The
 250     /// value_types between first_it and last_it will be inserted into
 251     /// the container object.
 252     template<typename It>
 253     cc_hash_table(It first, It last)
 254     { base_type::copy_from_range(first, last); }
 255
 256     /// Constructor taking __iterators to a range of value_types and
 257     /// some policy objects. The value_types between first_it and
 258     /// last_it will be inserted into the container object.
 259     template<typename It>
 260     cc_hash_table(It first, It last, const hash_fn& h)
 261     : base_type(h)
 262     { this->copy_from_range(first, last); }
 263
 264     /// Constructor taking __iterators to a range of value_types and
 265     /// some policy objects The value_types between first_it and
 266     /// last_it will be inserted into the container object. r_hash_fn
 267     /// will be copied by the hash_fn object of the container object,
 268     /// and r_eq_fn will be copied by the eq_fn object of the
 269     /// container object.
 270     template<typename It>
 271     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
 272     : base_type(h, e)
 273     { this->copy_from_range(first, last); }
 274
 275     /// Constructor taking __iterators to a range of value_types and
 276     /// some policy objects The value_types between first_it and
 277     /// last_it will be inserted into the container object. r_hash_fn
 278     /// will be copied by the hash_fn object of the container object,
 279     /// r_eq_fn will be copied by the eq_fn object of the container
 280     /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
 281     /// object of the container object.
 282     template<typename It>
 283     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 284                   const comb_hash_fn& ch)
 285     : base_type(h, e, ch)
 286     { this->copy_from_range(first, last); }
 287
 288     /// Constructor taking __iterators to a range of value_types and
 289     /// some policy objects The value_types between first_it and
 290     /// last_it will be inserted into the container object. r_hash_fn
 291     /// will be copied by the hash_fn object of the container object,
 292     /// r_eq_fn will be copied by the eq_fn object of the container
 293     /// object, r_comb_hash_fn will be copied by the comb_hash_fn
 294     /// object of the container object, and r_resize_policy will be
 295     /// copied by the resize_policy object of the container object.
 296     template<typename It>
 297     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 298                   const comb_hash_fn& ch, const resize_policy& rp)
 299     : base_type(h, e, ch, rp)
 300     { this->copy_from_range(first, last); }
 301
 302     cc_hash_table(const cc_hash_table& other)
 303     : base_type((const base_type&)other)
 304     { }
 305
 306     virtual
 307     ~cc_hash_table() { }
 308
 309     cc_hash_table&
 310     operator=(const cc_hash_table& other)
 311     {
 312       if (this != &other)
 313         {
 314           cc_hash_table tmp(other);
 315           swap(tmp);
 316         }
 317       return *this;
 318     }
 319
 320     void
 321     swap(cc_hash_table& other)
 322     { base_type::swap(other); }
 323   };
 324
 325 #undef PB_DS_CC_HASH_BASE
 326
 327
 328 #define PB_DS_GP_HASH_BASE \
 329   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
 330                    gp_hash_tag, \
 331   typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
 332
 333
 334   /**
 335    *  A general-probing hash-based associative container.
 336    *
 337    *  @tparam Key               Key type.
 338    *  @tparam Mapped            Map type.
 339    *  @tparam Hash_Fn           Hashing functor.
 340    *  @tparam Eq_Fn             Equal functor.
 341    *  @tparam Comb_Probe_Fn     Combining probe functor.
 342    *                            If Hash_Fn is not null_type, then this
 343    *                            is the ranged-probe functor; otherwise,
 344    *                            this is the range-hashing functor.
 345    *                    XXX See Design::Hash-Based Containers::Hash Policies.
 346    *  @tparam Probe_Fn          Probe functor.
 347    *  @tparam Resize_Policy     Resizes hash.
 348    *  @tparam Store_Hash        Indicates whether the hash value
 349    *                            will be stored along with each key.
 350    *                            If Hash_Fn is null_type, then the
 351    *                            container will not compile if this
 352    *                            value is true
 353    *  @tparam _Alloc            Allocator type.
 354    *
 355    *  Base tag choices are:     gp_hash_tag.
 356    *
 357    *  Base is basic_hash_table.
 358    */
 359   template<typename Key,
 360            typename Mapped,
 361            typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
 362            typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
 363            typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
 364            typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
 365            typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
 366            bool Store_Hash = detail::default_store_hash,
 367            typename _Alloc = std::allocator<char> >
 368   class gp_hash_table : public PB_DS_GP_HASH_BASE
 369   {
 370   private:
 371     typedef PB_DS_GP_HASH_BASE                  base_type;
 372
 373   public:
 374     typedef gp_hash_tag                         container_category;
 375     typedef Hash_Fn                             hash_fn;
 376     typedef Eq_Fn                               eq_fn;
 377     typedef Comb_Probe_Fn                       comb_probe_fn;
 378     typedef Probe_Fn                            probe_fn;
 379     typedef Resize_Policy                       resize_policy;
 380
 381     /// Default constructor.
 382     gp_hash_table() { }
 383
 384     /// Constructor taking some policy objects. r_hash_fn will be
 385     /// copied by the hash_fn object of the container object.
 386     gp_hash_table(const hash_fn& h)
 387     : base_type(h) { }
 388
 389     /// Constructor taking some policy objects. r_hash_fn will be
 390     /// copied by the hash_fn object of the container object, and
 391     /// r_eq_fn will be copied by the eq_fn object of the container
 392     /// object.
 393     gp_hash_table(const hash_fn& h, const eq_fn& e)
 394     : base_type(h, e) { }
 395
 396     /// Constructor taking some policy objects. r_hash_fn will be
 397     /// copied by the hash_fn object of the container object, r_eq_fn
 398     /// will be copied by the eq_fn object of the container object,
 399     /// and r_comb_probe_fn will be copied by the comb_probe_fn object
 400     /// of the container object.
 401     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
 402     : base_type(h, e, cp) { }
 403
 404     /// Constructor taking some policy objects. r_hash_fn will be
 405     /// copied by the hash_fn object of the container object, r_eq_fn
 406     /// will be copied by the eq_fn object of the container object,
 407     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
 408     /// the container object, and r_probe_fn will be copied by the
 409     /// probe_fn object of the container object.
 410     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
 411                   const probe_fn& p)
 412     : base_type(h, e, cp, p) { }
 413
 414     /// Constructor taking some policy objects. r_hash_fn will be
 415     /// copied by the hash_fn object of the container object, r_eq_fn
 416     /// will be copied by the eq_fn object of the container object,
 417     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
 418     /// the container object, r_probe_fn will be copied by the
 419     /// probe_fn object of the container object, and r_resize_policy
 420     /// will be copied by the Resize_Policy object of the container
 421     /// object.
 422     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
 423                   const probe_fn& p, const resize_policy& rp)
 424     : base_type(h, e, cp, p, rp) { }
 425
 426     /// Constructor taking __iterators to a range of value_types. The
 427     /// value_types between first_it and last_it will be inserted into
 428     /// the container object.
 429     template<typename It>
 430     gp_hash_table(It first, It last)
 431     { base_type::copy_from_range(first, last); }
 432
 433     /// Constructor taking __iterators to a range of value_types and
 434     /// some policy objects. The value_types between first_it and
 435     /// last_it will be inserted into the container object. r_hash_fn
 436     /// will be copied by the hash_fn object of the container object.
 437     template<typename It>
 438     gp_hash_table(It first, It last, const hash_fn& h)
 439     : base_type(h)
 440     { base_type::copy_from_range(first, last); }
 441
 442     /// Constructor taking __iterators to a range of value_types and
 443     /// some policy objects. The value_types between first_it and
 444     /// last_it will be inserted into the container object. r_hash_fn
 445     /// will be copied by the hash_fn object of the container object,
 446     /// and r_eq_fn will be copied by the eq_fn object of the
 447     /// container object.
 448     template<typename It>
 449     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
 450     : base_type(h, e)
 451     { base_type::copy_from_range(first, last); }
 452
 453     /// Constructor taking __iterators to a range of value_types and
 454     /// some policy objects. The value_types between first_it and
 455     /// last_it will be inserted into the container object. r_hash_fn
 456     /// will be copied by the hash_fn object of the container object,
 457     /// r_eq_fn will be copied by the eq_fn object of the container
 458     /// object, and r_comb_probe_fn will be copied by the
 459     /// comb_probe_fn object of the container object.
 460     template<typename It>
 461     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 462                   const comb_probe_fn& cp)
 463     : base_type(h, e, cp)
 464     { base_type::copy_from_range(first, last); }
 465
 466     /// Constructor taking __iterators to a range of value_types and
 467     /// some policy objects. The value_types between first_it and
 468     /// last_it will be inserted into the container object. r_hash_fn
 469     /// will be copied by the hash_fn object of the container object,
 470     /// r_eq_fn will be copied by the eq_fn object of the container
 471     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
 472     /// object of the container object, and r_probe_fn will be copied
 473     /// by the probe_fn object of the container object.
 474     template<typename It>
 475     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 476                   const comb_probe_fn& cp, const probe_fn& p)
 477     : base_type(h, e, cp, p)
 478     { base_type::copy_from_range(first, last); }
 479
 480     /// Constructor taking __iterators to a range of value_types and
 481     /// some policy objects. The value_types between first_it and
 482     /// last_it will be inserted into the container object. r_hash_fn
 483     /// will be copied by the hash_fn object of the container object,
 484     /// r_eq_fn will be copied by the eq_fn object of the container
 485     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
 486     /// object of the container object, r_probe_fn will be copied by
 487     /// the probe_fn object of the container object, and
 488     /// r_resize_policy will be copied by the resize_policy object of
 489     /// the container object.
 490     template<typename It>
 491     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 492                   const comb_probe_fn& cp, const probe_fn& p,
 493                   const resize_policy& rp)
 494     : base_type(h, e, cp, p, rp)
 495     { base_type::copy_from_range(first, last); }
 496
 497     gp_hash_table(const gp_hash_table& other)
 498     : base_type((const base_type&)other)
 499     { }
 500
 501     virtual
 502     ~gp_hash_table() { }
 503
 504     gp_hash_table&
 505     operator=(const gp_hash_table& other)
 506     {
 507       if (this != &other)
 508         {
 509           gp_hash_table tmp(other);
 510           swap(tmp);
 511         }
 512       return *this;
 513     }
 514
 515     void
 516     swap(gp_hash_table& other)
 517     { base_type::swap(other); }
 518   };
 519   //@} hash-based
 520 #undef PB_DS_GP_HASH_BASE
 521
 522
 523   /**
 524    *  @defgroup branch-based
 525    *  @ingroup containers-pbds
 526    *  @{
 527    */
 528 #define PB_DS_BRANCH_BASE \
 529   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
 530
 531   /**
 532    *  @defgroup branch-detail Base and Policy Classes
 533    *  @ingroup branch-based
 534    */
 535
 536   /**
 537    *  A branched, tree-like (tree, trie) container abstraction.
 538    *
 539    *  @tparam Key               Key type.
 540    *  @tparam Mapped            Map type.
 541    *  @tparam Tag               Instantiating data structure type,
 542    *                            see container_tag.
 543    *  @tparam Node_Update       Updates nodes, restores invariants.
 544    *  @tparam Policy_TL         Policy typelist.
 545    *  @tparam _Alloc            Allocator type.
 546    *
 547    *  Base is dispatched at compile time via Tag, from the following
 548    *  choices: tree_tag, trie_tag, and their descendants.
 549    *
 550    *  Base choices are: detail::ov_tree_map, detail::rb_tree_map,
 551    *                    detail::splay_tree_map, and detail::pat_trie_map.
 552    */
 553   template<typename Key, typename Mapped, typename Tag,
 554            typename Node_Update, typename Policy_Tl, typename _Alloc>
 555   class basic_branch : public PB_DS_BRANCH_BASE
 556   {
 557   private:
 558     typedef typename PB_DS_BRANCH_BASE          base_type;
 559
 560   public:
 561     typedef Node_Update                         node_update;
 562
 563     virtual
 564     ~basic_branch() { }
 565
 566   protected:
 567     basic_branch() { }
 568
 569     basic_branch(const basic_branch& other)
 570     : base_type((const base_type&)other) { }
 571
 572     template<typename T0>
 573       basic_branch(T0 t0) : base_type(t0) { }
 574
 575     template<typename T0, typename T1>
 576       basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
 577
 578     template<typename T0, typename T1, typename T2>
 579       basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
 580
 581     template<typename T0, typename T1, typename T2, typename T3>
 582       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
 583       : base_type(t0, t1, t2, t3) { }
 584
 585     template<typename T0, typename T1, typename T2, typename T3, typename T4>
 586       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
 587       : base_type(t0, t1, t2, t3, t4) { }
 588
 589     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 590              typename T5>
 591       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
 592       : base_type(t0, t1, t2, t3, t4, t5) { }
 593
 594     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 595              typename T5, typename T6>
 596       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
 597       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
 598   };
 599 #undef PB_DS_BRANCH_BASE
 600
 601
 602 #define PB_DS_TREE_NODE_AND_IT_TRAITS \
 603   detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
 604
 605 #define PB_DS_TREE_BASE \
 606   basic_branch<Key,Mapped, Tag, \
 607                typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
 608                typename __gnu_cxx::typelist::create2<Cmp_Fn, \
 609                PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
 610
 611
 612   /**
 613    *  A tree-based container.
 614    *
 615    *  @tparam Key               Key type.
 616    *  @tparam Mapped            Map type.
 617    *  @tparam Cmp_Fn            Comparison functor.
 618    *  @tparam Tag               Instantiating data structure type,
 619    *                            see container_tag.
 620    *  @tparam Node_Update       Updates nodes,
 621    *                            restores invariants when invalidated.
 622    *                     XXX See design::tree-based-containers::node invariants.
 623    *  @tparam _Alloc            Allocator type.
 624    *
 625    *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
 626    *
 627    *  Base is basic_branch.
 628    */
 629   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
 630            typename Tag = rb_tree_tag,
 631            template<typename Node_CItr, typename Node_Itr,
 632                     typename Cmp_Fn_, typename _Alloc_>
 633            class Node_Update = null_node_update,
 634            typename _Alloc = std::allocator<char> >
 635   class tree : public PB_DS_TREE_BASE
 636   {
 637   private:
 638     typedef PB_DS_TREE_BASE                     base_type;
 639
 640   public:
 641     /// Comparison functor type.
 642     typedef Cmp_Fn                              cmp_fn;
 643
 644     tree() { }
 645
 646     /// Constructor taking some policy objects. r_cmp_fn will be
 647     /// copied by the Cmp_Fn object of the container object.
 648     tree(const cmp_fn& c)
 649     : base_type(c) { }
 650
 651     /// Constructor taking __iterators to a range of value_types. The
 652     /// value_types between first_it and last_it will be inserted into
 653     /// the container object.
 654     template<typename It>
 655     tree(It first, It last)
 656     { base_type::copy_from_range(first, last); }
 657
 658     /// Constructor taking __iterators to a range of value_types and
 659     /// some policy objects The value_types between first_it and
 660     /// last_it will be inserted into the container object. r_cmp_fn
 661     /// will be copied by the cmp_fn object of the container object.
 662     template<typename It>
 663     tree(It first, It last, const cmp_fn& c)
 664     : base_type(c)
 665     { base_type::copy_from_range(first, last); }
 666
 667     tree(const tree& other)
 668     : base_type((const base_type&)other) { }
 669
 670     virtual
 671     ~tree() { }
 672
 673     tree&
 674     operator=(const tree& other)
 675     {
 676       if (this != &other)
 677         {
 678           tree tmp(other);
 679           swap(tmp);
 680         }
 681       return *this;
 682     }
 683
 684     void
 685     swap(tree& other)
 686     { base_type::swap(other); }
 687   };
 688
 689 #undef PB_DS_TREE_BASE
 690 #undef PB_DS_TREE_NODE_AND_IT_TRAITS
 691
 692
 693 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \
 694   detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
 695
 696 #define PB_DS_TRIE_BASE \
 697   basic_branch<Key,Mapped,Tag, \
 698                typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
 699                typename __gnu_cxx::typelist::create2<_ATraits, \
 700                PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
 701
 702
 703   /**
 704    *  A trie-based container.
 705    *
 706    *  @tparam Key               Key type.
 707    *  @tparam Mapped            Map type.
 708    *  @tparam _ATraits          Element access traits.
 709    *  @tparam Tag               Instantiating data structure type,
 710    *                            see container_tag.
 711    *  @tparam Node_Update       Updates trie nodes,
 712    *                            restores invariants when invalidated.
 713    *                     XXX See design::tree-based-containers::node invariants.
 714    *  @tparam _Alloc            Allocator type.
 715    *
 716    *  Base tag choice is pat_trie_tag.
 717    *
 718    *  Base is basic_branch.
 719    */
 720   template<typename Key,
 721            typename Mapped,
 722            typename _ATraits = \
 723                     typename detail::default_trie_access_traits<Key>::type,
 724            typename Tag = pat_trie_tag,
 725            template<typename Node_CItr,
 726                     typename Node_Itr,
 727                     typename _ATraits_,
 728                     typename _Alloc_>
 729            class Node_Update = null_node_update,
 730            typename _Alloc = std::allocator<char> >
 731   class trie : public PB_DS_TRIE_BASE
 732   {
 733   private:
 734     typedef PB_DS_TRIE_BASE                     base_type;
 735
 736   public:
 737     /// Element access traits type.
 738     typedef _ATraits                            access_traits;
 739
 740     trie() { }
 741
 742     /// Constructor taking some policy objects. r_access_traits will
 743     /// be copied by the _ATraits object of the container object.
 744     trie(const access_traits& t)
 745     : base_type(t) { }
 746
 747     /// Constructor taking __iterators to a range of value_types. The
 748     /// value_types between first_it and last_it will be inserted into
 749     /// the container object.
 750     template<typename It>
 751     trie(It first, It last)
 752     { base_type::copy_from_range(first, last); }
 753
 754     /// Constructor taking __iterators to a range of value_types and
 755     /// some policy objects. The value_types between first_it and
 756     /// last_it will be inserted into the container object.
 757     template<typename It>
 758     trie(It first, It last, const access_traits& t)
 759     : base_type(t)
 760     { base_type::copy_from_range(first, last); }
 761
 762     trie(const trie& other)
 763     : base_type((const base_type&)other) { }
 764
 765     virtual
 766     ~trie() { }
 767
 768     trie&
 769     operator=(const trie& other)
 770     {
 771       if (this != &other)
 772         {
 773           trie tmp(other);
 774           swap(tmp);
 775         }
 776       return *this;
 777     }
 778
 779     void
 780     swap(trie& other)
 781     { base_type::swap(other); }
 782   };
 783   //@} branch-based
 784 #undef PB_DS_TRIE_BASE
 785 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS
 786
 787
 788   /**
 789    *  @defgroup list-based
 790    *  @ingroup containers-pbds
 791    *  @{
 792    */
 793 #define PB_DS_LU_BASE \
 794   detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
 795     typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
 796
 797
 798   /**
 799    *  A list-update based associative container.
 800    *
 801    *  @tparam Key               Key type.
 802    *  @tparam Mapped            Map type.
 803    *  @tparam Eq_Fn             Equal functor.
 804    *  @tparam Update_Policy     Update policy, determines when an element
 805    *                            will be moved to the front of the list.
 806    *  @tparam _Alloc            Allocator type.
 807    *
 808    *  Base is detail::lu_map.
 809    */
 810   template<typename Key,
 811            typename Mapped,
 812            class Eq_Fn = typename detail::default_eq_fn<Key>::type,
 813            class Update_Policy = detail::default_update_policy::type,
 814            class _Alloc = std::allocator<char> >
 815   class list_update : public PB_DS_LU_BASE
 816   {
 817   private:
 818     typedef typename PB_DS_LU_BASE              base_type;
 819
 820   public:
 821     typedef list_update_tag                     container_category;
 822     typedef Eq_Fn                               eq_fn;
 823     typedef Update_Policy                       update_policy;
 824
 825     list_update() { }
 826
 827     /// Constructor taking __iterators to a range of value_types. The
 828     /// value_types between first_it and last_it will be inserted into
 829     /// the container object.
 830     template<typename It>
 831     list_update(It first, It last)
 832     { base_type::copy_from_range(first, last); }
 833
 834     list_update(const list_update& other)
 835     : base_type((const base_type&)other) { }
 836
 837     virtual
 838     ~list_update() { }
 839
 840     list_update&
 841     operator=(const list_update& other)
 842     {
 843       if (this !=& other)
 844         {
 845           list_update tmp(other);
 846           swap(tmp);
 847         }
 848       return *this;
 849     }
 850
 851     void
 852     swap(list_update& other)
 853     { base_type::swap(other); }
 854   };
 855   //@} list-based
 856 #undef PB_DS_LU_BASE
 857
 858   // @} group containers-pbds
 859 } // namespace __gnu_pbds
 860
 861 #endif