stl_iterator_base.h

00001 /*
00002  *
00003  * Copyright (c) 1994
00004  * Hewlett-Packard Company
00005  *
00006  * Permission to use, copy, modify, distribute and sell this software
00007  * and its documentation for any purpose is hereby granted without fee,
00008  * provided that the above copyright notice appear in all copies and
00009  * that both that copyright notice and this permission notice appear
00010  * in supporting documentation.  Hewlett-Packard Company makes no
00011  * representations about the suitability of this software for any
00012  * purpose.  It is provided "as is" without express or implied warranty.
00013  *
00014  *
00015  * Copyright (c) 1996-1998
00016  * Silicon Graphics Computer Systems, Inc.
00017  *
00018  * Permission to use, copy, modify, distribute and sell this software
00019  * and its documentation for any purpose is hereby granted without fee,
00020  * provided that the above copyright notice appear in all copies and
00021  * that both that copyright notice and this permission notice appear
00022  * in supporting documentation.  Silicon Graphics makes no
00023  * representations about the suitability of this software for any
00024  * purpose.  It is provided "as is" without express or implied warranty.
00025  */
00026 
00027 /* NOTE: This is an internal header file, included by other STL headers.
00028  *   You should not attempt to use it directly.
00029  */
00030 
00031 #ifndef __SGI_STL_INTERNAL_ITERATOR_BASE_H
00032 #define __SGI_STL_INTERNAL_ITERATOR_BASE_H
00033 
00034 // This file contains all of the general iterator-related utilities.
00035 // The internal file stl_iterator.h contains predefined iterators, 
00036 // such as front_insert_iterator and istream_iterator.
00037 
00038 #include <concept_checks.h>
00039 
00040 __STL_BEGIN_NAMESPACE
00041 
00042 struct input_iterator_tag {};
00043 struct output_iterator_tag {};
00044 struct forward_iterator_tag : public input_iterator_tag {};
00045 struct bidirectional_iterator_tag : public forward_iterator_tag {};
00046 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
00047 
00048 // The base classes input_iterator, output_iterator, forward_iterator,
00049 // bidirectional_iterator, and random_access_iterator are not part of
00050 // the C++ standard.  (They have been replaced by struct iterator.)
00051 // They are included for backward compatibility with the HP STL.
00052 
00053 template <class _Tp, class _Distance> struct input_iterator {
00054   typedef input_iterator_tag iterator_category;
00055   typedef _Tp                value_type;
00056   typedef _Distance          difference_type;
00057   typedef _Tp*               pointer;
00058   typedef _Tp&               reference;
00059 };
00060 
00061 struct output_iterator {
00062   typedef output_iterator_tag iterator_category;
00063   typedef void                value_type;
00064   typedef void                difference_type;
00065   typedef void                pointer;
00066   typedef void                reference;
00067 };
00068 
00069 template <class _Tp, class _Distance> struct forward_iterator {
00070   typedef forward_iterator_tag iterator_category;
00071   typedef _Tp                  value_type;
00072   typedef _Distance            difference_type;
00073   typedef _Tp*                 pointer;
00074   typedef _Tp&                 reference;
00075 };
00076 
00077 
00078 template <class _Tp, class _Distance> struct bidirectional_iterator {
00079   typedef bidirectional_iterator_tag iterator_category;
00080   typedef _Tp                        value_type;
00081   typedef _Distance                  difference_type;
00082   typedef _Tp*                       pointer;
00083   typedef _Tp&                       reference;
00084 };
00085 
00086 template <class _Tp, class _Distance> struct random_access_iterator {
00087   typedef random_access_iterator_tag iterator_category;
00088   typedef _Tp                        value_type;
00089   typedef _Distance                  difference_type;
00090   typedef _Tp*                       pointer;
00091   typedef _Tp&                       reference;
00092 };
00093 
00094 #ifdef __STL_USE_NAMESPACES
00095 template <class _Category, class _Tp, class _Distance = ptrdiff_t,
00096           class _Pointer = _Tp*, class _Reference = _Tp&>
00097 struct iterator {
00098   typedef _Category  iterator_category;
00099   typedef _Tp        value_type;
00100   typedef _Distance  difference_type;
00101   typedef _Pointer   pointer;
00102   typedef _Reference reference;
00103 };
00104 #endif /* __STL_USE_NAMESPACES */
00105 
00106 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
00107 
00108 template <class _Iterator>
00109 struct iterator_traits {
00110   typedef typename _Iterator::iterator_category iterator_category;
00111   typedef typename _Iterator::value_type        value_type;
00112   typedef typename _Iterator::difference_type   difference_type;
00113   typedef typename _Iterator::pointer           pointer;
00114   typedef typename _Iterator::reference         reference;
00115 };
00116 
00117 template <class _Tp>
00118 struct iterator_traits<_Tp*> {
00119   typedef random_access_iterator_tag iterator_category;
00120   typedef _Tp                         value_type;
00121   typedef ptrdiff_t                   difference_type;
00122   typedef _Tp*                        pointer;
00123   typedef _Tp&                        reference;
00124 };
00125 
00126 template <class _Tp>
00127 struct iterator_traits<const _Tp*> {
00128   typedef random_access_iterator_tag iterator_category;
00129   typedef _Tp                         value_type;
00130   typedef ptrdiff_t                   difference_type;
00131   typedef const _Tp*                  pointer;
00132   typedef const _Tp&                  reference;
00133 };
00134 
00135 // The overloaded functions iterator_category, distance_type, and
00136 // value_type are not part of the C++ standard.  (They have been
00137 // replaced by struct iterator_traits.)  They are included for
00138 // backward compatibility with the HP STL.
00139 
00140 // We introduce internal names for these functions.
00141 
00142 template <class _Iter>
00143 inline typename iterator_traits<_Iter>::iterator_category
00144 __iterator_category(const _Iter&)
00145 {
00146   typedef typename iterator_traits<_Iter>::iterator_category _Category;
00147   return _Category();
00148 }
00149 
00150 template <class _Iter>
00151 inline typename iterator_traits<_Iter>::difference_type*
00152 __distance_type(const _Iter&)
00153 {
00154   return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
00155 }
00156 
00157 template <class _Iter>
00158 inline typename iterator_traits<_Iter>::value_type*
00159 __value_type(const _Iter&)
00160 {
00161   return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
00162 }
00163 
00164 template <class _Iter>
00165 inline typename iterator_traits<_Iter>::iterator_category
00166 iterator_category(const _Iter& __i) { return __iterator_category(__i); }
00167 
00168 
00169 template <class _Iter>
00170 inline typename iterator_traits<_Iter>::difference_type*
00171 distance_type(const _Iter& __i) { return __distance_type(__i); }
00172 
00173 template <class _Iter>
00174 inline typename iterator_traits<_Iter>::value_type*
00175 value_type(const _Iter& __i) { return __value_type(__i); }
00176 
00177 #define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
00178 #define __DISTANCE_TYPE(__i)     __distance_type(__i)
00179 #define __VALUE_TYPE(__i)        __value_type(__i)
00180 
00181 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
00182 
00183 template <class _Tp, class _Distance> 
00184 inline input_iterator_tag 
00185 iterator_category(const input_iterator<_Tp, _Distance>&)
00186   { return input_iterator_tag(); }
00187 
00188 inline output_iterator_tag iterator_category(const output_iterator&)
00189   { return output_iterator_tag(); }
00190 
00191 template <class _Tp, class _Distance> 
00192 inline forward_iterator_tag
00193 iterator_category(const forward_iterator<_Tp, _Distance>&)
00194   { return forward_iterator_tag(); }
00195 
00196 template <class _Tp, class _Distance> 
00197 inline bidirectional_iterator_tag
00198 iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
00199   { return bidirectional_iterator_tag(); }
00200 
00201 template <class _Tp, class _Distance> 
00202 inline random_access_iterator_tag
00203 iterator_category(const random_access_iterator<_Tp, _Distance>&)
00204   { return random_access_iterator_tag(); }
00205 
00206 template <class _Tp>
00207 inline random_access_iterator_tag iterator_category(const _Tp*)
00208   { return random_access_iterator_tag(); }
00209 
00210 template <class _Tp, class _Distance> 
00211 inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
00212   { return (_Tp*)(0); }
00213 
00214 template <class _Tp, class _Distance> 
00215 inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
00216   { return (_Tp*)(0); }
00217 
00218 template <class _Tp, class _Distance> 
00219 inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
00220   { return (_Tp*)(0); }
00221 
00222 template <class _Tp, class _Distance> 
00223 inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
00224   { return (_Tp*)(0); }
00225 
00226 template <class _Tp>
00227 inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
00228 
00229 template <class _Tp, class _Distance> 
00230 inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
00231 {
00232   return (_Distance*)(0);
00233 }
00234 
00235 template <class _Tp, class _Distance> 
00236 inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
00237 {
00238   return (_Distance*)(0);
00239 }
00240 
00241 template <class _Tp, class _Distance> 
00242 inline _Distance* 
00243 distance_type(const bidirectional_iterator<_Tp, _Distance>&)
00244 {
00245   return (_Distance*)(0);
00246 }
00247 
00248 template <class _Tp, class _Distance> 
00249 inline _Distance* 
00250 distance_type(const random_access_iterator<_Tp, _Distance>&)
00251 {
00252   return (_Distance*)(0);
00253 }
00254 
00255 template <class _Tp>
00256 inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
00257 
00258 // Without partial specialization we can't use iterator_traits, so
00259 // we must keep the old iterator query functions around.  
00260 
00261 #define __ITERATOR_CATEGORY(__i) iterator_category(__i)
00262 #define __DISTANCE_TYPE(__i)     distance_type(__i)
00263 #define __VALUE_TYPE(__i)        value_type(__i)
00264 
00265 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
00266 
00267 template <class _InputIterator, class _Distance>
00268 inline void __distance(_InputIterator __first, _InputIterator __last,
00269                        _Distance& __n, input_iterator_tag)
00270 {
00271   while (__first != __last) { ++__first; ++__n; }
00272 }
00273 
00274 template <class _RandomAccessIterator, class _Distance>
00275 inline void __distance(_RandomAccessIterator __first, 
00276                        _RandomAccessIterator __last, 
00277                        _Distance& __n, random_access_iterator_tag)
00278 {
00279   __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
00280   __n += __last - __first;
00281 }
00282 
00283 template <class _InputIterator, class _Distance>
00284 inline void distance(_InputIterator __first, 
00285                      _InputIterator __last, _Distance& __n)
00286 {
00287   __STL_REQUIRES(_InputIterator, _InputIterator);
00288   __distance(__first, __last, __n, iterator_category(__first));
00289 }
00290 
00291 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
00292 
00293 template <class _InputIterator>
00294 inline typename iterator_traits<_InputIterator>::difference_type
00295 __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
00296 {
00297   typename iterator_traits<_InputIterator>::difference_type __n = 0;
00298   while (__first != __last) {
00299     ++__first; ++__n;
00300   }
00301   return __n;
00302 }
00303 
00304 template <class _RandomAccessIterator>
00305 inline typename iterator_traits<_RandomAccessIterator>::difference_type
00306 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
00307            random_access_iterator_tag) {
00308   __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
00309   return __last - __first;
00310 }
00311 
00312 template <class _InputIterator>
00313 inline typename iterator_traits<_InputIterator>::difference_type
00314 distance(_InputIterator __first, _InputIterator __last) {
00315   typedef typename iterator_traits<_InputIterator>::iterator_category 
00316     _Category;
00317   __STL_REQUIRES(_InputIterator, _InputIterator);
00318   return __distance(__first, __last, _Category());
00319 }
00320 
00321 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
00322 
00323 template <class _InputIter, class _Distance>
00324 inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
00325   while (__n--) ++__i;
00326 }
00327 
00328 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
00329 #pragma set woff 1183
00330 #endif
00331 
00332 template <class _BidirectionalIterator, class _Distance>
00333 inline void __advance(_BidirectionalIterator& __i, _Distance __n, 
00334                       bidirectional_iterator_tag) {
00335   __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
00336   if (__n >= 0)
00337     while (__n--) ++__i;
00338   else
00339     while (__n++) --__i;
00340 }
00341 
00342 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
00343 #pragma reset woff 1183
00344 #endif
00345 
00346 template <class _RandomAccessIterator, class _Distance>
00347 inline void __advance(_RandomAccessIterator& __i, _Distance __n, 
00348                       random_access_iterator_tag) {
00349   __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
00350   __i += __n;
00351 }
00352 
00353 template <class _InputIterator, class _Distance>
00354 inline void advance(_InputIterator& __i, _Distance __n) {
00355   __STL_REQUIRES(_InputIterator, _InputIterator);
00356   __advance(__i, __n, iterator_category(__i));
00357 }
00358 
00359 __STL_END_NAMESPACE
00360 
00361 #endif /* __SGI_STL_INTERNAL_ITERATOR_BASE_H */
00362 
00363 
00364 
00365 // Local Variables:
00366 // mode:C++
00367 // End:

Generated on Mon Jun 5 10:20:44 2006 for Intelligence.kdevelop by  doxygen 1.4.6