Subversion Repositories altor32

// -*- C++ -*-

// Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the terms

// of the GNU General Public License as published by the Free Software

// Foundation; either version 3, or (at your option) any later

// version.

// This library is distributed in the hope that it will be useful, but

// WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software

// is hereby granted without fee, provided that the above copyright

// notice appears in all copies, and that both that copyright notice

// and this permission notice appear in supporting documentation. None

// of the above authors, nor IBM Haifa Research Laboratories, make any

// representation about the suitability of this software for any

// purpose. It is provided "as is" without express or implied

// warranty.

/**

 * @file assoc_container.hpp

 * Contains associative containers.

 */

#ifndef PB_DS_ASSOC_CNTNR_HPP

#define PB_DS_ASSOC_CNTNR_HPP

#include <bits/c++config.h>

#include <ext/typelist.h>

#include <ext/pb_ds/tag_and_trait.hpp>

#include <ext/pb_ds/detail/standard_policies.hpp>

#include <ext/pb_ds/detail/container_base_dispatch.hpp>

#include <ext/pb_ds/detail/branch_policy/traits.hpp>

namespace __gnu_pbds

{

  /**

   *  @defgroup containers-pbds Containers

   *  @ingroup pbds

   *  @{

   */

  /**

   *  @defgroup hash-based Hash-Based

   *  @ingroup containers-pbds

   *  @{

   */

#define PB_DS_HASH_BASE \

  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \

    typename __gnu_cxx::typelist::append< \

    typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \

    detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type

  /**

   *  @defgroup hash-detail Base and Policy Classes

   *  @ingroup hash-based

   */

  /**

   *  A hashed container abstraction.

   *

   *  @tparam Key               Key type.

   *  @tparam Mapped            Map type.

   *  @tparam Hash_Fn           Hashing functor.

   *  @tparam Eq_Fn             Equal functor.

   *  @tparam Resize_Policy     Resizes hash.

   *  @tparam Store_Hash        Indicates whether the hash value

   *                            will be stored along with each key.

   *  @tparam Tag               Instantiating data structure type,

   *                            see container_tag.

   *  @tparam Policy_TL         Policy typelist.

   *  @tparam _Alloc            Allocator type.

   *

   *  Base is dispatched at compile time via Tag, from the following

   *  choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.

   *

   *  Base choices are: detail::cc_ht_map, detail::gp_ht_map

   */

  template<typename Key,

           typename Mapped,

           typename Hash_Fn,

           typename Eq_Fn,

           typename Resize_Policy,

           bool Store_Hash,

           typename Tag,

           typename Policy_Tl,

           typename _Alloc>

  class basic_hash_table : public PB_DS_HASH_BASE

  {

  private:

    typedef typename PB_DS_HASH_BASE            base_type;

  public:

    virtual

    ~basic_hash_table() { }

  protected:

    basic_hash_table() { }

    basic_hash_table(const basic_hash_table& other)

    : base_type((const base_type&)other) { }

    template<typename T0>

      basic_hash_table(T0 t0) : base_type(t0) { }

    template<typename T0, typename T1>

      basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }

    template<typename T0, typename T1, typename T2>

      basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }

    template<typename T0, typename T1, typename T2, typename T3>

      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)

      : base_type(t0, t1, t2, t3) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4>

      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)

      : base_type(t0, t1, t2, t3, t4) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4,

             typename T5>

      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)

      : base_type(t0, t1, t2, t3, t4, t5) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4,

             typename T5, typename T6>

      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)

      : base_type(t0, t1, t2, t3, t4, t5, t6) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4,

             typename T5, typename T6, typename T7>

      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)

      : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4,

             typename T5, typename T6, typename T7, typename T8>

      basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,

                       T7 t7, T8 t8)

      : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)

      { }

  private:

    basic_hash_table&

    operator=(const base_type&);

  };

#undef PB_DS_HASH_BASE

