mingw/lib/gcc/mingw32/4.3.3/include/c++/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp

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