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 53namespace 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 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 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& 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& 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 159 operator->() const 160 { 161 _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 162 return &m_p_nd->m_value; 163 } 164 165 inline const_reference 166 operator*() const 167 { 168 _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 169 return m_p_nd->m_value; 170 } 171 172 inline bool 173 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 174 { return m_p_nd == other.m_p_nd; } 175 176 inline bool 177 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 181 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 182 { return m_p_nd != other.m_p_nd; } 183 184 inline bool 185 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& 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 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& 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 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 221 inc(false_type) 222 { dec(true_type()); } 223 224 void 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 254 dec(false_type) 255 { inc(true_type()); } 256 257 void 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 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 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& 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& 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 332 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 339 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& 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 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& 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 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