1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License 17 // along with this library; see the file COPYING. If not, write to 18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19 // MA 02111-1307, USA. 20 21 // As a special exception, you may use this file as part of a free 22 // software library without restriction. Specifically, if other files 23 // instantiate templates or use macros or inline functions from this 24 // file, or you compile this file and link it with other files to 25 // produce an executable, this file does not by itself cause the 26 // resulting executable to be covered by the GNU General Public 27 // License. This exception does not however invalidate any other 28 // reasons why the executable file might be covered by the GNU General 29 // Public License. 30 31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33 // Permission to use, copy, modify, sell, and distribute this software 34 // is hereby granted without fee, provided that the above copyright 35 // notice appears in all copies, and that both that copyright notice 36 // and this permission notice appear in supporting documentation. None 37 // of the above authors, nor IBM Haifa Research Laboratories, make any 38 // representation about the suitability of this software for any 39 // purpose. It is provided "as is" without express or implied 40 // warranty. 41 42 /** 43 * @file point_iterators.hpp 44 * Contains an implementation class for bin_search_tree_. 45 */ 46 47 #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 48 #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 49 50 #include <ext/pb_ds/tag_and_trait.hpp> 51 #include <debug/debug.h> 52 53 namespace pb_ds 54 { 55 namespace detail 56 { 57 58 #define PB_DS_TREE_CONST_IT_C_DEC \ 59 bin_search_tree_const_it_< \ 60 Node_Pointer, \ 61 Value_Type, \ 62 Pointer, \ 63 Const_Pointer, \ 64 Reference, \ 65 Const_Reference, \ 66 Is_Forward_Iterator, \ 67 Allocator> 68 69 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC \ 70 bin_search_tree_const_it_< \ 71 Node_Pointer, \ 72 Value_Type, \ 73 Pointer, \ 74 Const_Pointer, \ 75 Reference, \ 76 Const_Reference, \ 77 !Is_Forward_Iterator, \ 78 Allocator> 79 80 #define PB_DS_TREE_IT_C_DEC \ 81 bin_search_tree_it_< \ 82 Node_Pointer, \ 83 Value_Type, \ 84 Pointer, \ 85 Const_Pointer, \ 86 Reference, \ 87 Const_Reference, \ 88 Is_Forward_Iterator, \ 89 Allocator> 90 91 #define PB_DS_TREE_ODIR_IT_C_DEC \ 92 bin_search_tree_it_< \ 93 Node_Pointer, \ 94 Value_Type, \ 95 Pointer, \ 96 Const_Pointer, \ 97 Reference, \ 98 Const_Reference, \ 99 !Is_Forward_Iterator, \ 100 Allocator> 101 102 // Const iterator. 103 template<typename Node_Pointer, 104 typename Value_Type, 105 typename Pointer, 106 typename Const_Pointer, 107 typename Reference, 108 typename Const_Reference, 109 bool Is_Forward_Iterator, 110 class Allocator> 111 class bin_search_tree_const_it_ 112 { 113 114 public: 115 116 typedef std::bidirectional_iterator_tag iterator_category; 117 118 typedef typename Allocator::difference_type difference_type; 119 120 typedef Value_Type value_type; 121 122 typedef Pointer pointer; 123 124 typedef Const_Pointer const_pointer; 125 126 typedef Reference reference; 127 128 typedef Const_Reference const_reference; 129 130 public: 131 132 inline bin_search_tree_const_it_(const Node_Pointer p_nd=NULL)133 bin_search_tree_const_it_(const Node_Pointer p_nd = NULL) 134 : m_p_nd(const_cast<Node_Pointer>(p_nd)) 135 { } 136 137 inline bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other)138 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 139 : m_p_nd(other.m_p_nd) 140 { } 141 142 inline 143 PB_DS_TREE_CONST_IT_C_DEC& operator =(const PB_DS_TREE_CONST_IT_C_DEC & other)144 operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) 145 { 146 m_p_nd = other.m_p_nd; 147 return *this; 148 } 149 150 inline 151 PB_DS_TREE_CONST_IT_C_DEC& operator =(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other)152 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 153 { 154 m_p_nd = other.m_p_nd; 155 return *this; 156 } 157 158 inline const_pointer operator ->() const159 operator->() const 160 { 161 _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 162 return &m_p_nd->m_value; 163 } 164 165 inline const_reference operator *() const166 operator*() const 167 { 168 _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 169 return m_p_nd->m_value; 170 } 171 172 inline bool operator ==(const PB_DS_TREE_CONST_IT_C_DEC & other) const173 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 174 { return m_p_nd == other.m_p_nd; } 175 176 inline bool operator ==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const177 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const 178 { return m_p_nd == other.m_p_nd; } 179 180 inline bool operator !=(const PB_DS_TREE_CONST_IT_C_DEC & other) const181 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 182 { return m_p_nd != other.m_p_nd; } 183 184 inline bool operator !=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const185 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const 186 { return m_p_nd != other.m_p_nd; } 187 188 inline PB_DS_TREE_CONST_IT_C_DEC& operator ++()189 operator++() 190 { 191 _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 192 inc(integral_constant<int,Is_Forward_Iterator>()); 193 return *this; 194 } 195 196 inline PB_DS_TREE_CONST_IT_C_DEC operator ++(int)197 operator++(int) 198 { 199 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 200 operator++(); 201 return ret_it; 202 } 203 204 inline PB_DS_TREE_CONST_IT_C_DEC& operator --()205 operator--() 206 { 207 dec(integral_constant<int,Is_Forward_Iterator>()); 208 return *this; 209 } 210 211 inline PB_DS_TREE_CONST_IT_C_DEC operator --(int)212 operator--(int) 213 { 214 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 215 operator--(); 216 return ret_it; 217 } 218 219 protected: 220 inline void inc(false_type)221 inc(false_type) 222 { dec(true_type()); } 223 224 void inc(true_type)225 inc(true_type) 226 { 227 if (m_p_nd->special()&& 228 m_p_nd->m_p_parent->m_p_parent == m_p_nd) 229 { 230 m_p_nd = m_p_nd->m_p_left; 231 return; 232 } 233 234 if (m_p_nd->m_p_right != NULL) 235 { 236 m_p_nd = m_p_nd->m_p_right; 237 while (m_p_nd->m_p_left != NULL) 238 m_p_nd = m_p_nd->m_p_left; 239 return; 240 } 241 242 Node_Pointer p_y = m_p_nd->m_p_parent; 243 while (m_p_nd == p_y->m_p_right) 244 { 245 m_p_nd = p_y; 246 p_y = p_y->m_p_parent; 247 } 248 249 if (m_p_nd->m_p_right != p_y) 250 m_p_nd = p_y; 251 } 252 253 inline void dec(false_type)254 dec(false_type) 255 { inc(true_type()); } 256 257 void dec(true_type)258 dec(true_type) 259 { 260 if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) 261 { 262 m_p_nd = m_p_nd->m_p_right; 263 return; 264 } 265 266 if (m_p_nd->m_p_left != NULL) 267 { 268 Node_Pointer p_y = m_p_nd->m_p_left; 269 while (p_y->m_p_right != NULL) 270 p_y = p_y->m_p_right; 271 m_p_nd = p_y; 272 return; 273 } 274 275 Node_Pointer p_y = m_p_nd->m_p_parent; 276 while (m_p_nd == p_y->m_p_left) 277 { 278 m_p_nd = p_y; 279 p_y = p_y->m_p_parent; 280 } 281 if (m_p_nd->m_p_left != p_y) 282 m_p_nd = p_y; 283 } 284 285 public: 286 Node_Pointer m_p_nd; 287 }; 288 289 // Iterator. 290 template<typename Node_Pointer, 291 typename Value_Type, 292 typename Pointer, 293 typename Const_Pointer, 294 typename Reference, 295 typename Const_Reference, 296 bool Is_Forward_Iterator, 297 class Allocator> 298 class bin_search_tree_it_ : 299 public PB_DS_TREE_CONST_IT_C_DEC 300 301 { 302 303 public: 304 305 inline bin_search_tree_it_(const Node_Pointer p_nd=NULL)306 bin_search_tree_it_(const Node_Pointer p_nd = NULL) 307 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) 308 { } 309 310 inline bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC & other)311 bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 312 : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) 313 { } 314 315 inline 316 PB_DS_TREE_IT_C_DEC& operator =(const PB_DS_TREE_IT_C_DEC & other)317 operator=(const PB_DS_TREE_IT_C_DEC& other) 318 { 319 base_it_type::m_p_nd = other.m_p_nd; 320 return *this; 321 } 322 323 inline 324 PB_DS_TREE_IT_C_DEC& operator =(const PB_DS_TREE_ODIR_IT_C_DEC & other)325 operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) 326 { 327 base_it_type::m_p_nd = other.m_p_nd; 328 return *this; 329 } 330 331 inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer operator ->() const332 operator->() const 333 { 334 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); 335 return &base_it_type::m_p_nd->m_value; 336 } 337 338 inline typename PB_DS_TREE_CONST_IT_C_DEC::reference operator *() const339 operator*() const 340 { 341 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); 342 return base_it_type::m_p_nd->m_value; 343 } 344 345 inline PB_DS_TREE_IT_C_DEC& operator ++()346 operator++() 347 { 348 PB_DS_TREE_CONST_IT_C_DEC:: operator++(); 349 return *this; 350 } 351 352 inline PB_DS_TREE_IT_C_DEC operator ++(int)353 operator++(int) 354 { 355 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 356 operator++(); 357 return ret_it; 358 } 359 360 inline PB_DS_TREE_IT_C_DEC& operator --()361 operator--() 362 { 363 PB_DS_TREE_CONST_IT_C_DEC:: operator--(); 364 return *this; 365 } 366 367 inline PB_DS_TREE_IT_C_DEC operator --(int)368 operator--(int) 369 { 370 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 371 operator--(); 372 return ret_it; 373 } 374 375 protected: 376 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; 377 }; 378 379 #undef PB_DS_TREE_CONST_IT_C_DEC 380 #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC 381 #undef PB_DS_TREE_IT_C_DEC 382 #undef PB_DS_TREE_ODIR_IT_C_DEC 383 384 } // namespace detail 385 } // namespace pb_ds 386 387 #endif 388