contrib/gcc-4.7/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_/pat_trie_.hpp
  39  * Contains an implementation class for a patricia tree.
  40  */
  41
  42 #include <iterator>
  43 #include <utility>
  44 #include <algorithm>
  45 #include <functional>
  46 #include <assert.h>
  47 #include <list>
  48 #include <ext/pb_ds/exception.hpp>
  49 #include <ext/pb_ds/tag_and_trait.hpp>
  50 #include <ext/pb_ds/tree_policy.hpp>
  51 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  52 #include <ext/pb_ds/detail/type_utils.hpp>
  53 #include <ext/pb_ds/detail/types_traits.hpp>
  54 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  55 #include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp>
  56 #include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp>
  57 #ifdef _GLIBCXX_DEBUG
  58 #include <ext/pb_ds/detail/debug_map_base.hpp>
  59 #endif
  60 #include <debug/debug.h>
  61
  62 namespace __gnu_pbds
  63 {
  64   namespace detail
  65   {
  66 #ifdef PB_DS_DATA_TRUE_INDICATOR
  67 #define PB_DS_PAT_TRIE_NAME pat_trie_map
  68 #endif
  69
  70 #ifdef PB_DS_DATA_FALSE_INDICATOR
  71 #define PB_DS_PAT_TRIE_NAME pat_trie_set
  72 #endif
  73
  74 #define PB_DS_CLASS_T_DEC \
  75     template<typename Key, typename Mapped, typename Node_And_It_Traits, \
  76              typename _Alloc>
  77
  78 #define PB_DS_CLASS_C_DEC \
  79     PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc>
  80
  81 #define PB_DS_PAT_TRIE_TRAITS_BASE \
  82     types_traits<Key, Mapped, _Alloc, false>
  83
  84 #ifdef _GLIBCXX_DEBUG
  85 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
  86     debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \
  87                  typename _Alloc::template rebind<Key>::other::const_reference>
  88 #endif
  89
  90
  91     /**
  92      *  @brief PATRICIA trie.
  93      *  @ingroup branch-detail
  94      *
  95      *  This implementation loosely borrows ideas from:
  96      *  1) Fast Mergeable Integer Maps, Okasaki, Gill 1998
  97      *  2) Ptset: Sets of integers implemented as Patricia trees,
  98      *     Jean-Christophe Filliatr, 2000
  99      */
 100     template<typename Key, typename Mapped, typename Node_And_It_Traits,
 101              typename _Alloc>
 102     class PB_DS_PAT_TRIE_NAME :
 103 #ifdef _GLIBCXX_DEBUG
 104       public PB_DS_DEBUG_MAP_BASE_C_DEC,
 105 #endif
 106       public Node_And_It_Traits::synth_access_traits,
 107       public Node_And_It_Traits::node_update,
 108       public PB_DS_PAT_TRIE_TRAITS_BASE,
 109       public pat_trie_base
 110     {
 111     private:
 112       typedef pat_trie_base                             base_type;
 113       typedef PB_DS_PAT_TRIE_TRAITS_BASE                traits_base;
 114       typedef Node_And_It_Traits                        traits_type;
 115
 116       typedef typename traits_type::synth_access_traits synth_access_traits;
 117       typedef typename synth_access_traits::const_iterator a_const_iterator;
 118
 119       typedef typename traits_type::node                node;
 120       typedef typename _Alloc::template rebind<node>    __rebind_n;
 121       typedef typename __rebind_n::other::const_pointer node_const_pointer;
 122       typedef typename __rebind_n::other::pointer       node_pointer;
 123
 124       typedef typename traits_type::head                head;
 125       typedef typename _Alloc::template rebind<head>    __rebind_h;
 126       typedef typename __rebind_h::other                head_allocator;
 127       typedef typename head_allocator::pointer          head_pointer;
 128
 129       typedef typename traits_type::leaf                leaf;
 130       typedef typename _Alloc::template rebind<leaf>    __rebind_l;
 131       typedef typename __rebind_l::other                leaf_allocator;
 132       typedef typename leaf_allocator::pointer          leaf_pointer;
 133       typedef typename leaf_allocator::const_pointer    leaf_const_pointer;
 134
 135       typedef typename traits_type::inode               inode;
 136       typedef typename inode::iterator                  inode_iterator;
 137       typedef typename _Alloc::template rebind<inode>   __rebind_in;
 138       typedef typename __rebind_in::other               __rebind_ina;
 139       typedef typename __rebind_in::other               inode_allocator;
 140       typedef typename __rebind_ina::pointer            inode_pointer;
 141       typedef typename __rebind_ina::const_pointer      inode_const_pointer;
 142
 143
 144       /// Conditional deallocator.
 145       class cond_dealtor
 146       {
 147       protected:
 148         leaf_pointer            m_p_nd;
 149         bool                    m_no_action_dtor;
 150         bool                    m_call_destructor;
 151
 152       public:
 153         cond_dealtor(leaf_pointer p_nd)
 154         : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false)
 155         { }
 156
 157         void
 158         set_no_action_dtor()
 159         { m_no_action_dtor = true; }
 160
 161         void
 162         set_call_destructor()
 163         { m_call_destructor = true; }
 164
 165         ~cond_dealtor()
 166         {
 167           if (m_no_action_dtor)
 168             return;
 169
 170           if (m_call_destructor)
 171             m_p_nd->~leaf();
 172
 173           s_leaf_allocator.deallocate(m_p_nd, 1);
 174         }
 175       };
 176
 177
 178       /// Branch bag, for split-join.
 179       class branch_bag
 180       {
 181       private:
 182         typedef inode_pointer                           __inp;
 183         typedef typename _Alloc::template rebind<__inp>::other  __rebind_inp;
 184
 185 #ifdef _GLIBCXX_DEBUG
 186         typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp>  bag_type;
 187 #else
 188         typedef std::list<__inp, __rebind_inp>                  bag_type;
 189 #endif
 190
 191         bag_type                                                m_bag;
 192       public:
 193         void
 194         add_branch()
 195         {
 196           inode_pointer p_nd = s_inode_allocator.allocate(1);
 197           __try
 198             {
 199               m_bag.push_back(p_nd);
 200             }
 201           __catch(...)
 202             {
 203               s_inode_allocator.deallocate(p_nd, 1);
 204               __throw_exception_again;
 205             }
 206         }
 207
 208         inode_pointer
 209         get_branch()
 210         {
 211           _GLIBCXX_DEBUG_ASSERT(!m_bag.empty());
 212           inode_pointer p_nd = *m_bag.begin();
 213           m_bag.pop_front();
 214           return p_nd;
 215         }
 216
 217         ~branch_bag()
 218         {
 219           while (!m_bag.empty())
 220             {
 221               inode_pointer p_nd = *m_bag.begin();
 222               s_inode_allocator.deallocate(p_nd, 1);
 223               m_bag.pop_front();
 224             }
 225         }
 226
 227         inline bool
 228         empty() const
 229         { return m_bag.empty(); }
 230       };
 231
 232 #ifdef _GLIBCXX_DEBUG
 233       typedef PB_DS_DEBUG_MAP_BASE_C_DEC                debug_base;
 234 #endif
 235
 236       typedef typename traits_type::null_node_update_pointer null_node_update_pointer;
 237
 238     public:
 239       typedef pat_trie_tag                              container_category;
 240       typedef _Alloc                                    allocator_type;
 241       typedef typename _Alloc::size_type                size_type;
 242       typedef typename _Alloc::difference_type          difference_type;
 243
 244       typedef typename traits_base::key_type            key_type;
 245       typedef typename traits_base::key_pointer         key_pointer;
 246       typedef typename traits_base::key_const_pointer   key_const_pointer;
 247       typedef typename traits_base::key_reference       key_reference;
 248       typedef typename traits_base::key_const_reference key_const_reference;
 249       typedef typename traits_base::mapped_type         mapped_type;
 250       typedef typename traits_base::mapped_pointer      mapped_pointer;
 251       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
 252       typedef typename traits_base::mapped_reference    mapped_reference;
 253       typedef typename traits_base::mapped_const_reference mapped_const_reference;
 254       typedef typename traits_base::value_type          value_type;
 255       typedef typename traits_base::pointer             pointer;
 256       typedef typename traits_base::const_pointer       const_pointer;
 257       typedef typename traits_base::reference           reference;
 258       typedef typename traits_base::const_reference     const_reference;
 259
 260       typedef typename traits_type::access_traits       access_traits;
 261       typedef typename traits_type::const_iterator      point_const_iterator;
 262       typedef typename traits_type::iterator            point_iterator;
 263       typedef point_const_iterator                      const_iterator;
 264       typedef point_iterator                            iterator;
 265
 266       typedef typename traits_type::reverse_iterator    reverse_iterator;
 267       typedef typename traits_type::const_reverse_iterator const_reverse_iterator;
 268       typedef typename traits_type::node_const_iterator node_const_iterator;
 269       typedef typename traits_type::node_iterator       node_iterator;
 270       typedef typename traits_type::node_update         node_update;
 271
 272       PB_DS_PAT_TRIE_NAME();
 273
 274       PB_DS_PAT_TRIE_NAME(const access_traits&);
 275
 276       PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&);
 277
 278       void
 279       swap(PB_DS_CLASS_C_DEC&);
 280
 281       ~PB_DS_PAT_TRIE_NAME();
 282
 283       inline bool
 284       empty() const;
 285
 286       inline size_type
 287       size() const;
 288
 289       inline size_type
 290       max_size() const;
 291
 292       access_traits&
 293       get_access_traits();
 294
 295       const access_traits&
 296       get_access_traits() const;
 297
 298       node_update&
 299       get_node_update();
 300
 301       const node_update&
 302       get_node_update() const;
 303
 304       inline std::pair<point_iterator, bool>
 305       insert(const_reference);
 306
 307       inline mapped_reference
 308       operator[](key_const_reference r_key)
 309       {
 310 #ifdef PB_DS_DATA_TRUE_INDICATOR
 311         return insert(std::make_pair(r_key, mapped_type())).first->second;
 312 #else
 313         insert(r_key);
 314         return traits_base::s_null_type;
 315 #endif
 316       }
 317
 318       inline point_iterator
 319       find(key_const_reference);
 320
 321       inline point_const_iterator
 322       find(key_const_reference) const;
 323
 324       inline point_iterator
 325       lower_bound(key_const_reference);
 326
 327       inline point_const_iterator
 328       lower_bound(key_const_reference) const;
 329
 330       inline point_iterator
 331       upper_bound(key_const_reference);
 332
 333       inline point_const_iterator
 334       upper_bound(key_const_reference) const;
 335
 336       void
 337       clear();
 338
 339       inline bool
 340       erase(key_const_reference);
 341
 342       inline const_iterator
 343       erase(const_iterator);
 344
 345 #ifdef PB_DS_DATA_TRUE_INDICATOR
 346       inline iterator
 347       erase(iterator);
 348 #endif
 349
 350       inline const_reverse_iterator
 351       erase(const_reverse_iterator);
 352
 353 #ifdef PB_DS_DATA_TRUE_INDICATOR
 354       inline reverse_iterator
 355       erase(reverse_iterator);
 356 #endif
 357
 358       template<typename Pred>
 359       inline size_type
 360       erase_if(Pred);
 361
 362       void
 363       join(PB_DS_CLASS_C_DEC&);
 364
 365       void
 366       split(key_const_reference, PB_DS_CLASS_C_DEC&);
 367
 368       inline iterator
 369       begin();
 370
 371       inline const_iterator
 372       begin() const;
 373
 374       inline iterator
 375       end();
 376
 377       inline const_iterator
 378       end() const;
 379
 380       inline reverse_iterator
 381       rbegin();
 382
 383       inline const_reverse_iterator
 384       rbegin() const;
 385
 386       inline reverse_iterator
 387       rend();
 388
 389       inline const_reverse_iterator
 390       rend() const;
 391
 392       /// Returns a const node_iterator corresponding to the node at the
 393       /// root of the tree.
 394       inline node_const_iterator
 395       node_begin() const;
 396
 397       /// Returns a node_iterator corresponding to the node at the
 398       /// root of the tree.
 399       inline node_iterator
 400       node_begin();
 401
 402       /// Returns a const node_iterator corresponding to a node just
 403       /// after a leaf of the tree.
 404       inline node_const_iterator
 405       node_end() const;
 406
 407       /// Returns a node_iterator corresponding to a node just
 408       /// after a leaf of the tree.
 409       inline node_iterator
 410       node_end();
 411
 412 #ifdef PB_DS_PAT_TRIE_TRACE_
 413       void
 414       trace() const;
 415 #endif
 416
 417     protected:
 418       template<typename It>
 419       void
 420       copy_from_range(It, It);
 421
 422       void
 423       value_swap(PB_DS_CLASS_C_DEC&);
 424
 425       node_pointer
 426       recursive_copy_node(node_const_pointer);
 427
 428     private:
 429       void
 430       initialize();
 431
 432       inline void
 433       apply_update(node_pointer, null_node_update_pointer);
 434
 435       template<typename Node_Update_>
 436       inline void
 437       apply_update(node_pointer, Node_Update_*);
 438
 439       bool
 440       join_prep(PB_DS_CLASS_C_DEC&, branch_bag&);
 441
 442       void
 443       rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&);
 444
 445       void
 446       rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&);
 447
 448       void
 449       rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&);
 450
 451       void
 452       rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&);
 453
 454       void
 455       rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&);
 456
 457       node_pointer
 458       rec_join(node_pointer, node_pointer, size_type, branch_bag&);
 459
 460       node_pointer
 461       rec_join(leaf_pointer, leaf_pointer, branch_bag&);
 462
 463       node_pointer
 464       rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&);
 465
 466       node_pointer
 467       rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&);
 468
 469       node_pointer
 470       rec_join(inode_pointer, inode_pointer, branch_bag&);
 471
 472       size_type
 473       keys_diff_ind(typename access_traits::const_iterator,
 474                     typename access_traits::const_iterator,
 475                     typename access_traits::const_iterator,
 476                     typename access_traits::const_iterator);
 477
 478       inode_pointer
 479       insert_branch(node_pointer, node_pointer, branch_bag&);
 480
 481       void
 482       update_min_max_for_inserted_leaf(leaf_pointer);
 483
 484       void
 485       erase_leaf(leaf_pointer);
 486
 487       inline void
 488       actual_erase_leaf(leaf_pointer);
 489
 490       void
 491       clear_imp(node_pointer);
 492
 493       void
 494       erase_fixup(inode_pointer);
 495
 496       void
 497       update_min_max_for_erased_leaf(leaf_pointer);
 498
 499       static inline a_const_iterator
 500       pref_begin(node_const_pointer);
 501
 502       static inline a_const_iterator
 503       pref_end(node_const_pointer);
 504
 505       inline node_pointer
 506       find_imp(key_const_reference);
 507
 508       inline node_pointer
 509       lower_bound_imp(key_const_reference);
 510
 511       inline node_pointer
 512       upper_bound_imp(key_const_reference);
 513
 514       inline static leaf_const_pointer
 515       leftmost_descendant(node_const_pointer);
 516
 517       inline static leaf_pointer
 518       leftmost_descendant(node_pointer);
 519
 520       inline static leaf_const_pointer
 521       rightmost_descendant(node_const_pointer);
 522
 523       inline static leaf_pointer
 524       rightmost_descendant(node_pointer);
 525
 526 #ifdef _GLIBCXX_DEBUG
 527       void
 528       assert_valid(const char*, int) const;
 529
 530       void
 531       assert_iterators(const char*, int) const;
 532
 533       void
 534       assert_reverse_iterators(const char*, int) const;
 535
 536       static size_type
 537       recursive_count_leafs(node_const_pointer, const char*, int);
 538 #endif
 539
 540 #ifdef PB_DS_PAT_TRIE_TRACE_
 541       static void
 542       trace_node(node_const_pointer, size_type);
 543
 544       template<typename Metadata_>
 545       static void
 546       trace_node_metadata(node_const_pointer, type_to_type<Metadata_>);
 547
 548       static void
 549       trace_node_metadata(node_const_pointer, type_to_type<null_type>);
 550 #endif
 551
 552       leaf_pointer
 553       split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&);
 554
 555       node_pointer
 556       rec_split(node_pointer, a_const_iterator, a_const_iterator,
 557                 PB_DS_CLASS_C_DEC&, branch_bag&);
 558
 559       void
 560       split_insert_branch(size_type, a_const_iterator, inode_iterator,
 561                           size_type, branch_bag&);
 562
 563       static head_allocator             s_head_allocator;
 564       static inode_allocator            s_inode_allocator;
 565       static leaf_allocator             s_leaf_allocator;
 566
 567       head_pointer                      m_p_head;
 568       size_type                         m_size;
 569     };
 570
 571 #define PB_DS_ASSERT_NODE_VALID(X) \
 572   _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);)
 573
 574 #define PB_DS_RECURSIVE_COUNT_LEAFS(X) \
 575   recursive_count_leafs(X, __FILE__, __LINE__)
 576
 577 #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp>
 578 #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp>
 579 #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp>
 580 #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp>
 581 #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp>
 582 #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp>
 583 #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp>
 584 #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp>
 585 #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp>
 586 #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp>
 587 #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp>
 588
 589 #undef PB_DS_RECURSIVE_COUNT_LEAFS
 590 #undef PB_DS_ASSERT_NODE_VALID
 591 #undef PB_DS_CLASS_C_DEC
 592 #undef PB_DS_CLASS_T_DEC
 593 #undef PB_DS_PAT_TRIE_NAME
 594 #undef PB_DS_PAT_TRIE_TRAITS_BASE
 595 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 596   } // namespace detail
 597 } // namespace __gnu_pbds