3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the terms
8 // of the GNU General Public License as published by the Free Software
9 // Foundation; either version 3, or (at your option) any later
12 // This library is distributed in the hope that it will be useful, but
13 // WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 // General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
28 // Permission to use, copy, modify, sell, and distribute this software
29 // is hereby granted without fee, provided that the above copyright
30 // notice appears in all copies, and that both that copyright notice
31 // and this permission notice appear in supporting documentation. None
32 // of the above authors, nor IBM Haifa Research Laboratories, make any
33 // representation about the suitability of this software for any
34 // purpose. It is provided "as is" without express or implied
38 * @file internal_node.hpp
39 * Contains an internal PB_DS_BASE_C_DEC for a patricia tree.
42 #ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP
43 #define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP
45 #include <debug/debug.h>
51 #define PB_DS_CLASS_T_DEC \
52 template<typename Type_Traits, typename E_Access_Traits, \
53 typename Metadata, typename Allocator>
55 #define PB_DS_CLASS_C_DEC \
56 pat_trie_internal_node<Type_Traits, E_Access_Traits, Metadata, Allocator>
58 #define PB_DS_BASE_C_DEC \
59 pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator>
61 #define PB_DS_LEAF_C_DEC \
62 pat_trie_leaf<Type_Traits, E_Access_Traits, Metadata, Allocator>
64 template<typename Type_Traits
,
65 typename E_Access_Traits
,
68 struct pat_trie_internal_node
: public PB_DS_BASE_C_DEC
71 typedef PB_DS_BASE_C_DEC base_type
;
72 typedef Type_Traits type_traits
;
73 typedef typename
type_traits::value_type value_type
;
74 typedef typename
Allocator::size_type size_type
;
76 typedef E_Access_Traits e_access_traits
;
77 typedef typename
e_access_traits::const_iterator const_e_iterator
;
78 typedef typename
Allocator::template rebind
<e_access_traits
>::other access_rebind
;
79 typedef typename
access_rebind::const_pointer const_e_access_traits_pointer
;
81 typedef typename
Allocator::template rebind
<base_type
>::other base_rebind
;
82 typedef typename
base_rebind::pointer node_pointer
;
83 typedef typename
base_rebind::const_pointer const_node_pointer
;
85 typedef PB_DS_LEAF_C_DEC leaf
;
86 typedef typename
Allocator::template rebind
<leaf
>::other leaf_rebind
;
87 typedef typename
leaf_rebind::pointer leaf_pointer
;
88 typedef typename
leaf_rebind::const_pointer const_leaf_pointer
;
90 typedef typename
Allocator::template rebind
<pat_trie_internal_node
>::other internal_node_rebind
;
91 typedef typename
internal_node_rebind::pointer internal_node_pointer
;
92 typedef typename
internal_node_rebind::const_pointer const_internal_node_pointer
;
95 typedef typename
base_type::subtree_debug_info subtree_debug_info
;
97 virtual subtree_debug_info
98 assert_valid_imp(const_e_access_traits_pointer
,
99 const char* file
, int line
) const;
103 get_pref_pos(const_e_iterator
, const_e_iterator
,
104 const_e_access_traits_pointer
) const;
107 typedef typename
Allocator::template rebind
<node_pointer
>::other node_pointer_rebind
;
108 typedef typename
node_pointer_rebind::pointer node_pointer_pointer
;
109 typedef typename
node_pointer_rebind::reference node_pointer_reference
;
113 arr_size
= E_Access_Traits::max_size
+ 1
115 PB_DS_STATIC_ASSERT(min_arr_size
, arr_size
>= 2);
117 #include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp>
118 #include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp>
120 pat_trie_internal_node(size_type
, const const_e_iterator
);
123 update_prefixes(const_e_access_traits_pointer
);
138 get_child_node(const_e_iterator
, const_e_iterator
,
139 const_e_access_traits_pointer
);
141 inline const_node_pointer
142 get_child_node(const_e_iterator
, const_e_iterator
,
143 const_e_access_traits_pointer
) const;
146 get_child_it(const_e_iterator
, const_e_iterator
,
147 const_e_access_traits_pointer
);
150 get_lower_bound_child_node(const_e_iterator
, const_e_iterator
,
151 size_type
, const_e_access_traits_pointer
);
154 add_child(node_pointer
, const_e_iterator
, const_e_iterator
,
155 const_e_access_traits_pointer
);
157 inline const_node_pointer
158 get_join_child(const_node_pointer
, const_e_access_traits_pointer
) const;
161 get_join_child(node_pointer
, const_e_access_traits_pointer
);
164 remove_child(node_pointer p_nd
);
167 remove_child(iterator it
);
170 replace_child(node_pointer
, const_e_iterator
, const_e_iterator
,
171 const_e_access_traits_pointer
);
173 inline const_e_iterator
176 inline const_e_iterator
183 should_be_mine(const_e_iterator
, const_e_iterator
, size_type
,
184 const_e_access_traits_pointer
) const;
187 leftmost_descendant();
190 leftmost_descendant() const;
193 rightmost_descendant();
196 rightmost_descendant() const;
198 #ifdef _GLIBCXX_DEBUG
204 pat_trie_internal_node(const pat_trie_internal_node
&);
207 get_begin_pos() const;
209 const size_type m_e_ind
;
210 const_e_iterator m_pref_b_it
;
211 const_e_iterator m_pref_e_it
;
212 node_pointer m_a_p_children
[arr_size
];
213 static leaf_rebind s_leaf_alloc
;
214 static internal_node_rebind s_internal_node_alloc
;
218 typename
PB_DS_CLASS_C_DEC::leaf_rebind
219 PB_DS_CLASS_C_DEC::s_leaf_alloc
;
222 typename
PB_DS_CLASS_C_DEC::internal_node_rebind
223 PB_DS_CLASS_C_DEC::s_internal_node_alloc
;
226 inline typename
PB_DS_CLASS_C_DEC::size_type
228 get_pref_pos(const_e_iterator b_it
, const_e_iterator e_it
,
229 const_e_access_traits_pointer p_traits
) const
231 if (static_cast<std::size_t>(std::distance(b_it
, e_it
)) <= m_e_ind
)
233 std::advance(b_it
, m_e_ind
);
234 return 1 + p_traits
->e_pos(*b_it
);
239 pat_trie_internal_node(size_type len
, const const_e_iterator it
) :
240 PB_DS_BASE_C_DEC(pat_trie_internal_node_type
),
241 m_e_ind(len
), m_pref_b_it(it
), m_pref_e_it(it
)
243 std::advance(m_pref_e_it
, m_e_ind
);
244 std::fill(m_a_p_children
, m_a_p_children
+ arr_size
,
245 static_cast<node_pointer
>(0));
251 update_prefixes(const_e_access_traits_pointer p_traits
)
253 node_pointer p_first
= *begin();
254 if (p_first
->m_type
== pat_trie_leaf_node_type
)
256 const_leaf_pointer p
= static_cast<const_leaf_pointer
>(p_first
);
257 m_pref_b_it
= p_traits
->begin(e_access_traits::extract_key(p
->value()));
261 _GLIBCXX_DEBUG_ASSERT(p_first
->m_type
== pat_trie_internal_node_type
);
262 m_pref_b_it
= static_cast<internal_node_pointer
>(p_first
)->pref_b_it();
264 m_pref_e_it
= m_pref_b_it
;
265 std::advance(m_pref_e_it
, m_e_ind
);
269 typename
PB_DS_CLASS_C_DEC::const_iterator
273 typedef node_pointer_pointer pointer_type
;
274 pointer_type p
= const_cast<pointer_type
>(m_a_p_children
);
275 return const_iterator(p
+ get_begin_pos(), p
+ arr_size
);
279 typename
PB_DS_CLASS_C_DEC::iterator
283 return iterator(m_a_p_children
+ get_begin_pos(),
284 m_a_p_children
+ arr_size
);
288 typename
PB_DS_CLASS_C_DEC::const_iterator
292 typedef node_pointer_pointer pointer_type
;
293 pointer_type p
= const_cast<pointer_type
>(m_a_p_children
) + arr_size
;
294 return const_iterator(p
, p
);
298 typename
PB_DS_CLASS_C_DEC::iterator
301 { return iterator(m_a_p_children
+ arr_size
, m_a_p_children
+ arr_size
); }
304 inline typename
PB_DS_CLASS_C_DEC::node_pointer
306 get_child_node(const_e_iterator b_it
, const_e_iterator e_it
,
307 const_e_access_traits_pointer p_traits
)
309 const size_type i
= get_pref_pos(b_it
, e_it
, p_traits
);
310 _GLIBCXX_DEBUG_ASSERT(i
< arr_size
);
311 return m_a_p_children
[i
];
315 inline typename
PB_DS_CLASS_C_DEC::iterator
317 get_child_it(const_e_iterator b_it
, const_e_iterator e_it
,
318 const_e_access_traits_pointer p_traits
)
320 const size_type i
= get_pref_pos(b_it
, e_it
, p_traits
);
321 _GLIBCXX_DEBUG_ASSERT(i
< arr_size
);
322 _GLIBCXX_DEBUG_ASSERT(m_a_p_children
[i
] != 0);
323 return iterator(m_a_p_children
+ i
, m_a_p_children
+ i
);
327 inline typename
PB_DS_CLASS_C_DEC::const_node_pointer
329 get_child_node(const_e_iterator b_it
, const_e_iterator e_it
,
330 const_e_access_traits_pointer p_traits
) const
331 { return const_cast<node_pointer
>(get_child_node(b_it
, e_it
, p_traits
)); }
334 typename
PB_DS_CLASS_C_DEC::node_pointer
336 get_lower_bound_child_node(const_e_iterator b_it
, const_e_iterator e_it
,
337 size_type checked_ind
,
338 const_e_access_traits_pointer p_traits
)
340 if (!should_be_mine(b_it
, e_it
, checked_ind
, p_traits
))
342 if (p_traits
->cmp_prefixes(b_it
, e_it
, m_pref_b_it
, m_pref_e_it
, true))
343 return leftmost_descendant();
344 return rightmost_descendant();
347 size_type i
= get_pref_pos(b_it
, e_it
, p_traits
);
348 _GLIBCXX_DEBUG_ASSERT(i
< arr_size
);
350 if (m_a_p_children
[i
] != 0)
351 return m_a_p_children
[i
];
353 while (++i
< arr_size
)
354 if (m_a_p_children
[i
] != 0)
356 if (m_a_p_children
[i
]->m_type
== pat_trie_leaf_node_type
)
357 return m_a_p_children
[i
];
359 _GLIBCXX_DEBUG_ASSERT(m_a_p_children
[i
]->m_type
== pat_trie_internal_node_type
);
361 return static_cast<internal_node_pointer
>(m_a_p_children
[i
])->leftmost_descendant();
364 return rightmost_descendant();
368 inline typename
PB_DS_CLASS_C_DEC::node_pointer
370 add_child(node_pointer p_nd
, const_e_iterator b_it
, const_e_iterator e_it
,
371 const_e_access_traits_pointer p_traits
)
373 const size_type i
= get_pref_pos(b_it
, e_it
, p_traits
);
374 _GLIBCXX_DEBUG_ASSERT(i
< arr_size
);
375 if (m_a_p_children
[i
] == 0)
377 m_a_p_children
[i
] = p_nd
;
378 p_nd
->m_p_parent
= this;
381 return m_a_p_children
[i
];
385 typename
PB_DS_CLASS_C_DEC::const_node_pointer
387 get_join_child(const_node_pointer p_nd
, const_e_access_traits_pointer p_traits
) const
389 node_pointer p
= const_cast<node_pointer
>(p_nd
);
390 return const_cast<internal_node_pointer
>(this)->get_join_child(p
, p_traits
);
394 typename
PB_DS_CLASS_C_DEC::node_pointer
396 get_join_child(node_pointer p_nd
, const_e_access_traits_pointer p_traits
)
399 const_e_iterator b_it
;
400 const_e_iterator e_it
;
401 if (p_nd
->m_type
== pat_trie_leaf_node_type
)
403 typename
Type_Traits::const_key_reference r_key
=
404 e_access_traits::extract_key(static_cast<const_leaf_pointer
>(p_nd
)->value());
406 b_it
= p_traits
->begin(r_key
);
407 e_it
= p_traits
->end(r_key
);
411 b_it
= static_cast<internal_node_pointer
>(p_nd
)->pref_b_it();
412 e_it
= static_cast<internal_node_pointer
>(p_nd
)->pref_e_it();
414 i
= get_pref_pos(b_it
, e_it
, p_traits
);
415 _GLIBCXX_DEBUG_ASSERT(i
< arr_size
);
416 return m_a_p_children
[i
];
422 remove_child(node_pointer p_nd
)
425 for (; i
< arr_size
; ++i
)
426 if (m_a_p_children
[i
] == p_nd
)
428 m_a_p_children
[i
] = 0;
431 _GLIBCXX_DEBUG_ASSERT(i
!= arr_size
);
435 typename
PB_DS_CLASS_C_DEC::iterator
437 remove_child(iterator it
)
448 replace_child(node_pointer p_nd
, const_e_iterator b_it
,
449 const_e_iterator e_it
,
450 const_e_access_traits_pointer p_traits
)
452 const size_type i
= get_pref_pos(b_it
, e_it
, p_traits
);
453 _GLIBCXX_DEBUG_ASSERT(i
< arr_size
);
454 m_a_p_children
[i
] = p_nd
;
455 p_nd
->m_p_parent
= this;
459 inline typename
PB_DS_CLASS_C_DEC::const_e_iterator
462 { return m_pref_b_it
; }
465 inline typename
PB_DS_CLASS_C_DEC::const_e_iterator
468 { return m_pref_e_it
; }
471 inline typename
PB_DS_CLASS_C_DEC::size_type
479 should_be_mine(const_e_iterator b_it
, const_e_iterator e_it
,
480 size_type checked_ind
,
481 const_e_access_traits_pointer p_traits
) const
486 const size_type num_es
= std::distance(b_it
, e_it
);
487 if (num_es
< m_e_ind
)
490 const_e_iterator key_b_it
= b_it
;
491 std::advance(key_b_it
, checked_ind
);
492 const_e_iterator key_e_it
= b_it
;
493 std::advance(key_e_it
, m_e_ind
);
495 const_e_iterator value_b_it
= m_pref_b_it
;
496 std::advance(value_b_it
, checked_ind
);
497 const_e_iterator value_e_it
= m_pref_b_it
;
498 std::advance(value_e_it
, m_e_ind
);
500 return p_traits
->equal_prefixes(key_b_it
, key_e_it
, value_b_it
,
505 typename
PB_DS_CLASS_C_DEC::leaf_pointer
507 leftmost_descendant()
509 node_pointer p_pot
=* begin();
510 if (p_pot
->m_type
== pat_trie_leaf_node_type
)
511 return (static_cast<leaf_pointer
>(p_pot
));
512 _GLIBCXX_DEBUG_ASSERT(p_pot
->m_type
== pat_trie_internal_node_type
);
513 return static_cast<internal_node_pointer
>(p_pot
)->leftmost_descendant();
517 typename
PB_DS_CLASS_C_DEC::const_leaf_pointer
519 leftmost_descendant() const
521 return const_cast<internal_node_pointer
>(this)->leftmost_descendant();
525 typename
PB_DS_CLASS_C_DEC::leaf_pointer
527 rightmost_descendant()
529 const size_type num_children
= std::distance(begin(), end());
530 _GLIBCXX_DEBUG_ASSERT(num_children
>= 2);
532 iterator it
= begin();
533 std::advance(it
, num_children
- 1);
534 node_pointer p_pot
=* it
;
535 if (p_pot
->m_type
== pat_trie_leaf_node_type
)
536 return static_cast<leaf_pointer
>(p_pot
);
537 _GLIBCXX_DEBUG_ASSERT(p_pot
->m_type
== pat_trie_internal_node_type
);
538 return static_cast<internal_node_pointer
>(p_pot
)->rightmost_descendant();
542 typename
PB_DS_CLASS_C_DEC::const_leaf_pointer
544 rightmost_descendant() const
546 return const_cast<internal_node_pointer
>(this)->rightmost_descendant();
549 #ifdef _GLIBCXX_DEBUG
551 typename
PB_DS_CLASS_C_DEC::size_type
558 typename
PB_DS_CLASS_C_DEC::size_type
560 get_begin_pos() const
563 for (i
= 0; i
< arr_size
&& m_a_p_children
[i
] == 0; ++i
)
568 #ifdef _GLIBCXX_DEBUG
569 # define PB_DS_DEBUG_VERIFY(_Cond) \
570 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \
571 _M_message(#_Cond" assertion from %1;:%2;") \
572 ._M_string(__FILE__)._M_integer(__LINE__) \
576 typename
PB_DS_CLASS_C_DEC::subtree_debug_info
578 assert_valid_imp(const_e_access_traits_pointer p_traits
,
579 const char* __file
, int __line
) const
581 PB_DS_DEBUG_VERIFY(base_type::m_type
== pat_trie_internal_node_type
);
582 PB_DS_DEBUG_VERIFY(static_cast<size_type
>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind
);
583 PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2);
585 for (typename
pat_trie_internal_node::const_iterator it
= begin();
588 const_node_pointer p_nd
=* it
;
589 PB_DS_DEBUG_VERIFY(p_nd
->m_p_parent
== this);
590 subtree_debug_info child_ret
=
591 p_nd
->assert_valid_imp(p_traits
, __file
, __line
);
593 PB_DS_DEBUG_VERIFY(static_cast<size_type
>(std::distance(child_ret
.first
, child_ret
.second
)) >= m_e_ind
);
594 PB_DS_DEBUG_VERIFY(should_be_mine(child_ret
.first
, child_ret
.second
, 0, p_traits
));
595 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
));
597 return std::make_pair(pref_b_it(), pref_e_it());
599 # undef PB_DS_DEBUG_VERIFY
602 #undef PB_DS_CLASS_T_DEC
603 #undef PB_DS_CLASS_C_DEC
604 #undef PB_DS_BASE_C_DEC
605 #undef PB_DS_LEAF_C_DEC
607 } // namespace detail
608 } // namespace __gnu_pbds