GNU C++ STL: splay_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 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00046 #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
00047 #define BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
00048 #include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
00049 #endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
00050 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00051 
00052 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00053 #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
00054 #define BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
00055 #include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
00056 #endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
00057 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00058 
00059 #include <ext/pb_assoc/detail/splay_tree_/node.hpp>
00060 #include <utility>
00061 #include <vector>
00062 #include <assert.h>
00063 
00064 namespace pb_assoc
00065 {
00066 
00067   namespace detail
00068   {
00069 
00070 #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00071 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
00072 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
00073 #define PB_ASSOC_DBG_ONLY(X) X
00074 #else // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00075 #define PB_ASSOC_DBG_ASSERT(X)
00076 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
00077 #define PB_ASSOC_DBG_ONLY(X) ;
00078 #endif // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00079 
00080 #define PB_ASSOC_CLASS_T_DEC \
00081     template< \
00082         typename Key, \
00083         typename Data, \
00084         class Cmp_Fn, \
00085         class Allocator, \
00086         class Node_Updator>
00087 
00088 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00089 #define PB_ASSOC_CLASS_NAME \
00090     splay_tree_data_
00091 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00092 
00093 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00094 #define PB_ASSOC_CLASS_NAME \
00095     splay_tree_no_data_
00096 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00097 
00098 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00099 #define PB_ASSOC_BASE_CLASS_NAME \
00100     bin_search_tree_data_
00101 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00102 
00103 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00104 #define PB_ASSOC_BASE_CLASS_NAME \
00105     bin_search_tree_no_data_
00106 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
00107 
00108 #define PB_ASSOC_CLASS_C_DEC \
00109     PB_ASSOC_CLASS_NAME< \
00110         Key, \
00111         Data, \
00112         Cmp_Fn, \
00113         Allocator, \
00114         Node_Updator>
00115 
00116 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
00117     types_traits< \
00118         Key, \
00119         Data, \
00120         Allocator>
00121 
00122 #define PB_ASSOC_NODE_C_DEC \
00123     splay_tree_node_< \
00124         typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type, \
00125         Allocator>
00126 
00127 #define PB_ASSOC_BASE_C_DEC \
00128     PB_ASSOC_BASE_CLASS_NAME< \
00129         Key, \
00130         Data, \
00131         PB_ASSOC_NODE_C_DEC, \
00132         Cmp_Fn, \
00133         Allocator, \
00134         Node_Updator>
00135 
00136     template<typename Key,
00137          typename Data,
00138          class Cmp_Fn,
00139          class Allocator,
00140          class Node_Updator>
00141     struct PB_ASSOC_CLASS_NAME : public PB_ASSOC_BASE_C_DEC
00142     {
00143 
00144     protected:
00145 
00146       typedef typename Allocator::size_type size_type;
00147 
00148       typedef
00149       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
00150       const_key_reference;
00151 
00152       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
00153 
00154       typedef
00155       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
00156       data_reference;
00157 
00158       typedef
00159       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
00160       const_data_reference;
00161 
00162       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
00163 
00164       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
00165 
00166       typedef
00167       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
00168       const_pointer;
00169 
00170       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
00171 
00172       typedef
00173       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
00174       const_reference;
00175 
00176       typedef typename PB_ASSOC_BASE_C_DEC::node_pointer node_pointer;
00177 
00178       typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
00179 
00180       typedef
00181       typename PB_ASSOC_BASE_C_DEC::const_iterator
00182       const_find_iterator;
00183 
00184       typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
00185 
00186       typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
00187 
00188       typedef
00189       typename PB_ASSOC_BASE_C_DEC::reverse_iterator
00190       reverse_iterator;
00191 
00192       typedef
00193       typename PB_ASSOC_BASE_C_DEC::const_reverse_iterator
00194       const_reverse_iterator;
00195 
00196     protected:
00197 
00198       PB_ASSOC_CLASS_NAME();
00199 
00200       PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
00201 
00202       PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator);
00203 
00204       PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
00205 
00206       void
00207       swap(PB_ASSOC_CLASS_C_DEC& r_other);
00208 
00209       template<class It>
00210       void
00211       copy_from_range(It first_it, It last_it);
00212 
00213       void
00214       initialize();
00215 
00216       inline std::pair<find_iterator, bool>
00217       insert(const_reference r_value);
00218 
00219 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00220       inline data_reference
00221       subscript_imp(const_key_reference r_key);
00222 #endif // #ifdef PB_ASSOC_DATA_TRUE
00223 
00224       inline find_iterator
00225       lower_bound(const_key_reference r_key);
00226 
00227       inline const_find_iterator
00228       lower_bound(const_key_reference r_key) const;
00229 
00230       inline find_iterator
00231       upper_bound(const_key_reference r_key);
00232 
00233       inline const_find_iterator
00234       upper_bound(const_key_reference r_key) const;
00235 
00236       inline find_iterator
00237       find(const_key_reference r_key);
00238 
00239       inline const_find_iterator
00240       find(const_key_reference r_key) const;
00241 
00242       inline size_type
00243       erase(const_key_reference r_key);
00244 
00245       inline const_iterator
00246       erase(const_iterator it);
00247 
00248 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00249       inline iterator
00250       erase(iterator it);
00251 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00252 
00253       inline const_reverse_iterator
00254       erase(const_reverse_iterator it);
00255 
00256 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00257       inline reverse_iterator
00258       erase(reverse_iterator it);
00259 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
00260 
00261       template<class Pred>
00262       inline size_type
00263       erase_if(Pred pred);
00264 
00265       inline node_pointer
00266       leftmost(node_pointer p_nd);
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_SPLAY_TREE_DEBUG_
00275 
00276       virtual void
00277       assert_valid() const;
00278 
00279       void
00280       assert_special_imp(const node_pointer p_nd) const;
00281 
00282 #endif // #ifdef PB_ASSOC_SPLAY_TREE_DEBUG_
00283 
00284     private:
00285 
00286       void
00287       splay(node_pointer p_nd);
00288 
00289       inline void
00290       splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
00291 
00292       inline void
00293       splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
00294 
00295       inline void
00296       splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
00297 
00298       inline void
00299       splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
00300 
00301       inline void
00302       splay_zz_start(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
00303 
00304       inline void
00305       splay_zz_end(node_pointer p_nd, node_pointer p_parent, node_pointer p_grandparent);
00306 
00307       void
00308       erase_node(node_pointer p_nd);
00309 
00310     };
00311 
00312 #include <ext/pb_assoc/detail/splay_tree_/constructors_destructor_fn_imps.hpp>
00313 #include <ext/pb_assoc/detail/splay_tree_/info_fn_imps.hpp>
00314 #include <ext/pb_assoc/detail/splay_tree_/insert_fn_imps.hpp>
00315 #include <ext/pb_assoc/detail/splay_tree_/splay_fn_imps.hpp>
00316 #include <ext/pb_assoc/detail/splay_tree_/erase_fn_imps.hpp>
00317 #include <ext/pb_assoc/detail/splay_tree_/find_fn_imps.hpp>
00318 #include <ext/pb_assoc/detail/splay_tree_/debug_fn_imps.hpp>
00319 #include <ext/pb_assoc/detail/splay_tree_/split_join_fn_imps.hpp>
00320 
00321 #undef PB_ASSOC_CLASS_T_DEC
00322 
00323 #undef PB_ASSOC_CLASS_C_DEC
00324 
00325 #undef PB_ASSOC_CLASS_NAME
00326 
00327 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
00328 
00329 #undef PB_ASSOC_BASE_CLASS_NAME
00330 
00331 #undef PB_ASSOC_NODE_C_DEC
00332 
00333 #undef PB_ASSOC_BASE_C_DEC
00334 
00335 #undef PB_ASSOC_DBG_ASSERT
00336 #undef PB_ASSOC_DBG_VERIFY
00337 #undef PB_ASSOC_DBG_ONLY
00338 
00339   } // namespace detail
00340 
00341 } // namespace pb_assoc
00342