00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005 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 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00031 00032 // Permission to use, copy, modify, sell, and distribute this software 00033 // is hereby granted without fee, provided that the above copyright 00034 // notice appears in all copies, and that both that copyright notice and 00035 // this permission notice appear in supporting documentation. None of 00036 // the above authors, nor IBM Haifa Research Laboratories, make any 00037 // representation about the suitability of this software for any 00038 // purpose. It is provided "as is" without express or implied warranty. 00039 00045 #define PB_ASSOC_CONST_IT_C_DEC \ 00046 const_it_< \ 00047 Is_Forward_Iterator> 00048 00049 #define PB_ASSOC_CONST_ODIR_IT_C_DEC \ 00050 const_it_< \ 00051 !Is_Forward_Iterator> 00052 00053 #define PB_ASSOC_IT_C_DEC \ 00054 it_< \ 00055 Is_Forward_Iterator> 00056 00057 #define PB_ASSOC_ODIR_IT_C_DEC \ 00058 it_< \ 00059 !Is_Forward_Iterator> 00060 00061 template<bool Is_Forward_Iterator> 00062 class const_it_ 00063 { 00064 00065 public: 00066 00067 typedef std::bidirectional_iterator_tag iterator_category; 00068 00069 typedef typename Allocator::difference_type difference_type; 00070 00071 typedef mapped_value_type value_type; 00072 00073 typedef mapped_pointer pointer; 00074 00075 typedef const_mapped_pointer const_pointer; 00076 00077 typedef mapped_reference reference; 00078 00079 typedef const_mapped_reference const_reference; 00080 00081 public: 00082 00083 inline 00084 const_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd)) 00085 { } 00086 00087 inline 00088 const_it_(const PB_ASSOC_CONST_ODIR_IT_C_DEC& 00089 r_other) 00090 00091 : m_p_nd(r_other.m_p_nd) 00092 { } 00093 00094 inline 00095 PB_ASSOC_CONST_IT_C_DEC& 00096 operator=(const PB_ASSOC_CONST_IT_C_DEC& 00097 r_other) 00098 { 00099 m_p_nd = r_other.m_p_nd; 00100 00101 return (*this); 00102 } 00103 00104 inline 00105 PB_ASSOC_CONST_IT_C_DEC& 00106 operator=(const PB_ASSOC_CONST_ODIR_IT_C_DEC& 00107 r_other) 00108 { 00109 m_p_nd = r_other.m_p_nd; 00110 00111 return (*this); 00112 } 00113 00114 inline const_pointer 00115 operator->() const 00116 { 00117 PB_ASSOC_DBG_ASSERT(m_p_nd != NULL); 00118 00119 return (&m_p_nd->m_value); 00120 } 00121 00122 inline const_reference 00123 operator*() const 00124 { 00125 PB_ASSOC_DBG_ASSERT(m_p_nd != NULL); 00126 00127 return (m_p_nd->m_value); 00128 } 00129 00130 inline bool 00131 operator==(const PB_ASSOC_CONST_IT_C_DEC 00132 &r_other) const 00133 { 00134 return (m_p_nd == r_other.m_p_nd); 00135 } 00136 00137 inline bool 00138 operator==(const PB_ASSOC_CONST_ODIR_IT_C_DEC 00139 &r_other) const 00140 { 00141 return (m_p_nd == r_other.m_p_nd); 00142 } 00143 00144 inline bool 00145 operator!=(const PB_ASSOC_CONST_IT_C_DEC& 00146 r_other) const 00147 { 00148 return (m_p_nd != r_other.m_p_nd); 00149 } 00150 00151 inline bool 00152 operator!=(const PB_ASSOC_CONST_ODIR_IT_C_DEC& 00153 r_other) const 00154 { 00155 return (m_p_nd != r_other.m_p_nd); 00156 } 00157 00158 inline PB_ASSOC_CONST_IT_C_DEC& 00159 operator++() 00160 { 00161 PB_ASSOC_DBG_ASSERT(m_p_nd != NULL); 00162 00163 inc(int_to_type<Is_Forward_Iterator>()); 00164 00165 return (*this); 00166 } 00167 00168 inline PB_ASSOC_CONST_IT_C_DEC 00169 operator++(int) 00170 { 00171 PB_ASSOC_CONST_IT_C_DEC 00172 ret_it(m_p_nd); 00173 00174 operator++(); 00175 00176 return (ret_it); 00177 } 00178 00179 inline PB_ASSOC_CONST_IT_C_DEC& 00180 operator--() 00181 { 00182 dec(int_to_type<Is_Forward_Iterator>()); 00183 00184 return (*this); 00185 } 00186 00187 inline PB_ASSOC_CONST_IT_C_DEC 00188 operator--(int) 00189 { 00190 PB_ASSOC_CONST_IT_C_DEC 00191 ret_it(m_p_nd); 00192 00193 operator--(); 00194 00195 return (ret_it); 00196 } 00197 00198 protected: 00199 inline void 00200 inc(int_to_type<false>) 00201 { 00202 dec(int_to_type<true>()); 00203 } 00204 00205 void 00206 inc(int_to_type<true>) 00207 { 00208 if (m_p_nd->m_p_right != NULL) 00209 { 00210 m_p_nd = m_p_nd->m_p_right; 00211 00212 while (m_p_nd->m_p_left != NULL) 00213 m_p_nd = m_p_nd->m_p_left; 00214 00215 return; 00216 } 00217 00218 node_pointer p_y = m_p_nd->m_p_parent; 00219 00220 while (m_p_nd == p_y->m_p_right) 00221 { 00222 m_p_nd = p_y; 00223 00224 p_y = p_y->m_p_parent; 00225 } 00226 00227 if (m_p_nd->m_p_right != p_y) 00228 m_p_nd = p_y; 00229 } 00230 00231 inline void 00232 dec(int_to_type<false>) 00233 { 00234 inc(int_to_type<true>()); 00235 } 00236 00237 void 00238 dec(int_to_type<true>) 00239 { 00240 if (m_p_nd->special_dec_check()&& 00241 m_p_nd->m_p_parent->m_p_parent == m_p_nd) 00242 { 00243 m_p_nd = m_p_nd->m_p_right; 00244 00245 return; 00246 } 00247 00248 if (m_p_nd->m_p_left != NULL) 00249 { 00250 node_pointer p_y = m_p_nd->m_p_left; 00251 00252 while (p_y->m_p_right != NULL) 00253 p_y = p_y->m_p_right; 00254 00255 m_p_nd = p_y; 00256 00257 return; 00258 } 00259 00260 node_pointer p_y = m_p_nd->m_p_parent; 00261 00262 while (m_p_nd == p_y->m_p_left) 00263 { 00264 m_p_nd = p_y; 00265 00266 p_y = p_y->m_p_parent; 00267 } 00268 00269 /* 00270 * This seems to correct an apparent bug in the SGI STL 00271 * implementation. */ 00272 if (m_p_nd->m_p_left != p_y) 00273 m_p_nd = p_y; 00274 } 00275 00276 friend class PB_ASSOC_CLASS_C_DEC; 00277 00278 public: 00279 node_pointer m_p_nd; 00280 }; 00281 00282 template<bool Is_Forward_Iterator> 00283 class it_ : 00284 public PB_ASSOC_CONST_IT_C_DEC 00285 00286 { 00287 00288 public: 00289 00290 inline 00291 it_(const node_pointer p_nd = NULL) : PB_ASSOC_CONST_IT_C_DEC((node_pointer)p_nd) 00292 { } 00293 00294 inline 00295 it_(const PB_ASSOC_ODIR_IT_C_DEC& 00296 r_other) 00297 00298 : PB_ASSOC_CONST_IT_C_DEC( 00299 r_other.m_p_nd) 00300 { } 00301 00302 inline 00303 PB_ASSOC_IT_C_DEC& 00304 operator=(const PB_ASSOC_IT_C_DEC& 00305 r_other) 00306 { 00307 my_base_it::m_p_nd = r_other.m_p_nd; 00308 00309 return (*this); 00310 } 00311 00312 inline 00313 PB_ASSOC_IT_C_DEC& 00314 operator=(const PB_ASSOC_ODIR_IT_C_DEC& 00315 r_other) 00316 { 00317 my_base_it::m_p_nd = r_other.m_p_nd; 00318 00319 return (*this); 00320 } 00321 00322 inline pointer 00323 operator->() 00324 { 00325 PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL); 00326 00327 return (&my_base_it::m_p_nd->m_value); 00328 } 00329 00330 inline reference 00331 operator*() 00332 { 00333 PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL); 00334 00335 return (my_base_it::m_p_nd->m_value); 00336 } 00337 00338 inline PB_ASSOC_IT_C_DEC& 00339 operator++() 00340 { 00341 PB_ASSOC_CONST_IT_C_DEC:: 00342 operator++(); 00343 00344 return (*this); 00345 } 00346 00347 inline PB_ASSOC_IT_C_DEC 00348 operator++(int) 00349 { 00350 PB_ASSOC_IT_C_DEC 00351 ret_it(my_base_it::m_p_nd); 00352 00353 operator++(); 00354 00355 return (ret_it); 00356 } 00357 00358 inline PB_ASSOC_IT_C_DEC& 00359 operator--() 00360 { 00361 PB_ASSOC_CONST_IT_C_DEC:: 00362 operator--(); 00363 00364 return (*this); 00365 } 00366 00367 inline PB_ASSOC_IT_C_DEC 00368 operator--(int) 00369 { 00370 PB_ASSOC_IT_C_DEC 00371 ret_it(my_base_it::m_p_nd); 00372 00373 operator--(); 00374 00375 return (ret_it); 00376 } 00377 00378 protected: 00379 typedef PB_ASSOC_CONST_IT_C_DEC my_base_it; 00380 00381 friend class PB_ASSOC_CLASS_C_DEC; 00382 }; 00383 00384 #undef PB_ASSOC_CONST_IT_C_DEC 00385 00386 #undef PB_ASSOC_CONST_ODIR_IT_C_DEC 00387 00388 #undef PB_ASSOC_IT_C_DEC 00389 00390 #undef PB_ASSOC_ODIR_IT_C_DEC 00391