1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file bin_search_tree_.hpp 44169691Skan * Contains an implementation class for bin_search_tree_. 45169691Skan */ 46169691Skan/* 47169691Skan * This implementation uses an idea from the SGI STL (using a "header" node 48169691Skan * which is needed for efficient iteration). 49169691Skan */ 50169691Skan 51169691Skan#include <ext/pb_ds/exception.hpp> 52169691Skan#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 53169691Skan#include <ext/pb_ds/detail/types_traits.hpp> 54169691Skan#include <ext/pb_ds/detail/map_debug_base.hpp> 55169691Skan#include <ext/pb_ds/tree_policy.hpp> 56169691Skan#include <ext/pb_ds/detail/cond_dealtor.hpp> 57169691Skan#include <ext/pb_ds/detail/type_utils.hpp> 58169691Skan#include <ext/pb_ds/detail/tree_trace_base.hpp> 59169691Skan#include <utility> 60169691Skan#include <functional> 61169691Skan#include <debug/debug.h> 62169691Skan 63169691Skannamespace pb_ds 64169691Skan{ 65169691Skan namespace detail 66169691Skan { 67169691Skan 68169691Skan#define PB_DS_CLASS_T_DEC \ 69169691Skan template<typename Key, typename Mapped, class Cmp_Fn, \ 70169691Skan class Node_And_It_Traits, class Allocator> 71169691Skan 72169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 73169691Skan#define PB_DS_CLASS_NAME \ 74169691Skan bin_search_tree_data_ 75169691Skan#endif 76169691Skan 77169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 78169691Skan#define PB_DS_CLASS_NAME \ 79169691Skan bin_search_tree_no_data_ 80169691Skan#endif 81169691Skan 82169691Skan#define PB_DS_CLASS_C_DEC \ 83169691Skan PB_DS_CLASS_NAME< \ 84169691Skan Key, \ 85169691Skan Mapped, \ 86169691Skan Cmp_Fn, \ 87169691Skan Node_And_It_Traits, \ 88169691Skan Allocator> 89169691Skan 90169691Skan#define PB_DS_TYPES_TRAITS_C_DEC \ 91169691Skan types_traits< \ 92169691Skan Key, \ 93169691Skan Mapped, \ 94169691Skan Allocator, \ 95169691Skan false> 96169691Skan 97169691Skan#ifdef _GLIBCXX_DEBUG 98169691Skan#define PB_DS_MAP_DEBUG_BASE_C_DEC \ 99169691Skan map_debug_base<Key, eq_by_less<Key, Cmp_Fn>, \ 100169691Skan typename Allocator::template rebind<Key>::other::const_reference> 101169691Skan#endif 102169691Skan 103169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 104169691Skan#define PB_DS_V2F(X) (X).first 105169691Skan#define PB_DS_V2S(X) (X).second 106169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value) 107169691Skan#endif 108169691Skan 109169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 110169691Skan#define PB_DS_V2F(X) (X) 111169691Skan#define PB_DS_V2S(X) Mapped_Data() 112169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value.first) 113169691Skan#endif 114169691Skan 115169691Skan#ifdef PB_DS_TREE_TRACE 116169691Skan#define PB_DS_TREE_TRACE_BASE_C_DEC \ 117169691Skan tree_trace_base< \ 118169691Skan typename Node_And_It_Traits::const_node_iterator, \ 119169691Skan typename Node_And_It_Traits::node_iterator, \ 120169691Skan Cmp_Fn, \ 121169691Skan true, \ 122169691Skan Allocator> 123169691Skan#endif 124169691Skan 125169691Skan /** 126169691Skan * class description = "8i|\|4ree $34rc|-| 7r33 74813."> 127169691Skan **/ 128169691Skan template<typename Key, 129169691Skan typename Mapped, 130169691Skan class Cmp_Fn, 131169691Skan class Node_And_It_Traits, 132169691Skan class Allocator> 133169691Skan class PB_DS_CLASS_NAME : 134169691Skan#ifdef _GLIBCXX_DEBUG 135169691Skan public PB_DS_MAP_DEBUG_BASE_C_DEC, 136169691Skan#endif 137169691Skan#ifdef PB_DS_TREE_TRACE 138169691Skan public PB_DS_TREE_TRACE_BASE_C_DEC, 139169691Skan#endif 140169691Skan public Cmp_Fn, 141169691Skan public PB_DS_TYPES_TRAITS_C_DEC, 142169691Skan public Node_And_It_Traits::node_update 143169691Skan { 144169691Skan 145169691Skan protected: 146169691Skan typedef 147169691Skan typename Allocator::template rebind< 148169691Skan typename Node_And_It_Traits::node>::other 149169691Skan node_allocator; 150169691Skan 151169691Skan typedef typename node_allocator::value_type node; 152169691Skan 153169691Skan typedef typename node_allocator::pointer node_pointer; 154169691Skan 155169691Skan typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 156169691Skan 157169691Skan typedef 158169691Skan typename Node_And_It_Traits::null_node_update_pointer 159169691Skan null_node_update_pointer; 160169691Skan 161169691Skan private: 162169691Skan typedef cond_dealtor< node, Allocator> cond_dealtor_t; 163169691Skan 164169691Skan#ifdef _GLIBCXX_DEBUG 165169691Skan typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; 166169691Skan#endif 167169691Skan 168169691Skan public: 169169691Skan 170169691Skan typedef typename Allocator::size_type size_type; 171169691Skan 172169691Skan typedef typename Allocator::difference_type difference_type; 173169691Skan 174169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; 175169691Skan 176169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; 177169691Skan 178169691Skan typedef 179169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer 180169691Skan const_key_pointer; 181169691Skan 182169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; 183169691Skan 184169691Skan typedef 185169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference 186169691Skan const_key_reference; 187169691Skan 188169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 189169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; 190169691Skan 191169691Skan typedef 192169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer 193169691Skan mapped_pointer; 194169691Skan 195169691Skan typedef 196169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer 197169691Skan const_mapped_pointer; 198169691Skan 199169691Skan typedef 200169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference 201169691Skan mapped_reference; 202169691Skan 203169691Skan typedef 204169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference 205169691Skan const_mapped_reference; 206169691Skan#endif 207169691Skan 208169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; 209169691Skan 210169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; 211169691Skan 212169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; 213169691Skan 214169691Skan typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; 215169691Skan 216169691Skan typedef 217169691Skan typename PB_DS_TYPES_TRAITS_C_DEC::const_reference 218169691Skan const_reference; 219169691Skan 220169691Skan typedef 221169691Skan typename Node_And_It_Traits::const_point_iterator 222169691Skan const_point_iterator; 223169691Skan 224169691Skan typedef const_point_iterator const_iterator; 225169691Skan 226169691Skan typedef typename Node_And_It_Traits::point_iterator point_iterator; 227169691Skan 228169691Skan typedef point_iterator iterator; 229169691Skan 230169691Skan typedef 231169691Skan typename Node_And_It_Traits::const_reverse_iterator 232169691Skan const_reverse_iterator; 233169691Skan 234169691Skan typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; 235169691Skan 236169691Skan typedef 237169691Skan typename Node_And_It_Traits::const_node_iterator 238169691Skan const_node_iterator; 239169691Skan 240169691Skan typedef typename Node_And_It_Traits::node_iterator node_iterator; 241169691Skan 242169691Skan typedef Cmp_Fn cmp_fn; 243169691Skan 244169691Skan typedef Allocator allocator; 245169691Skan 246169691Skan typedef typename Node_And_It_Traits::node_update node_update; 247169691Skan 248169691Skan public: 249169691Skan 250169691Skan PB_DS_CLASS_NAME(); 251169691Skan 252169691Skan PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); 253169691Skan 254169691Skan PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update); 255169691Skan 256169691Skan PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); 257169691Skan 258169691Skan void 259169691Skan swap(PB_DS_CLASS_C_DEC& other); 260169691Skan 261169691Skan ~PB_DS_CLASS_NAME(); 262169691Skan 263169691Skan inline bool 264169691Skan empty() const; 265169691Skan 266169691Skan inline size_type 267169691Skan size() const; 268169691Skan 269169691Skan inline size_type 270169691Skan max_size() const; 271169691Skan 272169691Skan Cmp_Fn& 273169691Skan get_cmp_fn(); 274169691Skan 275169691Skan const Cmp_Fn& 276169691Skan get_cmp_fn() const; 277169691Skan 278169691Skan inline point_iterator 279169691Skan lower_bound(const_key_reference r_key); 280169691Skan 281169691Skan inline const_point_iterator 282169691Skan lower_bound(const_key_reference r_key) const; 283169691Skan 284169691Skan inline point_iterator 285169691Skan upper_bound(const_key_reference r_key); 286169691Skan 287169691Skan inline const_point_iterator 288169691Skan upper_bound(const_key_reference r_key) const; 289169691Skan 290169691Skan inline point_iterator 291169691Skan find(const_key_reference r_key); 292169691Skan 293169691Skan inline const_point_iterator 294169691Skan find(const_key_reference r_key) const; 295169691Skan 296169691Skan inline iterator 297169691Skan begin(); 298169691Skan 299169691Skan inline const_iterator 300169691Skan begin() const; 301169691Skan 302169691Skan inline iterator 303169691Skan end(); 304169691Skan 305169691Skan inline const_iterator 306169691Skan end() const; 307169691Skan 308169691Skan inline reverse_iterator 309169691Skan rbegin(); 310169691Skan 311169691Skan inline const_reverse_iterator 312169691Skan rbegin() const; 313169691Skan 314169691Skan inline reverse_iterator 315169691Skan rend(); 316169691Skan 317169691Skan inline const_reverse_iterator 318169691Skan rend() const; 319169691Skan 320169691Skan inline const_node_iterator 321169691Skan node_begin() const; 322169691Skan 323169691Skan inline node_iterator 324169691Skan node_begin(); 325169691Skan 326169691Skan inline const_node_iterator 327169691Skan node_end() const; 328169691Skan 329169691Skan inline node_iterator 330169691Skan node_end(); 331169691Skan 332169691Skan void 333169691Skan clear(); 334169691Skan 335169691Skan protected: 336169691Skan 337169691Skan void 338169691Skan value_swap(PB_DS_CLASS_C_DEC& other); 339169691Skan 340169691Skan void 341169691Skan initialize_min_max(); 342169691Skan 343169691Skan inline iterator 344169691Skan insert_imp_empty(const_reference r_value); 345169691Skan 346169691Skan inline iterator 347169691Skan insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd); 348169691Skan 349169691Skan inline node_pointer 350169691Skan get_new_node_for_leaf_insert(const_reference r_val, false_type); 351169691Skan 352169691Skan inline node_pointer 353169691Skan get_new_node_for_leaf_insert(const_reference r_val, true_type); 354169691Skan 355169691Skan inline void 356169691Skan actual_erase_node(node_pointer p_nd); 357169691Skan 358169691Skan inline std::pair<node_pointer, bool> 359169691Skan erase(node_pointer p_nd); 360169691Skan 361169691Skan inline void 362169691Skan update_min_max_for_erased_node(node_pointer p_nd); 363169691Skan 364169691Skan static void 365169691Skan clear_imp(node_pointer p_nd); 366169691Skan 367169691Skan inline std::pair< 368169691Skan point_iterator, 369169691Skan bool> 370169691Skan insert_leaf(const_reference r_value); 371169691Skan 372169691Skan inline void 373169691Skan rotate_left(node_pointer p_x); 374169691Skan 375169691Skan inline void 376169691Skan rotate_right(node_pointer p_y); 377169691Skan 378169691Skan inline void 379169691Skan rotate_parent(node_pointer p_nd); 380169691Skan 381169691Skan inline void 382169691Skan apply_update(node_pointer p_nd, null_node_update_pointer); 383169691Skan 384169691Skan template<typename Node_Update_> 385169691Skan inline void 386169691Skan apply_update(node_pointer p_nd, Node_Update_* p_update); 387169691Skan 388169691Skan inline void 389169691Skan update_to_top(node_pointer p_nd, null_node_update_pointer); 390169691Skan 391169691Skan template<typename Node_Update_> 392169691Skan inline void 393169691Skan update_to_top(node_pointer p_nd, Node_Update_* p_update); 394169691Skan 395169691Skan bool 396169691Skan join_prep(PB_DS_CLASS_C_DEC& other); 397169691Skan 398169691Skan void 399169691Skan join_finish(PB_DS_CLASS_C_DEC& other); 400169691Skan 401169691Skan bool 402169691Skan split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); 403169691Skan 404169691Skan void 405169691Skan split_finish(PB_DS_CLASS_C_DEC& other); 406169691Skan 407169691Skan size_type 408169691Skan recursive_count(node_pointer p_nd) const; 409169691Skan 410169691Skan#ifdef _GLIBCXX_DEBUG 411169691Skan void 412169691Skan assert_valid() const; 413169691Skan 414169691Skan void 415169691Skan structure_only_assert_valid() const; 416169691Skan 417169691Skan void 418169691Skan assert_node_consistent(const node_pointer p_nd) const; 419169691Skan#endif 420169691Skan 421169691Skan private: 422169691Skan#ifdef _GLIBCXX_DEBUG 423169691Skan void 424169691Skan assert_iterators() const; 425169691Skan 426169691Skan void 427169691Skan assert_consistent_with_debug_base() const; 428169691Skan 429169691Skan void 430169691Skan assert_node_consistent_with_left(const node_pointer p_nd) const; 431169691Skan 432169691Skan void 433169691Skan assert_node_consistent_with_right(const node_pointer p_nd) const; 434169691Skan 435169691Skan void 436169691Skan assert_consistent_with_debug_base(const node_pointer p_nd) const; 437169691Skan 438169691Skan void 439169691Skan assert_min() const; 440169691Skan 441169691Skan void 442169691Skan assert_min_imp(const node_pointer p_nd) const; 443169691Skan 444169691Skan void 445169691Skan assert_max() const; 446169691Skan 447169691Skan void 448169691Skan assert_max_imp(const node_pointer p_nd) const; 449169691Skan 450169691Skan void 451169691Skan assert_size() const; 452169691Skan 453169691Skan typedef std::pair< const_pointer, const_pointer> node_consistent_t; 454169691Skan 455169691Skan node_consistent_t 456169691Skan assert_node_consistent_(const node_pointer p_nd) const; 457169691Skan#endif 458169691Skan 459169691Skan void 460169691Skan initialize(); 461169691Skan 462169691Skan node_pointer 463169691Skan recursive_copy_node(const node_pointer p_nd); 464169691Skan 465169691Skan protected: 466169691Skan node_pointer m_p_head; 467169691Skan 468169691Skan size_type m_size; 469169691Skan 470169691Skan static node_allocator s_node_allocator; 471169691Skan }; 472169691Skan 473169691Skan#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> 474169691Skan#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> 475169691Skan#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> 476169691Skan#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> 477169691Skan#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> 478169691Skan#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> 479169691Skan#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> 480169691Skan#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> 481169691Skan#include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp> 482169691Skan#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 483169691Skan 484169691Skan#undef PB_DS_CLASS_C_DEC 485169691Skan 486169691Skan#undef PB_DS_CLASS_T_DEC 487169691Skan 488169691Skan#undef PB_DS_CLASS_NAME 489169691Skan 490169691Skan#undef PB_DS_TYPES_TRAITS_C_DEC 491169691Skan 492169691Skan#undef PB_DS_MAP_DEBUG_BASE_C_DEC 493169691Skan 494169691Skan#ifdef PB_DS_TREE_TRACE 495169691Skan#undef PB_DS_TREE_TRACE_BASE_C_DEC 496169691Skan#endif 497169691Skan 498169691Skan#undef PB_DS_V2F 499169691Skan#undef PB_DS_EP2VP 500169691Skan#undef PB_DS_V2S 501169691Skan 502169691Skan } // namespace detail 503169691Skan} // namespace pb_ds 504