libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file bin_search_tree_/point_iterators.hpp 00038 * Contains an implementation class for bin_search_tree_. 00039 */ 00040 00041 #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 00042 #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP 00043 00044 #include <ext/pb_ds/tag_and_trait.hpp> 00045 #include <debug/debug.h> 00046 00047 namespace __gnu_pbds 00048 { 00049 namespace detail 00050 { 00051 00052 #define PB_DS_TREE_CONST_IT_C_DEC \ 00053 bin_search_tree_const_it_< \ 00054 Node_Pointer, \ 00055 Value_Type, \ 00056 Pointer, \ 00057 Const_Pointer, \ 00058 Reference, \ 00059 Const_Reference, \ 00060 Is_Forward_Iterator, \ 00061 _Alloc> 00062 00063 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC \ 00064 bin_search_tree_const_it_< \ 00065 Node_Pointer, \ 00066 Value_Type, \ 00067 Pointer, \ 00068 Const_Pointer, \ 00069 Reference, \ 00070 Const_Reference, \ 00071 !Is_Forward_Iterator, \ 00072 _Alloc> 00073 00074 #define PB_DS_TREE_IT_C_DEC \ 00075 bin_search_tree_it_< \ 00076 Node_Pointer, \ 00077 Value_Type, \ 00078 Pointer, \ 00079 Const_Pointer, \ 00080 Reference, \ 00081 Const_Reference, \ 00082 Is_Forward_Iterator, \ 00083 _Alloc> 00084 00085 #define PB_DS_TREE_ODIR_IT_C_DEC \ 00086 bin_search_tree_it_< \ 00087 Node_Pointer, \ 00088 Value_Type, \ 00089 Pointer, \ 00090 Const_Pointer, \ 00091 Reference, \ 00092 Const_Reference, \ 00093 !Is_Forward_Iterator, \ 00094 _Alloc> 00095 00096 /// Const iterator. 00097 template<typename Node_Pointer, 00098 typename Value_Type, 00099 typename Pointer, 00100 typename Const_Pointer, 00101 typename Reference, 00102 typename Const_Reference, 00103 bool Is_Forward_Iterator, 00104 typename _Alloc> 00105 class bin_search_tree_const_it_ 00106 { 00107 public: 00108 typedef std::bidirectional_iterator_tag iterator_category; 00109 typedef typename _Alloc::difference_type difference_type; 00110 typedef Value_Type value_type; 00111 typedef Pointer pointer; 00112 typedef Const_Pointer const_pointer; 00113 typedef Reference reference; 00114 typedef Const_Reference const_reference; 00115 00116 inline 00117 bin_search_tree_const_it_(const Node_Pointer p_nd = 0) 00118 : m_p_nd(const_cast<Node_Pointer>(p_nd)) 00119 { } 00120 00121 inline 00122 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 00123 : m_p_nd(other.m_p_nd) 00124 { } 00125 00126 inline 00127 PB_DS_TREE_CONST_IT_C_DEC& 00128 operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) 00129 { 00130 m_p_nd = other.m_p_nd; 00131 return *this; 00132 } 00133 00134 inline 00135 PB_DS_TREE_CONST_IT_C_DEC& 00136 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) 00137 { 00138 m_p_nd = other.m_p_nd; 00139 return *this; 00140 } 00141 00142 inline const_pointer 00143 operator->() const 00144 { 00145 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 00146 return &m_p_nd->m_value; 00147 } 00148 00149 inline const_reference 00150 operator*() const 00151 { 00152 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 00153 return m_p_nd->m_value; 00154 } 00155 00156 inline bool 00157 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const 00158 { return m_p_nd == other.m_p_nd; } 00159 00160 inline bool 00161 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const 00162 { return m_p_nd == other.m_p_nd; } 00163 00164 inline bool 00165 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const 00166 { return m_p_nd != other.m_p_nd; } 00167 00168 inline bool 00169 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const 00170 { return m_p_nd != other.m_p_nd; } 00171 00172 inline PB_DS_TREE_CONST_IT_C_DEC& 00173 operator++() 00174 { 00175 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0); 00176 inc(integral_constant<int,Is_Forward_Iterator>()); 00177 return *this; 00178 } 00179 00180 inline PB_DS_TREE_CONST_IT_C_DEC 00181 operator++(int) 00182 { 00183 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 00184 operator++(); 00185 return ret_it; 00186 } 00187 00188 inline PB_DS_TREE_CONST_IT_C_DEC& 00189 operator--() 00190 { 00191 dec(integral_constant<int,Is_Forward_Iterator>()); 00192 return *this; 00193 } 00194 00195 inline PB_DS_TREE_CONST_IT_C_DEC 00196 operator--(int) 00197 { 00198 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); 00199 operator--(); 00200 return ret_it; 00201 } 00202 00203 protected: 00204 inline void 00205 inc(false_type) 00206 { dec(true_type()); } 00207 00208 void 00209 inc(true_type) 00210 { 00211 if (m_p_nd->special()&& 00212 m_p_nd->m_p_parent->m_p_parent == m_p_nd) 00213 { 00214 m_p_nd = m_p_nd->m_p_left; 00215 return; 00216 } 00217 00218 if (m_p_nd->m_p_right != 0) 00219 { 00220 m_p_nd = m_p_nd->m_p_right; 00221 while (m_p_nd->m_p_left != 0) 00222 m_p_nd = m_p_nd->m_p_left; 00223 return; 00224 } 00225 00226 Node_Pointer p_y = m_p_nd->m_p_parent; 00227 while (m_p_nd == p_y->m_p_right) 00228 { 00229 m_p_nd = p_y; 00230 p_y = p_y->m_p_parent; 00231 } 00232 00233 if (m_p_nd->m_p_right != p_y) 00234 m_p_nd = p_y; 00235 } 00236 00237 inline void 00238 dec(false_type) 00239 { inc(true_type()); } 00240 00241 void 00242 dec(true_type) 00243 { 00244 if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) 00245 { 00246 m_p_nd = m_p_nd->m_p_right; 00247 return; 00248 } 00249 00250 if (m_p_nd->m_p_left != 0) 00251 { 00252 Node_Pointer p_y = m_p_nd->m_p_left; 00253 while (p_y->m_p_right != 0) 00254 p_y = p_y->m_p_right; 00255 m_p_nd = p_y; 00256 return; 00257 } 00258 00259 Node_Pointer p_y = m_p_nd->m_p_parent; 00260 while (m_p_nd == p_y->m_p_left) 00261 { 00262 m_p_nd = p_y; 00263 p_y = p_y->m_p_parent; 00264 } 00265 if (m_p_nd->m_p_left != p_y) 00266 m_p_nd = p_y; 00267 } 00268 00269 public: 00270 Node_Pointer m_p_nd; 00271 }; 00272 00273 /// Iterator. 00274 template<typename Node_Pointer, 00275 typename Value_Type, 00276 typename Pointer, 00277 typename Const_Pointer, 00278 typename Reference, 00279 typename Const_Reference, 00280 bool Is_Forward_Iterator, 00281 typename _Alloc> 00282 class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC 00283 { 00284 public: 00285 inline 00286 bin_search_tree_it_(const Node_Pointer p_nd = 0) 00287 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) 00288 { } 00289 00290 inline 00291 bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) 00292 : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) 00293 { } 00294 00295 inline 00296 PB_DS_TREE_IT_C_DEC& 00297 operator=(const PB_DS_TREE_IT_C_DEC& other) 00298 { 00299 base_it_type::m_p_nd = other.m_p_nd; 00300 return *this; 00301 } 00302 00303 inline 00304 PB_DS_TREE_IT_C_DEC& 00305 operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) 00306 { 00307 base_it_type::m_p_nd = other.m_p_nd; 00308 return *this; 00309 } 00310 00311 inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer 00312 operator->() const 00313 { 00314 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 00315 return &base_it_type::m_p_nd->m_value; 00316 } 00317 00318 inline typename PB_DS_TREE_CONST_IT_C_DEC::reference 00319 operator*() const 00320 { 00321 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0); 00322 return base_it_type::m_p_nd->m_value; 00323 } 00324 00325 inline PB_DS_TREE_IT_C_DEC& 00326 operator++() 00327 { 00328 PB_DS_TREE_CONST_IT_C_DEC:: operator++(); 00329 return *this; 00330 } 00331 00332 inline PB_DS_TREE_IT_C_DEC 00333 operator++(int) 00334 { 00335 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 00336 operator++(); 00337 return ret_it; 00338 } 00339 00340 inline PB_DS_TREE_IT_C_DEC& 00341 operator--() 00342 { 00343 PB_DS_TREE_CONST_IT_C_DEC:: operator--(); 00344 return *this; 00345 } 00346 00347 inline PB_DS_TREE_IT_C_DEC 00348 operator--(int) 00349 { 00350 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); 00351 operator--(); 00352 return ret_it; 00353 } 00354 00355 protected: 00356 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; 00357 }; 00358 00359 #undef PB_DS_TREE_CONST_IT_C_DEC 00360 #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC 00361 #undef PB_DS_TREE_IT_C_DEC 00362 #undef PB_DS_TREE_ODIR_IT_C_DEC 00363 00364 } // namespace detail 00365 } // namespace __gnu_pbds 00366 00367 #endif