11592Srgrimes// -*- C++ -*- 21592Srgrimes 31592Srgrimes// Copyright (C) 2005-2022 Free Software Foundation, Inc. 41592Srgrimes// 51592Srgrimes// This file is part of the GNU ISO C++ Library. This library is free 61592Srgrimes// software; you can redistribute it and/or modify it under the terms 71592Srgrimes// of the GNU General Public License as published by the Free Software 81592Srgrimes// Foundation; either version 3, or (at your option) any later 91592Srgrimes// version. 101592Srgrimes 111592Srgrimes// This library is distributed in the hope that it will be useful, but 121592Srgrimes// WITHOUT ANY WARRANTY; without even the implied warranty of 13262435Sbrueffer// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 141592Srgrimes// General Public License for more details. 151592Srgrimes 161592Srgrimes// Under Section 7 of GPL version 3, you are granted additional 171592Srgrimes// permissions described in the GCC Runtime Library Exception, version 181592Srgrimes// 3.1, as published by the Free Software Foundation. 191592Srgrimes 201592Srgrimes// You should have received a copy of the GNU General Public License and 211592Srgrimes// a copy of the GCC Runtime Library Exception along with this program; 221592Srgrimes// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 231592Srgrimes// <http://www.gnu.org/licenses/>. 241592Srgrimes 251592Srgrimes// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 261592Srgrimes 271592Srgrimes// Permission to use, copy, modify, sell, and distribute this software 281592Srgrimes// is hereby granted without fee, provided that the above copyright 291592Srgrimes// notice appears in all copies, and that both that copyright notice 301592Srgrimes// and this permission notice appear in supporting documentation. None 3131512Scharnier// of the above authors, nor IBM Haifa Research Laboratories, make any 321592Srgrimes// representation about the suitability of this software for any 331592Srgrimes// purpose. It is provided "as is" without express or implied 341592Srgrimes// warranty. 351592Srgrimes 361592Srgrimes/** 3731512Scharnier * @file rb_tree_map_/rb_tree_.hpp 381592Srgrimes * Contains an implementation for Red Black trees. 3931512Scharnier */ 401592Srgrimes 41207608Simp#include <ext/pb_ds/detail/standard_policies.hpp> 42207608Simp#include <utility> 431592Srgrimes#include <vector> 441592Srgrimes#include <assert.h> 451592Srgrimes#include <debug/debug.h> 461592Srgrimes 471592Srgrimesnamespace __gnu_pbds 481592Srgrimes{ 491592Srgrimes namespace detail 501592Srgrimes { 511592Srgrimes#define PB_DS_CLASS_T_DEC \ 521592Srgrimes template<typename Key, typename Mapped, typename Cmp_Fn, \ 531592Srgrimes typename Node_And_It_Traits, typename _Alloc> 541592Srgrimes 551592Srgrimes#ifdef PB_DS_DATA_TRUE_INDICATOR 561592Srgrimes# define PB_DS_RB_TREE_NAME rb_tree_map 571592Srgrimes# define PB_DS_RB_TREE_BASE_NAME bin_search_tree_map 581592Srgrimes#endif 591592Srgrimes 601592Srgrimes#ifdef PB_DS_DATA_FALSE_INDICATOR 611592Srgrimes# define PB_DS_RB_TREE_NAME rb_tree_set 621592Srgrimes# define PB_DS_RB_TREE_BASE_NAME bin_search_tree_set 6331512Scharnier#endif 64246139Smarius 651592Srgrimes#define PB_DS_CLASS_C_DEC \ 661592Srgrimes PB_DS_RB_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 671592Srgrimes 681592Srgrimes#define PB_DS_RB_TREE_BASE \ 69207608Simp PB_DS_RB_TREE_BASE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 701592Srgrimes 711592Srgrimes 72207608Simp /** 73207608Simp * @brief Red-Black tree. 74207608Simp * @ingroup branch-detail 75207608Simp * 76207608Simp * This implementation uses an idea from the SGI STL (using a 771592Srgrimes * @a header node which is needed for efficient iteration). 78207608Simp */ 79207608Simp template<typename Key, 801592Srgrimes typename Mapped, 811592Srgrimes typename Cmp_Fn, 821592Srgrimes typename Node_And_It_Traits, 831592Srgrimes typename _Alloc> 841592Srgrimes class PB_DS_RB_TREE_NAME : public PB_DS_RB_TREE_BASE 851592Srgrimes { 861592Srgrimes private: 871592Srgrimes typedef PB_DS_RB_TREE_BASE base_type; 881592Srgrimes typedef typename base_type::node_pointer node_pointer; 891592Srgrimes 90112452Sdwmalone public: 911592Srgrimes typedef rb_tree_tag container_category; 921592Srgrimes typedef Cmp_Fn cmp_fn; 931592Srgrimes typedef _Alloc allocator_type; 941592Srgrimes typedef typename _Alloc::size_type size_type; 9571616Sbillf typedef typename _Alloc::difference_type difference_type; 96129680Smdodd typedef typename base_type::key_type key_type; 97213099Smarius typedef typename base_type::key_pointer key_pointer; 98173852Sedwin typedef typename base_type::key_const_pointer key_const_pointer; 99207608Simp typedef typename base_type::key_reference key_reference; 1001592Srgrimes typedef typename base_type::key_const_reference key_const_reference; 101207608Simp typedef typename base_type::mapped_type mapped_type; 102207608Simp typedef typename base_type::mapped_pointer mapped_pointer; 103207608Simp typedef typename base_type::mapped_const_pointer mapped_const_pointer; 104207608Simp typedef typename base_type::mapped_reference mapped_reference; 105207608Simp typedef typename base_type::mapped_const_reference mapped_const_reference; 1061592Srgrimes typedef typename base_type::value_type value_type; 107241720Sed typedef typename base_type::pointer pointer; 108112452Sdwmalone typedef typename base_type::const_pointer const_pointer; 109241720Sed typedef typename base_type::reference reference; 110207608Simp typedef typename base_type::const_reference const_reference; 111207608Simp typedef typename base_type::point_iterator point_iterator; 112207608Simp typedef typename base_type::const_iterator point_const_iterator; 113207608Simp typedef typename base_type::iterator iterator; 114207608Simp typedef typename base_type::const_iterator const_iterator; 115207608Simp typedef typename base_type::reverse_iterator reverse_iterator; 116207608Simp typedef typename base_type::const_reverse_iterator const_reverse_iterator; 117207608Simp typedef typename base_type::node_update node_update; 1181592Srgrimes 11990333Simp PB_DS_RB_TREE_NAME(); 1201592Srgrimes 12190333Simp PB_DS_RB_TREE_NAME(const Cmp_Fn&); 122207608Simp 123207608Simp PB_DS_RB_TREE_NAME(const Cmp_Fn&, const node_update&); 124207608Simp 125207608Simp PB_DS_RB_TREE_NAME(const PB_DS_CLASS_C_DEC&); 126207608Simp 127207608Simp void 128207608Simp swap(PB_DS_CLASS_C_DEC&); 129207608Simp 130207608Simp template<typename It> 1311592Srgrimes void 132130839Sbrian copy_from_range(It, It); 133207608Simp 134130839Sbrian inline std::pair<point_iterator, bool> 135207608Simp insert(const_reference); 136207608Simp 1371592Srgrimes inline mapped_reference 13871616Sbillf operator[](key_const_reference r_key) 13971616Sbillf { 14071616Sbillf#ifdef PB_DS_DATA_TRUE_INDICATOR 14171616Sbillf _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 14271616Sbillf std::pair<point_iterator, bool> ins_pair = 14371616Sbillf base_type::insert_leaf(value_type(r_key, mapped_type())); 144207608Simp 145207608Simp if (ins_pair.second == true) 146207608Simp { 147207608Simp ins_pair.first.m_p_nd->m_red = true; 148207608Simp _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid(__FILE__, __LINE__);) 149207608Simp insert_fixup(ins_pair.first.m_p_nd); 150173852Sedwin } 151173852Sedwin _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 152173852Sedwin return ins_pair.first.m_p_nd->m_value.second; 1531592Srgrimes#else 1541592Srgrimes insert(r_key); 1551592Srgrimes return base_type::s_null_type; 1561592Srgrimes#endif 1571592Srgrimes } 1581592Srgrimes 159207608Simp inline bool 160207608Simp erase(key_const_reference); 161207608Simp 162207608Simp inline iterator 163207608Simp erase(iterator); 164207608Simp 165207608Simp inline reverse_iterator 166207608Simp erase(reverse_iterator); 167207608Simp 168207608Simp template<typename Pred> 169207608Simp inline size_type 170207608Simp erase_if(Pred); 17118458Simp 17218458Simp void 17318458Simp join(PB_DS_CLASS_C_DEC&); 17465850Swollman 17565850Swollman void 17665850Swollman split(key_const_reference, PB_DS_CLASS_C_DEC&); 177129680Smdodd 178129680Smdodd private: 179129680Smdodd 180129680Smdodd#ifdef _GLIBCXX_DEBUG 181129680Smdodd void 182129680Smdodd assert_valid(const char*, int) const; 183173852Sedwin 184173852Sedwin size_type 185173852Sedwin assert_node_consistent(const node_pointer, const char*, int) const; 186173852Sedwin#endif 1871592Srgrimes 188207608Simp inline static bool 189207608Simp is_effectively_black(const node_pointer); 1901592Srgrimes 1911592Srgrimes void 1921592Srgrimes initialize(); 1931592Srgrimes 1941592Srgrimes void 1951592Srgrimes insert_fixup(node_pointer); 1961592Srgrimes 1971592Srgrimes void 1981592Srgrimes erase_node(node_pointer); 1991592Srgrimes 2001592Srgrimes void 2011592Srgrimes remove_node(node_pointer); 2021592Srgrimes 2031592Srgrimes void 2041592Srgrimes remove_fixup(node_pointer, node_pointer); 20518458Simp 20618458Simp void 20718458Simp split_imp(node_pointer, PB_DS_CLASS_C_DEC&); 20818458Simp 209113714Sbillf inline node_pointer 210207608Simp split_min(); 21171616Sbillf 21271616Sbillf std::pair<node_pointer, node_pointer> 2131592Srgrimes split_min_imp(); 214129680Smdodd 215129680Smdodd void 216207608Simp join_imp(node_pointer, node_pointer); 217207608Simp 218207608Simp std::pair<node_pointer, node_pointer> 219207608Simp find_join_pos_right(node_pointer, size_type, size_type); 220207608Simp 221207608Simp std::pair<node_pointer, node_pointer> 2221592Srgrimes find_join_pos_left(node_pointer, size_type, size_type); 223207608Simp 224207608Simp inline size_type 225207608Simp black_height(node_pointer); 226207608Simp 227207608Simp void 2281592Srgrimes split_at_node(node_pointer, PB_DS_CLASS_C_DEC&); 229207608Simp }; 2301592Srgrimes 2311592Srgrimes#define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \ 232207608Simp _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);) 233207608Simp 234207608Simp#include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp> 2351592Srgrimes#include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp> 2361592Srgrimes#include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp> 2371592Srgrimes#include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp> 2381592Srgrimes#include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp> 2391592Srgrimes#include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp> 2401592Srgrimes 2411592Srgrimes#undef PB_DS_STRUCT_ONLY_ASSERT_VALID 2421592Srgrimes#undef PB_DS_CLASS_T_DEC 2431592Srgrimes#undef PB_DS_CLASS_C_DEC 2441592Srgrimes#undef PB_DS_RB_TREE_NAME 2451592Srgrimes#undef PB_DS_RB_TREE_BASE_NAME 2461592Srgrimes#undef PB_DS_RB_TREE_BASE 2471592Srgrimes } // namespace detail 2481592Srgrimes} // namespace __gnu_pbds 2491592Srgrimes