libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_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 rb_tree_.hpp
  44  * Contains an implementation for rb_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 #ifdef PB_DS_DATA_TRUE_INDICATOR
  52 #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  53 #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  54 #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
  55 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  56 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
  57
  58 #ifdef PB_DS_DATA_FALSE_INDICATOR
  59 #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  60 #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  61 #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
  62 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  63 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
  64
  65 #include <ext/pb_ds/detail/standard_policies.hpp>
  66 #include <ext/pb_ds/detail/basic_types.hpp>
  67 #include <utility>
  68 #include <vector>
  69 #include <assert.h>
  70
  71 namespace pb_ds
  72 {
  73   namespace detail
  74   {
  75
  76 #ifdef PB_DS_RB_TREE_DEBUG_
  77 #define PB_DS_DBG_ASSERT(X) assert(X)
  78 #define PB_DS_DBG_VERIFY(X) assert(X)
  79 #define PB_DS_DBG_ONLY(X) X
  80 #else // #ifdef PB_DS_RB_TREE_DEBUG_
  81 #define PB_DS_DBG_ASSERT(X)
  82 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
  83 #define PB_DS_DBG_ONLY(X) ;
  84 #endif // #ifdef PB_DS_RB_TREE_DEBUG_
  85
  86 #define PB_DS_CLASS_T_DEC                                               \
  87     template<                                                           \
  88                                                 typename Key,           \
  89                                                 typename Mapped,        \
  90                                                 class Cmp_Fn,           \
  91                                                 class Node_And_It_Traits, \
  92                                                 class Allocator>
  93
  94 #ifdef PB_DS_DATA_TRUE_INDICATOR
  95 #define PB_DS_CLASS_NAME                        \
  96     rb_tree_data_
  97 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
  98
  99 #ifdef PB_DS_DATA_FALSE_INDICATOR
 100 #define PB_DS_CLASS_NAME                        \
 101     rb_tree_no_data_
 102 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 103
 104 #ifdef PB_DS_DATA_TRUE_INDICATOR
 105 #define PB_DS_BASE_CLASS_NAME                   \
 106     bin_search_tree_data_
 107 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 108
 109 #ifdef PB_DS_DATA_FALSE_INDICATOR
 110 #define PB_DS_BASE_CLASS_NAME                   \
 111     bin_search_tree_no_data_
 112 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 113
 114 #define PB_DS_CLASS_C_DEC                                               \
 115     PB_DS_CLASS_NAME<                                                   \
 116                                                 Key,                    \
 117                                                 Mapped,                 \
 118                                                 Cmp_Fn,                 \
 119                                                 Node_And_It_Traits,     \
 120                                                 Allocator>
 121
 122 #define PB_DS_BASE_C_DEC                                                \
 123     PB_DS_BASE_CLASS_NAME<                                              \
 124                                                         Key,            \
 125                                                         Mapped,         \
 126                                                         Cmp_Fn,         \
 127                                                         Node_And_It_Traits, \
 128                                                         Allocator>
 129
 130 #ifdef PB_DS_DATA_TRUE_INDICATOR
 131 #define PB_DS_V2F(X) (X).first
 132 #define PB_DS_V2S(X) (X).second
 133 #define PB_DS_EP2VP(X)& ((X)->m_value)
 134 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 135
 136 #ifdef PB_DS_DATA_FALSE_INDICATOR
 137 #define PB_DS_V2F(X) (X)
 138 #define PB_DS_V2S(X) Mapped_Data()
 139 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
 140 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 141
 142     template<typename Key,
 143              typename Mapped,
 144              class Cmp_Fn,
 145              class Node_And_It_Traits,
 146              class Allocator>
 147     class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC
 148     {
 149
 150     private:
 151       typedef typename PB_DS_BASE_C_DEC::node_pointer node_pointer;
 152
 153     public:
 154
 155       typedef typename Allocator::size_type size_type;
 156
 157       typedef typename Allocator::difference_type difference_type;
 158
 159       typedef typename PB_DS_BASE_C_DEC::key_type key_type;
 160
 161       typedef typename PB_DS_BASE_C_DEC::key_pointer key_pointer;
 162
 163       typedef typename PB_DS_BASE_C_DEC::const_key_pointer const_key_pointer;
 164
 165       typedef typename PB_DS_BASE_C_DEC::key_reference key_reference;
 166
 167       typedef
 168       typename PB_DS_BASE_C_DEC::const_key_reference
 169       const_key_reference;
 170
 171       typedef typename PB_DS_BASE_C_DEC::mapped_type mapped_type;
 172
 173       typedef typename PB_DS_BASE_C_DEC::mapped_pointer mapped_pointer;
 174
 175       typedef
 176       typename PB_DS_BASE_C_DEC::const_mapped_pointer
 177       const_mapped_pointer;
 178
 179       typedef typename PB_DS_BASE_C_DEC::mapped_reference mapped_reference;
 180
 181       typedef
 182       typename PB_DS_BASE_C_DEC::const_mapped_reference
 183       const_mapped_reference;
 184
 185       typedef typename PB_DS_BASE_C_DEC::value_type value_type;
 186
 187       typedef typename PB_DS_BASE_C_DEC::pointer pointer;
 188
 189       typedef typename PB_DS_BASE_C_DEC::const_pointer const_pointer;
 190
 191       typedef typename PB_DS_BASE_C_DEC::reference reference;
 192
 193       typedef typename PB_DS_BASE_C_DEC::const_reference const_reference;
 194
 195       typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
 196
 197       typedef typename PB_DS_BASE_C_DEC::const_iterator const_point_iterator;
 198
 199       typedef typename PB_DS_BASE_C_DEC::iterator iterator;
 200
 201       typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
 202
 203       typedef typename PB_DS_BASE_C_DEC::reverse_iterator reverse_iterator;
 204
 205       typedef
 206       typename PB_DS_BASE_C_DEC::const_reverse_iterator
 207       const_reverse_iterator;
 208
 209       typedef Cmp_Fn cmp_fn;
 210
 211       typedef Allocator allocator;
 212
 213       typedef typename PB_DS_BASE_C_DEC::node_update node_update;
 214
 215     public:
 216
 217       PB_DS_CLASS_NAME();
 218
 219       PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
 220
 221       PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update);
 222
 223       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
 224
 225       void
 226       swap(PB_DS_CLASS_C_DEC& other);
 227
 228       template<typename It>
 229       void
 230       copy_from_range(It first_it, It last_it);
 231
 232       inline std::pair<
 233         point_iterator,
 234         bool>
 235       insert(const_reference r_value);
 236
 237       inline mapped_reference
 238       operator[](const_key_reference r_key)
 239       {
 240 #ifdef PB_DS_DATA_TRUE_INDICATOR
 241         PB_DS_DBG_ONLY(assert_valid();)
 242
 243           std::pair<point_iterator, bool> ins_pair =
 244           PB_DS_BASE_C_DEC::insert_leaf(
 245                                         value_type(
 246                                                    r_key,
 247                                                    mapped_type()));
 248
 249         if (ins_pair.second == true)
 250           {
 251             ins_pair.first.m_p_nd->m_red = true;
 252
 253             PB_DS_DBG_ONLY(this->structure_only_assert_valid();)
 254
 255               insert_fixup(ins_pair.first.m_p_nd);
 256           }
 257
 258         PB_DS_DBG_ONLY(assert_valid();)
 259
 260           return (ins_pair.first.m_p_nd->m_value.second);
 261 #else // #ifdef PB_DS_DATA_TRUE_INDICATOR
 262         insert(r_key);
 263
 264         return (PB_DS_BASE_C_DEC::s_null_mapped);
 265 #endif // #ifdef PB_DS_DATA_TRUE
 266       }
 267
 268       inline bool
 269       erase(const_key_reference r_key);
 270
 271       inline iterator
 272       erase(iterator it);
 273
 274       inline reverse_iterator
 275       erase(reverse_iterator it);
 276
 277       template<typename Pred>
 278       inline size_type
 279       erase_if(Pred pred);
 280
 281       void
 282       join(PB_DS_CLASS_C_DEC& other);
 283
 284       void
 285       split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
 286
 287     protected:
 288
 289     private:
 290
 291 #ifdef PB_DS_RB_TREE_DEBUG_
 292
 293       void
 294       assert_valid() const;
 295
 296       size_type
 297       assert_node_consistent(const node_pointer p_nd) const;
 298
 299 #endif // #ifdef PB_DS_RB_TREE_DEBUG_
 300
 301       inline static bool
 302       is_effectively_black(const node_pointer p_nd);
 303
 304       void
 305       initialize();
 306
 307       void
 308       insert_fixup(node_pointer p_nd);
 309
 310       void
 311       erase_node(node_pointer p_nd);
 312
 313       void
 314       remove_node(node_pointer p_nd);
 315
 316       void
 317       remove_fixup(node_pointer p_x, node_pointer p_new_x_parent);
 318
 319       void
 320       split_imp(node_pointer p_nd, PB_DS_CLASS_C_DEC& other);
 321
 322       inline node_pointer
 323       split_min();
 324
 325       std::pair<node_pointer, node_pointer>
 326       split_min_imp();
 327
 328       void
 329       join_imp(node_pointer p_x, node_pointer p_r);
 330
 331       std::pair<node_pointer, node_pointer>
 332       find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r);
 333
 334       std::pair<node_pointer, node_pointer>
 335       find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r);
 336
 337       inline size_type
 338       black_height(node_pointer p_nd);
 339
 340       void
 341       split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other);
 342
 343     };
 344
 345 #include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
 346 #include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp>
 347 #include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp>
 348 #include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp>
 349 #include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp>
 350 #include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp>
 351
 352 #undef PB_DS_CLASS_T_DEC
 353
 354 #undef PB_DS_CLASS_C_DEC
 355
 356 #undef PB_DS_CLASS_NAME
 357
 358 #undef PB_DS_BASE_CLASS_NAME
 359
 360 #undef PB_DS_BASE_C_DEC
 361
 362 #undef PB_DS_DBG_ASSERT
 363 #undef PB_DS_DBG_VERIFY
 364 #undef PB_DS_DBG_ONLY
 365
 366 #undef PB_DS_V2F
 367 #undef PB_DS_EP2VP
 368 #undef PB_DS_V2S
 369
 370   } // namespace detail
 371 } // namespace pb_ds
 372