libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp

   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 #ifdef PB_DS_PAT_TRIE_DEBUG_
  51 #include <cassert>
  52 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
  53
  54 namespace pb_ds
  55 {
  56   namespace detail
  57   {
  58
  59 #define PB_DS_CLASS_T_DEC                                               \
  60     template<                                                           \
  61                                                 class Type_Traits,      \
  62                                                 class E_Access_Traits,  \
  63                                                 class Metadata,         \
  64                                                 class Allocator>
  65
  66 #define PB_DS_CLASS_C_DEC                                               \
  67     pat_trie_internal_node<                                             \
  68                                                 Type_Traits,            \
  69                                                 E_Access_Traits,        \
  70                                                 Metadata,               \
  71                                                 Allocator>
  72
  73 #define PB_DS_BASE_C_DEC                                        \
  74     pat_trie_node_base<                                         \
  75                                         Type_Traits,            \
  76                                         E_Access_Traits,        \
  77                                         Metadata,               \
  78                                         Allocator>
  79
  80 #define PB_DS_LEAF_C_DEC                                                \
  81     pat_trie_leaf<                                                      \
  82                                                 Type_Traits,            \
  83                                                 E_Access_Traits,        \
  84                                                 Metadata,               \
  85                                                 Allocator>
  86
  87 #define PB_DS_STATIC_ASSERT(UNIQUE, E)                                  \
  88     typedef                                                             \
  89     static_assert_dumclass<                             \
  90                                                                         sizeof(static_assert<(bool)(E)>)> \
  91     UNIQUE##static_assert_type
  92
  93 #ifdef PB_DS_PAT_TRIE_DEBUG_
  94 #define PB_DS_DBG_ASSERT(X) assert(X)
  95 #define PB_DS_DBG_VERIFY(X) assert(X)
  96 #define PB_DS_DBG_ONLY(X) X
  97 #else // #ifdef PB_DS_PAT_TRIE_DEBUG_
  98 #define PB_DS_DBG_ASSERT(X)
  99 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
 100 #define PB_DS_DBG_ONLY(X) ;
 101 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 102
 103     template<typename Type_Traits,
 104              class E_Access_Traits,
 105              class Metadata,
 106              class Allocator>
 107     struct pat_trie_internal_node : public PB_DS_BASE_C_DEC
 108     {
 109     public:
 110       enum
 111         {
 112           arr_size =
 113           E_Access_Traits::max_size + 1
 114         };
 115
 116     private:
 117       typedef typename Allocator::size_type size_type;
 118
 119       typedef E_Access_Traits e_access_traits;
 120
 121       typedef
 122       typename Allocator::template rebind<
 123         e_access_traits>::other::const_pointer
 124       const_e_access_traits_pointer;
 125
 126       typedef typename e_access_traits::const_iterator const_e_iterator;
 127
 128       typedef
 129       typename Allocator::template rebind<
 130         PB_DS_BASE_C_DEC >::other::pointer
 131       node_pointer;
 132
 133       typedef
 134       typename Allocator::template rebind<
 135         PB_DS_BASE_C_DEC >::other::const_pointer
 136       const_node_pointer;
 137
 138       typedef PB_DS_LEAF_C_DEC leaf;
 139
 140       typedef
 141       typename Allocator::template rebind<
 142         leaf>::other
 143       leaf_allocator;
 144
 145       typedef typename leaf_allocator::pointer leaf_pointer;
 146
 147       typedef typename leaf_allocator::const_pointer const_leaf_pointer;
 148
 149       typedef
 150       typename Allocator::template rebind<
 151         PB_DS_CLASS_C_DEC>::other
 152       internal_node_allocator;
 153
 154       typedef
 155       typename Allocator::template rebind<
 156         PB_DS_CLASS_C_DEC>::other::const_pointer
 157       const_internal_node_pointer;
 158
 159       typedef
 160       typename Allocator::template rebind<
 161         PB_DS_CLASS_C_DEC>::other::pointer
 162       internal_node_pointer;
 163
 164       PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2);
 165
 166       typedef typename Type_Traits::value_type value_type;
 167
 168 #ifdef PB_DS_PAT_TRIE_DEBUG_
 169       typedef
 170       typename PB_DS_BASE_C_DEC::subtree_debug_info
 171       subtree_debug_info;
 172 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 173
 174       typedef PB_DS_BASE_C_DEC base_type;
 175
 176     private:
 177       inline size_type
 178       get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) const;
 179
 180 #ifdef PB_DS_PAT_TRIE_DEBUG_
 181       virtual subtree_debug_info
 182       assert_valid_imp(const_e_access_traits_pointer p_traits) const;
 183 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 184
 185     public:
 186       typedef
 187       typename Allocator::template rebind<
 188       node_pointer>::other::pointer
 189       node_pointer_pointer;
 190
 191       typedef
 192       typename Allocator::template rebind<
 193         node_pointer>::other::reference
 194       node_pointer_reference;
 195
 196 #include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp>
 197 #include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp>
 198
 199     public:
 200       pat_trie_internal_node(size_type e_ind, const const_e_iterator pref_b_it);
 201
 202       void
 203       update_prefixes(const_e_access_traits_pointer p_traits);
 204
 205       const_iterator
 206       begin() const;
 207
 208       iterator
 209       begin();
 210
 211       const_iterator
 212       end() const;
 213
 214       iterator
 215       end();
 216
 217       inline node_pointer
 218       get_child_node(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits);
 219
 220       inline const_node_pointer
 221       get_child_node(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) const;
 222
 223       inline iterator
 224       get_child_it(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits);
 225
 226       inline node_pointer
 227       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);
 228
 229       inline node_pointer
 230       add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits);
 231
 232       inline const_node_pointer
 233       get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const;
 234
 235       inline node_pointer
 236       get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits);
 237
 238       void
 239       remove_child(node_pointer p_nd);
 240
 241       iterator
 242       remove_child(iterator it);
 243
 244       void
 245       replace_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits);
 246
 247       inline const_e_iterator
 248       pref_b_it() const;
 249
 250       inline const_e_iterator
 251       pref_e_it() const;
 252
 253       inline size_type
 254       get_e_ind() const;
 255
 256       bool
 257       should_be_mine(const_e_iterator b_it, const_e_iterator e_it, size_type checked_ind, const_e_access_traits_pointer p_traits) const;
 258
 259       leaf_pointer
 260       leftmost_descendant();
 261
 262       const_leaf_pointer
 263       leftmost_descendant() const;
 264
 265       leaf_pointer
 266       rightmost_descendant();
 267
 268       const_leaf_pointer
 269       rightmost_descendant() const;
 270
 271 #ifdef PB_DS_PAT_TRIE_DEBUG_
 272       size_type
 273       e_ind() const;
 274 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 275
 276     private:
 277       pat_trie_internal_node(const PB_DS_CLASS_C_DEC& other);
 278
 279       size_type
 280       get_begin_pos() const;
 281
 282     private:
 283       const size_type m_e_ind;
 284
 285       const_e_iterator m_pref_b_it;
 286       const_e_iterator m_pref_e_it;
 287
 288       node_pointer m_a_p_children[arr_size];
 289
 290       static leaf_allocator s_leaf_alloc;
 291
 292       static internal_node_allocator s_internal_node_alloc;
 293     };
 294
 295     PB_DS_CLASS_T_DEC
 296     typename PB_DS_CLASS_C_DEC::leaf_allocator
 297     PB_DS_CLASS_C_DEC::s_leaf_alloc;
 298
 299     PB_DS_CLASS_T_DEC
 300     typename PB_DS_CLASS_C_DEC::internal_node_allocator
 301     PB_DS_CLASS_C_DEC::s_internal_node_alloc;
 302
 303     PB_DS_CLASS_T_DEC
 304     inline typename PB_DS_CLASS_C_DEC::size_type
 305     PB_DS_CLASS_C_DEC::
 306     get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) const
 307     {
 308       if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind)
 309         return (0);
 310
 311       std::advance(b_it, m_e_ind);
 312
 313       return (1 + p_traits->e_pos(*b_it));
 314     }
 315
 316     PB_DS_CLASS_T_DEC
 317     PB_DS_CLASS_C_DEC::
 318     pat_trie_internal_node(size_type e_ind, const const_e_iterator pref_b_it) :
 319       PB_DS_BASE_C_DEC(pat_trie_internal_node_type),
 320       m_e_ind(e_ind),
 321       m_pref_b_it(pref_b_it),
 322       m_pref_e_it(pref_b_it)
 323     {
 324       std::advance(m_pref_e_it, m_e_ind);
 325
 326       std::fill(m_a_p_children, m_a_p_children + arr_size,
 327                 static_cast<node_pointer>(NULL));
 328     }
 329
 330     PB_DS_CLASS_T_DEC
 331     void
 332     PB_DS_CLASS_C_DEC::
 333     update_prefixes(const_e_access_traits_pointer p_traits)
 334     {
 335       node_pointer p_first =* begin();
 336
 337       if (p_first->m_type == pat_trie_leaf_node_type)
 338         m_pref_b_it =
 339           p_traits->begin(
 340                           E_Access_Traits::extract_key(
 341                                                        static_cast<const_leaf_pointer>(p_first)->value()));
 342       else
 343         {
 344           PB_DS_DBG_ASSERT(p_first->m_type == pat_trie_internal_node_type);
 345
 346           m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it();
 347         }
 348
 349       m_pref_e_it = m_pref_b_it;
 350
 351       std::advance(m_pref_e_it, m_e_ind);
 352     }
 353
 354     PB_DS_CLASS_T_DEC
 355     typename PB_DS_CLASS_C_DEC::const_iterator
 356     PB_DS_CLASS_C_DEC::
 357     begin() const
 358     {
 359       return (const_iterator(
 360                              const_cast<node_pointer_pointer>(m_a_p_children) + get_begin_pos(),
 361                              const_cast<node_pointer_pointer>(m_a_p_children) + arr_size));
 362     }
 363
 364     PB_DS_CLASS_T_DEC
 365     typename PB_DS_CLASS_C_DEC::iterator
 366     PB_DS_CLASS_C_DEC::
 367     begin()
 368     {
 369       return (iterator(
 370                        m_a_p_children + get_begin_pos(),
 371                        m_a_p_children + arr_size));
 372     }
 373
 374     PB_DS_CLASS_T_DEC
 375     typename PB_DS_CLASS_C_DEC::const_iterator
 376     PB_DS_CLASS_C_DEC::
 377     end() const
 378     {
 379       return (const_iterator(
 380                              const_cast<node_pointer_pointer>(m_a_p_children) + arr_size,
 381                              const_cast<node_pointer_pointer>(m_a_p_children) + arr_size));
 382     }
 383
 384     PB_DS_CLASS_T_DEC
 385     typename PB_DS_CLASS_C_DEC::iterator
 386     PB_DS_CLASS_C_DEC::
 387     end()
 388     {
 389       return (iterator(        m_a_p_children + arr_size, m_a_p_children + arr_size));
 390     }
 391
 392     PB_DS_CLASS_T_DEC
 393     inline typename PB_DS_CLASS_C_DEC::node_pointer
 394     PB_DS_CLASS_C_DEC::
 395     get_child_node(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits)
 396     {
 397       const size_type i = get_pref_pos(        b_it, e_it, p_traits);
 398
 399       PB_DS_DBG_ASSERT(i < arr_size);
 400
 401       return (m_a_p_children[i]);
 402     }
 403
 404     PB_DS_CLASS_T_DEC
 405     inline typename PB_DS_CLASS_C_DEC::iterator
 406     PB_DS_CLASS_C_DEC::
 407     get_child_it(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits)
 408     {
 409       const size_type i = get_pref_pos(        b_it, e_it, p_traits);
 410
 411       PB_DS_DBG_ASSERT(i < arr_size);
 412
 413       PB_DS_DBG_ASSERT(m_a_p_children[i] != NULL);
 414
 415       return (iterator(m_a_p_children + i, m_a_p_children + i));
 416     }
 417
 418     PB_DS_CLASS_T_DEC
 419     inline typename PB_DS_CLASS_C_DEC::const_node_pointer
 420     PB_DS_CLASS_C_DEC::
 421     get_child_node(const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits) const
 422     {
 423       return (const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)));
 424     }
 425
 426     PB_DS_CLASS_T_DEC
 427     typename PB_DS_CLASS_C_DEC::node_pointer
 428     PB_DS_CLASS_C_DEC::
 429     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)
 430     {
 431       if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
 432         {
 433           if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true))
 434             return (leftmost_descendant());
 435
 436           return (rightmost_descendant());
 437         }
 438
 439       size_type i = get_pref_pos(        b_it, e_it, p_traits);
 440
 441       PB_DS_DBG_ASSERT(i < arr_size);
 442
 443       if (m_a_p_children[i] != NULL)
 444         return (m_a_p_children[i]);
 445
 446       while (++i < arr_size)
 447         if (m_a_p_children[i] != NULL)
 448           {
 449             if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type)
 450               return (m_a_p_children[i]);
 451
 452             PB_DS_DBG_ASSERT(m_a_p_children[i]->m_type ==
 453                              pat_trie_internal_node_type);
 454
 455             return (static_cast<internal_node_pointer>(
 456                                                        m_a_p_children[i])->leftmost_descendant());
 457           }
 458
 459       return (rightmost_descendant());
 460     }
 461
 462     PB_DS_CLASS_T_DEC
 463     inline typename PB_DS_CLASS_C_DEC::node_pointer
 464     PB_DS_CLASS_C_DEC::
 465     add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits)
 466     {
 467       const size_type i = get_pref_pos(        b_it, e_it, p_traits);
 468
 469       PB_DS_DBG_ASSERT(i < arr_size);
 470
 471       if (m_a_p_children[i] == NULL)
 472         {
 473           m_a_p_children[i] = p_nd;
 474
 475           p_nd->m_p_parent = this;
 476
 477           return (p_nd);
 478         }
 479
 480       return (m_a_p_children[i]);
 481     }
 482
 483     PB_DS_CLASS_T_DEC
 484     typename PB_DS_CLASS_C_DEC::const_node_pointer
 485     PB_DS_CLASS_C_DEC::
 486     get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const
 487     {
 488       return (const_cast<internal_node_pointer>(this)->get_join_child(
 489                                                                       const_cast<node_pointer>(p_nd),
 490                                                                       p_traits));
 491     }
 492
 493     PB_DS_CLASS_T_DEC
 494     typename PB_DS_CLASS_C_DEC::node_pointer
 495     PB_DS_CLASS_C_DEC::
 496     get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits)
 497     {
 498       size_type i;
 499
 500       const_e_iterator b_it;
 501       const_e_iterator e_it;
 502
 503       if (p_nd->m_type == pat_trie_leaf_node_type)
 504         {
 505           typename Type_Traits::const_key_reference r_key =
 506             e_access_traits::extract_key(
 507                                          static_cast<const_leaf_pointer>(p_nd)->value());
 508
 509           b_it = p_traits->begin(r_key);
 510           e_it = p_traits->end(r_key);
 511         }
 512       else
 513         {
 514           b_it = static_cast<internal_node_pointer>(p_nd)->pref_b_it();
 515           e_it = static_cast<internal_node_pointer>(p_nd)->pref_e_it();
 516         }
 517
 518       i = get_pref_pos(b_it, e_it, p_traits);
 519
 520       PB_DS_DBG_ASSERT(i < arr_size);
 521
 522       return (m_a_p_children[i]);
 523     }
 524
 525     PB_DS_CLASS_T_DEC
 526     void
 527     PB_DS_CLASS_C_DEC::
 528     remove_child(node_pointer p_nd)
 529     {
 530       size_type i = 0;
 531
 532       for (; i < arr_size; ++i)
 533         if (m_a_p_children[i] == p_nd)
 534           {
 535             m_a_p_children[i] = NULL;
 536
 537             return;
 538           }
 539
 540       PB_DS_DBG_ASSERT(i != arr_size);
 541     }
 542
 543     PB_DS_CLASS_T_DEC
 544     typename PB_DS_CLASS_C_DEC::iterator
 545     PB_DS_CLASS_C_DEC::
 546     remove_child(iterator it)
 547     {
 548       iterator ret = it;
 549
 550       ++ret;
 551
 552       * it.m_p_p_cur = NULL;
 553
 554       return (ret);
 555     }
 556
 557     PB_DS_CLASS_T_DEC
 558     void
 559     PB_DS_CLASS_C_DEC::
 560     replace_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, const_e_access_traits_pointer p_traits)
 561     {
 562       const size_type i = get_pref_pos(        b_it, e_it, p_traits);
 563
 564       PB_DS_DBG_ASSERT(i < arr_size);
 565
 566       m_a_p_children[i] = p_nd;
 567
 568       p_nd->m_p_parent = this;
 569     }
 570
 571     PB_DS_CLASS_T_DEC
 572     inline typename PB_DS_CLASS_C_DEC::const_e_iterator
 573     PB_DS_CLASS_C_DEC::
 574     pref_b_it() const
 575     {
 576       return (m_pref_b_it);
 577     }
 578
 579     PB_DS_CLASS_T_DEC
 580     inline typename PB_DS_CLASS_C_DEC::const_e_iterator
 581     PB_DS_CLASS_C_DEC::
 582     pref_e_it() const
 583     {
 584       return (m_pref_e_it);
 585     }
 586
 587     PB_DS_CLASS_T_DEC
 588     inline typename PB_DS_CLASS_C_DEC::size_type
 589     PB_DS_CLASS_C_DEC::
 590     get_e_ind() const
 591     {
 592       return (m_e_ind);
 593     }
 594
 595     PB_DS_CLASS_T_DEC
 596     bool
 597     PB_DS_CLASS_C_DEC::
 598     should_be_mine(const_e_iterator b_it, const_e_iterator e_it, size_type checked_ind, const_e_access_traits_pointer p_traits) const
 599     {
 600       if (m_e_ind == 0)
 601         return (true);
 602
 603       const size_type num_es = std::distance(b_it, e_it);
 604
 605       if (num_es < m_e_ind)
 606         return (false);
 607
 608       const_e_iterator key_b_it = b_it;
 609       std::advance(key_b_it, checked_ind);
 610       const_e_iterator key_e_it = b_it;
 611       std::advance(key_e_it, m_e_ind);
 612
 613       const_e_iterator value_b_it = m_pref_b_it;
 614       std::advance(value_b_it, checked_ind);
 615       const_e_iterator value_e_it = m_pref_b_it;
 616       std::advance(value_e_it, m_e_ind);
 617
 618       return (p_traits->equal_prefixes(            key_b_it, key_e_it, value_b_it, value_e_it));
 619     }
 620
 621     PB_DS_CLASS_T_DEC
 622     typename PB_DS_CLASS_C_DEC::leaf_pointer
 623     PB_DS_CLASS_C_DEC::
 624     leftmost_descendant()
 625     {
 626       node_pointer p_pot =* begin();
 627
 628       if (p_pot->m_type == pat_trie_leaf_node_type)
 629         return (static_cast<leaf_pointer>(p_pot));
 630
 631       PB_DS_DBG_ASSERT(p_pot->m_type == pat_trie_internal_node_type);
 632
 633       return (static_cast<internal_node_pointer>(p_pot)->leftmost_descendant());
 634     }
 635
 636     PB_DS_CLASS_T_DEC
 637     typename PB_DS_CLASS_C_DEC::const_leaf_pointer
 638     PB_DS_CLASS_C_DEC::
 639     leftmost_descendant() const
 640     {
 641       return (const_cast<internal_node_pointer>(this)->leftmost_descendant());
 642     }
 643
 644     PB_DS_CLASS_T_DEC
 645     typename PB_DS_CLASS_C_DEC::leaf_pointer
 646     PB_DS_CLASS_C_DEC::
 647     rightmost_descendant()
 648     {
 649       const size_type num_children = std::distance(begin(), end());
 650
 651       PB_DS_DBG_ASSERT(num_children >= 2);
 652
 653       iterator it = begin();
 654       std::advance(it, num_children - 1);
 655
 656       node_pointer p_pot =* it;
 657
 658       if (p_pot->m_type == pat_trie_leaf_node_type)
 659         return (static_cast<leaf_pointer>(p_pot));
 660
 661       PB_DS_DBG_ASSERT(p_pot->m_type == pat_trie_internal_node_type);
 662
 663       return (static_cast<internal_node_pointer>(p_pot)->rightmost_descendant());
 664     }
 665
 666     PB_DS_CLASS_T_DEC
 667     typename PB_DS_CLASS_C_DEC::const_leaf_pointer
 668     PB_DS_CLASS_C_DEC::
 669     rightmost_descendant() const
 670     {
 671       return (const_cast<internal_node_pointer>(this)->rightmost_descendant());
 672     }
 673
 674 #ifdef PB_DS_PAT_TRIE_DEBUG_
 675     PB_DS_CLASS_T_DEC
 676     typename PB_DS_CLASS_C_DEC::size_type
 677     PB_DS_CLASS_C_DEC::
 678     e_ind() const
 679     {
 680       return (m_e_ind);
 681     }
 682 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 683
 684     PB_DS_CLASS_T_DEC
 685     typename PB_DS_CLASS_C_DEC::size_type
 686     PB_DS_CLASS_C_DEC::
 687     get_begin_pos() const
 688     {
 689       size_type i;
 690
 691       for (i = 0; i < arr_size&&  m_a_p_children[i] == NULL; ++i)
 692         ;
 693
 694       return (i);
 695     }
 696
 697 #ifdef PB_DS_PAT_TRIE_DEBUG_
 698     PB_DS_CLASS_T_DEC
 699     typename PB_DS_CLASS_C_DEC::subtree_debug_info
 700     PB_DS_CLASS_C_DEC::
 701     assert_valid_imp(const_e_access_traits_pointer p_traits) const
 702     {
 703       PB_DS_DBG_ASSERT(base_type::m_type == pat_trie_internal_node_type);
 704
 705       PB_DS_DBG_ASSERT(
 706                        static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) ==
 707                        m_e_ind);
 708
 709       PB_DS_DBG_ASSERT(
 710                        std::distance(begin(), end()) >= 2);
 711
 712       for (typename pat_trie_internal_node::const_iterator it = begin();
 713            it != end(); ++it)
 714         {
 715           const_node_pointer p_nd =* it;
 716
 717           PB_DS_DBG_ASSERT(p_nd->m_p_parent == this);
 718
 719           subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits);
 720
 721           PB_DS_DBG_ASSERT(
 722                            static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >=
 723                            m_e_ind);
 724
 725           PB_DS_DBG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
 726
 727           PB_DS_DBG_ASSERT(
 728                            get_pref_pos(child_ret.first, child_ret.second, p_traits) ==
 729                            static_cast<size_type>(it.m_p_p_cur - m_a_p_children));
 730         }
 731
 732       return (std::make_pair(pref_b_it(), pref_e_it()));
 733     }
 734 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 735
 736 #undef PB_DS_CLASS_T_DEC
 737
 738 #undef PB_DS_CLASS_C_DEC
 739
 740 #undef PB_DS_BASE_C_DEC
 741
 742 #undef PB_DS_LEAF_C_DEC
 743
 744 #undef PB_DS_STATIC_ASSERT
 745
 746 #undef PB_DS_DBG_ASSERT
 747 #undef PB_DS_DBG_VERIFY
 748 #undef PB_DS_DBG_ONLY
 749
 750   } // namespace detail
 751 } // namespace pb_ds
 752
 753 #endif // #ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP
 754