1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Permission to use, copy, modify, distribute and sell this software 7 * and its documentation for any purpose is hereby granted without fee, 8 * provided that the above copyright notice appear in all copies and 9 * that both that copyright notice and this permission notice appear 10 * in supporting documentation. Hewlett-Packard Company makes no 11 * representations about the suitability of this software for any 12 * purpose. It is provided "as is" without express or implied warranty. 13 * 14 * 15 * Copyright (c) 1996-1998 16 * Silicon Graphics Computer Systems, Inc. 17 * 18 * Permission to use, copy, modify, distribute and sell this software 19 * and its documentation for any purpose is hereby granted without fee, 20 * provided that the above copyright notice appear in all copies and 21 * that both that copyright notice and this permission notice appear 22 * in supporting documentation. Silicon Graphics makes no 23 * representations about the suitability of this software for any 24 * purpose. It is provided "as is" without express or implied warranty. 25 */ 26 27 /* NOTE: This is an internal header file, included by other STL headers. 28 * You should not attempt to use it directly. 29 */ 30 31 #ifndef __SGI_STL_INTERNAL_ITERATOR_BASE_H 32 #define __SGI_STL_INTERNAL_ITERATOR_BASE_H 33 34 // This file contains all of the general iterator-related utilities. 35 // The internal file stl_iterator.h contains predefined iterators, 36 // such as front_insert_iterator and istream_iterator. 37 38 #include <concept_checks.h> 39 40 __STL_BEGIN_NAMESPACE 41 42 struct input_iterator_tag {}; 43 struct output_iterator_tag {}; 44 struct forward_iterator_tag : public input_iterator_tag {}; 45 struct bidirectional_iterator_tag : public forward_iterator_tag {}; 46 struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 47 48 // The base classes input_iterator, output_iterator, forward_iterator, 49 // bidirectional_iterator, and random_access_iterator are not part of 50 // the C++ standard. (They have been replaced by struct iterator.) 51 // They are included for backward compatibility with the HP STL. 52 53 template <class _Tp, class _Distance> struct input_iterator { 54 typedef input_iterator_tag iterator_category; 55 typedef _Tp value_type; 56 typedef _Distance difference_type; 57 typedef _Tp* pointer; 58 typedef _Tp& reference; 59 }; 60 61 struct output_iterator { 62 typedef output_iterator_tag iterator_category; 63 typedef void value_type; 64 typedef void difference_type; 65 typedef void pointer; 66 typedef void reference; 67 }; 68 69 template <class _Tp, class _Distance> struct forward_iterator { 70 typedef forward_iterator_tag iterator_category; 71 typedef _Tp value_type; 72 typedef _Distance difference_type; 73 typedef _Tp* pointer; 74 typedef _Tp& reference; 75 }; 76 77 78 template <class _Tp, class _Distance> struct bidirectional_iterator { 79 typedef bidirectional_iterator_tag iterator_category; 80 typedef _Tp value_type; 81 typedef _Distance difference_type; 82 typedef _Tp* pointer; 83 typedef _Tp& reference; 84 }; 85 86 template <class _Tp, class _Distance> struct random_access_iterator { 87 typedef random_access_iterator_tag iterator_category; 88 typedef _Tp value_type; 89 typedef _Distance difference_type; 90 typedef _Tp* pointer; 91 typedef _Tp& reference; 92 }; 93 94 #ifdef __STL_USE_NAMESPACES 95 template <class _Category, class _Tp, class _Distance = ptrdiff_t, 96 class _Pointer = _Tp*, class _Reference = _Tp&> 97 struct iterator { 98 typedef _Category iterator_category; 99 typedef _Tp value_type; 100 typedef _Distance difference_type; 101 typedef _Pointer pointer; 102 typedef _Reference reference; 103 }; 104 #endif /* __STL_USE_NAMESPACES */ 105 106 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 107 108 template <class _Iterator> 109 struct iterator_traits { 110 typedef typename _Iterator::iterator_category iterator_category; 111 typedef typename _Iterator::value_type value_type; 112 typedef typename _Iterator::difference_type difference_type; 113 typedef typename _Iterator::pointer pointer; 114 typedef typename _Iterator::reference reference; 115 }; 116 117 template <class _Tp> 118 struct iterator_traits<_Tp*> { 119 typedef random_access_iterator_tag iterator_category; 120 typedef _Tp value_type; 121 typedef ptrdiff_t difference_type; 122 typedef _Tp* pointer; 123 typedef _Tp& reference; 124 }; 125 126 template <class _Tp> 127 struct iterator_traits<const _Tp*> { 128 typedef random_access_iterator_tag iterator_category; 129 typedef _Tp value_type; 130 typedef ptrdiff_t difference_type; 131 typedef const _Tp* pointer; 132 typedef const _Tp& reference; 133 }; 134 135 // The overloaded functions iterator_category, distance_type, and 136 // value_type are not part of the C++ standard. (They have been 137 // replaced by struct iterator_traits.) They are included for 138 // backward compatibility with the HP STL. 139 140 // We introduce internal names for these functions. 141 142 template <class _Iter> 143 inline typename iterator_traits<_Iter>::iterator_category 144 __iterator_category(const _Iter&) 145 { 146 typedef typename iterator_traits<_Iter>::iterator_category _Category; 147 return _Category(); 148 } 149 150 template <class _Iter> 151 inline typename iterator_traits<_Iter>::difference_type* 152 __distance_type(const _Iter&) 153 { 154 return static_cast<typename iterator_traits<_Iter>::difference_type*>(0); 155 } 156 157 template <class _Iter> 158 inline typename iterator_traits<_Iter>::value_type* 159 __value_type(const _Iter&) 160 { 161 return static_cast<typename iterator_traits<_Iter>::value_type*>(0); 162 } 163 164 template <class _Iter> 165 inline typename iterator_traits<_Iter>::iterator_category 166 iterator_category(const _Iter& __i) { return __iterator_category(__i); } 167 168 169 template <class _Iter> 170 inline typename iterator_traits<_Iter>::difference_type* 171 distance_type(const _Iter& __i) { return __distance_type(__i); } 172 173 template <class _Iter> 174 inline typename iterator_traits<_Iter>::value_type* 175 value_type(const _Iter& __i) { return __value_type(__i); } 176 177 #define __ITERATOR_CATEGORY(__i) __iterator_category(__i) 178 #define __DISTANCE_TYPE(__i) __distance_type(__i) 179 #define __VALUE_TYPE(__i) __value_type(__i) 180 181 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 182 183 template <class _Tp, class _Distance> 184 inline input_iterator_tag 185 iterator_category(const input_iterator<_Tp, _Distance>&) 186 { return input_iterator_tag(); } 187 188 inline output_iterator_tag iterator_category(const output_iterator&) 189 { return output_iterator_tag(); } 190 191 template <class _Tp, class _Distance> 192 inline forward_iterator_tag 193 iterator_category(const forward_iterator<_Tp, _Distance>&) 194 { return forward_iterator_tag(); } 195 196 template <class _Tp, class _Distance> 197 inline bidirectional_iterator_tag 198 iterator_category(const bidirectional_iterator<_Tp, _Distance>&) 199 { return bidirectional_iterator_tag(); } 200 201 template <class _Tp, class _Distance> 202 inline random_access_iterator_tag 203 iterator_category(const random_access_iterator<_Tp, _Distance>&) 204 { return random_access_iterator_tag(); } 205 206 template <class _Tp> 207 inline random_access_iterator_tag iterator_category(const _Tp*) 208 { return random_access_iterator_tag(); } 209 210 template <class _Tp, class _Distance> 211 inline _Tp* value_type(const input_iterator<_Tp, _Distance>&) 212 { return (_Tp*)(0); } 213 214 template <class _Tp, class _Distance> 215 inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&) 216 { return (_Tp*)(0); } 217 218 template <class _Tp, class _Distance> 219 inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&) 220 { return (_Tp*)(0); } 221 222 template <class _Tp, class _Distance> 223 inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&) 224 { return (_Tp*)(0); } 225 226 template <class _Tp> 227 inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); } 228 229 template <class _Tp, class _Distance> 230 inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&) 231 { 232 return (_Distance*)(0); 233 } 234 235 template <class _Tp, class _Distance> 236 inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&) 237 { 238 return (_Distance*)(0); 239 } 240 241 template <class _Tp, class _Distance> 242 inline _Distance* 243 distance_type(const bidirectional_iterator<_Tp, _Distance>&) 244 { 245 return (_Distance*)(0); 246 } 247 248 template <class _Tp, class _Distance> 249 inline _Distance* 250 distance_type(const random_access_iterator<_Tp, _Distance>&) 251 { 252 return (_Distance*)(0); 253 } 254 255 template <class _Tp> 256 inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); } 257 258 // Without partial specialization we can't use iterator_traits, so 259 // we must keep the old iterator query functions around. 260 261 #define __ITERATOR_CATEGORY(__i) iterator_category(__i) 262 #define __DISTANCE_TYPE(__i) distance_type(__i) 263 #define __VALUE_TYPE(__i) value_type(__i) 264 265 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 266 267 template <class _InputIterator, class _Distance> 268 inline void __distance(_InputIterator __first, _InputIterator __last, 269 _Distance& __n, input_iterator_tag) 270 { 271 while (__first != __last) { ++__first; ++__n; } 272 } 273 274 template <class _RandomAccessIterator, class _Distance> 275 inline void __distance(_RandomAccessIterator __first, 276 _RandomAccessIterator __last, 277 _Distance& __n, random_access_iterator_tag) 278 { 279 __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); 280 __n += __last - __first; 281 } 282 283 template <class _InputIterator, class _Distance> 284 inline void distance(_InputIterator __first, 285 _InputIterator __last, _Distance& __n) 286 { 287 __STL_REQUIRES(_InputIterator, _InputIterator); 288 __distance(__first, __last, __n, iterator_category(__first)); 289 } 290 291 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 292 293 template <class _InputIterator> 294 inline typename iterator_traits<_InputIterator>::difference_type 295 __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag) 296 { 297 typename iterator_traits<_InputIterator>::difference_type __n = 0; 298 while (__first != __last) { 299 ++__first; ++__n; 300 } 301 return __n; 302 } 303 304 template <class _RandomAccessIterator> 305 inline typename iterator_traits<_RandomAccessIterator>::difference_type 306 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 307 random_access_iterator_tag) { 308 __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); 309 return __last - __first; 310 } 311 312 template <class _InputIterator> 313 inline typename iterator_traits<_InputIterator>::difference_type 314 distance(_InputIterator __first, _InputIterator __last) { 315 typedef typename iterator_traits<_InputIterator>::iterator_category 316 _Category; 317 __STL_REQUIRES(_InputIterator, _InputIterator); 318 return __distance(__first, __last, _Category()); 319 } 320 321 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 322 323 template <class _InputIter, class _Distance> 324 inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) { 325 while (__n--) ++__i; 326 } 327 328 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 329 #pragma set woff 1183 330 #endif 331 332 template <class _BidirectionalIterator, class _Distance> 333 inline void __advance(_BidirectionalIterator& __i, _Distance __n, 334 bidirectional_iterator_tag) { 335 __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator); 336 if (__n >= 0) 337 while (__n--) ++__i; 338 else 339 while (__n++) --__i; 340 } 341 342 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 343 #pragma reset woff 1183 344 #endif 345 346 template <class _RandomAccessIterator, class _Distance> 347 inline void __advance(_RandomAccessIterator& __i, _Distance __n, 348 random_access_iterator_tag) { 349 __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); 350 __i += __n; 351 } 352 353 template <class _InputIterator, class _Distance> 354 inline void advance(_InputIterator& __i, _Distance __n) { 355 __STL_REQUIRES(_InputIterator, _InputIterator); 356 __advance(__i, __n, iterator_category(__i)); 357 } 358 359 __STL_END_NAMESPACE 360 361 #endif /* __SGI_STL_INTERNAL_ITERATOR_BASE_H */ 362 363 364 365 // Local Variables: 366 // mode:C++ 367 // End: 368