libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file pat_trie_/pat_trie_base.hpp 00038 * Contains the base class for a patricia tree. 00039 */ 00040 00041 #ifndef PB_DS_PAT_TRIE_BASE 00042 #define PB_DS_PAT_TRIE_BASE 00043 00044 #include <debug/debug.h> 00045 00046 namespace __gnu_pbds 00047 { 00048 namespace detail 00049 { 00050 /// Base type for PATRICIA trees. 00051 struct pat_trie_base 00052 { 00053 /** 00054 * @brief Three types of nodes. 00055 * 00056 * i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head. 00057 */ 00058 enum node_type 00059 { 00060 i_node, 00061 leaf_node, 00062 head_node 00063 }; 00064 00065 /// Metadata base primary template. 00066 template<typename Metadata, typename _Alloc> 00067 struct _Metadata 00068 { 00069 typedef Metadata metadata_type; 00070 typedef _Alloc allocator_type; 00071 typedef typename _Alloc::template rebind<Metadata> __rebind_m; 00072 typedef typename __rebind_m::other::const_reference const_reference; 00073 00074 const_reference 00075 get_metadata() const 00076 { return m_metadata; } 00077 00078 metadata_type m_metadata; 00079 }; 00080 00081 /// Specialization for null metadata. 00082 template<typename _Alloc> 00083 struct _Metadata<null_type, _Alloc> 00084 { 00085 typedef null_type metadata_type; 00086 typedef _Alloc allocator_type; 00087 }; 00088 00089 00090 /// Node base. 00091 template<typename _ATraits, typename Metadata> 00092 struct _Node_base 00093 : public Metadata 00094 { 00095 private: 00096 typedef typename Metadata::allocator_type _Alloc; 00097 00098 public: 00099 typedef _Alloc allocator_type; 00100 typedef _ATraits access_traits; 00101 typedef typename _ATraits::type_traits type_traits; 00102 typedef typename _Alloc::template rebind<_Node_base> __rebind_n; 00103 typedef typename __rebind_n::other::pointer node_pointer; 00104 00105 node_pointer m_p_parent; 00106 const node_type m_type; 00107 00108 _Node_base(node_type type) : m_type(type) 00109 { } 00110 00111 typedef typename _Alloc::template rebind<_ATraits> __rebind_at; 00112 typedef typename __rebind_at::other::const_pointer a_const_pointer; 00113 typedef typename _ATraits::const_iterator a_const_iterator; 00114 00115 #ifdef _GLIBCXX_DEBUG 00116 typedef std::pair<a_const_iterator, a_const_iterator> node_debug_info; 00117 00118 void 00119 assert_valid(a_const_pointer p_traits, 00120 const char* __file, int __line) const 00121 { assert_valid_imp(p_traits, __file, __line); } 00122 00123 virtual node_debug_info 00124 assert_valid_imp(a_const_pointer, const char*, int) const = 0; 00125 #endif 00126 }; 00127 00128 00129 /// Head node for PATRICIA tree. 00130 template<typename _ATraits, typename Metadata> 00131 struct _Head 00132 : public _Node_base<_ATraits, Metadata> 00133 { 00134 typedef _Node_base<_ATraits, Metadata> base_type; 00135 typedef typename base_type::type_traits type_traits; 00136 typedef typename base_type::node_pointer node_pointer; 00137 00138 node_pointer m_p_min; 00139 node_pointer m_p_max; 00140 00141 _Head() : base_type(head_node) { } 00142 00143 #ifdef _GLIBCXX_DEBUG 00144 typedef typename base_type::node_debug_info node_debug_info; 00145 typedef typename base_type::a_const_pointer a_const_pointer; 00146 00147 virtual node_debug_info 00148 assert_valid_imp(a_const_pointer, const char* __file, int __line) const 00149 { 00150 _GLIBCXX_DEBUG_VERIFY_AT(false, 00151 _M_message("Assertion from %1;:%2;") 00152 ._M_string(__FILE__)._M_integer(__LINE__), 00153 __file, __line); 00154 return node_debug_info(); 00155 } 00156 #endif 00157 }; 00158 00159 00160 /// Leaf node for PATRICIA tree. 00161 template<typename _ATraits, typename Metadata> 00162 struct _Leaf 00163 : public _Node_base<_ATraits, Metadata> 00164 { 00165 typedef _Node_base<_ATraits, Metadata> base_type; 00166 typedef typename base_type::type_traits type_traits; 00167 typedef typename type_traits::value_type value_type; 00168 typedef typename type_traits::reference reference; 00169 typedef typename type_traits::const_reference const_reference; 00170 00171 private: 00172 value_type m_value; 00173 00174 _Leaf(const _Leaf&); 00175 00176 public: 00177 _Leaf(const_reference other) 00178 : base_type(leaf_node), m_value(other) { } 00179 00180 reference 00181 value() 00182 { return m_value; } 00183 00184 const_reference 00185 value() const 00186 { return m_value; } 00187 00188 #ifdef _GLIBCXX_DEBUG 00189 typedef typename base_type::node_debug_info node_debug_info; 00190 typedef typename base_type::a_const_pointer a_const_pointer; 00191 00192 virtual node_debug_info 00193 assert_valid_imp(a_const_pointer p_traits, 00194 const char* __file, int __line) const 00195 { 00196 PB_DS_DEBUG_VERIFY(base_type::m_type == leaf_node); 00197 node_debug_info ret; 00198 const_reference r_val = value(); 00199 return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)), 00200 p_traits->end(p_traits->extract_key(r_val))); 00201 } 00202 00203 virtual 00204 ~_Leaf() { } 00205 #endif 00206 }; 00207 00208 00209 /// Internal node type, PATRICIA tree. 00210 template<typename _ATraits, typename Metadata> 00211 struct _Inode 00212 : public _Node_base<_ATraits, Metadata> 00213 { 00214 typedef _Node_base<_ATraits, Metadata> base_type; 00215 typedef typename base_type::type_traits type_traits; 00216 typedef typename base_type::access_traits access_traits; 00217 typedef typename type_traits::value_type value_type; 00218 typedef typename base_type::allocator_type _Alloc; 00219 typedef _Alloc allocator_type; 00220 typedef typename _Alloc::size_type size_type; 00221 00222 private: 00223 typedef typename base_type::a_const_pointer a_const_pointer; 00224 typedef typename base_type::a_const_iterator a_const_iterator; 00225 00226 typedef typename base_type::node_pointer node_pointer; 00227 typedef typename _Alloc::template rebind<base_type> __rebind_n; 00228 typedef typename __rebind_n::other::const_pointer node_const_pointer; 00229 00230 typedef _Leaf<_ATraits, Metadata> leaf; 00231 typedef typename _Alloc::template rebind<leaf>::other __rebind_l; 00232 typedef typename __rebind_l::pointer leaf_pointer; 00233 typedef typename __rebind_l::const_pointer leaf_const_pointer; 00234 00235 typedef typename _Alloc::template rebind<_Inode>::other __rebind_in; 00236 typedef typename __rebind_in::pointer inode_pointer; 00237 typedef typename __rebind_in::const_pointer inode_const_pointer; 00238 00239 inline size_type 00240 get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer) const; 00241 00242 public: 00243 typedef typename _Alloc::template rebind<node_pointer>::other __rebind_np; 00244 typedef typename __rebind_np::pointer node_pointer_pointer; 00245 typedef typename __rebind_np::reference node_pointer_reference; 00246 00247 enum 00248 { 00249 arr_size = _ATraits::max_size + 1 00250 }; 00251 PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); 00252 00253 00254 /// Constant child iterator. 00255 struct const_iterator 00256 { 00257 node_pointer_pointer m_p_p_cur; 00258 node_pointer_pointer m_p_p_end; 00259 00260 typedef std::forward_iterator_tag iterator_category; 00261 typedef typename _Alloc::difference_type difference_type; 00262 typedef node_pointer value_type; 00263 typedef node_pointer_pointer pointer; 00264 typedef node_pointer_reference reference; 00265 00266 const_iterator(node_pointer_pointer p_p_cur = 0, 00267 node_pointer_pointer p_p_end = 0) 00268 : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end) 00269 { } 00270 00271 bool 00272 operator==(const const_iterator& other) const 00273 { return m_p_p_cur == other.m_p_p_cur; } 00274 00275 bool 00276 operator!=(const const_iterator& other) const 00277 { return m_p_p_cur != other.m_p_p_cur; } 00278 00279 const_iterator& 00280 operator++() 00281 { 00282 do 00283 ++m_p_p_cur; 00284 while (m_p_p_cur != m_p_p_end && *m_p_p_cur == 0); 00285 return *this; 00286 } 00287 00288 const_iterator 00289 operator++(int) 00290 { 00291 const_iterator ret_it(*this); 00292 operator++(); 00293 return ret_it; 00294 } 00295 00296 const node_pointer_pointer 00297 operator->() const 00298 { 00299 _GLIBCXX_DEBUG_ONLY(assert_referencible();) 00300 return m_p_p_cur; 00301 } 00302 00303 node_const_pointer 00304 operator*() const 00305 { 00306 _GLIBCXX_DEBUG_ONLY(assert_referencible();) 00307 return *m_p_p_cur; 00308 } 00309 00310 protected: 00311 #ifdef _GLIBCXX_DEBUG 00312 void 00313 assert_referencible() const 00314 { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end && *m_p_p_cur != 0); } 00315 #endif 00316 }; 00317 00318 00319 /// Child iterator. 00320 struct iterator : public const_iterator 00321 { 00322 public: 00323 typedef std::forward_iterator_tag iterator_category; 00324 typedef typename _Alloc::difference_type difference_type; 00325 typedef node_pointer value_type; 00326 typedef node_pointer_pointer pointer; 00327 typedef node_pointer_reference reference; 00328 00329 inline 00330 iterator(node_pointer_pointer p_p_cur = 0, 00331 node_pointer_pointer p_p_end = 0) 00332 : const_iterator(p_p_cur, p_p_end) { } 00333 00334 bool 00335 operator==(const iterator& other) const 00336 { return const_iterator::m_p_p_cur == other.m_p_p_cur; } 00337 00338 bool 00339 operator!=(const iterator& other) const 00340 { return const_iterator::m_p_p_cur != other.m_p_p_cur; } 00341 00342 iterator& 00343 operator++() 00344 { 00345 const_iterator::operator++(); 00346 return *this; 00347 } 00348 00349 iterator 00350 operator++(int) 00351 { 00352 iterator ret_it(*this); 00353 operator++(); 00354 return ret_it; 00355 } 00356 00357 node_pointer_pointer 00358 operator->() 00359 { 00360 _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) 00361 return const_iterator::m_p_p_cur; 00362 } 00363 00364 node_pointer 00365 operator*() 00366 { 00367 _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) 00368 return *const_iterator::m_p_p_cur; 00369 } 00370 }; 00371 00372 00373 _Inode(size_type, const a_const_iterator); 00374 00375 void 00376 update_prefixes(a_const_pointer); 00377 00378 const_iterator 00379 begin() const; 00380 00381 iterator 00382 begin(); 00383 00384 const_iterator 00385 end() const; 00386 00387 iterator 00388 end(); 00389 00390 inline node_pointer 00391 get_child_node(a_const_iterator, a_const_iterator, a_const_pointer); 00392 00393 inline node_const_pointer 00394 get_child_node(a_const_iterator, a_const_iterator, a_const_pointer) const; 00395 00396 inline iterator 00397 get_child_it(a_const_iterator, a_const_iterator, a_const_pointer); 00398 00399 inline node_pointer 00400 get_lower_bound_child_node(a_const_iterator, a_const_iterator, 00401 size_type, a_const_pointer); 00402 00403 inline node_pointer 00404 add_child(node_pointer, a_const_iterator, a_const_iterator, 00405 a_const_pointer); 00406 00407 inline node_const_pointer 00408 get_join_child(node_const_pointer, a_const_pointer) const; 00409 00410 inline node_pointer 00411 get_join_child(node_pointer, a_const_pointer); 00412 00413 void 00414 remove_child(node_pointer); 00415 00416 void 00417 remove_child(iterator); 00418 00419 void 00420 replace_child(node_pointer, a_const_iterator, a_const_iterator, 00421 a_const_pointer); 00422 00423 inline a_const_iterator 00424 pref_b_it() const; 00425 00426 inline a_const_iterator 00427 pref_e_it() const; 00428 00429 bool 00430 should_be_mine(a_const_iterator, a_const_iterator, size_type, 00431 a_const_pointer) const; 00432 00433 leaf_pointer 00434 leftmost_descendant(); 00435 00436 leaf_const_pointer 00437 leftmost_descendant() const; 00438 00439 leaf_pointer 00440 rightmost_descendant(); 00441 00442 leaf_const_pointer 00443 rightmost_descendant() const; 00444 00445 #ifdef _GLIBCXX_DEBUG 00446 typedef typename base_type::node_debug_info node_debug_info; 00447 00448 virtual node_debug_info 00449 assert_valid_imp(a_const_pointer, const char*, int) const; 00450 #endif 00451 00452 size_type 00453 get_e_ind() const 00454 { return m_e_ind; } 00455 00456 private: 00457 _Inode(const _Inode&); 00458 00459 size_type 00460 get_begin_pos() const; 00461 00462 static __rebind_l s_leaf_alloc; 00463 static __rebind_in s_inode_alloc; 00464 00465 const size_type m_e_ind; 00466 a_const_iterator m_pref_b_it; 00467 a_const_iterator m_pref_e_it; 00468 node_pointer m_a_p_children[arr_size]; 00469 }; 00470 00471 #define PB_DS_CONST_IT_C_DEC \ 00472 _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 00473 00474 #define PB_DS_CONST_ODIR_IT_C_DEC \ 00475 _CIter<Node, Leaf, Head, Inode, !Is_Forward_Iterator> 00476 00477 #define PB_DS_IT_C_DEC \ 00478 _Iter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 00479 00480 #define PB_DS_ODIR_IT_C_DEC \ 00481 _Iter<Node, Leaf, Head, Inode, !Is_Forward_Iterator> 00482 00483 00484 /// Const iterator. 00485 template<typename Node, typename Leaf, typename Head, typename Inode, 00486 bool Is_Forward_Iterator> 00487 class _CIter 00488 { 00489 public: 00490 // These types are all the same for the first four template arguments. 00491 typedef typename Node::allocator_type allocator_type; 00492 typedef typename Node::type_traits type_traits; 00493 00494 typedef std::bidirectional_iterator_tag iterator_category; 00495 typedef typename allocator_type::difference_type difference_type; 00496 typedef typename type_traits::value_type value_type; 00497 typedef typename type_traits::pointer pointer; 00498 typedef typename type_traits::reference reference; 00499 typedef typename type_traits::const_pointer const_pointer; 00500 typedef typename type_traits::const_reference const_reference; 00501 00502 typedef allocator_type _Alloc; 00503 typedef typename _Alloc::template rebind<Node> __rebind_n; 00504 typedef typename __rebind_n::other::pointer node_pointer; 00505 typedef typename _Alloc::template rebind<Leaf> __rebind_l; 00506 typedef typename __rebind_l::other::pointer leaf_pointer; 00507 typedef typename __rebind_l::other::const_pointer leaf_const_pointer; 00508 typedef typename _Alloc::template rebind<Head> __rebind_h; 00509 typedef typename __rebind_h::other::pointer head_pointer; 00510 00511 typedef typename _Alloc::template rebind<Inode> __rebind_in; 00512 typedef typename __rebind_in::other::pointer inode_pointer; 00513 typedef typename Inode::iterator inode_iterator; 00514 00515 node_pointer m_p_nd; 00516 00517 _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd) 00518 { } 00519 00520 _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other) 00521 : m_p_nd(other.m_p_nd) 00522 { } 00523 00524 _CIter& 00525 operator=(const _CIter& other) 00526 { 00527 m_p_nd = other.m_p_nd; 00528 return *this; 00529 } 00530 00531 _CIter& 00532 operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) 00533 { 00534 m_p_nd = other.m_p_nd; 00535 return *this; 00536 } 00537 00538 const_pointer 00539 operator->() const 00540 { 00541 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); 00542 return &static_cast<leaf_pointer>(m_p_nd)->value(); 00543 } 00544 00545 const_reference 00546 operator*() const 00547 { 00548 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); 00549 return static_cast<leaf_pointer>(m_p_nd)->value(); 00550 } 00551 00552 bool 00553 operator==(const _CIter& other) const 00554 { return m_p_nd == other.m_p_nd; } 00555 00556 bool 00557 operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 00558 { return m_p_nd == other.m_p_nd; } 00559 00560 bool 00561 operator!=(const _CIter& other) const 00562 { return m_p_nd != other.m_p_nd; } 00563 00564 bool 00565 operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 00566 { return m_p_nd != other.m_p_nd; } 00567 00568 _CIter& 00569 operator++() 00570 { 00571 inc(integral_constant<int, Is_Forward_Iterator>()); 00572 return *this; 00573 } 00574 00575 _CIter 00576 operator++(int) 00577 { 00578 _CIter ret_it(m_p_nd); 00579 operator++(); 00580 return ret_it; 00581 } 00582 00583 _CIter& 00584 operator--() 00585 { 00586 dec(integral_constant<int, Is_Forward_Iterator>()); 00587 return *this; 00588 } 00589 00590 _CIter 00591 operator--(int) 00592 { 00593 _CIter ret_it(m_p_nd); 00594 operator--(); 00595 return ret_it; 00596 } 00597 00598 protected: 00599 void 00600 inc(false_type) 00601 { dec(true_type()); } 00602 00603 void 00604 inc(true_type) 00605 { 00606 if (m_p_nd->m_type == head_node) 00607 { 00608 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min; 00609 return; 00610 } 00611 00612 node_pointer p_y = m_p_nd->m_p_parent; 00613 while (p_y->m_type != head_node && get_larger_sibling(m_p_nd) == 0) 00614 { 00615 m_p_nd = p_y; 00616 p_y = p_y->m_p_parent; 00617 } 00618 00619 if (p_y->m_type == head_node) 00620 { 00621 m_p_nd = p_y; 00622 return; 00623 } 00624 m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); 00625 } 00626 00627 void 00628 dec(false_type) 00629 { inc(true_type()); } 00630 00631 void 00632 dec(true_type) 00633 { 00634 if (m_p_nd->m_type == head_node) 00635 { 00636 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max; 00637 return; 00638 } 00639 00640 node_pointer p_y = m_p_nd->m_p_parent; 00641 while (p_y->m_type != head_node && get_smaller_sibling(m_p_nd) == 0) 00642 { 00643 m_p_nd = p_y; 00644 p_y = p_y->m_p_parent; 00645 } 00646 00647 if (p_y->m_type == head_node) 00648 { 00649 m_p_nd = p_y; 00650 return; 00651 } 00652 m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); 00653 } 00654 00655 static node_pointer 00656 get_larger_sibling(node_pointer p_nd) 00657 { 00658 inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); 00659 00660 inode_iterator it = p_parent->begin(); 00661 while (*it != p_nd) 00662 ++it; 00663 00664 inode_iterator next_it = it; 00665 ++next_it; 00666 return (next_it == p_parent->end())? 0 : *next_it; 00667 } 00668 00669 static node_pointer 00670 get_smaller_sibling(node_pointer p_nd) 00671 { 00672 inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); 00673 00674 inode_iterator it = p_parent->begin(); 00675 if (*it == p_nd) 00676 return 0; 00677 00678 inode_iterator prev_it; 00679 do 00680 { 00681 prev_it = it; 00682 ++it; 00683 if (*it == p_nd) 00684 return *prev_it; 00685 } 00686 while (true); 00687 00688 _GLIBCXX_DEBUG_ASSERT(false); 00689 return 0; 00690 } 00691 00692 static leaf_pointer 00693 leftmost_descendant(node_pointer p_nd) 00694 { 00695 if (p_nd->m_type == leaf_node) 00696 return static_cast<leaf_pointer>(p_nd); 00697 return static_cast<inode_pointer>(p_nd)->leftmost_descendant(); 00698 } 00699 00700 static leaf_pointer 00701 rightmost_descendant(node_pointer p_nd) 00702 { 00703 if (p_nd->m_type == leaf_node) 00704 return static_cast<leaf_pointer>(p_nd); 00705 return static_cast<inode_pointer>(p_nd)->rightmost_descendant(); 00706 } 00707 }; 00708 00709 00710 /// Iterator. 00711 template<typename Node, typename Leaf, typename Head, typename Inode, 00712 bool Is_Forward_Iterator> 00713 class _Iter 00714 : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 00715 { 00716 public: 00717 typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 00718 base_type; 00719 typedef typename base_type::allocator_type allocator_type; 00720 typedef typename base_type::type_traits type_traits; 00721 typedef typename type_traits::value_type value_type; 00722 typedef typename type_traits::pointer pointer; 00723 typedef typename type_traits::reference reference; 00724 00725 typedef typename base_type::node_pointer node_pointer; 00726 typedef typename base_type::leaf_pointer leaf_pointer; 00727 typedef typename base_type::leaf_const_pointer leaf_const_pointer; 00728 typedef typename base_type::head_pointer head_pointer; 00729 typedef typename base_type::inode_pointer inode_pointer; 00730 00731 _Iter(node_pointer p_nd = 0) 00732 : base_type(p_nd) { } 00733 00734 _Iter(const PB_DS_ODIR_IT_C_DEC& other) 00735 : base_type(other.m_p_nd) { } 00736 00737 _Iter& 00738 operator=(const _Iter& other) 00739 { 00740 base_type::m_p_nd = other.m_p_nd; 00741 return *this; 00742 } 00743 00744 _Iter& 00745 operator=(const PB_DS_ODIR_IT_C_DEC& other) 00746 { 00747 base_type::m_p_nd = other.m_p_nd; 00748 return *this; 00749 } 00750 00751 pointer 00752 operator->() const 00753 { 00754 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node); 00755 return &static_cast<leaf_pointer>(base_type::m_p_nd)->value(); 00756 } 00757 00758 reference 00759 operator*() const 00760 { 00761 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node); 00762 return static_cast<leaf_pointer>(base_type::m_p_nd)->value(); 00763 } 00764 00765 _Iter& 00766 operator++() 00767 { 00768 base_type::operator++(); 00769 return *this; 00770 } 00771 00772 _Iter 00773 operator++(int) 00774 { 00775 _Iter ret(base_type::m_p_nd); 00776 operator++(); 00777 return ret; 00778 } 00779 00780 _Iter& 00781 operator--() 00782 { 00783 base_type::operator--(); 00784 return *this; 00785 } 00786 00787 _Iter 00788 operator--(int) 00789 { 00790 _Iter ret(base_type::m_p_nd); 00791 operator--(); 00792 return ret; 00793 } 00794 }; 00795 00796 #undef PB_DS_CONST_ODIR_IT_C_DEC 00797 #undef PB_DS_ODIR_IT_C_DEC 00798 00799 00800 #define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \ 00801 _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> 00802 00803 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ 00804 _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> 00805 00806 /// Node const iterator. 00807 template<typename Node, 00808 typename Leaf, 00809 typename Head, 00810 typename Inode, 00811 typename _CIterator, 00812 typename Iterator, 00813 typename _Alloc> 00814 class _Node_citer 00815 { 00816 protected: 00817 typedef typename _Alloc::template rebind<Node> __rebind_n; 00818 typedef typename __rebind_n::other::pointer node_pointer; 00819 00820 typedef typename _Alloc::template rebind<Leaf> __rebind_l; 00821 typedef typename __rebind_l::other::pointer leaf_pointer; 00822 typedef typename __rebind_l::other::const_pointer leaf_const_pointer; 00823 00824 typedef typename _Alloc::template rebind<Inode> __rebind_in; 00825 typedef typename __rebind_in::other::pointer inode_pointer; 00826 typedef typename __rebind_in::other::const_pointer inode_const_pointer; 00827 00828 typedef typename Node::a_const_pointer a_const_pointer; 00829 typedef typename Node::a_const_iterator a_const_iterator; 00830 00831 private: 00832 a_const_iterator 00833 pref_begin() const 00834 { 00835 if (m_p_nd->m_type == leaf_node) 00836 { 00837 leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd); 00838 return m_p_traits->begin(m_p_traits->extract_key(lcp->value())); 00839 } 00840 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 00841 return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it(); 00842 } 00843 00844 a_const_iterator 00845 pref_end() const 00846 { 00847 if (m_p_nd->m_type == leaf_node) 00848 { 00849 leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd); 00850 return m_p_traits->end(m_p_traits->extract_key(lcp->value())); 00851 } 00852 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 00853 return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it(); 00854 } 00855 00856 public: 00857 typedef trivial_iterator_tag iterator_category; 00858 typedef trivial_iterator_difference_type difference_type; 00859 typedef typename _Alloc::size_type size_type; 00860 00861 typedef _CIterator value_type; 00862 typedef value_type reference; 00863 typedef value_type const_reference; 00864 00865 /// Metadata type. 00866 typedef typename Node::metadata_type metadata_type; 00867 00868 /// Const metadata reference type. 00869 typedef typename _Alloc::template rebind<metadata_type> __rebind_m; 00870 typedef typename __rebind_m::other __rebind_ma; 00871 typedef typename __rebind_ma::const_reference metadata_const_reference; 00872 00873 inline 00874 _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0) 00875 : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) 00876 { } 00877 00878 /// Subtree valid prefix. 00879 std::pair<a_const_iterator, a_const_iterator> 00880 valid_prefix() const 00881 { return std::make_pair(pref_begin(), pref_end()); } 00882 00883 /// Const access; returns the __const iterator* associated with 00884 /// the current leaf. 00885 const_reference 00886 operator*() const 00887 { 00888 _GLIBCXX_DEBUG_ASSERT(num_children() == 0); 00889 return _CIterator(m_p_nd); 00890 } 00891 00892 /// Metadata access. 00893 metadata_const_reference 00894 get_metadata() const 00895 { return m_p_nd->get_metadata(); } 00896 00897 /// Returns the number of children in the corresponding node. 00898 size_type 00899 num_children() const 00900 { 00901 if (m_p_nd->m_type == leaf_node) 00902 return 0; 00903 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 00904 inode_pointer inp = static_cast<inode_pointer>(m_p_nd); 00905 return std::distance(inp->begin(), inp->end()); 00906 } 00907 00908 /// Returns a __const node __iterator to the corresponding node's 00909 /// i-th child. 00910 _Node_citer 00911 get_child(size_type i) const 00912 { 00913 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 00914 inode_pointer inp = static_cast<inode_pointer>(m_p_nd); 00915 typename Inode::iterator it = inp->begin(); 00916 std::advance(it, i); 00917 return _Node_citer(*it, m_p_traits); 00918 } 00919 00920 /// Compares content to a different iterator object. 00921 bool 00922 operator==(const _Node_citer& other) const 00923 { return m_p_nd == other.m_p_nd; } 00924 00925 /// Compares content (negatively) to a different iterator object. 00926 bool 00927 operator!=(const _Node_citer& other) const 00928 { return m_p_nd != other.m_p_nd; } 00929 00930 node_pointer m_p_nd; 00931 a_const_pointer m_p_traits; 00932 }; 00933 00934 00935 /// Node iterator. 00936 template<typename Node, 00937 typename Leaf, 00938 typename Head, 00939 typename Inode, 00940 typename _CIterator, 00941 typename Iterator, 00942 typename _Alloc> 00943 class _Node_iter 00944 : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc> 00945 { 00946 private: 00947 typedef _Node_citer<Node, Leaf, Head, Inode, 00948 _CIterator, Iterator, _Alloc> base_type; 00949 typedef typename _Alloc::template rebind<Node> __rebind_n; 00950 typedef typename __rebind_n::other::pointer node_pointer; 00951 typedef typename base_type::inode_pointer inode_pointer; 00952 typedef typename base_type::a_const_pointer a_const_pointer; 00953 typedef Iterator iterator; 00954 00955 public: 00956 typedef typename base_type::size_type size_type; 00957 00958 typedef Iterator value_type; 00959 typedef value_type reference; 00960 typedef value_type const_reference; 00961 00962 _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0) 00963 : base_type(p_nd, p_traits) 00964 { } 00965 00966 /// Access; returns the iterator* associated with the current leaf. 00967 reference 00968 operator*() const 00969 { 00970 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); 00971 return iterator(base_type::m_p_nd); 00972 } 00973 00974 /// Returns a node __iterator to the corresponding node's i-th child. 00975 _Node_iter 00976 get_child(size_type i) const 00977 { 00978 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node); 00979 00980 typename Inode::iterator it = 00981 static_cast<inode_pointer>(base_type::m_p_nd)->begin(); 00982 00983 std::advance(it, i); 00984 return _Node_iter(*it, base_type::m_p_traits); 00985 } 00986 }; 00987 }; 00988 00989 00990 #define PB_DS_CLASS_T_DEC \ 00991 template<typename _ATraits, typename Metadata> 00992 00993 #define PB_DS_CLASS_C_DEC \ 00994 pat_trie_base::_Inode<_ATraits, Metadata> 00995 00996 PB_DS_CLASS_T_DEC 00997 typename PB_DS_CLASS_C_DEC::__rebind_l 00998 PB_DS_CLASS_C_DEC::s_leaf_alloc; 00999 01000 PB_DS_CLASS_T_DEC 01001 typename PB_DS_CLASS_C_DEC::__rebind_in 01002 PB_DS_CLASS_C_DEC::s_inode_alloc; 01003 01004 PB_DS_CLASS_T_DEC 01005 inline typename PB_DS_CLASS_C_DEC::size_type 01006 PB_DS_CLASS_C_DEC:: 01007 get_pref_pos(a_const_iterator b_it, a_const_iterator e_it, 01008 a_const_pointer p_traits) const 01009 { 01010 if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind) 01011 return 0; 01012 std::advance(b_it, m_e_ind); 01013 return 1 + p_traits->e_pos(*b_it); 01014 } 01015 01016 PB_DS_CLASS_T_DEC 01017 PB_DS_CLASS_C_DEC:: 01018 _Inode(size_type len, const a_const_iterator it) 01019 : base_type(i_node), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) 01020 { 01021 std::advance(m_pref_e_it, m_e_ind); 01022 std::fill(m_a_p_children, m_a_p_children + arr_size, 01023 static_cast<node_pointer>(0)); 01024 } 01025 01026 PB_DS_CLASS_T_DEC 01027 void 01028 PB_DS_CLASS_C_DEC:: 01029 update_prefixes(a_const_pointer p_traits) 01030 { 01031 node_pointer p_first = *begin(); 01032 if (p_first->m_type == leaf_node) 01033 { 01034 leaf_const_pointer p = static_cast<leaf_const_pointer>(p_first); 01035 m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value())); 01036 } 01037 else 01038 { 01039 inode_pointer p = static_cast<inode_pointer>(p_first); 01040 _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node); 01041 m_pref_b_it = p->pref_b_it(); 01042 } 01043 m_pref_e_it = m_pref_b_it; 01044 std::advance(m_pref_e_it, m_e_ind); 01045 } 01046 01047 PB_DS_CLASS_T_DEC 01048 typename PB_DS_CLASS_C_DEC::const_iterator 01049 PB_DS_CLASS_C_DEC:: 01050 begin() const 01051 { 01052 typedef node_pointer_pointer pointer_type; 01053 pointer_type p = const_cast<pointer_type>(m_a_p_children); 01054 return const_iterator(p + get_begin_pos(), p + arr_size); 01055 } 01056 01057 PB_DS_CLASS_T_DEC 01058 typename PB_DS_CLASS_C_DEC::iterator 01059 PB_DS_CLASS_C_DEC:: 01060 begin() 01061 { 01062 return iterator(m_a_p_children + get_begin_pos(), 01063 m_a_p_children + arr_size); 01064 } 01065 01066 PB_DS_CLASS_T_DEC 01067 typename PB_DS_CLASS_C_DEC::const_iterator 01068 PB_DS_CLASS_C_DEC:: 01069 end() const 01070 { 01071 typedef node_pointer_pointer pointer_type; 01072 pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size; 01073 return const_iterator(p, p); 01074 } 01075 01076 PB_DS_CLASS_T_DEC 01077 typename PB_DS_CLASS_C_DEC::iterator 01078 PB_DS_CLASS_C_DEC:: 01079 end() 01080 { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } 01081 01082 PB_DS_CLASS_T_DEC 01083 inline typename PB_DS_CLASS_C_DEC::node_pointer 01084 PB_DS_CLASS_C_DEC:: 01085 get_child_node(a_const_iterator b_it, a_const_iterator e_it, 01086 a_const_pointer p_traits) 01087 { 01088 const size_type i = get_pref_pos(b_it, e_it, p_traits); 01089 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 01090 return m_a_p_children[i]; 01091 } 01092 01093 PB_DS_CLASS_T_DEC 01094 inline typename PB_DS_CLASS_C_DEC::iterator 01095 PB_DS_CLASS_C_DEC:: 01096 get_child_it(a_const_iterator b_it, a_const_iterator e_it, 01097 a_const_pointer p_traits) 01098 { 01099 const size_type i = get_pref_pos(b_it, e_it, p_traits); 01100 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 01101 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0); 01102 return iterator(m_a_p_children + i, m_a_p_children + i); 01103 } 01104 01105 PB_DS_CLASS_T_DEC 01106 inline typename PB_DS_CLASS_C_DEC::node_const_pointer 01107 PB_DS_CLASS_C_DEC:: 01108 get_child_node(a_const_iterator b_it, a_const_iterator e_it, 01109 a_const_pointer p_traits) const 01110 { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); } 01111 01112 PB_DS_CLASS_T_DEC 01113 typename PB_DS_CLASS_C_DEC::node_pointer 01114 PB_DS_CLASS_C_DEC:: 01115 get_lower_bound_child_node(a_const_iterator b_it, a_const_iterator e_it, 01116 size_type checked_ind, 01117 a_const_pointer p_traits) 01118 { 01119 if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) 01120 { 01121 if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, 01122 m_pref_e_it, true)) 01123 return leftmost_descendant(); 01124 return rightmost_descendant(); 01125 } 01126 01127 size_type i = get_pref_pos(b_it, e_it, p_traits); 01128 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 01129 01130 if (m_a_p_children[i] != 0) 01131 return m_a_p_children[i]; 01132 01133 while (++i < arr_size) 01134 if (m_a_p_children[i] != 0) 01135 { 01136 const node_type& __nt = m_a_p_children[i]->m_type; 01137 node_pointer ret = m_a_p_children[i]; 01138 01139 if (__nt == leaf_node) 01140 return ret; 01141 01142 _GLIBCXX_DEBUG_ASSERT(__nt == i_node); 01143 inode_pointer inp = static_cast<inode_pointer>(ret); 01144 return inp->leftmost_descendant(); 01145 } 01146 01147 return rightmost_descendant(); 01148 } 01149 01150 PB_DS_CLASS_T_DEC 01151 inline typename PB_DS_CLASS_C_DEC::node_pointer 01152 PB_DS_CLASS_C_DEC:: 01153 add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it, 01154 a_const_pointer p_traits) 01155 { 01156 const size_type i = get_pref_pos(b_it, e_it, p_traits); 01157 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 01158 if (m_a_p_children[i] == 0) 01159 { 01160 m_a_p_children[i] = p_nd; 01161 p_nd->m_p_parent = this; 01162 return p_nd; 01163 } 01164 return m_a_p_children[i]; 01165 } 01166 01167 PB_DS_CLASS_T_DEC 01168 typename PB_DS_CLASS_C_DEC::node_const_pointer 01169 PB_DS_CLASS_C_DEC:: 01170 get_join_child(node_const_pointer p_nd, 01171 a_const_pointer p_tr) const 01172 { 01173 node_pointer p = const_cast<node_pointer>(p_nd); 01174 return const_cast<inode_pointer>(this)->get_join_child(p, p_tr); 01175 } 01176 01177 PB_DS_CLASS_T_DEC 01178 typename PB_DS_CLASS_C_DEC::node_pointer 01179 PB_DS_CLASS_C_DEC:: 01180 get_join_child(node_pointer p_nd, a_const_pointer p_traits) 01181 { 01182 size_type i; 01183 a_const_iterator b_it; 01184 a_const_iterator e_it; 01185 if (p_nd->m_type == leaf_node) 01186 { 01187 leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd); 01188 01189 typedef typename type_traits::key_const_reference kcr; 01190 kcr r_key = access_traits::extract_key(p->value()); 01191 b_it = p_traits->begin(r_key); 01192 e_it = p_traits->end(r_key); 01193 } 01194 else 01195 { 01196 b_it = static_cast<inode_pointer>(p_nd)->pref_b_it(); 01197 e_it = static_cast<inode_pointer>(p_nd)->pref_e_it(); 01198 } 01199 i = get_pref_pos(b_it, e_it, p_traits); 01200 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 01201 return m_a_p_children[i]; 01202 } 01203 01204 PB_DS_CLASS_T_DEC 01205 void 01206 PB_DS_CLASS_C_DEC:: 01207 remove_child(node_pointer p_nd) 01208 { 01209 size_type i = 0; 01210 for (; i < arr_size; ++i) 01211 if (m_a_p_children[i] == p_nd) 01212 { 01213 m_a_p_children[i] = 0; 01214 return; 01215 } 01216 _GLIBCXX_DEBUG_ASSERT(i != arr_size); 01217 } 01218 01219 PB_DS_CLASS_T_DEC 01220 void 01221 PB_DS_CLASS_C_DEC:: 01222 remove_child(iterator it) 01223 { *it.m_p_p_cur = 0; } 01224 01225 PB_DS_CLASS_T_DEC 01226 void 01227 PB_DS_CLASS_C_DEC:: 01228 replace_child(node_pointer p_nd, a_const_iterator b_it, 01229 a_const_iterator e_it, 01230 a_const_pointer p_traits) 01231 { 01232 const size_type i = get_pref_pos(b_it, e_it, p_traits); 01233 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 01234 m_a_p_children[i] = p_nd; 01235 p_nd->m_p_parent = this; 01236 } 01237 01238 PB_DS_CLASS_T_DEC 01239 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 01240 PB_DS_CLASS_C_DEC:: 01241 pref_b_it() const 01242 { return m_pref_b_it; } 01243 01244 PB_DS_CLASS_T_DEC 01245 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 01246 PB_DS_CLASS_C_DEC:: 01247 pref_e_it() const 01248 { return m_pref_e_it; } 01249 01250 PB_DS_CLASS_T_DEC 01251 bool 01252 PB_DS_CLASS_C_DEC:: 01253 should_be_mine(a_const_iterator b_it, a_const_iterator e_it, 01254 size_type checked_ind, 01255 a_const_pointer p_traits) const 01256 { 01257 if (m_e_ind == 0) 01258 return true; 01259 01260 const size_type num_es = std::distance(b_it, e_it); 01261 if (num_es < m_e_ind) 01262 return false; 01263 01264 a_const_iterator key_b_it = b_it; 01265 std::advance(key_b_it, checked_ind); 01266 a_const_iterator key_e_it = b_it; 01267 std::advance(key_e_it, m_e_ind); 01268 01269 a_const_iterator value_b_it = m_pref_b_it; 01270 std::advance(value_b_it, checked_ind); 01271 a_const_iterator value_e_it = m_pref_b_it; 01272 std::advance(value_e_it, m_e_ind); 01273 01274 return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, 01275 value_e_it); 01276 } 01277 01278 PB_DS_CLASS_T_DEC 01279 typename PB_DS_CLASS_C_DEC::leaf_pointer 01280 PB_DS_CLASS_C_DEC:: 01281 leftmost_descendant() 01282 { 01283 node_pointer p_pot = *begin(); 01284 if (p_pot->m_type == leaf_node) 01285 return (static_cast<leaf_pointer>(p_pot)); 01286 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node); 01287 return static_cast<inode_pointer>(p_pot)->leftmost_descendant(); 01288 } 01289 01290 PB_DS_CLASS_T_DEC 01291 typename PB_DS_CLASS_C_DEC::leaf_const_pointer 01292 PB_DS_CLASS_C_DEC:: 01293 leftmost_descendant() const 01294 { return const_cast<inode_pointer>(this)->leftmost_descendant(); } 01295 01296 PB_DS_CLASS_T_DEC 01297 typename PB_DS_CLASS_C_DEC::leaf_pointer 01298 PB_DS_CLASS_C_DEC:: 01299 rightmost_descendant() 01300 { 01301 const size_type num_children = std::distance(begin(), end()); 01302 _GLIBCXX_DEBUG_ASSERT(num_children >= 2); 01303 01304 iterator it = begin(); 01305 std::advance(it, num_children - 1); 01306 node_pointer p_pot =* it; 01307 if (p_pot->m_type == leaf_node) 01308 return static_cast<leaf_pointer>(p_pot); 01309 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node); 01310 return static_cast<inode_pointer>(p_pot)->rightmost_descendant(); 01311 } 01312 01313 PB_DS_CLASS_T_DEC 01314 typename PB_DS_CLASS_C_DEC::leaf_const_pointer 01315 PB_DS_CLASS_C_DEC:: 01316 rightmost_descendant() const 01317 { return const_cast<inode_pointer>(this)->rightmost_descendant(); } 01318 01319 PB_DS_CLASS_T_DEC 01320 typename PB_DS_CLASS_C_DEC::size_type 01321 PB_DS_CLASS_C_DEC:: 01322 get_begin_pos() const 01323 { 01324 size_type i = 0; 01325 for (; i < arr_size && m_a_p_children[i] == 0; ++i) 01326 ; 01327 return i; 01328 } 01329 01330 #ifdef _GLIBCXX_DEBUG 01331 PB_DS_CLASS_T_DEC 01332 typename PB_DS_CLASS_C_DEC::node_debug_info 01333 PB_DS_CLASS_C_DEC:: 01334 assert_valid_imp(a_const_pointer p_traits, 01335 const char* __file, int __line) const 01336 { 01337 PB_DS_DEBUG_VERIFY(base_type::m_type == i_node); 01338 PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); 01339 PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2); 01340 01341 for (typename _Inode::const_iterator it = begin(); it != end(); ++it) 01342 { 01343 node_const_pointer p_nd = *it; 01344 PB_DS_DEBUG_VERIFY(p_nd->m_p_parent == this); 01345 node_debug_info child_ret = p_nd->assert_valid_imp(p_traits, 01346 __file, __line); 01347 01348 PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); 01349 PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); 01350 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)); 01351 } 01352 return std::make_pair(pref_b_it(), pref_e_it()); 01353 } 01354 #endif 01355 01356 #undef PB_DS_CLASS_T_DEC 01357 #undef PB_DS_CLASS_C_DEC 01358 } // namespace detail 01359 } // namespace __gnu_pbds 01360 01361 #endif