#define PB_DS_CC_HASH_BASE \

  basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \

                   cc_hash_tag, \

          typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>

  /**

   *  A collision-chaining hash-based associative container.

   *

   *  @tparam Key               Key type.

   *  @tparam Mapped            Map type.

   *  @tparam Hash_Fn           Hashing functor.

   *  @tparam Eq_Fn             Equal functor.

   *  @tparam Comb_Hash_Fn      Combining hash functor.

   *                            If Hash_Fn is not null_type, then this

   *                            is the ranged-hash functor; otherwise,

   *                            this is the range-hashing functor.

   *                    XXX(See Design::Hash-Based Containers::Hash Policies.)

   *  @tparam Resize_Policy     Resizes hash.

   *  @tparam Store_Hash        Indicates whether the hash value

   *                            will be stored along with each key.

   *                            If Hash_Fn is null_type, then the

   *                            container will not compile if this

   *                            value is true

   *  @tparam _Alloc            Allocator type.

   *

   *  Base tag choices are:     cc_hash_tag.

   *

   *  Base is basic_hash_table.

   */

  template<typename Key,

           typename Mapped,

           typename Hash_Fn = typename detail::default_hash_fn<Key>::type,

           typename Eq_Fn = typename detail::default_eq_fn<Key>::type,

           typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,

           typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,

           bool Store_Hash = detail::default_store_hash,

           typename _Alloc = std::allocator<char> >

  class cc_hash_table :  public PB_DS_CC_HASH_BASE

  {

  private:

    typedef PB_DS_CC_HASH_BASE                  base_type;

  public:

    typedef cc_hash_tag                         container_category;

    typedef Hash_Fn                             hash_fn;

    typedef Eq_Fn                               eq_fn;

    typedef Resize_Policy                       resize_policy;

    typedef Comb_Hash_Fn                        comb_hash_fn;

    /// Default constructor.

    cc_hash_table() { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the Hash_Fn object of the container object.

    cc_hash_table(const hash_fn& h)

    : base_type(h) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, and

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object.

    cc_hash_table(const hash_fn& h, const eq_fn& e)

    : base_type(h, e) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, r_eq_fn

    /// will be copied by the eq_fn object of the container object,

    /// and r_comb_hash_fn will be copied by the comb_hash_fn object

    /// of the container object.

    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)

    : base_type(h, e, ch) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, r_eq_fn

    /// will be copied by the eq_fn object of the container object,

    /// r_comb_hash_fn will be copied by the comb_hash_fn object of

    /// the container object, and r_resize_policy will be copied by

    /// the resize_policy object of the container object.

    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,

                  const resize_policy& rp)

    : base_type(h, e, ch, rp) { }

    /// Constructor taking __iterators to a range of value_types. The

    /// value_types between first_it and last_it will be inserted into

    /// the container object.

    template<typename It>

    cc_hash_table(It first, It last)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects. The value_types between first_it and

    /// last_it will be inserted into the container object.

    template<typename It>

    cc_hash_table(It first, It last, const hash_fn& h)

    : base_type(h)

    { this->copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// and r_eq_fn will be copied by the eq_fn object of the

    /// container object.

    template<typename It>

    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)

    : base_type(h, e)

    { this->copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object, and r_comb_hash_fn will be copied by the comb_hash_fn

    /// object of the container object.

    template<typename It>

    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,

                  const comb_hash_fn& ch)

    : base_type(h, e, ch)

    { this->copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object, r_comb_hash_fn will be copied by the comb_hash_fn

    /// object of the container object, and r_resize_policy will be

    /// copied by the resize_policy object of the container object.

    template<typename It>

    cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,

                  const comb_hash_fn& ch, const resize_policy& rp)

    : base_type(h, e, ch, rp)

    { this->copy_from_range(first, last); }

    cc_hash_table(const cc_hash_table& other)

    : base_type((const base_type&)other)

    { }

    virtual

    ~cc_hash_table() { }

    cc_hash_table&

    operator=(const cc_hash_table& other)

    {

      if (this != &other)

        {

          cc_hash_table tmp(other);

          swap(tmp);

        }

      return *this;

    }

    void

    swap(cc_hash_table& other)

    { base_type::swap(other); }

  };

