X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fext%2Fpb_ds%2Fassoc_container.hpp;fp=libstdc%2B%2B-v3%2Finclude%2Fext%2Fpb_ds%2Fassoc_container.hpp;h=7bccb88fff112e2d005d3173fb266bb39f5926a1;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git 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 00000000..7bccb88f --- /dev/null +++ b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp @@ -0,0 +1,683 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 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 +// . + +// 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 +#include +#include +#include +#include + +namespace __gnu_pbds +{ +#define PB_DS_BASE_C_DEC \ + detail::container_base_dispatch::type + + // An abstract basic associative container. + template + 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::other::value_type key_type; + typedef typename allocator_type::template rebind::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::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::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 +#undef PB_DS_CLASS_NAME + }; + +#undef PB_DS_BASE_C_DEC + + +#define PB_DS_BASE_C_DEC \ + container_base >::type, Policy_TL>::type, Allocator> + + // An abstract basic hash-based associative container. + template + 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 +#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::type, Allocator> + + // A concrete collision-chaining hash-based associative container. + template::type, + typename Eq_Fn = typename detail::default_eq_fn::type, + typename Comb_Hash_Fn = detail::default_comb_hash_fn::type, + typename Resize_Policy = typename detail::default_resize_policy::type, + bool Store_Hash = detail::default_store_hash, + typename Allocator = std::allocator > + 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 + 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 + 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 + 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 + 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 + 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::type, Allocator> + + // A concrete general-probing hash-based associative container. + template::type, + typename Eq_Fn = typename detail::default_eq_fn::type, + typename Comb_Probe_Fn = detail::default_comb_hash_fn::type, + typename Probe_Fn = typename detail::default_probe_fn::type, + typename Resize_Policy = typename detail::default_resize_policy::type, + bool Store_Hash = detail::default_store_hash, + typename Allocator = std::allocator > + 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 + 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 + 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 + 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 + 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 + 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 + 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 + + // An abstract basic tree-like (tree, trie) associative container. + template + 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 +#undef PB_DS_CLASS_NAME + }; + +#undef PB_DS_BASE_C_DEC + + +#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \ + detail::tree_traits + +#define PB_DS_BASE_C_DEC \ + basic_tree::type, Allocator> + + // A concrete basic tree-based associative container. + template, + typename Tag = rb_tree_tag, + template + class Node_Update = __gnu_pbds::null_tree_node_update, + typename Allocator = std::allocator > + 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 + 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 + 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 + +#define PB_DS_BASE_C_DEC \ + basic_tree::type, Allocator> + + // A concrete basic trie-based associative container. + template::type, + typename Tag = pat_trie_tag, + template + class Node_Update = null_trie_node_update, + typename Allocator = std::allocator > + 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 + 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 + 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::type, Allocator> + + // A list-update based associative container. + template::type, + class Update_Policy = detail::default_update_policy::type, + class Allocator = std::allocator > + 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 + 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 + +} // namespace __gnu_pbds + +#endif