pat_trie_.hpp File Reference

#include <iterator>
#include <utility>
#include <algorithm>
#include <functional>
#include <assert.h>
#include <list>
#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>
#include <debug/debug.h>
#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_/insert_join_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp>
#include <ext/pb_ds/detail/pat_trie_/debug_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>

Go to the source code of this file.

Classes
class	__gnu_pbds::detail::PB_DS_PAT_TRIE_NAME< Key, Mapped, Node_And_It_Traits, _Alloc >
	PATRICIA trie.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. More...
class	__gnu_pbds::detail::PB_DS_PAT_TRIE_NAME< Key, Mapped, Node_And_It_Traits, _Alloc >::cond_dealtor
	Conditional deallocator. More...
class	__gnu_pbds::detail::PB_DS_PAT_TRIE_NAME< Key, Mapped, Node_And_It_Traits, _Alloc >::branch_bag
	Branch bag, for split-join. More...

Namespaces
	__gnu_pbds
	GNU extensions for policy-based data structures for public use.
	__gnu_pbds::detail

Macros
#define	PB_DS_CLASS_T_DEC
#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>
#define	PB_DS_ASSERT_NODE_VALID(X)   _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)
#define	PB_DS_RECURSIVE_COUNT_LEAFS(X)   recursive_count_leafs(X, __FILE__, __LINE__)

Detailed Description

Contains an implementation class for a patricia tree.

Macro Definition Documentation

#define PB_DS_ASSERT_NODE_VALID

(

X

)

_GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)

#define PB_DS_CLASS_C_DEC   PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc>

#define PB_DS_CLASS_T_DEC

Value:

template<typename Key, typename Mapped, typename Node_And_It_Traits, \
         typename _Alloc>

#define PB_DS_PAT_TRIE_TRAITS_BASE   types_traits<Key, Mapped, _Alloc, false>

#define PB_DS_RECURSIVE_COUNT_LEAFS

(

X

)

recursive_count_leafs(X, __FILE__, __LINE__)