diff options
Diffstat (limited to 'libstdc++-v3/include/ext/pb_ds/assoc_container.hpp')
| -rw-r--r-- | libstdc++-v3/include/ext/pb_ds/assoc_container.hpp | 700 |
1 files changed, 700 insertions, 0 deletions
diff --git a/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp new file mode 100644 index 000000000..9cec3b72c --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp @@ -0,0 +1,700 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009, 2010 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/basic_tree_policy/traits.hpp> + +namespace __gnu_pbds +{ + /** @defgroup pbds Policy-Based Data Structures + * @ingroup extensions + * + * This is a library of policy-based elementary data structures: + * associative containers and priority queues. It is designed for + * high-performance, flexibility, semantic safety, and conformance + * to the corresponding containers in std (except for some points + * where it differs by design). + * + * For details, see: + * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html + * + * @{ + */ + +#define PB_DS_BASE_C_DEC \ + detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type + + /// An abstract basic associative container. + template<typename Key, + typename Mapped, + typename Tag, + typename Policy_Tl, + typename Allocator> + class container_base : public PB_DS_BASE_C_DEC + { + private: + typedef typename PB_DS_BASE_C_DEC base_type; + + public: + typedef Tag container_category; + typedef Allocator allocator_type; + typedef typename allocator_type::size_type size_type; + typedef typename allocator_type::difference_type difference_type; + + // key_type + typedef typename allocator_type::template rebind<Key>::other::value_type key_type; + typedef typename allocator_type::template rebind<key_type>::other key_rebind; + typedef typename key_rebind::reference key_reference; + typedef typename key_rebind::const_reference const_key_reference; + typedef typename key_rebind::pointer key_pointer; + typedef typename key_rebind::const_pointer const_key_pointer; + + // mapped_type + typedef Mapped mapped_type; + typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind; + typedef typename mapped_rebind::reference mapped_reference; + typedef typename mapped_rebind::const_reference const_mapped_reference; + typedef typename mapped_rebind::pointer mapped_pointer; + typedef typename mapped_rebind::const_pointer const_mapped_pointer; + + // value_type + typedef typename base_type::value_type value_type; + typedef typename allocator_type::template rebind<value_type>::other value_rebind; + typedef typename value_rebind::reference reference; + typedef typename value_rebind::const_reference const_reference; + typedef typename value_rebind::pointer pointer; + typedef typename value_rebind::const_pointer const_pointer; + + // iterators + typedef typename base_type::iterator iterator; + typedef typename base_type::const_iterator const_iterator; + typedef typename base_type::point_iterator point_iterator; + typedef typename base_type::const_point_iterator const_point_iterator; + + virtual + ~container_base() { } + + protected: +#define PB_DS_CLASS_NAME container_base +#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> +#undef PB_DS_CLASS_NAME + }; + +#undef PB_DS_BASE_C_DEC + + +#define PB_DS_BASE_C_DEC \ + container_base<Key, Mapped, 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, Allocator> + + /// An abstract basic hash-based associative container. + template<typename Key, + typename Mapped, + typename Hash_Fn, + typename Eq_Fn, + typename Resize_Policy, + bool Store_Hash, + typename Tag, + typename Policy_TL, + typename Allocator> + class basic_hash_table : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + virtual + ~basic_hash_table() { } + + protected: +#define PB_DS_CLASS_NAME basic_hash_table +#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> +#undef PB_DS_CLASS_NAME + + private: + basic_hash_table& + operator=(const base_type&); + }; + +#undef PB_DS_BASE_C_DEC + + +#define PB_DS_BASE_C_DEC \ + 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, Allocator> + + /// A concrete collision-chaining hash-based associative container. + 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 Allocator = std::allocator<char> > + class cc_hash_table : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + 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) + { 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) + { 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) + { 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) + { 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_BASE_C_DEC + + +#define PB_DS_BASE_C_DEC \ + 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, Allocator> + + /// A concrete general-probing hash-based associative container. + 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 Allocator = std::allocator<char> > + class gp_hash_table : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + 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); } + }; + +#undef PB_DS_BASE_C_DEC + + +#define PB_DS_BASE_C_DEC \ + container_base<Key, Mapped, Tag, Policy_Tl, Allocator> + + /// An abstract basic tree-like (tree, trie) associative container. + template<typename Key, typename Mapped, typename Tag, + typename Node_Update, typename Policy_Tl, typename Allocator> + class basic_tree : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + typedef Node_Update node_update; + + virtual + ~basic_tree() { } + + protected: +#define PB_DS_CLASS_NAME basic_tree +#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> +#undef PB_DS_CLASS_NAME + }; + +#undef PB_DS_BASE_C_DEC + + +#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \ + detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator> + +#define PB_DS_BASE_C_DEC \ + basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \ + typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator> + + /// A concrete basic tree-based associative container. + template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, + typename Tag = rb_tree_tag, + template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_> + class Node_Update = __gnu_pbds::null_tree_node_update, + typename Allocator = std::allocator<char> > + class tree : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC 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_BASE_C_DEC +#undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC + + +#define PB_DS_TRIE_NODE_AND_ITS_TRAITS \ + detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator> + +#define PB_DS_BASE_C_DEC \ + basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \ + typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator> + + /// A concrete basic trie-based associative container. + template<typename Key, + typename Mapped, + typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type, + typename Tag = pat_trie_tag, + template<typename Const_Node_Iterator, + typename Node_Iterator, + typename E_Access_Traits_, + typename Allocator_> + class Node_Update = null_trie_node_update, + typename Allocator = std::allocator<char> > + class trie : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + // Element access traits type. + typedef E_Access_Traits e_access_traits; + + trie() { } + + // Constructor taking some policy objects. r_e_access_traits will + // be copied by the E_Access_Traits object of the container + // object. + trie(const e_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 e_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_BASE_C_DEC +#undef PB_DS_TRIE_NODE_AND_ITS_TRAITS + + +#define PB_DS_BASE_C_DEC \ + container_base<Key, Mapped, list_update_tag, \ + typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator> + + /// A list-update based associative container. + template<typename Key, + typename Mapped, + class Eq_Fn = typename detail::default_eq_fn<Key>::type, + class Update_Policy = detail::default_update_policy::type, + class Allocator = std::allocator<char> > + class list_update : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + + public: + typedef Eq_Fn eq_fn; + typedef Update_Policy update_policy; + typedef Allocator allocator; + + 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); } + }; + +#undef PB_DS_BASE_C_DEC + + // @} group pbds +} // namespace __gnu_pbds + +#endif |