1*38fd1498Szrj // -*- C++ -*- 2*38fd1498Szrj 3*38fd1498Szrj // Copyright (C) 2005-2018 Free Software Foundation, Inc. 4*38fd1498Szrj // 5*38fd1498Szrj // This file is part of the GNU ISO C++ Library. This library is free 6*38fd1498Szrj // software; you can redistribute it and/or modify it under the terms 7*38fd1498Szrj // of the GNU General Public License as published by the Free Software 8*38fd1498Szrj // Foundation; either version 3, or (at your option) any later 9*38fd1498Szrj // version. 10*38fd1498Szrj 11*38fd1498Szrj // This library is distributed in the hope that it will be useful, but 12*38fd1498Szrj // WITHOUT ANY WARRANTY; without even the implied warranty of 13*38fd1498Szrj // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14*38fd1498Szrj // General Public License for more details. 15*38fd1498Szrj 16*38fd1498Szrj // Under Section 7 of GPL version 3, you are granted additional 17*38fd1498Szrj // permissions described in the GCC Runtime Library Exception, version 18*38fd1498Szrj // 3.1, as published by the Free Software Foundation. 19*38fd1498Szrj 20*38fd1498Szrj // You should have received a copy of the GNU General Public License and 21*38fd1498Szrj // a copy of the GCC Runtime Library Exception along with this program; 22*38fd1498Szrj // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23*38fd1498Szrj // <http://www.gnu.org/licenses/>. 24*38fd1498Szrj 25*38fd1498Szrj // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26*38fd1498Szrj 27*38fd1498Szrj // Permission to use, copy, modify, sell, and distribute this software 28*38fd1498Szrj // is hereby granted without fee, provided that the above copyright 29*38fd1498Szrj // notice appears in all copies, and that both that copyright notice 30*38fd1498Szrj // and this permission notice appear in supporting documentation. None 31*38fd1498Szrj // of the above authors, nor IBM Haifa Research Laboratories, make any 32*38fd1498Szrj // representation about the suitability of this software for any 33*38fd1498Szrj // purpose. It is provided "as is" without express or implied 34*38fd1498Szrj // warranty. 35*38fd1498Szrj 36*38fd1498Szrj /** 37*38fd1498Szrj * @file bin_search_tree_/point_iterators.hpp 38*38fd1498Szrj * Contains an implementation class for bin_search_tree_. 39*38fd1498Szrj */ 40*38fd1498Szrj 41*38fd1498Szrj #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 42*38fd1498Szrj #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 43*38fd1498Szrj 44*38fd1498Szrj #include <ext/pb_ds/tag_and_trait.hpp> 45*38fd1498Szrj #include <debug/debug.h> 46*38fd1498Szrj 47*38fd1498Szrj namespace __gnu_pbds 48*38fd1498Szrj { 49*38fd1498Szrj namespace detail 50*38fd1498Szrj { 51*38fd1498Szrj 52*38fd1498Szrj #define PB_DS_TREE_CONST_IT_C_DEC \ 53*38fd1498Szrj bin_search_tree_const_it_< \ 54*38fd1498Szrj Node_Pointer, \ 55*38fd1498Szrj Value_Type, \ 56*38fd1498Szrj Pointer, \ 57*38fd1498Szrj Const_Pointer, \ 58*38fd1498Szrj Reference, \ 59*38fd1498Szrj Const_Reference, \ 60*38fd1498Szrj Is_Forward_Iterator, \ 61*38fd1498Szrj _Alloc> 62*38fd1498Szrj 63*38fd1498Szrj #define PB_DS_TREE_CONST_ODIR_IT_C_DEC \ 64*38fd1498Szrj bin_search_tree_const_it_< \ 65*38fd1498Szrj Node_Pointer, \ 66*38fd1498Szrj Value_Type, \ 67*38fd1498Szrj Pointer, \ 68*38fd1498Szrj Const_Pointer, \ 69*38fd1498Szrj Reference, \ 70*38fd1498Szrj Const_Reference, \ 71*38fd1498Szrj !Is_Forward_Iterator, \ 72*38fd1498Szrj _Alloc> 73*38fd1498Szrj 74*38fd1498Szrj #define PB_DS_TREE_IT_C_DEC \ 75*38fd1498Szrj bin_search_tree_it_< \ 76*38fd1498Szrj Node_Pointer, \ 77*38fd1498Szrj Value_Type, \ 78*38fd1498Szrj Pointer, \ 79*38fd1498Szrj Const_Pointer, \ 80*38fd1498Szrj Reference, \ 81*38fd1498Szrj Const_Reference, \ 82*38fd1498Szrj Is_Forward_Iterator, \ 83*38fd1498Szrj _Alloc> 84*38fd1498Szrj 85*38fd1498Szrj #define PB_DS_TREE_ODIR_IT_C_DEC \ 86*38fd1498Szrj bin_search_tree_it_< \ 87*38fd1498Szrj Node_Pointer, \ 88*38fd1498Szrj Value_Type, \ 89*38fd1498Szrj Pointer, \ 90*38fd1498Szrj Const_Pointer, \ 91*38fd1498Szrj Reference, \ 92*38fd1498Szrj Const_Reference, \ 93*38fd1498Szrj !Is_Forward_Iterator, \ 94*38fd1498Szrj _Alloc> 95*38fd1498Szrj 96*38fd1498Szrj /// Const iterator. 97*38fd1498Szrj template<typename Node_Pointer, 98*38fd1498Szrj typename Value_Type, 99*38fd1498Szrj typename Pointer, 100*38fd1498Szrj typename Const_Pointer, 101*38fd1498Szrj typename Reference, 102*38fd1498Szrj typename Const_Reference, 103*38fd1498Szrj bool Is_Forward_Iterator, 104*38fd1498Szrj typename _Alloc> 105*38fd1498Szrj class bin_search_tree_const_it_ 106*38fd1498Szrj { 107*38fd1498Szrj public: 108*38fd1498Szrj typedef std::bidirectional_iterator_tag iterator_category; 109*38fd1498Szrj typedef typename _Alloc::difference_type difference_type; 110*38fd1498Szrj typedef Value_Type value_type; 111*38fd1498Szrj typedef Pointer pointer; 112*38fd1498Szrj typedef Const_Pointer const_pointer; 113*38fd1498Szrj typedef Reference reference; 114*38fd1498Szrj typedef Const_Reference const_reference; 115*38fd1498Szrj 116*38fd1498Szrj inline bin_search_tree_const_it_(const Node_Pointer p_nd=0)117*38fd1498Szrj bin_search_tree_const_it_(const Node_Pointer p_nd = 0) 118*38fd1498Szrj : m_p_nd(const_cast<Node_Pointer>(p_nd)) 119*38fd1498Szrj { } 120*38fd1498Szrj 121*38fd1498Szrj inline bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other)122*38fd1498Szrj bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 123*38fd1498Szrj : m_p_nd(other.m_p_nd) 124*38fd1498Szrj { } 125*38fd1498Szrj 126*38fd1498Szrj inline 127*38fd1498Szrj PB_DS_TREE_CONST_IT_C_DEC& operator =(const PB_DS_TREE_CONST_IT_C_DEC & other)128*38fd1498Szrj operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) 129*38fd1498Szrj { 130*38fd1498Szrj m_p_nd = other.m_p_nd; 131*38fd1498Szrj return *this; 132*38fd1498Szrj } 133*38fd1498Szrj 134*38fd1498Szrj inline 135*38fd1498Szrj PB_DS_TREE_CONST_IT_C_DEC& operator =(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other)136*38fd1498Szrj operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 137*38fd1498Szrj { 138*38fd1498Szrj m_p_nd = other.m_p_nd; 139*38fd1498Szrj return *this; 140*38fd1498Szrj } 141*38fd1498Szrj 142*38fd1498Szrj inline const_pointer operator ->() const143*38fd1498Szrj operator->() const 144*38fd1498Szrj { 145*38fd1498Szrj _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 146*38fd1498Szrj return &m_p_nd->m_value; 147*38fd1498Szrj } 148*38fd1498Szrj 149*38fd1498Szrj inline const_reference operator *() const150*38fd1498Szrj operator*() const 151*38fd1498Szrj { 152*38fd1498Szrj _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 153*38fd1498Szrj return m_p_nd->m_value; 154*38fd1498Szrj } 155*38fd1498Szrj 156*38fd1498Szrj inline bool operator ==(const PB_DS_TREE_CONST_IT_C_DEC & other) const157*38fd1498Szrj operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 158*38fd1498Szrj { return m_p_nd == other.m_p_nd; } 159*38fd1498Szrj 160*38fd1498Szrj inline bool operator ==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const161*38fd1498Szrj operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const 162*38fd1498Szrj { return m_p_nd == other.m_p_nd; } 163*38fd1498Szrj 164*38fd1498Szrj inline bool operator !=(const PB_DS_TREE_CONST_IT_C_DEC & other) const165*38fd1498Szrj operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 166*38fd1498Szrj { return m_p_nd != other.m_p_nd; } 167*38fd1498Szrj 168*38fd1498Szrj inline bool operator !=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const169*38fd1498Szrj operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const 170*38fd1498Szrj { return m_p_nd != other.m_p_nd; } 171*38fd1498Szrj 172*38fd1498Szrj inline PB_DS_TREE_CONST_IT_C_DEC& operator ++()173*38fd1498Szrj operator++() 174*38fd1498Szrj { 175*38fd1498Szrj _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 176*38fd1498Szrj inc(integral_constant<int,Is_Forward_Iterator>()); 177*38fd1498Szrj return *this; 178*38fd1498Szrj } 179*38fd1498Szrj 180*38fd1498Szrj inline PB_DS_TREE_CONST_IT_C_DEC operator ++(int)181*38fd1498Szrj operator++(int) 182*38fd1498Szrj { 183*38fd1498Szrj PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 184*38fd1498Szrj operator++(); 185*38fd1498Szrj return ret_it; 186*38fd1498Szrj } 187*38fd1498Szrj 188*38fd1498Szrj inline PB_DS_TREE_CONST_IT_C_DEC& operator --()189*38fd1498Szrj operator--() 190*38fd1498Szrj { 191*38fd1498Szrj dec(integral_constant<int,Is_Forward_Iterator>()); 192*38fd1498Szrj return *this; 193*38fd1498Szrj } 194*38fd1498Szrj 195*38fd1498Szrj inline PB_DS_TREE_CONST_IT_C_DEC operator --(int)196*38fd1498Szrj operator--(int) 197*38fd1498Szrj { 198*38fd1498Szrj PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 199*38fd1498Szrj operator--(); 200*38fd1498Szrj return ret_it; 201*38fd1498Szrj } 202*38fd1498Szrj 203*38fd1498Szrj protected: 204*38fd1498Szrj inline void inc(false_type)205*38fd1498Szrj inc(false_type) 206*38fd1498Szrj { dec(true_type()); } 207*38fd1498Szrj 208*38fd1498Szrj void inc(true_type)209*38fd1498Szrj inc(true_type) 210*38fd1498Szrj { 211*38fd1498Szrj if (m_p_nd->special()&& 212*38fd1498Szrj m_p_nd->m_p_parent->m_p_parent == m_p_nd) 213*38fd1498Szrj { 214*38fd1498Szrj m_p_nd = m_p_nd->m_p_left; 215*38fd1498Szrj return; 216*38fd1498Szrj } 217*38fd1498Szrj 218*38fd1498Szrj if (m_p_nd->m_p_right != 0) 219*38fd1498Szrj { 220*38fd1498Szrj m_p_nd = m_p_nd->m_p_right; 221*38fd1498Szrj while (m_p_nd->m_p_left != 0) 222*38fd1498Szrj m_p_nd = m_p_nd->m_p_left; 223*38fd1498Szrj return; 224*38fd1498Szrj } 225*38fd1498Szrj 226*38fd1498Szrj Node_Pointer p_y = m_p_nd->m_p_parent; 227*38fd1498Szrj while (m_p_nd == p_y->m_p_right) 228*38fd1498Szrj { 229*38fd1498Szrj m_p_nd = p_y; 230*38fd1498Szrj p_y = p_y->m_p_parent; 231*38fd1498Szrj } 232*38fd1498Szrj 233*38fd1498Szrj if (m_p_nd->m_p_right != p_y) 234*38fd1498Szrj m_p_nd = p_y; 235*38fd1498Szrj } 236*38fd1498Szrj 237*38fd1498Szrj inline void dec(false_type)238*38fd1498Szrj dec(false_type) 239*38fd1498Szrj { inc(true_type()); } 240*38fd1498Szrj 241*38fd1498Szrj void dec(true_type)242*38fd1498Szrj dec(true_type) 243*38fd1498Szrj { 244*38fd1498Szrj if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) 245*38fd1498Szrj { 246*38fd1498Szrj m_p_nd = m_p_nd->m_p_right; 247*38fd1498Szrj return; 248*38fd1498Szrj } 249*38fd1498Szrj 250*38fd1498Szrj if (m_p_nd->m_p_left != 0) 251*38fd1498Szrj { 252*38fd1498Szrj Node_Pointer p_y = m_p_nd->m_p_left; 253*38fd1498Szrj while (p_y->m_p_right != 0) 254*38fd1498Szrj p_y = p_y->m_p_right; 255*38fd1498Szrj m_p_nd = p_y; 256*38fd1498Szrj return; 257*38fd1498Szrj } 258*38fd1498Szrj 259*38fd1498Szrj Node_Pointer p_y = m_p_nd->m_p_parent; 260*38fd1498Szrj while (m_p_nd == p_y->m_p_left) 261*38fd1498Szrj { 262*38fd1498Szrj m_p_nd = p_y; 263*38fd1498Szrj p_y = p_y->m_p_parent; 264*38fd1498Szrj } 265*38fd1498Szrj if (m_p_nd->m_p_left != p_y) 266*38fd1498Szrj m_p_nd = p_y; 267*38fd1498Szrj } 268*38fd1498Szrj 269*38fd1498Szrj public: 270*38fd1498Szrj Node_Pointer m_p_nd; 271*38fd1498Szrj }; 272*38fd1498Szrj 273*38fd1498Szrj /// Iterator. 274*38fd1498Szrj template<typename Node_Pointer, 275*38fd1498Szrj typename Value_Type, 276*38fd1498Szrj typename Pointer, 277*38fd1498Szrj typename Const_Pointer, 278*38fd1498Szrj typename Reference, 279*38fd1498Szrj typename Const_Reference, 280*38fd1498Szrj bool Is_Forward_Iterator, 281*38fd1498Szrj typename _Alloc> 282*38fd1498Szrj class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC 283*38fd1498Szrj { 284*38fd1498Szrj public: 285*38fd1498Szrj inline bin_search_tree_it_(const Node_Pointer p_nd=0)286*38fd1498Szrj bin_search_tree_it_(const Node_Pointer p_nd = 0) 287*38fd1498Szrj : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) 288*38fd1498Szrj { } 289*38fd1498Szrj 290*38fd1498Szrj inline bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC & other)291*38fd1498Szrj bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 292*38fd1498Szrj : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) 293*38fd1498Szrj { } 294*38fd1498Szrj 295*38fd1498Szrj inline 296*38fd1498Szrj PB_DS_TREE_IT_C_DEC& operator =(const PB_DS_TREE_IT_C_DEC & other)297*38fd1498Szrj operator=(const PB_DS_TREE_IT_C_DEC& other) 298*38fd1498Szrj { 299*38fd1498Szrj base_it_type::m_p_nd = other.m_p_nd; 300*38fd1498Szrj return *this; 301*38fd1498Szrj } 302*38fd1498Szrj 303*38fd1498Szrj inline 304*38fd1498Szrj PB_DS_TREE_IT_C_DEC& operator =(const PB_DS_TREE_ODIR_IT_C_DEC & other)305*38fd1498Szrj operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) 306*38fd1498Szrj { 307*38fd1498Szrj base_it_type::m_p_nd = other.m_p_nd; 308*38fd1498Szrj return *this; 309*38fd1498Szrj } 310*38fd1498Szrj 311*38fd1498Szrj inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer operator ->() const312*38fd1498Szrj operator->() const 313*38fd1498Szrj { 314*38fd1498Szrj _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 315*38fd1498Szrj return &base_it_type::m_p_nd->m_value; 316*38fd1498Szrj } 317*38fd1498Szrj 318*38fd1498Szrj inline typename PB_DS_TREE_CONST_IT_C_DEC::reference operator *() const319*38fd1498Szrj operator*() const 320*38fd1498Szrj { 321*38fd1498Szrj _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 322*38fd1498Szrj return base_it_type::m_p_nd->m_value; 323*38fd1498Szrj } 324*38fd1498Szrj 325*38fd1498Szrj inline PB_DS_TREE_IT_C_DEC& operator ++()326*38fd1498Szrj operator++() 327*38fd1498Szrj { 328*38fd1498Szrj PB_DS_TREE_CONST_IT_C_DEC:: operator++(); 329*38fd1498Szrj return *this; 330*38fd1498Szrj } 331*38fd1498Szrj 332*38fd1498Szrj inline PB_DS_TREE_IT_C_DEC operator ++(int)333*38fd1498Szrj operator++(int) 334*38fd1498Szrj { 335*38fd1498Szrj PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 336*38fd1498Szrj operator++(); 337*38fd1498Szrj return ret_it; 338*38fd1498Szrj } 339*38fd1498Szrj 340*38fd1498Szrj inline PB_DS_TREE_IT_C_DEC& operator --()341*38fd1498Szrj operator--() 342*38fd1498Szrj { 343*38fd1498Szrj PB_DS_TREE_CONST_IT_C_DEC:: operator--(); 344*38fd1498Szrj return *this; 345*38fd1498Szrj } 346*38fd1498Szrj 347*38fd1498Szrj inline PB_DS_TREE_IT_C_DEC operator --(int)348*38fd1498Szrj operator--(int) 349*38fd1498Szrj { 350*38fd1498Szrj PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 351*38fd1498Szrj operator--(); 352*38fd1498Szrj return ret_it; 353*38fd1498Szrj } 354*38fd1498Szrj 355*38fd1498Szrj protected: 356*38fd1498Szrj typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; 357*38fd1498Szrj }; 358*38fd1498Szrj 359*38fd1498Szrj #undef PB_DS_TREE_CONST_IT_C_DEC 360*38fd1498Szrj #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC 361*38fd1498Szrj #undef PB_DS_TREE_IT_C_DEC 362*38fd1498Szrj #undef PB_DS_TREE_ODIR_IT_C_DEC 363*38fd1498Szrj 364*38fd1498Szrj } // namespace detail 365*38fd1498Szrj } // namespace __gnu_pbds 366*38fd1498Szrj 367*38fd1498Szrj #endif 368