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 50 #include <debug/debug.h> 51 52 namespace pb_ds 53 { 54 namespace detail 55 { 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> 68 69 #define PB_DS_STATIC_ASSERT(UNIQUE, E) \ 70 typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> UNIQUE##static_assert_type 71 72 template<typename Type_Traits, 73 typename E_Access_Traits, 74 typename Metadata, 75 typename Allocator> 76 struct pat_trie_internal_node : public PB_DS_BASE_C_DEC 77 { 78 private: 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; 83 84 typedef E_Access_Traits e_access_traits; 85 typedef typename e_access_traits::const_iterator const_e_iterator; 86 typedef typename Allocator::template rebind<e_access_traits>::other access_rebind; 87 typedef typename access_rebind::const_pointer const_e_access_traits_pointer; 88 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; 92 93 typedef PB_DS_LEAF_C_DEC leaf; 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; 97 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; 101 102 #ifdef _GLIBCXX_DEBUG 103 typedef typename base_type::subtree_debug_info subtree_debug_info; 104 105 virtual subtree_debug_info 106 assert_valid_imp(const_e_access_traits_pointer) const; 107 #endif 108 109 inline size_type 110 get_pref_pos(const_e_iterator, const_e_iterator, 111 const_e_access_traits_pointer) const; 112 113 public: 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; 117 118 enum 119 { 120 arr_size = E_Access_Traits::max_size + 1 121 }; 122 PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); 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 127 pat_trie_internal_node(size_type, const const_e_iterator); 128 129 void 130 update_prefixes(const_e_access_traits_pointer); 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 145 get_child_node(const_e_iterator, const_e_iterator, 146 const_e_access_traits_pointer); 147 148 inline const_node_pointer 149 get_child_node(const_e_iterator, const_e_iterator, 150 const_e_access_traits_pointer) const; 151 152 inline iterator 153 get_child_it(const_e_iterator, const_e_iterator, 154 const_e_access_traits_pointer); 155 156 inline node_pointer 157 get_lower_bound_child_node(const_e_iterator, const_e_iterator, 158 size_type, const_e_access_traits_pointer); 159 160 inline node_pointer 161 add_child(node_pointer, const_e_iterator, const_e_iterator, 162 const_e_access_traits_pointer); 163 164 inline const_node_pointer 165 get_join_child(const_node_pointer, const_e_access_traits_pointer) const; 166 167 inline node_pointer 168 get_join_child(node_pointer, const_e_access_traits_pointer); 169 170 void 171 remove_child(node_pointer p_nd); 172 173 iterator 174 remove_child(iterator it); 175 176 void 177 replace_child(node_pointer, const_e_iterator, const_e_iterator, 178 const_e_access_traits_pointer); 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 190 should_be_mine(const_e_iterator, const_e_iterator, size_type, 191 const_e_access_traits_pointer) const; 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 205 #ifdef _GLIBCXX_DEBUG 206 size_type 207 e_ind() const; 208 #endif 209 210 private: 211 pat_trie_internal_node(const pat_trie_internal_node&); 212 213 size_type 214 get_begin_pos() const; 215 216 const size_type m_e_ind; 217 const_e_iterator m_pref_b_it; 218 const_e_iterator m_pref_e_it; 219 node_pointer m_a_p_children[arr_size]; 220 static leaf_rebind s_leaf_alloc; 221 static internal_node_rebind s_internal_node_alloc; 222 }; 223 224 PB_DS_CLASS_T_DEC 225 typename PB_DS_CLASS_C_DEC::leaf_rebind 226 PB_DS_CLASS_C_DEC::s_leaf_alloc; 227 228 PB_DS_CLASS_T_DEC 229 typename PB_DS_CLASS_C_DEC::internal_node_rebind 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:: get_pref_pos(const_e_iterator b_it,const_e_iterator e_it,const_e_access_traits_pointer p_traits) const235 get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, 236 const_e_access_traits_pointer p_traits) const 237 { 238 if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind) 239 return 0; 240 std::advance(b_it, m_e_ind); 241 return 1 + p_traits->e_pos(*b_it); 242 } 243 244 PB_DS_CLASS_T_DEC 245 PB_DS_CLASS_C_DEC:: pat_trie_internal_node(size_type len,const const_e_iterator it)246 pat_trie_internal_node(size_type len, const const_e_iterator it) : 247 PB_DS_BASE_C_DEC(pat_trie_internal_node_type), 248 m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) 249 { 250 std::advance(m_pref_e_it, m_e_ind); 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:: update_prefixes(const_e_access_traits_pointer p_traits)258 update_prefixes(const_e_access_traits_pointer p_traits) 259 { 260 node_pointer p_first = *begin(); 261 if (p_first->m_type == pat_trie_leaf_node_type) 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 } 266 else 267 { 268 _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type); 269 m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it(); 270 } 271 m_pref_e_it = m_pref_b_it; 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:: begin() const278 begin() const 279 { 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); 283 } 284 285 PB_DS_CLASS_T_DEC 286 typename PB_DS_CLASS_C_DEC::iterator 287 PB_DS_CLASS_C_DEC:: begin()288 begin() 289 { 290 return iterator(m_a_p_children + get_begin_pos(), 291 m_a_p_children + arr_size); 292 } 293 294 PB_DS_CLASS_T_DEC 295 typename PB_DS_CLASS_C_DEC::const_iterator 296 PB_DS_CLASS_C_DEC:: end() const297 end() const 298 { 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); 302 } 303 304 PB_DS_CLASS_T_DEC 305 typename PB_DS_CLASS_C_DEC::iterator 306 PB_DS_CLASS_C_DEC:: end()307 end() 308 { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } 309 310 PB_DS_CLASS_T_DEC 311 inline typename PB_DS_CLASS_C_DEC::node_pointer 312 PB_DS_CLASS_C_DEC:: get_child_node(const_e_iterator b_it,const_e_iterator e_it,const_e_access_traits_pointer p_traits)313 get_child_node(const_e_iterator b_it, const_e_iterator e_it, 314 const_e_access_traits_pointer p_traits) 315 { 316 const size_type i = get_pref_pos(b_it, e_it, p_traits); 317 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 318 return m_a_p_children[i]; 319 } 320 321 PB_DS_CLASS_T_DEC 322 inline typename PB_DS_CLASS_C_DEC::iterator 323 PB_DS_CLASS_C_DEC:: get_child_it(const_e_iterator b_it,const_e_iterator e_it,const_e_access_traits_pointer p_traits)324 get_child_it(const_e_iterator b_it, const_e_iterator e_it, 325 const_e_access_traits_pointer p_traits) 326 { 327 const size_type i = get_pref_pos(b_it, e_it, p_traits); 328 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 329 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL); 330 return iterator(m_a_p_children + i, m_a_p_children + i); 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:: get_child_node(const_e_iterator b_it,const_e_iterator e_it,const_e_access_traits_pointer p_traits) const336 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)); } 339 340 PB_DS_CLASS_T_DEC 341 typename PB_DS_CLASS_C_DEC::node_pointer 342 PB_DS_CLASS_C_DEC:: get_lower_bound_child_node(const_e_iterator b_it,const_e_iterator e_it,size_type checked_ind,const_e_access_traits_pointer p_traits)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) 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)) 350 return leftmost_descendant(); 351 return rightmost_descendant(); 352 } 353 354 size_type i = get_pref_pos(b_it, e_it, p_traits); 355 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 356 357 if (m_a_p_children[i] != NULL) 358 return m_a_p_children[i]; 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) 364 return m_a_p_children[i]; 365 366 _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type); 367 368 return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant(); 369 } 370 371 return rightmost_descendant(); 372 } 373 374 PB_DS_CLASS_T_DEC 375 inline typename PB_DS_CLASS_C_DEC::node_pointer 376 PB_DS_CLASS_C_DEC:: add_child(node_pointer p_nd,const_e_iterator b_it,const_e_iterator e_it,const_e_access_traits_pointer p_traits)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) 379 { 380 const size_type i = get_pref_pos(b_it, e_it, p_traits); 381 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 382 if (m_a_p_children[i] == NULL) 383 { 384 m_a_p_children[i] = p_nd; 385 p_nd->m_p_parent = this; 386 return p_nd; 387 } 388 return m_a_p_children[i]; 389 } 390 391 PB_DS_CLASS_T_DEC 392 typename PB_DS_CLASS_C_DEC::const_node_pointer 393 PB_DS_CLASS_C_DEC:: get_join_child(const_node_pointer p_nd,const_e_access_traits_pointer p_traits) const394 get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const 395 { 396 node_pointer p = const_cast<node_pointer>(p_nd); 397 return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits); 398 } 399 400 PB_DS_CLASS_T_DEC 401 typename PB_DS_CLASS_C_DEC::node_pointer 402 PB_DS_CLASS_C_DEC:: get_join_child(node_pointer p_nd,const_e_access_traits_pointer p_traits)403 get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits) 404 { 405 size_type i; 406 const_e_iterator b_it; 407 const_e_iterator e_it; 408 if (p_nd->m_type == pat_trie_leaf_node_type) 409 { 410 typename Type_Traits::const_key_reference r_key = 411 e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value()); 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 } 421 i = get_pref_pos(b_it, e_it, p_traits); 422 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 423 return m_a_p_children[i]; 424 } 425 426 PB_DS_CLASS_T_DEC 427 void 428 PB_DS_CLASS_C_DEC:: remove_child(node_pointer p_nd)429 remove_child(node_pointer p_nd) 430 { 431 size_type i = 0; 432 for (; i < arr_size; ++i) 433 if (m_a_p_children[i] == p_nd) 434 { 435 m_a_p_children[i] = NULL; 436 return; 437 } 438 _GLIBCXX_DEBUG_ASSERT(i != arr_size); 439 } 440 441 PB_DS_CLASS_T_DEC 442 typename PB_DS_CLASS_C_DEC::iterator 443 PB_DS_CLASS_C_DEC:: remove_child(iterator it)444 remove_child(iterator it) 445 { 446 iterator ret = it; 447 ++ret; 448 * it.m_p_p_cur = NULL; 449 return ret; 450 } 451 452 PB_DS_CLASS_T_DEC 453 void 454 PB_DS_CLASS_C_DEC:: replace_child(node_pointer p_nd,const_e_iterator b_it,const_e_iterator e_it,const_e_access_traits_pointer p_traits)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) 458 { 459 const size_type i = get_pref_pos(b_it, e_it, p_traits); 460 _GLIBCXX_DEBUG_ASSERT(i < arr_size); 461 m_a_p_children[i] = p_nd; 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:: pref_b_it() const468 pref_b_it() const 469 { return m_pref_b_it; } 470 471 PB_DS_CLASS_T_DEC 472 inline typename PB_DS_CLASS_C_DEC::const_e_iterator 473 PB_DS_CLASS_C_DEC:: pref_e_it() const474 pref_e_it() const 475 { return m_pref_e_it; } 476 477 PB_DS_CLASS_T_DEC 478 inline typename PB_DS_CLASS_C_DEC::size_type 479 PB_DS_CLASS_C_DEC:: get_e_ind() const480 get_e_ind() const 481 { return m_e_ind; } 482 483 PB_DS_CLASS_T_DEC 484 bool 485 PB_DS_CLASS_C_DEC:: should_be_mine(const_e_iterator b_it,const_e_iterator e_it,size_type checked_ind,const_e_access_traits_pointer p_traits) const486 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 489 { 490 if (m_e_ind == 0) 491 return true; 492 493 const size_type num_es = std::distance(b_it, e_it); 494 if (num_es < m_e_ind) 495 return false; 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 507 return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, 508 value_e_it); 509 } 510 511 PB_DS_CLASS_T_DEC 512 typename PB_DS_CLASS_C_DEC::leaf_pointer 513 PB_DS_CLASS_C_DEC:: leftmost_descendant()514 leftmost_descendant() 515 { 516 node_pointer p_pot =* begin(); 517 if (p_pot->m_type == pat_trie_leaf_node_type) 518 return (static_cast<leaf_pointer>(p_pot)); 519 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); 520 return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant(); 521 } 522 523 PB_DS_CLASS_T_DEC 524 typename PB_DS_CLASS_C_DEC::const_leaf_pointer 525 PB_DS_CLASS_C_DEC:: leftmost_descendant() const526 leftmost_descendant() const 527 { 528 return const_cast<internal_node_pointer>(this)->leftmost_descendant(); 529 } 530 531 PB_DS_CLASS_T_DEC 532 typename PB_DS_CLASS_C_DEC::leaf_pointer 533 PB_DS_CLASS_C_DEC:: rightmost_descendant()534 rightmost_descendant() 535 { 536 const size_type num_children = std::distance(begin(), end()); 537 _GLIBCXX_DEBUG_ASSERT(num_children >= 2); 538 539 iterator it = begin(); 540 std::advance(it, num_children - 1); 541 node_pointer p_pot =* it; 542 if (p_pot->m_type == pat_trie_leaf_node_type) 543 return static_cast<leaf_pointer>(p_pot); 544 _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); 545 return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant(); 546 } 547 548 PB_DS_CLASS_T_DEC 549 typename PB_DS_CLASS_C_DEC::const_leaf_pointer 550 PB_DS_CLASS_C_DEC:: rightmost_descendant() const551 rightmost_descendant() const 552 { 553 return const_cast<internal_node_pointer>(this)->rightmost_descendant(); 554 } 555 556 #ifdef _GLIBCXX_DEBUG 557 PB_DS_CLASS_T_DEC 558 typename PB_DS_CLASS_C_DEC::size_type 559 PB_DS_CLASS_C_DEC:: e_ind() const560 e_ind() const 561 { return m_e_ind; } 562 #endif 563 564 PB_DS_CLASS_T_DEC 565 typename PB_DS_CLASS_C_DEC::size_type 566 PB_DS_CLASS_C_DEC:: get_begin_pos() const567 get_begin_pos() const 568 { 569 size_type i; 570 for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i) 571 ; 572 return i; 573 } 574 575 #ifdef _GLIBCXX_DEBUG 576 PB_DS_CLASS_T_DEC 577 typename PB_DS_CLASS_C_DEC::subtree_debug_info 578 PB_DS_CLASS_C_DEC:: assert_valid_imp(const_e_access_traits_pointer p_traits) const579 assert_valid_imp(const_e_access_traits_pointer p_traits) const 580 { 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); 584 585 for (typename pat_trie_internal_node::const_iterator it = begin(); 586 it != end(); ++it) 587 { 588 const_node_pointer p_nd =* it; 589 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this); 590 subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits); 591 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)); 595 } 596 return std::make_pair(pref_b_it(), pref_e_it()); 597 } 598 #endif 599 600 #undef PB_DS_CLASS_T_DEC 601 #undef PB_DS_CLASS_C_DEC 602 #undef PB_DS_BASE_C_DEC 603 #undef PB_DS_LEAF_C_DEC 604 #undef PB_DS_STATIC_ASSERT 605 606 } // namespace detail 607 } // namespace pb_ds 608 609 #endif 610