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