1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009, 2011, 2012 Free Software Foundation, Inc. 4 // 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 9 // version. 10 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. 15 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. 19 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/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 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 34 // warranty. 35 36 /** 37 * @file pat_trie_/pat_trie_base.hpp 38 * Contains the base class for a patricia tree. 39 */ 40 41 #ifndef PB_DS_PAT_TRIE_BASE 42 #define PB_DS_PAT_TRIE_BASE 43 44 #include <debug/debug.h> 45 46 namespace __gnu_pbds 47 { 48 namespace detail 49 { 50 /// Base type for PATRICIA trees. 51 struct pat_trie_base 52 { 53 /** 54 * @brief Three types of nodes. 55 * 56 * i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head. 57 */ 58 enum node_type 59 { 60 i_node, 61 leaf_node, 62 head_node 63 }; 64 65 /// Metadata base primary template. 66 template<typename Metadata, typename _Alloc> 67 struct _Metadata 68 { 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; 73 74 const_reference 75 get_metadata() const 76 { return m_metadata; } 77 78 metadata_type m_metadata; 79 }; 80 81 /// Specialization for null metadata. 82 template<typename _Alloc> 83 struct _Metadata<null_type, _Alloc> 84 { 85 typedef null_type metadata_type; 86 typedef _Alloc allocator_type; 87 }; 88 89 90 /// Node base. 91 template<typename _ATraits, typename Metadata> 92 struct _Node_base 93 : public Metadata 94 { 95 private: 96 typedef typename Metadata::allocator_type _Alloc; 97 98 public: 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; 104 105 node_pointer m_p_parent; 106 const node_type m_type; 107 108 _Node_base(node_type type) : m_type(type) 109 { } 110 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; 114 115 #ifdef _GLIBCXX_DEBUG 116 typedef std::pair<a_const_iterator, a_const_iterator> node_debug_info; 117 118 void 119 assert_valid(a_const_pointer p_traits, 120 const char* __file, int __line) const 121 { assert_valid_imp(p_traits, __file, __line); } 122 123 virtual node_debug_info 124 assert_valid_imp(a_const_pointer, const char*, int) const = 0; 125 #endif 126 }; 127 128 129 /// Head node for PATRICIA tree. 130 template<typename _ATraits, typename Metadata> 131 struct _Head 132 : public _Node_base<_ATraits, Metadata> 133 { 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; 137 138 node_pointer m_p_min; 139 node_pointer m_p_max; 140 141 _Head() : base_type(head_node) { } 142 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; 146 147 virtual node_debug_info 148 assert_valid_imp(a_const_pointer, const char* __file, int __line) const 149 { 150 _GLIBCXX_DEBUG_VERIFY_AT(false, 151 _M_message("Assertion from %1;:%2;") 152 ._M_string(__FILE__)._M_integer(__LINE__), 153 __file, __line); 154 return node_debug_info(); 155 } 156 #endif 157 }; 158 159 160 /// Leaf node for PATRICIA tree. 161 template<typename _ATraits, typename Metadata> 162 struct _Leaf 163 : public _Node_base<_ATraits, Metadata> 164 { 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; 170 171 private: 172 value_type m_value; 173 174 _Leaf(const _Leaf&); 175 176 public: 177 _Leaf(const_reference other) 178 : base_type(leaf_node), m_value(other) { } 179 180 reference 181 value() 182 { return m_value; } 183 184 const_reference 185 value() const 186 { return m_value; } 187 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; 191 192 virtual node_debug_info 193 assert_valid_imp(a_const_pointer p_traits, 194 const char* __file, int __line) const 195 { 196 PB_DS_DEBUG_VERIFY(base_type::m_type == leaf_node); 197 node_debug_info ret; 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))); 201 } 202 203 virtual 204 ~_Leaf() { } 205 #endif 206 }; 207 208 209 /// Internal node type, PATRICIA tree. 210 template<typename _ATraits, typename Metadata> 211 struct _Inode 212 : public _Node_base<_ATraits, Metadata> 213 { 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; 221 222 private: 223 typedef typename base_type::a_const_pointer a_const_pointer; 224 typedef typename base_type::a_const_iterator a_const_iterator; 225 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; 229 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; 234 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; 238 239 inline size_type 240 get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer) const; 241 242 public: 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; 246 247 enum 248 { 249 arr_size = _ATraits::max_size + 1 250 }; 251 PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); 252 253 254 /// Constant child iterator. 255 struct const_iterator 256 { 257 node_pointer_pointer m_p_p_cur; 258 node_pointer_pointer m_p_p_end; 259 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; 265 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) 269 { } 270 271 bool 272 operator==(const const_iterator& other) const 273 { return m_p_p_cur == other.m_p_p_cur; } 274 275 bool 276 operator!=(const const_iterator& other) const 277 { return m_p_p_cur != other.m_p_p_cur; } 278 279 const_iterator& 280 operator++() 281 { 282 do 283 ++m_p_p_cur; 284 while (m_p_p_cur != m_p_p_end && *m_p_p_cur == 0); 285 return *this; 286 } 287 288 const_iterator 289 operator++(int) 290 { 291 const_iterator ret_it(*this); 292 operator++(); 293 return ret_it; 294 } 295 296 const node_pointer_pointer 297 operator->() const 298 { 299 _GLIBCXX_DEBUG_ONLY(assert_referencible();) 300 return m_p_p_cur; 301 } 302 303 node_const_pointer 304 operator*() const 305 { 306 _GLIBCXX_DEBUG_ONLY(assert_referencible();) 307 return *m_p_p_cur; 308 } 309 310 protected: 311 #ifdef _GLIBCXX_DEBUG 312 void 313 assert_referencible() const 314 { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end && *m_p_p_cur != 0); } 315 #endif 316 }; 317 318 319 /// Child iterator. 320 struct iterator : public const_iterator 321 { 322 public: 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; 328 329 inline 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) { } 333 334 bool 335 operator==(const iterator& other) const 336 { return const_iterator::m_p_p_cur == other.m_p_p_cur; } 337 338 bool 339 operator!=(const iterator& other) const 340 { return const_iterator::m_p_p_cur != other.m_p_p_cur; } 341 342 iterator& 343 operator++() 344 { 345 const_iterator::operator++(); 346 return *this; 347 } 348 349 iterator 350 operator++(int) 351 { 352 iterator ret_it(*this); 353 operator++(); 354 return ret_it; 355 } 356 357 node_pointer_pointer 358 operator->() 359 { 360 _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) 361 return const_iterator::m_p_p_cur; 362 } 363 364 node_pointer 365 operator*() 366 { 367 _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) 368 return *const_iterator::m_p_p_cur; 369 } 370 }; 371 372 373 _Inode(size_type, const a_const_iterator); 374 375 void 376 update_prefixes(a_const_pointer); 377 378 const_iterator 379 begin() const; 380 381 iterator 382 begin(); 383 384 const_iterator 385 end() const; 386 387 iterator 388 end(); 389 390 inline node_pointer 391 get_child_node(a_const_iterator, a_const_iterator, a_const_pointer); 392 393 inline node_const_pointer 394 get_child_node(a_const_iterator, a_const_iterator, a_const_pointer) const; 395 396 inline iterator 397 get_child_it(a_const_iterator, a_const_iterator, a_const_pointer); 398 399 inline node_pointer 400 get_lower_bound_child_node(a_const_iterator, a_const_iterator, 401 size_type, a_const_pointer); 402 403 inline node_pointer 404 add_child(node_pointer, a_const_iterator, a_const_iterator, 405 a_const_pointer); 406 407 inline node_const_pointer 408 get_join_child(node_const_pointer, a_const_pointer) const; 409 410 inline node_pointer 411 get_join_child(node_pointer, a_const_pointer); 412 413 void 414 remove_child(node_pointer); 415 416 void 417 remove_child(iterator); 418 419 void 420 replace_child(node_pointer, a_const_iterator, a_const_iterator, 421 a_const_pointer); 422 423 inline a_const_iterator 424 pref_b_it() const; 425 426 inline a_const_iterator 427 pref_e_it() const; 428 429 bool 430 should_be_mine(a_const_iterator, a_const_iterator, size_type, 431 a_const_pointer) const; 432 433 leaf_pointer 434 leftmost_descendant(); 435 436 leaf_const_pointer 437 leftmost_descendant() const; 438 439 leaf_pointer 440 rightmost_descendant(); 441 442 leaf_const_pointer 443 rightmost_descendant() const; 444 445 #ifdef _GLIBCXX_DEBUG 446 typedef typename base_type::node_debug_info node_debug_info; 447 448 virtual node_debug_info 449 assert_valid_imp(a_const_pointer, const char*, int) const; 450 #endif 451 452 size_type 453 get_e_ind() const 454 { return m_e_ind; } 455 456 private: 457 _Inode(const _Inode&); 458 459 size_type 460 get_begin_pos() const; 461 462 static __rebind_l s_leaf_alloc; 463 static __rebind_in s_inode_alloc; 464 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]; 469 }; 470 471 #define PB_DS_CONST_IT_C_DEC \ 472 _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 473 474 #define PB_DS_CONST_ODIR_IT_C_DEC \ 475 _CIter<Node, Leaf, Head, Inode, !Is_Forward_Iterator> 476 477 #define PB_DS_IT_C_DEC \ 478 _Iter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 479 480 #define PB_DS_ODIR_IT_C_DEC \ 481 _Iter<Node, Leaf, Head, Inode, !Is_Forward_Iterator> 482 483 484 /// Const iterator. 485 template<typename Node, typename Leaf, typename Head, typename Inode, 486 bool Is_Forward_Iterator> 487 class _CIter 488 { 489 public: 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; 493 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; 501 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; 510 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; 514 515 node_pointer m_p_nd; 516 517 _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd) 518 { } 519 520 _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other) 521 : m_p_nd(other.m_p_nd) 522 { } 523 524 _CIter& 525 operator=(const _CIter& other) 526 { 527 m_p_nd = other.m_p_nd; 528 return *this; 529 } 530 531 _CIter& 532 operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) 533 { 534 m_p_nd = other.m_p_nd; 535 return *this; 536 } 537 538 const_pointer 539 operator->() const 540 { 541 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); 542 return &static_cast<leaf_pointer>(m_p_nd)->value(); 543 } 544 545 const_reference 546 operator*() const 547 { 548 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); 549 return static_cast<leaf_pointer>(m_p_nd)->value(); 550 } 551 552 bool 553 operator==(const _CIter& other) const 554 { return m_p_nd == other.m_p_nd; } 555 556 bool 557 operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 558 { return m_p_nd == other.m_p_nd; } 559 560 bool 561 operator!=(const _CIter& other) const 562 { return m_p_nd != other.m_p_nd; } 563 564 bool 565 operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 566 { return m_p_nd != other.m_p_nd; } 567 568 _CIter& 569 operator++() 570 { 571 inc(integral_constant<int, Is_Forward_Iterator>()); 572 return *this; 573 } 574 575 _CIter 576 operator++(int) 577 { 578 _CIter ret_it(m_p_nd); 579 operator++(); 580 return ret_it; 581 } 582 583 _CIter& 584 operator--() 585 { 586 dec(integral_constant<int, Is_Forward_Iterator>()); 587 return *this; 588 } 589 590 _CIter 591 operator--(int) 592 { 593 _CIter ret_it(m_p_nd); 594 operator--(); 595 return ret_it; 596 } 597 598 protected: 599 void 600 inc(false_type) 601 { dec(true_type()); } 602 603 void 604 inc(true_type) 605 { 606 if (m_p_nd->m_type == head_node) 607 { 608 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min; 609 return; 610 } 611 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) 614 { 615 m_p_nd = p_y; 616 p_y = p_y->m_p_parent; 617 } 618 619 if (p_y->m_type == head_node) 620 { 621 m_p_nd = p_y; 622 return; 623 } 624 m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); 625 } 626 627 void 628 dec(false_type) 629 { inc(true_type()); } 630 631 void 632 dec(true_type) 633 { 634 if (m_p_nd->m_type == head_node) 635 { 636 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max; 637 return; 638 } 639 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) 642 { 643 m_p_nd = p_y; 644 p_y = p_y->m_p_parent; 645 } 646 647 if (p_y->m_type == head_node) 648 { 649 m_p_nd = p_y; 650 return; 651 } 652 m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); 653 } 654 655 static node_pointer 656 get_larger_sibling(node_pointer p_nd) 657 { 658 inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); 659 660 inode_iterator it = p_parent->begin(); 661 while (*it != p_nd) 662 ++it; 663 664 inode_iterator next_it = it; 665 ++next_it; 666 return (next_it == p_parent->end())? 0 : *next_it; 667 } 668 669 static node_pointer 670 get_smaller_sibling(node_pointer p_nd) 671 { 672 inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); 673 674 inode_iterator it = p_parent->begin(); 675 if (*it == p_nd) 676 return 0; 677 678 inode_iterator prev_it; 679 do 680 { 681 prev_it = it; 682 ++it; 683 if (*it == p_nd) 684 return *prev_it; 685 } 686 while (true); 687 688 _GLIBCXX_DEBUG_ASSERT(false); 689 return 0; 690 } 691 692 static leaf_pointer 693 leftmost_descendant(node_pointer p_nd) 694 { 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(); 698 } 699 700 static leaf_pointer 701 rightmost_descendant(node_pointer p_nd) 702 { 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(); 706 } 707 }; 708 709 710 /// Iterator. 711 template<typename Node, typename Leaf, typename Head, typename Inode, 712 bool Is_Forward_Iterator> 713 class _Iter 714 : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 715 { 716 public: 717 typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 718 base_type; 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; 724 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; 730 731 _Iter(node_pointer p_nd = 0) 732 : base_type(p_nd) { } 733 734 _Iter(const PB_DS_ODIR_IT_C_DEC& other) 735 : base_type(other.m_p_nd) { } 736 737 _Iter& 738 operator=(const _Iter& other) 739 { 740 base_type::m_p_nd = other.m_p_nd; 741 return *this; 742 } 743 744 _Iter& 745 operator=(const PB_DS_ODIR_IT_C_DEC& other) 746 { 747 base_type::m_p_nd = other.m_p_nd; 748 return *this; 749 } 750 751 pointer 752 operator->() const 753 { 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(); 756 } 757 758 reference 759 operator*() const 760 { 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(); 763 } 764 765 _Iter& 766 operator++() 767 { 768 base_type::operator++(); 769 return *this; 770 } 771 772 _Iter 773 operator++(int) 774 { 775 _Iter ret(base_type::m_p_nd); 776 operator++(); 777 return ret; 778 } 779 780 _Iter& 781 operator--() 782 { 783 base_type::operator--(); 784 return *this; 785 } 786 787 _Iter 788 operator--(int) 789 { 790 _Iter ret(base_type::m_p_nd); 791 operator--(); 792 return ret; 793 } 794 }; 795 796 #undef PB_DS_CONST_ODIR_IT_C_DEC 797 #undef PB_DS_ODIR_IT_C_DEC 798 799 800 #define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \ 801 _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> 802 803 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ 804 _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> 805 806 /// Node const iterator. 807 template<typename Node, 808 typename Leaf, 809 typename Head, 810 typename Inode, 811 typename _CIterator, 812 typename Iterator, 813 typename _Alloc> 814 class _Node_citer 815 { 816 protected: 817 typedef typename _Alloc::template rebind<Node> __rebind_n; 818 typedef typename __rebind_n::other::pointer node_pointer; 819 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; 823 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; 827 828 typedef typename Node::a_const_pointer a_const_pointer; 829 typedef typename Node::a_const_iterator a_const_iterator; 830 831 private: 832 a_const_iterator 833 pref_begin() const 834 { 835 if (m_p_nd->m_type == leaf_node) 836 { 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())); 839 } 840 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 841 return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it(); 842 } 843 844 a_const_iterator 845 pref_end() const 846 { 847 if (m_p_nd->m_type == leaf_node) 848 { 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())); 851 } 852 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 853 return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it(); 854 } 855 856 public: 857 typedef trivial_iterator_tag iterator_category; 858 typedef trivial_iterator_difference_type difference_type; 859 typedef typename _Alloc::size_type size_type; 860 861 typedef _CIterator value_type; 862 typedef value_type reference; 863 typedef value_type const_reference; 864 865 /// Metadata type. 866 typedef typename Node::metadata_type metadata_type; 867 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; 872 873 inline 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) 876 { } 877 878 /// Subtree valid prefix. 879 std::pair<a_const_iterator, a_const_iterator> 880 valid_prefix() const 881 { return std::make_pair(pref_begin(), pref_end()); } 882 883 /// Const access; returns the __const iterator* associated with 884 /// the current leaf. 885 const_reference 886 operator*() const 887 { 888 _GLIBCXX_DEBUG_ASSERT(num_children() == 0); 889 return _CIterator(m_p_nd); 890 } 891 892 /// Metadata access. 893 metadata_const_reference 894 get_metadata() const 895 { return m_p_nd->get_metadata(); } 896 897 /// Returns the number of children in the corresponding node. 898 size_type 899 num_children() const 900 { 901 if (m_p_nd->m_type == leaf_node) 902 return 0; 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()); 906 } 907 908 /// Returns a __const node __iterator to the corresponding node's 909 /// i-th child. 910 _Node_citer 911 get_child(size_type i) const 912 { 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(); 916 std::advance(it, i); 917 return _Node_citer(*it, m_p_traits); 918 } 919 920 /// Compares content to a different iterator object. 921 bool 922 operator==(const _Node_citer& other) const 923 { return m_p_nd == other.m_p_nd; } 924 925 /// Compares content (negatively) to a different iterator object. 926 bool 927 operator!=(const _Node_citer& other) const 928 { return m_p_nd != other.m_p_nd; } 929 930 node_pointer m_p_nd; 931 a_const_pointer m_p_traits; 932 }; 933 934 935 /// Node iterator. 936 template<typename Node, 937 typename Leaf, 938 typename Head, 939 typename Inode, 940 typename _CIterator, 941 typename Iterator, 942 typename _Alloc> 943 class _Node_iter 944 : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc> 945 { 946 private: 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; 954 955 public: 956 typedef typename base_type::size_type size_type; 957 958 typedef Iterator value_type; 959 typedef value_type reference; 960 typedef value_type const_reference; 961 962 _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0) 963 : base_type(p_nd, p_traits) 964 { } 965 966 /// Access; returns the iterator* associated with the current leaf. 967 reference 968 operator*() const 969 { 970 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); 971 return iterator(base_type::m_p_nd); 972 } 973 974 /// Returns a node __iterator to the corresponding node's i-th child. 975 _Node_iter 976 get_child(size_type i) const 977 { 978 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node); 979 980 typename Inode::iterator it = 981 static_cast<inode_pointer>(base_type::m_p_nd)->begin(); 982 983 std::advance(it, i); 984 return _Node_iter(*it, base_type::m_p_traits); 985 } 986 }; 987 }; 988 989 990 #define PB_DS_CLASS_T_DEC \ 991 template<typename _ATraits, typename Metadata> 992 993 #define PB_DS_CLASS_C_DEC \ 994 pat_trie_base::_Inode<_ATraits, Metadata> 995 996 PB_DS_CLASS_T_DEC 997 typename PB_DS_CLASS_C_DEC::__rebind_l 998 PB_DS_CLASS_C_DEC::s_leaf_alloc; 999 1000 PB_DS_CLASS_T_DEC 1001 typename PB_DS_CLASS_C_DEC::__rebind_in 1002 PB_DS_CLASS_C_DEC::s_inode_alloc; 1003 1004 PB_DS_CLASS_T_DEC 1005 inline typename PB_DS_CLASS_C_DEC::size_type 1006 PB_DS_CLASS_C_DEC:: 1007 get_pref_pos(a_const_iterator b_it, a_const_iterator e_it, 1008 a_const_pointer p_traits) const 1009 { 1010 if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind) 1011 return 0; 1012 std::advance(b_it, m_e_ind); 1013 return 1 + p_traits->e_pos(*b_it); 1014 } 1015 1016 PB_DS_CLASS_T_DEC 1017 PB_DS_CLASS_C_DEC:: 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) 1020 { 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)); 1024 } 1025 1026 PB_DS_CLASS_T_DEC 1027 void 1028 PB_DS_CLASS_C_DEC:: 1029 update_prefixes(a_const_pointer p_traits) 1030 { 1031 node_pointer p_first = *begin(); 1032 if (p_first->m_type == leaf_node) 1033 { 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())); 1036 } 1037 else 1038 { 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(); 1042 } 1043 m_pref_e_it = m_pref_b_it; 1044 std::advance(m_pref_e_it, m_e_ind); 1045 } 1046 1047 PB_DS_CLASS_T_DEC 1048 typename PB_DS_CLASS_C_DEC::const_iterator 1049 PB_DS_CLASS_C_DEC:: 1050 begin() const 1051 { 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); 1055 } 1056 1057 PB_DS_CLASS_T_DEC 1058 typename PB_DS_CLASS_C_DEC::iterator 1059 PB_DS_CLASS_C_DEC:: 1060 begin() 1061 { 1062 return iterator(m_a_p_children + get_begin_pos(), 1063 m_a_p_children + arr_size); 1064 } 1065 1066 PB_DS_CLASS_T_DEC 1067 typename PB_DS_CLASS_C_DEC::const_iterator 1068 PB_DS_CLASS_C_DEC:: 1069 end() const 1070 { 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); 1074 } 1075 1076 PB_DS_CLASS_T_DEC 1077 typename PB_DS_CLASS_C_DEC::iterator 1078 PB_DS_CLASS_C_DEC:: 1079 end() 1080 { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } 1081 1082 PB_DS_CLASS_T_DEC 1083 inline typename PB_DS_CLASS_C_DEC::node_pointer 1084 PB_DS_CLASS_C_DEC:: 1085 get_child_node(a_const_iterator b_it, a_const_iterator e_it, 1086 a_const_pointer p_traits) 1087 { 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]; 1091 } 1092 1093 PB_DS_CLASS_T_DEC 1094 inline typename PB_DS_CLASS_C_DEC::iterator 1095 PB_DS_CLASS_C_DEC:: 1096 get_child_it(a_const_iterator b_it, a_const_iterator e_it, 1097 a_const_pointer p_traits) 1098 { 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); 1103 } 1104 1105 PB_DS_CLASS_T_DEC 1106 inline typename PB_DS_CLASS_C_DEC::node_const_pointer 1107 PB_DS_CLASS_C_DEC:: 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)); } 1111 1112 PB_DS_CLASS_T_DEC 1113 typename PB_DS_CLASS_C_DEC::node_pointer 1114 PB_DS_CLASS_C_DEC:: 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) 1118 { 1119 if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) 1120 { 1121 if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, 1122 m_pref_e_it, true)) 1123 return leftmost_descendant(); 1124 return rightmost_descendant(); 1125 } 1126 1127 size_type i = get_pref_pos(b_it, e_it, p_traits); 1128 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1129 1130 if (m_a_p_children[i] != 0) 1131 return m_a_p_children[i]; 1132 1133 while (++i < arr_size) 1134 if (m_a_p_children[i] != 0) 1135 { 1136 const node_type& __nt = m_a_p_children[i]->m_type; 1137 node_pointer ret = m_a_p_children[i]; 1138 1139 if (__nt == leaf_node) 1140 return ret; 1141 1142 _GLIBCXX_DEBUG_ASSERT(__nt == i_node); 1143 inode_pointer inp = static_cast<inode_pointer>(ret); 1144 return inp->leftmost_descendant(); 1145 } 1146 1147 return rightmost_descendant(); 1148 } 1149 1150 PB_DS_CLASS_T_DEC 1151 inline typename PB_DS_CLASS_C_DEC::node_pointer 1152 PB_DS_CLASS_C_DEC:: 1153 add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it, 1154 a_const_pointer p_traits) 1155 { 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) 1159 { 1160 m_a_p_children[i] = p_nd; 1161 p_nd->m_p_parent = this; 1162 return p_nd; 1163 } 1164 return m_a_p_children[i]; 1165 } 1166 1167 PB_DS_CLASS_T_DEC 1168 typename PB_DS_CLASS_C_DEC::node_const_pointer 1169 PB_DS_CLASS_C_DEC:: 1170 get_join_child(node_const_pointer p_nd, 1171 a_const_pointer p_tr) const 1172 { 1173 node_pointer p = const_cast<node_pointer>(p_nd); 1174 return const_cast<inode_pointer>(this)->get_join_child(p, p_tr); 1175 } 1176 1177 PB_DS_CLASS_T_DEC 1178 typename PB_DS_CLASS_C_DEC::node_pointer 1179 PB_DS_CLASS_C_DEC:: 1180 get_join_child(node_pointer p_nd, a_const_pointer p_traits) 1181 { 1182 size_type i; 1183 a_const_iterator b_it; 1184 a_const_iterator e_it; 1185 if (p_nd->m_type == leaf_node) 1186 { 1187 leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd); 1188 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); 1193 } 1194 else 1195 { 1196 b_it = static_cast<inode_pointer>(p_nd)->pref_b_it(); 1197 e_it = static_cast<inode_pointer>(p_nd)->pref_e_it(); 1198 } 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]; 1202 } 1203 1204 PB_DS_CLASS_T_DEC 1205 void 1206 PB_DS_CLASS_C_DEC:: 1207 remove_child(node_pointer p_nd) 1208 { 1209 size_type i = 0; 1210 for (; i < arr_size; ++i) 1211 if (m_a_p_children[i] == p_nd) 1212 { 1213 m_a_p_children[i] = 0; 1214 return; 1215 } 1216 _GLIBCXX_DEBUG_ASSERT(i != arr_size); 1217 } 1218 1219 PB_DS_CLASS_T_DEC 1220 void 1221 PB_DS_CLASS_C_DEC:: 1222 remove_child(iterator it) 1223 { *it.m_p_p_cur = 0; } 1224 1225 PB_DS_CLASS_T_DEC 1226 void 1227 PB_DS_CLASS_C_DEC:: 1228 replace_child(node_pointer p_nd, a_const_iterator b_it, 1229 a_const_iterator e_it, 1230 a_const_pointer p_traits) 1231 { 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; 1236 } 1237 1238 PB_DS_CLASS_T_DEC 1239 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 1240 PB_DS_CLASS_C_DEC:: 1241 pref_b_it() const 1242 { return m_pref_b_it; } 1243 1244 PB_DS_CLASS_T_DEC 1245 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 1246 PB_DS_CLASS_C_DEC:: 1247 pref_e_it() const 1248 { return m_pref_e_it; } 1249 1250 PB_DS_CLASS_T_DEC 1251 bool 1252 PB_DS_CLASS_C_DEC:: 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 1256 { 1257 if (m_e_ind == 0) 1258 return true; 1259 1260 const size_type num_es = std::distance(b_it, e_it); 1261 if (num_es < m_e_ind) 1262 return false; 1263 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); 1268 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); 1273 1274 return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, 1275 value_e_it); 1276 } 1277 1278 PB_DS_CLASS_T_DEC 1279 typename PB_DS_CLASS_C_DEC::leaf_pointer 1280 PB_DS_CLASS_C_DEC:: 1281 leftmost_descendant() 1282 { 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(); 1288 } 1289 1290 PB_DS_CLASS_T_DEC 1291 typename PB_DS_CLASS_C_DEC::leaf_const_pointer 1292 PB_DS_CLASS_C_DEC:: 1293 leftmost_descendant() const 1294 { return const_cast<inode_pointer>(this)->leftmost_descendant(); } 1295 1296 PB_DS_CLASS_T_DEC 1297 typename PB_DS_CLASS_C_DEC::leaf_pointer 1298 PB_DS_CLASS_C_DEC:: 1299 rightmost_descendant() 1300 { 1301 const size_type num_children = std::distance(begin(), end()); 1302 _GLIBCXX_DEBUG_ASSERT(num_children >= 2); 1303 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(); 1311 } 1312 1313 PB_DS_CLASS_T_DEC 1314 typename PB_DS_CLASS_C_DEC::leaf_const_pointer 1315 PB_DS_CLASS_C_DEC:: 1316 rightmost_descendant() const 1317 { return const_cast<inode_pointer>(this)->rightmost_descendant(); } 1318 1319 PB_DS_CLASS_T_DEC 1320 typename PB_DS_CLASS_C_DEC::size_type 1321 PB_DS_CLASS_C_DEC:: 1322 get_begin_pos() const 1323 { 1324 size_type i = 0; 1325 for (; i < arr_size && m_a_p_children[i] == 0; ++i) 1326 ; 1327 return i; 1328 } 1329 1330 #ifdef _GLIBCXX_DEBUG 1331 PB_DS_CLASS_T_DEC 1332 typename PB_DS_CLASS_C_DEC::node_debug_info 1333 PB_DS_CLASS_C_DEC:: 1334 assert_valid_imp(a_const_pointer p_traits, 1335 const char* __file, int __line) const 1336 { 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); 1340 1341 for (typename _Inode::const_iterator it = begin(); it != end(); ++it) 1342 { 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, 1346 __file, __line); 1347 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)); 1351 } 1352 return std::make_pair(pref_b_it(), pref_e_it()); 1353 } 1354 #endif 1355 1356 #undef PB_DS_CLASS_T_DEC 1357 #undef PB_DS_CLASS_C_DEC 1358 } // namespace detail 1359 } // namespace __gnu_pbds 1360 1361 #endif 1362
