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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2010, 2011 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 bin_search_tree_.hpp
  38  * Contains an implementation class for bin_search_tree_.
  39  */
  40 /*
  41  * This implementation uses an idea from the SGI STL (using a @a header node
  42  *    which is needed for efficient iteration).
  43  */
  44
  45 #include <ext/pb_ds/exception.hpp>
  46 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  47 #include <ext/pb_ds/detail/types_traits.hpp>
  48 #include <ext/pb_ds/detail/debug_map_base.hpp>
  49 #include <ext/pb_ds/tree_policy.hpp>
  50 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  51 #include <ext/pb_ds/detail/type_utils.hpp>
  52 #include <ext/pb_ds/detail/tree_trace_base.hpp>
  53 #include <utility>
  54 #include <functional>
  55 #include <debug/debug.h>
  56
  57 namespace __gnu_pbds
  58 {
  59   namespace detail
  60   {
  61
  62 #define PB_DS_CLASS_T_DEC                                               \
  63     template<typename Key, typename Mapped, class Cmp_Fn,               \
  64              class Node_And_It_Traits, class Allocator>
  65
  66 #ifdef PB_DS_DATA_TRUE_INDICATOR
  67 #define PB_DS_CLASS_NAME                        \
  68     bin_search_tree_data_
  69 #endif
  70
  71 #ifdef PB_DS_DATA_FALSE_INDICATOR
  72 #define PB_DS_CLASS_NAME                        \
  73     bin_search_tree_no_data_
  74 #endif
  75
  76 #define PB_DS_CLASS_C_DEC                                               \
  77     PB_DS_CLASS_NAME<                                                   \
  78                                                 Key,                    \
  79                                                 Mapped,                 \
  80                                                 Cmp_Fn,                 \
  81                                                 Node_And_It_Traits,     \
  82                                                 Allocator>
  83
  84 #define PB_DS_TYPES_TRAITS_C_DEC                                \
  85     types_traits<                               \
  86                                                 Key,            \
  87                                                 Mapped,         \
  88                                                 Allocator,      \
  89                                                 false>
  90
  91 #ifdef _GLIBCXX_DEBUG
  92 #define PB_DS_DEBUG_MAP_BASE_C_DEC                                      \
  93     debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
  94               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 #ifdef PB_DS_TREE_TRACE
 110 #define PB_DS_TREE_TRACE_BASE_C_DEC                                     \
 111     tree_trace_base<                                                    \
 112                                                                         typename Node_And_It_Traits::const_node_iterator, \
 113                                                                         typename Node_And_It_Traits::node_iterator, \
 114                                                                         Cmp_Fn, \
 115                                                                         true, \
 116                                                                         Allocator>
 117 #endif
 118
 119     /**
 120      * class description = "8i|\|4ree $34rc|-| 7r33 74813.">
 121      **/
 122     template<typename Key,
 123              typename Mapped,
 124              class Cmp_Fn,
 125              class Node_And_It_Traits,
 126              class Allocator>
 127     class PB_DS_CLASS_NAME :
 128 #ifdef _GLIBCXX_DEBUG
 129       public PB_DS_DEBUG_MAP_BASE_C_DEC,
 130 #endif
 131 #ifdef PB_DS_TREE_TRACE
 132       public PB_DS_TREE_TRACE_BASE_C_DEC,
 133 #endif
 134       public Cmp_Fn,
 135       public PB_DS_TYPES_TRAITS_C_DEC,
 136       public Node_And_It_Traits::node_update
 137     {
 138
 139     protected:
 140       typedef
 141       typename Allocator::template rebind<
 142       typename Node_And_It_Traits::node>::other
 143       node_allocator;
 144
 145       typedef typename node_allocator::value_type node;
 146
 147       typedef typename node_allocator::pointer node_pointer;
 148
 149       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 150
 151       typedef
 152       typename Node_And_It_Traits::null_node_update_pointer
 153       null_node_update_pointer;
 154
 155     private:
 156       typedef cond_dealtor< node, Allocator> cond_dealtor_t;
 157
 158 #ifdef _GLIBCXX_DEBUG
 159       typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
 160 #endif
 161
 162     public:
 163
 164       typedef typename Allocator::size_type size_type;
 165
 166       typedef typename Allocator::difference_type difference_type;
 167
 168       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
 169
 170       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
 171
 172       typedef
 173       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
 174       const_key_pointer;
 175
 176       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
 177
 178       typedef
 179       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
 180       const_key_reference;
 181
 182 #ifdef PB_DS_DATA_TRUE_INDICATOR
 183       typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
 184
 185       typedef
 186       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
 187       mapped_pointer;
 188
 189       typedef
 190       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
 191       const_mapped_pointer;
 192
 193       typedef
 194       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
 195       mapped_reference;
 196
 197       typedef
 198       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
 199       const_mapped_reference;
 200 #endif
 201
 202       typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
 203
 204       typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
 205
 206       typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
 207
 208       typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
 209
 210       typedef
 211       typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
 212       const_reference;
 213
 214       typedef
 215       typename Node_And_It_Traits::const_point_iterator
 216       const_point_iterator;
 217
 218       typedef const_point_iterator const_iterator;
 219
 220       typedef typename Node_And_It_Traits::point_iterator point_iterator;
 221
 222       typedef point_iterator iterator;
 223
 224       typedef
 225       typename Node_And_It_Traits::const_reverse_iterator
 226       const_reverse_iterator;
 227
 228       typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
 229
 230       typedef
 231       typename Node_And_It_Traits::const_node_iterator
 232       const_node_iterator;
 233
 234       typedef typename Node_And_It_Traits::node_iterator node_iterator;
 235
 236       typedef Cmp_Fn cmp_fn;
 237
 238       typedef Allocator allocator_type;
 239
 240       typedef typename Node_And_It_Traits::node_update node_update;
 241
 242     public:
 243
 244       PB_DS_CLASS_NAME();
 245
 246       PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
 247
 248       PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update);
 249
 250       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
 251
 252       void
 253       swap(PB_DS_CLASS_C_DEC& other);
 254
 255       ~PB_DS_CLASS_NAME();
 256
 257       inline bool
 258       empty() const;
 259
 260       inline size_type
 261       size() const;
 262
 263       inline size_type
 264       max_size() const;
 265
 266       Cmp_Fn&
 267       get_cmp_fn();
 268
 269       const Cmp_Fn&
 270       get_cmp_fn() const;
 271
 272       inline point_iterator
 273       lower_bound(const_key_reference r_key);
 274
 275       inline const_point_iterator
 276       lower_bound(const_key_reference r_key) const;
 277
 278       inline point_iterator
 279       upper_bound(const_key_reference r_key);
 280
 281       inline const_point_iterator
 282       upper_bound(const_key_reference r_key) const;
 283
 284       inline point_iterator
 285       find(const_key_reference r_key);
 286
 287       inline const_point_iterator
 288       find(const_key_reference r_key) const;
 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       void
 327       clear();
 328
 329     protected:
 330
 331       void
 332       value_swap(PB_DS_CLASS_C_DEC& other);
 333
 334       void
 335       initialize_min_max();
 336
 337       inline iterator
 338       insert_imp_empty(const_reference r_value);
 339
 340       inline iterator
 341       insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd);
 342
 343       inline node_pointer
 344       get_new_node_for_leaf_insert(const_reference r_val, false_type);
 345
 346       inline node_pointer
 347       get_new_node_for_leaf_insert(const_reference r_val, true_type);
 348
 349       inline void
 350       actual_erase_node(node_pointer p_nd);
 351
 352       inline std::pair<node_pointer, bool>
 353       erase(node_pointer p_nd);
 354
 355       inline void
 356       update_min_max_for_erased_node(node_pointer p_nd);
 357
 358       static void
 359       clear_imp(node_pointer p_nd);
 360
 361       inline std::pair<
 362         point_iterator,
 363         bool>
 364       insert_leaf(const_reference r_value);
 365
 366       inline void
 367       rotate_left(node_pointer p_x);
 368
 369       inline void
 370       rotate_right(node_pointer p_y);
 371
 372       inline void
 373       rotate_parent(node_pointer p_nd);
 374
 375       inline void
 376       apply_update(node_pointer p_nd, null_node_update_pointer);
 377
 378       template<typename Node_Update_>
 379       inline void
 380       apply_update(node_pointer p_nd, Node_Update_* p_update);
 381
 382       inline void
 383       update_to_top(node_pointer p_nd, null_node_update_pointer);
 384
 385       template<typename Node_Update_>
 386       inline void
 387       update_to_top(node_pointer p_nd, Node_Update_* p_update);
 388
 389       bool
 390       join_prep(PB_DS_CLASS_C_DEC& other);
 391
 392       void
 393       join_finish(PB_DS_CLASS_C_DEC& other);
 394
 395       bool
 396       split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
 397
 398       void
 399       split_finish(PB_DS_CLASS_C_DEC& other);
 400
 401       size_type
 402       recursive_count(node_pointer p_nd) const;
 403
 404 #ifdef _GLIBCXX_DEBUG
 405       void
 406       assert_valid(const char* file, int line) const;
 407
 408       void
 409       structure_only_assert_valid(const char* file, int line) const;
 410
 411       void
 412       assert_node_consistent(const node_pointer p_nd,
 413                              const char* file, int line) const;
 414 #endif
 415
 416     private:
 417 #ifdef _GLIBCXX_DEBUG
 418       void
 419       assert_iterators(const char* file, int line) const;
 420
 421       void
 422       assert_consistent_with_debug_base(const char* file, int line) const;
 423
 424       void
 425       assert_node_consistent_with_left(const node_pointer p_nd,
 426                                        const char* file, int line) const;
 427
 428       void
 429       assert_node_consistent_with_right(const node_pointer p_nd,
 430                                         const char* file, int line) const;
 431
 432       void
 433       assert_consistent_with_debug_base(const node_pointer p_nd,
 434                                         const char* file, int line) const;
 435
 436       void
 437       assert_min(const char* file, int line) const;
 438
 439       void
 440       assert_min_imp(const node_pointer p_nd,
 441                      const char* file, int line) const;
 442
 443       void
 444       assert_max(const char* file, int line) const;
 445
 446       void
 447       assert_max_imp(const node_pointer p_nd,
 448                      const char* file, int line) const;
 449
 450       void
 451       assert_size(const char* file, int line) const;
 452
 453       typedef std::pair< const_pointer, const_pointer> node_consistent_t;
 454
 455       node_consistent_t
 456       assert_node_consistent_(const node_pointer p_nd,
 457                               const char* file, int line) const;
 458 #endif
 459
 460       void
 461       initialize();
 462
 463       node_pointer
 464       recursive_copy_node(const node_pointer p_nd);
 465
 466     protected:
 467       node_pointer m_p_head;
 468
 469       size_type m_size;
 470
 471       static node_allocator s_node_allocator;
 472     };
 473
 474 #define PB_DS_ASSERT_VALID(X)                                           \
 475   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
 476
 477 #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X)                               \
 478   _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);)
 479
 480 #define PB_DS_ASSERT_NODE_CONSISTENT(_Node)                             \
 481   _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);)
 482
 483 #define PB_DS_CHECK_KEY_EXISTS(_Key)                                    \
 484   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);)
 485
 486 #define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key)                            \
 487   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key,        \
 488                                                            __FILE__, __LINE__);)
 489
 490 #define PB_DS_DEBUG_VERIFY(_Cond)                                       \
 491   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
 492                            _M_message(#_Cond" assertion from %1;:%2;")  \
 493                            ._M_string(__FILE__)._M_integer(__LINE__)    \
 494                            ,__file,__line)
 495
 496 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp>
 497 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp>
 498 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
 499 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
 500 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
 501 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
 502 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
 503 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
 504 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp>
 505 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 506
 507 #undef PB_DS_DEBUG_VERIFY
 508 #undef PB_DS_CHECK_KEY_DOES_NOT_EXIST
 509 #undef PB_DS_CHECK_KEY_EXISTS
 510 #undef PB_DS_ASSERT_NODE_CONSISTENT
 511 #undef PB_DS_STRUCT_ONLY_ASSERT_VALID
 512 #undef PB_DS_ASSERT_VALID
 513 #undef PB_DS_CLASS_C_DEC
 514 #undef PB_DS_CLASS_T_DEC
 515 #undef PB_DS_CLASS_NAME
 516 #undef PB_DS_TYPES_TRAITS_C_DEC
 517 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
 518
 519 #ifdef PB_DS_TREE_TRACE
 520 #undef PB_DS_TREE_TRACE_BASE_C_DEC
 521 #endif
 522
 523 #undef PB_DS_V2F
 524 #undef PB_DS_EP2VP
 525 #undef PB_DS_V2S
 526
 527   } // namespace detail
 528 } // namespace __gnu_pbds