]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
8fc81078 | 3 | // Copyright (C) 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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/>. | |
4569a895 AT |
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 internal_node.hpp | |
38 | * Contains an internal PB_DS_BASE_C_DEC for a patricia tree. | |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP | |
42 | #define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP | |
43 | ||
47bea7b8 | 44 | #include <debug/debug.h> |
4569a895 | 45 | |
5e11f978 | 46 | namespace __gnu_pbds |
4569a895 AT |
47 | { |
48 | namespace detail | |
49 | { | |
81ee09de BK |
50 | #define PB_DS_CLASS_T_DEC \ |
51 | template<typename Type_Traits, typename E_Access_Traits, \ | |
52 | typename Metadata, typename Allocator> | |
53 | ||
54 | #define PB_DS_CLASS_C_DEC \ | |
55 | pat_trie_internal_node<Type_Traits, E_Access_Traits, Metadata, Allocator> | |
56 | ||
57 | #define PB_DS_BASE_C_DEC \ | |
58 | pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> | |
59 | ||
60 | #define PB_DS_LEAF_C_DEC \ | |
61 | pat_trie_leaf<Type_Traits, E_Access_Traits, Metadata, Allocator> | |
4569a895 | 62 | |
4569a895 | 63 | template<typename Type_Traits, |
81ee09de BK |
64 | typename E_Access_Traits, |
65 | typename Metadata, | |
66 | typename Allocator> | |
4569a895 AT |
67 | struct pat_trie_internal_node : public PB_DS_BASE_C_DEC |
68 | { | |
4569a895 | 69 | private: |
81ee09de BK |
70 | typedef PB_DS_BASE_C_DEC base_type; |
71 | typedef Type_Traits type_traits; | |
72 | typedef typename type_traits::value_type value_type; | |
73 | typedef typename Allocator::size_type size_type; | |
4569a895 AT |
74 | |
75 | typedef E_Access_Traits e_access_traits; | |
4569a895 | 76 | typedef typename e_access_traits::const_iterator const_e_iterator; |
81ee09de BK |
77 | typedef typename Allocator::template rebind<e_access_traits>::other access_rebind; |
78 | typedef typename access_rebind::const_pointer const_e_access_traits_pointer; | |
4569a895 | 79 | |
81ee09de BK |
80 | typedef typename Allocator::template rebind<base_type>::other base_rebind; |
81 | typedef typename base_rebind::pointer node_pointer; | |
82 | typedef typename base_rebind::const_pointer const_node_pointer; | |
4569a895 AT |
83 | |
84 | typedef PB_DS_LEAF_C_DEC leaf; | |
81ee09de BK |
85 | typedef typename Allocator::template rebind<leaf>::other leaf_rebind; |
86 | typedef typename leaf_rebind::pointer leaf_pointer; | |
87 | typedef typename leaf_rebind::const_pointer const_leaf_pointer; | |
4569a895 | 88 | |
81ee09de BK |
89 | typedef typename Allocator::template rebind<pat_trie_internal_node>::other internal_node_rebind; |
90 | typedef typename internal_node_rebind::pointer internal_node_pointer; | |
91 | typedef typename internal_node_rebind::const_pointer const_internal_node_pointer; | |
4569a895 | 92 | |
47bea7b8 | 93 | #ifdef _GLIBCXX_DEBUG |
81ee09de | 94 | typedef typename base_type::subtree_debug_info subtree_debug_info; |
4569a895 | 95 | |
81ee09de BK |
96 | virtual subtree_debug_info |
97 | assert_valid_imp(const_e_access_traits_pointer) const; | |
98 | #endif | |
4569a895 | 99 | |
4569a895 | 100 | inline size_type |
81ee09de BK |
101 | get_pref_pos(const_e_iterator, const_e_iterator, |
102 | const_e_access_traits_pointer) const; | |
4569a895 AT |
103 | |
104 | public: | |
81ee09de BK |
105 | typedef typename Allocator::template rebind<node_pointer>::other node_pointer_rebind; |
106 | typedef typename node_pointer_rebind::pointer node_pointer_pointer; | |
107 | typedef typename node_pointer_rebind::reference node_pointer_reference; | |
4569a895 | 108 | |
81ee09de BK |
109 | enum |
110 | { | |
111 | arr_size = E_Access_Traits::max_size + 1 | |
112 | }; | |
113 | PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); | |
4569a895 AT |
114 | |
115 | #include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp> | |
116 | #include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp> | |
117 | ||
81ee09de | 118 | pat_trie_internal_node(size_type, const const_e_iterator); |
4569a895 AT |
119 | |
120 | void | |
81ee09de | 121 | update_prefixes(const_e_access_traits_pointer); |
4569a895 AT |
122 | |
123 | const_iterator | |
124 | begin() const; | |
125 | ||
126 | iterator | |
127 | begin(); | |
128 | ||
129 | const_iterator | |
130 | end() const; | |
131 | ||
132 | iterator | |
133 | end(); | |
134 | ||
135 | inline node_pointer | |
81ee09de BK |
136 | get_child_node(const_e_iterator, const_e_iterator, |
137 | const_e_access_traits_pointer); | |
4569a895 AT |
138 | |
139 | inline const_node_pointer | |
81ee09de BK |
140 | get_child_node(const_e_iterator, const_e_iterator, |
141 | const_e_access_traits_pointer) const; | |
4569a895 AT |
142 | |
143 | inline iterator | |
81ee09de BK |
144 | get_child_it(const_e_iterator, const_e_iterator, |
145 | const_e_access_traits_pointer); | |
4569a895 AT |
146 | |
147 | inline node_pointer | |
81ee09de BK |
148 | get_lower_bound_child_node(const_e_iterator, const_e_iterator, |
149 | size_type, const_e_access_traits_pointer); | |
4569a895 AT |
150 | |
151 | inline node_pointer | |
81ee09de BK |
152 | add_child(node_pointer, const_e_iterator, const_e_iterator, |
153 | const_e_access_traits_pointer); | |
4569a895 AT |
154 | |
155 | inline const_node_pointer | |
81ee09de | 156 | get_join_child(const_node_pointer, const_e_access_traits_pointer) const; |
4569a895 AT |
157 | |
158 | inline node_pointer | |
81ee09de | 159 | get_join_child(node_pointer, const_e_access_traits_pointer); |
4569a895 AT |
160 | |
161 | void | |
162 | remove_child(node_pointer p_nd); | |
163 | ||
164 | iterator | |
165 | remove_child(iterator it); | |
166 | ||
167 | void | |
81ee09de BK |
168 | replace_child(node_pointer, const_e_iterator, const_e_iterator, |
169 | const_e_access_traits_pointer); | |
4569a895 AT |
170 | |
171 | inline const_e_iterator | |
172 | pref_b_it() const; | |
173 | ||
174 | inline const_e_iterator | |
175 | pref_e_it() const; | |
176 | ||
177 | inline size_type | |
178 | get_e_ind() const; | |
179 | ||
180 | bool | |
81ee09de BK |
181 | should_be_mine(const_e_iterator, const_e_iterator, size_type, |
182 | const_e_access_traits_pointer) const; | |
4569a895 AT |
183 | |
184 | leaf_pointer | |
185 | leftmost_descendant(); | |
186 | ||
187 | const_leaf_pointer | |
188 | leftmost_descendant() const; | |
189 | ||
190 | leaf_pointer | |
191 | rightmost_descendant(); | |
192 | ||
193 | const_leaf_pointer | |
194 | rightmost_descendant() const; | |
195 | ||
47bea7b8 | 196 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
197 | size_type |
198 | e_ind() const; | |
81ee09de | 199 | #endif |
4569a895 AT |
200 | |
201 | private: | |
81ee09de | 202 | pat_trie_internal_node(const pat_trie_internal_node&); |
4569a895 AT |
203 | |
204 | size_type | |
205 | get_begin_pos() const; | |
206 | ||
4569a895 | 207 | const size_type m_e_ind; |
4569a895 AT |
208 | const_e_iterator m_pref_b_it; |
209 | const_e_iterator m_pref_e_it; | |
4569a895 | 210 | node_pointer m_a_p_children[arr_size]; |
81ee09de BK |
211 | static leaf_rebind s_leaf_alloc; |
212 | static internal_node_rebind s_internal_node_alloc; | |
4569a895 AT |
213 | }; |
214 | ||
215 | PB_DS_CLASS_T_DEC | |
81ee09de | 216 | typename PB_DS_CLASS_C_DEC::leaf_rebind |
4569a895 AT |
217 | PB_DS_CLASS_C_DEC::s_leaf_alloc; |
218 | ||
219 | PB_DS_CLASS_T_DEC | |
81ee09de | 220 | typename PB_DS_CLASS_C_DEC::internal_node_rebind |
4569a895 AT |
221 | PB_DS_CLASS_C_DEC::s_internal_node_alloc; |
222 | ||
223 | PB_DS_CLASS_T_DEC | |
224 | inline typename PB_DS_CLASS_C_DEC::size_type | |
225 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
226 | get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, |
227 | const_e_access_traits_pointer p_traits) const | |
4569a895 | 228 | { |
8fc81078 | 229 | if (static_cast<std::size_t>(std::distance(b_it, e_it)) <= m_e_ind) |
81ee09de | 230 | return 0; |
4569a895 | 231 | std::advance(b_it, m_e_ind); |
81ee09de | 232 | return 1 + p_traits->e_pos(*b_it); |
4569a895 AT |
233 | } |
234 | ||
235 | PB_DS_CLASS_T_DEC | |
236 | PB_DS_CLASS_C_DEC:: | |
1ab79481 | 237 | pat_trie_internal_node(size_type len, const const_e_iterator it) : |
4569a895 | 238 | PB_DS_BASE_C_DEC(pat_trie_internal_node_type), |
1ab79481 | 239 | m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) |
4569a895 AT |
240 | { |
241 | std::advance(m_pref_e_it, m_e_ind); | |
4569a895 | 242 | std::fill(m_a_p_children, m_a_p_children + arr_size, |
8fc81078 | 243 | static_cast<node_pointer>(0)); |
4569a895 AT |
244 | } |
245 | ||
246 | PB_DS_CLASS_T_DEC | |
247 | void | |
248 | PB_DS_CLASS_C_DEC:: | |
249 | update_prefixes(const_e_access_traits_pointer p_traits) | |
250 | { | |
81ee09de | 251 | node_pointer p_first = *begin(); |
4569a895 | 252 | if (p_first->m_type == pat_trie_leaf_node_type) |
81ee09de BK |
253 | { |
254 | const_leaf_pointer p = static_cast<const_leaf_pointer>(p_first); | |
255 | m_pref_b_it = p_traits->begin(e_access_traits::extract_key(p->value())); | |
256 | } | |
4569a895 AT |
257 | else |
258 | { | |
47bea7b8 | 259 | _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type); |
4569a895 AT |
260 | m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it(); |
261 | } | |
4569a895 | 262 | m_pref_e_it = m_pref_b_it; |
4569a895 AT |
263 | std::advance(m_pref_e_it, m_e_ind); |
264 | } | |
265 | ||
266 | PB_DS_CLASS_T_DEC | |
267 | typename PB_DS_CLASS_C_DEC::const_iterator | |
268 | PB_DS_CLASS_C_DEC:: | |
269 | begin() const | |
270 | { | |
81ee09de BK |
271 | typedef node_pointer_pointer pointer_type; |
272 | pointer_type p = const_cast<pointer_type>(m_a_p_children); | |
273 | return const_iterator(p + get_begin_pos(), p + arr_size); | |
4569a895 AT |
274 | } |
275 | ||
276 | PB_DS_CLASS_T_DEC | |
277 | typename PB_DS_CLASS_C_DEC::iterator | |
278 | PB_DS_CLASS_C_DEC:: | |
279 | begin() | |
280 | { | |
81ee09de BK |
281 | return iterator(m_a_p_children + get_begin_pos(), |
282 | m_a_p_children + arr_size); | |
4569a895 AT |
283 | } |
284 | ||
285 | PB_DS_CLASS_T_DEC | |
286 | typename PB_DS_CLASS_C_DEC::const_iterator | |
287 | PB_DS_CLASS_C_DEC:: | |
288 | end() const | |
289 | { | |
81ee09de BK |
290 | typedef node_pointer_pointer pointer_type; |
291 | pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size; | |
292 | return const_iterator(p, p); | |
4569a895 AT |
293 | } |
294 | ||
295 | PB_DS_CLASS_T_DEC | |
296 | typename PB_DS_CLASS_C_DEC::iterator | |
297 | PB_DS_CLASS_C_DEC:: | |
298 | end() | |
81ee09de | 299 | { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } |
4569a895 AT |
300 | |
301 | PB_DS_CLASS_T_DEC | |
302 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
303 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
304 | get_child_node(const_e_iterator b_it, const_e_iterator e_it, |
305 | const_e_access_traits_pointer p_traits) | |
4569a895 | 306 | { |
81ee09de | 307 | const size_type i = get_pref_pos(b_it, e_it, p_traits); |
47bea7b8 | 308 | _GLIBCXX_DEBUG_ASSERT(i < arr_size); |
81ee09de | 309 | return m_a_p_children[i]; |
4569a895 AT |
310 | } |
311 | ||
312 | PB_DS_CLASS_T_DEC | |
313 | inline typename PB_DS_CLASS_C_DEC::iterator | |
314 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
315 | get_child_it(const_e_iterator b_it, const_e_iterator e_it, |
316 | const_e_access_traits_pointer p_traits) | |
4569a895 | 317 | { |
81ee09de | 318 | const size_type i = get_pref_pos(b_it, e_it, p_traits); |
47bea7b8 | 319 | _GLIBCXX_DEBUG_ASSERT(i < arr_size); |
8fc81078 | 320 | _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != 0); |
81ee09de | 321 | return iterator(m_a_p_children + i, m_a_p_children + i); |
4569a895 AT |
322 | } |
323 | ||
324 | PB_DS_CLASS_T_DEC | |
325 | inline typename PB_DS_CLASS_C_DEC::const_node_pointer | |
326 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
327 | get_child_node(const_e_iterator b_it, const_e_iterator e_it, |
328 | const_e_access_traits_pointer p_traits) const | |
329 | { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); } | |
4569a895 AT |
330 | |
331 | PB_DS_CLASS_T_DEC | |
332 | typename PB_DS_CLASS_C_DEC::node_pointer | |
333 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
334 | get_lower_bound_child_node(const_e_iterator b_it, const_e_iterator e_it, |
335 | size_type checked_ind, | |
336 | const_e_access_traits_pointer p_traits) | |
4569a895 AT |
337 | { |
338 | if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) | |
339 | { | |
340 | if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true)) | |
81ee09de BK |
341 | return leftmost_descendant(); |
342 | return rightmost_descendant(); | |
4569a895 AT |
343 | } |
344 | ||
81ee09de | 345 | size_type i = get_pref_pos(b_it, e_it, p_traits); |
47bea7b8 | 346 | _GLIBCXX_DEBUG_ASSERT(i < arr_size); |
4569a895 | 347 | |
8fc81078 | 348 | if (m_a_p_children[i] != 0) |
81ee09de | 349 | return m_a_p_children[i]; |
4569a895 AT |
350 | |
351 | while (++i < arr_size) | |
8fc81078 | 352 | if (m_a_p_children[i] != 0) |
4569a895 AT |
353 | { |
354 | if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type) | |
81ee09de | 355 | return m_a_p_children[i]; |
4569a895 | 356 | |
47bea7b8 | 357 | _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type); |
4569a895 | 358 | |
81ee09de | 359 | return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant(); |
4569a895 AT |
360 | } |
361 | ||
81ee09de | 362 | return rightmost_descendant(); |
4569a895 AT |
363 | } |
364 | ||
365 | PB_DS_CLASS_T_DEC | |
366 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
367 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
368 | add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, |
369 | const_e_access_traits_pointer p_traits) | |
4569a895 | 370 | { |
81ee09de | 371 | const size_type i = get_pref_pos(b_it, e_it, p_traits); |
47bea7b8 | 372 | _GLIBCXX_DEBUG_ASSERT(i < arr_size); |
8fc81078 | 373 | if (m_a_p_children[i] == 0) |
4569a895 AT |
374 | { |
375 | m_a_p_children[i] = p_nd; | |
4569a895 | 376 | p_nd->m_p_parent = this; |
81ee09de | 377 | return p_nd; |
4569a895 | 378 | } |
81ee09de | 379 | return m_a_p_children[i]; |
4569a895 AT |
380 | } |
381 | ||
382 | PB_DS_CLASS_T_DEC | |
383 | typename PB_DS_CLASS_C_DEC::const_node_pointer | |
384 | PB_DS_CLASS_C_DEC:: | |
385 | get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const | |
386 | { | |
81ee09de BK |
387 | node_pointer p = const_cast<node_pointer>(p_nd); |
388 | return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits); | |
4569a895 AT |
389 | } |
390 | ||
391 | PB_DS_CLASS_T_DEC | |
392 | typename PB_DS_CLASS_C_DEC::node_pointer | |
393 | PB_DS_CLASS_C_DEC:: | |
394 | get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits) | |
395 | { | |
396 | size_type i; | |
4569a895 AT |
397 | const_e_iterator b_it; |
398 | const_e_iterator e_it; | |
4569a895 AT |
399 | if (p_nd->m_type == pat_trie_leaf_node_type) |
400 | { | |
401 | typename Type_Traits::const_key_reference r_key = | |
81ee09de | 402 | e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value()); |
4569a895 AT |
403 | |
404 | b_it = p_traits->begin(r_key); | |
405 | e_it = p_traits->end(r_key); | |
406 | } | |
407 | else | |
408 | { | |
409 | b_it = static_cast<internal_node_pointer>(p_nd)->pref_b_it(); | |
410 | e_it = static_cast<internal_node_pointer>(p_nd)->pref_e_it(); | |
411 | } | |
4569a895 | 412 | i = get_pref_pos(b_it, e_it, p_traits); |
47bea7b8 | 413 | _GLIBCXX_DEBUG_ASSERT(i < arr_size); |
81ee09de | 414 | return m_a_p_children[i]; |
4569a895 AT |
415 | } |
416 | ||
417 | PB_DS_CLASS_T_DEC | |
418 | void | |
419 | PB_DS_CLASS_C_DEC:: | |
420 | remove_child(node_pointer p_nd) | |
421 | { | |
422 | size_type i = 0; | |
4569a895 AT |
423 | for (; i < arr_size; ++i) |
424 | if (m_a_p_children[i] == p_nd) | |
425 | { | |
8fc81078 | 426 | m_a_p_children[i] = 0; |
4569a895 AT |
427 | return; |
428 | } | |
47bea7b8 | 429 | _GLIBCXX_DEBUG_ASSERT(i != arr_size); |
4569a895 AT |
430 | } |
431 | ||
432 | PB_DS_CLASS_T_DEC | |
433 | typename PB_DS_CLASS_C_DEC::iterator | |
434 | PB_DS_CLASS_C_DEC:: | |
435 | remove_child(iterator it) | |
436 | { | |
437 | iterator ret = it; | |
4569a895 | 438 | ++ret; |
8fc81078 | 439 | * it.m_p_p_cur = 0; |
81ee09de | 440 | return ret; |
4569a895 AT |
441 | } |
442 | ||
443 | PB_DS_CLASS_T_DEC | |
444 | void | |
445 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
446 | replace_child(node_pointer p_nd, const_e_iterator b_it, |
447 | const_e_iterator e_it, | |
448 | const_e_access_traits_pointer p_traits) | |
4569a895 | 449 | { |
81ee09de | 450 | const size_type i = get_pref_pos(b_it, e_it, p_traits); |
47bea7b8 | 451 | _GLIBCXX_DEBUG_ASSERT(i < arr_size); |
4569a895 | 452 | m_a_p_children[i] = p_nd; |
4569a895 AT |
453 | p_nd->m_p_parent = this; |
454 | } | |
455 | ||
456 | PB_DS_CLASS_T_DEC | |
457 | inline typename PB_DS_CLASS_C_DEC::const_e_iterator | |
458 | PB_DS_CLASS_C_DEC:: | |
459 | pref_b_it() const | |
81ee09de | 460 | { return m_pref_b_it; } |
4569a895 AT |
461 | |
462 | PB_DS_CLASS_T_DEC | |
463 | inline typename PB_DS_CLASS_C_DEC::const_e_iterator | |
464 | PB_DS_CLASS_C_DEC:: | |
465 | pref_e_it() const | |
81ee09de | 466 | { return m_pref_e_it; } |
4569a895 AT |
467 | |
468 | PB_DS_CLASS_T_DEC | |
469 | inline typename PB_DS_CLASS_C_DEC::size_type | |
470 | PB_DS_CLASS_C_DEC:: | |
471 | get_e_ind() const | |
81ee09de | 472 | { return m_e_ind; } |
4569a895 AT |
473 | |
474 | PB_DS_CLASS_T_DEC | |
475 | bool | |
476 | PB_DS_CLASS_C_DEC:: | |
81ee09de BK |
477 | should_be_mine(const_e_iterator b_it, const_e_iterator e_it, |
478 | size_type checked_ind, | |
479 | const_e_access_traits_pointer p_traits) const | |
4569a895 AT |
480 | { |
481 | if (m_e_ind == 0) | |
81ee09de | 482 | return true; |
4569a895 AT |
483 | |
484 | const size_type num_es = std::distance(b_it, e_it); | |
4569a895 | 485 | if (num_es < m_e_ind) |
81ee09de | 486 | return false; |
4569a895 AT |
487 | |
488 | const_e_iterator key_b_it = b_it; | |
489 | std::advance(key_b_it, checked_ind); | |
490 | const_e_iterator key_e_it = b_it; | |
491 | std::advance(key_e_it, m_e_ind); | |
492 | ||
493 | const_e_iterator value_b_it = m_pref_b_it; | |
494 | std::advance(value_b_it, checked_ind); | |
495 | const_e_iterator value_e_it = m_pref_b_it; | |
496 | std::advance(value_e_it, m_e_ind); | |
497 | ||
81ee09de BK |
498 | return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, |
499 | value_e_it); | |
4569a895 AT |
500 | } |
501 | ||
502 | PB_DS_CLASS_T_DEC | |
503 | typename PB_DS_CLASS_C_DEC::leaf_pointer | |
504 | PB_DS_CLASS_C_DEC:: | |
505 | leftmost_descendant() | |
506 | { | |
507 | node_pointer p_pot =* begin(); | |
4569a895 AT |
508 | if (p_pot->m_type == pat_trie_leaf_node_type) |
509 | return (static_cast<leaf_pointer>(p_pot)); | |
47bea7b8 | 510 | _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); |
81ee09de | 511 | return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant(); |
4569a895 AT |
512 | } |
513 | ||
514 | PB_DS_CLASS_T_DEC | |
515 | typename PB_DS_CLASS_C_DEC::const_leaf_pointer | |
516 | PB_DS_CLASS_C_DEC:: | |
517 | leftmost_descendant() const | |
518 | { | |
81ee09de | 519 | return const_cast<internal_node_pointer>(this)->leftmost_descendant(); |
4569a895 AT |
520 | } |
521 | ||
522 | PB_DS_CLASS_T_DEC | |
523 | typename PB_DS_CLASS_C_DEC::leaf_pointer | |
524 | PB_DS_CLASS_C_DEC:: | |
525 | rightmost_descendant() | |
526 | { | |
527 | const size_type num_children = std::distance(begin(), end()); | |
47bea7b8 | 528 | _GLIBCXX_DEBUG_ASSERT(num_children >= 2); |
4569a895 AT |
529 | |
530 | iterator it = begin(); | |
531 | std::advance(it, num_children - 1); | |
4569a895 | 532 | node_pointer p_pot =* it; |
4569a895 | 533 | if (p_pot->m_type == pat_trie_leaf_node_type) |
81ee09de | 534 | return static_cast<leaf_pointer>(p_pot); |
47bea7b8 | 535 | _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); |
81ee09de | 536 | return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant(); |
4569a895 AT |
537 | } |
538 | ||
539 | PB_DS_CLASS_T_DEC | |
540 | typename PB_DS_CLASS_C_DEC::const_leaf_pointer | |
541 | PB_DS_CLASS_C_DEC:: | |
542 | rightmost_descendant() const | |
543 | { | |
81ee09de | 544 | return const_cast<internal_node_pointer>(this)->rightmost_descendant(); |
4569a895 AT |
545 | } |
546 | ||
47bea7b8 | 547 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
548 | PB_DS_CLASS_T_DEC |
549 | typename PB_DS_CLASS_C_DEC::size_type | |
550 | PB_DS_CLASS_C_DEC:: | |
551 | e_ind() const | |
81ee09de | 552 | { return m_e_ind; } |
47bea7b8 | 553 | #endif |
4569a895 AT |
554 | |
555 | PB_DS_CLASS_T_DEC | |
556 | typename PB_DS_CLASS_C_DEC::size_type | |
557 | PB_DS_CLASS_C_DEC:: | |
558 | get_begin_pos() const | |
559 | { | |
560 | size_type i; | |
8fc81078 | 561 | for (i = 0; i < arr_size && m_a_p_children[i] == 0; ++i) |
4569a895 | 562 | ; |
81ee09de | 563 | return i; |
4569a895 AT |
564 | } |
565 | ||
47bea7b8 | 566 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
567 | PB_DS_CLASS_T_DEC |
568 | typename PB_DS_CLASS_C_DEC::subtree_debug_info | |
569 | PB_DS_CLASS_C_DEC:: | |
570 | assert_valid_imp(const_e_access_traits_pointer p_traits) const | |
571 | { | |
47bea7b8 BK |
572 | _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_internal_node_type); |
573 | _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); | |
574 | _GLIBCXX_DEBUG_ASSERT(std::distance(begin(), end()) >= 2); | |
4569a895 AT |
575 | |
576 | for (typename pat_trie_internal_node::const_iterator it = begin(); | |
577 | it != end(); ++it) | |
578 | { | |
579 | const_node_pointer p_nd =* it; | |
47bea7b8 | 580 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this); |
4569a895 AT |
581 | subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits); |
582 | ||
47bea7b8 BK |
583 | _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); |
584 | _GLIBCXX_DEBUG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); | |
585 | _GLIBCXX_DEBUG_ASSERT(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast<size_type>(it.m_p_p_cur - m_a_p_children)); | |
4569a895 | 586 | } |
81ee09de | 587 | return std::make_pair(pref_b_it(), pref_e_it()); |
4569a895 | 588 | } |
47bea7b8 | 589 | #endif |
4569a895 AT |
590 | |
591 | #undef PB_DS_CLASS_T_DEC | |
4569a895 | 592 | #undef PB_DS_CLASS_C_DEC |
4569a895 | 593 | #undef PB_DS_BASE_C_DEC |
4569a895 | 594 | #undef PB_DS_LEAF_C_DEC |
4569a895 | 595 | |
4569a895 | 596 | } // namespace detail |
5e11f978 | 597 | } // namespace __gnu_pbds |
4569a895 | 598 | |
81ee09de | 599 | #endif |