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