libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.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 pat_trie_.hpp
  44  * Contains an implementation class for a patricia tree.
  45  */
  46
  47 /**
  48  * This implementation loosely borrows ideas from:
  49  * 1) "Fast Mergeable Integer Maps", Okasaki, Gill 1998
  50  * 2) "Ptset: Sets of integers implemented as Patricia trees",
  51  *    Jean-Christophe Filliatr, 2000
  52  **/
  53
  54 #include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>
  55 #include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
  56 #include <ext/pb_ds/exception.hpp>
  57 #include <ext/pb_ds/tag_and_trait.hpp>
  58 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  59 #include <ext/pb_ds/detail/types_traits.hpp>
  60 #include <ext/pb_ds/tree_policy.hpp>
  61 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  62 #include <ext/pb_ds/detail/type_utils.hpp>
  63 #include <iterator>
  64 #include <utility>
  65 #include <algorithm>
  66 #include <functional>
  67 #include <assert.h>
  68 #include <list>
  69 #ifdef PB_DS_USE_MAP_DEBUG_BASE
  70 #include <ext/pb_ds/detail/map_debug_base.hpp>
  71 #endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
  72
  73 namespace pb_ds
  74 {
  75   namespace detail
  76   {
  77
  78 #ifdef PB_DS_PAT_TRIE_DEBUG_
  79 #define PB_DS_DBG_ASSERT(X) assert(X)
  80 #define PB_DS_DBG_VERIFY(X) assert(X)
  81 #define PB_DS_DBG_ONLY(X) X
  82 #else // #ifdef PB_DS_PAT_TRIE_DEBUG_
  83 #define PB_DS_DBG_ASSERT(X)
  84 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
  85 #define PB_DS_DBG_ONLY(X) ;
  86 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
  87
  88 #define PB_DS_CLASS_T_DEC                                               \
  89     template<                                                           \
  90                                                 typename Key,           \
  91                                                 typename Mapped,        \
  92                                                 class Node_And_It_Traits, \
  93                                                 class Allocator>
  94
  95 #ifdef PB_DS_DATA_TRUE_INDICATOR
  96 #define PB_DS_CLASS_NAME                        \
  97     pat_trie_data_
  98 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
  99
 100 #ifdef PB_DS_DATA_FALSE_INDICATOR
 101 #define PB_DS_CLASS_NAME                        \
 102     pat_trie_no_data_
 103 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 104
 105 #define PB_DS_CLASS_C_DEC                                               \
 106     PB_DS_CLASS_NAME<                                                   \
 107                                                 Key,                    \
 108                                                 Mapped,                 \
 109                                                 Node_And_It_Traits,     \
 110                                                 Allocator>
 111
 112 #define PB_DS_TYPES_TRAITS_C_DEC                                \
 113     types_traits<                               \
 114                                                 Key,            \
 115                                                 Mapped,         \
 116                                                 Allocator,      \
 117                                                 false>
 118
 119 #ifdef PB_DS_USE_MAP_DEBUG_BASE
 120 #define PB_DS_MAP_DEBUG_BASE_C_DEC                                      \
 121     map_debug_base<                                     \
 122                                                                 Key,    \
 123                                                                 eq_by_less< \
 124                                                                                                 Key, \
 125                                                                                                 std::less< \
 126                                                                                                                 Key> >, \
 127                                                                 typename Allocator::template rebind< \
 128                                                                                                      Key>::other::const_reference>
 129 #endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
 130
 131 #ifdef PB_DS_DATA_TRUE_INDICATOR
 132 #define PB_DS_V2F(X) (X).first
 133 #define PB_DS_V2S(X) (X).second
 134 #define PB_DS_EP2VP(X)& ((X)->m_value)
 135 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 136
 137 #ifdef PB_DS_DATA_FALSE_INDICATOR
 138 #define PB_DS_V2F(X) (X)
 139 #define PB_DS_V2S(X) Mapped_Data()
 140 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
 141 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 142
 143 #define PB_DS_STATIC_ASSERT(UNIQUE, E)                                  \
 144     typedef                                                             \
 145     static_assert_dumclass<                             \
 146                                                                         sizeof(static_assert<(bool)(E)>)> \
 147     UNIQUE##static_assert_type
 148
 149     /**
 150      * class description = PATRICIA trie implementation.">
 151      **/
 152     template<typename Key,
 153              typename Mapped,
 154              class Node_And_It_Traits,
 155              class Allocator>
 156     class PB_DS_CLASS_NAME :
 157 #ifdef PB_DS_PAT_TRIE_DEBUG_
 158       public PB_DS_MAP_DEBUG_BASE_C_DEC,
 159 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 160       public Node_And_It_Traits::synth_e_access_traits,
 161       public Node_And_It_Traits::node_update,
 162       public PB_DS_TYPES_TRAITS_C_DEC
 163     {
 164
 165     private:
 166
 167       typedef
 168       typename Node_And_It_Traits::synth_e_access_traits
 169       synth_e_access_traits;
 170
 171       typedef
 172       typename Allocator::template rebind<
 173         synth_e_access_traits>::other::const_pointer
 174       const_e_access_traits_pointer;
 175
 176       typedef
 177       typename synth_e_access_traits::const_iterator
 178       const_e_iterator;
 179
 180       typedef typename Node_And_It_Traits::node node;
 181
 182       typedef
 183       typename Allocator::template rebind<
 184         node>::other::const_pointer
 185       const_node_pointer;
 186
 187       typedef
 188       typename Allocator::template rebind<
 189         node>::other::pointer
 190       node_pointer;
 191
 192       typedef typename Node_And_It_Traits::head head;
 193
 194       typedef
 195       typename Allocator::template rebind<
 196         head>::other
 197       head_allocator;
 198
 199       typedef typename head_allocator::pointer head_pointer;
 200
 201       typedef typename Node_And_It_Traits::leaf leaf;
 202
 203       typedef
 204       typename Allocator::template rebind<
 205         leaf>::other
 206       leaf_allocator;
 207
 208       typedef typename leaf_allocator::const_pointer const_leaf_pointer;
 209
 210       typedef typename leaf_allocator::pointer leaf_pointer;
 211
 212       typedef typename Node_And_It_Traits::internal_node internal_node;
 213
 214       typedef
 215       typename Allocator::template rebind<
 216         internal_node>::other
 217       internal_node_allocator;
 218
 219       typedef
 220       typename internal_node_allocator::const_pointer
 221       const_internal_node_pointer;
 222
 223       typedef
 224       typename internal_node_allocator::pointer
 225       internal_node_pointer;
 226
 227       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 228
 229 #include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp>
 230
 231 #ifdef PB_DS_PAT_TRIE_DEBUG_
 232       typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
 233 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 234
 235 #include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp>
 236
 237       typedef
 238       typename Node_And_It_Traits::null_node_update_pointer
 239       null_node_update_pointer;
 240
 241     public:
 242       typedef pat_trie_tag container_category;
 243
 244       typedef typename Allocator::size_type size_type;
 245
 246       typedef typename Allocator::difference_type difference_type;
 247
 248       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
 249
 250       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
 251
 252       typedef
 253       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
 254       const_key_pointer;
 255
 256       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
 257
 258       typedef
 259       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
 260       const_key_reference;
 261
 262       typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
 263
 264       typedef
 265       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
 266       mapped_pointer;
 267
 268       typedef
 269       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
 270       const_mapped_pointer;
 271
 272       typedef
 273       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
 274       mapped_reference;
 275
 276       typedef
 277       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
 278       const_mapped_reference;
 279
 280       typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
 281
 282       typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
 283
 284       typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
 285
 286       typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
 287
 288       typedef
 289       typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
 290       const_reference;
 291
 292       typedef
 293       typename Node_And_It_Traits::const_iterator
 294       const_point_iterator;
 295
 296       typedef typename Node_And_It_Traits::iterator point_iterator;
 297
 298       typedef const_point_iterator const_iterator;
 299
 300       typedef point_iterator iterator;
 301
 302       typedef
 303       typename Node_And_It_Traits::const_reverse_iterator
 304       const_reverse_iterator;
 305
 306       typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
 307
 308       typedef
 309       typename Node_And_It_Traits::const_node_iterator
 310       const_node_iterator;
 311
 312       typedef typename Node_And_It_Traits::node_iterator node_iterator;
 313
 314       typedef typename Node_And_It_Traits::e_access_traits e_access_traits;
 315
 316       typedef typename Node_And_It_Traits::node_update node_update;
 317
 318       typedef Allocator allocator;
 319
 320     public:
 321
 322       PB_DS_CLASS_NAME();
 323
 324       PB_DS_CLASS_NAME(const e_access_traits& r_e_access_traits);
 325
 326       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
 327
 328       void
 329       swap(PB_DS_CLASS_C_DEC& other);
 330
 331       ~PB_DS_CLASS_NAME();
 332
 333       inline bool
 334       empty() const;
 335
 336       inline size_type
 337       size() const;
 338
 339       inline size_type
 340       max_size() const;
 341
 342       e_access_traits&
 343       get_e_access_traits();
 344
 345       const e_access_traits&
 346       get_e_access_traits() const;
 347
 348       node_update&
 349       get_node_update();
 350
 351       const node_update&
 352       get_node_update() const;
 353
 354       inline std::pair<
 355         point_iterator,
 356         bool>
 357       insert(const_reference r_val);
 358
 359       inline mapped_reference
 360       operator[](const_key_reference r_key)
 361       {
 362 #ifdef PB_DS_DATA_TRUE_INDICATOR
 363         return (insert(std::make_pair(
 364                                       r_key,
 365                                       mapped_type())).first->second);
 366 #else // #ifdef PB_DS_DATA_TRUE_INDICATOR
 367         insert(r_key);
 368
 369         return (traits_base::s_null_mapped);
 370 #endif // #ifdef PB_DS_DATA_TRUE
 371       }
 372
 373       inline point_iterator
 374       find(const_key_reference r_key);
 375
 376       inline const_point_iterator
 377       find(const_key_reference r_key) const;
 378
 379       inline point_iterator
 380       lower_bound(const_key_reference r_key);
 381
 382       inline const_point_iterator
 383       lower_bound(const_key_reference r_key) const;
 384
 385       inline point_iterator
 386       upper_bound(const_key_reference r_key);
 387
 388       inline const_point_iterator
 389       upper_bound(const_key_reference r_key) const;
 390
 391       void
 392       clear();
 393
 394       inline bool
 395       erase(const_key_reference r_key);
 396
 397       inline const_iterator
 398       erase(const_iterator it);
 399
 400 #ifdef PB_DS_DATA_TRUE_INDICATOR
 401       inline iterator
 402       erase(iterator it);
 403 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 404
 405       inline const_reverse_iterator
 406       erase(const_reverse_iterator it);
 407
 408 #ifdef PB_DS_DATA_TRUE_INDICATOR
 409       inline reverse_iterator
 410       erase(reverse_iterator it);
 411 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 412
 413       template<typename Pred>
 414       inline size_type
 415       erase_if(Pred pred);
 416
 417       void
 418       join(PB_DS_CLASS_C_DEC& other);
 419
 420       void
 421       split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
 422
 423       inline iterator
 424       begin();
 425
 426       inline const_iterator
 427       begin() const;
 428
 429       inline iterator
 430       end();
 431
 432       inline const_iterator
 433       end() const;
 434
 435       inline reverse_iterator
 436       rbegin();
 437
 438       inline const_reverse_iterator
 439       rbegin() const;
 440
 441       inline reverse_iterator
 442       rend();
 443
 444       inline const_reverse_iterator
 445       rend() const;
 446
 447       inline const_node_iterator
 448       node_begin() const;
 449
 450       inline node_iterator
 451       node_begin();
 452
 453       inline const_node_iterator
 454       node_end() const;
 455
 456       inline node_iterator
 457       node_end();
 458
 459 #ifdef PB_DS_PAT_TRIE_TRACE_
 460
 461       void
 462       trace() const;
 463
 464 #endif // #ifdef PB_DS_PAT_TRIE_TRACE_
 465
 466     protected:
 467
 468       template<typename It>
 469       void
 470       copy_from_range(It first_it, It last_it);
 471
 472       void
 473       value_swap(PB_DS_CLASS_C_DEC& other);
 474
 475       node_pointer
 476       recursive_copy_node(const_node_pointer p_other_nd);
 477
 478     private:
 479
 480       void
 481       initialize();
 482
 483       inline void
 484       apply_update(node_pointer p_nd, null_node_update_pointer);
 485
 486       template<typename Node_Update_>
 487       inline void
 488       apply_update(node_pointer p_nd, Node_Update_* p_update);
 489
 490       bool
 491       join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag);
 492
 493       void
 494       rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag);
 495
 496       void
 497       rec_join_prep(const_leaf_pointer p_l, const_leaf_pointer p_r, split_join_branch_bag& r_bag);
 498
 499       void
 500       rec_join_prep(const_leaf_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag);
 501
 502       void
 503       rec_join_prep(const_internal_node_pointer p_l, const_leaf_pointer p_r, split_join_branch_bag& r_bag);
 504
 505       void
 506       rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag);
 507
 508       node_pointer
 509       rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag);
 510
 511       node_pointer
 512       rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag);
 513
 514       node_pointer
 515       rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag);
 516
 517       node_pointer
 518       rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag);
 519
 520       node_pointer
 521       rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag);
 522
 523       size_type
 524       keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r);
 525
 526       internal_node_pointer
 527       insert_branch(node_pointer p_left_nd, node_pointer p_right_nd, split_join_branch_bag& r_bag);
 528
 529       void
 530       update_min_max_for_inserted_leaf(leaf_pointer p_l);
 531
 532       void
 533       erase_leaf(leaf_pointer p_l);
 534
 535       inline void
 536       actual_erase_leaf(leaf_pointer p_lf);
 537
 538       void
 539       clear_imp(node_pointer p_nd);
 540
 541       void
 542       erase_fixup(internal_node_pointer p_nd);
 543
 544       void
 545       update_min_max_for_erased_leaf(leaf_pointer p_l);
 546
 547       static inline const_e_iterator
 548       pref_begin(const_node_pointer p_nd);
 549
 550       static inline const_e_iterator
 551       pref_end(const_node_pointer p_nd);
 552
 553       inline node_pointer
 554       find_imp(const_key_reference r_key);
 555
 556       inline node_pointer
 557       lower_bound_imp(const_key_reference r_key);
 558
 559       inline node_pointer
 560       upper_bound_imp(const_key_reference r_key);
 561
 562       inline static const_leaf_pointer
 563       leftmost_descendant(const_node_pointer p_nd);
 564
 565       inline static leaf_pointer
 566       leftmost_descendant(node_pointer p_nd);
 567
 568       inline static const_leaf_pointer
 569       rightmost_descendant(const_node_pointer p_nd);
 570
 571       inline static leaf_pointer
 572       rightmost_descendant(node_pointer p_nd);
 573
 574 #ifdef PB_DS_PAT_TRIE_DEBUG_
 575
 576       void
 577       assert_valid() const;
 578
 579       void
 580       assert_iterators() const;
 581
 582       void
 583       assert_reverse_iterators() const;
 584
 585       static size_type
 586       recursive_count_leafs(const_node_pointer p_nd);
 587
 588 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 589
 590 #ifdef PB_DS_PAT_TRIE_TRACE_
 591
 592       static void
 593       trace_node(const_node_pointer p_nd, size_type level);
 594
 595       template<typename Metadata_>
 596       static void
 597       trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>);
 598
 599       static void
 600       trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>);
 601
 602 #endif // #ifdef PB_DS_PAT_TRIE_TRACE_
 603
 604       leaf_pointer
 605       split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag);
 606
 607       node_pointer
 608       rec_split(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag);
 609
 610       void
 611       split_insert_branch(size_type e_ind, const_e_iterator b_it, typename internal_node::iterator child_b_it, size_type num_children, split_join_branch_bag& r_bag);
 612
 613     private:
 614       static head_allocator s_head_allocator;
 615
 616       static internal_node_allocator s_internal_node_allocator;
 617
 618       static leaf_allocator s_leaf_allocator;
 619
 620       head_pointer m_p_head;
 621
 622       size_type m_size;
 623     };
 624
 625 #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp>
 626 #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp>
 627 #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp>
 628 #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp>
 629 #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp>
 630 #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp>
 631 #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp>
 632 #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp>
 633 #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp>
 634 #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp>
 635 #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp>
 636
 637 #undef PB_DS_CLASS_C_DEC
 638
 639 #undef PB_DS_CLASS_T_DEC
 640
 641 #undef PB_DS_CLASS_NAME
 642
 643 #undef PB_DS_TYPES_TRAITS_C_DEC
 644
 645 #undef PB_DS_MAP_DEBUG_BASE_C_DEC
 646
 647 #undef PB_DS_V2F
 648 #undef PB_DS_EP2VP
 649 #undef PB_DS_V2S
 650
 651 #undef PB_DS_DBG_ASSERT
 652 #undef PB_DS_DBG_VERIFY
 653 #undef PB_DS_DBG_ONLY
 654
 655 #undef PB_DS_STATIC_ASSERT
 656
 657   } // namespace detail
 658 } // namespace pb_ds