assoc_container.hpp

Go to the documentation of this file.

// -*- C++ -*-

// Copyright (C) 2005-2013 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.

#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
{
#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

  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>


  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;

    cc_hash_table() { }

    cc_hash_table(const hash_fn& h)
    : base_type(h) { }

    cc_hash_table(const hash_fn& h, const eq_fn& e)
    : base_type(h, e) { }

    cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
    : base_type(h, e, ch) { }

    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) { }

    template<typename It>
    cc_hash_table(It first, It last)
    { base_type::copy_from_range(first, last); }

    template<typename It>
    cc_hash_table(It first, It last, const hash_fn& h)
    : base_type(h)
    { this->copy_from_range(first, last); }

    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); }

    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); }

    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>


  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;

    gp_hash_table() { }

    gp_hash_table(const hash_fn& h)
    : base_type(h) { }

    gp_hash_table(const hash_fn& h, const eq_fn& e)
    : base_type(h, e) { }

    gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
    : base_type(h, e, cp) { }

    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) { }

    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) { }

    template<typename It>
    gp_hash_table(It first, It last)
    { base_type::copy_from_range(first, last); }

    template<typename It>
    gp_hash_table(It first, It last, const hash_fn& h)
    : base_type(h)
    { base_type::copy_from_range(first, last); }

    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); }

    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); }

    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); }

    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); }
  };
#undef PB_DS_GP_HASH_BASE


#define PB_DS_BRANCH_BASE \
  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type

  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>


  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:
    typedef Cmp_Fn              cmp_fn;

    tree() { }

    tree(const cmp_fn& c)
    : base_type(c) { }

    template<typename It>
    tree(It first, It last)
    { base_type::copy_from_range(first, last); }

    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>


  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:
    typedef _ATraits                access_traits;

    trie() { }

    trie(const access_traits& t)
    : base_type(t) { }

    template<typename It>
    trie(It first, It last)
    { base_type::copy_from_range(first, last); }

    template<typename It>
    trie(It first, It last, const access_traits& t)
    : base_type(t)
    { base_type::copy_from_range(first, last); }

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

    virtual
    ~trie() { }

    trie&
    operator=(const trie& other)
    {
      if (this != &other)
    {
      trie tmp(other);
      swap(tmp);
    }
      return *this;
    }

    void
    swap(trie& other)
    { base_type::swap(other); }
  };
#undef PB_DS_TRIE_BASE
#undef PB_DS_TRIE_NODE_AND_IT_TRAITS


#define PB_DS_LU_BASE \
  detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
    typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type


  template<typename Key,
       typename Mapped,
       class Eq_Fn = typename detail::default_eq_fn<Key>::type,
       class Update_Policy = detail::default_update_policy::type,
       class _Alloc = std::allocator<char> >
  class list_update : public PB_DS_LU_BASE
  {
  private:
    typedef typename PB_DS_LU_BASE      base_type;

  public:
    typedef list_update_tag             container_category;
    typedef Eq_Fn               eq_fn;
    typedef Update_Policy           update_policy;

    list_update() { }

    template<typename It>
    list_update(It first, It last)
    { base_type::copy_from_range(first, last); }

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

    virtual
    ~list_update() { }

    list_update&
    operator=(const list_update& other)
    {
      if (this !=& other)
    {
      list_update tmp(other);
      swap(tmp);
    }
      return *this;
    }

    void
    swap(list_update& other)
    { base_type::swap(other); }
  };
#undef PB_DS_LU_BASE

  // @} group containers-pbds
} // namespace __gnu_pbds

#endif