#undef PB_DS_CC_HASH_BASE

#define PB_DS_GP_HASH_BASE \

  basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \

                   gp_hash_tag, \

  typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>

  /**

   *  A general-probing hash-based associative container.

   *

   *  @tparam Key               Key type.

   *  @tparam Mapped            Map type.

   *  @tparam Hash_Fn           Hashing functor.

   *  @tparam Eq_Fn             Equal functor.

   *  @tparam Comb_Probe_Fn     Combining probe functor.

   *                            If Hash_Fn is not null_type, then this

   *                            is the ranged-probe functor; otherwise,

   *                            this is the range-hashing functor.

   *                    XXX See Design::Hash-Based Containers::Hash Policies.

   *  @tparam Probe_Fn          Probe functor.

   *  @tparam Resize_Policy     Resizes hash.

   *  @tparam Store_Hash        Indicates whether the hash value

   *                            will be stored along with each key.

   *                            If Hash_Fn is null_type, then the

   *                            container will not compile if this

   *                            value is true

   *  @tparam _Alloc            Allocator type.

   *

   *  Base tag choices are:     gp_hash_tag.

   *

   *  Base is basic_hash_table.

   */

  template<typename Key,

           typename Mapped,

           typename Hash_Fn = typename detail::default_hash_fn<Key>::type,

           typename Eq_Fn = typename detail::default_eq_fn<Key>::type,

           typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,

           typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,

           typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,

           bool Store_Hash = detail::default_store_hash,

           typename _Alloc = std::allocator<char> >

  class gp_hash_table : public PB_DS_GP_HASH_BASE

  {

  private:

    typedef PB_DS_GP_HASH_BASE                  base_type;

  public:

    typedef gp_hash_tag                         container_category;

    typedef Hash_Fn                             hash_fn;

    typedef Eq_Fn                               eq_fn;

    typedef Comb_Probe_Fn                       comb_probe_fn;

    typedef Probe_Fn                            probe_fn;

    typedef Resize_Policy                       resize_policy;

    /// Default constructor.

    gp_hash_table() { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object.

    gp_hash_table(const hash_fn& h)

    : base_type(h) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, and

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object.

    gp_hash_table(const hash_fn& h, const eq_fn& e)

    : base_type(h, e) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, r_eq_fn

    /// will be copied by the eq_fn object of the container object,

    /// and r_comb_probe_fn will be copied by the comb_probe_fn object

    /// of the container object.

    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)

    : base_type(h, e, cp) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, r_eq_fn

    /// will be copied by the eq_fn object of the container object,

    /// r_comb_probe_fn will be copied by the comb_probe_fn object of

    /// the container object, and r_probe_fn will be copied by the

    /// probe_fn object of the container object.

    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,

                  const probe_fn& p)

    : base_type(h, e, cp, p) { }

    /// Constructor taking some policy objects. r_hash_fn will be

    /// copied by the hash_fn object of the container object, r_eq_fn

    /// will be copied by the eq_fn object of the container object,

    /// r_comb_probe_fn will be copied by the comb_probe_fn object of

    /// the container object, r_probe_fn will be copied by the

    /// probe_fn object of the container object, and r_resize_policy

    /// will be copied by the Resize_Policy object of the container

    /// object.

    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,

                  const probe_fn& p, const resize_policy& rp)

    : base_type(h, e, cp, p, rp) { }

    /// Constructor taking __iterators to a range of value_types. The

    /// value_types between first_it and last_it will be inserted into

    /// the container object.

    template<typename It>

    gp_hash_table(It first, It last)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects. The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object.

    template<typename It>

    gp_hash_table(It first, It last, const hash_fn& h)

    : base_type(h)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects. The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// and r_eq_fn will be copied by the eq_fn object of the

    /// container object.

    template<typename It>

    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)

    : base_type(h, e)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects. The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object, and r_comb_probe_fn will be copied by the

    /// comb_probe_fn object of the container object.

    template<typename It>

    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,

                  const comb_probe_fn& cp)

    : base_type(h, e, cp)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects. The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object, r_comb_probe_fn will be copied by the comb_probe_fn

    /// object of the container object, and r_probe_fn will be copied

    /// by the probe_fn object of the container object.

    template<typename It>

    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,

                  const comb_probe_fn& cp, const probe_fn& p)

    : base_type(h, e, cp, p)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects. The value_types between first_it and

    /// last_it will be inserted into the container object. r_hash_fn

    /// will be copied by the hash_fn object of the container object,

    /// r_eq_fn will be copied by the eq_fn object of the container

    /// object, r_comb_probe_fn will be copied by the comb_probe_fn

    /// object of the container object, r_probe_fn will be copied by

    /// the probe_fn object of the container object, and

    /// r_resize_policy will be copied by the resize_policy object of

    /// the container object.

    template<typename It>

    gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,

                  const comb_probe_fn& cp, const probe_fn& p,

                  const resize_policy& rp)

    : base_type(h, e, cp, p, rp)

    { base_type::copy_from_range(first, last); }

    gp_hash_table(const gp_hash_table& other)

    : base_type((const base_type&)other)

    { }

    virtual

    ~gp_hash_table() { }

    gp_hash_table&

    operator=(const gp_hash_table& other)

    {

      if (this != &other)

        {

          gp_hash_table tmp(other);

          swap(tmp);

        }

      return *this;

    }

    void

    swap(gp_hash_table& other)

    { base_type::swap(other); }

  };

  //@} hash-based

