libstdc++
pat_trie_base.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2015 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.
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  {
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  {
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;
227  typedef typename _Alloc::template rebind<base_type> __rebind_n;
228  typedef typename __rebind_n::other::const_pointer node_const_pointer;
229 
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.
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 
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 
379  begin() const;
380 
381  iterator
382  begin();
383 
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 
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:
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>
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:
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.
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.
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>
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
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
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
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
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
Leaf node for PATRICIA tree.
Bidirectional iterators support a superset of forward iterator operations.
Head node for PATRICIA tree.
const_reference operator*() const
Const access; returns the __const iterator* associated with the current leaf.
_Node_iter get_child(size_type i) const
Returns a node __iterator to the corresponding node&#39;s i-th child.
node_type
Three types of nodes.
_Alloc::template rebind< metadata_type > __rebind_m
Const metadata reference type.
reference operator*() const
Access; returns the iterator* associated with the current leaf.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Node::metadata_type metadata_type
Metadata type.
Forward iterators support a superset of input iterator operations.
bool operator==(const _Node_citer &other) const
Compares content to a different iterator object.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
bool operator!=(const _Node_citer &other) const
Compares content (negatively) to a different iterator object.
metadata_const_reference get_metadata() const
Metadata access.
void trivial_iterator_difference_type
Prohibit moving trivial iterators.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
A trivial iterator tag. Signifies that the iterators has none of std::iterators&#39;s movement abilities...
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:87
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:276
_Node_citer get_child(size_type i) const
Returns a __const node __iterator to the corresponding node&#39;s i-th child.
std::pair< a_const_iterator, a_const_iterator > valid_prefix() const
Subtree valid prefix.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
size_type num_children() const
Returns the number of children in the corresponding node.
Base type for PATRICIA trees.
Internal node type, PATRICIA tree.
Metadata base primary template.
Represents no type, or absence of type, for template tricks.
#define _GLIBCXX_DEBUG_VERIFY_AT(_Condition, _ErrorMessage, _File, _Line)
Definition: macros.h:41