1// -*- C++ -*- 2 3// Copyright (C) 2005-2022 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 46namespace __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 detail::rebind_traits<_Alloc, Metadata>::const_reference 72 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 detail::rebind_traits<_Alloc, _Node_base>::pointer 103 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 detail::rebind_traits<_Alloc, _ATraits>::const_pointer 112 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 detail::rebind_traits<_Alloc, base_type>::const_pointer 228 node_const_pointer; 229 230 typedef _Leaf<_ATraits, Metadata> leaf; 231 typedef typename detail::rebind_traits<_Alloc, leaf> __rebind_l; 232 typedef typename __rebind_l::pointer leaf_pointer; 233 typedef typename __rebind_l::const_pointer leaf_const_pointer; 234 235 typedef detail::rebind_traits<_Alloc, _Inode> __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 detail::rebind_traits<_Alloc, node_pointer> __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 rebind_traits<_Alloc, Node>::pointer node_pointer; 504 typedef typename rebind_traits<_Alloc, Leaf>::pointer leaf_pointer; 505 typedef typename rebind_traits<_Alloc, Leaf>::const_pointer leaf_const_pointer; 506 typedef typename rebind_traits<_Alloc, Head>::pointer head_pointer; 507 508 typedef typename rebind_traits<_Alloc, Inode>::pointer inode_pointer; 509 typedef typename Inode::iterator inode_iterator; 510 511 node_pointer m_p_nd; 512 513 _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd) 514 { } 515 516 _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other) 517 : m_p_nd(other.m_p_nd) 518 { } 519 520 _CIter& 521 operator=(const _CIter& other) 522 { 523 m_p_nd = other.m_p_nd; 524 return *this; 525 } 526 527 _CIter& 528 operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) 529 { 530 m_p_nd = other.m_p_nd; 531 return *this; 532 } 533 534 const_pointer 535 operator->() const 536 { 537 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); 538 return &static_cast<leaf_pointer>(m_p_nd)->value(); 539 } 540 541 const_reference 542 operator*() const 543 { 544 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); 545 return static_cast<leaf_pointer>(m_p_nd)->value(); 546 } 547 548 bool 549 operator==(const _CIter& other) const 550 { return m_p_nd == other.m_p_nd; } 551 552 bool 553 operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 554 { return m_p_nd == other.m_p_nd; } 555 556 bool 557 operator!=(const _CIter& other) const 558 { return m_p_nd != other.m_p_nd; } 559 560 bool 561 operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const 562 { return m_p_nd != other.m_p_nd; } 563 564 _CIter& 565 operator++() 566 { 567 inc(integral_constant<int, Is_Forward_Iterator>()); 568 return *this; 569 } 570 571 _CIter 572 operator++(int) 573 { 574 _CIter ret_it(m_p_nd); 575 operator++(); 576 return ret_it; 577 } 578 579 _CIter& 580 operator--() 581 { 582 dec(integral_constant<int, Is_Forward_Iterator>()); 583 return *this; 584 } 585 586 _CIter 587 operator--(int) 588 { 589 _CIter ret_it(m_p_nd); 590 operator--(); 591 return ret_it; 592 } 593 594 protected: 595 void 596 inc(false_type) 597 { dec(true_type()); } 598 599 void 600 inc(true_type) 601 { 602 if (m_p_nd->m_type == head_node) 603 { 604 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min; 605 return; 606 } 607 608 node_pointer p_y = m_p_nd->m_p_parent; 609 while (p_y->m_type != head_node && get_larger_sibling(m_p_nd) == 0) 610 { 611 m_p_nd = p_y; 612 p_y = p_y->m_p_parent; 613 } 614 615 if (p_y->m_type == head_node) 616 { 617 m_p_nd = p_y; 618 return; 619 } 620 m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); 621 } 622 623 void 624 dec(false_type) 625 { inc(true_type()); } 626 627 void 628 dec(true_type) 629 { 630 if (m_p_nd->m_type == head_node) 631 { 632 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max; 633 return; 634 } 635 636 node_pointer p_y = m_p_nd->m_p_parent; 637 while (p_y->m_type != head_node && get_smaller_sibling(m_p_nd) == 0) 638 { 639 m_p_nd = p_y; 640 p_y = p_y->m_p_parent; 641 } 642 643 if (p_y->m_type == head_node) 644 { 645 m_p_nd = p_y; 646 return; 647 } 648 m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); 649 } 650 651 static node_pointer 652 get_larger_sibling(node_pointer p_nd) 653 { 654 inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); 655 656 inode_iterator it = p_parent->begin(); 657 while (*it != p_nd) 658 ++it; 659 660 inode_iterator next_it = it; 661 ++next_it; 662 return (next_it == p_parent->end())? 0 : *next_it; 663 } 664 665 static node_pointer 666 get_smaller_sibling(node_pointer p_nd) 667 { 668 inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); 669 670 inode_iterator it = p_parent->begin(); 671 if (*it == p_nd) 672 return 0; 673 674 inode_iterator prev_it; 675 do 676 { 677 prev_it = it; 678 ++it; 679 if (*it == p_nd) 680 return *prev_it; 681 } 682 while (true); 683 684 _GLIBCXX_DEBUG_ASSERT(false); 685 return 0; 686 } 687 688 static leaf_pointer 689 leftmost_descendant(node_pointer p_nd) 690 { 691 if (p_nd->m_type == leaf_node) 692 return static_cast<leaf_pointer>(p_nd); 693 return static_cast<inode_pointer>(p_nd)->leftmost_descendant(); 694 } 695 696 static leaf_pointer 697 rightmost_descendant(node_pointer p_nd) 698 { 699 if (p_nd->m_type == leaf_node) 700 return static_cast<leaf_pointer>(p_nd); 701 return static_cast<inode_pointer>(p_nd)->rightmost_descendant(); 702 } 703 }; 704 705 706 /// Iterator. 707 template<typename Node, typename Leaf, typename Head, typename Inode, 708 bool Is_Forward_Iterator> 709 class _Iter 710 : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 711 { 712 public: 713 typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> 714 base_type; 715 typedef typename base_type::allocator_type allocator_type; 716 typedef typename base_type::type_traits type_traits; 717 typedef typename type_traits::value_type value_type; 718 typedef typename type_traits::pointer pointer; 719 typedef typename type_traits::reference reference; 720 721 typedef typename base_type::node_pointer node_pointer; 722 typedef typename base_type::leaf_pointer leaf_pointer; 723 typedef typename base_type::leaf_const_pointer leaf_const_pointer; 724 typedef typename base_type::head_pointer head_pointer; 725 typedef typename base_type::inode_pointer inode_pointer; 726 727 _Iter(node_pointer p_nd = 0) 728 : base_type(p_nd) { } 729 730 _Iter(const PB_DS_ODIR_IT_C_DEC& other) 731 : base_type(other.m_p_nd) { } 732 733 _Iter& 734 operator=(const _Iter& other) 735 { 736 base_type::m_p_nd = other.m_p_nd; 737 return *this; 738 } 739 740 _Iter& 741 operator=(const PB_DS_ODIR_IT_C_DEC& other) 742 { 743 base_type::m_p_nd = other.m_p_nd; 744 return *this; 745 } 746 747 pointer 748 operator->() const 749 { 750 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node); 751 return &static_cast<leaf_pointer>(base_type::m_p_nd)->value(); 752 } 753 754 reference 755 operator*() const 756 { 757 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node); 758 return static_cast<leaf_pointer>(base_type::m_p_nd)->value(); 759 } 760 761 _Iter& 762 operator++() 763 { 764 base_type::operator++(); 765 return *this; 766 } 767 768 _Iter 769 operator++(int) 770 { 771 _Iter ret(base_type::m_p_nd); 772 operator++(); 773 return ret; 774 } 775 776 _Iter& 777 operator--() 778 { 779 base_type::operator--(); 780 return *this; 781 } 782 783 _Iter 784 operator--(int) 785 { 786 _Iter ret(base_type::m_p_nd); 787 operator--(); 788 return ret; 789 } 790 }; 791 792#undef PB_DS_CONST_ODIR_IT_C_DEC 793#undef PB_DS_ODIR_IT_C_DEC 794 795 796#define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \ 797 _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> 798 799#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ 800 _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> 801 802 /// Node const iterator. 803 template<typename Node, 804 typename Leaf, 805 typename Head, 806 typename Inode, 807 typename _CIterator, 808 typename Iterator, 809 typename _Alloc> 810 class _Node_citer 811 { 812 protected: 813 typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer; 814 815 typedef typename rebind_traits<_Alloc, Leaf>::pointer leaf_pointer; 816 typedef typename rebind_traits<_Alloc, Leaf>::const_pointer leaf_const_pointer; 817 818 typedef typename rebind_traits<_Alloc, Inode>::pointer inode_pointer; 819 typedef typename rebind_traits<_Alloc, Inode>::const_pointer inode_const_pointer; 820 821 typedef typename Node::a_const_pointer a_const_pointer; 822 typedef typename Node::a_const_iterator a_const_iterator; 823 824 private: 825 a_const_iterator 826 pref_begin() const 827 { 828 if (m_p_nd->m_type == leaf_node) 829 { 830 leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd); 831 return m_p_traits->begin(m_p_traits->extract_key(lcp->value())); 832 } 833 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 834 return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it(); 835 } 836 837 a_const_iterator 838 pref_end() const 839 { 840 if (m_p_nd->m_type == leaf_node) 841 { 842 leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd); 843 return m_p_traits->end(m_p_traits->extract_key(lcp->value())); 844 } 845 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 846 return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it(); 847 } 848 849 public: 850 typedef trivial_iterator_tag iterator_category; 851 typedef trivial_iterator_difference_type difference_type; 852 typedef typename _Alloc::size_type size_type; 853 854 typedef _CIterator value_type; 855 typedef value_type reference; 856 typedef value_type const_reference; 857 858 /// Metadata type. 859 typedef typename Node::metadata_type metadata_type; 860 861 /// Const metadata reference type. 862 typedef typename rebind_traits<_Alloc, metadata_type>::const_reference metadata_const_reference; 863 864 inline 865 _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0) 866 : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) 867 { } 868 869 /// Subtree valid prefix. 870 std::pair<a_const_iterator, a_const_iterator> 871 valid_prefix() const 872 { return std::make_pair(pref_begin(), pref_end()); } 873 874 /// Const access; returns the __const iterator* associated with 875 /// the current leaf. 876 const_reference 877 operator*() const 878 { 879 _GLIBCXX_DEBUG_ASSERT(num_children() == 0); 880 return _CIterator(m_p_nd); 881 } 882 883 /// Metadata access. 884 metadata_const_reference 885 get_metadata() const 886 { return m_p_nd->get_metadata(); } 887 888 /// Returns the number of children in the corresponding node. 889 size_type 890 num_children() const 891 { 892 if (m_p_nd->m_type == leaf_node) 893 return 0; 894 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 895 inode_pointer inp = static_cast<inode_pointer>(m_p_nd); 896 return std::distance(inp->begin(), inp->end()); 897 } 898 899 /// Returns a __const node __iterator to the corresponding node's 900 /// i-th child. 901 _Node_citer 902 get_child(size_type i) const 903 { 904 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); 905 inode_pointer inp = static_cast<inode_pointer>(m_p_nd); 906 typename Inode::iterator it = inp->begin(); 907 std::advance(it, i); 908 return _Node_citer(*it, m_p_traits); 909 } 910 911 /// Compares content to a different iterator object. 912 bool 913 operator==(const _Node_citer& other) const 914 { return m_p_nd == other.m_p_nd; } 915 916 /// Compares content (negatively) to a different iterator object. 917 bool 918 operator!=(const _Node_citer& other) const 919 { return m_p_nd != other.m_p_nd; } 920 921 node_pointer m_p_nd; 922 a_const_pointer m_p_traits; 923 }; 924 925 926 /// Node iterator. 927 template<typename Node, 928 typename Leaf, 929 typename Head, 930 typename Inode, 931 typename _CIterator, 932 typename Iterator, 933 typename _Alloc> 934 class _Node_iter 935 : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc> 936 { 937 private: 938 typedef _Node_citer<Node, Leaf, Head, Inode, 939 _CIterator, Iterator, _Alloc> base_type; 940 typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer; 941 typedef typename base_type::inode_pointer inode_pointer; 942 typedef typename base_type::a_const_pointer a_const_pointer; 943 typedef Iterator iterator; 944 945 public: 946 typedef typename base_type::size_type size_type; 947 948 typedef Iterator value_type; 949 typedef value_type reference; 950 typedef value_type const_reference; 951 952 _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0) 953 : base_type(p_nd, p_traits) 954 { } 955 956 /// Access; returns the iterator* associated with the current leaf. 957 reference 958 operator*() const 959 { 960 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); 961 return iterator(base_type::m_p_nd); 962 } 963 964 /// Returns a node __iterator to the corresponding node's i-th child. 965 _Node_iter 966 get_child(size_type i) const 967 { 968 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node); 969 970 typename Inode::iterator it = 971 static_cast<inode_pointer>(base_type::m_p_nd)->begin(); 972 973 std::advance(it, i); 974 return _Node_iter(*it, base_type::m_p_traits); 975 } 976 }; 977 }; 978 979 980#define PB_DS_CLASS_T_DEC \ 981 template<typename _ATraits, typename Metadata> 982 983#define PB_DS_CLASS_C_DEC \ 984 pat_trie_base::_Inode<_ATraits, Metadata> 985 986 PB_DS_CLASS_T_DEC 987 typename PB_DS_CLASS_C_DEC::__rebind_l 988 PB_DS_CLASS_C_DEC::s_leaf_alloc; 989 990 PB_DS_CLASS_T_DEC 991 typename PB_DS_CLASS_C_DEC::__rebind_in 992 PB_DS_CLASS_C_DEC::s_inode_alloc; 993 994 PB_DS_CLASS_T_DEC 995 inline typename PB_DS_CLASS_C_DEC::size_type 996 PB_DS_CLASS_C_DEC:: 997 get_pref_pos(a_const_iterator b_it, a_const_iterator e_it, 998 a_const_pointer p_traits) const 999 { 1000 if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind) 1001 return 0; 1002 std::advance(b_it, m_e_ind); 1003 return 1 + p_traits->e_pos(*b_it); 1004 } 1005 1006 PB_DS_CLASS_T_DEC 1007 PB_DS_CLASS_C_DEC:: 1008 _Inode(size_type len, const a_const_iterator it) 1009 : base_type(i_node), m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) 1010 { 1011 std::advance(m_pref_e_it, m_e_ind); 1012 std::fill(m_a_p_children, m_a_p_children + arr_size, 1013 static_cast<node_pointer>(0)); 1014 } 1015 1016 PB_DS_CLASS_T_DEC 1017 void 1018 PB_DS_CLASS_C_DEC:: 1019 update_prefixes(a_const_pointer p_traits) 1020 { 1021 node_pointer p_first = *begin(); 1022 if (p_first->m_type == leaf_node) 1023 { 1024 leaf_const_pointer p = static_cast<leaf_const_pointer>(p_first); 1025 m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value())); 1026 } 1027 else 1028 { 1029 inode_pointer p = static_cast<inode_pointer>(p_first); 1030 _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node); 1031 m_pref_b_it = p->pref_b_it(); 1032 } 1033 m_pref_e_it = m_pref_b_it; 1034 std::advance(m_pref_e_it, m_e_ind); 1035 } 1036 1037 PB_DS_CLASS_T_DEC 1038 typename PB_DS_CLASS_C_DEC::const_iterator 1039 PB_DS_CLASS_C_DEC:: 1040 begin() const 1041 { 1042 typedef node_pointer_pointer pointer_type; 1043 pointer_type p = const_cast<pointer_type>(m_a_p_children); 1044 return const_iterator(p + get_begin_pos(), p + arr_size); 1045 } 1046 1047 PB_DS_CLASS_T_DEC 1048 typename PB_DS_CLASS_C_DEC::iterator 1049 PB_DS_CLASS_C_DEC:: 1050 begin() 1051 { 1052 return iterator(m_a_p_children + get_begin_pos(), 1053 m_a_p_children + arr_size); 1054 } 1055 1056 PB_DS_CLASS_T_DEC 1057 typename PB_DS_CLASS_C_DEC::const_iterator 1058 PB_DS_CLASS_C_DEC:: 1059 end() const 1060 { 1061 typedef node_pointer_pointer pointer_type; 1062 pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size; 1063 return const_iterator(p, p); 1064 } 1065 1066 PB_DS_CLASS_T_DEC 1067 typename PB_DS_CLASS_C_DEC::iterator 1068 PB_DS_CLASS_C_DEC:: 1069 end() 1070 { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } 1071 1072 PB_DS_CLASS_T_DEC 1073 inline typename PB_DS_CLASS_C_DEC::node_pointer 1074 PB_DS_CLASS_C_DEC:: 1075 get_child_node(a_const_iterator b_it, a_const_iterator e_it, 1076 a_const_pointer p_traits) 1077 { 1078 const size_type i = get_pref_pos(b_it, e_it, p_traits); 1079 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1080 return m_a_p_children[i]; 1081 } 1082 1083 PB_DS_CLASS_T_DEC 1084 inline typename PB_DS_CLASS_C_DEC::iterator 1085 PB_DS_CLASS_C_DEC:: 1086 get_child_it(a_const_iterator b_it, a_const_iterator e_it, 1087 a_const_pointer p_traits) 1088 { 1089 const size_type i = get_pref_pos(b_it, e_it, p_traits); 1090 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1091 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0); 1092 return iterator(m_a_p_children + i, m_a_p_children + i); 1093 } 1094 1095 PB_DS_CLASS_T_DEC 1096 inline typename PB_DS_CLASS_C_DEC::node_const_pointer 1097 PB_DS_CLASS_C_DEC:: 1098 get_child_node(a_const_iterator b_it, a_const_iterator e_it, 1099 a_const_pointer p_traits) const 1100 { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); } 1101 1102 PB_DS_CLASS_T_DEC 1103 typename PB_DS_CLASS_C_DEC::node_pointer 1104 PB_DS_CLASS_C_DEC:: 1105 get_lower_bound_child_node(a_const_iterator b_it, a_const_iterator e_it, 1106 size_type checked_ind, 1107 a_const_pointer p_traits) 1108 { 1109 if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) 1110 { 1111 if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, 1112 m_pref_e_it, true)) 1113 return leftmost_descendant(); 1114 return rightmost_descendant(); 1115 } 1116 1117 size_type i = get_pref_pos(b_it, e_it, p_traits); 1118 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1119 1120 if (m_a_p_children[i] != 0) 1121 return m_a_p_children[i]; 1122 1123 while (++i < arr_size) 1124 if (m_a_p_children[i] != 0) 1125 { 1126 const node_type& __nt = m_a_p_children[i]->m_type; 1127 node_pointer ret = m_a_p_children[i]; 1128 1129 if (__nt == leaf_node) 1130 return ret; 1131 1132 _GLIBCXX_DEBUG_ASSERT(__nt == i_node); 1133 inode_pointer inp = static_cast<inode_pointer>(ret); 1134 return inp->leftmost_descendant(); 1135 } 1136 1137 return rightmost_descendant(); 1138 } 1139 1140 PB_DS_CLASS_T_DEC 1141 inline typename PB_DS_CLASS_C_DEC::node_pointer 1142 PB_DS_CLASS_C_DEC:: 1143 add_child(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it, 1144 a_const_pointer p_traits) 1145 { 1146 const size_type i = get_pref_pos(b_it, e_it, p_traits); 1147 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1148 if (m_a_p_children[i] == 0) 1149 { 1150 m_a_p_children[i] = p_nd; 1151 p_nd->m_p_parent = this; 1152 return p_nd; 1153 } 1154 return m_a_p_children[i]; 1155 } 1156 1157 PB_DS_CLASS_T_DEC 1158 typename PB_DS_CLASS_C_DEC::node_const_pointer 1159 PB_DS_CLASS_C_DEC:: 1160 get_join_child(node_const_pointer p_nd, 1161 a_const_pointer p_tr) const 1162 { 1163 node_pointer p = const_cast<node_pointer>(p_nd); 1164 return const_cast<inode_pointer>(this)->get_join_child(p, p_tr); 1165 } 1166 1167 PB_DS_CLASS_T_DEC 1168 typename PB_DS_CLASS_C_DEC::node_pointer 1169 PB_DS_CLASS_C_DEC:: 1170 get_join_child(node_pointer p_nd, a_const_pointer p_traits) 1171 { 1172 size_type i; 1173 a_const_iterator b_it; 1174 a_const_iterator e_it; 1175 if (p_nd->m_type == leaf_node) 1176 { 1177 leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd); 1178 1179 typedef typename type_traits::key_const_reference kcr; 1180 kcr r_key = access_traits::extract_key(p->value()); 1181 b_it = p_traits->begin(r_key); 1182 e_it = p_traits->end(r_key); 1183 } 1184 else 1185 { 1186 b_it = static_cast<inode_pointer>(p_nd)->pref_b_it(); 1187 e_it = static_cast<inode_pointer>(p_nd)->pref_e_it(); 1188 } 1189 i = get_pref_pos(b_it, e_it, p_traits); 1190 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1191 return m_a_p_children[i]; 1192 } 1193 1194 PB_DS_CLASS_T_DEC 1195 void 1196 PB_DS_CLASS_C_DEC:: 1197 remove_child(node_pointer p_nd) 1198 { 1199 size_type i = 0; 1200 for (; i < arr_size; ++i) 1201 if (m_a_p_children[i] == p_nd) 1202 { 1203 m_a_p_children[i] = 0; 1204 return; 1205 } 1206 _GLIBCXX_DEBUG_ASSERT(i != arr_size); 1207 } 1208 1209 PB_DS_CLASS_T_DEC 1210 void 1211 PB_DS_CLASS_C_DEC:: 1212 remove_child(iterator it) 1213 { *it.m_p_p_cur = 0; } 1214 1215 PB_DS_CLASS_T_DEC 1216 void 1217 PB_DS_CLASS_C_DEC:: 1218 replace_child(node_pointer p_nd, a_const_iterator b_it, 1219 a_const_iterator e_it, 1220 a_const_pointer p_traits) 1221 { 1222 const size_type i = get_pref_pos(b_it, e_it, p_traits); 1223 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 1224 m_a_p_children[i] = p_nd; 1225 p_nd->m_p_parent = this; 1226 } 1227 1228 PB_DS_CLASS_T_DEC 1229 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 1230 PB_DS_CLASS_C_DEC:: 1231 pref_b_it() const 1232 { return m_pref_b_it; } 1233 1234 PB_DS_CLASS_T_DEC 1235 inline typename PB_DS_CLASS_C_DEC::a_const_iterator 1236 PB_DS_CLASS_C_DEC:: 1237 pref_e_it() const 1238 { return m_pref_e_it; } 1239 1240 PB_DS_CLASS_T_DEC 1241 bool 1242 PB_DS_CLASS_C_DEC:: 1243 should_be_mine(a_const_iterator b_it, a_const_iterator e_it, 1244 size_type checked_ind, 1245 a_const_pointer p_traits) const 1246 { 1247 if (m_e_ind == 0) 1248 return true; 1249 1250 const size_type num_es = std::distance(b_it, e_it); 1251 if (num_es < m_e_ind) 1252 return false; 1253 1254 a_const_iterator key_b_it = b_it; 1255 std::advance(key_b_it, checked_ind); 1256 a_const_iterator key_e_it = b_it; 1257 std::advance(key_e_it, m_e_ind); 1258 1259 a_const_iterator value_b_it = m_pref_b_it; 1260 std::advance(value_b_it, checked_ind); 1261 a_const_iterator value_e_it = m_pref_b_it; 1262 std::advance(value_e_it, m_e_ind); 1263 1264 return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, 1265 value_e_it); 1266 } 1267 1268 PB_DS_CLASS_T_DEC 1269 typename PB_DS_CLASS_C_DEC::leaf_pointer 1270 PB_DS_CLASS_C_DEC:: 1271 leftmost_descendant() 1272 { 1273 node_pointer p_pot = *begin(); 1274 if (p_pot->m_type == leaf_node) 1275 return (static_cast<leaf_pointer>(p_pot)); 1276 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node); 1277 return static_cast<inode_pointer>(p_pot)->leftmost_descendant(); 1278 } 1279 1280 PB_DS_CLASS_T_DEC 1281 typename PB_DS_CLASS_C_DEC::leaf_const_pointer 1282 PB_DS_CLASS_C_DEC:: 1283 leftmost_descendant() const 1284 { return const_cast<inode_pointer>(this)->leftmost_descendant(); } 1285 1286 PB_DS_CLASS_T_DEC 1287 typename PB_DS_CLASS_C_DEC::leaf_pointer 1288 PB_DS_CLASS_C_DEC:: 1289 rightmost_descendant() 1290 { 1291 const size_type num_children = std::distance(begin(), end()); 1292 _GLIBCXX_DEBUG_ASSERT(num_children >= 2); 1293 1294 iterator it = begin(); 1295 std::advance(it, num_children - 1); 1296 node_pointer p_pot =* it; 1297 if (p_pot->m_type == leaf_node) 1298 return static_cast<leaf_pointer>(p_pot); 1299 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node); 1300 return static_cast<inode_pointer>(p_pot)->rightmost_descendant(); 1301 } 1302 1303 PB_DS_CLASS_T_DEC 1304 typename PB_DS_CLASS_C_DEC::leaf_const_pointer 1305 PB_DS_CLASS_C_DEC:: 1306 rightmost_descendant() const 1307 { return const_cast<inode_pointer>(this)->rightmost_descendant(); } 1308 1309 PB_DS_CLASS_T_DEC 1310 typename PB_DS_CLASS_C_DEC::size_type 1311 PB_DS_CLASS_C_DEC:: 1312 get_begin_pos() const 1313 { 1314 size_type i = 0; 1315 for (; i < arr_size && m_a_p_children[i] == 0; ++i) 1316 ; 1317 return i; 1318 } 1319 1320#ifdef _GLIBCXX_DEBUG 1321 PB_DS_CLASS_T_DEC 1322 typename PB_DS_CLASS_C_DEC::node_debug_info 1323 PB_DS_CLASS_C_DEC:: 1324 assert_valid_imp(a_const_pointer p_traits, 1325 const char* __file, int __line) const 1326 { 1327 PB_DS_DEBUG_VERIFY(base_type::m_type == i_node); 1328 PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); 1329 PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2); 1330 1331 for (typename _Inode::const_iterator it = begin(); it != end(); ++it) 1332 { 1333 node_const_pointer p_nd = *it; 1334 PB_DS_DEBUG_VERIFY(p_nd->m_p_parent == this); 1335 node_debug_info child_ret = p_nd->assert_valid_imp(p_traits, 1336 __file, __line); 1337 1338 PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); 1339 PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); 1340 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)); 1341 } 1342 return std::make_pair(pref_b_it(), pref_e_it()); 1343 } 1344#endif 1345 1346#undef PB_DS_CLASS_T_DEC 1347#undef PB_DS_CLASS_C_DEC 1348 } // namespace detail 1349} // namespace __gnu_pbds 1350 1351#endif 1352