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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the terms
   8 // of the GNU General Public License as published by the Free Software
   9 // Foundation; either version 3, or (at your option) any later
  10 // version.
  11
  12 // This library is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  27
  28 // Permission to use, copy, modify, sell, and distribute this software
  29 // is hereby granted without fee, provided that the above copyright
  30 // notice appears in all copies, and that both that copyright notice
  31 // and this permission notice appear in supporting documentation. None
  32 // of the above authors, nor IBM Haifa Research Laboratories, make any
  33 // representation about the suitability of this software for any
  34 // purpose. It is provided "as is" without express or implied
  35 // warranty.
  36
  37 /**
  38  * @file pat_trie_.hpp
  39  * Contains an implementation class for a patricia tree.
  40  */
  41
  42 /**
  43  * This implementation loosely borrows ideas from:
  44  * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998
  45  * 2) Ptset: Sets of integers implemented as Patricia trees,
  46  *    Jean-Christophe Filliatr, 2000
  47  **/
  48
  49 #include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>
  50 #include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
  51 #include <ext/pb_ds/exception.hpp>
  52 #include <ext/pb_ds/tag_and_trait.hpp>
  53 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  54 #include <ext/pb_ds/detail/types_traits.hpp>
  55 #include <ext/pb_ds/tree_policy.hpp>
  56 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  57 #include <ext/pb_ds/detail/type_utils.hpp>
  58 #include <iterator>
  59 #include <utility>
  60 #include <algorithm>
  61 #include <functional>
  62 #include <assert.h>
  63 #include <list>
  64 #ifdef _GLIBCXX_DEBUG
  65 #include <ext/pb_ds/detail/debug_map_base.hpp>
  66 #endif
  67 #include <debug/debug.h>
  68
  69 namespace __gnu_pbds
  70 {
  71   namespace detail
  72   {
  73 #define PB_DS_CLASS_T_DEC \
  74     template<typename Key, typename Mapped, typename Node_And_It_Traits, \
  75              typename Allocator>
  76
  77 #ifdef PB_DS_DATA_TRUE_INDICATOR
  78 #define PB_DS_CLASS_NAME pat_trie_data_
  79 #endif
  80
  81 #ifdef PB_DS_DATA_FALSE_INDICATOR
  82 #define PB_DS_CLASS_NAME pat_trie_no_data_
  83 #endif
  84
  85 #define PB_DS_CLASS_C_DEC \
  86     PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator>
  87
  88 #define PB_DS_TYPES_TRAITS_C_DEC \
  89     types_traits<Key, Mapped, Allocator, false>
  90
  91 #ifdef _GLIBCXX_DEBUG
  92 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
  93     debug_map_base<Key, eq_by_less<Key, \
  94                         std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference>
  95 #endif
  96
  97 #ifdef PB_DS_DATA_TRUE_INDICATOR
  98 #define PB_DS_V2F(X) (X).first
  99 #define PB_DS_V2S(X) (X).second
 100 #define PB_DS_EP2VP(X)& ((X)->m_value)
 101 #endif
 102
 103 #ifdef PB_DS_DATA_FALSE_INDICATOR
 104 #define PB_DS_V2F(X) (X)
 105 #define PB_DS_V2S(X) Mapped_Data()
 106 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
 107 #endif
 108
 109     /**
 110      * class description = PATRICIA trie implementation.">
 111      **/
 112     template<typename Key,
 113              typename Mapped,
 114              typename Node_And_It_Traits,
 115              typename Allocator>
 116     class PB_DS_CLASS_NAME :
 117 #ifdef _GLIBCXX_DEBUG
 118       public PB_DS_DEBUG_MAP_BASE_C_DEC,
 119 #endif
 120       public Node_And_It_Traits::synth_e_access_traits,
 121       public Node_And_It_Traits::node_update,
 122       public PB_DS_TYPES_TRAITS_C_DEC
 123     {
 124     private:
 125       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 126
 127       typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits;
 128       typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer;
 129       typedef typename synth_e_access_traits::const_iterator const_e_iterator;
 130
 131       typedef typename Node_And_It_Traits::node node;
 132       typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer;
 133
 134       typedef typename Allocator::template rebind<node>::other::pointer node_pointer;
 135
 136       typedef typename Node_And_It_Traits::head head;
 137       typedef typename Allocator::template rebind<head>::other head_allocator;
 138       typedef typename head_allocator::pointer head_pointer;
 139
 140       typedef typename Node_And_It_Traits::leaf leaf;
 141       typedef typename Allocator::template rebind<leaf>::other leaf_allocator;
 142       typedef typename leaf_allocator::const_pointer const_leaf_pointer;
 143       typedef typename leaf_allocator::pointer leaf_pointer;
 144
 145       typedef typename Node_And_It_Traits::internal_node internal_node;
 146       typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator;
 147       typedef typename internal_node_allocator::const_pointer const_internal_node_pointer;
 148       typedef typename internal_node_allocator::pointer internal_node_pointer;
 149
 150 #include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp>
 151
 152 #ifdef _GLIBCXX_DEBUG
 153       typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
 154 #endif
 155
 156 #include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp>
 157
 158       typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer;
 159
 160     public:
 161       typedef pat_trie_tag container_category;
 162       typedef Allocator allocator_type;
 163       typedef typename Allocator::size_type size_type;
 164       typedef typename Allocator::difference_type difference_type;
 165
 166       typedef typename traits_base::key_type key_type;
 167       typedef typename traits_base::key_pointer key_pointer;
 168       typedef typename traits_base::const_key_pointer const_key_pointer;
 169       typedef typename traits_base::key_reference key_reference;
 170       typedef typename traits_base::const_key_reference const_key_reference;
 171       typedef typename traits_base::mapped_type mapped_type;
 172       typedef typename traits_base::mapped_pointer mapped_pointer;
 173       typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
 174       typedef typename traits_base::mapped_reference mapped_reference;
 175       typedef typename traits_base::const_mapped_reference const_mapped_reference;
 176       typedef typename traits_base::value_type value_type;
 177       typedef typename traits_base::pointer pointer;
 178       typedef typename traits_base::const_pointer const_pointer;
 179       typedef typename traits_base::reference reference;
 180       typedef typename traits_base::const_reference const_reference;
 181
 182       typedef typename Node_And_It_Traits::const_iterator const_point_iterator;
 183       typedef typename Node_And_It_Traits::iterator point_iterator;
 184       typedef const_point_iterator const_iterator;
 185       typedef point_iterator iterator;
 186
 187       typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator;
 188       typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
 189       typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator;
 190       typedef typename Node_And_It_Traits::node_iterator node_iterator;
 191       typedef typename Node_And_It_Traits::e_access_traits e_access_traits;
 192       typedef typename Node_And_It_Traits::node_update node_update;
 193
 194       PB_DS_CLASS_NAME();
 195
 196       PB_DS_CLASS_NAME(const e_access_traits&);
 197
 198       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 199
 200       void
 201       swap(PB_DS_CLASS_C_DEC&);
 202
 203       ~PB_DS_CLASS_NAME();
 204
 205       inline bool
 206       empty() const;
 207
 208       inline size_type
 209       size() const;
 210
 211       inline size_type
 212       max_size() const;
 213
 214       e_access_traits&
 215       get_e_access_traits();
 216
 217       const e_access_traits&
 218       get_e_access_traits() const;
 219
 220       node_update&
 221       get_node_update();
 222
 223       const node_update&
 224       get_node_update() const;
 225
 226       inline std::pair<point_iterator, bool>
 227       insert(const_reference);
 228
 229       inline mapped_reference
 230       operator[](const_key_reference r_key)
 231       {
 232 #ifdef PB_DS_DATA_TRUE_INDICATOR
 233         return insert(std::make_pair(r_key, mapped_type())).first->second;
 234 #else
 235         insert(r_key);
 236         return traits_base::s_null_mapped;
 237 #endif
 238       }
 239
 240       inline point_iterator
 241       find(const_key_reference);
 242
 243       inline const_point_iterator
 244       find(const_key_reference) const;
 245
 246       inline point_iterator
 247       lower_bound(const_key_reference);
 248
 249       inline const_point_iterator
 250       lower_bound(const_key_reference) const;
 251
 252       inline point_iterator
 253       upper_bound(const_key_reference);
 254
 255       inline const_point_iterator
 256       upper_bound(const_key_reference) const;
 257
 258       void
 259       clear();
 260
 261       inline bool
 262       erase(const_key_reference);
 263
 264       inline const_iterator
 265       erase(const_iterator);
 266
 267 #ifdef PB_DS_DATA_TRUE_INDICATOR
 268       inline iterator
 269       erase(iterator);
 270 #endif
 271
 272       inline const_reverse_iterator
 273       erase(const_reverse_iterator);
 274
 275 #ifdef PB_DS_DATA_TRUE_INDICATOR
 276       inline reverse_iterator
 277       erase(reverse_iterator);
 278 #endif
 279
 280       template<typename Pred>
 281       inline size_type
 282       erase_if(Pred);
 283
 284       void
 285       join(PB_DS_CLASS_C_DEC&);
 286
 287       void
 288       split(const_key_reference, PB_DS_CLASS_C_DEC&);
 289
 290       inline iterator
 291       begin();
 292
 293       inline const_iterator
 294       begin() const;
 295
 296       inline iterator
 297       end();
 298
 299       inline const_iterator
 300       end() const;
 301
 302       inline reverse_iterator
 303       rbegin();
 304
 305       inline const_reverse_iterator
 306       rbegin() const;
 307
 308       inline reverse_iterator
 309       rend();
 310
 311       inline const_reverse_iterator
 312       rend() const;
 313
 314       inline const_node_iterator
 315       node_begin() const;
 316
 317       inline node_iterator
 318       node_begin();
 319
 320       inline const_node_iterator
 321       node_end() const;
 322
 323       inline node_iterator
 324       node_end();
 325
 326 #ifdef PB_DS_PAT_TRIE_TRACE_
 327       void
 328       trace() const;
 329 #endif
 330
 331     protected:
 332
 333       template<typename It>
 334       void
 335       copy_from_range(It, It);
 336
 337       void
 338       value_swap(PB_DS_CLASS_C_DEC&);
 339
 340       node_pointer
 341       recursive_copy_node(const_node_pointer);
 342
 343     private:
 344
 345       void
 346       initialize();
 347
 348       inline void
 349       apply_update(node_pointer, null_node_update_pointer);
 350
 351       template<typename Node_Update_>
 352       inline void
 353       apply_update(node_pointer, Node_Update_*);
 354
 355       bool
 356       join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&);
 357
 358       void
 359       rec_join_prep(const_node_pointer, const_node_pointer,
 360                     split_join_branch_bag&);
 361
 362       void
 363       rec_join_prep(const_leaf_pointer, const_leaf_pointer,
 364                     split_join_branch_bag&);
 365
 366       void
 367       rec_join_prep(const_leaf_pointer, const_internal_node_pointer,
 368                     split_join_branch_bag&);
 369
 370       void
 371       rec_join_prep(const_internal_node_pointer, const_leaf_pointer,
 372                     split_join_branch_bag&);
 373
 374       void
 375       rec_join_prep(const_internal_node_pointer, const_internal_node_pointer,
 376                     split_join_branch_bag&);
 377
 378       node_pointer
 379       rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&);
 380
 381       node_pointer
 382       rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&);
 383
 384       node_pointer
 385       rec_join(leaf_pointer, internal_node_pointer, size_type,
 386                split_join_branch_bag&);
 387
 388       node_pointer
 389       rec_join(internal_node_pointer, leaf_pointer, size_type,
 390                split_join_branch_bag&);
 391
 392       node_pointer
 393       rec_join(internal_node_pointer, internal_node_pointer,
 394                split_join_branch_bag&);
 395
 396       size_type
 397       keys_diff_ind(typename e_access_traits::const_iterator,
 398                     typename e_access_traits::const_iterator,
 399                     typename e_access_traits::const_iterator,
 400                     typename e_access_traits::const_iterator);
 401
 402       internal_node_pointer
 403       insert_branch(node_pointer, node_pointer, split_join_branch_bag&);
 404
 405       void
 406       update_min_max_for_inserted_leaf(leaf_pointer);
 407
 408       void
 409       erase_leaf(leaf_pointer);
 410
 411       inline void
 412       actual_erase_leaf(leaf_pointer);
 413
 414       void
 415       clear_imp(node_pointer);
 416
 417       void
 418       erase_fixup(internal_node_pointer);
 419
 420       void
 421       update_min_max_for_erased_leaf(leaf_pointer);
 422
 423       static inline const_e_iterator
 424       pref_begin(const_node_pointer);
 425
 426       static inline const_e_iterator
 427       pref_end(const_node_pointer);
 428
 429       inline node_pointer
 430       find_imp(const_key_reference);
 431
 432       inline node_pointer
 433       lower_bound_imp(const_key_reference);
 434
 435       inline node_pointer
 436       upper_bound_imp(const_key_reference);
 437
 438       inline static const_leaf_pointer
 439       leftmost_descendant(const_node_pointer);
 440
 441       inline static leaf_pointer
 442       leftmost_descendant(node_pointer);
 443
 444       inline static const_leaf_pointer
 445       rightmost_descendant(const_node_pointer);
 446
 447       inline static leaf_pointer
 448       rightmost_descendant(node_pointer);
 449
 450 #ifdef _GLIBCXX_DEBUG
 451       void
 452       assert_valid(const char* file, int line) const;
 453
 454       void
 455       assert_iterators(const char* file, int line) const;
 456
 457       void
 458       assert_reverse_iterators(const char* file, int line) const;
 459
 460       static size_type
 461       recursive_count_leafs(const_node_pointer,
 462                             const char* file, int line);
 463 #endif
 464
 465 #ifdef PB_DS_PAT_TRIE_TRACE_
 466       static void
 467       trace_node(const_node_pointer, size_type);
 468
 469       template<typename Metadata_>
 470       static void
 471       trace_node_metadata(const_node_pointer, type_to_type<Metadata_>);
 472
 473       static void
 474       trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>);
 475 #endif
 476
 477       leaf_pointer
 478       split_prep(const_key_reference, PB_DS_CLASS_C_DEC&,
 479                  split_join_branch_bag&);
 480
 481       node_pointer
 482       rec_split(node_pointer, const_e_iterator, const_e_iterator,
 483                 PB_DS_CLASS_C_DEC&, split_join_branch_bag&);
 484
 485       void
 486       split_insert_branch(size_type, const_e_iterator,
 487                           typename internal_node::iterator,
 488                           size_type, split_join_branch_bag&);
 489
 490       static head_allocator s_head_allocator;
 491       static internal_node_allocator s_internal_node_allocator;
 492       static leaf_allocator s_leaf_allocator;
 493
 494       head_pointer m_p_head;
 495       size_type m_size;
 496     };
 497
 498 #define PB_DS_ASSERT_VALID(X)                                           \
 499   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
 500
 501 #define PB_DS_ASSERT_NODE_VALID(X)                                      \
 502   _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)
 503
 504 #define PB_DS_RECURSIVE_COUNT_LEAFS(X)                                  \
 505   recursive_count_leafs(X, __FILE__, __LINE__)
 506
 507 #define PB_DS_CHECK_KEY_EXISTS(_Key)                                    \
 508   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);)
 509
 510 #define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key)                            \
 511   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key,        \
 512                                                            __FILE__, __LINE__);)
 513
 514 #define PB_DS_DEBUG_VERIFY(_Cond)                                       \
 515   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
 516                            _M_message(#_Cond" assertion from %1;:%2;")  \
 517                            ._M_string(__FILE__)._M_integer(__LINE__)    \
 518                            ,__file,__line)
 519
 520 #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp>
 521 #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp>
 522 #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp>
 523 #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp>
 524 #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp>
 525 #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp>
 526 #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp>
 527 #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp>
 528 #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp>
 529 #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp>
 530 #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp>
 531
 532 #undef PB_DS_DEBUG_VERIFY
 533 #undef PB_DS_CHECK_KEY_DOES_NOT_EXIST
 534 #undef PB_DS_CHECK_KEY_EXISTS
 535 #undef PB_DS_RECURSIVE_COUNT_LEAFS
 536 #undef PB_DS_ASSERT_NODE_VALID
 537 #undef PB_DS_ASSERT_VALID
 538 #undef PB_DS_CLASS_C_DEC
 539 #undef PB_DS_CLASS_T_DEC
 540 #undef PB_DS_CLASS_NAME
 541 #undef PB_DS_TYPES_TRAITS_C_DEC
 542 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 543 #undef PB_DS_V2F
 544 #undef PB_DS_EP2VP
 545 #undef PB_DS_V2S
 546
 547   } // namespace detail
 548 } // namespace __gnu_pbds