1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2013 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** 37 * @file bin_search_tree_/bin_search_tree_.hpp 38 * Contains an implementation class for binary search tree. 39 */ 40 41 #include <ext/pb_ds/exception.hpp> 42 #include <ext/pb_ds/tree_policy.hpp> 43 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 44 #include <ext/pb_ds/detail/types_traits.hpp> 45 #include <ext/pb_ds/detail/cond_dealtor.hpp> 46 #include <ext/pb_ds/detail/type_utils.hpp> 47 #include <ext/pb_ds/detail/tree_trace_base.hpp> 48 #ifdef _GLIBCXX_DEBUG 49 #include <ext/pb_ds/detail/debug_map_base.hpp> 50 #endif 51 #include <utility> 52 #include <functional> 53 #include <debug/debug.h> 54 55 namespace __gnu_pbds 56 { 57 namespace detail 58 { 59 #ifdef PB_DS_DATA_TRUE_INDICATOR 60 #define PB_DS_BIN_TREE_NAME bin_search_tree_map 61 #endif 62 63 #ifdef PB_DS_DATA_FALSE_INDICATOR 64 #define PB_DS_BIN_TREE_NAME bin_search_tree_set 65 #endif 66 67 #define PB_DS_CLASS_T_DEC \ 68 template<typename Key, typename Mapped, typename Cmp_Fn, \ 69 typename Node_And_It_Traits, typename _Alloc> 70 71 #define PB_DS_CLASS_C_DEC \ 72 PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 73 74 #define PB_DS_BIN_TREE_TRAITS_BASE \ 75 types_traits<Key, Mapped, _Alloc, false> 76 77 #ifdef _GLIBCXX_DEBUG 78 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 79 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 80 typename _Alloc::template rebind<Key>::other::const_reference> 81 #endif 82 83 #ifdef PB_DS_TREE_TRACE 84 #define PB_DS_TREE_TRACE_BASE_C_DEC \ 85 tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \ 86 typename Node_And_It_Traits::node_iterator, \ 87 Cmp_Fn, true, _Alloc> 88 #endif 89 90 91 /* 92 * @brief Binary search tree (BST). 93 * 94 * This implementation uses an idea from the SGI STL (using a @a 95 * header node which is needed for efficient iteration). 96 */ 97 template<typename Key, typename Mapped, typename Cmp_Fn, 98 typename Node_And_It_Traits, typename _Alloc> 99 class PB_DS_BIN_TREE_NAME : 100 #ifdef _GLIBCXX_DEBUG 101 public PB_DS_DEBUG_MAP_BASE_C_DEC, 102 #endif 103 #ifdef PB_DS_TREE_TRACE 104 public PB_DS_TREE_TRACE_BASE_C_DEC, 105 #endif 106 public Cmp_Fn, 107 public PB_DS_BIN_TREE_TRAITS_BASE, 108 public Node_And_It_Traits::node_update 109 { 110 typedef Node_And_It_Traits traits_type; 111 112 protected: 113 typedef PB_DS_BIN_TREE_TRAITS_BASE traits_base; 114 115 typedef 116 typename _Alloc::template rebind<typename traits_type::node>::other 117 node_allocator; 118 119 typedef typename node_allocator::value_type node; 120 typedef typename node_allocator::pointer node_pointer; 121 122 typedef typename traits_type::null_node_update_pointer 123 null_node_update_pointer; 124 125 private: 126 typedef cond_dealtor<node, _Alloc> cond_dealtor_t; 127 128 #ifdef _GLIBCXX_DEBUG 129 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 130 #endif 131 132 public: 133 typedef typename _Alloc::size_type size_type; 134 typedef typename _Alloc::difference_type difference_type; 135 typedef typename traits_base::key_type key_type; 136 typedef typename traits_base::key_pointer key_pointer; 137 typedef typename traits_base::key_const_pointer key_const_pointer; 138 typedef typename traits_base::key_reference key_reference; 139 typedef typename traits_base::key_const_reference key_const_reference; 140 141 #ifdef PB_DS_DATA_TRUE_INDICATOR 142 typedef typename traits_base::mapped_type mapped_type; 143 typedef typename traits_base::mapped_pointer mapped_pointer; 144 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 145 typedef typename traits_base::mapped_reference mapped_reference; 146 typedef typename traits_base::mapped_const_reference mapped_const_reference; 147 #endif 148 149 typedef typename traits_base::value_type value_type; 150 typedef typename traits_base::pointer pointer; 151 typedef typename traits_base::const_pointer const_pointer; 152 typedef typename traits_base::reference reference; 153 typedef typename traits_base::const_reference const_reference; 154 typedef typename traits_type::point_const_iterator point_const_iterator; 155 156 typedef point_const_iterator const_iterator; 157 typedef typename traits_type::point_iterator point_iterator; 158 typedef point_iterator iterator; 159 160 typedef typename traits_type::const_reverse_iterator const_reverse_iterator; 161 162 typedef typename traits_type::reverse_iterator reverse_iterator; 163 typedef typename traits_type::node_const_iterator node_const_iterator; 164 typedef typename traits_type::node_iterator node_iterator; 165 typedef typename traits_type::node_update node_update; 166 167 typedef Cmp_Fn cmp_fn; 168 typedef _Alloc allocator_type; 169 170 PB_DS_BIN_TREE_NAME(); 171 172 PB_DS_BIN_TREE_NAME(const Cmp_Fn&); 173 174 PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&); 175 176 PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&); 177 178 void 179 swap(PB_DS_CLASS_C_DEC&); 180 181 ~PB_DS_BIN_TREE_NAME(); 182 183 inline bool 184 empty() const; 185 186 inline size_type 187 size() const; 188 189 inline size_type 190 max_size() const; 191 192 Cmp_Fn& 193 get_cmp_fn(); 194 195 const Cmp_Fn& 196 get_cmp_fn() const; 197 198 inline point_iterator 199 lower_bound(key_const_reference); 200 201 inline point_const_iterator 202 lower_bound(key_const_reference) const; 203 204 inline point_iterator 205 upper_bound(key_const_reference); 206 207 inline point_const_iterator 208 upper_bound(key_const_reference) const; 209 210 inline point_iterator 211 find(key_const_reference); 212 213 inline point_const_iterator 214 find(key_const_reference) const; 215 216 inline iterator 217 begin(); 218 219 inline const_iterator 220 begin() const; 221 222 inline iterator 223 end(); 224 225 inline const_iterator 226 end() const; 227 228 inline reverse_iterator 229 rbegin(); 230 231 inline const_reverse_iterator 232 rbegin() const; 233 234 inline reverse_iterator 235 rend(); 236 237 inline const_reverse_iterator 238 rend() const; 239 240 /// Returns a const node_iterator corresponding to the node at the 241 /// root of the tree. 242 inline node_const_iterator 243 node_begin() const; 244 245 /// Returns a node_iterator corresponding to the node at the 246 /// root of the tree. 247 inline node_iterator 248 node_begin(); 249 250 /// Returns a const node_iterator corresponding to a node just 251 /// after a leaf of the tree. 252 inline node_const_iterator 253 node_end() const; 254 255 /// Returns a node_iterator corresponding to a node just 256 /// after a leaf of the tree. 257 inline node_iterator 258 node_end(); 259 260 void 261 clear(); 262 263 protected: 264 void 265 value_swap(PB_DS_CLASS_C_DEC&); 266 267 void 268 initialize_min_max(); 269 270 inline iterator 271 insert_imp_empty(const_reference); 272 273 inline iterator 274 insert_leaf_new(const_reference, node_pointer, bool); 275 276 inline node_pointer 277 get_new_node_for_leaf_insert(const_reference, false_type); 278 279 inline node_pointer 280 get_new_node_for_leaf_insert(const_reference, true_type); 281 282 inline void 283 actual_erase_node(node_pointer); 284 285 inline std::pair<node_pointer, bool> 286 erase(node_pointer); 287 288 inline void 289 update_min_max_for_erased_node(node_pointer); 290 291 static void 292 clear_imp(node_pointer); 293 294 inline std::pair<point_iterator, bool> 295 insert_leaf(const_reference); 296 297 inline void 298 rotate_left(node_pointer); 299 300 inline void 301 rotate_right(node_pointer); 302 303 inline void 304 rotate_parent(node_pointer); 305 306 inline void 307 apply_update(node_pointer, null_node_update_pointer); 308 309 template<typename Node_Update_> 310 inline void 311 apply_update(node_pointer, Node_Update_*); 312 313 inline void 314 update_to_top(node_pointer, null_node_update_pointer); 315 316 template<typename Node_Update_> 317 inline void 318 update_to_top(node_pointer, Node_Update_*); 319 320 bool 321 join_prep(PB_DS_CLASS_C_DEC&); 322 323 void 324 join_finish(PB_DS_CLASS_C_DEC&); 325 326 bool 327 split_prep(key_const_reference, PB_DS_CLASS_C_DEC&); 328 329 void 330 split_finish(PB_DS_CLASS_C_DEC&); 331 332 size_type 333 recursive_count(node_pointer) const; 334 335 #ifdef _GLIBCXX_DEBUG 336 void 337 assert_valid(const char*, int) const; 338 339 void 340 structure_only_assert_valid(const char*, int) const; 341 342 void 343 assert_node_consistent(const node_pointer, const char*, int) const; 344 #endif 345 346 private: 347 #ifdef _GLIBCXX_DEBUG 348 void 349 assert_iterators(const char*, int) const; 350 351 void 352 assert_consistent_with_debug_base(const char*, int) const; 353 354 void 355 assert_node_consistent_with_left(const node_pointer, 356 const char*, int) const; 357 358 void 359 assert_node_consistent_with_right(const node_pointer, 360 const char*, int) const; 361 362 void 363 assert_consistent_with_debug_base(const node_pointer, 364 const char*, int) const; 365 366 void 367 assert_min(const char*, int) const; 368 369 void 370 assert_min_imp(const node_pointer, const char*, int) const; 371 372 void 373 assert_max(const char*, int) const; 374 375 void 376 assert_max_imp(const node_pointer, const char*, int) const; 377 378 void 379 assert_size(const char*, int) const; 380 381 typedef std::pair<const_pointer, const_pointer> node_consistent_t; 382 383 node_consistent_t 384 assert_node_consistent_(const node_pointer, const char*, int) const; 385 #endif 386 387 void 388 initialize(); 389 390 node_pointer 391 recursive_copy_node(const node_pointer); 392 393 protected: 394 node_pointer m_p_head; 395 size_type m_size; 396 static node_allocator s_node_allocator; 397 }; 398 399 #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \ 400 _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);) 401 402 #define PB_DS_ASSERT_NODE_CONSISTENT(_Node) \ 403 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);) 404 405 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> 406 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> 407 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> 408 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> 409 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> 410 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> 411 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> 412 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> 413 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp> 414 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 415 416 #undef PB_DS_ASSERT_NODE_CONSISTENT 417 #undef PB_DS_STRUCT_ONLY_ASSERT_VALID 418 #undef PB_DS_CLASS_C_DEC 419 #undef PB_DS_CLASS_T_DEC 420 #undef PB_DS_BIN_TREE_NAME 421 #undef PB_DS_BIN_TREE_TRAITS_BASE 422 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 423 424 #ifdef PB_DS_TREE_TRACE 425 #undef PB_DS_TREE_TRACE_BASE_C_DEC 426 #endif 427 } // namespace detail 428 } // namespace __gnu_pbds 429