#undef PB_DS_GP_HASH_BASE

  /**

   *  @defgroup branch-based Branch-Based

   *  @ingroup containers-pbds

   *  @{

   */

#define PB_DS_BRANCH_BASE \

  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type

  /**

   *  @defgroup branch-detail Base and Policy Classes

   *  @ingroup branch-based

   */

  /**

   *  A branched, tree-like (tree, trie) container abstraction.

   *

   *  @tparam Key               Key type.

   *  @tparam Mapped            Map type.

   *  @tparam Tag               Instantiating data structure type,

   *                            see container_tag.

   *  @tparam Node_Update       Updates nodes, restores invariants.

   *  @tparam Policy_TL         Policy typelist.

   *  @tparam _Alloc            Allocator type.

   *

   *  Base is dispatched at compile time via Tag, from the following

   *  choices: tree_tag, trie_tag, and their descendants.

   *

   *  Base choices are: detail::ov_tree_map, detail::rb_tree_map,

   *                    detail::splay_tree_map, and detail::pat_trie_map.

   */

  template<typename Key, typename Mapped, typename Tag,

           typename Node_Update, typename Policy_Tl, typename _Alloc>

  class basic_branch : public PB_DS_BRANCH_BASE

  {

  private:

    typedef typename PB_DS_BRANCH_BASE          base_type;

  public:

    typedef Node_Update                         node_update;

    virtual

    ~basic_branch() { }

  protected:

    basic_branch() { }

    basic_branch(const basic_branch& other)

    : base_type((const base_type&)other) { }

    template<typename T0>

      basic_branch(T0 t0) : base_type(t0) { }

    template<typename T0, typename T1>

      basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }

    template<typename T0, typename T1, typename T2>

      basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }

    template<typename T0, typename T1, typename T2, typename T3>

      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)

      : base_type(t0, t1, t2, t3) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4>

      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)

      : base_type(t0, t1, t2, t3, t4) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4,

             typename T5>

      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)

      : base_type(t0, t1, t2, t3, t4, t5) { }

    template<typename T0, typename T1, typename T2, typename T3, typename T4,

             typename T5, typename T6>

      basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)

      : base_type(t0, t1, t2, t3, t4, t5, t6) { }

  };

#undef PB_DS_BRANCH_BASE

