1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2021 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 rebind_traits<_Alloc, Key>::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 typedef rebind_traits<_Alloc, typename traits_type::node> 112 node_alloc_traits; 113 114 protected: 115 typedef PB_DS_BIN_TREE_TRAITS_BASE traits_base; 116 117 typedef 118 typename node_alloc_traits::allocator_type node_allocator; 119 120 typedef typename node_alloc_traits::value_type node; 121 typedef typename node_alloc_traits::pointer node_pointer; 122 123 typedef typename traits_type::null_node_update_pointer 124 null_node_update_pointer; 125 126 private: 127 typedef cond_dealtor<node, _Alloc> cond_dealtor_t; 128 129 #ifdef _GLIBCXX_DEBUG 130 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 131 #endif 132 133 public: 134 typedef typename _Alloc::size_type size_type; 135 typedef typename _Alloc::difference_type difference_type; 136 typedef typename traits_base::key_type key_type; 137 typedef typename traits_base::key_pointer key_pointer; 138 typedef typename traits_base::key_const_pointer key_const_pointer; 139 typedef typename traits_base::key_reference key_reference; 140 typedef typename traits_base::key_const_reference key_const_reference; 141 142 #ifdef PB_DS_DATA_TRUE_INDICATOR 143 typedef typename traits_base::mapped_type mapped_type; 144 typedef typename traits_base::mapped_pointer mapped_pointer; 145 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 146 typedef typename traits_base::mapped_reference mapped_reference; 147 typedef typename traits_base::mapped_const_reference mapped_const_reference; 148 #endif 149 150 typedef typename traits_base::value_type value_type; 151 typedef typename traits_base::pointer pointer; 152 typedef typename traits_base::const_pointer const_pointer; 153 typedef typename traits_base::reference reference; 154 typedef typename traits_base::const_reference const_reference; 155 typedef typename traits_type::point_const_iterator point_const_iterator; 156 157 typedef point_const_iterator const_iterator; 158 typedef typename traits_type::point_iterator point_iterator; 159 typedef point_iterator iterator; 160 161 typedef typename traits_type::const_reverse_iterator const_reverse_iterator; 162 163 typedef typename traits_type::reverse_iterator reverse_iterator; 164 typedef typename traits_type::node_const_iterator node_const_iterator; 165 typedef typename traits_type::node_iterator node_iterator; 166 typedef typename traits_type::node_update node_update; 167 168 typedef Cmp_Fn cmp_fn; 169 typedef _Alloc allocator_type; 170 171 PB_DS_BIN_TREE_NAME(); 172 173 PB_DS_BIN_TREE_NAME(const Cmp_Fn&); 174 175 PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&); 176 177 PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&); 178 179 void 180 swap(PB_DS_CLASS_C_DEC&); 181 182 ~PB_DS_BIN_TREE_NAME(); 183 184 inline bool 185 empty() const; 186 187 inline size_type 188 size() const; 189 190 inline size_type 191 max_size() const; 192 193 Cmp_Fn& 194 get_cmp_fn(); 195 196 const Cmp_Fn& 197 get_cmp_fn() const; 198 199 inline point_iterator 200 lower_bound(key_const_reference); 201 202 inline point_const_iterator 203 lower_bound(key_const_reference) const; 204 205 inline point_iterator 206 upper_bound(key_const_reference); 207 208 inline point_const_iterator 209 upper_bound(key_const_reference) const; 210 211 inline point_iterator 212 find(key_const_reference); 213 214 inline point_const_iterator 215 find(key_const_reference) const; 216 217 inline iterator 218 begin(); 219 220 inline const_iterator 221 begin() const; 222 223 inline iterator 224 end(); 225 226 inline const_iterator 227 end() const; 228 229 inline reverse_iterator 230 rbegin(); 231 232 inline const_reverse_iterator 233 rbegin() const; 234 235 inline reverse_iterator 236 rend(); 237 238 inline const_reverse_iterator 239 rend() const; 240 241 /// Returns a const node_iterator corresponding to the node at the 242 /// root of the tree. 243 inline node_const_iterator 244 node_begin() const; 245 246 /// Returns a node_iterator corresponding to the node at the 247 /// root of the tree. 248 inline node_iterator 249 node_begin(); 250 251 /// Returns a const node_iterator corresponding to a node just 252 /// after a leaf of the tree. 253 inline node_const_iterator 254 node_end() const; 255 256 /// Returns a node_iterator corresponding to a node just 257 /// after a leaf of the tree. 258 inline node_iterator 259 node_end(); 260 261 void 262 clear(); 263 264 protected: 265 void 266 value_swap(PB_DS_CLASS_C_DEC&); 267 268 void 269 initialize_min_max(); 270 271 inline iterator 272 insert_imp_empty(const_reference); 273 274 inline iterator 275 insert_leaf_new(const_reference, node_pointer, bool); 276 277 inline node_pointer 278 get_new_node_for_leaf_insert(const_reference, false_type); 279 280 inline node_pointer 281 get_new_node_for_leaf_insert(const_reference, true_type); 282 283 inline void 284 actual_erase_node(node_pointer); 285 286 inline std::pair<node_pointer, bool> 287 erase(node_pointer); 288 289 inline void 290 update_min_max_for_erased_node(node_pointer); 291 292 static void 293 clear_imp(node_pointer); 294 295 inline std::pair<point_iterator, bool> 296 insert_leaf(const_reference); 297 298 inline void 299 rotate_left(node_pointer); 300 301 inline void 302 rotate_right(node_pointer); 303 304 inline void 305 rotate_parent(node_pointer); 306 307 inline void 308 apply_update(node_pointer, null_node_update_pointer); 309 310 template<typename Node_Update_> 311 inline void 312 apply_update(node_pointer, Node_Update_*); 313 314 inline void 315 update_to_top(node_pointer, null_node_update_pointer); 316 317 template<typename Node_Update_> 318 inline void 319 update_to_top(node_pointer, Node_Update_*); 320 321 bool 322 join_prep(PB_DS_CLASS_C_DEC&); 323 324 void 325 join_finish(PB_DS_CLASS_C_DEC&); 326 327 bool 328 split_prep(key_const_reference, PB_DS_CLASS_C_DEC&); 329 330 void 331 split_finish(PB_DS_CLASS_C_DEC&); 332 333 size_type 334 recursive_count(node_pointer) const; 335 336 #ifdef _GLIBCXX_DEBUG 337 void 338 assert_valid(const char*, int) const; 339 340 void 341 structure_only_assert_valid(const char*, int) const; 342 343 void 344 assert_node_consistent(const node_pointer, const char*, int) const; 345 #endif 346 347 private: 348 #ifdef _GLIBCXX_DEBUG 349 void 350 assert_iterators(const char*, int) const; 351 352 void 353 assert_consistent_with_debug_base(const char*, int) const; 354 355 void 356 assert_node_consistent_with_left(const node_pointer, 357 const char*, int) const; 358 359 void 360 assert_node_consistent_with_right(const node_pointer, 361 const char*, int) const; 362 363 void 364 assert_consistent_with_debug_base(const node_pointer, 365 const char*, int) const; 366 367 void 368 assert_min(const char*, int) const; 369 370 void 371 assert_min_imp(const node_pointer, const char*, int) const; 372 373 void 374 assert_max(const char*, int) const; 375 376 void 377 assert_max_imp(const node_pointer, const char*, int) const; 378 379 void 380 assert_size(const char*, int) const; 381 382 typedef std::pair<const_pointer, const_pointer> node_consistent_t; 383 384 node_consistent_t 385 assert_node_consistent_(const node_pointer, const char*, int) const; 386 #endif 387 388 void 389 initialize(); 390 391 node_pointer 392 recursive_copy_node(const node_pointer); 393 394 protected: 395 node_pointer m_p_head; 396 size_type m_size; 397 static node_allocator s_node_allocator; 398 }; 399 400 #define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \ 401 _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);) 402 403 #define PB_DS_ASSERT_NODE_CONSISTENT(_Node) \ 404 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);) 405 406 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> 407 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> 408 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> 409 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> 410 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> 411 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> 412 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> 413 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> 414 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp> 415 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 416 417 #undef PB_DS_ASSERT_NODE_CONSISTENT 418 #undef PB_DS_STRUCT_ONLY_ASSERT_VALID 419 #undef PB_DS_CLASS_C_DEC 420 #undef PB_DS_CLASS_T_DEC 421 #undef PB_DS_BIN_TREE_NAME 422 #undef PB_DS_BIN_TREE_TRAITS_BASE 423 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 424 425 #ifdef PB_DS_TREE_TRACE 426 #undef PB_DS_TREE_TRACE_BASE_C_DEC 427 #endif 428 } // namespace detail 429 } // namespace __gnu_pbds 430