1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009, 2010 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 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 Allocator> 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 Allocator> 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 Allocator> 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 Allocator> 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 class Allocator> 105 class bin_search_tree_const_it_ 106 { 107 108 public: 109 110 typedef std::bidirectional_iterator_tag iterator_category; 111 112 typedef typename Allocator::difference_type difference_type; 113 114 typedef Value_Type value_type; 115 116 typedef Pointer pointer; 117 118 typedef Const_Pointer const_pointer; 119 120 typedef Reference reference; 121 122 typedef Const_Reference const_reference; 123 124 public: 125 126 inline 127 bin_search_tree_const_it_(const Node_Pointer p_nd = 0) 128 : m_p_nd(const_cast<Node_Pointer>(p_nd)) 129 { } 130 131 inline 132 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 133 : m_p_nd(other.m_p_nd) 134 { } 135 136 inline 137 PB_DS_TREE_CONST_IT_C_DEC& 138 operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) 139 { 140 m_p_nd = other.m_p_nd; 141 return *this; 142 } 143 144 inline 145 PB_DS_TREE_CONST_IT_C_DEC& 146 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 147 { 148 m_p_nd = other.m_p_nd; 149 return *this; 150 } 151 152 inline const_pointer 153 operator->() const 154 { 155 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 156 return &m_p_nd->m_value; 157 } 158 159 inline const_reference 160 operator*() const 161 { 162 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 163 return m_p_nd->m_value; 164 } 165 166 inline bool 167 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 168 { return m_p_nd == other.m_p_nd; } 169 170 inline bool 171 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const 172 { return m_p_nd == other.m_p_nd; } 173 174 inline bool 175 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 176 { return m_p_nd != other.m_p_nd; } 177 178 inline bool 179 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const 180 { return m_p_nd != other.m_p_nd; } 181 182 inline PB_DS_TREE_CONST_IT_C_DEC& 183 operator++() 184 { 185 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 186 inc(integral_constant<int,Is_Forward_Iterator>()); 187 return *this; 188 } 189 190 inline PB_DS_TREE_CONST_IT_C_DEC 191 operator++(int) 192 { 193 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 194 operator++(); 195 return ret_it; 196 } 197 198 inline PB_DS_TREE_CONST_IT_C_DEC& 199 operator--() 200 { 201 dec(integral_constant<int,Is_Forward_Iterator>()); 202 return *this; 203 } 204 205 inline PB_DS_TREE_CONST_IT_C_DEC 206 operator--(int) 207 { 208 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 209 operator--(); 210 return ret_it; 211 } 212 213 protected: 214 inline void 215 inc(false_type) 216 { dec(true_type()); } 217 218 void 219 inc(true_type) 220 { 221 if (m_p_nd->special()&& 222 m_p_nd->m_p_parent->m_p_parent == m_p_nd) 223 { 224 m_p_nd = m_p_nd->m_p_left; 225 return; 226 } 227 228 if (m_p_nd->m_p_right != 0) 229 { 230 m_p_nd = m_p_nd->m_p_right; 231 while (m_p_nd->m_p_left != 0) 232 m_p_nd = m_p_nd->m_p_left; 233 return; 234 } 235 236 Node_Pointer p_y = m_p_nd->m_p_parent; 237 while (m_p_nd == p_y->m_p_right) 238 { 239 m_p_nd = p_y; 240 p_y = p_y->m_p_parent; 241 } 242 243 if (m_p_nd->m_p_right != p_y) 244 m_p_nd = p_y; 245 } 246 247 inline void 248 dec(false_type) 249 { inc(true_type()); } 250 251 void 252 dec(true_type) 253 { 254 if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) 255 { 256 m_p_nd = m_p_nd->m_p_right; 257 return; 258 } 259 260 if (m_p_nd->m_p_left != 0) 261 { 262 Node_Pointer p_y = m_p_nd->m_p_left; 263 while (p_y->m_p_right != 0) 264 p_y = p_y->m_p_right; 265 m_p_nd = p_y; 266 return; 267 } 268 269 Node_Pointer p_y = m_p_nd->m_p_parent; 270 while (m_p_nd == p_y->m_p_left) 271 { 272 m_p_nd = p_y; 273 p_y = p_y->m_p_parent; 274 } 275 if (m_p_nd->m_p_left != p_y) 276 m_p_nd = p_y; 277 } 278 279 public: 280 Node_Pointer m_p_nd; 281 }; 282 283 // Iterator. 284 template<typename Node_Pointer, 285 typename Value_Type, 286 typename Pointer, 287 typename Const_Pointer, 288 typename Reference, 289 typename Const_Reference, 290 bool Is_Forward_Iterator, 291 class Allocator> 292 class bin_search_tree_it_ : 293 public PB_DS_TREE_CONST_IT_C_DEC 294 295 { 296 297 public: 298 299 inline 300 bin_search_tree_it_(const Node_Pointer p_nd = 0) 301 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) 302 { } 303 304 inline 305 bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 306 : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) 307 { } 308 309 inline 310 PB_DS_TREE_IT_C_DEC& 311 operator=(const PB_DS_TREE_IT_C_DEC& other) 312 { 313 base_it_type::m_p_nd = other.m_p_nd; 314 return *this; 315 } 316 317 inline 318 PB_DS_TREE_IT_C_DEC& 319 operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) 320 { 321 base_it_type::m_p_nd = other.m_p_nd; 322 return *this; 323 } 324 325 inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer 326 operator->() const 327 { 328 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 329 return &base_it_type::m_p_nd->m_value; 330 } 331 332 inline typename PB_DS_TREE_CONST_IT_C_DEC::reference 333 operator*() const 334 { 335 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 336 return base_it_type::m_p_nd->m_value; 337 } 338 339 inline PB_DS_TREE_IT_C_DEC& 340 operator++() 341 { 342 PB_DS_TREE_CONST_IT_C_DEC:: operator++(); 343 return *this; 344 } 345 346 inline PB_DS_TREE_IT_C_DEC 347 operator++(int) 348 { 349 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 350 operator++(); 351 return ret_it; 352 } 353 354 inline PB_DS_TREE_IT_C_DEC& 355 operator--() 356 { 357 PB_DS_TREE_CONST_IT_C_DEC:: operator--(); 358 return *this; 359 } 360 361 inline PB_DS_TREE_IT_C_DEC 362 operator--(int) 363 { 364 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 365 operator--(); 366 return ret_it; 367 } 368 369 protected: 370 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; 371 }; 372 373 #undef PB_DS_TREE_CONST_IT_C_DEC 374 #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC 375 #undef PB_DS_TREE_IT_C_DEC 376 #undef PB_DS_TREE_ODIR_IT_C_DEC 377 378 } // namespace detail 379 } // namespace __gnu_pbds 380 381 #endif 382
