2011-05-07 François Dumont <francois.cppdevs@free.fr>
[official-gcc.git] / libstdc++-v3 / include / ext / pb_ds / detail / pat_trie_ / internal_node.hpp
blob9e30e65cd12505a8e98e49c46ae8237e0cc31ef3
1 // -*- C++ -*-
3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
5 //
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
10 // version.
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
35 // warranty.
37 /**
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>
47 namespace __gnu_pbds
49 namespace detail
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,
66 typename Metadata,
67 typename Allocator>
68 struct pat_trie_internal_node : public PB_DS_BASE_C_DEC
70 private:
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;
94 #ifdef _GLIBCXX_DEBUG
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;
100 #endif
102 inline size_type
103 get_pref_pos(const_e_iterator, const_e_iterator,
104 const_e_access_traits_pointer) const;
106 public:
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;
111 enum
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);
122 void
123 update_prefixes(const_e_access_traits_pointer);
125 const_iterator
126 begin() const;
128 iterator
129 begin();
131 const_iterator
132 end() const;
134 iterator
135 end();
137 inline node_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;
145 inline iterator
146 get_child_it(const_e_iterator, const_e_iterator,
147 const_e_access_traits_pointer);
149 inline node_pointer
150 get_lower_bound_child_node(const_e_iterator, const_e_iterator,
151 size_type, const_e_access_traits_pointer);
153 inline node_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;
160 inline node_pointer
161 get_join_child(node_pointer, const_e_access_traits_pointer);
163 void
164 remove_child(node_pointer p_nd);
166 iterator
167 remove_child(iterator it);
169 void
170 replace_child(node_pointer, const_e_iterator, const_e_iterator,
171 const_e_access_traits_pointer);
173 inline const_e_iterator
174 pref_b_it() const;
176 inline const_e_iterator
177 pref_e_it() const;
179 inline size_type
180 get_e_ind() const;
182 bool
183 should_be_mine(const_e_iterator, const_e_iterator, size_type,
184 const_e_access_traits_pointer) const;
186 leaf_pointer
187 leftmost_descendant();
189 const_leaf_pointer
190 leftmost_descendant() const;
192 leaf_pointer
193 rightmost_descendant();
195 const_leaf_pointer
196 rightmost_descendant() const;
198 #ifdef _GLIBCXX_DEBUG
199 size_type
200 e_ind() const;
201 #endif
203 private:
204 pat_trie_internal_node(const pat_trie_internal_node&);
206 size_type
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;
217 PB_DS_CLASS_T_DEC
218 typename PB_DS_CLASS_C_DEC::leaf_rebind
219 PB_DS_CLASS_C_DEC::s_leaf_alloc;
221 PB_DS_CLASS_T_DEC
222 typename PB_DS_CLASS_C_DEC::internal_node_rebind
223 PB_DS_CLASS_C_DEC::s_internal_node_alloc;
225 PB_DS_CLASS_T_DEC
226 inline typename PB_DS_CLASS_C_DEC::size_type
227 PB_DS_CLASS_C_DEC::
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)
232 return 0;
233 std::advance(b_it, m_e_ind);
234 return 1 + p_traits->e_pos(*b_it);
237 PB_DS_CLASS_T_DEC
238 PB_DS_CLASS_C_DEC::
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));
248 PB_DS_CLASS_T_DEC
249 void
250 PB_DS_CLASS_C_DEC::
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()));
259 else
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);
268 PB_DS_CLASS_T_DEC
269 typename PB_DS_CLASS_C_DEC::const_iterator
270 PB_DS_CLASS_C_DEC::
271 begin() const
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);
278 PB_DS_CLASS_T_DEC
279 typename PB_DS_CLASS_C_DEC::iterator
280 PB_DS_CLASS_C_DEC::
281 begin()
283 return iterator(m_a_p_children + get_begin_pos(),
284 m_a_p_children + arr_size);
287 PB_DS_CLASS_T_DEC
288 typename PB_DS_CLASS_C_DEC::const_iterator
289 PB_DS_CLASS_C_DEC::
290 end() const
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);
297 PB_DS_CLASS_T_DEC
298 typename PB_DS_CLASS_C_DEC::iterator
299 PB_DS_CLASS_C_DEC::
300 end()
301 { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }
303 PB_DS_CLASS_T_DEC
304 inline typename PB_DS_CLASS_C_DEC::node_pointer
305 PB_DS_CLASS_C_DEC::
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];
314 PB_DS_CLASS_T_DEC
315 inline typename PB_DS_CLASS_C_DEC::iterator
316 PB_DS_CLASS_C_DEC::
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);
326 PB_DS_CLASS_T_DEC
327 inline typename PB_DS_CLASS_C_DEC::const_node_pointer
328 PB_DS_CLASS_C_DEC::
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)); }
333 PB_DS_CLASS_T_DEC
334 typename PB_DS_CLASS_C_DEC::node_pointer
335 PB_DS_CLASS_C_DEC::
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();
367 PB_DS_CLASS_T_DEC
368 inline typename PB_DS_CLASS_C_DEC::node_pointer
369 PB_DS_CLASS_C_DEC::
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;
379 return p_nd;
381 return m_a_p_children[i];
384 PB_DS_CLASS_T_DEC
385 typename PB_DS_CLASS_C_DEC::const_node_pointer
386 PB_DS_CLASS_C_DEC::
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);
393 PB_DS_CLASS_T_DEC
394 typename PB_DS_CLASS_C_DEC::node_pointer
395 PB_DS_CLASS_C_DEC::
396 get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits)
398 size_type i;
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);
409 else
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];
419 PB_DS_CLASS_T_DEC
420 void
421 PB_DS_CLASS_C_DEC::
422 remove_child(node_pointer p_nd)
424 size_type i = 0;
425 for (; i < arr_size; ++i)
426 if (m_a_p_children[i] == p_nd)
428 m_a_p_children[i] = 0;
429 return;
431 _GLIBCXX_DEBUG_ASSERT(i != arr_size);
434 PB_DS_CLASS_T_DEC
435 typename PB_DS_CLASS_C_DEC::iterator
436 PB_DS_CLASS_C_DEC::
437 remove_child(iterator it)
439 iterator ret = it;
440 ++ret;
441 * it.m_p_p_cur = 0;
442 return ret;
445 PB_DS_CLASS_T_DEC
446 void
447 PB_DS_CLASS_C_DEC::
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;
458 PB_DS_CLASS_T_DEC
459 inline typename PB_DS_CLASS_C_DEC::const_e_iterator
460 PB_DS_CLASS_C_DEC::
461 pref_b_it() const
462 { return m_pref_b_it; }
464 PB_DS_CLASS_T_DEC
465 inline typename PB_DS_CLASS_C_DEC::const_e_iterator
466 PB_DS_CLASS_C_DEC::
467 pref_e_it() const
468 { return m_pref_e_it; }
470 PB_DS_CLASS_T_DEC
471 inline typename PB_DS_CLASS_C_DEC::size_type
472 PB_DS_CLASS_C_DEC::
473 get_e_ind() const
474 { return m_e_ind; }
476 PB_DS_CLASS_T_DEC
477 bool
478 PB_DS_CLASS_C_DEC::
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
483 if (m_e_ind == 0)
484 return true;
486 const size_type num_es = std::distance(b_it, e_it);
487 if (num_es < m_e_ind)
488 return false;
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,
501 value_e_it);
504 PB_DS_CLASS_T_DEC
505 typename PB_DS_CLASS_C_DEC::leaf_pointer
506 PB_DS_CLASS_C_DEC::
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();
516 PB_DS_CLASS_T_DEC
517 typename PB_DS_CLASS_C_DEC::const_leaf_pointer
518 PB_DS_CLASS_C_DEC::
519 leftmost_descendant() const
521 return const_cast<internal_node_pointer>(this)->leftmost_descendant();
524 PB_DS_CLASS_T_DEC
525 typename PB_DS_CLASS_C_DEC::leaf_pointer
526 PB_DS_CLASS_C_DEC::
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();
541 PB_DS_CLASS_T_DEC
542 typename PB_DS_CLASS_C_DEC::const_leaf_pointer
543 PB_DS_CLASS_C_DEC::
544 rightmost_descendant() const
546 return const_cast<internal_node_pointer>(this)->rightmost_descendant();
549 #ifdef _GLIBCXX_DEBUG
550 PB_DS_CLASS_T_DEC
551 typename PB_DS_CLASS_C_DEC::size_type
552 PB_DS_CLASS_C_DEC::
553 e_ind() const
554 { return m_e_ind; }
555 #endif
557 PB_DS_CLASS_T_DEC
558 typename PB_DS_CLASS_C_DEC::size_type
559 PB_DS_CLASS_C_DEC::
560 get_begin_pos() const
562 size_type i;
563 for (i = 0; i < arr_size && m_a_p_children[i] == 0; ++i)
565 return 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__) \
573 ,__file,__line)
575 PB_DS_CLASS_T_DEC
576 typename PB_DS_CLASS_C_DEC::subtree_debug_info
577 PB_DS_CLASS_C_DEC::
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();
586 it != end(); ++it)
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
600 #endif
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
610 #endif