1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file internal_node.hpp 44169691Skan * Contains an internal PB_DS_BASE_C_DEC for a patricia tree. 45169691Skan */ 46169691Skan 47169691Skan#ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP 48169691Skan#define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP 49169691Skan 50169691Skan#include <debug/debug.h> 51169691Skan 52169691Skannamespace pb_ds 53169691Skan{ 54169691Skan namespace detail 55169691Skan { 56169691Skan#define PB_DS_CLASS_T_DEC \ 57169691Skan template<typename Type_Traits, typename E_Access_Traits, \ 58169691Skan typename Metadata, typename Allocator> 59169691Skan 60169691Skan#define PB_DS_CLASS_C_DEC \ 61169691Skan pat_trie_internal_node<Type_Traits, E_Access_Traits, Metadata, Allocator> 62169691Skan 63169691Skan#define PB_DS_BASE_C_DEC \ 64169691Skan pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> 65169691Skan 66169691Skan#define PB_DS_LEAF_C_DEC \ 67169691Skan pat_trie_leaf<Type_Traits, E_Access_Traits, Metadata, Allocator> 68169691Skan 69169691Skan#define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 70169691Skan typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> UNIQUE##static_assert_type 71169691Skan 72169691Skan template<typename Type_Traits, 73169691Skan typename E_Access_Traits, 74169691Skan typename Metadata, 75169691Skan typename Allocator> 76169691Skan struct pat_trie_internal_node : public PB_DS_BASE_C_DEC 77169691Skan { 78169691Skan private: 79169691Skan typedef PB_DS_BASE_C_DEC base_type; 80169691Skan typedef Type_Traits type_traits; 81169691Skan typedef typename type_traits::value_type value_type; 82169691Skan typedef typename Allocator::size_type size_type; 83169691Skan 84169691Skan typedef E_Access_Traits e_access_traits; 85169691Skan typedef typename e_access_traits::const_iterator const_e_iterator; 86169691Skan typedef typename Allocator::template rebind<e_access_traits>::other access_rebind; 87169691Skan typedef typename access_rebind::const_pointer const_e_access_traits_pointer; 88169691Skan 89169691Skan typedef typename Allocator::template rebind<base_type>::other base_rebind; 90169691Skan typedef typename base_rebind::pointer node_pointer; 91169691Skan typedef typename base_rebind::const_pointer const_node_pointer; 92169691Skan 93169691Skan typedef PB_DS_LEAF_C_DEC leaf; 94169691Skan typedef typename Allocator::template rebind<leaf>::other leaf_rebind; 95169691Skan typedef typename leaf_rebind::pointer leaf_pointer; 96169691Skan typedef typename leaf_rebind::const_pointer const_leaf_pointer; 97169691Skan 98169691Skan typedef typename Allocator::template rebind<pat_trie_internal_node>::other internal_node_rebind; 99169691Skan typedef typename internal_node_rebind::pointer internal_node_pointer; 100169691Skan typedef typename internal_node_rebind::const_pointer const_internal_node_pointer; 101169691Skan 102169691Skan#ifdef _GLIBCXX_DEBUG 103169691Skan typedef typename base_type::subtree_debug_info subtree_debug_info; 104169691Skan 105169691Skan virtual subtree_debug_info 106169691Skan assert_valid_imp(const_e_access_traits_pointer) const; 107169691Skan#endif 108169691Skan 109169691Skan inline size_type 110169691Skan get_pref_pos(const_e_iterator, const_e_iterator, 111169691Skan const_e_access_traits_pointer) const; 112169691Skan 113169691Skan public: 114169691Skan typedef typename Allocator::template rebind<node_pointer>::other node_pointer_rebind; 115169691Skan typedef typename node_pointer_rebind::pointer node_pointer_pointer; 116169691Skan typedef typename node_pointer_rebind::reference node_pointer_reference; 117169691Skan 118169691Skan enum 119169691Skan { 120169691Skan arr_size = E_Access_Traits::max_size + 1 121169691Skan }; 122169691Skan PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); 123169691Skan 124169691Skan#include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp> 125169691Skan#include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp> 126169691Skan 127169691Skan pat_trie_internal_node(size_type, const const_e_iterator); 128169691Skan 129169691Skan void 130169691Skan update_prefixes(const_e_access_traits_pointer); 131169691Skan 132169691Skan const_iterator 133169691Skan begin() const; 134169691Skan 135169691Skan iterator 136169691Skan begin(); 137169691Skan 138169691Skan const_iterator 139169691Skan end() const; 140169691Skan 141169691Skan iterator 142169691Skan end(); 143169691Skan 144169691Skan inline node_pointer 145169691Skan get_child_node(const_e_iterator, const_e_iterator, 146169691Skan const_e_access_traits_pointer); 147169691Skan 148169691Skan inline const_node_pointer 149169691Skan get_child_node(const_e_iterator, const_e_iterator, 150169691Skan const_e_access_traits_pointer) const; 151169691Skan 152169691Skan inline iterator 153169691Skan get_child_it(const_e_iterator, const_e_iterator, 154169691Skan const_e_access_traits_pointer); 155169691Skan 156169691Skan inline node_pointer 157169691Skan get_lower_bound_child_node(const_e_iterator, const_e_iterator, 158169691Skan size_type, const_e_access_traits_pointer); 159169691Skan 160169691Skan inline node_pointer 161169691Skan add_child(node_pointer, const_e_iterator, const_e_iterator, 162169691Skan const_e_access_traits_pointer); 163169691Skan 164169691Skan inline const_node_pointer 165169691Skan get_join_child(const_node_pointer, const_e_access_traits_pointer) const; 166169691Skan 167169691Skan inline node_pointer 168169691Skan get_join_child(node_pointer, const_e_access_traits_pointer); 169169691Skan 170169691Skan void 171169691Skan remove_child(node_pointer p_nd); 172169691Skan 173169691Skan iterator 174169691Skan remove_child(iterator it); 175169691Skan 176169691Skan void 177169691Skan replace_child(node_pointer, const_e_iterator, const_e_iterator, 178169691Skan const_e_access_traits_pointer); 179169691Skan 180169691Skan inline const_e_iterator 181169691Skan pref_b_it() const; 182169691Skan 183169691Skan inline const_e_iterator 184169691Skan pref_e_it() const; 185169691Skan 186169691Skan inline size_type 187169691Skan get_e_ind() const; 188169691Skan 189169691Skan bool 190169691Skan should_be_mine(const_e_iterator, const_e_iterator, size_type, 191169691Skan const_e_access_traits_pointer) const; 192169691Skan 193169691Skan leaf_pointer 194169691Skan leftmost_descendant(); 195169691Skan 196169691Skan const_leaf_pointer 197169691Skan leftmost_descendant() const; 198169691Skan 199169691Skan leaf_pointer 200169691Skan rightmost_descendant(); 201169691Skan 202169691Skan const_leaf_pointer 203169691Skan rightmost_descendant() const; 204169691Skan 205169691Skan#ifdef _GLIBCXX_DEBUG 206169691Skan size_type 207169691Skan e_ind() const; 208169691Skan#endif 209169691Skan 210169691Skan private: 211169691Skan pat_trie_internal_node(const pat_trie_internal_node&); 212169691Skan 213169691Skan size_type 214169691Skan get_begin_pos() const; 215169691Skan 216169691Skan const size_type m_e_ind; 217169691Skan const_e_iterator m_pref_b_it; 218169691Skan const_e_iterator m_pref_e_it; 219169691Skan node_pointer m_a_p_children[arr_size]; 220169691Skan static leaf_rebind s_leaf_alloc; 221169691Skan static internal_node_rebind s_internal_node_alloc; 222169691Skan }; 223169691Skan 224169691Skan PB_DS_CLASS_T_DEC 225169691Skan typename PB_DS_CLASS_C_DEC::leaf_rebind 226169691Skan PB_DS_CLASS_C_DEC::s_leaf_alloc; 227169691Skan 228169691Skan PB_DS_CLASS_T_DEC 229169691Skan typename PB_DS_CLASS_C_DEC::internal_node_rebind 230169691Skan PB_DS_CLASS_C_DEC::s_internal_node_alloc; 231169691Skan 232169691Skan PB_DS_CLASS_T_DEC 233169691Skan inline typename PB_DS_CLASS_C_DEC::size_type 234169691Skan PB_DS_CLASS_C_DEC:: 235169691Skan get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, 236169691Skan const_e_access_traits_pointer p_traits) const 237169691Skan { 238169691Skan if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind) 239169691Skan return 0; 240169691Skan std::advance(b_it, m_e_ind); 241169691Skan return 1 + p_traits->e_pos(*b_it); 242169691Skan } 243169691Skan 244169691Skan PB_DS_CLASS_T_DEC 245169691Skan PB_DS_CLASS_C_DEC:: 246169691Skan pat_trie_internal_node(size_type len, const const_e_iterator it) : 247169691Skan PB_DS_BASE_C_DEC(pat_trie_internal_node_type), 248169691Skan m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) 249169691Skan { 250169691Skan std::advance(m_pref_e_it, m_e_ind); 251169691Skan std::fill(m_a_p_children, m_a_p_children + arr_size, 252169691Skan static_cast<node_pointer>(NULL)); 253169691Skan } 254169691Skan 255169691Skan PB_DS_CLASS_T_DEC 256169691Skan void 257169691Skan PB_DS_CLASS_C_DEC:: 258169691Skan update_prefixes(const_e_access_traits_pointer p_traits) 259169691Skan { 260169691Skan node_pointer p_first = *begin(); 261169691Skan if (p_first->m_type == pat_trie_leaf_node_type) 262169691Skan { 263169691Skan const_leaf_pointer p = static_cast<const_leaf_pointer>(p_first); 264169691Skan m_pref_b_it = p_traits->begin(e_access_traits::extract_key(p->value())); 265169691Skan } 266169691Skan else 267169691Skan { 268169691Skan _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type); 269169691Skan m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it(); 270169691Skan } 271169691Skan m_pref_e_it = m_pref_b_it; 272169691Skan std::advance(m_pref_e_it, m_e_ind); 273169691Skan } 274169691Skan 275169691Skan PB_DS_CLASS_T_DEC 276169691Skan typename PB_DS_CLASS_C_DEC::const_iterator 277169691Skan PB_DS_CLASS_C_DEC:: 278169691Skan begin() const 279169691Skan { 280169691Skan typedef node_pointer_pointer pointer_type; 281169691Skan pointer_type p = const_cast<pointer_type>(m_a_p_children); 282169691Skan return const_iterator(p + get_begin_pos(), p + arr_size); 283169691Skan } 284169691Skan 285169691Skan PB_DS_CLASS_T_DEC 286169691Skan typename PB_DS_CLASS_C_DEC::iterator 287169691Skan PB_DS_CLASS_C_DEC:: 288169691Skan begin() 289169691Skan { 290169691Skan return iterator(m_a_p_children + get_begin_pos(), 291169691Skan m_a_p_children + arr_size); 292169691Skan } 293169691Skan 294169691Skan PB_DS_CLASS_T_DEC 295169691Skan typename PB_DS_CLASS_C_DEC::const_iterator 296169691Skan PB_DS_CLASS_C_DEC:: 297169691Skan end() const 298169691Skan { 299169691Skan typedef node_pointer_pointer pointer_type; 300169691Skan pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size; 301169691Skan return const_iterator(p, p); 302169691Skan } 303169691Skan 304169691Skan PB_DS_CLASS_T_DEC 305169691Skan typename PB_DS_CLASS_C_DEC::iterator 306169691Skan PB_DS_CLASS_C_DEC:: 307169691Skan end() 308169691Skan { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } 309169691Skan 310169691Skan PB_DS_CLASS_T_DEC 311169691Skan inline typename PB_DS_CLASS_C_DEC::node_pointer 312169691Skan PB_DS_CLASS_C_DEC:: 313169691Skan get_child_node(const_e_iterator b_it, const_e_iterator e_it, 314169691Skan const_e_access_traits_pointer p_traits) 315169691Skan { 316169691Skan const size_type i = get_pref_pos(b_it, e_it, p_traits); 317169691Skan _GLIBCXX_DEBUG_ASSERT(i < arr_size); 318169691Skan return m_a_p_children[i]; 319169691Skan } 320169691Skan 321169691Skan PB_DS_CLASS_T_DEC 322169691Skan inline typename PB_DS_CLASS_C_DEC::iterator 323169691Skan PB_DS_CLASS_C_DEC:: 324169691Skan get_child_it(const_e_iterator b_it, const_e_iterator e_it, 325169691Skan const_e_access_traits_pointer p_traits) 326169691Skan { 327169691Skan const size_type i = get_pref_pos(b_it, e_it, p_traits); 328169691Skan _GLIBCXX_DEBUG_ASSERT(i < arr_size); 329169691Skan _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL); 330169691Skan return iterator(m_a_p_children + i, m_a_p_children + i); 331169691Skan } 332169691Skan 333169691Skan PB_DS_CLASS_T_DEC 334169691Skan inline typename PB_DS_CLASS_C_DEC::const_node_pointer 335169691Skan PB_DS_CLASS_C_DEC:: 336169691Skan get_child_node(const_e_iterator b_it, const_e_iterator e_it, 337169691Skan const_e_access_traits_pointer p_traits) const 338169691Skan { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); } 339169691Skan 340169691Skan PB_DS_CLASS_T_DEC 341169691Skan typename PB_DS_CLASS_C_DEC::node_pointer 342169691Skan PB_DS_CLASS_C_DEC:: 343169691Skan get_lower_bound_child_node(const_e_iterator b_it, const_e_iterator e_it, 344169691Skan size_type checked_ind, 345169691Skan const_e_access_traits_pointer p_traits) 346169691Skan { 347169691Skan if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) 348169691Skan { 349169691Skan if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true)) 350169691Skan return leftmost_descendant(); 351169691Skan return rightmost_descendant(); 352169691Skan } 353169691Skan 354169691Skan size_type i = get_pref_pos(b_it, e_it, p_traits); 355169691Skan _GLIBCXX_DEBUG_ASSERT(i < arr_size); 356169691Skan 357169691Skan if (m_a_p_children[i] != NULL) 358169691Skan return m_a_p_children[i]; 359169691Skan 360169691Skan while (++i < arr_size) 361169691Skan if (m_a_p_children[i] != NULL) 362169691Skan { 363169691Skan if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type) 364169691Skan return m_a_p_children[i]; 365169691Skan 366169691Skan _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type); 367169691Skan 368169691Skan return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant(); 369169691Skan } 370169691Skan 371169691Skan return rightmost_descendant(); 372169691Skan } 373169691Skan 374169691Skan PB_DS_CLASS_T_DEC 375169691Skan inline typename PB_DS_CLASS_C_DEC::node_pointer 376169691Skan PB_DS_CLASS_C_DEC:: 377169691Skan add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, 378169691Skan const_e_access_traits_pointer p_traits) 379169691Skan { 380169691Skan const size_type i = get_pref_pos(b_it, e_it, p_traits); 381169691Skan _GLIBCXX_DEBUG_ASSERT(i < arr_size); 382169691Skan if (m_a_p_children[i] == NULL) 383169691Skan { 384169691Skan m_a_p_children[i] = p_nd; 385169691Skan p_nd->m_p_parent = this; 386169691Skan return p_nd; 387169691Skan } 388169691Skan return m_a_p_children[i]; 389169691Skan } 390169691Skan 391169691Skan PB_DS_CLASS_T_DEC 392169691Skan typename PB_DS_CLASS_C_DEC::const_node_pointer 393169691Skan PB_DS_CLASS_C_DEC:: 394169691Skan get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const 395169691Skan { 396169691Skan node_pointer p = const_cast<node_pointer>(p_nd); 397169691Skan return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits); 398169691Skan } 399169691Skan 400169691Skan PB_DS_CLASS_T_DEC 401169691Skan typename PB_DS_CLASS_C_DEC::node_pointer 402169691Skan PB_DS_CLASS_C_DEC:: 403169691Skan get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits) 404169691Skan { 405169691Skan size_type i; 406169691Skan const_e_iterator b_it; 407169691Skan const_e_iterator e_it; 408169691Skan if (p_nd->m_type == pat_trie_leaf_node_type) 409169691Skan { 410169691Skan typename Type_Traits::const_key_reference r_key = 411169691Skan e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value()); 412169691Skan 413169691Skan b_it = p_traits->begin(r_key); 414169691Skan e_it = p_traits->end(r_key); 415169691Skan } 416169691Skan else 417169691Skan { 418169691Skan b_it = static_cast<internal_node_pointer>(p_nd)->pref_b_it(); 419169691Skan e_it = static_cast<internal_node_pointer>(p_nd)->pref_e_it(); 420169691Skan } 421169691Skan i = get_pref_pos(b_it, e_it, p_traits); 422169691Skan _GLIBCXX_DEBUG_ASSERT(i < arr_size); 423169691Skan return m_a_p_children[i]; 424169691Skan } 425169691Skan 426169691Skan PB_DS_CLASS_T_DEC 427169691Skan void 428169691Skan PB_DS_CLASS_C_DEC:: 429169691Skan remove_child(node_pointer p_nd) 430169691Skan { 431169691Skan size_type i = 0; 432169691Skan for (; i < arr_size; ++i) 433169691Skan if (m_a_p_children[i] == p_nd) 434169691Skan { 435169691Skan m_a_p_children[i] = NULL; 436169691Skan return; 437169691Skan } 438169691Skan _GLIBCXX_DEBUG_ASSERT(i != arr_size); 439169691Skan } 440169691Skan 441169691Skan PB_DS_CLASS_T_DEC 442169691Skan typename PB_DS_CLASS_C_DEC::iterator 443169691Skan PB_DS_CLASS_C_DEC:: 444169691Skan remove_child(iterator it) 445169691Skan { 446169691Skan iterator ret = it; 447169691Skan ++ret; 448169691Skan * it.m_p_p_cur = NULL; 449169691Skan return ret; 450169691Skan } 451169691Skan 452169691Skan PB_DS_CLASS_T_DEC 453169691Skan void 454169691Skan PB_DS_CLASS_C_DEC:: 455169691Skan replace_child(node_pointer p_nd, const_e_iterator b_it, 456169691Skan const_e_iterator e_it, 457169691Skan const_e_access_traits_pointer p_traits) 458169691Skan { 459169691Skan const size_type i = get_pref_pos(b_it, e_it, p_traits); 460169691Skan _GLIBCXX_DEBUG_ASSERT(i < arr_size); 461169691Skan m_a_p_children[i] = p_nd; 462169691Skan p_nd->m_p_parent = this; 463169691Skan } 464169691Skan 465169691Skan PB_DS_CLASS_T_DEC 466169691Skan inline typename PB_DS_CLASS_C_DEC::const_e_iterator 467169691Skan PB_DS_CLASS_C_DEC:: 468169691Skan pref_b_it() const 469169691Skan { return m_pref_b_it; } 470169691Skan 471169691Skan PB_DS_CLASS_T_DEC 472169691Skan inline typename PB_DS_CLASS_C_DEC::const_e_iterator 473169691Skan PB_DS_CLASS_C_DEC:: 474169691Skan pref_e_it() const 475169691Skan { return m_pref_e_it; } 476169691Skan 477169691Skan PB_DS_CLASS_T_DEC 478169691Skan inline typename PB_DS_CLASS_C_DEC::size_type 479169691Skan PB_DS_CLASS_C_DEC:: 480169691Skan get_e_ind() const 481169691Skan { return m_e_ind; } 482169691Skan 483169691Skan PB_DS_CLASS_T_DEC 484169691Skan bool 485169691Skan PB_DS_CLASS_C_DEC:: 486169691Skan should_be_mine(const_e_iterator b_it, const_e_iterator e_it, 487169691Skan size_type checked_ind, 488169691Skan const_e_access_traits_pointer p_traits) const 489169691Skan { 490169691Skan if (m_e_ind == 0) 491169691Skan return true; 492169691Skan 493169691Skan const size_type num_es = std::distance(b_it, e_it); 494169691Skan if (num_es < m_e_ind) 495169691Skan return false; 496169691Skan 497169691Skan const_e_iterator key_b_it = b_it; 498169691Skan std::advance(key_b_it, checked_ind); 499169691Skan const_e_iterator key_e_it = b_it; 500169691Skan std::advance(key_e_it, m_e_ind); 501169691Skan 502169691Skan const_e_iterator value_b_it = m_pref_b_it; 503169691Skan std::advance(value_b_it, checked_ind); 504169691Skan const_e_iterator value_e_it = m_pref_b_it; 505169691Skan std::advance(value_e_it, m_e_ind); 506169691Skan 507169691Skan return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, 508169691Skan value_e_it); 509169691Skan } 510169691Skan 511169691Skan PB_DS_CLASS_T_DEC 512169691Skan typename PB_DS_CLASS_C_DEC::leaf_pointer 513169691Skan PB_DS_CLASS_C_DEC:: 514169691Skan leftmost_descendant() 515169691Skan { 516169691Skan node_pointer p_pot =* begin(); 517169691Skan if (p_pot->m_type == pat_trie_leaf_node_type) 518169691Skan return (static_cast<leaf_pointer>(p_pot)); 519169691Skan _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); 520169691Skan return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant(); 521169691Skan } 522169691Skan 523169691Skan PB_DS_CLASS_T_DEC 524169691Skan typename PB_DS_CLASS_C_DEC::const_leaf_pointer 525169691Skan PB_DS_CLASS_C_DEC:: 526169691Skan leftmost_descendant() const 527169691Skan { 528169691Skan return const_cast<internal_node_pointer>(this)->leftmost_descendant(); 529169691Skan } 530169691Skan 531169691Skan PB_DS_CLASS_T_DEC 532169691Skan typename PB_DS_CLASS_C_DEC::leaf_pointer 533169691Skan PB_DS_CLASS_C_DEC:: 534169691Skan rightmost_descendant() 535169691Skan { 536169691Skan const size_type num_children = std::distance(begin(), end()); 537169691Skan _GLIBCXX_DEBUG_ASSERT(num_children >= 2); 538169691Skan 539169691Skan iterator it = begin(); 540169691Skan std::advance(it, num_children - 1); 541169691Skan node_pointer p_pot =* it; 542169691Skan if (p_pot->m_type == pat_trie_leaf_node_type) 543169691Skan return static_cast<leaf_pointer>(p_pot); 544169691Skan _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); 545169691Skan return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant(); 546169691Skan } 547169691Skan 548169691Skan PB_DS_CLASS_T_DEC 549169691Skan typename PB_DS_CLASS_C_DEC::const_leaf_pointer 550169691Skan PB_DS_CLASS_C_DEC:: 551169691Skan rightmost_descendant() const 552169691Skan { 553169691Skan return const_cast<internal_node_pointer>(this)->rightmost_descendant(); 554169691Skan } 555169691Skan 556169691Skan#ifdef _GLIBCXX_DEBUG 557169691Skan PB_DS_CLASS_T_DEC 558169691Skan typename PB_DS_CLASS_C_DEC::size_type 559169691Skan PB_DS_CLASS_C_DEC:: 560169691Skan e_ind() const 561169691Skan { return m_e_ind; } 562169691Skan#endif 563169691Skan 564169691Skan PB_DS_CLASS_T_DEC 565169691Skan typename PB_DS_CLASS_C_DEC::size_type 566169691Skan PB_DS_CLASS_C_DEC:: 567169691Skan get_begin_pos() const 568169691Skan { 569169691Skan size_type i; 570169691Skan for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i) 571169691Skan ; 572169691Skan return i; 573169691Skan } 574169691Skan 575169691Skan#ifdef _GLIBCXX_DEBUG 576169691Skan PB_DS_CLASS_T_DEC 577169691Skan typename PB_DS_CLASS_C_DEC::subtree_debug_info 578169691Skan PB_DS_CLASS_C_DEC:: 579169691Skan assert_valid_imp(const_e_access_traits_pointer p_traits) const 580169691Skan { 581169691Skan _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_internal_node_type); 582169691Skan _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); 583169691Skan _GLIBCXX_DEBUG_ASSERT(std::distance(begin(), end()) >= 2); 584169691Skan 585169691Skan for (typename pat_trie_internal_node::const_iterator it = begin(); 586169691Skan it != end(); ++it) 587169691Skan { 588169691Skan const_node_pointer p_nd =* it; 589169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this); 590169691Skan subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits); 591169691Skan 592169691Skan _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); 593169691Skan _GLIBCXX_DEBUG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); 594169691Skan _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)); 595169691Skan } 596169691Skan return std::make_pair(pref_b_it(), pref_e_it()); 597169691Skan } 598169691Skan#endif 599169691Skan 600169691Skan#undef PB_DS_CLASS_T_DEC 601169691Skan#undef PB_DS_CLASS_C_DEC 602169691Skan#undef PB_DS_BASE_C_DEC 603169691Skan#undef PB_DS_LEAF_C_DEC 604169691Skan#undef PB_DS_STATIC_ASSERT 605169691Skan 606169691Skan } // namespace detail 607169691Skan} // namespace pb_ds 608169691Skan 609169691Skan#endif 610