point_iterators.hpp revision 169691
1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file point_iterators.hpp 44169691Skan * Contains an implementation class for bin_search_tree_. 45169691Skan */ 46169691Skan 47169691Skan#ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 48169691Skan#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 49169691Skan 50169691Skan#include <ext/pb_ds/tag_and_trait.hpp> 51169691Skan#include <debug/debug.h> 52169691Skan 53169691Skannamespace pb_ds 54169691Skan{ 55169691Skan namespace detail 56169691Skan { 57169691Skan 58169691Skan#define PB_DS_TREE_CONST_IT_C_DEC \ 59169691Skan bin_search_tree_const_it_< \ 60169691Skan Node_Pointer, \ 61169691Skan Value_Type, \ 62169691Skan Pointer, \ 63169691Skan Const_Pointer, \ 64169691Skan Reference, \ 65169691Skan Const_Reference, \ 66169691Skan Is_Forward_Iterator, \ 67169691Skan Allocator> 68169691Skan 69169691Skan#define PB_DS_TREE_CONST_ODIR_IT_C_DEC \ 70169691Skan bin_search_tree_const_it_< \ 71169691Skan Node_Pointer, \ 72169691Skan Value_Type, \ 73169691Skan Pointer, \ 74169691Skan Const_Pointer, \ 75169691Skan Reference, \ 76169691Skan Const_Reference, \ 77169691Skan !Is_Forward_Iterator, \ 78169691Skan Allocator> 79169691Skan 80169691Skan#define PB_DS_TREE_IT_C_DEC \ 81169691Skan bin_search_tree_it_< \ 82169691Skan Node_Pointer, \ 83169691Skan Value_Type, \ 84169691Skan Pointer, \ 85169691Skan Const_Pointer, \ 86169691Skan Reference, \ 87169691Skan Const_Reference, \ 88169691Skan Is_Forward_Iterator, \ 89169691Skan Allocator> 90169691Skan 91169691Skan#define PB_DS_TREE_ODIR_IT_C_DEC \ 92169691Skan bin_search_tree_it_< \ 93169691Skan Node_Pointer, \ 94169691Skan Value_Type, \ 95169691Skan Pointer, \ 96169691Skan Const_Pointer, \ 97169691Skan Reference, \ 98169691Skan Const_Reference, \ 99169691Skan !Is_Forward_Iterator, \ 100169691Skan Allocator> 101169691Skan 102169691Skan // Const iterator. 103169691Skan template<typename Node_Pointer, 104169691Skan typename Value_Type, 105169691Skan typename Pointer, 106169691Skan typename Const_Pointer, 107169691Skan typename Reference, 108169691Skan typename Const_Reference, 109169691Skan bool Is_Forward_Iterator, 110169691Skan class Allocator> 111169691Skan class bin_search_tree_const_it_ 112169691Skan { 113169691Skan 114169691Skan public: 115169691Skan 116169691Skan typedef std::bidirectional_iterator_tag iterator_category; 117169691Skan 118169691Skan typedef typename Allocator::difference_type difference_type; 119169691Skan 120169691Skan typedef Value_Type value_type; 121169691Skan 122169691Skan typedef Pointer pointer; 123169691Skan 124169691Skan typedef Const_Pointer const_pointer; 125169691Skan 126169691Skan typedef Reference reference; 127169691Skan 128169691Skan typedef Const_Reference const_reference; 129169691Skan 130169691Skan public: 131169691Skan 132169691Skan inline 133169691Skan bin_search_tree_const_it_(const Node_Pointer p_nd = NULL) 134169691Skan : m_p_nd(const_cast<Node_Pointer>(p_nd)) 135169691Skan { } 136169691Skan 137169691Skan inline 138169691Skan bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 139169691Skan : m_p_nd(other.m_p_nd) 140169691Skan { } 141169691Skan 142169691Skan inline 143169691Skan PB_DS_TREE_CONST_IT_C_DEC& 144169691Skan operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) 145169691Skan { 146169691Skan m_p_nd = other.m_p_nd; 147169691Skan return *this; 148169691Skan } 149169691Skan 150169691Skan inline 151169691Skan PB_DS_TREE_CONST_IT_C_DEC& 152169691Skan operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 153169691Skan { 154169691Skan m_p_nd = other.m_p_nd; 155169691Skan return *this; 156169691Skan } 157169691Skan 158169691Skan inline const_pointer 159169691Skan operator->() const 160169691Skan { 161169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 162169691Skan return &m_p_nd->m_value; 163169691Skan } 164169691Skan 165169691Skan inline const_reference 166169691Skan operator*() const 167169691Skan { 168169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 169169691Skan return m_p_nd->m_value; 170169691Skan } 171169691Skan 172169691Skan inline bool 173169691Skan operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 174169691Skan { return m_p_nd == other.m_p_nd; } 175169691Skan 176169691Skan inline bool 177169691Skan operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const 178169691Skan { return m_p_nd == other.m_p_nd; } 179169691Skan 180169691Skan inline bool 181169691Skan operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 182169691Skan { return m_p_nd != other.m_p_nd; } 183169691Skan 184169691Skan inline bool 185169691Skan operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const 186169691Skan { return m_p_nd != other.m_p_nd; } 187169691Skan 188169691Skan inline PB_DS_TREE_CONST_IT_C_DEC& 189169691Skan operator++() 190169691Skan { 191169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); 192169691Skan inc(integral_constant<int,Is_Forward_Iterator>()); 193169691Skan return *this; 194169691Skan } 195169691Skan 196169691Skan inline PB_DS_TREE_CONST_IT_C_DEC 197169691Skan operator++(int) 198169691Skan { 199169691Skan PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 200169691Skan operator++(); 201169691Skan return ret_it; 202169691Skan } 203169691Skan 204169691Skan inline PB_DS_TREE_CONST_IT_C_DEC& 205169691Skan operator--() 206169691Skan { 207169691Skan dec(integral_constant<int,Is_Forward_Iterator>()); 208169691Skan return *this; 209169691Skan } 210169691Skan 211169691Skan inline PB_DS_TREE_CONST_IT_C_DEC 212169691Skan operator--(int) 213169691Skan { 214169691Skan PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 215169691Skan operator--(); 216169691Skan return ret_it; 217169691Skan } 218169691Skan 219169691Skan protected: 220169691Skan inline void 221169691Skan inc(false_type) 222169691Skan { dec(true_type()); } 223169691Skan 224169691Skan void 225169691Skan inc(true_type) 226169691Skan { 227169691Skan if (m_p_nd->special()&& 228169691Skan m_p_nd->m_p_parent->m_p_parent == m_p_nd) 229169691Skan { 230169691Skan m_p_nd = m_p_nd->m_p_left; 231169691Skan return; 232169691Skan } 233169691Skan 234169691Skan if (m_p_nd->m_p_right != NULL) 235169691Skan { 236169691Skan m_p_nd = m_p_nd->m_p_right; 237169691Skan while (m_p_nd->m_p_left != NULL) 238169691Skan m_p_nd = m_p_nd->m_p_left; 239169691Skan return; 240169691Skan } 241169691Skan 242169691Skan Node_Pointer p_y = m_p_nd->m_p_parent; 243169691Skan while (m_p_nd == p_y->m_p_right) 244169691Skan { 245169691Skan m_p_nd = p_y; 246169691Skan p_y = p_y->m_p_parent; 247169691Skan } 248169691Skan 249169691Skan if (m_p_nd->m_p_right != p_y) 250169691Skan m_p_nd = p_y; 251169691Skan } 252169691Skan 253169691Skan inline void 254169691Skan dec(false_type) 255169691Skan { inc(true_type()); } 256169691Skan 257169691Skan void 258169691Skan dec(true_type) 259169691Skan { 260169691Skan if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) 261169691Skan { 262169691Skan m_p_nd = m_p_nd->m_p_right; 263169691Skan return; 264169691Skan } 265169691Skan 266169691Skan if (m_p_nd->m_p_left != NULL) 267169691Skan { 268169691Skan Node_Pointer p_y = m_p_nd->m_p_left; 269169691Skan while (p_y->m_p_right != NULL) 270169691Skan p_y = p_y->m_p_right; 271169691Skan m_p_nd = p_y; 272169691Skan return; 273169691Skan } 274169691Skan 275169691Skan Node_Pointer p_y = m_p_nd->m_p_parent; 276169691Skan while (m_p_nd == p_y->m_p_left) 277169691Skan { 278169691Skan m_p_nd = p_y; 279169691Skan p_y = p_y->m_p_parent; 280169691Skan } 281169691Skan if (m_p_nd->m_p_left != p_y) 282169691Skan m_p_nd = p_y; 283169691Skan } 284169691Skan 285169691Skan public: 286169691Skan Node_Pointer m_p_nd; 287169691Skan }; 288169691Skan 289169691Skan // Iterator. 290169691Skan template<typename Node_Pointer, 291169691Skan typename Value_Type, 292169691Skan typename Pointer, 293169691Skan typename Const_Pointer, 294169691Skan typename Reference, 295169691Skan typename Const_Reference, 296169691Skan bool Is_Forward_Iterator, 297169691Skan class Allocator> 298169691Skan class bin_search_tree_it_ : 299169691Skan public PB_DS_TREE_CONST_IT_C_DEC 300169691Skan 301169691Skan { 302169691Skan 303169691Skan public: 304169691Skan 305169691Skan inline 306169691Skan bin_search_tree_it_(const Node_Pointer p_nd = NULL) 307169691Skan : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) 308169691Skan { } 309169691Skan 310169691Skan inline 311169691Skan bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 312169691Skan : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) 313169691Skan { } 314169691Skan 315169691Skan inline 316169691Skan PB_DS_TREE_IT_C_DEC& 317169691Skan operator=(const PB_DS_TREE_IT_C_DEC& other) 318169691Skan { 319169691Skan base_it_type::m_p_nd = other.m_p_nd; 320169691Skan return *this; 321169691Skan } 322169691Skan 323169691Skan inline 324169691Skan PB_DS_TREE_IT_C_DEC& 325169691Skan operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) 326169691Skan { 327169691Skan base_it_type::m_p_nd = other.m_p_nd; 328169691Skan return *this; 329169691Skan } 330169691Skan 331169691Skan inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer 332169691Skan operator->() const 333169691Skan { 334169691Skan _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); 335169691Skan return &base_it_type::m_p_nd->m_value; 336169691Skan } 337169691Skan 338169691Skan inline typename PB_DS_TREE_CONST_IT_C_DEC::reference 339169691Skan operator*() const 340169691Skan { 341169691Skan _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); 342169691Skan return base_it_type::m_p_nd->m_value; 343169691Skan } 344169691Skan 345169691Skan inline PB_DS_TREE_IT_C_DEC& 346169691Skan operator++() 347169691Skan { 348169691Skan PB_DS_TREE_CONST_IT_C_DEC:: operator++(); 349169691Skan return *this; 350169691Skan } 351169691Skan 352169691Skan inline PB_DS_TREE_IT_C_DEC 353169691Skan operator++(int) 354169691Skan { 355169691Skan PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 356169691Skan operator++(); 357169691Skan return ret_it; 358169691Skan } 359169691Skan 360169691Skan inline PB_DS_TREE_IT_C_DEC& 361169691Skan operator--() 362169691Skan { 363169691Skan PB_DS_TREE_CONST_IT_C_DEC:: operator--(); 364169691Skan return *this; 365169691Skan } 366169691Skan 367169691Skan inline PB_DS_TREE_IT_C_DEC 368169691Skan operator--(int) 369169691Skan { 370169691Skan PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 371169691Skan operator--(); 372169691Skan return ret_it; 373169691Skan } 374169691Skan 375169691Skan protected: 376169691Skan typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; 377169691Skan }; 378169691Skan 379169691Skan#undef PB_DS_TREE_CONST_IT_C_DEC 380169691Skan#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC 381169691Skan#undef PB_DS_TREE_IT_C_DEC 382169691Skan#undef PB_DS_TREE_ODIR_IT_C_DEC 383169691Skan 384169691Skan } // namespace detail 385169691Skan} // namespace pb_ds 386169691Skan 387169691Skan#endif 388