diff options
68 files changed, 1294 insertions, 1380 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index b2a183c596c..f02cede5506 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,9 @@ +2011-06-10 Benjamin Kosnik <bkoz@redhat.com> + + * include/ext/pb_ds/*: Doxygen markup redo. + * include/Makefile.am: Fold in constructors_destructor_fn_imps.hpp. + * include/Makefile.in: Regenerate. + 2011-06-10 Jason Merrill <jason@redhat.com> * testsuite/20_util/bind/ref_neg.cc: Remove wrong test lines. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index a4b7f27aaa4..6a21c162216 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -314,7 +314,6 @@ pb_headers2 = \ pb_headers3 = \ ${pb_srcdir}/detail/cc_hash_table_map_/trace_fn_imps.hpp \ ${pb_srcdir}/detail/cond_dealtor.hpp \ - ${pb_srcdir}/detail/constructors_destructor_fn_imps.hpp \ ${pb_srcdir}/detail/container_base_dispatch.hpp \ ${pb_srcdir}/detail/eq_fn/eq_by_less.hpp \ ${pb_srcdir}/detail/eq_fn/hash_eq_fn.hpp \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 3cbe0e4500e..5b05ef3fe6c 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -564,7 +564,6 @@ pb_headers2 = \ pb_headers3 = \ ${pb_srcdir}/detail/cc_hash_table_map_/trace_fn_imps.hpp \ ${pb_srcdir}/detail/cond_dealtor.hpp \ - ${pb_srcdir}/detail/constructors_destructor_fn_imps.hpp \ ${pb_srcdir}/detail/container_base_dispatch.hpp \ ${pb_srcdir}/detail/eq_fn/eq_by_less.hpp \ ${pb_srcdir}/detail/eq_fn/hash_eq_fn.hpp \ diff --git a/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp index d366f431ccf..e31da0e442e 100644 --- a/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp +++ b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp @@ -51,17 +51,47 @@ namespace __gnu_pbds { /** - * @addtogroup 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 - /// An abstract basic hash-based associative container. + /** + * @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, @@ -81,9 +111,49 @@ namespace __gnu_pbds ~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 + 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& @@ -98,7 +168,31 @@ namespace __gnu_pbds cc_hash_tag, \ typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc> - /// A concrete collision-chaining hash-based associative container. + + /** + * 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, @@ -119,86 +213,86 @@ namespace __gnu_pbds typedef Resize_Policy resize_policy; typedef Comb_Hash_Fn comb_hash_fn; - // Default constructor. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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) @@ -236,7 +330,32 @@ namespace __gnu_pbds gp_hash_tag, \ typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc> - /// A concrete general-probing hash-based associative container. + + /** + * 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, @@ -259,114 +378,115 @@ namespace __gnu_pbds typedef Probe_Fn probe_fn; typedef Resize_Policy resize_policy; - // Default constructor. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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. + /// 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, @@ -396,13 +516,40 @@ namespace __gnu_pbds 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 - /// An abstract basic tree-like (tree, trie) associative container. + /** + * @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 @@ -417,11 +564,38 @@ namespace __gnu_pbds ~basic_branch() { } protected: -#define PB_DS_CLASS_NAME basic_branch -#include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> -#undef PB_DS_CLASS_NAME - }; + 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 @@ -434,7 +608,24 @@ namespace __gnu_pbds typename __gnu_cxx::typelist::create2<Cmp_Fn, \ PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc> - /// A basic tree-based associative container. + + /** + * 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, @@ -447,30 +638,30 @@ namespace __gnu_pbds typedef PB_DS_TREE_BASE base_type; public: - // Comparison functor type. + /// 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. + /// 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. + /// 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. + /// 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(c) { base_type::copy_from_range(first, last); } tree(const tree& other) @@ -508,7 +699,24 @@ namespace __gnu_pbds typename __gnu_cxx::typelist::create2<_ATraits, \ PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc> - /// A basic trie-based associative container. + + /** + * 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 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 = \ @@ -526,27 +734,26 @@ namespace __gnu_pbds typedef PB_DS_TRIE_BASE base_type; public: - // Element access traits type. + /// 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. + /// 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. + /// 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. + /// 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) @@ -573,16 +780,33 @@ namespace __gnu_pbds 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. + + /** + * 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, @@ -600,9 +824,9 @@ namespace __gnu_pbds 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. + /// 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); } @@ -628,10 +852,10 @@ namespace __gnu_pbds swap(list_update& other) { base_type::swap(other); } }; - + //@} list-based #undef PB_DS_LU_BASE - // @} group pbds + // @} group containers-pbds } // namespace __gnu_pbds #endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp deleted file mode 100644 index 0ca90dbc791..00000000000 --- a/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/basic_tree_policy_base.hpp +++ /dev/null @@ -1,173 +0,0 @@ -// -*- 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 -// <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 basic_tree_policy_base.hpp - * Contains a base class for tree_like policies. - */ - -#ifndef PB_DS_TREE_LIKE_POLICY_BASE_HPP -#define PB_DS_TREE_LIKE_POLICY_BASE_HPP - -namespace __gnu_pbds -{ - namespace detail - { - -#define PB_DS_CLASS_C_DEC \ - basic_tree_policy_base< \ - Const_Node_Iterator, \ - Node_Iterator, \ - Allocator> - - template<typename Const_Node_Iterator, - typename Node_Iterator, - typename Allocator> - struct basic_tree_policy_base - { - protected: - typedef typename Node_Iterator::value_type it_type; - - typedef typename std::iterator_traits< it_type>::value_type value_type; - - typedef typename value_type::first_type key_type; - - typedef - typename Allocator::template rebind< - typename remove_const< - key_type>::type>::other::const_reference - const_key_reference; - - typedef - typename Allocator::template rebind< - typename remove_const< - value_type>::type>::other::const_reference - const_reference; - - typedef - typename Allocator::template rebind< - typename remove_const< - value_type>::type>::other::reference - reference; - - typedef - typename Allocator::template rebind< - typename remove_const< - value_type>::type>::other::const_pointer - const_pointer; - - static inline const_key_reference - extract_key(const_reference r_val) - { - return (r_val.first); - } - - virtual it_type - end() = 0; - - it_type - end_iterator() const - { - return (const_cast<PB_DS_CLASS_C_DEC* >(this)->end()); - } - - virtual - ~basic_tree_policy_base() - { } - }; - - template<typename Const_Node_Iterator, typename Allocator> - struct basic_tree_policy_base< - Const_Node_Iterator, - Const_Node_Iterator, - Allocator> - { - protected: - typedef typename Const_Node_Iterator::value_type it_type; - - typedef typename std::iterator_traits< it_type>::value_type value_type; - - typedef value_type key_type; - - typedef - typename Allocator::template rebind< - typename remove_const< - key_type>::type>::other::const_reference - const_key_reference; - - typedef - typename Allocator::template rebind< - typename remove_const< - value_type>::type>::other::const_reference - const_reference; - - typedef - typename Allocator::template rebind< - typename remove_const< - value_type>::type>::other::reference - reference; - - typedef - typename Allocator::template rebind< - typename remove_const< - value_type>::type>::other::const_pointer - const_pointer; - - static inline const_key_reference - extract_key(const_reference r_val) - { - return (r_val); - } - - virtual it_type - end() const = 0; - - it_type - end_iterator() const - { - return (end()); - } - - virtual - ~basic_tree_policy_base() - { } - }; - -#undef PB_DS_CLASS_C_DEC - - } // namespace detail -} // namespace __gnu_pbds - -#endif // #ifndef PB_DS_TREE_LIKE_POLICY_BASE_HPP diff --git a/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp b/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp deleted file mode 100644 index e600f2ca36e..00000000000 --- a/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp +++ /dev/null @@ -1,67 +0,0 @@ -// -*- 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 null_node_metadata.hpp - * Contains an implementation class for tree-like classes. - */ - -#ifndef PB_DS_0_NODE_METADATA_HPP -#define PB_DS_0_NODE_METADATA_HPP - -#include <ext/pb_ds/detail/types_traits.hpp> - -namespace __gnu_pbds -{ - namespace detail - { - template<typename Key, class Data, class Allocator> - struct dumconst_node_iterator - { - private: - typedef typename types_traits<Key, Data, Allocator, false>::pointer const_iterator; - - public: - typedef const_iterator value_type; - typedef const_iterator const_reference; - typedef const_reference reference; - }; - - struct null_node_metadata - { }; - } // namespace detail -} // namespace __gnu_pbds - -#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/traits.hpp deleted file mode 100644 index d245127c875..00000000000 --- a/libstdc++-v3/include/ext/pb_ds/detail/basic_tree_policy/traits.hpp +++ /dev/null @@ -1,92 +0,0 @@ -// -*- 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 -// <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 traits.hpp - * Contains an implementation class for tree-like classes. - */ - -#ifndef PB_DS_NODE_AND_IT_TRAITS_HPP -#define PB_DS_NODE_AND_IT_TRAITS_HPP - -#define PB_DS_DEBUG_VERIFY(_Cond) \ - _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ - _M_message(#_Cond" assertion from %1;:%2;") \ - ._M_string(__FILE__)._M_integer(__LINE__) \ - ,__file,__line) - -#include <ext/pb_ds/detail/types_traits.hpp> -#include <ext/pb_ds/detail/bin_search_tree_/traits.hpp> -#include <ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp> -#include <ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp> - -namespace __gnu_pbds -{ - namespace detail - { - template<typename Key, - typename Data, - class Cmp_Fn, - template<typename Const_Node_Iterator, - class Node_Iterator, - class Cmp_Fn_, - class Allocator> - class Node_Update, - class Tag, - class Allocator> - struct tree_traits; - - template<typename Key, - typename Data, - class E_Access_Traits, - template<typename Const_Node_Iterator, - class Node_Iterator, - class E_Access_Traits_, - class Allocator> - class Node_Update, - class Tag, - class Allocator> - struct trie_traits; - - } // namespace detail -} // namespace __gnu_pbds - -#include <ext/pb_ds/detail/rb_tree_map_/traits.hpp> -#include <ext/pb_ds/detail/splay_tree_/traits.hpp> -#include <ext/pb_ds/detail/ov_tree_map_/traits.hpp> -#include <ext/pb_ds/detail/pat_trie_/traits.hpp> -#undef PB_DS_DEBUG_VERIFY - -#endif // #ifndef PB_DS_NODE_AND_IT_TRAITS_HPP diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp index a875e300d4d..4f847083ba7 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp @@ -237,15 +237,23 @@ namespace __gnu_pbds inline const_reverse_iterator rend() const; + /// Returns a const node_iterator corresponding to the node at the + /// root of the tree. inline node_const_iterator node_begin() const; + /// Returns a node_iterator corresponding to the node at the + /// root of the tree. inline node_iterator node_begin(); + /// Returns a const node_iterator corresponding to a node just + /// after a leaf of the tree. inline node_const_iterator node_end() const; + /// Returns a node_iterator corresponding to a node just + /// after a leaf of the tree. inline node_iterator node_end(); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp index d64bdf75d9c..8fa80b73b78 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp @@ -47,12 +47,8 @@ namespace __gnu_pbds { namespace detail { -#define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \ - bin_search_tree_const_node_it_< \ - Node, \ - Const_Iterator, \ - Iterator, \ - _Alloc> +#define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \ + bin_search_tree_const_node_it_<Node, Const_Iterator, Iterator, _Alloc> /// Const node iterator. template<typename Node, @@ -68,99 +64,76 @@ namespace __gnu_pbds node_pointer; public: - // Category. + /// Category. typedef trivial_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef trivial_iterator_difference_type difference_type; - // __Iterator's value type. + /// Iterator's value type. typedef Const_Iterator value_type; - // __Iterator's reference type. + /// Iterator's reference type. typedef Const_Iterator reference; - // __Iterator's __const reference type. + /// Iterator's __const reference type. typedef Const_Iterator const_reference; - // Metadata type. + /// Metadata type. typedef typename Node::metadata_type metadata_type; - // Const metadata reference type. + /// Const metadata reference type. typedef - typename _Alloc::template rebind< - metadata_type>::other::const_reference + typename _Alloc::template rebind<metadata_type>::other::const_reference metadata_const_reference; - // Default constructor. - /* - inline - bin_search_tree_const_node_it_() - */ - inline - bin_search_tree_const_node_it_(const node_pointer p_nd = 0) + bin_search_tree_const_node_it_(const node_pointer p_nd = 0) : m_p_nd(const_cast<node_pointer>(p_nd)) { } - // Access. - inline const_reference + /// Access. + const_reference operator*() const - { - return (Const_Iterator(m_p_nd)); - } + { return Const_Iterator(m_p_nd); } - // Metadata access. - inline metadata_const_reference + /// Metadata access. + metadata_const_reference get_metadata() const - { - return (m_p_nd->get_metadata()); - } + { return m_p_nd->get_metadata(); } - // Returns the __const node iterator associated with the left node. - inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC + /// Returns the __const node iterator associated with the left node. + PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC get_l_child() const - { - return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left)); - } + { return PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left); } - // Returns the __const node iterator associated with the right node. - inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC + /// Returns the __const node iterator associated with the right node. + PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC get_r_child() const - { - return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right)); - } + { return PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right); } - // Compares to a different iterator object. - inline bool + /// Compares to a different iterator object. + bool operator==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const - { - return (m_p_nd == other.m_p_nd); - } + { return m_p_nd == other.m_p_nd; } - // Compares (negatively) to a different iterator object. - inline bool + /// Compares (negatively) to a different iterator object. + bool operator!=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const - { - return (m_p_nd != other.m_p_nd); - } + { return m_p_nd != other.m_p_nd; } node_pointer m_p_nd; }; -#define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \ - bin_search_tree_node_it_< \ - Node, \ - Const_Iterator, \ - Iterator, \ - _Alloc> +#define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \ + bin_search_tree_node_it_<Node, Const_Iterator, Iterator, _Alloc> /// Node iterator. template<typename Node, class Const_Iterator, class Iterator, typename _Alloc> - class bin_search_tree_node_it_ + class bin_search_tree_node_it_ : public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC { private: @@ -170,47 +143,39 @@ namespace __gnu_pbds node_pointer; public: - // __Iterator's value type. + /// Iterator's value type. typedef Iterator value_type; - // __Iterator's reference type. + /// Iterator's reference type. typedef Iterator reference; - // __Iterator's __const reference type. + /// Iterator's __const reference type. typedef Iterator const_reference; - // Default constructor. - /* - inline - bin_search_tree_node_it_(); - */ - inline - bin_search_tree_node_it_(const node_pointer p_nd = 0) + bin_search_tree_node_it_(const node_pointer p_nd = 0) : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(const_cast<node_pointer>(p_nd)) { } - // Access. - inline Iterator + /// Access. + Iterator operator*() const - { - return (Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd)); - } + { return Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd); } - // Returns the node iterator associated with the left node. - inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC + /// Returns the node iterator associated with the left node. + PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC get_l_child() const { - return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( - PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left)); + return PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( + PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left); } - // Returns the node iterator associated with the right node. - inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC + /// Returns the node iterator associated with the right node. + PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC get_r_child() const { - return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( - PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right)); + return PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( + PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right); } }; @@ -222,4 +187,3 @@ namespace __gnu_pbds } // namespace __gnu_pbds #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP - diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp index 3066c381f42..416815e762e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp @@ -48,7 +48,8 @@ namespace __gnu_pbds { namespace detail { - /// Binary search tree traits, primary template. + /// Binary search tree traits, primary template + /// @ingroup traits template<typename Key, typename Mapped, class Cmp_Fn, @@ -56,7 +57,7 @@ namespace __gnu_pbds class Node_Itr, class Cmp_Fn, typename _Alloc> - class Node_Update, + class Node_Update, class Node, typename _Alloc> struct bin_search_tree_traits @@ -119,6 +120,8 @@ namespace __gnu_pbds _Alloc> reverse_iterator; + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. typedef bin_search_tree_const_node_it_< Node, @@ -153,13 +156,14 @@ namespace __gnu_pbds }; /// Specialization. + /// @ingroup traits template<typename Key, class Cmp_Fn, template<typename Node_CItr, class Node_Itr, class Cmp_Fn, typename _Alloc> - class Node_Update, + class Node_Update, class Node, typename _Alloc> struct bin_search_tree_traits< @@ -206,6 +210,8 @@ namespace __gnu_pbds typedef const_reverse_iterator reverse_iterator; + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. typedef bin_search_tree_const_node_it_< Node, diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp index ee408e8ea02..8d91c4ca0b6 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp @@ -74,7 +74,9 @@ namespace __gnu_pbds __gnu_pbds::detail::resize_policy<typename _Alloc::size_type> /** - * @brief Binary heaps composed of resize and compare policies. + * Binary heaps composed of resize and compare policies. + * + * @ingroup heap-detail * * Based on CLRS. */ diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp index a6ac261b9ba..aaadd67e6f2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/const_iterator.hpp @@ -64,48 +64,48 @@ namespace __gnu_pbds typedef typename base_type::entry_pointer entry_pointer; public: - // Category. + /// Category. typedef std::forward_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef typename _Alloc::difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef typename base_type::value_type value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef typename base_type::pointer pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef typename base_type::const_pointer const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef typename base_type::reference reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef typename base_type::const_reference const_reference; inline binary_heap_const_iterator_(entry_pointer p_e) : base_type(p_e) { } - // Default constructor. + /// Default constructor. inline binary_heap_const_iterator_() { } - // Copy constructor. + /// Copy constructor. inline binary_heap_const_iterator_(const binary_heap_const_iterator_& other) : base_type(other) { } - // Compares content to a different iterator object. + /// Compares content to a different iterator object. inline bool operator==(const binary_heap_const_iterator_& other) const { return base_type::m_p_e == other.m_p_e; } - // Compares content (negatively) to a different iterator object. + /// Compares content (negatively) to a different iterator object. inline bool operator!=(const binary_heap_const_iterator_& other) const { return base_type::m_p_e != other.m_p_e; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp index 87362607387..f88dd4ae4ed 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp @@ -49,7 +49,7 @@ namespace __gnu_pbds { namespace detail { - // Const point-type iterator. + /// Const point-type iterator. template<typename Value_Type, typename Entry, bool Simple, typename _Alloc> class binary_heap_point_const_iterator_ @@ -58,30 +58,30 @@ namespace __gnu_pbds typedef typename _Alloc::template rebind<Entry>::other::pointer entry_pointer; public: - // Category. + /// Category. typedef trivial_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef trivial_iterator_difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef Value_Type value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef typename _Alloc::template rebind<value_type>::other::pointer pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef typename _Alloc::template rebind<value_type>::other::const_pointer const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef typename _Alloc::template rebind<value_type>::other::reference reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef typename _Alloc::template rebind<value_type>::other::const_reference const_reference; @@ -90,17 +90,17 @@ namespace __gnu_pbds binary_heap_point_const_iterator_(entry_pointer p_e) : m_p_e(p_e) { } - // Default constructor. + /// Default constructor. inline binary_heap_point_const_iterator_() : m_p_e(0) { } - // Copy constructor. + /// Copy constructor. inline binary_heap_point_const_iterator_(const binary_heap_point_const_iterator_& other) : m_p_e(other.m_p_e) { } - // Access. + /// Access. inline const_pointer operator->() const { @@ -108,7 +108,7 @@ namespace __gnu_pbds return to_ptr(integral_constant<int, Simple>()); } - // Access. + /// Access. inline const_reference operator*() const { @@ -116,12 +116,12 @@ namespace __gnu_pbds return *to_ptr(integral_constant<int, Simple>()); } - // Compares content to a different iterator object. + /// Compares content to a different iterator object. inline bool operator==(const binary_heap_point_const_iterator_& other) const { return m_p_e == other.m_p_e; } - // Compares content (negatively) to a different iterator object. + /// Compares content (negatively) to a different iterator object. inline bool operator!=(const binary_heap_point_const_iterator_& other) const { return m_p_e != other.m_p_e; } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp index e3d74bffd69..ab9b0ecc0b2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp @@ -58,10 +58,10 @@ namespace __gnu_pbds factor = 2 }; - // Next shrink size. + /// Next shrink size. _Tp m_shrink_size; - // Next grow size. + /// Next grow size. _Tp m_grow_size; public: diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp index d8704f65c41..5f22f95823c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp @@ -59,7 +59,11 @@ namespace __gnu_pbds #define PB_DS_CLASS_C_DEC \ binomial_heap<Value_Type, Cmp_Fn, _Alloc> - /// Binomial heap. + /** + * Binomial heap. + * + * @ingroup heap-detail + */ template<typename Value_Type, typename Cmp_Fn, typename _Alloc> class binomial_heap : public binomial_heap_base<Value_Type, Cmp_Fn, _Alloc> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp b/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp index efe39f2fe4a..3c90b49d1f7 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp @@ -45,11 +45,6 @@ namespace __gnu_pbds { - /// A null node updator, indicating that no node updates are required. - template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4> - struct null_node_update : public null_type - { }; - namespace detail { /// Primary template, base class for branch structure policies. diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp index f1c2540e7d5..ee487ff76de 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp @@ -91,7 +91,44 @@ namespace __gnu_pbds typename _Alloc::template rebind<Key>::other::const_reference> #endif - /// Collision chaining hash. + + /** + * A collision-chaining hash-based container. + * + * + * @ingroup hash-detail + * + * @tparam Key Key type. + * + * @tparam Mapped Map type. + * + * @tparam Hash_Fn Hashing functor. + * Default is __gnu_cxx::hash. + * + * @tparam Eq_Fn Equal functor. + * Default std::equal_to<Key> + * + * @tparam _Alloc Allocator type. + * + * @tparam Store_Hash If key type stores extra metadata. + * Defaults to false. + * + * @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.) + * Default direct_mask_range_hashing. + * + * @tparam Resize_Policy Resizes hash. + * Defaults to hash_standard_resize_policy, + * using hash_exponential_size_policy and + * hash_load_check_resize_trigger. + * + * + * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_hash_fn, + * detail::types_traits. (Optional: detail::debug_map_base.) + */ template<typename Key, typename Mapped, typename Hash_Fn, @@ -160,6 +197,7 @@ namespace __gnu_pbds typedef Comb_Hash_Fn comb_hash_fn; typedef Resize_Policy resize_policy; + /// Value stores hash, true or false. enum { store_hash = Store_Hash @@ -233,30 +271,39 @@ namespace __gnu_pbds inline size_type max_size() const; + /// True if size() == 0. inline bool empty() const; + /// Return current hash_fn. Hash_Fn& get_hash_fn(); + /// Return current const hash_fn. const Hash_Fn& get_hash_fn() const; + /// Return current eq_fn. Eq_Fn& get_eq_fn(); + /// Return current const eq_fn. const Eq_Fn& get_eq_fn() const; + /// Return current comb_hash_fn. Comb_Hash_Fn& get_comb_hash_fn(); + /// Return current const comb_hash_fn. const Comb_Hash_Fn& get_comb_hash_fn() const; + /// Return current resize_policy. Resize_Policy& get_resize_policy(); + /// Return current const resize_policy. const Resize_Policy& get_resize_policy() const; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp deleted file mode 100644 index a960b7d2317..00000000000 --- a/libstdc++-v3/include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp +++ /dev/null @@ -1,103 +0,0 @@ -// -*- 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 -// <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 detail/constructors_destructor_fn_imps.hpp - * Contains constructors_destructor_fn_imps applicable to different containers. - */ - -inline -PB_DS_CLASS_NAME() -{ } - -inline -PB_DS_CLASS_NAME(const PB_DS_CLASS_NAME& other) -: base_type((const base_type&)other) -{ } - -template<typename T0> -inline -PB_DS_CLASS_NAME(T0 t0) : base_type(t0) -{ } - -template<typename T0, typename T1> -inline -PB_DS_CLASS_NAME(T0 t0, T1 t1) : base_type(t0, t1) -{ } - -template<typename T0, typename T1, typename T2> -inline -PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) -{ } - -template<typename T0, typename T1, typename T2, typename T3> -inline -PB_DS_CLASS_NAME(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> -inline -PB_DS_CLASS_NAME(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> -inline -PB_DS_CLASS_NAME(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> -inline -PB_DS_CLASS_NAME(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> -inline -PB_DS_CLASS_NAME(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> -inline -PB_DS_CLASS_NAME(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) -{ } diff --git a/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp index 6255d55eb0e..52844f6f9d9 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp @@ -49,6 +49,7 @@ namespace __gnu_pbds { namespace detail { + /// Primary template. template<typename Key, typename Eq_Fn, typename _Alloc, bool Store_Hash> struct hash_eq_fn; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp index 4ce94aefecd..e1161fb5d7c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp @@ -90,7 +90,47 @@ namespace __gnu_pbds #endif - /// General probing hash. + /** + * A general-probing hash-based container. + * + * + * @ingroup hash-detail + * + * @tparam Key Key type. + * + * @tparam Mapped Map type. + * + * @tparam Hash_Fn Hashing functor. + * Default is __gnu_cxx::hash. + * + * @tparam Eq_Fn Equal functor. + * Default std::equal_to<Key> + * + * @tparam _Alloc Allocator type. + * + * @tparam Store_Hash If key type stores extra metadata. + * Defaults to false. + * + * @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. + * Default direct_mask_range_hashing. + * + * @tparam Probe_Fn Probe functor. + * Defaults to linear_probe_fn, + * also quadratic_probe_fn. + * + * @tparam Resize_Policy Resizes hash. + * Defaults to hash_standard_resize_policy, + * using hash_exponential_size_policy and + * hash_load_check_resize_trigger. + * + * + * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_probe_fn, + * detail::types_traits. (Optional: detail::debug_map_base.) + */ template<typename Key, typename Mapped, typename Hash_Fn, @@ -165,6 +205,7 @@ namespace __gnu_pbds typedef Comb_Probe_Fn comb_probe_fn; typedef Resize_Policy resize_policy; + /// Value stores hash, true or false. enum { store_hash = Store_Hash @@ -217,10 +258,10 @@ namespace __gnu_pbds PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&); PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, - const Probe_Fn&); + const Probe_Fn&); PB_DS_GP_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&, - const Probe_Fn&, const Resize_Policy&); + const Probe_Fn&, const Resize_Policy&); template<typename It> void @@ -238,36 +279,47 @@ namespace __gnu_pbds inline size_type max_size() const; + /// True if size() == 0. inline bool empty() const; + /// Return current hash_fn. Hash_Fn& get_hash_fn(); + /// Return current const hash_fn. const Hash_Fn& get_hash_fn() const; + /// Return current eq_fn. Eq_Fn& get_eq_fn(); + /// Return current const eq_fn. const Eq_Fn& get_eq_fn() const; + /// Return current probe_fn. Probe_Fn& get_probe_fn(); + /// Return current const probe_fn. const Probe_Fn& get_probe_fn() const; + /// Return current comb_probe_fn. Comb_Probe_Fn& get_comb_probe_fn(); + /// Return current const comb_probe_fn. const Comb_Probe_Fn& get_comb_probe_fn() const; + /// Return current resize_policy. Resize_Policy& get_resize_policy(); + /// Return current const resize_policy. const Resize_Policy& get_resize_policy() const; @@ -305,8 +357,8 @@ namespace __gnu_pbds erase(key_const_reference); template<typename Pred> - inline size_type - erase_if(Pred); + inline size_type + erase_if(Pred); void clear(); @@ -319,7 +371,7 @@ namespace __gnu_pbds inline iterator end(); - + inline const_iterator end() const; @@ -406,7 +458,7 @@ namespace __gnu_pbds insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) { _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat != - valid_entry_status); + valid_entry_status); if (do_resize_if_needed()) r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val), diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp index 936abbee17d..6fe8465c645 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp @@ -45,14 +45,12 @@ namespace __gnu_pbds { namespace detail { -#define PB_DS_CLASS_T_DEC template<typename Size_Type> -#define PB_DS_CLASS_C_DEC mask_based_range_hashing<Size_Type> - + /// Range hashing policy. template<typename Size_Type> class mask_based_range_hashing { protected: - typedef Size_Type size_type; + typedef Size_Type size_type; void swap(mask_based_range_hashing& other) @@ -71,18 +69,18 @@ namespace __gnu_pbds const static size_type s_highest_bit_1; }; - PB_DS_CLASS_T_DEC - const typename PB_DS_CLASS_C_DEC::size_type - PB_DS_CLASS_C_DEC::s_num_bits_in_size_type = - sizeof(typename PB_DS_CLASS_C_DEC::size_type) << 3; + template<typename Size_Type> + const typename mask_based_range_hashing<Size_Type>::size_type + mask_based_range_hashing<Size_Type>::s_num_bits_in_size_type = + sizeof(typename mask_based_range_hashing<Size_Type>::size_type) << 3; - PB_DS_CLASS_T_DEC - const typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC::s_highest_bit_1 = static_cast<typename PB_DS_CLASS_C_DEC::size_type>(1) << (s_num_bits_in_size_type - 1); + template<typename Size_Type> + const typename mask_based_range_hashing<Size_Type>::size_type mask_based_range_hashing<Size_Type>::s_highest_bit_1 = static_cast<typename mask_based_range_hashing<Size_Type>::size_type>(1) << (s_num_bits_in_size_type - 1); - PB_DS_CLASS_T_DEC + template<typename Size_Type> void - PB_DS_CLASS_C_DEC:: + mask_based_range_hashing<Size_Type>:: notify_resized(size_type size) { size_type i = 0; @@ -97,10 +95,6 @@ namespace __gnu_pbds while (i++ < s_num_bits_in_size_type) m_mask = (m_mask << 1) ^ 1; } - -#undef PB_DS_CLASS_T_DEC -#undef PB_DS_CLASS_C_DEC - } // namespace detail } // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp index 2610e04577e..2c14c8607bc 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp @@ -43,64 +43,30 @@ namespace __gnu_pbds { - namespace detail { - -#define PB_DS_CLASS_T_DEC \ - template<typename Size_Type> - -#define PB_DS_CLASS_C_DEC \ - mod_based_range_hashing< \ - Size_Type> - + /// Mod based range hashing. template<typename Size_Type> class mod_based_range_hashing { protected: - typedef Size_Type size_type; + typedef Size_Type size_type; - protected: void - swap(PB_DS_CLASS_C_DEC& other); + swap(mod_based_range_hashing& other) + { std::swap(m_size, other.m_size); } void - notify_resized(size_type size); + notify_resized(size_type s) + { m_size = s; } inline size_type - range_hash(size_type hash) const; + range_hash(size_type s) const + { return s % m_size; } private: size_type m_size; }; - - PB_DS_CLASS_T_DEC - void - PB_DS_CLASS_C_DEC:: - swap(PB_DS_CLASS_C_DEC& other) - { - std::swap(m_size, other.m_size); - } - - PB_DS_CLASS_T_DEC - void - PB_DS_CLASS_C_DEC:: - notify_resized(size_type size) - { - m_size = size; - } - - PB_DS_CLASS_T_DEC - inline typename PB_DS_CLASS_C_DEC::size_type - PB_DS_CLASS_C_DEC:: - range_hash(size_type hash) const - { - return (hash % m_size); - } - -#undef PB_DS_CLASS_T_DEC -#undef PB_DS_CLASS_C_DEC - } // namespace detail } // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp index 19855ac1e8b..8907f085858 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/probe_fn_base.hpp @@ -47,6 +47,7 @@ namespace __gnu_pbds { namespace detail { + /// Probe functor base. template<typename _Alloc> class probe_fn_base { diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp index 8567851f798..f71b843f017 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp @@ -49,6 +49,7 @@ namespace __gnu_pbds { namespace detail { + /// Primary template. template<typename Key, typename Hash_Fn, typename _Alloc, typename Comb_Hash_Fn, bool Store_Hash> class ranged_hash_fn; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp index b13de65555a..4c24f492651 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp @@ -49,6 +49,7 @@ namespace __gnu_pbds { namespace detail { + /// Primary template. template<typename Key, typename Hash_Fn, typename _Alloc, typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash> class ranged_probe_fn; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp index 3ca9001e025..921547188aa 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_probe_fn.hpp @@ -49,18 +49,18 @@ namespace __gnu_pbds public: typedef std::size_t size_type; - // Default constructor. + /// Default constructor. sample_probe_fn(); - // Copy constructor. + /// Copy constructor. sample_probe_fn(const sample_probe_fn&); - // Swaps content. + /// Swaps content. inline void swap(sample_probe_fn&); protected: - // Returns the i-th offset from the hash value of some key r_key. + /// Returns the i-th offset from the hash value of some key r_key. inline size_type operator()(key_const_reference r_key, size_type i) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp index 3092376832c..1fbcf8c0dae 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_range_hashing.hpp @@ -47,26 +47,26 @@ namespace __gnu_pbds class sample_range_hashing { public: - // Size type. + /// Size type. typedef std::size_t size_type; - // Default constructor. + /// Default constructor. sample_range_hashing(); - // Copy constructor. + /// Copy constructor. sample_range_hashing(const sample_range_hashing& other); - // Swaps content. + /// Swaps content. inline void swap(sample_range_hashing& other); protected: - // Notifies the policy object that the container's __size has - // changed to size. + /// Notifies the policy object that the container's size has + /// changed to argument's size. void notify_resized(size_type); - // Transforms the __hash value hash into a ranged-hash value. + /// Transforms the __hash value hash into a ranged-hash value. inline size_type operator()(size_type ) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp index cc9aaab9134..759d93cf119 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/sample_ranged_hash_fn.hpp @@ -49,24 +49,24 @@ namespace __gnu_pbds public: typedef std::size_t size_type; - // Default constructor. + /// Default constructor. sample_ranged_hash_fn(); - // Copy constructor. + /// Copy constructor. sample_ranged_hash_fn(const sample_ranged_hash_fn&); - // Swaps content. + /// Swaps content. inline void swap(sample_ranged_hash_fn&); protected: - // Notifies the policy object that the container's __size has - // changed to size. + /// Notifies the policy object that the container's __size has + /// changed to size. void notify_resized(size_type); - // Transforms key_const_reference into a position within the table. + /// Transforms key_const_reference into a position within the table. inline size_type operator()(key_const_reference) const; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp index e51abe17e06..7fc50576ae2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp @@ -65,25 +65,25 @@ namespace __gnu_pbds typedef typename base_type::node_pointer node_pointer; public: - // Category. + /// Category. typedef std::forward_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef typename _Alloc::difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef typename base_type::value_type value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef typename base_type::pointer pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef typename base_type::const_pointer const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef typename base_type::reference reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef typename base_type::const_reference const_reference; inline @@ -91,27 +91,27 @@ namespace __gnu_pbds : base_type(p_nd) { } - // Default constructor. + /// Default constructor. inline left_child_next_sibling_heap_const_iterator_() { } - // Copy constructor. + /// Copy constructor. inline left_child_next_sibling_heap_const_iterator_(const PB_DS_CLASS_C_DEC& other) : base_type(other) { } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator==(const PB_DS_CLASS_C_DEC& other) const { return (base_type::m_p_nd == other.m_p_nd); } - // Compares content (negatively) to a different iterator object. - inline bool + /// Compares content (negatively) to a different iterator object. + bool operator!=(const PB_DS_CLASS_C_DEC& other) const { return (base_type::m_p_nd != other.m_p_nd); } - inline PB_DS_CLASS_C_DEC& + PB_DS_CLASS_C_DEC& operator++() { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd != 0); @@ -119,7 +119,7 @@ namespace __gnu_pbds return (*this); } - inline PB_DS_CLASS_C_DEC + PB_DS_CLASS_C_DEC operator++(int) { PB_DS_CLASS_C_DEC ret_it(base_type::m_p_nd); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp index b6f3b51710b..9642f18e90c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp @@ -92,7 +92,7 @@ namespace __gnu_pbds protected: typedef typename _Alloc::template rebind< - left_child_next_sibling_heap_node_<Value_Type, Node_Metadata, + left_child_next_sibling_heap_node_<Value_Type, Node_Metadata, _Alloc> >::other node_allocator; @@ -135,8 +135,6 @@ namespace __gnu_pbds typedef Cmp_Fn cmp_fn; typedef _Alloc allocator_type; - public: - left_child_next_sibling_heap(); left_child_next_sibling_heap(const Cmp_Fn&); left_child_next_sibling_heap(const left_child_next_sibling_heap&); @@ -182,7 +180,6 @@ namespace __gnu_pbds #endif protected: - inline node_pointer get_new_node_for_insert(const_reference); @@ -260,16 +257,15 @@ namespace __gnu_pbds trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); static void - trace_node_metadata(node_const_pointer, - type_to_type<null_type>); + trace_node_metadata(node_const_pointer, type_to_type<null_type>); #endif - protected: - node_pointer m_p_root; - size_type m_size; - private: static node_allocator s_node_allocator; static no_throw_copies_t s_no_throw_copies_ind; + + protected: + node_pointer m_p_root; + size_type m_size; }; #include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp index 5b29254f6aa..5d3251f1e97 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp @@ -60,88 +60,83 @@ namespace __gnu_pbds template<typename Node, typename _Alloc> class left_child_next_sibling_heap_node_point_const_iterator_ { - protected: typedef typename _Alloc::template rebind<Node>::other::pointer node_pointer; public: - - // Category. + /// Category. typedef trivial_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef trivial_iterator_difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef typename Node::value_type value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef typename _Alloc::template rebind< value_type>::other::pointer pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef typename _Alloc::template rebind< value_type>::other::const_pointer const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef typename _Alloc::template rebind< value_type>::other::reference reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef typename _Alloc::template rebind< value_type>::other::const_reference const_reference; - public: - inline left_child_next_sibling_heap_node_point_const_iterator_(node_pointer p_nd) : m_p_nd(p_nd) { } - // Default constructor. + /// Default constructor. inline left_child_next_sibling_heap_node_point_const_iterator_() : m_p_nd(0) { } - // Copy constructor. + /// Copy constructor. inline left_child_next_sibling_heap_node_point_const_iterator_(const PB_DS_CLASS_C_DEC& other) : m_p_nd(other.m_p_nd) { } - // Access. - inline const_pointer + /// Access. + const_pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); return &m_p_nd->m_value; } - // Access. - inline const_reference + /// Access. + const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); return m_p_nd->m_value; } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator==(const PB_DS_CLASS_C_DEC& other) const { return m_p_nd == other.m_p_nd; } - // Compares content (negatively) to a different iterator object. - inline bool + /// Compares content (negatively) to a different iterator object. + bool operator!=(const PB_DS_CLASS_C_DEC& other) const { return m_p_nd != other.m_p_nd; } - public: node_pointer m_p_nd; }; @@ -151,4 +146,4 @@ namespace __gnu_pbds } // namespace detail } // namespace __gnu_pbds -#endif +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/sample_update_policy.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/sample_update_policy.hpp index 13ee6e1c7b0..a446c3f11f2 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/sample_update_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_policy/sample_update_policy.hpp @@ -46,29 +46,29 @@ namespace __gnu_pbds /// A sample list-update policy. struct sample_update_policy { - // Default constructor. + /// Default constructor. sample_update_policy(); - // Copy constructor. + /// Copy constructor. sample_update_policy(const sample_update_policy&); - // Swaps content. + /// Swaps content. inline void swap(sample_update_policy& other); protected: - // Metadata on which this functor operates. + /// Metadata on which this functor operates. typedef some_metadata_type metadata_type; - // Creates a metadata object. + /// Creates a metadata object. metadata_type operator()() const; - // Decides whether a metadata object should be moved to the front of - // the list. A list-update based containers object will call this - // method to decide whether to move a node to the front of the - // list. The method shoule return true if the node should be moved - // to the front of the list. + /// Decides whether a metadata object should be moved to the front + /// of the list. A list-update based containers object will call + /// this method to decide whether to move a node to the front of + /// the list. The method shoule return true if the node should be + /// moved to the front of the list. bool operator()(metadata_reference) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp index 79c95043853..19a424d822f 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp @@ -137,6 +137,7 @@ namespace __gnu_pbds return *m_p_metadata; } + /// Returns the node iterator associated with the left node. inline this_type get_l_child() const { @@ -152,11 +153,12 @@ namespace __gnu_pbds mid_pointer(p_begin_metadata, m_p_metadata))); } + /// Returns the node iterator associated with the right node. inline this_type get_r_child() const { if (m_p_value == m_p_end_value) - return (this_type(m_p_end_value, m_p_end_value, m_p_end_value)); + return (this_type(m_p_end_value, m_p_end_value, m_p_end_value)); const_metadata_pointer p_end_metadata = m_p_metadata + (m_p_end_value - m_p_value); @@ -201,7 +203,6 @@ namespace __gnu_pbds template<typename Value_Type, typename Metadata_Type, typename _Alloc> class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC { - private: typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type; @@ -216,7 +217,6 @@ namespace __gnu_pbds const_metadata_pointer; public: - typedef trivial_iterator_tag iterator_category; typedef trivial_iterator_difference_type difference_type; @@ -238,17 +238,16 @@ namespace __gnu_pbds Value_Type>::type>::other::pointer const_reference; - public: inline ov_tree_node_it_(const_pointer p_nd = 0, const_pointer p_begin_nd = 0, const_pointer p_end_nd = 0, const_metadata_pointer p_metadata = 0) : base_type(p_nd, p_begin_nd, p_end_nd, p_metadata) { } - // Access. + /// Access. inline reference operator*() const { return reference(base_type::m_p_value); } - // Returns the node reference associated with the left node. + /// Returns the node reference associated with the left node. inline ov_tree_node_it_ get_l_child() const { @@ -264,13 +263,12 @@ namespace __gnu_pbds base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata))); } - // Returns the node reference associated with the right node. + /// Returns the node reference associated with the right node. inline ov_tree_node_it_ get_r_child() const { if (base_type::m_p_value == base_type::m_p_end_value) - return this_type(base_type::m_p_end_value, - base_type::m_p_end_value, + return this_type(base_type::m_p_end_value, base_type::m_p_end_value, base_type::m_p_end_value); const_metadata_pointer p_end_metadata = diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp index 20a435047dd..c24ae557a70 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp @@ -35,7 +35,7 @@ /** * @file ov_tree_map_/ov_tree_map_.hpp - * Contains an implementation class for ov_tree_. + * Contains an implementation class for ov_tree. */ #include <map> @@ -97,7 +97,10 @@ namespace __gnu_pbds # error Missing definition #endif - /// Ordered-vector tree associative-container. + /** + * @brief Ordered-vector tree associative-container. + * @ingroup branch-detail + */ template<typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename _Alloc> class PB_DS_OV_TREE_NAME : @@ -377,15 +380,23 @@ namespace __gnu_pbds end() const { return m_end_it; } + /// Returns a const node_iterator corresponding to the node at the + /// root of the tree. inline node_const_iterator node_begin() const; - inline node_const_iterator - node_end() const; - + /// Returns a node_iterator corresponding to the node at the + /// root of the tree. inline node_iterator node_begin(); + /// Returns a const node_iterator corresponding to a node just + /// after a leaf of the tree. + inline node_const_iterator + node_end() const; + + /// Returns a node_iterator corresponding to a node just + /// after a leaf of the tree. inline node_iterator node_end(); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/traits.hpp index 359e599627b..ac933136bdf 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/traits.hpp @@ -48,6 +48,7 @@ namespace __gnu_pbds namespace detail { /// Tree traits. + /// @ingroup traits template<typename Key, typename Mapped, class Cmp_Fn, @@ -84,6 +85,8 @@ namespace __gnu_pbds _Alloc>::type metadata_type; + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. typedef ov_tree_node_const_it_< value_type, @@ -115,7 +118,9 @@ namespace __gnu_pbds null_node_update_pointer; }; + /// Specialization. + /// @ingroup traits template<typename Key, class Cmp_Fn, template<typename Node_CItr, @@ -151,6 +156,8 @@ namespace __gnu_pbds _Alloc>::type metadata_type; + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. typedef ov_tree_node_const_it_< value_type, diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp index 85e098ad4c8..7c9e6e3ee95 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp @@ -68,7 +68,11 @@ namespace __gnu_pbds left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc> #endif - /// Pairing heap. + /** + * Pairing heap. + * + * @ingroup heap-detail + */ template<typename Value_Type, typename Cmp_Fn, typename _Alloc> class pairing_heap : public PB_DS_P_HEAP_BASE { diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp index 46bb016e25e..66272b3119e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp @@ -90,11 +90,12 @@ namespace __gnu_pbds /** * @brief PATRICIA trie. + * @ingroup branch-detail * - * This implementation loosely borrows ideas from: - * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 - * 2) Ptset: Sets of integers implemented as Patricia trees, - * Jean-Christophe Filliatr, 2000 + * This implementation loosely borrows ideas from: + * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 + * 2) Ptset: Sets of integers implemented as Patricia trees, + * Jean-Christophe Filliatr, 2000 */ template<typename Key, typename Mapped, typename Node_And_It_Traits, typename _Alloc> @@ -388,15 +389,23 @@ namespace __gnu_pbds inline const_reverse_iterator rend() const; + /// Returns a const node_iterator corresponding to the node at the + /// root of the tree. inline node_const_iterator node_begin() const; + /// Returns a node_iterator corresponding to the node at the + /// root of the tree. inline node_iterator node_begin(); + /// Returns a const node_iterator corresponding to a node just + /// after a leaf of the tree. inline node_const_iterator node_end() const; + /// Returns a node_iterator corresponding to a node just + /// after a leaf of the tree. inline node_iterator node_end(); diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp index b3718b51ed2..f5326e944fb 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp @@ -858,10 +858,10 @@ namespace __gnu_pbds typedef value_type reference; typedef value_type const_reference; - // Metadata type. + /// Metadata type. typedef typename Node::metadata_type metadata_type; - // Const metadata reference type. + /// Const metadata reference type. typedef typename _Alloc::template rebind<metadata_type> __rebind_m; typedef typename __rebind_m::other __rebind_ma; typedef typename __rebind_ma::const_reference metadata_const_reference; @@ -871,13 +871,13 @@ namespace __gnu_pbds : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) { } - // Subtree valid prefix. + /// Subtree valid prefix. std::pair<a_const_iterator, a_const_iterator> valid_prefix() const { return std::make_pair(pref_begin(), pref_end()); } - // Const access; returns the __const iterator* associated with - // the current leaf. + /// Const access; returns the __const iterator* associated with + /// the current leaf. const_reference operator*() const { @@ -885,12 +885,12 @@ namespace __gnu_pbds return _CIterator(m_p_nd); } - // Metadata access. + /// Metadata access. metadata_const_reference get_metadata() const { return m_p_nd->get_metadata(); } - // Returns the number of children in the corresponding node. + /// Returns the number of children in the corresponding node. size_type num_children() const { @@ -901,8 +901,8 @@ namespace __gnu_pbds return std::distance(inp->begin(), inp->end()); } - // Returns a __const node __iterator to the corresponding node's - // i-th child. + /// Returns a __const node __iterator to the corresponding node's + /// i-th child. _Node_citer get_child(size_type i) const { @@ -913,12 +913,12 @@ namespace __gnu_pbds return _Node_citer(*it, m_p_traits); } - // Compares content to a different iterator object. + /// Compares content to a different iterator object. bool operator==(const _Node_citer& other) const { return m_p_nd == other.m_p_nd; } - // Compares content (negatively) to a different iterator object. + /// Compares content (negatively) to a different iterator object. bool operator!=(const _Node_citer& other) const { return m_p_nd != other.m_p_nd; } @@ -959,7 +959,7 @@ namespace __gnu_pbds : base_type(p_nd, p_traits) { } - // Access; returns the iterator* associated with the current leaf. + /// Access; returns the iterator* associated with the current leaf. reference operator*() const { @@ -967,7 +967,7 @@ namespace __gnu_pbds return iterator(base_type::m_p_nd); } - // Returns a node __iterator to the corresponding node's i-th child. + /// Returns a node __iterator to the corresponding node's i-th child. _Node_iter get_child(size_type i) const { diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp index 2e64c52480f..6113393da0e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp @@ -49,6 +49,7 @@ namespace __gnu_pbds namespace detail { /// Specialization. + /// @ingroup traits template<typename Key, typename Mapped, typename _ATraits, @@ -69,6 +70,7 @@ namespace __gnu_pbds typedef base_type::_Metadata<metadata_type, _Alloc> metadata; typedef _ATraits access_traits; + /// Type for synthesized traits. typedef __gnu_pbds::detail::synth_access_traits<type_traits, false, access_traits> synth_access_traits; typedef base_type::_Node_base<synth_access_traits, metadata> node; @@ -81,17 +83,21 @@ namespace __gnu_pbds typedef base_type::_Iter<node, leaf, head, inode, false> reverse_iterator; typedef base_type::_CIter<node, leaf, head, inode, false> const_reverse_iterator; - + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. typedef base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_const_iterator; typedef base_type::_Node_iter<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_iterator; + /// Type for node update. typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update; typedef null_node_update<node_const_iterator, node_iterator, _ATraits, _Alloc>* null_node_update_pointer; }; + /// Specialization. + /// @ingroup traits template<typename Key, typename _ATraits, template<typename Node_CItr, @@ -110,6 +116,8 @@ namespace __gnu_pbds typedef typename trie_node_metadata_dispatch<Key, null_type, _ATraits, Node_Update, _Alloc>::type metadata_type; typedef base_type::_Metadata<metadata_type, _Alloc> metadata; typedef _ATraits access_traits; + + /// Type for synthesized traits. typedef __gnu_pbds::detail::synth_access_traits<type_traits, true, access_traits> synth_access_traits; typedef base_type::_Node_base<synth_access_traits, metadata> node; @@ -122,11 +130,13 @@ namespace __gnu_pbds typedef base_type::_CIter<node, leaf, head, inode, false> const_reverse_iterator; typedef const_reverse_iterator reverse_iterator; - + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. typedef base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_const_iterator; typedef node_const_iterator node_iterator; + /// Type for node update. typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update; typedef null_node_update<node_const_iterator, node_const_iterator, _ATraits, _Alloc>* null_node_update_pointer; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp b/libstdc++-v3/include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp index 739d2b18bf6..fadb7c1a1dc 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/priority_queue_base_dispatch.hpp @@ -107,7 +107,7 @@ namespace __gnu_pbds /// Dispatched type. typedef thin_heap<_VTp, Cmp_Fn, _Alloc> type; }; - // @} group pbds + //@} group pbds } // namespace detail } // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp index a0e374b350c..ff120331dd1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp @@ -69,8 +69,9 @@ namespace __gnu_pbds PB_DS_RB_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> - /* + /** * @brief Red-Black tree. + * @ingroup branch-detail * * This implementation uses an idea from the SGI STL (using a * @a header node which is needed for efficient iteration). diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp index e6f2d8974ff..33ec735c5c1 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/traits.hpp @@ -48,6 +48,7 @@ namespace __gnu_pbds namespace detail { /// Specialization. + /// @ingroup traits template<typename Key, typename Mapped, typename Cmp_Fn, @@ -57,7 +58,7 @@ namespace __gnu_pbds typename _Alloc_> class Node_Update, typename _Alloc> - struct tree_traits<Key, Mapped, Cmp_Fn, Node_Update, rb_tree_tag, _Alloc> + struct tree_traits<Key, Mapped, Cmp_Fn, Node_Update, rb_tree_tag,_Alloc> : public bin_search_tree_traits< Key, Mapped, @@ -72,6 +73,7 @@ namespace __gnu_pbds { }; /// Specialization. + /// @ingroup traits template<typename Key, typename Cmp_Fn, template<typename Node_CItr, @@ -80,7 +82,7 @@ namespace __gnu_pbds typename _Alloc_> class Node_Update, typename _Alloc> - struct tree_traits<Key, null_type, Cmp_Fn, Node_Update, rb_tree_tag, _Alloc> + struct tree_traits<Key, null_type, Cmp_Fn, Node_Update, rb_tree_tag,_Alloc> : public bin_search_tree_traits< Key, null_type, diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp index e4d67049108..a8562470650 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp @@ -57,7 +57,11 @@ namespace __gnu_pbds #define PB_DS_RC_C_DEC \ rc<typename binomial_heap_base<Value_Type, Cmp_Fn, _Alloc>::node, _Alloc> - /// Base class for redundant-counter binomial heap. + /** + * Redundant-counter binomial heap. + * + * @ingroup heap-detail + */ template<typename Value_Type, typename Cmp_Fn, typename _Alloc> class rc_binomial_heap : public binomial_heap_base<Value_Type, Cmp_Fn, _Alloc> diff --git a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp index c29b3d5bed5..a4344e7c59f 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp @@ -45,11 +45,11 @@ namespace __gnu_pbds { namespace detail { - // Primary template. + /// Primary template. template<typename Size_Type, bool Hold_Size> class hash_load_check_resize_trigger_size_base; - // Specializations. + /// Specializations. template<typename Size_Type> class hash_load_check_resize_trigger_size_base<Size_Type, true> { diff --git a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp index 97533a34e45..9bbdf159e9c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp @@ -47,77 +47,77 @@ namespace __gnu_pbds class sample_resize_policy { public: - // Size type. + /// Size type. typedef std::size_t size_type; - // Default constructor. + /// Default constructor. sample_resize_policy(); - // Copy constructor. + /// Copy constructor. sample_range_hashing(const sample_resize_policy& other); - // Swaps content. + /// Swaps content. inline void swap(sample_resize_policy& other); protected: - // Notifies a search started. + /// Notifies a search started. inline void notify_insert_search_start(); - // Notifies a search encountered a collision. + /// Notifies a search encountered a collision. inline void notify_insert_search_collision(); - // Notifies a search ended. + /// Notifies a search ended. inline void notify_insert_search_end(); - // Notifies a search started. + /// Notifies a search started. inline void notify_find_search_start(); - // Notifies a search encountered a collision. + /// Notifies a search encountered a collision. inline void notify_find_search_collision(); - // Notifies a search ended. + /// Notifies a search ended. inline void notify_find_search_end(); - // Notifies a search started. + /// Notifies a search started. inline void notify_erase_search_start(); - // Notifies a search encountered a collision. + /// Notifies a search encountered a collision. inline void notify_erase_search_collision(); - // Notifies a search ended. + /// Notifies a search ended. inline void notify_erase_search_end(); - // Notifies an element was inserted. + /// Notifies an element was inserted. inline void notify_inserted(size_type num_e); - // Notifies an element was erased. + /// Notifies an element was erased. inline void notify_erased(size_type num_e); - // Notifies the table was cleared. + /// Notifies the table was cleared. void notify_cleared(); - // Notifies the table was resized to new_size. + /// Notifies the table was resized to new_size. void notify_resized(size_type new_size); - // Queries whether a resize is needed. + /// Queries whether a resize is needed. inline bool is_resize_needed() const; - // Queries what the new size should be. + /// Queries what the new size should be. size_type get_new_size(size_type size, size_type num_used_e) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp index ebc28b7cbc7..1640a120c79 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp @@ -48,88 +48,88 @@ namespace __gnu_pbds class sample_resize_trigger { public: - // Size type. + /// Size type. typedef std::size_t size_type; - // Default constructor. + /// Default constructor. sample_resize_trigger(); - // Copy constructor. + /// Copy constructor. sample_range_hashing(const sample_resize_trigger&); - // Swaps content. + /// Swaps content. inline void swap(sample_resize_trigger&); protected: - // Notifies a search started. + /// Notifies a search started. inline void notify_insert_search_start(); - // Notifies a search encountered a collision. + /// Notifies a search encountered a collision. inline void notify_insert_search_collision(); - // Notifies a search ended. + /// Notifies a search ended. inline void notify_insert_search_end(); - // Notifies a search started. + /// Notifies a search started. inline void notify_find_search_start(); - // Notifies a search encountered a collision. + /// Notifies a search encountered a collision. inline void notify_find_search_collision(); - // Notifies a search ended. + /// Notifies a search ended. inline void notify_find_search_end(); - // Notifies a search started. + /// Notifies a search started. inline void notify_erase_search_start(); - // Notifies a search encountered a collision. + /// Notifies a search encountered a collision. inline void notify_erase_search_collision(); - // Notifies a search ended. + /// Notifies a search ended. inline void notify_erase_search_end(); - // Notifies an element was inserted. the total number of entries in - // the table is num_entries. + /// Notifies an element was inserted. the total number of entries in + /// the table is num_entries. inline void notify_inserted(size_type num_entries); - // Notifies an element was erased. + /// Notifies an element was erased. inline void notify_erased(size_type num_entries); - // Notifies the table was cleared. + /// Notifies the table was cleared. void notify_cleared(); - // Notifies the table was resized as a result of this object's - // signifying that a resize is needed. + /// Notifies the table was resized as a result of this object's + /// signifying that a resize is needed. void notify_resized(size_type new_size); - // Notifies the table was resized externally. + /// Notifies the table was resized externally. void notify_externally_resized(size_type new_size); - // Queries whether a resize is needed. + /// Queries whether a resize is needed. inline bool is_resize_needed() const; - // Queries whether a grow is needed. + /// Queries whether a grow is needed. inline bool is_grow_needed(size_type size, size_type num_entries) const; private: - // Resizes to new_size. + /// Resizes to new_size. virtual void do_resize(size_type); }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp index b6c49aea69d..0779925491f 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp @@ -47,25 +47,25 @@ namespace __gnu_pbds class sample_size_policy { public: - // Size type. + /// Size type. typedef std::size_t size_type; - // Default constructor. + /// Default constructor. sample_size_policy(); - // Copy constructor. + /// Copy constructor. sample_range_hashing(const sample_size_policy&); - // Swaps content. + /// Swaps content. inline void swap(sample_size_policy& other); protected: - // Given a __size size, returns a __size that is larger. + /// Given a __size size, returns a __size that is larger. inline size_type get_nearest_larger_size(size_type size) const; - // Given a __size size, returns a __size that is smaller. + /// Given a __size size, returns a __size that is smaller. inline size_type get_nearest_smaller_size(size_type size) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp index 4d67dba4d85..a83ed555722 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp @@ -98,7 +98,10 @@ namespace __gnu_pbds PB_DS_S_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> - /// Splay Tree. + /** + * @brief Splay tree. + * @ingroup branch-detail + */ template<typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename _Alloc> class PB_DS_S_TREE_NAME : public PB_DS_S_TREE_BASE diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp index e5020ec92f0..d9ed261bfce 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/traits.hpp @@ -48,6 +48,7 @@ namespace __gnu_pbds namespace detail { /// Specialization. + /// @ingroup traits template<typename Key, typename Mapped, typename Cmp_Fn, @@ -68,6 +69,7 @@ namespace __gnu_pbds { }; /// Specialization. + /// @ingroup traits template<typename Key, class Cmp_Fn, template<typename Node_CItr, diff --git a/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp b/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp index cdb09d451d4..7596f8b56d5 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/standard_policies.hpp @@ -54,87 +54,103 @@ namespace __gnu_pbds { namespace detail { - /// default_hash_fn + /// Primary template, default_hash_fn. template<typename Key> struct default_hash_fn { - typedef std::tr1::hash<Key> type; + /// Dispatched type. + typedef std::tr1::hash<Key> type; }; - /// default_eq_fn + /// Primary template, default_eq_fn. template<typename Key> struct default_eq_fn { - typedef std::equal_to<Key> type; + /// Dispatched type. + typedef std::equal_to<Key> type; }; + /// Enumeration for default behavior of stored hash data. enum { default_store_hash = false }; - /// default_comb_hash_fn + /// Primary template, default_comb_hash_fn. struct default_comb_hash_fn { - typedef __gnu_pbds::direct_mask_range_hashing<> type; + /// Dispatched type. + typedef direct_mask_range_hashing<> type; }; - /// default_resize_policy + /// Primary template, default_resize_policy. template<typename Comb_Hash_Fn> struct default_resize_policy { private: - typedef typename Comb_Hash_Fn::size_type size_type; + typedef typename Comb_Hash_Fn::size_type size_type; - typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn; - typedef is_same<default_fn, Comb_Hash_Fn> same_type; - typedef __gnu_pbds::hash_exponential_size_policy<size_type> iftrue; - typedef __gnu_pbds::hash_prime_size_policy iffalse; + typedef direct_mask_range_hashing<size_type> default_fn; + typedef is_same<default_fn, Comb_Hash_Fn> same_type; + typedef hash_exponential_size_policy<size_type> iftrue; + typedef hash_prime_size_policy iffalse; typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type; - typedef typename cond_type::__type size_policy_type; + typedef typename cond_type::__type size_policy_type; - typedef __gnu_pbds::hash_load_check_resize_trigger<false, size_type> trigger; + typedef hash_load_check_resize_trigger<false, size_type> trigger; public: - typedef __gnu_pbds::hash_standard_resize_policy<size_policy_type, trigger, false, size_type> type; + /// Dispatched type. + typedef hash_standard_resize_policy<size_policy_type, trigger, + false, size_type> type; }; - /// default_update_policy + /// Default update policy. struct default_update_policy { - typedef __gnu_pbds::lu_move_to_front_policy<> type; + /// Dispatched type. + typedef lu_move_to_front_policy<> type; }; - /// default_probe_fn + /// Primary template, default_probe_fn. template<typename Comb_Probe_Fn> struct default_probe_fn { private: - typedef typename Comb_Probe_Fn::size_type size_type; - - typedef __gnu_pbds::direct_mask_range_hashing<size_type> default_fn; - typedef is_same<default_fn, Comb_Probe_Fn> same_type; - typedef __gnu_pbds::linear_probe_fn<size_type> iftrue; - typedef __gnu_pbds::quadratic_probe_fn<size_type> iffalse; + typedef typename Comb_Probe_Fn::size_type size_type; + typedef direct_mask_range_hashing<size_type> default_fn; + typedef is_same<default_fn, Comb_Probe_Fn> same_type; + typedef linear_probe_fn<size_type> iftrue; + typedef quadratic_probe_fn<size_type> iffalse; typedef __conditional_type<same_type::value, iftrue, iffalse> cond_type; public: - typedef typename cond_type::__type type; + /// Dispatched type. + typedef typename cond_type::__type type; }; - /// default_trie_access_traits + + /// Primary template, default_trie_access_traits. template<typename Key> - struct default_trie_access_traits; + struct default_trie_access_traits; + +#define __dtrie_alloc std::allocator<char> +#define __dtrie_string std::basic_string<Char, Char_Traits, __dtrie_alloc> + /// Partial specialization, default_trie_access_traits. template<typename Char, typename Char_Traits> - struct default_trie_access_traits<std::basic_string<Char, Char_Traits, std::allocator<char> > > - { - private: - typedef std::basic_string<Char, Char_Traits, std::allocator<char> > string_type; + struct default_trie_access_traits<__dtrie_string> + { + private: + typedef __dtrie_string string_type; - public: - typedef __gnu_pbds::trie_string_access_traits<string_type> type; - }; + public: + /// Dispatched type. + typedef trie_string_access_traits<string_type> type; + }; + +#undef __dtrie_alloc +#undef __dtrie_string } // namespace detail } // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp index fb30eb1b774..e040203ceeb 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp @@ -65,9 +65,11 @@ namespace __gnu_pbds <Value_Type, Cmp_Fn, typename _Alloc::size_type, _Alloc> #endif + /** * Thin heap. - * Base class for @ref priority_queue. + * + * @ingroup heap-detail * * See Tarjan and Kaplan. */ diff --git a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp b/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp index 1279b4dca49..fbaace2c29e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/node_metadata_selector.hpp @@ -48,16 +48,23 @@ namespace __gnu_pbds { namespace detail { + /** + * @addtogroup traits Traits + * @{ + */ + /// Tree metadata helper. template<typename Node_Update, bool _BTp> struct tree_metadata_helper; + /// Specialization, false. template<typename Node_Update> struct tree_metadata_helper<Node_Update, false> { typedef typename Node_Update::metadata_type type; }; + /// Specialization, true. template<typename Node_Update> struct tree_metadata_helper<Node_Update, true> { @@ -89,6 +96,7 @@ namespace __gnu_pbds public: typedef typename tree_metadata_helper<__node_u, null_update>::type type; }; + //@} } // namespace detail } // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/sample_tree_node_update.hpp b/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/sample_tree_node_update.hpp index cb455da42d6..e8033f62d42 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/sample_tree_node_update.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/sample_tree_node_update.hpp @@ -50,11 +50,11 @@ namespace __gnu_pbds { typedef std::size_t metadata_type; - // Default constructor. + /// Default constructor. sample_tree_node_update(); - // Updates the rank of a node through a node_iterator node_it; - // end_nd_it is the end node iterator. + /// Updates the rank of a node through a node_iterator node_it; + /// end_nd_it is the end node iterator. inline void operator()(node_iterator node_it, node_const_iterator end_nd_it) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp index b20181b8aef..da25ebbc467 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp @@ -48,16 +48,23 @@ namespace __gnu_pbds { namespace detail { + /** + * @addtogroup traits Traits + * @{ + */ + /// Trie metadata helper. template<typename Node_Update, bool _BTp> struct trie_metadata_helper; + /// Specialization, false. template<typename Node_Update> struct trie_metadata_helper<Node_Update, false> { typedef typename Node_Update::metadata_type type; }; + /// Specialization, true. template<typename Node_Update> struct trie_metadata_helper<Node_Update, true> { @@ -89,6 +96,7 @@ namespace __gnu_pbds public: typedef typename trie_metadata_helper<__node_u, null_update>::type type; }; + //@} } // namespace detail } // namespace __gnu_pbds diff --git a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp index 59edfbb5760..467c0773663 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp @@ -53,7 +53,7 @@ namespace __gnu_pbds typedef typename __rebind_k::other::const_reference key_const_reference; typedef std::string::const_iterator const_iterator; - // Element type. + /// Element type. typedef char e_type; enum @@ -61,15 +61,15 @@ namespace __gnu_pbds max_size = 4 }; - // Returns a const_iterator to the first element of r_key. + /// Returns a const_iterator to the first element of r_key. inline static const_iterator begin(key_const_reference); - // Returns a const_iterator to the after-last element of r_key. + /// Returns a const_iterator to the after-last element of r_key. inline static const_iterator end(key_const_reference); - // Maps an element to a position. + /// Maps an element to a position. inline static size_type e_pos(e_type); }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp index 6c97aee052a..6c71ba81ce7 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp @@ -52,11 +52,11 @@ namespace __gnu_pbds typedef std::size_t metadata_type; protected: - // Default constructor. + /// Default constructor. sample_trie_node_update(); - // Updates the rank of a node through a node_iterator node_it; - // end_nd_it is the end node iterator. + /// Updates the rank of a node through a node_iterator node_it; + /// end_nd_it is the end node iterator. inline void operator()(node_iterator, node_const_iterator) const; }; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp index 50db9b2bc90..cb0afdbd70e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp @@ -51,6 +51,11 @@ namespace __gnu_pbds { namespace detail { + /** + * @addtogroup traits Traits + * @{ + */ + /// Primary template. template<typename Key, typename Mapped> struct no_throw_copies @@ -68,11 +73,6 @@ namespace __gnu_pbds }; - //@{ - /** - * Data properties computation. - */ - /// Stored value. template<typename _Tv> struct stored_value diff --git a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp index d1221413c66..0cd75fc05a6 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/const_iterator.hpp @@ -39,83 +39,66 @@ * table. */ -// Const range-type iterator. -class const_iterator_ : - public point_const_iterator_ - +/// Const range-type iterator. +class const_iterator_ +: public point_const_iterator_ { - public: - - // Category. + /// Category. typedef std::forward_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef typename _Alloc::difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef value_type_ value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef pointer_ pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef const_pointer_ const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef reference_ reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef const_reference_ const_reference; -public: - - // Default constructor. - inline - const_iterator_() - - : m_p_tbl(0) + /// Default constructor. + const_iterator_() : m_p_tbl(0) { } - // Increments. - inline const_iterator_& + /// Increments. + const_iterator_& operator++() { m_p_tbl->inc_it_state(base_type::m_p_value, m_pos); - - return (*this); + return *this; } - // Increments. - inline const_iterator_ + /// Increments. + const_iterator_ operator++(int) { const_iterator_ ret =* this; - m_p_tbl->inc_it_state(base_type::m_p_value, m_pos); - - return (ret); + return ret; } protected: - typedef point_const_iterator_ base_type; -protected: - /** * Constructor used by the table to initiate the generalized * pointer and position (e.g., this is called from within a find() * of a table. * */ - inline - const_iterator_(const_pointer_ p_value, PB_DS_GEN_POS pos, const PB_DS_CLASS_C_DEC* p_tbl) : point_const_iterator_(p_value), - m_p_tbl(p_tbl), - m_pos(pos) + const_iterator_(const_pointer_ p_value, PB_DS_GEN_POS pos, + const PB_DS_CLASS_C_DEC* p_tbl) + : point_const_iterator_(p_value), m_p_tbl(p_tbl), m_pos(pos) { } -protected: - /** * Pointer to the table object which created the iterator (used for * incrementing its position. @@ -126,4 +109,3 @@ protected: friend class PB_DS_CLASS_C_DEC; }; - diff --git a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/iterator.hpp index 52b90a511e0..781bd44206c 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/iterator.hpp @@ -39,112 +39,92 @@ * table. */ -// Range-type iterator. -class iterator_ : - public const_iterator_ - +/// Range-type iterator. +class iterator_ +: public const_iterator_ { - public: - - // Category. + /// Category. typedef std::forward_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef typename _Alloc::difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef value_type_ value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef pointer_ pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef const_pointer_ const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef reference_ reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef const_reference_ const_reference; -public: - - // Default constructor. + /// Default constructor. inline iterator_() + : const_iterator_(0, PB_DS_GEN_POS(), 0) { } - : const_iterator_(0, PB_DS_GEN_POS(), 0) - { } - - // Conversion to a point-type iterator. + /// Conversion to a point-type iterator. inline operator point_iterator_() - { - return (point_iterator_( - const_cast<pointer>(const_iterator_::m_p_value))); - } + { return point_iterator_(const_cast<pointer>(const_iterator_::m_p_value)); } - // Conversion to a point-type iterator. + /// Conversion to a point-type iterator. inline operator const point_iterator_() const - { - return (point_iterator_( - const_cast<pointer>(const_iterator_::m_p_value))); - } + { return point_iterator_(const_cast<pointer>(const_iterator_::m_p_value)); } - // Access. - inline pointer + /// Access. + pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_value != 0); - return (const_cast<pointer>(base_type::m_p_value)); } - // Access. - inline reference + /// Access. + reference operator*() const { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_value != 0); - return (const_cast<reference>(*base_type::m_p_value)); } - // Increments. - inline iterator_& + /// Increments. + iterator_& operator++() { base_type::m_p_tbl->inc_it_state(base_type::m_p_value, base_type::m_pos); - - return (*this); + return *this; } - // Increments. - inline iterator_ + /// Increments. + iterator_ operator++(int) { iterator_ ret =* this; - base_type::m_p_tbl->inc_it_state(base_type::m_p_value, base_type::m_pos); - - return (ret); + return ret; } protected: typedef const_iterator_ base_type; -protected: - /** * Constructor used by the table to initiate the generalized * pointer and position (e.g., this is called from within a find() * of a table. * */ inline - iterator_(pointer p_value, PB_DS_GEN_POS pos, PB_DS_CLASS_C_DEC* p_tbl) : const_iterator_(p_value, pos, p_tbl) + iterator_(pointer p_value, PB_DS_GEN_POS pos, PB_DS_CLASS_C_DEC* p_tbl) + : const_iterator_(p_value, pos, p_tbl) { } friend class PB_DS_CLASS_C_DEC; }; - diff --git a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp index 257067a8952..fa33f22df4b 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp @@ -41,105 +41,87 @@ class point_iterator_; -// Const point-type iterator. +/// Const point-type iterator. class point_const_iterator_ { - public: - - // Category. + /// Category. typedef trivial_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef trivial_iterator_difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef value_type_ value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef pointer_ pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef const_pointer_ const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef reference_ reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef const_reference_ const_reference; -public: - inline point_const_iterator_(const_pointer p_value) : m_p_value(p_value) { } - // Default constructor. + /// Default constructor. inline - point_const_iterator_() - - : m_p_value(0) + point_const_iterator_() : m_p_value(0) { } - // Copy constructor. + /// Copy constructor. inline point_const_iterator_(const point_const_iterator_& other) - - : m_p_value(other.m_p_value) + : m_p_value(other.m_p_value) { } - // Copy constructor. + /// Copy constructor. inline point_const_iterator_(const point_iterator_& other) - - : m_p_value(other.m_p_value) + : m_p_value(other.m_p_value) { } - // Access. - inline const_pointer + /// Access. + const_pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != 0); - - return (m_p_value); + return m_p_value; } - // Access. - inline const_reference + /// Access. + const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != 0); - - return (*m_p_value); + return *m_p_value; } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator==(const point_iterator_& other) const - { - return (m_p_value == other.m_p_value); - } + { return m_p_value == other.m_p_value; } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator==(const point_const_iterator_& other) const - { - return (m_p_value == other.m_p_value); - } + { return m_p_value == other.m_p_value; } - // Compares content (negatively) to a different iterator object. - inline bool + /// Compares content (negatively) to a different iterator object. + bool operator!=(const point_iterator_& other) const - { - return (m_p_value != other.m_p_value); - } + { return m_p_value != other.m_p_value; } - // Compares content (negatively) to a different iterator object. - inline bool + /// Compares content (negatively) to a different iterator object. + bool operator!=(const point_const_iterator_& other) const - { - return (m_p_value != other.m_p_value); - } + { return m_p_value != other.m_p_value; } protected: const_pointer m_p_value; diff --git a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp index f74f03d7a48..0dd3946bf52 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/unordered_iterator/point_iterator.hpp @@ -39,94 +39,78 @@ * methods. */ -// Find type iterator. +/// Find type iterator. class point_iterator_ { - public: - - // Category. + /// Category. typedef trivial_iterator_tag iterator_category; - // Difference type. + /// Difference type. typedef trivial_iterator_difference_type difference_type; - // Iterator's value type. + /// Iterator's value type. typedef value_type_ value_type; - // Iterator's pointer type. + /// Iterator's pointer type. typedef pointer_ pointer; - // Iterator's const pointer type. + /// Iterator's const pointer type. typedef const_pointer_ const_pointer; - // Iterator's reference type. + /// Iterator's reference type. typedef reference_ reference; - // Iterator's const reference type. + /// Iterator's const reference type. typedef const_reference_ const_reference; -public: - - // Default constructor. + /// Default constructor. inline point_iterator_() - - : m_p_value(0) + : m_p_value(0) { } - // Copy constructor. + /// Copy constructor. inline point_iterator_(const point_iterator_& other) - - : m_p_value(other.m_p_value) + : m_p_value(other.m_p_value) { } - // Access. - inline pointer + /// Access. + pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != 0); - return (m_p_value); } - // Access. - inline reference + /// Access. + reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != 0); - return (*m_p_value); } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator==(const point_iterator_& other) const - { - return (m_p_value == other.m_p_value); - } + { return m_p_value == other.m_p_value; } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator==(const point_const_iterator_& other) const - { - return (m_p_value == other.m_p_value); - } + { return m_p_value == other.m_p_value; } - // Compares content to a different iterator object. - inline bool + /// Compares content to a different iterator object. + bool operator!=(const point_iterator_& other) const - { - return (m_p_value != other.m_p_value); - } + { return m_p_value != other.m_p_value; } - // Compares content (negatively) to a different iterator object. - inline bool + /// Compares content (negatively) to a different iterator object. + bool operator!=(const point_const_iterator_& other) const - { - return (m_p_value != other.m_p_value); - } + { return m_p_value != other.m_p_value; } inline point_iterator_(pointer p_value) : m_p_value(p_value) @@ -140,4 +124,3 @@ protected: protected: pointer m_p_value; }; - diff --git a/libstdc++-v3/include/ext/pb_ds/exception.hpp b/libstdc++-v3/include/ext/pb_ds/exception.hpp index b34e3ed26f2..5213fa43aa9 100644 --- a/libstdc++-v3/include/ext/pb_ds/exception.hpp +++ b/libstdc++-v3/include/ext/pb_ds/exception.hpp @@ -1,6 +1,6 @@ // -*- C++ -*- -// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -48,23 +48,29 @@ namespace __gnu_pbds { - // Base class for exceptions. + /** + * @defgroup exceptions-pbds Exceptions + * @ingroup pbds + * @{ + */ + + /// Base class for exceptions. struct container_error : public std::logic_error { - container_error() + container_error() : std::logic_error(__N("__gnu_pbds::container_error")) { } }; - // An entry cannot be inserted into a container object for logical - // reasons (not, e.g., if memory is unabvailable, in which case - // the allocator_type's exception will be thrown). + /// An entry cannot be inserted into a container object for logical + /// reasons (not, e.g., if memory is unabvailable, in which case + /// the allocator_type's exception will be thrown). struct insert_error : public container_error { }; - // A join cannot be performed logical reasons (i.e., the ranges of - // the two container objects being joined overlaps. + /// A join cannot be performed logical reasons (i.e., the ranges of + /// the two container objects being joined overlaps. struct join_error : public container_error { }; - // A container cannot be resized. + /// A container cannot be resized. struct resize_error : public container_error { }; #if __EXCEPTIONS @@ -100,6 +106,7 @@ namespace __gnu_pbds __throw_resize_error(void) { std::abort(); } #endif + //@} } // namespace __gnu_pbds #endif diff --git a/libstdc++-v3/include/ext/pb_ds/hash_policy.hpp b/libstdc++-v3/include/ext/pb_ds/hash_policy.hpp index 1fa93035109..dbada2110f9 100644 --- a/libstdc++-v3/include/ext/pb_ds/hash_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/hash_policy.hpp @@ -67,7 +67,7 @@ namespace __gnu_pbds swap(PB_DS_CLASS_C_DEC& other); protected: - // Returns the i-th offset from the hash value. + /// Returns the i-th offset from the hash value. inline size_type operator()(size_type i) const; }; @@ -91,7 +91,7 @@ namespace __gnu_pbds swap(PB_DS_CLASS_C_DEC& other); protected: - // Returns the i-th offset from the hash value. + /// Returns the i-th offset from the hash value. inline size_type operator()(size_type i) const; }; @@ -104,9 +104,9 @@ namespace __gnu_pbds #define PB_DS_CLASS_T_DEC template<typename Size_Type> #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type> - /// A mask range-hashing class (uses a bit-mask). + /// A mask range-hashing class (uses a bitmask). template<typename Size_Type = std::size_t> - class direct_mask_range_hashing + class direct_mask_range_hashing : public detail::mask_based_range_hashing<Size_Type> { private: @@ -122,8 +122,8 @@ namespace __gnu_pbds void notify_resized(size_type size); - // Transforms the __hash value hash into a ranged-hash value - // (using a bit-mask). + /// Transforms the __hash value hash into a ranged-hash value + /// (using a bit-mask). inline size_type operator()(size_type hash) const; }; @@ -138,24 +138,24 @@ namespace __gnu_pbds /// A mod range-hashing class (uses the modulo function). template<typename Size_Type = std::size_t> - class direct_mod_range_hashing + class direct_mod_range_hashing : public detail::mod_based_range_hashing<Size_Type> { public: typedef Size_Type size_type; - + void swap(PB_DS_CLASS_C_DEC& other); protected: void notify_resized(size_type size); - - // Transforms the __hash value hash into a ranged-hash value - // (using a modulo operation). + + /// Transforms the __hash value hash into a ranged-hash value + /// (using a modulo operation). inline size_type operator()(size_type hash) const; - + private: typedef detail::mod_based_range_hashing<size_type> mod_based_base; }; @@ -179,12 +179,15 @@ namespace __gnu_pbds enum { + /// Specifies whether the load factor can be accessed + /// externally. The two options have different trade-offs in + /// terms of flexibility, genericity, and encapsulation. external_load_access = External_Load_Access }; - // Default constructor, or constructor taking load_min and - // load_max load factors between which this policy will keep the - // actual load. + /// Default constructor, or constructor taking load_min and + /// load_max load factors between which this policy will keep the + /// actual load. hash_load_check_resize_trigger(float load_min = 0.125, float load_max = 0.5); @@ -194,12 +197,12 @@ namespace __gnu_pbds virtual ~hash_load_check_resize_trigger(); - // Returns a pair of the minimal and maximal loads, respectively. + /// Returns a pair of the minimal and maximal loads, respectively. inline std::pair<float, float> get_loads() const; - // Sets the loads through a pair of the minimal and maximal - // loads, respectively. + /// Sets the loads through a pair of the minimal and maximal + /// loads, respectively. void set_loads(std::pair<float, float> load_pair); @@ -231,20 +234,20 @@ namespace __gnu_pbds inline void notify_erase_search_end(); - // Notifies an element was inserted. The total number of entries - // in the table is num_entries. + /// Notifies an element was inserted. The total number of entries + /// in the table is num_entries. inline void notify_inserted(size_type num_entries); inline void notify_erased(size_type num_entries); - // Notifies the table was cleared. + /// Notifies the table was cleared. void notify_cleared(); - // Notifies the table was resized as a result of this object's - // signifying that a resize is needed. + /// Notifies the table was resized as a result of this object's + /// signifying that a resize is needed. void notify_resized(size_type new_size); @@ -266,7 +269,7 @@ namespace __gnu_pbds #ifdef _GLIBCXX_DEBUG void assert_valid(const char* file, int line) const; -#endif +#endif float m_load_min; float m_load_max; @@ -290,76 +293,95 @@ namespace __gnu_pbds class cc_hash_max_collision_check_resize_trigger { public: - typedef Size_Type size_type; + typedef Size_Type size_type; enum { + /// Specifies whether the load factor can be accessed + /// externally. The two options have different trade-offs in + /// terms of flexibility, genericity, and encapsulation. external_load_access = External_Load_Access }; - // Default constructor, or constructor taking load, a __load - // factor which it will attempt to maintain. + /// Default constructor, or constructor taking load, a __load + /// factor which it will attempt to maintain. cc_hash_max_collision_check_resize_trigger(float load = 0.5); void swap(PB_DS_CLASS_C_DEC& other); - // Returns the current load. + /// Returns the current load. inline float get_load() const; - // Sets the load; does not resize the container. + /// Sets the load; does not resize the container. void set_load(float load); protected: + /// Notifies an insert search started. inline void notify_insert_search_start(); + /// Notifies a search encountered a collision. inline void notify_insert_search_collision(); + /// Notifies a search ended. inline void notify_insert_search_end(); + /// Notifies a find search started. inline void notify_find_search_start(); + /// Notifies a search encountered a collision. inline void notify_find_search_collision(); + /// Notifies a search ended. inline void notify_find_search_end(); + /// Notifies an erase search started. inline void notify_erase_search_start(); + /// Notifies a search encountered a collision. inline void notify_erase_search_collision(); + /// Notifies a search ended. inline void notify_erase_search_end(); + /// Notifies an element was inserted. inline void notify_inserted(size_type num_entries); + /// Notifies an element was erased. inline void notify_erased(size_type num_entries); + /// Notifies the table was cleared. void notify_cleared(); - // Notifies the table was resized as a result of this object's - // signifying that a resize is needed. + /// Notifies the table was resized as a result of this object's + /// signifying that a resize is needed. void notify_resized(size_type new_size); + /// Notifies the table was resized externally. void notify_externally_resized(size_type new_size); + /// Queries whether a resize is needed. inline bool is_resize_needed() const; + /// Queries whether a grow is needed. This method is called only + /// if this object indicated is needed. inline bool is_grow_needed(size_type size, size_type num_entries) const; @@ -393,10 +415,10 @@ namespace __gnu_pbds public: typedef Size_Type size_type; - // Default constructor, or onstructor taking a start_size, or - // constructor taking a start size and grow_factor. The policy - // will use the sequence of sizes start_size, start_size* - // grow_factor, start_size* grow_factor^2, ... + /// Default constructor, or onstructor taking a start_size, or + /// constructor taking a start size and grow_factor. The policy + /// will use the sequence of sizes start_size, start_size* + /// grow_factor, start_size* grow_factor^2, ... hash_exponential_size_policy(size_type start_size = 8, size_type grow_factor = 2); @@ -428,12 +450,12 @@ namespace __gnu_pbds class hash_prime_size_policy { public: - // Size type. + /// Size type. typedef std::size_t size_type; - // Default constructor, or onstructor taking a start_size The - // policy will use the sequence of sizes approximately - // start_size, start_size* 2, start_size* 2^2, ... + /// Default constructor, or onstructor taking a start_size The + /// policy will use the sequence of sizes approximately + /// start_size, start_size* 2, start_size* 2^2, ... hash_prime_size_policy(size_type start_size = 8); inline void @@ -464,7 +486,7 @@ namespace __gnu_pbds typename Trigger_Policy = hash_load_check_resize_trigger<>, bool External_Size_Access = false, typename Size_Type = std::size_t> - class hash_standard_resize_policy + class hash_standard_resize_policy : public Size_Policy, public Trigger_Policy { public: @@ -477,18 +499,18 @@ namespace __gnu_pbds external_size_access = External_Size_Access }; - // Default constructor. + /// Default constructor. hash_standard_resize_policy(); - // constructor taking some policies r_size_policy will be copied - // by the Size_Policy object of this object. + /// constructor taking some policies r_size_policy will be copied + /// by the Size_Policy object of this object. hash_standard_resize_policy(const Size_Policy& r_size_policy); - // constructor taking some policies. r_size_policy will be - // copied by the Size_Policy object of this - // object. r_trigger_policy will be copied by the Trigger_Policy - // object of this object. - hash_standard_resize_policy(const Size_Policy& r_size_policy, + /// constructor taking some policies. r_size_policy will be + /// copied by the Size_Policy object of this + /// object. r_trigger_policy will be copied by the Trigger_Policy + /// object of this object. + hash_standard_resize_policy(const Size_Policy& r_size_policy, const Trigger_Policy& r_trigger_policy); virtual @@ -497,29 +519,29 @@ namespace __gnu_pbds inline void swap(PB_DS_CLASS_C_DEC& other); - // Access to the Size_Policy object used. - Size_Policy& + /// Access to the Size_Policy object used. + Size_Policy& get_size_policy(); - // Const access to the Size_Policy object used. - const Size_Policy& + /// Const access to the Size_Policy object used. + const Size_Policy& get_size_policy() const; - // Access to the Trigger_Policy object used. - Trigger_Policy& + /// Access to the Trigger_Policy object used. + Trigger_Policy& get_trigger_policy(); - // Access to the Trigger_Policy object used. - const Trigger_Policy& + /// Access to the Trigger_Policy object used. + const Trigger_Policy& get_trigger_policy() const; - // Returns the actual size of the container. + /// Returns the actual size of the container. inline size_type get_actual_size() const; - // Resizes the container to suggested_new_size, a suggested size - // (the actual size will be determined by the Size_Policy - // object). + /// Resizes the container to suggested_new_size, a suggested size + /// (the actual size will be determined by the Size_Policy + /// object). void resize(size_type suggested_new_size); @@ -566,15 +588,15 @@ namespace __gnu_pbds inline bool is_resize_needed() const; - // Queries what the new size should be, when the container is - // resized naturally. The current __size of the container is - // size, and the number of used entries within the container is - // num_used_e. + /// Queries what the new size should be, when the container is + /// resized naturally. The current __size of the container is + /// size, and the number of used entries within the container is + /// num_used_e. size_type get_new_size(size_type size, size_type num_used_e) const; private: - // Resizes to new_size. + /// Resizes to new_size. virtual void do_resize(size_type new_size); @@ -592,4 +614,4 @@ namespace __gnu_pbds } // namespace __gnu_pbds -#endif +#endif diff --git a/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp b/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp index e879b8088c9..d73d55f0aaa 100644 --- a/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp @@ -60,23 +60,23 @@ namespace __gnu_pbds public: typedef _Alloc allocator_type; - // Metadata on which this functor operates. + /// Metadata on which this functor operates. typedef null_type metadata_type; private: typedef typename _Alloc::template rebind<metadata_type> __rebind_m; public: - // Reference to metadata on which this functor operates. + /// Reference to metadata on which this functor operates. typedef typename __rebind_m::other::reference metadata_reference; - // Creates a metadata object. + /// Creates a metadata object. metadata_type operator()() const { return s_metadata; } - // Decides whether a metadata object should be moved to the front - // of the list. + /// Decides whether a metadata object should be moved to the front + /// of the list. inline bool operator()(metadata_reference r_metadata) const { return true; } @@ -99,10 +99,12 @@ namespace __gnu_pbds enum { + /// When some element is accessed this number of times, it + /// will be moved to the front of the list. max_count = Max_Count }; - // Metadata on which this functor operates. + /// Metadata on which this functor operates. typedef detail::lu_counter_metadata<size_type> metadata_type; private: @@ -110,16 +112,16 @@ namespace __gnu_pbds typedef typename _Alloc::template rebind<metadata_type> __rebind_m; public: - // Reference to metadata on which this functor operates. + /// Reference to metadata on which this functor operates. typedef typename __rebind_m::other::reference metadata_reference; - // Creates a metadata object. + /// Creates a metadata object. metadata_type operator()() const { return base_type::operator()(max_count); } - // Decides whether a metadata object should be moved to the front - // of the list. + /// Decides whether a metadata object should be moved to the front + /// of the list. bool operator()(metadata_reference r_data) const { return base_type::operator()(r_data, max_count); } diff --git a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp index 8cd7a26db6a..825699f4685 100644 --- a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp +++ b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp @@ -49,10 +49,34 @@ namespace __gnu_pbds { /** - * @brief A priority queue composed of one specific heap policy. - * @ingroup pbds + * @defgroup heap-based + * @ingroup containers-pbds + * @{ */ - template<typename _Tv, + + /** + * @defgroup heap-detail Base and Policy Classes + * @ingroup heap-based + */ + + /** + * A priority queue composed of one specific heap policy. + * + * @tparam _Tv Value type. + * @tparam Cmp_Fn Comparison functor. + * @tparam Tag Instantiating data structure type, + * see container_tag. + * @tparam _Alloc Allocator type. + * + * Base is dispatched at compile time via Tag, from the following + * choices: binary_heap_tag, binomial_heap_tag, pairing_heap_tag, + * rc_binomial_heap_tag, thin_heap_tag + * + * Base choices are: detail::binary_heap, detail::binomial_heap, + * detail::pairing_heap, detail::rc_binomial_heap, + * detail::thin_heap. + */ + template<typename _Tv, typename Cmp_Fn = std::less<_Tv>, typename Tag = pairing_heap_tag, typename _Alloc = std::allocator<char> > @@ -87,21 +111,21 @@ namespace __gnu_pbds priority_queue() { } - // Constructor taking some policy objects. r_cmp_fn will be copied - // by the Cmp_Fn object of the container object. + /// Constructor taking some policy objects. r_cmp_fn will be + /// copied by the Cmp_Fn object of the container object. priority_queue(const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) { } - // 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. + /// 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> priority_queue(It first_it, It last_it) { base_type::copy_from_range(first_it, last_it); } - // 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. + /// 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> priority_queue(It first_it, It last_it, const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) @@ -129,5 +153,5 @@ namespace __gnu_pbds { base_type::swap(other); } }; } // namespace __gnu_pbds - + //@} heap-based #endif diff --git a/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp b/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp index d5df54f5877..f7544ff7ef3 100644 --- a/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp +++ b/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp @@ -72,7 +72,7 @@ namespace __gnu_pbds * @{ */ /// A trivial iterator tag. Signifies that the iterators has none of - /// the STL's movement abilities. + /// std::iterators's movement abilities. struct trivial_iterator_tag { }; @@ -81,7 +81,7 @@ namespace __gnu_pbds /** - * @defgroup invalidation_tags Invalidation Guarantees. + * @defgroup invalidation_tags Invalidation Guarantees * @ingroup tags * @{ */ @@ -118,7 +118,7 @@ namespace __gnu_pbds /** - * @defgroup ds_tags Data Structure Tag Hierarchy. + * @defgroup ds_tags Data Structure Type * @ingroup tags * @{ */ @@ -147,7 +147,7 @@ namespace __gnu_pbds /// Basic branch structure. struct basic_branch_tag : public associative_tag { }; - /// tree. + /// Basic tree structure. struct tree_tag : public basic_branch_tag { }; /// Red-black tree. @@ -159,7 +159,7 @@ namespace __gnu_pbds /// Ordered-vector tree. struct ov_tree_tag : public tree_tag { }; - /// trie. + /// Basic trie structure. struct trie_tag : public basic_branch_tag { }; /// PATRICIA trie. @@ -210,6 +210,11 @@ namespace __gnu_pbds */ struct null_type { }; + /// A null node updator, indicating that no node updates are required. + template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4> + struct null_node_update : public null_type + { }; + /// Primary template, container traits base. template<typename _Tag> @@ -219,8 +224,8 @@ namespace __gnu_pbds template<> struct container_traits_base<cc_hash_tag> { - typedef cc_hash_tag container_category; - typedef point_invalidation_guarantee invalidation_guarantee; + typedef cc_hash_tag container_category; + typedef point_invalidation_guarantee invalidation_guarantee; enum { @@ -235,8 +240,8 @@ namespace __gnu_pbds template<> struct container_traits_base<gp_hash_tag> { - typedef gp_hash_tag container_category; - typedef basic_invalidation_guarantee invalidation_guarantee; + typedef gp_hash_tag container_category; + typedef basic_invalidation_guarantee invalidation_guarantee; enum { @@ -251,8 +256,8 @@ namespace __gnu_pbds template<> struct container_traits_base<rb_tree_tag> { - typedef rb_tree_tag container_category; - typedef range_invalidation_guarantee invalidation_guarantee; + typedef rb_tree_tag container_category; + typedef range_invalidation_guarantee invalidation_guarantee; enum { @@ -267,8 +272,8 @@ namespace __gnu_pbds template<> struct container_traits_base<splay_tree_tag> { - typedef splay_tree_tag container_category; - typedef range_invalidation_guarantee invalidation_guarantee; + typedef splay_tree_tag container_category; + typedef range_invalidation_guarantee invalidation_guarantee; enum { @@ -283,8 +288,8 @@ namespace __gnu_pbds template<> struct container_traits_base<ov_tree_tag> { - typedef ov_tree_tag container_category; - typedef basic_invalidation_guarantee invalidation_guarantee; + typedef ov_tree_tag container_category; + typedef basic_invalidation_guarantee invalidation_guarantee; enum { @@ -299,8 +304,8 @@ namespace __gnu_pbds template<> struct container_traits_base<pat_trie_tag> { - typedef pat_trie_tag container_category; - typedef range_invalidation_guarantee invalidation_guarantee; + typedef pat_trie_tag container_category; + typedef range_invalidation_guarantee invalidation_guarantee; enum { @@ -315,8 +320,8 @@ namespace __gnu_pbds template<> struct container_traits_base<list_update_tag> { - typedef list_update_tag container_category; - typedef point_invalidation_guarantee invalidation_guarantee; + typedef list_update_tag container_category; + typedef point_invalidation_guarantee invalidation_guarantee; enum { @@ -331,8 +336,8 @@ namespace __gnu_pbds template<> struct container_traits_base<pairing_heap_tag> { - typedef pairing_heap_tag container_category; - typedef point_invalidation_guarantee invalidation_guarantee; + typedef pairing_heap_tag container_category; + typedef point_invalidation_guarantee invalidation_guarantee; enum { @@ -347,8 +352,8 @@ namespace __gnu_pbds template<> struct container_traits_base<thin_heap_tag> { - typedef thin_heap_tag container_category; - typedef point_invalidation_guarantee invalidation_guarantee; + typedef thin_heap_tag container_category; + typedef point_invalidation_guarantee invalidation_guarantee; enum { @@ -363,8 +368,8 @@ namespace __gnu_pbds template<> struct container_traits_base<binomial_heap_tag> { - typedef binomial_heap_tag container_category; - typedef point_invalidation_guarantee invalidation_guarantee; + typedef binomial_heap_tag container_category; + typedef point_invalidation_guarantee invalidation_guarantee; enum { @@ -379,8 +384,8 @@ namespace __gnu_pbds template<> struct container_traits_base<rc_binomial_heap_tag> { - typedef rc_binomial_heap_tag container_category; - typedef point_invalidation_guarantee invalidation_guarantee; + typedef rc_binomial_heap_tag container_category; + typedef point_invalidation_guarantee invalidation_guarantee; enum { @@ -395,8 +400,8 @@ namespace __gnu_pbds template<> struct container_traits_base<binary_heap_tag> { - typedef binary_heap_tag container_category; - typedef basic_invalidation_guarantee invalidation_guarantee; + typedef binary_heap_tag container_category; + typedef basic_invalidation_guarantee invalidation_guarantee; enum { @@ -421,9 +426,16 @@ namespace __gnu_pbds enum { + /// True only if Cntnr objects guarantee storing keys by order. order_preserving = base_type::order_preserving, + + /// True only if erasing a key can throw. erase_can_throw = base_type::erase_can_throw, + + /// True only if split or join operations can throw. split_join_can_throw = base_type::split_join_can_throw, + + /// True only reverse iterators are supported. reverse_iteration = base_type::reverse_iteration }; }; diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp index 4df9df1df2a..ecc4991f720 100644 --- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp @@ -79,66 +79,66 @@ namespace __gnu_pbds typedef typename node_const_iterator::value_type const_iterator; typedef typename node_iterator::value_type iterator; - // Finds an entry by __order. Returns a const_iterator to the - // entry with the __order order, or a const_iterator to the - // container object's end if order is at least the size of the - // container object. + /// Finds an entry by __order. Returns a const_iterator to the + /// entry with the __order order, or a const_iterator to the + /// container object's end if order is at least the size of the + /// container object. inline const_iterator find_by_order(size_type) const; - // Finds an entry by __order. Returns an iterator to the entry - // with the __order order, or an iterator to the container - // object's end if order is at least the size of the container - // object. + /// Finds an entry by __order. Returns an iterator to the entry + /// with the __order order, or an iterator to the container + /// object's end if order is at least the size of the container + /// object. inline iterator find_by_order(size_type); - // Returns the order of a key within a sequence. For exapmle, if - // r_key is the smallest key, this method will return 0; if r_key - // is a key between the smallest and next key, this method will - // return 1; if r_key is a key larger than the largest key, this - // method will return the size of r_c. + /// Returns the order of a key within a sequence. For exapmle, if + /// r_key is the smallest key, this method will return 0; if r_key + /// is a key between the smallest and next key, this method will + /// return 1; if r_key is a key larger than the largest key, this + /// method will return the size of r_c. inline size_type order_of_key(key_const_reference) const; private: - // Const reference to the container's value-type. + /// Const reference to the container's value-type. typedef typename base_type::const_reference const_reference; - // Const pointer to the container's value-type. + /// Const pointer to the container's value-type. typedef typename base_type::const_pointer const_pointer; typedef typename _Alloc::template rebind<metadata_type>::other __rebind_m; - // Const metadata reference. + /// Const metadata reference. typedef typename __rebind_m::const_reference metadata_const_reference; - // Metadata reference. + /// Metadata reference. typedef typename __rebind_m::reference metadata_reference; - // Returns the node_const_iterator associated with the tree's root node. + /// Returns the node_const_iterator associated with the tree's root node. virtual node_const_iterator node_begin() const = 0; - // Returns the node_iterator associated with the tree's root node. + /// Returns the node_iterator associated with the tree's root node. virtual node_iterator node_begin() = 0; - // Returns the node_const_iterator associated with a just-after leaf node. + /// Returns the node_const_iterator associated with a just-after leaf node. virtual node_const_iterator node_end() const = 0; - // Returns the node_iterator associated with a just-after leaf node. + /// Returns the node_iterator associated with a just-after leaf node. virtual node_iterator node_end() = 0; - // Access to the cmp_fn object. + /// Access to the cmp_fn object. virtual cmp_fn& get_cmp_fn() = 0; protected: - // Updates the rank of a node through a node_iterator node_it; - // end_nd_it is the end node iterator. + /// Updates the rank of a node through a node_iterator node_it; + /// end_nd_it is the end node iterator. inline void operator()(node_iterator, node_const_iterator) const; diff --git a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp index 8fd4900b133..a5c3399f3f4 100644 --- a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp +++ b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp @@ -57,7 +57,16 @@ namespace __gnu_pbds #define PB_DS_CLASS_C_DEC \ trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc> - /// Element access traits for string types. + /** + * Element access traits for string types. + * + * @tparam String String type. + * @tparam Min_E_Val Minimal element value. + * @tparam Max_E_Val Maximum element value. + * @tparam Reverse Reverse iteration should be used. + * Default: false. + * @tparam _Alloc Allocator type. + */ template<typename String = std::string, typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min, typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max, @@ -76,12 +85,12 @@ namespace __gnu_pbds reverse = Reverse }; - // Element const iterator type. + /// Element const iterator type. typedef typename detail::__conditional_type<Reverse, \ typename String::const_reverse_iterator, \ typename String::const_iterator>::__type const_iterator; - // Element type. + /// Element type. typedef typename std::iterator_traits<const_iterator>::value_type e_type; enum @@ -92,17 +101,17 @@ namespace __gnu_pbds }; PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); - // Returns a const_iterator to the first element of - // key_const_reference agumnet. + /// Returns a const_iterator to the first element of + /// key_const_reference agumnet. inline static const_iterator begin(key_const_reference); - // Returns a const_iterator to the after-last element of - // key_const_reference argument. + /// Returns a const_iterator to the after-last element of + /// key_const_reference argument. inline static const_iterator end(key_const_reference); - // Maps an element to a position. + /// Maps an element to a position. inline static size_type e_pos(e_type e); @@ -153,16 +162,16 @@ namespace __gnu_pbds typedef typename base_type::key_type key_type; typedef typename base_type::key_const_reference key_const_reference; - // Element access traits. + /// Element access traits. typedef _ATraits access_traits; - // Const element iterator. + /// Const element iterator. typedef typename access_traits::const_iterator a_const_iterator; - // _Alloc type. + /// _Alloc type. typedef _Alloc allocator_type; - // Size type. + /// Size type. typedef typename allocator_type::size_type size_type; typedef null_type metadata_type; typedef Node_Itr node_iterator; @@ -170,28 +179,28 @@ namespace __gnu_pbds typedef typename node_iterator::value_type iterator; typedef typename node_const_iterator::value_type const_iterator; - // Finds the const iterator range corresponding to all values - // whose prefixes match r_key. + /// Finds the const iterator range corresponding to all values + /// whose prefixes match r_key. std::pair<const_iterator, const_iterator> prefix_range(key_const_reference) const; - // Finds the iterator range corresponding to all values whose - // prefixes match r_key. + /// Finds the iterator range corresponding to all values whose + /// prefixes match r_key. std::pair<iterator, iterator> prefix_range(key_const_reference); - // Finds the const iterator range corresponding to all values - // whose prefixes match [b, e). + /// Finds the const iterator range corresponding to all values + /// whose prefixes match [b, e). std::pair<const_iterator, const_iterator> prefix_range(a_const_iterator, a_const_iterator) const; - // Finds the iterator range corresponding to all values whose - // prefixes match [b, e). + /// Finds the iterator range corresponding to all values whose + /// prefixes match [b, e). std::pair<iterator, iterator> prefix_range(a_const_iterator, a_const_iterator); protected: - // Called to update a node's metadata. + /// Called to update a node's metadata. inline void operator()(node_iterator node_it, node_const_iterator end_nd_it) const; @@ -200,31 +209,31 @@ namespace __gnu_pbds next_child(node_iterator, a_const_iterator, a_const_iterator, node_iterator, const access_traits&); - // Returns the const iterator associated with the just-after last element. + /// Returns the const iterator associated with the just-after last element. virtual const_iterator end() const = 0; - // Returns the iterator associated with the just-after last element. + /// Returns the iterator associated with the just-after last element. virtual iterator end() = 0; - // Returns the node_const_iterator associated with the trie's root node. + /// Returns the node_const_iterator associated with the trie's root node. virtual node_const_iterator node_begin() const = 0; - // Returns the node_iterator associated with the trie's root node. + /// Returns the node_iterator associated with the trie's root node. virtual node_iterator node_begin() = 0; - // Returns the node_const_iterator associated with a just-after leaf node. + /// Returns the node_const_iterator associated with a just-after leaf node. virtual node_const_iterator node_end() const = 0; - // Returns the node_iterator associated with a just-after leaf node. + /// Returns the node_iterator associated with a just-after leaf node. virtual node_iterator node_end() = 0; - // Access to the cmp_fn object. + /// Access to the cmp_fn object. virtual const access_traits& get_access_traits() const = 0; }; @@ -261,39 +270,39 @@ namespace __gnu_pbds typedef typename node_const_iterator::value_type const_iterator; typedef typename node_iterator::value_type iterator; - // Finds an entry by __order. Returns a const_iterator to the - // entry with the __order order, or a const_iterator to the - // container object's end if order is at least the size of the - // container object. + /// Finds an entry by __order. Returns a const_iterator to the + /// entry with the __order order, or a const_iterator to the + /// container object's end if order is at least the size of the + /// container object. inline const_iterator find_by_order(size_type) const; - // Finds an entry by __order. Returns an iterator to the entry - // with the __order order, or an iterator to the container - // object's end if order is at least the size of the container - // object. + /// Finds an entry by __order. Returns an iterator to the entry + /// with the __order order, or an iterator to the container + /// object's end if order is at least the size of the container + /// object. inline iterator find_by_order(size_type); - // Returns the order of a key within a sequence. For exapmle, if - // r_key is the smallest key, this method will return 0; if r_key - // is a key between the smallest and next key, this method will - // return 1; if r_key is a key larger than the largest key, this - // method will return the size of r_c. + /// Returns the order of a key within a sequence. For exapmle, if + /// r_key is the smallest key, this method will return 0; if r_key + /// is a key between the smallest and next key, this method will + /// return 1; if r_key is a key larger than the largest key, this + /// method will return the size of r_c. inline size_type order_of_key(key_const_reference) const; - // Returns the order of a prefix within a sequence. For exapmle, - // if [b, e] is the smallest prefix, this method will return 0; if - // r_key is a key between the smallest and next key, this method - // will return 1; if r_key is a key larger than the largest key, - // this method will return the size of r_c. + /// Returns the order of a prefix within a sequence. For exapmle, + /// if [b, e] is the smallest prefix, this method will return 0; if + /// r_key is a key between the smallest and next key, this method + /// will return 1; if r_key is a key larger than the largest key, + /// this method will return the size of r_c. inline size_type order_of_prefix(a_const_iterator, a_const_iterator) const; protected: - // Updates the rank of a node through a node_iterator node_it; - // end_nd_it is the end node iterator. + /// Updates the rank of a node through a node_iterator node_it; + /// end_nd_it is the end node iterator. inline void operator()(node_iterator, node_const_iterator) const; @@ -306,37 +315,37 @@ namespace __gnu_pbds typedef typename __rebind_ma::const_reference metadata_const_reference; typedef typename __rebind_ma::reference metadata_reference; - // Returns true if the container is empty. + /// Returns true if the container is empty. virtual bool empty() const = 0; - // Returns the iterator associated with the trie's first element. + /// Returns the iterator associated with the trie's first element. virtual iterator begin() = 0; - // Returns the iterator associated with the trie's - // just-after-last element. + /// Returns the iterator associated with the trie's + /// just-after-last element. virtual iterator end() = 0; - // Returns the node_const_iterator associated with the trie's root node. + /// Returns the node_const_iterator associated with the trie's root node. virtual node_const_iterator node_begin() const = 0; - // Returns the node_iterator associated with the trie's root node. + /// Returns the node_iterator associated with the trie's root node. virtual node_iterator node_begin() = 0; - // Returns the node_const_iterator associated with a just-after - // leaf node. + /// Returns the node_const_iterator associated with a just-after + /// leaf node. virtual node_const_iterator node_end() const = 0; - // Returns the node_iterator associated with a just-after leaf node. + /// Returns the node_iterator associated with a just-after leaf node. virtual node_iterator node_end() = 0; - // Access to the cmp_fn object. + /// Access to the cmp_fn object. virtual access_traits& get_access_traits() = 0; }; |