41 #ifndef PB_DS_PAT_TRIE_BASE
42 #define PB_DS_PAT_TRIE_BASE
66 template<
typename Metadata,
typename _Alloc>
69 typedef Metadata metadata_type;
70 typedef _Alloc allocator_type;
71 typedef typename _Alloc::template rebind<Metadata> __rebind_m;
72 typedef typename __rebind_m::other::const_reference const_reference;
76 {
return m_metadata; }
78 metadata_type m_metadata;
82 template<
typename _Alloc>
86 typedef _Alloc allocator_type;
91 template<
typename _ATraits,
typename Metadata>
96 typedef typename Metadata::allocator_type _Alloc;
99 typedef _Alloc allocator_type;
100 typedef _ATraits access_traits;
101 typedef typename _ATraits::type_traits type_traits;
102 typedef typename _Alloc::template rebind<_Node_base> __rebind_n;
103 typedef typename __rebind_n::other::pointer node_pointer;
105 node_pointer m_p_parent;
111 typedef typename _Alloc::template rebind<_ATraits> __rebind_at;
112 typedef typename __rebind_at::other::const_pointer a_const_pointer;
113 typedef typename _ATraits::const_iterator a_const_iterator;
115 #ifdef _GLIBCXX_DEBUG
119 assert_valid(a_const_pointer p_traits,
120 const char* __file,
int __line)
const
121 { assert_valid_imp(p_traits, __file, __line); }
123 virtual node_debug_info
124 assert_valid_imp(a_const_pointer,
const char*,
int)
const = 0;
130 template<
typename _ATraits,
typename Metadata>
135 typedef typename base_type::type_traits type_traits;
136 typedef typename base_type::node_pointer node_pointer;
138 node_pointer m_p_min;
139 node_pointer m_p_max;
141 _Head() : base_type(head_node) { }
143 #ifdef _GLIBCXX_DEBUG
144 typedef typename base_type::node_debug_info node_debug_info;
145 typedef typename base_type::a_const_pointer a_const_pointer;
147 virtual node_debug_info
148 assert_valid_imp(a_const_pointer,
const char* __file,
int __line)
const
151 _M_message(
"Assertion from %1;:%2;")
152 ._M_string(__FILE__)._M_integer(__LINE__),
154 return node_debug_info();
161 template<
typename _ATraits,
typename Metadata>
166 typedef typename base_type::type_traits type_traits;
167 typedef typename type_traits::value_type value_type;
168 typedef typename type_traits::reference reference;
169 typedef typename type_traits::const_reference const_reference;
177 _Leaf(const_reference other)
178 : base_type(leaf_node), m_value(other) { }
188 #ifdef _GLIBCXX_DEBUG
189 typedef typename base_type::node_debug_info node_debug_info;
190 typedef typename base_type::a_const_pointer a_const_pointer;
192 virtual node_debug_info
193 assert_valid_imp(a_const_pointer p_traits,
194 const char* __file,
int __line)
const
196 PB_DS_DEBUG_VERIFY(base_type::m_type == leaf_node);
198 const_reference r_val = value();
199 return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)),
200 p_traits->end(p_traits->extract_key(r_val)));
210 template<
typename _ATraits,
typename Metadata>
215 typedef typename base_type::type_traits type_traits;
216 typedef typename base_type::access_traits access_traits;
217 typedef typename type_traits::value_type value_type;
218 typedef typename base_type::allocator_type _Alloc;
219 typedef _Alloc allocator_type;
220 typedef typename _Alloc::size_type size_type;
223 typedef typename base_type::a_const_pointer a_const_pointer;
224 typedef typename base_type::a_const_iterator a_const_iterator;
226 typedef typename base_type::node_pointer node_pointer;
227 typedef typename _Alloc::template rebind<base_type> __rebind_n;
228 typedef typename __rebind_n::other::const_pointer node_const_pointer;
231 typedef typename _Alloc::template rebind<leaf>::other __rebind_l;
232 typedef typename __rebind_l::pointer leaf_pointer;
233 typedef typename __rebind_l::const_pointer leaf_const_pointer;
235 typedef typename _Alloc::template rebind<_Inode>::other __rebind_in;
236 typedef typename __rebind_in::pointer inode_pointer;
237 typedef typename __rebind_in::const_pointer inode_const_pointer;
240 get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer)
const;
243 typedef typename _Alloc::template rebind<node_pointer>::other __rebind_np;
244 typedef typename __rebind_np::pointer node_pointer_pointer;
245 typedef typename __rebind_np::reference node_pointer_reference;
249 arr_size = _ATraits::max_size + 1
251 PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2);
257 node_pointer_pointer m_p_p_cur;
258 node_pointer_pointer m_p_p_end;
261 typedef typename _Alloc::difference_type difference_type;
262 typedef node_pointer value_type;
263 typedef node_pointer_pointer pointer;
264 typedef node_pointer_reference reference;
267 node_pointer_pointer p_p_end = 0)
268 : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end)
273 {
return m_p_p_cur == other.m_p_p_cur; }
277 {
return m_p_p_cur != other.m_p_p_cur; }
284 while (m_p_p_cur != m_p_p_end && *m_p_p_cur == 0);
296 const node_pointer_pointer
299 _GLIBCXX_DEBUG_ONLY(assert_referencible();)
306 _GLIBCXX_DEBUG_ONLY(assert_referencible();)
311 #ifdef _GLIBCXX_DEBUG
313 assert_referencible()
const
314 { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end && *m_p_p_cur != 0); }
324 typedef typename _Alloc::difference_type difference_type;
325 typedef node_pointer value_type;
326 typedef node_pointer_pointer pointer;
327 typedef node_pointer_reference reference;
330 iterator(node_pointer_pointer p_p_cur = 0,
331 node_pointer_pointer p_p_end = 0)
335 operator==(
const iterator& other)
const
336 {
return const_iterator::m_p_p_cur == other.m_p_p_cur; }
339 operator!=(
const iterator& other)
const
340 {
return const_iterator::m_p_p_cur != other.m_p_p_cur; }
345 const_iterator::operator++();
360 _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();)
361 return const_iterator::m_p_p_cur;
367 _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();)
368 return *const_iterator::m_p_p_cur;
373 _Inode(size_type,
const a_const_iterator);
376 update_prefixes(a_const_pointer);
391 get_child_node(a_const_iterator, a_const_iterator, a_const_pointer);
393 inline node_const_pointer
394 get_child_node(a_const_iterator, a_const_iterator, a_const_pointer)
const;
397 get_child_it(a_const_iterator, a_const_iterator, a_const_pointer);
400 get_lower_bound_child_node(a_const_iterator, a_const_iterator,
401 size_type, a_const_pointer);
404 add_child(node_pointer, a_const_iterator, a_const_iterator,
407 inline node_const_pointer
408 get_join_child(node_const_pointer, a_const_pointer)
const;
411 get_join_child(node_pointer, a_const_pointer);
414 remove_child(node_pointer);
420 replace_child(node_pointer, a_const_iterator, a_const_iterator,
423 inline a_const_iterator
426 inline a_const_iterator
430 should_be_mine(a_const_iterator, a_const_iterator, size_type,
431 a_const_pointer)
const;
434 leftmost_descendant();
437 leftmost_descendant()
const;
440 rightmost_descendant();
443 rightmost_descendant()
const;
445 #ifdef _GLIBCXX_DEBUG
446 typedef typename base_type::node_debug_info node_debug_info;
448 virtual node_debug_info
449 assert_valid_imp(a_const_pointer,
const char*,
int)
const;
460 get_begin_pos()
const;
462 static __rebind_l s_leaf_alloc;
463 static __rebind_in s_inode_alloc;
465 const size_type m_e_ind;
466 a_const_iterator m_pref_b_it;
467 a_const_iterator m_pref_e_it;
468 node_pointer m_a_p_children[arr_size];
471 #define PB_DS_CONST_IT_C_DEC \
472 _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
474 #define PB_DS_CONST_ODIR_IT_C_DEC \
475 _CIter<Node, Leaf, Head, Inode, !Is_Forward_Iterator>
477 #define PB_DS_IT_C_DEC \
478 _Iter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
480 #define PB_DS_ODIR_IT_C_DEC \
481 _Iter<Node, Leaf, Head, Inode, !Is_Forward_Iterator>
485 template<
typename Node,
typename Leaf,
typename Head,
typename Inode,
486 bool Is_Forward_Iterator>
491 typedef typename Node::allocator_type allocator_type;
492 typedef typename Node::type_traits type_traits;
495 typedef typename allocator_type::difference_type difference_type;
496 typedef typename type_traits::value_type value_type;
497 typedef typename type_traits::pointer pointer;
498 typedef typename type_traits::reference reference;
499 typedef typename type_traits::const_pointer const_pointer;
500 typedef typename type_traits::const_reference const_reference;
502 typedef allocator_type _Alloc;
503 typedef typename _Alloc::template rebind<Node> __rebind_n;
504 typedef typename __rebind_n::other::pointer node_pointer;
505 typedef typename _Alloc::template rebind<Leaf> __rebind_l;
506 typedef typename __rebind_l::other::pointer leaf_pointer;
507 typedef typename __rebind_l::other::const_pointer leaf_const_pointer;
508 typedef typename _Alloc::template rebind<Head> __rebind_h;
509 typedef typename __rebind_h::other::pointer head_pointer;
511 typedef typename _Alloc::template rebind<Inode> __rebind_in;
512 typedef typename __rebind_in::other::pointer inode_pointer;
513 typedef typename Inode::iterator inode_iterator;
517 _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd)
520 _CIter(
const PB_DS_CONST_ODIR_IT_C_DEC& other)
521 : m_p_nd(other.m_p_nd)
525 operator=(
const _CIter& other)
527 m_p_nd = other.m_p_nd;
532 operator=(
const PB_DS_CONST_ODIR_IT_C_DEC& other)
534 m_p_nd = other.m_p_nd;
541 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
542 return &
static_cast<leaf_pointer
>(m_p_nd)->value();
548 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node);
549 return static_cast<leaf_pointer
>(m_p_nd)->value();
553 operator==(
const _CIter& other)
const
554 {
return m_p_nd == other.m_p_nd; }
557 operator==(
const PB_DS_CONST_ODIR_IT_C_DEC& other)
const
558 {
return m_p_nd == other.m_p_nd; }
561 operator!=(
const _CIter& other)
const
562 {
return m_p_nd != other.m_p_nd; }
565 operator!=(
const PB_DS_CONST_ODIR_IT_C_DEC& other)
const
566 {
return m_p_nd != other.m_p_nd; }
571 inc(integral_constant<int, Is_Forward_Iterator>());
586 dec(integral_constant<int, Is_Forward_Iterator>());
606 if (m_p_nd->m_type == head_node)
608 m_p_nd =
static_cast<head_pointer
>(m_p_nd)->m_p_min;
612 node_pointer p_y = m_p_nd->m_p_parent;
613 while (p_y->m_type != head_node && get_larger_sibling(m_p_nd) == 0)
616 p_y = p_y->m_p_parent;
619 if (p_y->m_type == head_node)
624 m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
634 if (m_p_nd->m_type == head_node)
636 m_p_nd =
static_cast<head_pointer
>(m_p_nd)->m_p_max;
640 node_pointer p_y = m_p_nd->m_p_parent;
641 while (p_y->m_type != head_node && get_smaller_sibling(m_p_nd) == 0)
644 p_y = p_y->m_p_parent;
647 if (p_y->m_type == head_node)
652 m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
656 get_larger_sibling(node_pointer p_nd)
658 inode_pointer p_parent =
static_cast<inode_pointer
>(p_nd->m_p_parent);
660 inode_iterator it = p_parent->begin();
664 inode_iterator next_it = it;
666 return (next_it == p_parent->end())? 0 : *next_it;
670 get_smaller_sibling(node_pointer p_nd)
672 inode_pointer p_parent =
static_cast<inode_pointer
>(p_nd->m_p_parent);
674 inode_iterator it = p_parent->begin();
678 inode_iterator prev_it;
688 _GLIBCXX_DEBUG_ASSERT(
false);
693 leftmost_descendant(node_pointer p_nd)
695 if (p_nd->m_type == leaf_node)
696 return static_cast<leaf_pointer
>(p_nd);
697 return static_cast<inode_pointer
>(p_nd)->leftmost_descendant();
701 rightmost_descendant(node_pointer p_nd)
703 if (p_nd->m_type == leaf_node)
704 return static_cast<leaf_pointer
>(p_nd);
705 return static_cast<inode_pointer
>(p_nd)->rightmost_descendant();
711 template<
typename Node,
typename Leaf,
typename Head,
typename Inode,
712 bool Is_Forward_Iterator>
714 :
public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator>
719 typedef typename base_type::allocator_type allocator_type;
720 typedef typename base_type::type_traits type_traits;
721 typedef typename type_traits::value_type value_type;
722 typedef typename type_traits::pointer pointer;
723 typedef typename type_traits::reference reference;
725 typedef typename base_type::node_pointer node_pointer;
726 typedef typename base_type::leaf_pointer leaf_pointer;
727 typedef typename base_type::leaf_const_pointer leaf_const_pointer;
728 typedef typename base_type::head_pointer head_pointer;
729 typedef typename base_type::inode_pointer inode_pointer;
731 _Iter(node_pointer p_nd = 0)
732 : base_type(p_nd) { }
734 _Iter(
const PB_DS_ODIR_IT_C_DEC& other)
735 : base_type(other.m_p_nd) { }
738 operator=(
const _Iter& other)
740 base_type::m_p_nd = other.m_p_nd;
745 operator=(
const PB_DS_ODIR_IT_C_DEC& other)
747 base_type::m_p_nd = other.m_p_nd;
754 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
755 return &
static_cast<leaf_pointer
>(base_type::m_p_nd)->value();
761 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node);
762 return static_cast<leaf_pointer
>(base_type::m_p_nd)->value();
768 base_type::operator++();
775 _Iter ret(base_type::m_p_nd);
783 base_type::operator--();
790 _Iter ret(base_type::m_p_nd);
796 #undef PB_DS_CONST_ODIR_IT_C_DEC
797 #undef PB_DS_ODIR_IT_C_DEC
800 #define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \
801 _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
803 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \
804 _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc>
807 template<
typename Node,
817 typedef typename _Alloc::template rebind<Node> __rebind_n;
818 typedef typename __rebind_n::other::pointer node_pointer;
820 typedef typename _Alloc::template rebind<Leaf> __rebind_l;
821 typedef typename __rebind_l::other::pointer leaf_pointer;
822 typedef typename __rebind_l::other::const_pointer leaf_const_pointer;
824 typedef typename _Alloc::template rebind<Inode> __rebind_in;
825 typedef typename __rebind_in::other::pointer inode_pointer;
826 typedef typename __rebind_in::other::const_pointer inode_const_pointer;
828 typedef typename Node::a_const_pointer a_const_pointer;
829 typedef typename Node::a_const_iterator a_const_iterator;
835 if (m_p_nd->m_type == leaf_node)
837 leaf_const_pointer lcp =
static_cast<leaf_const_pointer
>(m_p_nd);
838 return m_p_traits->begin(m_p_traits->extract_key(lcp->value()));
840 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
841 return static_cast<inode_const_pointer
>(m_p_nd)->pref_b_it();
847 if (m_p_nd->m_type == leaf_node)
849 leaf_const_pointer lcp =
static_cast<leaf_const_pointer
>(m_p_nd);
850 return m_p_traits->end(m_p_traits->extract_key(lcp->value()));
852 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
853 return static_cast<inode_const_pointer
>(m_p_nd)->pref_e_it();
859 typedef typename _Alloc::size_type size_type;
861 typedef _CIterator value_type;
862 typedef value_type reference;
863 typedef value_type const_reference;
869 typedef typename _Alloc::template rebind<metadata_type>
__rebind_m;
870 typedef typename __rebind_m::other __rebind_ma;
871 typedef typename __rebind_ma::const_reference metadata_const_reference;
874 _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
875 : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
889 return _CIterator(m_p_nd);
893 metadata_const_reference
895 {
return m_p_nd->get_metadata(); }
901 if (m_p_nd->m_type == leaf_node)
903 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
904 inode_pointer inp =
static_cast<inode_pointer
>(m_p_nd);
913 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node);
914 inode_pointer inp =
static_cast<inode_pointer
>(m_p_nd);
915 typename Inode::iterator it = inp->begin();
923 {
return m_p_nd == other.m_p_nd; }
928 {
return m_p_nd != other.m_p_nd; }
931 a_const_pointer m_p_traits;
936 template<
typename Node,
944 :
public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc>
949 typedef typename _Alloc::template rebind<Node> __rebind_n;
950 typedef typename __rebind_n::other::pointer node_pointer;
951 typedef typename base_type::inode_pointer inode_pointer;
952 typedef typename base_type::a_const_pointer a_const_pointer;
953 typedef Iterator iterator;
956 typedef typename base_type::size_type size_type;
958 typedef Iterator value_type;
959 typedef value_type reference;
960 typedef value_type const_reference;
962 _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
963 : base_type(p_nd, p_traits)
971 return iterator(base_type::m_p_nd);
978 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node);
980 typename Inode::iterator it =
981 static_cast<inode_pointer
>(base_type::m_p_nd)->
begin();
984 return _Node_iter(*it, base_type::m_p_traits);
990 #define PB_DS_CLASS_T_DEC \
991 template<typename _ATraits, typename Metadata>
993 #define PB_DS_CLASS_C_DEC \
994 pat_trie_base::_Inode<_ATraits, Metadata>
997 typename PB_DS_CLASS_C_DEC::__rebind_l
998 PB_DS_CLASS_C_DEC::s_leaf_alloc;
1001 typename PB_DS_CLASS_C_DEC::__rebind_in
1002 PB_DS_CLASS_C_DEC::s_inode_alloc;
1005 inline typename PB_DS_CLASS_C_DEC::size_type
1007 get_pref_pos(a_const_iterator b_it, a_const_iterator e_it,
1008 a_const_pointer p_traits)
const
1010 if (static_cast<std::size_t>(
std::distance(b_it, e_it)) <= m_e_ind)
1013 return 1 + p_traits->e_pos(*b_it);
1018 _Inode(size_type len,
const a_const_iterator it)
1019 : base_type(i_node), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it)
1022 std::fill(m_a_p_children, m_a_p_children + arr_size,
1023 static_cast<node_pointer>(0));
1029 update_prefixes(a_const_pointer p_traits)
1031 node_pointer p_first = *
begin();
1032 if (p_first->m_type == leaf_node)
1034 leaf_const_pointer p =
static_cast<leaf_const_pointer
>(p_first);
1035 m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value()));
1039 inode_pointer p =
static_cast<inode_pointer
>(p_first);
1040 _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node);
1041 m_pref_b_it = p->pref_b_it();
1043 m_pref_e_it = m_pref_b_it;
1048 typename PB_DS_CLASS_C_DEC::const_iterator
1052 typedef node_pointer_pointer pointer_type;
1053 pointer_type p =
const_cast<pointer_type
>(m_a_p_children);
1054 return const_iterator(p + get_begin_pos(), p + arr_size);
1058 typename PB_DS_CLASS_C_DEC::iterator
1062 return iterator(m_a_p_children + get_begin_pos(),
1063 m_a_p_children + arr_size);
1067 typename PB_DS_CLASS_C_DEC::const_iterator
1071 typedef node_pointer_pointer pointer_type;
1072 pointer_type p =
const_cast<pointer_type
>(m_a_p_children) + arr_size;
1073 return const_iterator(p, p);
1077 typename PB_DS_CLASS_C_DEC::iterator
1080 {
return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }
1083 inline typename PB_DS_CLASS_C_DEC::node_pointer
1085 get_child_node(a_const_iterator b_it, a_const_iterator e_it,
1086 a_const_pointer p_traits)
1088 const size_type i = get_pref_pos(b_it, e_it, p_traits);
1089 _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1090 return m_a_p_children[i];
1094 inline typename PB_DS_CLASS_C_DEC::iterator
1096 get_child_it(a_const_iterator b_it, a_const_iterator e_it,
1097 a_const_pointer p_traits)
1099 const size_type i = get_pref_pos(b_it, e_it, p_traits);
1100 _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1101 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0);
1102 return iterator(m_a_p_children + i, m_a_p_children + i);
1106 inline typename PB_DS_CLASS_C_DEC::node_const_pointer
1108 get_child_node(a_const_iterator b_it, a_const_iterator e_it,
1109 a_const_pointer p_traits)
const
1110 {
return const_cast<node_pointer
>(get_child_node(b_it, e_it, p_traits)); }
1113 typename PB_DS_CLASS_C_DEC::node_pointer
1115 get_lower_bound_child_node(a_const_iterator b_it, a_const_iterator e_it,
1116 size_type checked_ind,
1117 a_const_pointer p_traits)
1119 if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
1121 if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it,
1123 return leftmost_descendant();
1124 return rightmost_descendant();
1127 size_type i = get_pref_pos(b_it, e_it, p_traits);
1128 _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1130 if (m_a_p_children[i] != 0)
1131 return m_a_p_children[i];
1133 while (++i < arr_size)
1134 if (m_a_p_children[i] != 0)
1136 const node_type& __nt = m_a_p_children[i]->m_type;
1137 node_pointer ret = m_a_p_children[i];
1139 if (__nt == leaf_node)
1142 _GLIBCXX_DEBUG_ASSERT(__nt == i_node);
1143 inode_pointer inp =
static_cast<inode_pointer
>(ret);
1144 return inp->leftmost_descendant();
1147 return rightmost_descendant();
1151 inline typename PB_DS_CLASS_C_DEC::node_pointer
1153 add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it,
1154 a_const_pointer p_traits)
1156 const size_type i = get_pref_pos(b_it, e_it, p_traits);
1157 _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1158 if (m_a_p_children[i] == 0)
1160 m_a_p_children[i] = p_nd;
1161 p_nd->m_p_parent =
this;
1164 return m_a_p_children[i];
1168 typename PB_DS_CLASS_C_DEC::node_const_pointer
1170 get_join_child(node_const_pointer p_nd,
1171 a_const_pointer p_tr)
const
1173 node_pointer p =
const_cast<node_pointer
>(p_nd);
1174 return const_cast<inode_pointer
>(
this)->get_join_child(p, p_tr);
1178 typename PB_DS_CLASS_C_DEC::node_pointer
1180 get_join_child(node_pointer p_nd, a_const_pointer p_traits)
1183 a_const_iterator b_it;
1184 a_const_iterator e_it;
1185 if (p_nd->m_type == leaf_node)
1187 leaf_const_pointer p =
static_cast<leaf_const_pointer
>(p_nd);
1189 typedef typename type_traits::key_const_reference kcr;
1190 kcr r_key = access_traits::extract_key(p->value());
1191 b_it = p_traits->begin(r_key);
1192 e_it = p_traits->end(r_key);
1196 b_it =
static_cast<inode_pointer
>(p_nd)->pref_b_it();
1197 e_it =
static_cast<inode_pointer
>(p_nd)->pref_e_it();
1199 i = get_pref_pos(b_it, e_it, p_traits);
1200 _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1201 return m_a_p_children[i];
1207 remove_child(node_pointer p_nd)
1210 for (; i < arr_size; ++i)
1211 if (m_a_p_children[i] == p_nd)
1213 m_a_p_children[i] = 0;
1216 _GLIBCXX_DEBUG_ASSERT(i != arr_size);
1222 remove_child(iterator it)
1223 { *it.m_p_p_cur = 0; }
1228 replace_child(node_pointer p_nd, a_const_iterator b_it,
1229 a_const_iterator e_it,
1230 a_const_pointer p_traits)
1232 const size_type i = get_pref_pos(b_it, e_it, p_traits);
1233 _GLIBCXX_DEBUG_ASSERT(i < arr_size);
1234 m_a_p_children[i] = p_nd;
1235 p_nd->m_p_parent =
this;
1239 inline typename PB_DS_CLASS_C_DEC::a_const_iterator
1242 {
return m_pref_b_it; }
1245 inline typename PB_DS_CLASS_C_DEC::a_const_iterator
1248 {
return m_pref_e_it; }
1253 should_be_mine(a_const_iterator b_it, a_const_iterator e_it,
1254 size_type checked_ind,
1255 a_const_pointer p_traits)
const
1261 if (num_es < m_e_ind)
1264 a_const_iterator key_b_it = b_it;
1266 a_const_iterator key_e_it = b_it;
1269 a_const_iterator value_b_it = m_pref_b_it;
1271 a_const_iterator value_e_it = m_pref_b_it;
1274 return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it,
1279 typename PB_DS_CLASS_C_DEC::leaf_pointer
1281 leftmost_descendant()
1283 node_pointer p_pot = *
begin();
1284 if (p_pot->m_type == leaf_node)
1285 return (static_cast<leaf_pointer>(p_pot));
1286 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
1287 return static_cast<inode_pointer
>(p_pot)->leftmost_descendant();
1291 typename PB_DS_CLASS_C_DEC::leaf_const_pointer
1293 leftmost_descendant()
const
1294 {
return const_cast<inode_pointer
>(
this)->leftmost_descendant(); }
1297 typename PB_DS_CLASS_C_DEC::leaf_pointer
1299 rightmost_descendant()
1302 _GLIBCXX_DEBUG_ASSERT(num_children >= 2);
1304 iterator it =
begin();
1306 node_pointer p_pot =* it;
1307 if (p_pot->m_type == leaf_node)
1308 return static_cast<leaf_pointer
>(p_pot);
1309 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node);
1310 return static_cast<inode_pointer
>(p_pot)->rightmost_descendant();
1314 typename PB_DS_CLASS_C_DEC::leaf_const_pointer
1316 rightmost_descendant()
const
1317 {
return const_cast<inode_pointer
>(
this)->rightmost_descendant(); }
1320 typename PB_DS_CLASS_C_DEC::size_type
1322 get_begin_pos()
const
1325 for (; i < arr_size && m_a_p_children[i] == 0; ++i)
1330 #ifdef _GLIBCXX_DEBUG
1332 typename PB_DS_CLASS_C_DEC::node_debug_info
1334 assert_valid_imp(a_const_pointer p_traits,
1335 const char* __file,
int __line)
const
1337 PB_DS_DEBUG_VERIFY(base_type::m_type == i_node);
1338 PB_DS_DEBUG_VERIFY(static_cast<size_type>(
std::distance(pref_b_it(), pref_e_it())) == m_e_ind);
1341 for (
typename _Inode::const_iterator it =
begin(); it !=
end(); ++it)
1343 node_const_pointer p_nd = *it;
1344 PB_DS_DEBUG_VERIFY(p_nd->m_p_parent ==
this);
1345 node_debug_info child_ret = p_nd->assert_valid_imp(p_traits,
1348 PB_DS_DEBUG_VERIFY(static_cast<size_type>(
std::distance(child_ret.first, child_ret.second)) >= m_e_ind);
1349 PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
1350 PB_DS_DEBUG_VERIFY(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast<size_type>(it.m_p_p_cur - m_a_p_children));
1356 #undef PB_DS_CLASS_T_DEC
1357 #undef PB_DS_CLASS_C_DEC
Leaf node for PATRICIA tree.
Bidirectional iterators support a superset of forward iterator operations.
Head node for PATRICIA tree.
const_reference operator*() const
Const access; returns the __const iterator* associated with the current leaf.
_Node_iter get_child(size_type i) const
Returns a node __iterator to the corresponding node's i-th child.
node_type
Three types of nodes.
_Alloc::template rebind< metadata_type > __rebind_m
Const metadata reference type.
reference operator*() const
Access; returns the iterator* associated with the current leaf.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Node::metadata_type metadata_type
Metadata type.
Forward iterators support a superset of input iterator operations.
bool operator==(const _Node_citer &other) const
Compares content to a different iterator object.
Struct holding two objects of arbitrary type.
bool operator!=(const _Node_citer &other) const
Compares content (negatively) to a different iterator object.
GNU extensions for policy-based data structures for public use.
metadata_const_reference get_metadata() const
Metadata access.
void trivial_iterator_difference_type
Prohibit moving trivial iterators.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
A trivial iterator tag. Signifies that the iterators has none of std::iterators's movement abilities...
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_Node_citer get_child(size_type i) const
Returns a __const node __iterator to the corresponding node's i-th child.
std::pair< a_const_iterator, a_const_iterator > valid_prefix() const
Subtree valid prefix.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
size_type num_children() const
Returns the number of children in the corresponding node.
Base type for PATRICIA trees.
Internal node type, PATRICIA tree.
Metadata base primary template.
Represents no type, or absence of type, for template tricks.
#define _GLIBCXX_DEBUG_VERIFY_AT(_Condition, _ErrorMessage, _File, _Line)