libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 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 terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file bin_search_tree_/bin_search_tree_.hpp 00038 * Contains an implementation class for binary search tree. 00039 */ 00040 00041 #include <ext/pb_ds/exception.hpp> 00042 #include <ext/pb_ds/tree_policy.hpp> 00043 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 00044 #include <ext/pb_ds/detail/types_traits.hpp> 00045 #include <ext/pb_ds/detail/cond_dealtor.hpp> 00046 #include <ext/pb_ds/detail/type_utils.hpp> 00047 #include <ext/pb_ds/detail/tree_trace_base.hpp> 00048 #ifdef _GLIBCXX_DEBUG 00049 #include <ext/pb_ds/detail/debug_map_base.hpp> 00050 #endif 00051 #include <utility> 00052 #include <functional> 00053 #include <debug/debug.h> 00054 00055 namespace __gnu_pbds 00056 { 00057 namespace detail 00058 { 00059 #ifdef PB_DS_DATA_TRUE_INDICATOR 00060 #define PB_DS_BIN_TREE_NAME bin_search_tree_map 00061 #endif 00062 00063 #ifdef PB_DS_DATA_FALSE_INDICATOR 00064 #define PB_DS_BIN_TREE_NAME bin_search_tree_set 00065 #endif 00066 00067 #define PB_DS_CLASS_T_DEC \ 00068 template<typename Key, typename Mapped, typename Cmp_Fn, \ 00069 typename Node_And_It_Traits, typename _Alloc> 00070 00071 #define PB_DS_CLASS_C_DEC \ 00072 PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 00073 00074 #define PB_DS_BIN_TREE_TRAITS_BASE \ 00075 types_traits<Key, Mapped, _Alloc, false> 00076 00077 #ifdef _GLIBCXX_DEBUG 00078 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 00079 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 00080 typename _Alloc::template rebind<Key>::other::const_reference> 00081 #endif 00082 00083 #ifdef PB_DS_TREE_TRACE 00084 #define PB_DS_TREE_TRACE_BASE_C_DEC \ 00085 tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \ 00086 typename Node_And_It_Traits::node_iterator, \ 00087 Cmp_Fn, true, _Alloc> 00088 #endif 00089 00090 00091 /* 00092 * @brief Binary search tree (BST). 00093 * 00094 * This implementation uses an idea from the SGI STL (using a @a 00095 * header node which is needed for efficient iteration). 00096 */ 00097 template<typename Key, typename Mapped, typename Cmp_Fn, 00098 typename Node_And_It_Traits, typename _Alloc> 00099 class PB_DS_BIN_TREE_NAME : 00100 #ifdef _GLIBCXX_DEBUG 00101 public PB_DS_DEBUG_MAP_BASE_C_DEC, 00102 #endif 00103 #ifdef PB_DS_TREE_TRACE 00104 public PB_DS_TREE_TRACE_BASE_C_DEC, 00105 #endif 00106 public Cmp_Fn, 00107 public PB_DS_BIN_TREE_TRAITS_BASE, 00108 public Node_And_It_Traits::node_update 00109 { 00110 typedef Node_And_It_Traits traits_type; 00111 00112 protected: 00113 typedef PB_DS_BIN_TREE_TRAITS_BASE traits_base; 00114 00115 typedef 00116 typename _Alloc::template rebind<typename traits_type::node>::other 00117 node_allocator; 00118 00119 typedef typename node_allocator::value_type node; 00120 typedef typename node_allocator::pointer node_pointer; 00121 00122 typedef typename traits_type::null_node_update_pointer 00123 null_node_update_pointer; 00124 00125 private: 00126 typedef cond_dealtor<node, _Alloc> cond_dealtor_t; 00127 00128 #ifdef _GLIBCXX_DEBUG 00129 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 00130 #endif 00131 00132 public: 00133 typedef typename _Alloc::size_type size_type; 00134 typedef typename _Alloc::difference_type difference_type; 00135 typedef typename traits_base::key_type key_type; 00136 typedef typename traits_base::key_pointer key_pointer; 00137 typedef typename traits_base::key_const_pointer key_const_pointer; 00138 typedef typename traits_base::key_reference key_reference; 00139 typedef typename traits_base::key_const_reference key_const_reference; 00140 00141 #ifdef PB_DS_DATA_TRUE_INDICATOR 00142 typedef typename traits_base::mapped_type mapped_type; 00143 typedef typename traits_base::mapped_pointer mapped_pointer; 00144 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 00145 typedef typename traits_base::mapped_reference mapped_reference; 00146 typedef typename traits_base::mapped_const_reference mapped_const_reference; 00147 #endif 00148 00149 typedef typename traits_base::value_type value_type; 00150 typedef typename traits_base::pointer pointer; 00151 typedef typename traits_base::const_pointer const_pointer; 00152 typedef typename traits_base::reference reference; 00153 typedef typename traits_base::const_reference const_reference; 00154 typedef typename traits_type::point_const_iterator point_const_iterator; 00155 00156 typedef point_const_iterator const_iterator; 00157 typedef typename traits_type::point_iterator point_iterator; 00158 typedef point_iterator iterator; 00159 00160 typedef typename traits_type::const_reverse_iterator const_reverse_iterator; 00161 00162 typedef typename traits_type::reverse_iterator reverse_iterator; 00163 typedef typename traits_type::node_const_iterator node_const_iterator; 00164 typedef typename traits_type::node_iterator node_iterator; 00165 typedef typename traits_type::node_update node_update; 00166 00167 typedef Cmp_Fn cmp_fn; 00168 typedef _Alloc allocator_type; 00169 00170 PB_DS_BIN_TREE_NAME(); 00171 00172 PB_DS_BIN_TREE_NAME(const Cmp_Fn&); 00173 00174 PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&); 00175 00176 PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&); 00177 00178 void 00179 swap(PB_DS_CLASS_C_DEC&); 00180 00181 ~PB_DS_BIN_TREE_NAME(); 00182 00183 inline bool 00184 empty() const; 00185 00186 inline size_type 00187 size() const; 00188 00189 inline size_type 00190 max_size() const; 00191 00192 Cmp_Fn& 00193 get_cmp_fn(); 00194 00195 const Cmp_Fn& 00196 get_cmp_fn() const; 00197 00198 inline point_iterator 00199 lower_bound(key_const_reference); 00200 00201 inline point_const_iterator 00202 lower_bound(key_const_reference) const; 00203 00204 inline point_iterator 00205 upper_bound(key_const_reference); 00206 00207 inline point_const_iterator 00208 upper_bound(key_const_reference) const; 00209 00210 inline point_iterator 00211 find(key_const_reference); 00212 00213 inline point_const_iterator 00214 find(key_const_reference) const; 00215 00216 inline iterator 00217 begin(); 00218 00219 inline const_iterator 00220 begin() const; 00221 00222 inline iterator 00223 end(); 00224 00225 inline const_iterator 00226 end() const; 00227 00228 inline reverse_iterator 00229 rbegin(); 00230 00231 inline const_reverse_iterator 00232 rbegin() const; 00233 00234 inline reverse_iterator 00235 rend(); 00236 00237 inline const_reverse_iterator 00238 rend() const; 00239 00240 /// Returns a const node_iterator corresponding to the node at the 00241 /// root of the tree. 00242 inline node_const_iterator 00243 node_begin() const; 00244 00245 /// Returns a node_iterator corresponding to the node at the 00246 /// root of the tree. 00247 inline node_iterator 00248 node_begin(); 00249 00250 /// Returns a const node_iterator corresponding to a node just 00251 /// after a leaf of the tree. 00252 inline node_const_iterator 00253 node_end() const; 00254 00255 /// Returns a node_iterator corresponding to a node just 00256 /// after a leaf of the tree. 00257 inline node_iterator 00258 node_end(); 00259 00260 void 00261 clear(); 00262 00263 protected: 00264 void 00265 value_swap(PB_DS_CLASS_C_DEC&); 00266 00267 void 00268 initialize_min_max(); 00269 00270 inline iterator 00271 insert_imp_empty(const_reference); 00272 00273 inline iterator 00274 insert_leaf_new(const_reference, node_pointer, bool); 00275 00276 inline node_pointer 00277 get_new_node_for_leaf_insert(const_reference, false_type); 00278 00279 inline node_pointer 00280 get_new_node_for_leaf_insert(const_reference, true_type); 00281 00282 inline void 00283 actual_erase_node(node_pointer); 00284 00285 inline std::pair<node_pointer, bool> 00286 erase(node_pointer); 00287 00288 inline void 00289 update_min_max_for_erased_node(node_pointer); 00290 00291 static void 00292 clear_imp(node_pointer); 00293 00294 inline std::pair<point_iterator, bool> 00295 insert_leaf(const_reference); 00296 00297 inline void 00298 rotate_left(node_pointer); 00299 00300 inline void 00301 rotate_right(node_pointer); 00302 00303 inline void 00304 rotate_parent(node_pointer); 00305 00306 inline void 00307 apply_update(node_pointer, null_node_update_pointer); 00308 00309 template<typename Node_Update_> 00310 inline void 00311 apply_update(node_pointer, Node_Update_*); 00312 00313 inline void 00314 update_to_top(node_pointer, null_node_update_pointer); 00315 00316 template<typename Node_Update_> 00317 inline void 00318 update_to_top(node_pointer, Node_Update_*); 00319 00320 bool 00321 join_prep(PB_DS_CLASS_C_DEC&); 00322 00323 void 00324 join_finish(PB_DS_CLASS_C_DEC&); 00325 00326 bool 00327 split_prep(key_const_reference, PB_DS_CLASS_C_DEC&); 00328 00329 void 00330 split_finish(PB_DS_CLASS_C_DEC&); 00331 00332 size_type 00333 recursive_count(node_pointer) const; 00334 00335 #ifdef _GLIBCXX_DEBUG 00336 void 00337 assert_valid(const char*, int) const; 00338 00339 void 00340 structure_only_assert_valid(const char*, int) const; 00341 00342 void 00343 assert_node_consistent(const node_pointer, const char*, int) const; 00344 #endif 00345 00346 private: 00347 #ifdef _GLIBCXX_DEBUG 00348 void 00349 assert_iterators(const char*, int) const; 00350 00351 void 00352 assert_consistent_with_debug_base(const char*, int) const; 00353 00354 void 00355 assert_node_consistent_with_left(const node_pointer, 00356 const char*, int) const; 00357 00358 void 00359 assert_node_consistent_with_right(const node_pointer, 00360 const char*, int) const; 00361 00362 void 00363 assert_consistent_with_debug_base(const node_pointer, 00364 const char*, int) const; 00365 00366 void 00367 assert_min(const char*, int) const; 00368 00369 void 00370 assert_min_imp(const node_pointer, const char*, int) const; 00371 00372 void 00373 assert_max(const char*, int) const; 00374 00375 void 00376 assert_max_imp(const node_pointer, const char*, int) const; 00377 00378 void 00379 assert_size(const char*, int) const; 00380 00381 typedef std::pair<const_pointer, const_pointer> node_consistent_t; 00382 00383 node_consistent_t 00384 assert_node_consistent_(const node_pointer, const char*, int) const; 00385 #endif 00386 00387 void 00388 initialize(); 00389 00390 node_pointer 00391 recursive_copy_node(const node_pointer); 00392 00393 protected: 00394 node_pointer m_p_head; 00395 size_type m_size; 00396 static node_allocator s_node_allocator; 00397 }; 00398 00399 #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \ 00400 _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);) 00401 00402 #define PB_DS_ASSERT_NODE_CONSISTENT(_Node) \ 00403 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);) 00404 00405 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> 00406 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> 00407 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> 00408 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> 00409 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> 00410 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> 00411 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> 00412 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> 00413 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp> 00414 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 00415 00416 #undef PB_DS_ASSERT_NODE_CONSISTENT 00417 #undef PB_DS_STRUCT_ONLY_ASSERT_VALID 00418 #undef PB_DS_CLASS_C_DEC 00419 #undef PB_DS_CLASS_T_DEC 00420 #undef PB_DS_BIN_TREE_NAME 00421 #undef PB_DS_BIN_TREE_TRAITS_BASE 00422 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 00423 00424 #ifdef PB_DS_TREE_TRACE 00425 #undef PB_DS_TREE_TRACE_BASE_C_DEC 00426 #endif 00427 } // namespace detail 00428 } // namespace __gnu_pbds