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