libstdc++
pat_trie_base.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2014 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
void trivial_iterator_difference_type
Prohibit moving trivial iterators.
node_type
Three types of nodes.
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
metadata_const_reference get_metadata() const
Metadata access.
bool operator==(const _Node_citer &other) const
Compares content to a different iterator object.
_Node_iter get_child(size_type i) const
Returns a node __iterator to the corresponding node's i-th child.
_Alloc::template rebind< metadata_type > __rebind_m
Const metadata reference type.
Forward iterators support a superset of input iterator operations.
_Node_citer get_child(size_type i) const
Returns a __const node __iterator to the corresponding node's i-th child.
Base type for PATRICIA trees.
auto end(_Container &__cont) -> decltype(__cont.end())
Return an iterator pointing to one past the last element of the container.
Definition: range_access.h:68
GNU extensions for policy-based data structures for public use.
Internal node type, PATRICIA tree.
bool operator!=(const _Node_citer &other) const
Compares content (negatively) to a different iterator object.
reference operator*() const
Access; returns the iterator* associated with the current leaf.
auto begin(_Container &__cont) -> decltype(__cont.begin())
Return an iterator pointing to the first element of the container.
Definition: range_access.h:48
Node::metadata_type metadata_type
Metadata type.
Metadata base primary template.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
std::pair< a_const_iterator, a_const_iterator > valid_prefix() const
Subtree valid prefix.
const_reference operator*() const
Const access; returns the __const iterator* associated with the current leaf.
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.
size_type num_children() const
Returns the number of children in the corresponding node.
Bidirectional iterators support a superset of forward iterator operations.
#define _GLIBCXX_DEBUG_VERIFY_AT(_Condition, _ErrorMessage, _File, _Line)
Definition: macros.h:41
Head node for PATRICIA tree.
Leaf node for PATRICIA tree.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.