GNU C++ STL: rb_tree_.hpp Source File

00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00031 
00032 // Permission to use, copy, modify, sell, and distribute this software
00033 // is hereby granted without fee, provided that the above copyright
00034 // notice appears in all copies, and that both that copyright notice and
00035 // this permission notice appear in supporting documentation. None of
00036 // the above authors, nor IBM Haifa Research Laboratories, make any
00037 // representation about the suitability of this software for any
00038 // purpose. It is provided "as is" without express or implied warranty.
00039 
00045 /*
00046  * This implementation uses an idea from the SGI STL (using a "header" node
00047  *  which is needed for efficient iteration).
00048  */
00049 
00050 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00051 #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
00052 #define BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
00053 #include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
00054 #endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
00055 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00056 
00057 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00058 #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
00059 #define BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
00060 #include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
00061 #endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
00062 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00063 
00064 #include <ext/pb_assoc/tree_policy.hpp>
00065 #include <ext/pb_assoc/detail/standard_policies.hpp>
00066 #include <ext/pb_assoc/detail/rb_tree_map_/node.hpp>
00067 #include <utility>
00068 #include <vector>
00069 #include <assert.h>
00070 
00071 namespace pb_assoc
00072 {
00073 
00074   namespace detail
00075   {
00076 
00077 #ifdef PB_ASSOC_RB_TREE_DEBUG_
00078 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00079 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00080 #define PB_ASSOC_DBG_ONLY(X) X
00081 #else // #ifdef PB_ASSOC_RB_TREE_DEBUG_
00082 #define PB_ASSOC_DBG_ASSERT(X)
00083 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00084 #define PB_ASSOC_DBG_ONLY(X) ;
00085 #endif // #ifdef PB_ASSOC_RB_TREE_DEBUG_
00086 
00087 #define PB_ASSOC_CLASS_T_DEC \
00088     template< \
00089         typename Key, \
00090         typename Data, \
00091         class Cmp_Fn, \
00092         class Allocator, \
00093         class Node_Updator>
00094 
00095 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00096 #define PB_ASSOC_CLASS_NAME \
00097     rb_tree_data_
00098 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00099 
00100 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00101 #define PB_ASSOC_CLASS_NAME \
00102     rb_tree_no_data_
00103 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00104 
00105 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00106 #define PB_ASSOC_BASE_CLASS_NAME \
00107     bin_search_tree_data_
00108 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00109 
00110 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00111 #define PB_ASSOC_BASE_CLASS_NAME \
00112     bin_search_tree_no_data_
00113 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00114 
00115 #define PB_ASSOC_CLASS_C_DEC \
00116     PB_ASSOC_CLASS_NAME< \
00117         Key, \
00118         Data, \
00119         Cmp_Fn, \
00120         Allocator, \
00121         Node_Updator>
00122 
00123 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00124     types_traits< \
00125         Key, \
00126         Data, \
00127         Allocator>
00128 
00129 #define PB_ASSOC_NODE_C_DEC \
00130     rb_tree_node_< \
00131         typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type, \
00132         Allocator>
00133 
00134 #define PB_ASSOC_BASE_C_DEC \
00135     PB_ASSOC_BASE_CLASS_NAME< \
00136         Key, \
00137         Data, \
00138         PB_ASSOC_NODE_C_DEC, \
00139         Cmp_Fn, \
00140         Allocator, \
00141         Node_Updator>
00142 
00143 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00144 #define PB_ASSOC_V2F(X) (X).first
00145 #define PB_ASSOC_V2S(X) (X).second
00146 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
00147 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00148 
00149 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00150 #define PB_ASSOC_V2F(X) (X)
00151 #define PB_ASSOC_V2S(X) Mapped_Data()
00152 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
00153 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00154 
00155     template<typename Key,
00156          typename Data,
00157          class Cmp_Fn,
00158          class Allocator,
00159          class Node_Updator>
00160     struct PB_ASSOC_CLASS_NAME : public PB_ASSOC_BASE_C_DEC
00161     {
00162 
00163     public:
00164 
00165       typedef typename Allocator::size_type size_type;
00166 
00167       typedef
00168       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00169       const_key_reference;
00170 
00171       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00172 
00173       typedef
00174       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00175       data_reference;
00176 
00177       typedef
00178       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00179       const_data_reference;
00180 
00181       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00182 
00183       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00184 
00185       typedef
00186       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00187       const_pointer;
00188 
00189       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00190 
00191       typedef
00192       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00193       const_reference;
00194 
00195       typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
00196 
00197       typedef
00198       typename PB_ASSOC_BASE_C_DEC::const_iterator
00199       const_find_iterator;
00200 
00201       typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
00202 
00203       typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
00204 
00205       typedef
00206       typename PB_ASSOC_BASE_C_DEC::reverse_iterator
00207       reverse_iterator;
00208 
00209       typedef
00210       typename PB_ASSOC_BASE_C_DEC::const_reverse_iterator
00211       const_reverse_iterator;
00212 
00213     private:
00214 
00215       typedef typename PB_ASSOC_BASE_C_DEC::node_pointer node_pointer;
00216 
00217     protected:
00218 
00219       PB_ASSOC_CLASS_NAME();
00220 
00221       PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
00222 
00223       PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator);
00224 
00225       PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00226 
00227       void
00228       swap(PB_ASSOC_CLASS_C_DEC& r_other);
00229 
00230       template<class It>
00231       void
00232       copy_from_range(It first_it, It last_it);
00233 
00234       inline std::pair<find_iterator, bool>
00235       insert(const_reference r_value);
00236 
00237 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00238       inline data_reference
00239       subscript_imp(const_key_reference r_key);
00240 #endif // #ifdef PB_ASSOC_DATA_TRUE
00241 
00242       inline static bool
00243       is_effectively_black(const node_pointer p_nd);
00244 
00245       inline size_type
00246       erase(const_key_reference r_key);
00247 
00248       inline const_iterator
00249       erase(const_iterator it);
00250 
00251 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00252       inline iterator
00253       erase(iterator it);
00254 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00255 
00256       inline const_reverse_iterator
00257       erase(const_reverse_iterator it);
00258 
00259 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00260       inline reverse_iterator
00261       erase(reverse_iterator it);
00262 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00263 
00264       template<class Pred>
00265       inline size_type
00266       erase_if(Pred pred);
00267 
00268       void
00269       join(PB_ASSOC_CLASS_C_DEC& r_other);
00270 
00271       void
00272       split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
00273 
00274 #ifdef PB_ASSOC_RB_TREE_DEBUG_
00275 
00276       virtual void
00277       assert_valid() const;
00278 
00279       size_type
00280       assert_node_consistent(const node_pointer p_nd) const;
00281 
00282 #endif // #ifdef PB_ASSOC_RB_TREE_DEBUG_
00283 
00284     private:
00285 
00286       void
00287       initialize();
00288 
00289       void
00290       insert_fixup(node_pointer p_nd);
00291 
00292       void
00293       erase_node(node_pointer p_nd);
00294 
00295       void
00296       remove_node(node_pointer p_nd);
00297 
00298       void
00299       remove_fixup(node_pointer p_x, node_pointer p_new_x_parent);
00300 
00301       void
00302       split_imp(node_pointer p_nd, PB_ASSOC_CLASS_C_DEC& r_other);
00303 
00304       inline node_pointer
00305       split_min();
00306 
00307       std::pair<node_pointer, node_pointer>
00308       split_min_imp();
00309 
00310       void
00311       join_imp(node_pointer p_x, node_pointer p_r);
00312 
00313       std::pair<node_pointer, node_pointer>
00314       find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r);
00315 
00316       std::pair<node_pointer, node_pointer>
00317       find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r);
00318 
00319       inline size_type
00320       black_height(node_pointer p_nd);
00321 
00322       void
00323       split_at_node(node_pointer p_nd, PB_ASSOC_CLASS_C_DEC& r_other);
00324 
00325     };
00326 
00327 #include <ext/pb_assoc/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
00328 #include <ext/pb_assoc/detail/rb_tree_map_/insert_fn_imps.hpp>
00329 #include <ext/pb_assoc/detail/rb_tree_map_/erase_fn_imps.hpp>
00330 #include <ext/pb_assoc/detail/rb_tree_map_/find_fn_imps.hpp>
00331 #include <ext/pb_assoc/detail/rb_tree_map_/debug_fn_imps.hpp>
00332 #include <ext/pb_assoc/detail/rb_tree_map_/split_join_fn_imps.hpp>
00333 #include <ext/pb_assoc/detail/rb_tree_map_/info_fn_imps.hpp>
00334 
00335 #undef PB_ASSOC_CLASS_T_DEC
00336 
00337 #undef PB_ASSOC_CLASS_C_DEC
00338 
00339 #undef PB_ASSOC_CLASS_NAME
00340 
00341 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00342 
00343 #undef PB_ASSOC_BASE_CLASS_NAME
00344 
00345 #undef PB_ASSOC_NODE_C_DEC
00346 
00347 #undef PB_ASSOC_BASE_C_DEC
00348 
00349 #undef PB_ASSOC_DBG_ASSERT
00350 #undef PB_ASSOC_DBG_VERIFY
00351 #undef PB_ASSOC_DBG_ONLY
00352 
00353 #undef PB_ASSOC_V2F
00354 #undef PB_ASSOC_EP2VP
00355 #undef PB_ASSOC_V2S
00356 
00357   } // namespace detail
00358 
00359 } // namespace pb_assoc
00360