--- /dev/null
+// -*- 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
+ * @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
+ * @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 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 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;
+
+ trie() { }
+
+ /// Constructor taking some policy objects. r_access_traits will
+ /// be copied by the _ATraits object of the container object.
+ trie(const access_traits& t)
+ : base_type(t) { }
+
+ /// 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>
+ trie(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>
+ 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); }
+ };
+ //@} branch-based
+#undef PB_DS_TRIE_BASE
+#undef PB_DS_TRIE_NODE_AND_IT_TRAITS
+
+
+ /**
+ * @defgroup list-based
+ * @ingroup containers-pbds
+ * @{
+ */
+#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
+
+
+ /**
+ * A list-update based associative container.
+ *
+ * @tparam Key Key type.
+ * @tparam Mapped Map type.
+ * @tparam Eq_Fn Equal functor.
+ * @tparam Update_Policy Update policy, determines when an element
+ * will be moved to the front of the list.
+ * @tparam _Alloc Allocator type.
+ *
+ * Base is detail::lu_map.
+ */
+ 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() { }
+
+ /// 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>
+ 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); }
+ };
+ //@} list-based
+#undef PB_DS_LU_BASE
+
+ // @} group containers-pbds
+} // namespace __gnu_pbds
+
+#endif
projects / cross.git / blobdiff