#define PB_DS_TREE_NODE_AND_IT_TRAITS \

  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>

#define PB_DS_TREE_BASE \

  basic_branch<Key,Mapped, Tag, \

               typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \

               typename __gnu_cxx::typelist::create2<Cmp_Fn, \

               PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>

  /**

   *  A tree-based container.

   *

   *  @tparam Key               Key type.

   *  @tparam Mapped            Map type.

   *  @tparam Cmp_Fn            Comparison functor.

   *  @tparam Tag               Instantiating data structure type,

   *                            see container_tag.

   *  @tparam Node_Update       Updates tree internal-nodes,

   *                            restores invariants when invalidated.

   *                     XXX See design::tree-based-containers::node invariants.

   *  @tparam _Alloc            Allocator type.

   *

   *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.

   *

   *  Base is basic_branch.

   */

  template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,

           typename Tag = rb_tree_tag,

           template<typename Node_CItr, typename Node_Itr,

                    typename Cmp_Fn_, typename _Alloc_>

           class Node_Update = null_node_update,

           typename _Alloc = std::allocator<char> >

  class tree : public PB_DS_TREE_BASE

  {

  private:

    typedef PB_DS_TREE_BASE                     base_type;

  public:

    /// Comparison functor type.

    typedef Cmp_Fn                              cmp_fn;

    tree() { }

    /// Constructor taking some policy objects. r_cmp_fn will be

    /// copied by the Cmp_Fn object of the container object.

    tree(const cmp_fn& c)

    : base_type(c) { }

    /// Constructor taking __iterators to a range of value_types. The

    /// value_types between first_it and last_it will be inserted into

    /// the container object.

    template<typename It>

    tree(It first, It last)

    { base_type::copy_from_range(first, last); }

    /// Constructor taking __iterators to a range of value_types and

    /// some policy objects The value_types between first_it and

    /// last_it will be inserted into the container object. r_cmp_fn

    /// will be copied by the cmp_fn object of the container object.

    template<typename It>

    tree(It first, It last, const cmp_fn& c)

    : base_type(c)

    { base_type::copy_from_range(first, last); }

    tree(const tree& other)

    : base_type((const base_type&)other) { }

    virtual

    ~tree() { }

    tree&

    operator=(const tree& other)

    {

      if (this != &other)

        {

          tree tmp(other);

          swap(tmp);

        }

      return *this;

    }

    void

    swap(tree& other)

    { base_type::swap(other); }

  };

#undef PB_DS_TREE_BASE

#undef PB_DS_TREE_NODE_AND_IT_TRAITS

#define PB_DS_TRIE_NODE_AND_IT_TRAITS \

  detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>

#define PB_DS_TRIE_BASE \

  basic_branch<Key,Mapped,Tag, \

               typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \

               typename __gnu_cxx::typelist::create2<_ATraits, \

               PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>

  /**

   *  A trie-based container.

   *

   *  @tparam Key               Key type.

   *  @tparam Mapped            Map type.

   *  @tparam _ATraits          Element access traits.

   *  @tparam Tag               Instantiating data structure type,

   *                            see container_tag.

   *  @tparam Node_Update       Updates trie internal-nodes,

   *                            restores invariants when invalidated.

   *                     XXX See design::tree-based-containers::node invariants.

   *  @tparam _Alloc            Allocator type.

   *

   *  Base tag choice is pat_trie_tag.

   *

   *  Base is basic_branch.

   */

  template<typename Key,

           typename Mapped,

           typename _ATraits = \

                    typename detail::default_trie_access_traits<Key>::type,

           typename Tag = pat_trie_tag,

           template<typename Node_CItr,

                    typename Node_Itr,

                    typename _ATraits_,

                    typename _Alloc_>

           class Node_Update = null_node_update,

           typename _Alloc = std::allocator<char> >

  class trie : public PB_DS_TRIE_BASE

  {

  private:

    typedef PB_DS_TRIE_BASE                     base_type;

  public:

    /// Element access traits type.

    typedef _ATraits                            access_traits;