libstdc++
pat_trie_base.hpp
Go to the documentation of this file.
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.
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 */
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 {
86 typedef _Alloc allocator_type;
87 };
88
89
90 /// Node base.
91 template<typename _ATraits, typename Metadata>
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;
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
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 {
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 {
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 {
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;
228 node_const_pointer;
229
232 typedef typename __rebind_l::pointer leaf_pointer;
233 typedef typename __rebind_l::const_pointer leaf_const_pointer;
234
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:
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.
256 {
257 node_pointer_pointer m_p_p_cur;
258 node_pointer_pointer m_p_p_end;
259
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
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
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:
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
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
379 begin() const;
380
382 begin();
383
385 end() const;
386
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
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:
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>
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:
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.
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.
886 { return m_p_nd->get_metadata(); }
887
888 /// Returns the number of children in the corresponding node.
889 size_type
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.
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>
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.
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
void trivial_iterator_difference_type
Prohibit moving trivial iterators.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
GNU extensions for policy-based data structures for public use.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:187
Forward iterators support a superset of input iterator operations.
Bidirectional iterators support a superset of forward iterator operations.
A trivial iterator tag. Signifies that the iterators has none of std::iterators's movement abilities.
Represents no type, or absence of type, for template tricks.
Consistent API for accessing allocator-related types.
Base type for PATRICIA trees.
Metadata base primary template.
Internal node type, PATRICIA tree.
std::pair< a_const_iterator, a_const_iterator > valid_prefix() const
Subtree valid prefix.
bool operator!=(const _Node_citer &other) const
Compares content (negatively) to a different iterator object.
Node::metadata_type metadata_type
Metadata type.
bool operator==(const _Node_citer &other) const
Compares content to a different iterator object.
_Node_citer get_child(size_type i) const
Returns a __const node __iterator to the corresponding node's i-th child.
size_type num_children() const
Returns the number of children in the corresponding node.
rebind_traits< _Alloc, metadata_type >::const_reference metadata_const_reference
Const metadata reference type.
const_reference operator*() const
Const access; returns the __const iterator* associated with the current leaf.
metadata_const_reference get_metadata() const
Metadata access.
reference operator*() const
Access; returns the iterator* associated with the current leaf.
_Node_iter get_child(size_type i) const
Returns a node __iterator to the corresponding node's i-th child.