// -*- C++ -*-
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005-2024 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 2, or (at your option) any later
+// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
-// You should have received a copy of the GNU General Public License
-// along with this library; see the file COPYING. If not, write to
-// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
-// MA 02111-1307, USA.
-
-// As a special exception, you may use this file as part of a free
-// software library without restriction. Specifically, if other files
-// instantiate templates or use macros or inline functions from this
-// file, or you compile this file and link it with other files to
-// produce an executable, this file does not by itself cause the
-// resulting executable to be covered by the GNU General Public
-// License. This exception does not however invalidate any other
-// reasons why the executable file might be covered by the GNU General
-// Public License.
+// 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.
// warranty.
/**
- * @file pat_trie_.hpp
+ * @file pat_trie_/pat_trie_.hpp
* Contains an implementation class for a patricia tree.
*/
-/**
- * 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
- **/
-
-#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>
-#include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
-#include <ext/pb_ds/exception.hpp>
-#include <ext/pb_ds/tag_and_trait.hpp>
-#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
-#include <ext/pb_ds/detail/types_traits.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
-#include <ext/pb_ds/detail/cond_dealtor.hpp>
-#include <ext/pb_ds/detail/type_utils.hpp>
#include <iterator>
#include <utility>
#include <algorithm>
#include <functional>
#include <assert.h>
#include <list>
-#ifdef PB_DS_USE_MAP_DEBUG_BASE
-#include <ext/pb_ds/detail/map_debug_base.hpp>
-#endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
-
-namespace pb_ds
+#include <ext/pb_ds/exception.hpp>
+#include <ext/pb_ds/tag_and_trait.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+#include <ext/pb_ds/detail/cond_dealtor.hpp>
+#include <ext/pb_ds/detail/type_utils.hpp>
+#include <ext/pb_ds/detail/types_traits.hpp>
+#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
+#include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp>
+#include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp>
+#ifdef _GLIBCXX_DEBUG
+#include <ext/pb_ds/detail/debug_map_base.hpp>
+#endif
+#include <debug/debug.h>
+
+namespace __gnu_pbds
{
namespace detail
{
-
-#ifdef PB_DS_PAT_TRIE_DEBUG_
-#define PB_DS_DBG_ASSERT(X) assert(X)
-#define PB_DS_DBG_VERIFY(X) assert(X)
-#define PB_DS_DBG_ONLY(X) X
-#else // #ifdef PB_DS_PAT_TRIE_DEBUG_
-#define PB_DS_DBG_ASSERT(X)
-#define PB_DS_DBG_VERIFY(X) {if((X)==0);}
-#define PB_DS_DBG_ONLY(X) ;
-#endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
-
-#define PB_DS_CLASS_T_DEC \
- template< \
- typename Key, \
- typename Mapped, \
- class Node_And_It_Traits, \
- class Allocator>
-
#ifdef PB_DS_DATA_TRUE_INDICATOR
-#define PB_DS_CLASS_NAME \
- pat_trie_data_
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+#define PB_DS_PAT_TRIE_NAME pat_trie_map
+#endif
#ifdef PB_DS_DATA_FALSE_INDICATOR
-#define PB_DS_CLASS_NAME \
- pat_trie_no_data_
-#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
-
-#define PB_DS_CLASS_C_DEC \
- PB_DS_CLASS_NAME< \
- Key, \
- Mapped, \
- Node_And_It_Traits, \
- Allocator>
-
-#define PB_DS_TYPES_TRAITS_C_DEC \
- types_traits< \
- Key, \
- Mapped, \
- Allocator, \
- false>
-
-#ifdef PB_DS_USE_MAP_DEBUG_BASE
-#define PB_DS_MAP_DEBUG_BASE_C_DEC \
- map_debug_base< \
- Key, \
- eq_by_less< \
- Key, \
- std::less< \
- Key> >, \
- typename Allocator::template rebind< \
- Key>::other::const_reference>
-#endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
+#define PB_DS_PAT_TRIE_NAME pat_trie_set
+#endif
-#ifdef PB_DS_DATA_TRUE_INDICATOR
-#define PB_DS_V2F(X) (X).first
-#define PB_DS_V2S(X) (X).second
-#define PB_DS_EP2VP(X)& ((X)->m_value)
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+#define PB_DS_CLASS_T_DEC \
+ template<typename Key, typename Mapped, typename Node_And_It_Traits, \
+ typename _Alloc>
-#ifdef PB_DS_DATA_FALSE_INDICATOR
-#define PB_DS_V2F(X) (X)
-#define PB_DS_V2S(X) Mapped_Data()
-#define PB_DS_EP2VP(X)& ((X)->m_value.first)
-#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
+#define PB_DS_CLASS_C_DEC \
+ PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc>
+
+#define PB_DS_PAT_TRIE_TRAITS_BASE \
+ types_traits<Key, Mapped, _Alloc, false>
+
+#ifdef _GLIBCXX_DEBUG
+#define PB_DS_DEBUG_MAP_BASE_C_DEC \
+ debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \
+ typename rebind_traits<_Alloc, Key>::const_reference>
+#endif
-#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
- typedef \
- static_assert_dumclass< \
- sizeof(static_assert<(bool)(E)>)> \
- UNIQUE##static_assert_type
/**
- * class description = PATRICIA trie implementation.">
- **/
- template<typename Key,
- typename Mapped,
- class Node_And_It_Traits,
- class Allocator>
- class PB_DS_CLASS_NAME :
-#ifdef PB_DS_PAT_TRIE_DEBUG_
- public PB_DS_MAP_DEBUG_BASE_C_DEC,
-#endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
- public Node_And_It_Traits::synth_e_access_traits,
+ * @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
+ */
+ template<typename Key, typename Mapped, typename Node_And_It_Traits,
+ typename _Alloc>
+ class PB_DS_PAT_TRIE_NAME :
+#ifdef _GLIBCXX_DEBUG
+ public PB_DS_DEBUG_MAP_BASE_C_DEC,
+#endif
+ public Node_And_It_Traits::synth_access_traits,
public Node_And_It_Traits::node_update,
- public PB_DS_TYPES_TRAITS_C_DEC
+ public PB_DS_PAT_TRIE_TRAITS_BASE,
+ public pat_trie_base
{
-
private:
+ typedef pat_trie_base base_type;
+ typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base;
+ typedef Node_And_It_Traits traits_type;
+
+ typedef typename traits_type::synth_access_traits synth_access_traits;
+ typedef typename synth_access_traits::const_iterator a_const_iterator;
+
+ typedef typename traits_type::node node;
+ typedef rebind_traits<_Alloc, node> __rebind_n;
+ typedef typename __rebind_n::const_pointer node_const_pointer;
+ typedef typename __rebind_n::pointer node_pointer;
+
+ typedef typename traits_type::head head;
+ typedef rebind_traits<_Alloc, head> __rebind_h;
+ typedef typename __rebind_h::allocator_type head_allocator;
+ typedef typename __rebind_h::pointer head_pointer;
+
+ typedef typename traits_type::leaf leaf;
+ typedef rebind_traits<_Alloc, leaf> __rebind_l;
+ typedef typename __rebind_l::allocator_type leaf_allocator;
+ typedef typename __rebind_l::pointer leaf_pointer;
+ typedef typename __rebind_l::const_pointer leaf_const_pointer;
+
+ typedef typename traits_type::inode inode;
+ typedef typename inode::iterator inode_iterator;
+ typedef rebind_traits<_Alloc, inode> __rebind_in;
+ typedef typename __rebind_in::allocator_type inode_allocator;
+ typedef typename __rebind_in::pointer inode_pointer;
+ typedef typename __rebind_in::const_pointer inode_const_pointer;
+
+
+ /// Conditional deallocator.
+ class cond_dealtor
+ {
+ protected:
+ leaf_pointer m_p_nd;
+ bool m_no_action_dtor;
+ bool m_call_destructor;
- typedef
- typename Node_And_It_Traits::synth_e_access_traits
- synth_e_access_traits;
-
- typedef
- typename Allocator::template rebind<
- synth_e_access_traits>::other::const_pointer
- const_e_access_traits_pointer;
-
- typedef
- typename synth_e_access_traits::const_iterator
- const_e_iterator;
-
- typedef typename Node_And_It_Traits::node node;
-
- typedef
- typename Allocator::template rebind<
- node>::other::const_pointer
- const_node_pointer;
-
- typedef
- typename Allocator::template rebind<
- node>::other::pointer
- node_pointer;
-
- typedef typename Node_And_It_Traits::head head;
-
- typedef
- typename Allocator::template rebind<
- head>::other
- head_allocator;
-
- typedef typename head_allocator::pointer head_pointer;
-
- typedef typename Node_And_It_Traits::leaf leaf;
-
- typedef
- typename Allocator::template rebind<
- leaf>::other
- leaf_allocator;
-
- typedef typename leaf_allocator::const_pointer const_leaf_pointer;
-
- typedef typename leaf_allocator::pointer leaf_pointer;
-
- typedef typename Node_And_It_Traits::internal_node internal_node;
-
- typedef
- typename Allocator::template rebind<
- internal_node>::other
- internal_node_allocator;
-
- typedef
- typename internal_node_allocator::const_pointer
- const_internal_node_pointer;
-
- typedef
- typename internal_node_allocator::pointer
- internal_node_pointer;
-
- typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
-
-#include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp>
-
-#ifdef PB_DS_PAT_TRIE_DEBUG_
- typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
-#endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
-
-#include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp>
-
- typedef
- typename Node_And_It_Traits::null_node_update_pointer
- null_node_update_pointer;
-
- public:
- typedef pat_trie_tag container_category;
-
- typedef typename Allocator::size_type size_type;
-
- typedef typename Allocator::difference_type difference_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
- const_key_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
- const_key_reference;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
- mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
- const_mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
- mapped_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
- const_mapped_reference;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
- const_reference;
-
- typedef
- typename Node_And_It_Traits::const_iterator
- const_point_iterator;
-
- typedef typename Node_And_It_Traits::iterator point_iterator;
-
- typedef const_point_iterator const_iterator;
-
- typedef point_iterator iterator;
+ public:
+ cond_dealtor(leaf_pointer p_nd)
+ : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false)
+ { }
- typedef
- typename Node_And_It_Traits::const_reverse_iterator
- const_reverse_iterator;
+ void
+ set_no_action_dtor()
+ { m_no_action_dtor = true; }
- typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
+ void
+ set_call_destructor()
+ { m_call_destructor = true; }
- typedef
- typename Node_And_It_Traits::const_node_iterator
- const_node_iterator;
+ ~cond_dealtor()
+ {
+ if (m_no_action_dtor)
+ return;
- typedef typename Node_And_It_Traits::node_iterator node_iterator;
+ if (m_call_destructor)
+ m_p_nd->~leaf();
- typedef typename Node_And_It_Traits::e_access_traits e_access_traits;
+ s_leaf_allocator.deallocate(m_p_nd, 1);
+ }
+ };
- typedef typename Node_And_It_Traits::node_update node_update;
- typedef Allocator allocator;
+ /// Branch bag, for split-join.
+ class branch_bag
+ {
+ private:
+ typedef inode_pointer __inp;
+ typedef typename rebind_traits<_Alloc, __inp>::allocator_type
+ __rebind_inp;
+
+#ifdef _GLIBCXX_DEBUG
+ typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type;
+#else
+ typedef std::list<__inp, __rebind_inp> bag_type;
+#endif
+
+ bag_type m_bag;
+ public:
+ void
+ add_branch()
+ {
+ inode_pointer p_nd = s_inode_allocator.allocate(1);
+ __try
+ {
+ m_bag.push_back(p_nd);
+ }
+ __catch(...)
+ {
+ s_inode_allocator.deallocate(p_nd, 1);
+ __throw_exception_again;
+ }
+ }
+
+ inode_pointer
+ get_branch()
+ {
+ _GLIBCXX_DEBUG_ASSERT(!m_bag.empty());
+ inode_pointer p_nd = *m_bag.begin();
+ m_bag.pop_front();
+ return p_nd;
+ }
+
+ ~branch_bag()
+ {
+ while (!m_bag.empty())
+ {
+ inode_pointer p_nd = *m_bag.begin();
+ s_inode_allocator.deallocate(p_nd, 1);
+ m_bag.pop_front();
+ }
+ }
+
+ _GLIBCXX_NODISCARD inline bool
+ empty() const
+ { return m_bag.empty(); }
+ };
+
+#ifdef _GLIBCXX_DEBUG
+ typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
+#endif
+
+ typedef typename traits_type::null_node_update_pointer null_node_update_pointer;
public:
-
- PB_DS_CLASS_NAME();
-
- PB_DS_CLASS_NAME(const e_access_traits& r_e_access_traits);
-
- PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
+ typedef pat_trie_tag container_category;
+ typedef _Alloc allocator_type;
+ typedef typename _Alloc::size_type size_type;
+ typedef typename _Alloc::difference_type difference_type;
+
+ typedef typename traits_base::key_type key_type;
+ typedef typename traits_base::key_pointer key_pointer;
+ typedef typename traits_base::key_const_pointer key_const_pointer;
+ typedef typename traits_base::key_reference key_reference;
+ typedef typename traits_base::key_const_reference key_const_reference;
+ typedef typename traits_base::mapped_type mapped_type;
+ typedef typename traits_base::mapped_pointer mapped_pointer;
+ typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
+ typedef typename traits_base::mapped_reference mapped_reference;
+ typedef typename traits_base::mapped_const_reference mapped_const_reference;
+ typedef typename traits_base::value_type value_type;
+ typedef typename traits_base::pointer pointer;
+ typedef typename traits_base::const_pointer const_pointer;
+ typedef typename traits_base::reference reference;
+ typedef typename traits_base::const_reference const_reference;
+
+ typedef typename traits_type::access_traits access_traits;
+ typedef typename traits_type::const_iterator point_const_iterator;
+ typedef typename traits_type::iterator point_iterator;
+ typedef point_const_iterator const_iterator;
+ typedef point_iterator iterator;
+
+ typedef typename traits_type::reverse_iterator reverse_iterator;
+ typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
+ typedef typename traits_type::node_const_iterator node_const_iterator;
+ typedef typename traits_type::node_iterator node_iterator;
+ typedef typename traits_type::node_update node_update;
+
+ PB_DS_PAT_TRIE_NAME();
+
+ PB_DS_PAT_TRIE_NAME(const access_traits&);
+
+ PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&);
void
- swap(PB_DS_CLASS_C_DEC& other);
+ swap(PB_DS_CLASS_C_DEC&);
- ~PB_DS_CLASS_NAME();
+ ~PB_DS_PAT_TRIE_NAME();
- inline bool
+ _GLIBCXX_NODISCARD inline bool
empty() const;
inline size_type
inline size_type
max_size() const;
- e_access_traits&
- get_e_access_traits();
+ access_traits&
+ get_access_traits();
- const e_access_traits&
- get_e_access_traits() const;
+ const access_traits&
+ get_access_traits() const;
- node_update&
+ node_update&
get_node_update();
- const node_update&
+ const node_update&
get_node_update() const;
- inline std::pair<
- point_iterator,
- bool>
- insert(const_reference r_val);
+ inline std::pair<point_iterator, bool>
+ insert(const_reference);
inline mapped_reference
- operator[](const_key_reference r_key)
+ operator[](key_const_reference r_key)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
- return (insert(std::make_pair(
- r_key,
- mapped_type())).first->second);
-#else // #ifdef PB_DS_DATA_TRUE_INDICATOR
+ return insert(std::make_pair(r_key, mapped_type())).first->second;
+#else
insert(r_key);
-
- return (traits_base::s_null_mapped);
-#endif // #ifdef PB_DS_DATA_TRUE
+ return traits_base::s_null_type;
+#endif
}
inline point_iterator
- find(const_key_reference r_key);
+ find(key_const_reference);
- inline const_point_iterator
- find(const_key_reference r_key) const;
+ inline point_const_iterator
+ find(key_const_reference) const;
inline point_iterator
- lower_bound(const_key_reference r_key);
+ lower_bound(key_const_reference);
- inline const_point_iterator
- lower_bound(const_key_reference r_key) const;
+ inline point_const_iterator
+ lower_bound(key_const_reference) const;
inline point_iterator
- upper_bound(const_key_reference r_key);
+ upper_bound(key_const_reference);
- inline const_point_iterator
- upper_bound(const_key_reference r_key) const;
+ inline point_const_iterator
+ upper_bound(key_const_reference) const;
void
clear();
inline bool
- erase(const_key_reference r_key);
+ erase(key_const_reference);
inline const_iterator
- erase(const_iterator it);
+ erase(const_iterator);
#ifdef PB_DS_DATA_TRUE_INDICATOR
inline iterator
- erase(iterator it);
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+ erase(iterator);
+#endif
inline const_reverse_iterator
- erase(const_reverse_iterator it);
+ erase(const_reverse_iterator);
#ifdef PB_DS_DATA_TRUE_INDICATOR
inline reverse_iterator
- erase(reverse_iterator it);
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+ erase(reverse_iterator);
+#endif
template<typename Pred>
inline size_type
- erase_if(Pred pred);
+ erase_if(Pred);
void
- join(PB_DS_CLASS_C_DEC& other);
+ join(PB_DS_CLASS_C_DEC&);
void
- split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
+ split(key_const_reference, PB_DS_CLASS_C_DEC&);
inline iterator
begin();
inline const_reverse_iterator
rend() const;
- inline const_node_iterator
+ /// 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();
- inline const_node_iterator
+ /// 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();
#ifdef PB_DS_PAT_TRIE_TRACE_
-
void
trace() const;
-
-#endif // #ifdef PB_DS_PAT_TRIE_TRACE_
+#endif
protected:
-
template<typename It>
void
- copy_from_range(It first_it, It last_it);
+ copy_from_range(It, It);
void
- value_swap(PB_DS_CLASS_C_DEC& other);
+ value_swap(PB_DS_CLASS_C_DEC&);
node_pointer
- recursive_copy_node(const_node_pointer p_other_nd);
+ recursive_copy_node(node_const_pointer);
private:
-
void
initialize();
inline void
- apply_update(node_pointer p_nd, null_node_update_pointer);
+ apply_update(node_pointer, null_node_update_pointer);
template<typename Node_Update_>
inline void
- apply_update(node_pointer p_nd, Node_Update_* p_update);
+ apply_update(node_pointer, Node_Update_*);
bool
- join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag);
+ join_prep(PB_DS_CLASS_C_DEC&, branch_bag&);
void
- rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&);
void
- rec_join_prep(const_leaf_pointer p_l, const_leaf_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&);
void
- rec_join_prep(const_leaf_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&);
void
- rec_join_prep(const_internal_node_pointer p_l, const_leaf_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&);
void
- rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&);
node_pointer
- rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag);
+ rec_join(node_pointer, node_pointer, size_type, branch_bag&);
node_pointer
- rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join(leaf_pointer, leaf_pointer, branch_bag&);
node_pointer
- rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag);
+ rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&);
node_pointer
- rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag);
+ rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&);
node_pointer
- rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag);
+ rec_join(inode_pointer, inode_pointer, branch_bag&);
size_type
- keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r);
+ keys_diff_ind(typename access_traits::const_iterator,
+ typename access_traits::const_iterator,
+ typename access_traits::const_iterator,
+ typename access_traits::const_iterator);
- internal_node_pointer
- insert_branch(node_pointer p_left_nd, node_pointer p_right_nd, split_join_branch_bag& r_bag);
+ inode_pointer
+ insert_branch(node_pointer, node_pointer, branch_bag&);
void
- update_min_max_for_inserted_leaf(leaf_pointer p_l);
+ update_min_max_for_inserted_leaf(leaf_pointer);
void
- erase_leaf(leaf_pointer p_l);
+ erase_leaf(leaf_pointer);
inline void
- actual_erase_leaf(leaf_pointer p_lf);
+ actual_erase_leaf(leaf_pointer);
void
- clear_imp(node_pointer p_nd);
+ clear_imp(node_pointer);
void
- erase_fixup(internal_node_pointer p_nd);
+ erase_fixup(inode_pointer);
void
- update_min_max_for_erased_leaf(leaf_pointer p_l);
+ update_min_max_for_erased_leaf(leaf_pointer);
- static inline const_e_iterator
- pref_begin(const_node_pointer p_nd);
+ static inline a_const_iterator
+ pref_begin(node_const_pointer);
- static inline const_e_iterator
- pref_end(const_node_pointer p_nd);
+ static inline a_const_iterator
+ pref_end(node_const_pointer);
inline node_pointer
- find_imp(const_key_reference r_key);
+ find_imp(key_const_reference);
inline node_pointer
- lower_bound_imp(const_key_reference r_key);
+ lower_bound_imp(key_const_reference);
inline node_pointer
- upper_bound_imp(const_key_reference r_key);
+ upper_bound_imp(key_const_reference);
- inline static const_leaf_pointer
- leftmost_descendant(const_node_pointer p_nd);
+ inline static leaf_const_pointer
+ leftmost_descendant(node_const_pointer);
inline static leaf_pointer
- leftmost_descendant(node_pointer p_nd);
+ leftmost_descendant(node_pointer);
- inline static const_leaf_pointer
- rightmost_descendant(const_node_pointer p_nd);
+ inline static leaf_const_pointer
+ rightmost_descendant(node_const_pointer);
inline static leaf_pointer
- rightmost_descendant(node_pointer p_nd);
-
-#ifdef PB_DS_PAT_TRIE_DEBUG_
+ rightmost_descendant(node_pointer);
+#ifdef _GLIBCXX_DEBUG
void
- assert_valid() const;
+ assert_valid(const char*, int) const;
void
- assert_iterators() const;
+ assert_iterators(const char*, int) const;
void
- assert_reverse_iterators() const;
+ assert_reverse_iterators(const char*, int) const;
static size_type
- recursive_count_leafs(const_node_pointer p_nd);
-
-#endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
+ recursive_count_leafs(node_const_pointer, const char*, int);
+#endif
#ifdef PB_DS_PAT_TRIE_TRACE_
-
static void
- trace_node(const_node_pointer p_nd, size_type level);
+ trace_node(node_const_pointer, size_type);
template<typename Metadata_>
static void
- trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>);
+ trace_node_metadata(node_const_pointer, type_to_type<Metadata_>);
static void
- trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>);
-
-#endif // #ifdef PB_DS_PAT_TRIE_TRACE_
+ trace_node_metadata(node_const_pointer, type_to_type<null_type>);
+#endif
leaf_pointer
- split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag);
+ split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&);
node_pointer
- rec_split(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag);
+ rec_split(node_pointer, a_const_iterator, a_const_iterator,
+ PB_DS_CLASS_C_DEC&, branch_bag&);
void
- split_insert_branch(size_type e_ind, const_e_iterator b_it, typename internal_node::iterator child_b_it, size_type num_children, split_join_branch_bag& r_bag);
+ split_insert_branch(size_type, a_const_iterator, inode_iterator,
+ size_type, branch_bag&);
- private:
- static head_allocator s_head_allocator;
+ static head_allocator s_head_allocator;
+ static inode_allocator s_inode_allocator;
+ static leaf_allocator s_leaf_allocator;
- static internal_node_allocator s_internal_node_allocator;
-
- static leaf_allocator s_leaf_allocator;
+ head_pointer m_p_head;
+ size_type m_size;
+ };
- head_pointer m_p_head;
+#define PB_DS_ASSERT_NODE_VALID(X) \
+ _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)
- size_type m_size;
- };
+#define PB_DS_RECURSIVE_COUNT_LEAFS(X) \
+ recursive_count_leafs(X, __FILE__, __LINE__)
#include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp>
+#undef PB_DS_RECURSIVE_COUNT_LEAFS
+#undef PB_DS_ASSERT_NODE_VALID
#undef PB_DS_CLASS_C_DEC
-
#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_NAME
-
-#undef PB_DS_TYPES_TRAITS_C_DEC
-
-#undef PB_DS_MAP_DEBUG_BASE_C_DEC
-
-#undef PB_DS_V2F
-#undef PB_DS_EP2VP
-#undef PB_DS_V2S
-
-#undef PB_DS_DBG_ASSERT
-#undef PB_DS_DBG_VERIFY
-#undef PB_DS_DBG_ONLY
-
-#undef PB_DS_STATIC_ASSERT
-
+#undef PB_DS_PAT_TRIE_NAME
+#undef PB_DS_PAT_TRIE_TRAITS_BASE
+#undef PB_DS_DEBUG_MAP_BASE_C_DEC
} // namespace detail
-} // namespace pb_ds
+} // namespace __gnu_pbds
projects / thirdparty / gcc.git / blobdiff