1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2013 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_/point_iterators.hpp 38 * Contains an implementation class for bin_search_tree_. 39 */ 40 41 #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 42 #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 43 44 #include <ext/pb_ds/tag_and_trait.hpp> 45 #include <debug/debug.h> 46 47 namespace __gnu_pbds 48 { 49 namespace detail 50 { 51 52 #define PB_DS_TREE_CONST_IT_C_DEC \ 53 bin_search_tree_const_it_< \ 54 Node_Pointer, \ 55 Value_Type, \ 56 Pointer, \ 57 Const_Pointer, \ 58 Reference, \ 59 Const_Reference, \ 60 Is_Forward_Iterator, \ 61 _Alloc> 62 63 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC \ 64 bin_search_tree_const_it_< \ 65 Node_Pointer, \ 66 Value_Type, \ 67 Pointer, \ 68 Const_Pointer, \ 69 Reference, \ 70 Const_Reference, \ 71 !Is_Forward_Iterator, \ 72 _Alloc> 73 74 #define PB_DS_TREE_IT_C_DEC \ 75 bin_search_tree_it_< \ 76 Node_Pointer, \ 77 Value_Type, \ 78 Pointer, \ 79 Const_Pointer, \ 80 Reference, \ 81 Const_Reference, \ 82 Is_Forward_Iterator, \ 83 _Alloc> 84 85 #define PB_DS_TREE_ODIR_IT_C_DEC \ 86 bin_search_tree_it_< \ 87 Node_Pointer, \ 88 Value_Type, \ 89 Pointer, \ 90 Const_Pointer, \ 91 Reference, \ 92 Const_Reference, \ 93 !Is_Forward_Iterator, \ 94 _Alloc> 95 96 /// Const iterator. 97 template<typename Node_Pointer, 98 typename Value_Type, 99 typename Pointer, 100 typename Const_Pointer, 101 typename Reference, 102 typename Const_Reference, 103 bool Is_Forward_Iterator, 104 typename _Alloc> 105 class bin_search_tree_const_it_ 106 { 107 public: 108 typedef std::bidirectional_iterator_tag iterator_category; 109 typedef typename _Alloc::difference_type difference_type; 110 typedef Value_Type value_type; 111 typedef Pointer pointer; 112 typedef Const_Pointer const_pointer; 113 typedef Reference reference; 114 typedef Const_Reference const_reference; 115 116 inline 117 bin_search_tree_const_it_(const Node_Pointer p_nd = 0) 118 : m_p_nd(const_cast<Node_Pointer>(p_nd)) 119 { } 120 121 inline 122 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 123 : m_p_nd(other.m_p_nd) 124 { } 125 126 inline 127 PB_DS_TREE_CONST_IT_C_DEC& 128 operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) 129 { 130 m_p_nd = other.m_p_nd; 131 return *this; 132 } 133 134 inline 135 PB_DS_TREE_CONST_IT_C_DEC& 136 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 137 { 138 m_p_nd = other.m_p_nd; 139 return *this; 140 } 141 142 inline const_pointer 143 operator->() const 144 { 145 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 146 return &m_p_nd->m_value; 147 } 148 149 inline const_reference 150 operator*() const 151 { 152 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 153 return m_p_nd->m_value; 154 } 155 156 inline bool 157 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 158 { return m_p_nd == other.m_p_nd; } 159 160 inline bool 161 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const 162 { return m_p_nd == other.m_p_nd; } 163 164 inline bool 165 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 166 { return m_p_nd != other.m_p_nd; } 167 168 inline bool 169 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const 170 { return m_p_nd != other.m_p_nd; } 171 172 inline PB_DS_TREE_CONST_IT_C_DEC& 173 operator++() 174 { 175 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 176 inc(integral_constant<int,Is_Forward_Iterator>()); 177 return *this; 178 } 179 180 inline PB_DS_TREE_CONST_IT_C_DEC 181 operator++(int) 182 { 183 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 184 operator++(); 185 return ret_it; 186 } 187 188 inline PB_DS_TREE_CONST_IT_C_DEC& 189 operator--() 190 { 191 dec(integral_constant<int,Is_Forward_Iterator>()); 192 return *this; 193 } 194 195 inline PB_DS_TREE_CONST_IT_C_DEC 196 operator--(int) 197 { 198 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 199 operator--(); 200 return ret_it; 201 } 202 203 protected: 204 inline void 205 inc(false_type) 206 { dec(true_type()); } 207 208 void 209 inc(true_type) 210 { 211 if (m_p_nd->special()&& 212 m_p_nd->m_p_parent->m_p_parent == m_p_nd) 213 { 214 m_p_nd = m_p_nd->m_p_left; 215 return; 216 } 217 218 if (m_p_nd->m_p_right != 0) 219 { 220 m_p_nd = m_p_nd->m_p_right; 221 while (m_p_nd->m_p_left != 0) 222 m_p_nd = m_p_nd->m_p_left; 223 return; 224 } 225 226 Node_Pointer p_y = m_p_nd->m_p_parent; 227 while (m_p_nd == p_y->m_p_right) 228 { 229 m_p_nd = p_y; 230 p_y = p_y->m_p_parent; 231 } 232 233 if (m_p_nd->m_p_right != p_y) 234 m_p_nd = p_y; 235 } 236 237 inline void 238 dec(false_type) 239 { inc(true_type()); } 240 241 void 242 dec(true_type) 243 { 244 if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) 245 { 246 m_p_nd = m_p_nd->m_p_right; 247 return; 248 } 249 250 if (m_p_nd->m_p_left != 0) 251 { 252 Node_Pointer p_y = m_p_nd->m_p_left; 253 while (p_y->m_p_right != 0) 254 p_y = p_y->m_p_right; 255 m_p_nd = p_y; 256 return; 257 } 258 259 Node_Pointer p_y = m_p_nd->m_p_parent; 260 while (m_p_nd == p_y->m_p_left) 261 { 262 m_p_nd = p_y; 263 p_y = p_y->m_p_parent; 264 } 265 if (m_p_nd->m_p_left != p_y) 266 m_p_nd = p_y; 267 } 268 269 public: 270 Node_Pointer m_p_nd; 271 }; 272 273 /// Iterator. 274 template<typename Node_Pointer, 275 typename Value_Type, 276 typename Pointer, 277 typename Const_Pointer, 278 typename Reference, 279 typename Const_Reference, 280 bool Is_Forward_Iterator, 281 typename _Alloc> 282 class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC 283 { 284 public: 285 inline 286 bin_search_tree_it_(const Node_Pointer p_nd = 0) 287 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) 288 { } 289 290 inline 291 bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 292 : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) 293 { } 294 295 inline 296 PB_DS_TREE_IT_C_DEC& 297 operator=(const PB_DS_TREE_IT_C_DEC& other) 298 { 299 base_it_type::m_p_nd = other.m_p_nd; 300 return *this; 301 } 302 303 inline 304 PB_DS_TREE_IT_C_DEC& 305 operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) 306 { 307 base_it_type::m_p_nd = other.m_p_nd; 308 return *this; 309 } 310 311 inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer 312 operator->() const 313 { 314 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 315 return &base_it_type::m_p_nd->m_value; 316 } 317 318 inline typename PB_DS_TREE_CONST_IT_C_DEC::reference 319 operator*() const 320 { 321 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 322 return base_it_type::m_p_nd->m_value; 323 } 324 325 inline PB_DS_TREE_IT_C_DEC& 326 operator++() 327 { 328 PB_DS_TREE_CONST_IT_C_DEC:: operator++(); 329 return *this; 330 } 331 332 inline PB_DS_TREE_IT_C_DEC 333 operator++(int) 334 { 335 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 336 operator++(); 337 return ret_it; 338 } 339 340 inline PB_DS_TREE_IT_C_DEC& 341 operator--() 342 { 343 PB_DS_TREE_CONST_IT_C_DEC:: operator--(); 344 return *this; 345 } 346 347 inline PB_DS_TREE_IT_C_DEC 348 operator--(int) 349 { 350 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 351 operator--(); 352 return ret_it; 353 } 354 355 protected: 356 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; 357 }; 358 359 #undef PB_DS_TREE_CONST_IT_C_DEC 360 #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC 361 #undef PB_DS_TREE_IT_C_DEC 362 #undef PB_DS_TREE_ODIR_IT_C_DEC 363 364 } // namespace detail 365 } // namespace __gnu_pbds 366 367 #endif 368
