1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009, 2010 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_.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 /* 41 * This implementation uses an idea from the SGI STL (using a @a header node 42 * which is needed for efficient iteration). 43 */ 44 45 #include <ext/pb_ds/exception.hpp> 46 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 47 #include <ext/pb_ds/detail/types_traits.hpp> 48 #include <ext/pb_ds/detail/debug_map_base.hpp> 49 #include <ext/pb_ds/tree_policy.hpp> 50 #include <ext/pb_ds/detail/cond_dealtor.hpp> 51 #include <ext/pb_ds/detail/type_utils.hpp> 52 #include <ext/pb_ds/detail/tree_trace_base.hpp> 53 #include <utility> 54 #include <functional> 55 #include <debug/debug.h> 56 57 namespace __gnu_pbds 58 { 59 namespace detail 60 { 61 62 #define PB_DS_CLASS_T_DEC \ 63 template<typename Key, typename Mapped, class Cmp_Fn, \ 64 class Node_And_It_Traits, class Allocator> 65 66 #ifdef PB_DS_DATA_TRUE_INDICATOR 67 #define PB_DS_CLASS_NAME \ 68 bin_search_tree_data_ 69 #endif 70 71 #ifdef PB_DS_DATA_FALSE_INDICATOR 72 #define PB_DS_CLASS_NAME \ 73 bin_search_tree_no_data_ 74 #endif 75 76 #define PB_DS_CLASS_C_DEC \ 77 PB_DS_CLASS_NAME< \ 78 Key, \ 79 Mapped, \ 80 Cmp_Fn, \ 81 Node_And_It_Traits, \ 82 Allocator> 83 84 #define PB_DS_TYPES_TRAITS_C_DEC \ 85 types_traits< \ 86 Key, \ 87 Mapped, \ 88 Allocator, \ 89 false> 90 91 #ifdef _GLIBCXX_DEBUG 92 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 93 debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 94 typename Allocator::template rebind<Key>::other::const_reference> 95 #endif 96 97 #ifdef PB_DS_DATA_TRUE_INDICATOR 98 #define PB_DS_V2F(X) (X).first 99 #define PB_DS_V2S(X) (X).second 100 #define PB_DS_EP2VP(X)& ((X)->m_value) 101 #endif 102 103 #ifdef PB_DS_DATA_FALSE_INDICATOR 104 #define PB_DS_V2F(X) (X) 105 #define PB_DS_V2S(X) Mapped_Data() 106 #define PB_DS_EP2VP(X)& ((X)->m_value.first) 107 #endif 108 109 #ifdef PB_DS_TREE_TRACE 110 #define PB_DS_TREE_TRACE_BASE_C_DEC \ 111 tree_trace_base< \ 112 typename Node_And_It_Traits::const_node_iterator, \ 113 typename Node_And_It_Traits::node_iterator, \ 114 Cmp_Fn, \ 115 true, \ 116 Allocator> 117 #endif 118 119 /** 120 * class description = "8i|\|4ree $34rc|-| 7r33 74813."> 121 **/ 122 template<typename Key, 123 typename Mapped, 124 class Cmp_Fn, 125 class Node_And_It_Traits, 126 class Allocator> 127 class PB_DS_CLASS_NAME : 128 #ifdef _GLIBCXX_DEBUG 129 public PB_DS_DEBUG_MAP_BASE_C_DEC, 130 #endif 131 #ifdef PB_DS_TREE_TRACE 132 public PB_DS_TREE_TRACE_BASE_C_DEC, 133 #endif 134 public Cmp_Fn, 135 public PB_DS_TYPES_TRAITS_C_DEC, 136 public Node_And_It_Traits::node_update 137 { 138 139 protected: 140 typedef 141 typename Allocator::template rebind< 142 typename Node_And_It_Traits::node>::other 143 node_allocator; 144 145 typedef typename node_allocator::value_type node; 146 147 typedef typename node_allocator::pointer node_pointer; 148 149 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 150 151 typedef 152 typename Node_And_It_Traits::null_node_update_pointer 153 null_node_update_pointer; 154 155 private: 156 typedef cond_dealtor< node, Allocator> cond_dealtor_t; 157 158 #ifdef _GLIBCXX_DEBUG 159 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 160 #endif 161 162 public: 163 164 typedef typename Allocator::size_type size_type; 165 166 typedef typename Allocator::difference_type difference_type; 167 168 typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; 169 170 typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; 171 172 typedef 173 typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer 174 const_key_pointer; 175 176 typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; 177 178 typedef 179 typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference 180 const_key_reference; 181 182 #ifdef PB_DS_DATA_TRUE_INDICATOR 183 typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; 184 185 typedef 186 typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer 187 mapped_pointer; 188 189 typedef 190 typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer 191 const_mapped_pointer; 192 193 typedef 194 typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference 195 mapped_reference; 196 197 typedef 198 typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference 199 const_mapped_reference; 200 #endif 201 202 typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; 203 204 typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; 205 206 typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; 207 208 typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; 209 210 typedef 211 typename PB_DS_TYPES_TRAITS_C_DEC::const_reference 212 const_reference; 213 214 typedef 215 typename Node_And_It_Traits::const_point_iterator 216 const_point_iterator; 217 218 typedef const_point_iterator const_iterator; 219 220 typedef typename Node_And_It_Traits::point_iterator point_iterator; 221 222 typedef point_iterator iterator; 223 224 typedef 225 typename Node_And_It_Traits::const_reverse_iterator 226 const_reverse_iterator; 227 228 typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; 229 230 typedef 231 typename Node_And_It_Traits::const_node_iterator 232 const_node_iterator; 233 234 typedef typename Node_And_It_Traits::node_iterator node_iterator; 235 236 typedef Cmp_Fn cmp_fn; 237 238 typedef Allocator allocator_type; 239 240 typedef typename Node_And_It_Traits::node_update node_update; 241 242 public: 243 244 PB_DS_CLASS_NAME(); 245 246 PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); 247 248 PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update); 249 250 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); 251 252 void 253 swap(PB_DS_CLASS_C_DEC& other); 254 255 ~PB_DS_CLASS_NAME(); 256 257 inline bool 258 empty() const; 259 260 inline size_type 261 size() const; 262 263 inline size_type 264 max_size() const; 265 266 Cmp_Fn& 267 get_cmp_fn(); 268 269 const Cmp_Fn& 270 get_cmp_fn() const; 271 272 inline point_iterator 273 lower_bound(const_key_reference r_key); 274 275 inline const_point_iterator 276 lower_bound(const_key_reference r_key) const; 277 278 inline point_iterator 279 upper_bound(const_key_reference r_key); 280 281 inline const_point_iterator 282 upper_bound(const_key_reference r_key) const; 283 284 inline point_iterator 285 find(const_key_reference r_key); 286 287 inline const_point_iterator 288 find(const_key_reference r_key) const; 289 290 inline iterator 291 begin(); 292 293 inline const_iterator 294 begin() const; 295 296 inline iterator 297 end(); 298 299 inline const_iterator 300 end() const; 301 302 inline reverse_iterator 303 rbegin(); 304 305 inline const_reverse_iterator 306 rbegin() const; 307 308 inline reverse_iterator 309 rend(); 310 311 inline const_reverse_iterator 312 rend() const; 313 314 inline const_node_iterator 315 node_begin() const; 316 317 inline node_iterator 318 node_begin(); 319 320 inline const_node_iterator 321 node_end() const; 322 323 inline node_iterator 324 node_end(); 325 326 void 327 clear(); 328 329 protected: 330 331 void 332 value_swap(PB_DS_CLASS_C_DEC& other); 333 334 void 335 initialize_min_max(); 336 337 inline iterator 338 insert_imp_empty(const_reference r_value); 339 340 inline iterator 341 insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd); 342 343 inline node_pointer 344 get_new_node_for_leaf_insert(const_reference r_val, false_type); 345 346 inline node_pointer 347 get_new_node_for_leaf_insert(const_reference r_val, true_type); 348 349 inline void 350 actual_erase_node(node_pointer p_nd); 351 352 inline std::pair<node_pointer, bool> 353 erase(node_pointer p_nd); 354 355 inline void 356 update_min_max_for_erased_node(node_pointer p_nd); 357 358 static void 359 clear_imp(node_pointer p_nd); 360 361 inline std::pair< 362 point_iterator, 363 bool> 364 insert_leaf(const_reference r_value); 365 366 inline void 367 rotate_left(node_pointer p_x); 368 369 inline void 370 rotate_right(node_pointer p_y); 371 372 inline void 373 rotate_parent(node_pointer p_nd); 374 375 inline void 376 apply_update(node_pointer p_nd, null_node_update_pointer); 377 378 template<typename Node_Update_> 379 inline void 380 apply_update(node_pointer p_nd, Node_Update_* p_update); 381 382 inline void 383 update_to_top(node_pointer p_nd, null_node_update_pointer); 384 385 template<typename Node_Update_> 386 inline void 387 update_to_top(node_pointer p_nd, Node_Update_* p_update); 388 389 bool 390 join_prep(PB_DS_CLASS_C_DEC& other); 391 392 void 393 join_finish(PB_DS_CLASS_C_DEC& other); 394 395 bool 396 split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); 397 398 void 399 split_finish(PB_DS_CLASS_C_DEC& other); 400 401 size_type 402 recursive_count(node_pointer p_nd) const; 403 404 #ifdef _GLIBCXX_DEBUG 405 void 406 assert_valid() const; 407 408 void 409 structure_only_assert_valid() const; 410 411 void 412 assert_node_consistent(const node_pointer p_nd) const; 413 #endif 414 415 private: 416 #ifdef _GLIBCXX_DEBUG 417 void 418 assert_iterators() const; 419 420 void 421 assert_consistent_with_debug_base() const; 422 423 void 424 assert_node_consistent_with_left(const node_pointer p_nd) const; 425 426 void 427 assert_node_consistent_with_right(const node_pointer p_nd) const; 428 429 void 430 assert_consistent_with_debug_base(const node_pointer p_nd) const; 431 432 void 433 assert_min() const; 434 435 void 436 assert_min_imp(const node_pointer p_nd) const; 437 438 void 439 assert_max() const; 440 441 void 442 assert_max_imp(const node_pointer p_nd) const; 443 444 void 445 assert_size() const; 446 447 typedef std::pair< const_pointer, const_pointer> node_consistent_t; 448 449 node_consistent_t 450 assert_node_consistent_(const node_pointer p_nd) const; 451 #endif 452 453 void 454 initialize(); 455 456 node_pointer 457 recursive_copy_node(const node_pointer p_nd); 458 459 protected: 460 node_pointer m_p_head; 461 462 size_type m_size; 463 464 static node_allocator s_node_allocator; 465 }; 466 467 #include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> 468 #include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> 469 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> 470 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> 471 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> 472 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> 473 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> 474 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> 475 #include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp> 476 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 477 478 #undef PB_DS_CLASS_C_DEC 479 480 #undef PB_DS_CLASS_T_DEC 481 482 #undef PB_DS_CLASS_NAME 483 484 #undef PB_DS_TYPES_TRAITS_C_DEC 485 486 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 487 488 #ifdef PB_DS_TREE_TRACE 489 #undef PB_DS_TREE_TRACE_BASE_C_DEC 490 #endif 491 492 #undef PB_DS_V2F 493 #undef PB_DS_EP2VP 494 #undef PB_DS_V2S 495 496 } // namespace detail 497 } // namespace __gnu_pbds 498
