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