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

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