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