3 // Copyright (C) 2005-2015 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
37 * @file pat_trie_/pat_trie_base.hpp
38 * Contains the base class for a patricia tree.
41 #ifndef PB_DS_PAT_TRIE_BASE
42 #define PB_DS_PAT_TRIE_BASE
44 #include <debug/debug.h>
50 /// Base type for PATRICIA trees.
54 * @brief Three types of nodes.
56 * i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head.
65 /// Metadata base primary template.
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;
81 /// Specialization for null metadata.
82 template<typename _Alloc>
83 struct _Metadata<null_type, _Alloc>
85 typedef null_type metadata_type;
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;
106 const node_type m_type;
108 _Node_base(node_type type) : m_type(type)
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
116 typedef std::pair<a_const_iterator, a_const_iterator> node_debug_info;
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;
129 /// Head node for PATRICIA tree.
130 template<typename _ATraits, typename Metadata>
132 : public _Node_base<_ATraits, Metadata>
134 typedef _Node_base<_ATraits, Metadata> base_type;
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
150 _GLIBCXX_DEBUG_VERIFY_AT(false,
151 _M_message("Assertion from %1;:%2;")
152 ._M_string(__FILE__)._M_integer(__LINE__),
154 return node_debug_info();
160 /// Leaf node for PATRICIA tree.
161 template<typename _ATraits, typename Metadata>
163 : public _Node_base<_ATraits, Metadata>
165 typedef _Node_base<_ATraits, Metadata> base_type;
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)));
209 /// Internal node type, PATRICIA tree.
210 template<typename _ATraits, typename Metadata>
212 : public _Node_base<_ATraits, Metadata>
214 typedef _Node_base<_ATraits, Metadata> base_type;
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;
230 typedef _Leaf<_ATraits, Metadata> leaf;
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);
254 /// Constant child iterator.
255 struct const_iterator
257 node_pointer_pointer m_p_p_cur;
258 node_pointer_pointer m_p_p_end;
260 typedef std::forward_iterator_tag iterator_category;
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;
266 const_iterator(node_pointer_pointer p_p_cur = 0,
267 node_pointer_pointer p_p_end = 0)
268 : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end)
272 operator==(const const_iterator& other) const
273 { return m_p_p_cur == other.m_p_p_cur; }
276 operator!=(const const_iterator& other) const
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);
291 const_iterator ret_it(*this);
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); }
320 struct iterator : public const_iterator
323 typedef std::forward_iterator_tag iterator_category;
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)
332 : const_iterator(p_p_cur, p_p_end) { }
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++();
352 iterator ret_it(*this);
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);
417 remove_child(iterator);
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;
457 _Inode(const _Inode&);
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>
490 // These types are all the same for the first four template arguments.
491 typedef typename Node::allocator_type allocator_type;
492 typedef typename Node::type_traits type_traits;
494 typedef std::bidirectional_iterator_tag iterator_category;
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>());
578 _CIter ret_it(m_p_nd);
586 dec(integral_constant<int, Is_Forward_Iterator>());
593 _CIter ret_it(m_p_nd);
601 { dec(true_type()); }
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));
629 { inc(true_type()); }
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>
717 typedef _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>
806 /// Node const iterator.
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();
857 typedef trivial_iterator_tag iterator_category;
858 typedef trivial_iterator_difference_type difference_type;
859 typedef typename _Alloc::size_type size_type;
861 typedef _CIterator value_type;
862 typedef value_type reference;
863 typedef value_type const_reference;
866 typedef typename Node::metadata_type metadata_type;
868 /// Const metadata reference type.
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)
878 /// Subtree valid prefix.
879 std::pair<a_const_iterator, a_const_iterator>
881 { return std::make_pair(pref_begin(), pref_end()); }
883 /// Const access; returns the __const iterator* associated with
884 /// the current leaf.
888 _GLIBCXX_DEBUG_ASSERT(num_children() == 0);
889 return _CIterator(m_p_nd);
893 metadata_const_reference
895 { return m_p_nd->get_metadata(); }
897 /// Returns the number of children in the corresponding node.
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);
905 return std::distance(inp->begin(), inp->end());
908 /// Returns a __const node __iterator to the corresponding node's
911 get_child(size_type i) const
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();
917 return _Node_citer(*it, m_p_traits);
920 /// Compares content to a different iterator object.
922 operator==(const _Node_citer& other) const
923 { return m_p_nd == other.m_p_nd; }
925 /// Compares content (negatively) to a different iterator object.
927 operator!=(const _Node_citer& other) const
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>
947 typedef _Node_citer<Node, Leaf, Head, Inode,
948 _CIterator, Iterator, _Alloc> base_type;
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)
966 /// Access; returns the iterator* associated with the current leaf.
970 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
971 return iterator(base_type::m_p_nd);
974 /// Returns a node __iterator to the corresponding node's i-th child.
976 get_child(size_type i) const
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)
1012 std::advance(b_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)
1021 std::advance(m_pref_e_it, m_e_ind);
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;
1044 std::advance(m_pref_e_it, m_e_ind);
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
1260 const size_type num_es = std::distance(b_it, e_it);
1261 if (num_es < m_e_ind)
1264 a_const_iterator key_b_it = b_it;
1265 std::advance(key_b_it, checked_ind);
1266 a_const_iterator key_e_it = b_it;
1267 std::advance(key_e_it, m_e_ind);
1269 a_const_iterator value_b_it = m_pref_b_it;
1270 std::advance(value_b_it, checked_ind);
1271 a_const_iterator value_e_it = m_pref_b_it;
1272 std::advance(value_e_it, m_e_ind);
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()
1301 const size_type num_children = std::distance(begin(), end());
1302 _GLIBCXX_DEBUG_ASSERT(num_children >= 2);
1304 iterator it = begin();
1305 std::advance(it, num_children - 1);
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);
1339 PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2);
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));
1352 return std::make_pair(pref_b_it(), pref_e_it());
1356 #undef PB_DS_CLASS_T_DEC
1357 #undef PB_DS_CLASS_C_DEC
1358 } // namespace detail
1359 } // namespace __gnu_pbds