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