1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2007, 2009 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 3, 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// 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/>. 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 44#include <debug/debug.h> 45 46namespace __gnu_pbds 47{ 48 namespace detail 49 { 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> 62 63 template<typename Type_Traits, 64 typename E_Access_Traits, 65 typename Metadata, 66 typename Allocator> 67 struct pat_trie_internal_node : public PB_DS_BASE_C_DEC 68 { 69 private: 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; 74 75 typedef E_Access_Traits e_access_traits; 76 typedef typename e_access_traits::const_iterator const_e_iterator; 77 typedef typename Allocator::template rebind<e_access_traits>::other access_rebind; 78 typedef typename access_rebind::const_pointer const_e_access_traits_pointer; 79 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; 83 84 typedef PB_DS_LEAF_C_DEC leaf; 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; 88 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; 92 93#ifdef _GLIBCXX_DEBUG 94 typedef typename base_type::subtree_debug_info subtree_debug_info; 95 96 virtual subtree_debug_info 97 assert_valid_imp(const_e_access_traits_pointer) const; 98#endif 99 100 inline size_type 101 get_pref_pos(const_e_iterator, const_e_iterator, 102 const_e_access_traits_pointer) const; 103 104 public: 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; 108 109 enum 110 { 111 arr_size = E_Access_Traits::max_size + 1 112 }; 113 PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); 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 118 pat_trie_internal_node(size_type, const const_e_iterator); 119 120 void 121 update_prefixes(const_e_access_traits_pointer); 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 136 get_child_node(const_e_iterator, const_e_iterator, 137 const_e_access_traits_pointer); 138 139 inline const_node_pointer 140 get_child_node(const_e_iterator, const_e_iterator, 141 const_e_access_traits_pointer) const; 142 143 inline iterator 144 get_child_it(const_e_iterator, const_e_iterator, 145 const_e_access_traits_pointer); 146 147 inline node_pointer 148 get_lower_bound_child_node(const_e_iterator, const_e_iterator, 149 size_type, const_e_access_traits_pointer); 150 151 inline node_pointer 152 add_child(node_pointer, const_e_iterator, const_e_iterator, 153 const_e_access_traits_pointer); 154 155 inline const_node_pointer 156 get_join_child(const_node_pointer, const_e_access_traits_pointer) const; 157 158 inline node_pointer 159 get_join_child(node_pointer, const_e_access_traits_pointer); 160 161 void 162 remove_child(node_pointer p_nd); 163 164 iterator 165 remove_child(iterator it); 166 167 void 168 replace_child(node_pointer, const_e_iterator, const_e_iterator, 169 const_e_access_traits_pointer); 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 181 should_be_mine(const_e_iterator, const_e_iterator, size_type, 182 const_e_access_traits_pointer) const; 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 196#ifdef _GLIBCXX_DEBUG 197 size_type 198 e_ind() const; 199#endif 200 201 private: 202 pat_trie_internal_node(const pat_trie_internal_node&); 203 204 size_type 205 get_begin_pos() const; 206 207 const size_type m_e_ind; 208 const_e_iterator m_pref_b_it; 209 const_e_iterator m_pref_e_it; 210 node_pointer m_a_p_children[arr_size]; 211 static leaf_rebind s_leaf_alloc; 212 static internal_node_rebind s_internal_node_alloc; 213 }; 214 215 PB_DS_CLASS_T_DEC 216 typename PB_DS_CLASS_C_DEC::leaf_rebind 217 PB_DS_CLASS_C_DEC::s_leaf_alloc; 218 219 PB_DS_CLASS_T_DEC 220 typename PB_DS_CLASS_C_DEC::internal_node_rebind 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:: 226 get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, 227 const_e_access_traits_pointer p_traits) const 228 { 229 if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind) 230 return 0; 231 std::advance(b_it, m_e_ind); 232 return 1 + p_traits->e_pos(*b_it); 233 } 234 235 PB_DS_CLASS_T_DEC 236 PB_DS_CLASS_C_DEC:: 237 pat_trie_internal_node(size_type len, const const_e_iterator it) : 238 PB_DS_BASE_C_DEC(pat_trie_internal_node_type), 239 m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) 240 { 241 std::advance(m_pref_e_it, m_e_ind); 242 std::fill(m_a_p_children, m_a_p_children + arr_size, 243 static_cast<node_pointer>(NULL)); 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 { 251 node_pointer p_first = *begin(); 252 if (p_first->m_type == pat_trie_leaf_node_type) 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 } 257 else 258 { 259 _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type); 260 m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it(); 261 } 262 m_pref_e_it = m_pref_b_it; 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 { 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); 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 { 281 return iterator(m_a_p_children + get_begin_pos(), 282 m_a_p_children + arr_size); 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 { 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); 293 } 294 295 PB_DS_CLASS_T_DEC 296 typename PB_DS_CLASS_C_DEC::iterator 297 PB_DS_CLASS_C_DEC:: 298 end() 299 { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } 300 301 PB_DS_CLASS_T_DEC 302 inline typename PB_DS_CLASS_C_DEC::node_pointer 303 PB_DS_CLASS_C_DEC:: 304 get_child_node(const_e_iterator b_it, const_e_iterator e_it, 305 const_e_access_traits_pointer p_traits) 306 { 307 const size_type i = get_pref_pos(b_it, e_it, p_traits); 308 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 309 return m_a_p_children[i]; 310 } 311 312 PB_DS_CLASS_T_DEC 313 inline typename PB_DS_CLASS_C_DEC::iterator 314 PB_DS_CLASS_C_DEC:: 315 get_child_it(const_e_iterator b_it, const_e_iterator e_it, 316 const_e_access_traits_pointer p_traits) 317 { 318 const size_type i = get_pref_pos(b_it, e_it, p_traits); 319 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 320 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL); 321 return iterator(m_a_p_children + i, m_a_p_children + i); 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:: 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)); } 330 331 PB_DS_CLASS_T_DEC 332 typename PB_DS_CLASS_C_DEC::node_pointer 333 PB_DS_CLASS_C_DEC:: 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) 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)) 341 return leftmost_descendant(); 342 return rightmost_descendant(); 343 } 344 345 size_type i = get_pref_pos(b_it, e_it, p_traits); 346 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 347 348 if (m_a_p_children[i] != NULL) 349 return m_a_p_children[i]; 350 351 while (++i < arr_size) 352 if (m_a_p_children[i] != NULL) 353 { 354 if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type) 355 return m_a_p_children[i]; 356 357 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type); 358 359 return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant(); 360 } 361 362 return rightmost_descendant(); 363 } 364 365 PB_DS_CLASS_T_DEC 366 inline typename PB_DS_CLASS_C_DEC::node_pointer 367 PB_DS_CLASS_C_DEC:: 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) 370 { 371 const size_type i = get_pref_pos(b_it, e_it, p_traits); 372 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 373 if (m_a_p_children[i] == NULL) 374 { 375 m_a_p_children[i] = p_nd; 376 p_nd->m_p_parent = this; 377 return p_nd; 378 } 379 return m_a_p_children[i]; 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 { 387 node_pointer p = const_cast<node_pointer>(p_nd); 388 return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits); 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; 397 const_e_iterator b_it; 398 const_e_iterator e_it; 399 if (p_nd->m_type == pat_trie_leaf_node_type) 400 { 401 typename Type_Traits::const_key_reference r_key = 402 e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value()); 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 } 412 i = get_pref_pos(b_it, e_it, p_traits); 413 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 414 return m_a_p_children[i]; 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; 423 for (; i < arr_size; ++i) 424 if (m_a_p_children[i] == p_nd) 425 { 426 m_a_p_children[i] = NULL; 427 return; 428 } 429 _GLIBCXX_DEBUG_ASSERT(i != arr_size); 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; 438 ++ret; 439 * it.m_p_p_cur = NULL; 440 return ret; 441 } 442 443 PB_DS_CLASS_T_DEC 444 void 445 PB_DS_CLASS_C_DEC:: 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) 449 { 450 const size_type i = get_pref_pos(b_it, e_it, p_traits); 451 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 452 m_a_p_children[i] = p_nd; 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 460 { return m_pref_b_it; } 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 466 { return m_pref_e_it; } 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 472 { return m_e_ind; } 473 474 PB_DS_CLASS_T_DEC 475 bool 476 PB_DS_CLASS_C_DEC:: 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 480 { 481 if (m_e_ind == 0) 482 return true; 483 484 const size_type num_es = std::distance(b_it, e_it); 485 if (num_es < m_e_ind) 486 return false; 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 498 return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, 499 value_e_it); 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(); 508 if (p_pot->m_type == pat_trie_leaf_node_type) 509 return (static_cast<leaf_pointer>(p_pot)); 510 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); 511 return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant(); 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 { 519 return const_cast<internal_node_pointer>(this)->leftmost_descendant(); 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()); 528 _GLIBCXX_DEBUG_ASSERT(num_children >= 2); 529 530 iterator it = begin(); 531 std::advance(it, num_children - 1); 532 node_pointer p_pot =* it; 533 if (p_pot->m_type == pat_trie_leaf_node_type) 534 return static_cast<leaf_pointer>(p_pot); 535 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); 536 return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant(); 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 { 544 return const_cast<internal_node_pointer>(this)->rightmost_descendant(); 545 } 546 547#ifdef _GLIBCXX_DEBUG 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 552 { return m_e_ind; } 553#endif 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; 561 for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i) 562 ; 563 return i; 564 } 565 566#ifdef _GLIBCXX_DEBUG 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 { 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); 575 576 for (typename pat_trie_internal_node::const_iterator it = begin(); 577 it != end(); ++it) 578 { 579 const_node_pointer p_nd =* it; 580 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this); 581 subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits); 582 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)); 586 } 587 return std::make_pair(pref_b_it(), pref_e_it()); 588 } 589#endif 590 591#undef PB_DS_CLASS_T_DEC 592#undef PB_DS_CLASS_C_DEC 593#undef PB_DS_BASE_C_DEC 594#undef PB_DS_LEAF_C_DEC 595 596 } // namespace detail 597} // namespace __gnu_pbds 598 599#endif 600