4 * Hewlett-Packard Company
6 * Copyright (c) 1996-1998
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
31 #define _STLP_INTERNAL_ITERATOR_BASE_H
33 #ifndef _STLP_INTERNAL_CSTDDEF
34 # include <stl/_cstddef.h>
37 //# if defined (_STLP_IMPORT_VENDOR_CSTD) && ! defined (_STLP_VENDOR_GLOBAL_CSTD)
38 //_STLP_BEGIN_NAMESPACE
39 //using namespace _STLP_VENDOR_CSTD;
41 //#endif /* _STLP_IMPORT_VENDOR_CSTD */
43 #if !defined(_STLP_USE_OLD_HP_ITERATOR_QUERIES) && !defined(_STLP_CLASS_PARTIAL_SPECIALIZATION)
44 # ifndef _STLP_TYPE_TRAITS_H
45 # include <stl/type_traits.h>
51 struct input_iterator_tag {};
52 struct output_iterator_tag {};
53 struct forward_iterator_tag : public input_iterator_tag {};
54 struct bidirectional_iterator_tag : public forward_iterator_tag {};
55 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
58 template <class _Category, class _Tp, _STLP_DFL_TMPL_PARAM(_Distance,ptrdiff_t),
59 _STLP_DFL_TMPL_PARAM(_Pointer,_Tp*), _STLP_DFL_TMPL_PARAM(_Reference,_Tp&) >
61 typedef _Category iterator_category;
62 typedef _Tp value_type;
63 typedef _Distance difference_type;
64 typedef _Pointer pointer;
65 typedef _Reference reference;
68 struct iterator<output_iterator_tag, void, void, void, void> {
69 typedef output_iterator_tag iterator_category;
70 #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
71 typedef void value_type;
72 typedef void difference_type;
74 typedef void reference;
78 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
79 # define _STLP_ITERATOR_CATEGORY(_It, _Tp) iterator_category(_It)
80 # define _STLP_DISTANCE_TYPE(_It, _Tp) distance_type(_It)
81 # define _STLP_VALUE_TYPE(_It, _Tp) value_type(_It)
82 //Old HP iterator queries do not give information about the iterator
83 //associated reference type so we consider that it is not a real reference.
84 # define _STLP_IS_REF_TYPE_REAL_REF(_It, _Tp) __false_type()
86 # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
87 # define _STLP_VALUE_TYPE(_It, _Tp) (typename iterator_traits< _Tp >::value_type*)0
88 # define _STLP_DISTANCE_TYPE(_It, _Tp) (typename iterator_traits< _Tp >::difference_type*)0
89 # if defined (__BORLANDC__) || defined (__SUNPRO_CC) || ( defined (__MWERKS__) && (__MWERKS__ <= 0x2303)) || ( defined (__sgi) && defined (_COMPILER_VERSION)) || defined (__DMC__)
90 # define _STLP_ITERATOR_CATEGORY(_It, _Tp) iterator_traits< _Tp >::iterator_category()
92 # define _STLP_ITERATOR_CATEGORY(_It, _Tp) typename iterator_traits< _Tp >::iterator_category()
94 # define _STLP_IS_REF_TYPE_REAL_REF(_It, _Tp) _IsRefType< typename iterator_traits< _Tp >::reference >::_Ret()
96 # define _STLP_ITERATOR_CATEGORY(_It, _Tp) __iterator_category(_It, _IsPtrType<_Tp>::_Ret())
97 # define _STLP_DISTANCE_TYPE(_It, _Tp) (ptrdiff_t*)0
98 # define _STLP_VALUE_TYPE(_It, _Tp) __value_type(_It, _IsPtrType<_Tp>::_Ret() )
99 # define _STLP_IS_REF_TYPE_REAL_REF(_It, _Tp) __false_type()
103 template <class _Iterator>
104 struct iterator_traits {
105 typedef typename _Iterator::iterator_category iterator_category;
106 typedef typename _Iterator::value_type value_type;
107 typedef typename _Iterator::difference_type difference_type;
108 typedef typename _Iterator::pointer pointer;
109 typedef typename _Iterator::reference reference;
113 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && ! defined (__SUNPRO_CC)
114 # define _STLP_DIFFERENCE_TYPE(_Iterator) typename iterator_traits<_Iterator>::difference_type
116 # define _STLP_DIFFERENCE_TYPE(_Iterator) ptrdiff_t
119 #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
121 // fbp : this order keeps gcc happy
123 struct iterator_traits<const _Tp*> {
124 typedef random_access_iterator_tag iterator_category;
125 typedef _Tp value_type;
126 typedef ptrdiff_t difference_type;
127 typedef const _Tp* pointer;
128 typedef const _Tp& reference;
132 struct iterator_traits<_Tp*> {
133 typedef random_access_iterator_tag iterator_category;
134 typedef _Tp value_type;
135 typedef ptrdiff_t difference_type;
136 typedef _Tp* pointer;
137 typedef _Tp& reference;
140 # if defined (__BORLANDC__)
142 struct iterator_traits<_Tp* const> {
143 typedef random_access_iterator_tag iterator_category;
144 typedef _Tp value_type;
145 typedef ptrdiff_t difference_type;
146 typedef const _Tp* pointer;
147 typedef const _Tp& reference;
151 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
154 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) || \
155 (defined (_STLP_SIMULATE_PARTIAL_SPEC_FOR_TYPE_TRAITS) && ! defined (_STLP_NO_ARROW_OPERATOR))
156 # define _STLP_POINTERS_SPECIALIZE( _TpP )
157 # define _STLP_DEFINE_ARROW_OPERATOR pointer operator->() const { return &(operator*()); }
159 # include <stl/_ptrs_specialize.h>
162 #ifndef _STLP_USE_OLD_HP_ITERATOR_QUERIES
163 // The overloaded functions iterator_category, distance_type, and
164 // value_type are not part of the C++ standard. (They have been
165 // replaced by struct iterator_traits.) They are included for
166 // backward compatibility with the HP STL.
167 // We introduce internal names for these functions.
169 # ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
171 template <class _Iter>
172 inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&) {
173 typedef typename iterator_traits<_Iter>::iterator_category _Category;
177 template <class _Iter>
178 inline typename iterator_traits<_Iter>::difference_type* __distance_type(const _Iter&) {
179 typedef typename iterator_traits<_Iter>::difference_type _diff_type;
180 return __STATIC_CAST(_diff_type*,0);
183 template <class _Iter>
184 inline typename iterator_traits<_Iter>::value_type* __value_type(const _Iter&) {
185 typedef typename iterator_traits<_Iter>::value_type _value_type;
186 return __STATIC_CAST(_value_type*,0);
189 # else /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
191 template <class _Iter>
192 inline random_access_iterator_tag
193 __iterator_category(const _Iter&, const __true_type&) {
194 return random_access_iterator_tag();
197 template <class _Iter>
198 inline _STLP_TYPENAME_ON_RETURN_TYPE iterator_traits<_Iter>::iterator_category
199 __iterator_category(const _Iter&, const __false_type&) {
200 typedef typename iterator_traits<_Iter>::iterator_category _Category;
205 template <class _Iter>
206 inline ptrdiff_t* _STLP_CALL __distance_type(const _Iter&) { return __STATIC_CAST(ptrdiff_t*, 0); }
208 template <class _Iter>
209 inline _STLP_TYPENAME_ON_RETURN_TYPE iterator_traits<_Iter>::value_type*
210 __value_type(const _Iter&, const __false_type&) {
211 typedef typename iterator_traits<_Iter>::value_type _value_type;
212 return __STATIC_CAST(_value_type*,0);
217 __value_type(const _Tp*, const __true_type&) {
218 return __STATIC_CAST(_Tp*, 0);
221 # endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
223 #else /* _STLP_USE_OLD_HP_ITERATOR_QUERIES */
224 template <class _Category, class _Tp, class _Distance, class _Pointer, class _Reference>
225 inline _Category _STLP_CALL iterator_category(const iterator<_Category,_Tp,_Distance,_Pointer,_Reference>&) { return _Category(); }
226 template <class _Category, class _Tp, class _Distance, class _Pointer, class _Reference>
227 inline _Tp* _STLP_CALL value_type(const iterator<_Category,_Tp,_Distance,_Pointer,_Reference>&) { return __STATIC_CAST(_Tp*, 0); }
228 template <class _Category, class _Tp, class _Distance, class _Pointer, class _Reference>
229 inline _Distance* _STLP_CALL distance_type(const iterator<_Category,_Tp,_Distance,_Pointer,_Reference>&) { return __STATIC_CAST(_Distance*, 0); }
231 inline random_access_iterator_tag _STLP_CALL iterator_category(const _Tp*) { return random_access_iterator_tag(); }
233 inline _Tp* _STLP_CALL value_type(const _Tp*) { return __STATIC_CAST(_Tp*, 0); }
235 inline ptrdiff_t* _STLP_CALL distance_type(const _Tp*) { return __STATIC_CAST(ptrdiff_t*, 0); }
236 #endif /* _STLP_USE_OLD_HP_ITERATOR_QUERIES */
238 # if ! defined (_STLP_NO_ANACHRONISMS)
239 // The base classes input_iterator, output_iterator, forward_iterator,
240 // bidirectional_iterator, and random_access_iterator are not part of
241 // the C++ standard. (They have been replaced by struct iterator.)
242 // They are included for backward compatibility with the HP STL.
243 template <class _Tp, class _Distance> struct input_iterator :
244 public iterator <input_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
245 struct output_iterator : public iterator <output_iterator_tag, void, void, void, void> {};
246 template <class _Tp, class _Distance> struct forward_iterator :
247 public iterator<forward_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
248 template <class _Tp, class _Distance> struct bidirectional_iterator :
249 public iterator<bidirectional_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
250 template <class _Tp, class _Distance> struct random_access_iterator :
251 public iterator<random_access_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
253 # if defined (_STLP_BASE_MATCH_BUG) && defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
254 template <class _Tp, class _Distance>
255 inline input_iterator_tag _STLP_CALL
256 iterator_category(const input_iterator<_Tp, _Distance>&) { return input_iterator_tag(); }
257 inline output_iterator_tag _STLP_CALL
258 iterator_category(const output_iterator&) { return output_iterator_tag(); }
259 template <class _Tp, class _Distance>
260 inline forward_iterator_tag _STLP_CALL
261 iterator_category(const forward_iterator<_Tp, _Distance>&) { return forward_iterator_tag(); }
262 template <class _Tp, class _Distance>
263 inline bidirectional_iterator_tag _STLP_CALL
264 iterator_category(const bidirectional_iterator<_Tp, _Distance>&) { return bidirectional_iterator_tag(); }
265 template <class _Tp, class _Distance>
266 inline random_access_iterator_tag _STLP_CALL
267 iterator_category(const random_access_iterator<_Tp, _Distance>&) { return random_access_iterator_tag(); }
268 template <class _Tp, class _Distance>
269 inline _Tp* _STLP_CALL value_type(const input_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Tp*, 0); }
270 template <class _Tp, class _Distance>
271 inline _Tp* _STLP_CALL value_type(const forward_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Tp*, 0); }
272 template <class _Tp, class _Distance>
273 inline _Tp* _STLP_CALL value_type(const bidirectional_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Tp*, 0); }
274 template <class _Tp, class _Distance>
275 inline _Tp* _STLP_CALL value_type(const random_access_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Tp*, 0); }
276 template <class _Tp, class _Distance>
277 inline _Distance* _STLP_CALL distance_type(const input_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Distance*, 0); }
278 template <class _Tp, class _Distance>
279 inline _Distance* _STLP_CALL distance_type(const forward_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Distance*, 0); }
280 template <class _Tp, class _Distance>
281 inline _Distance* _STLP_CALL distance_type(const bidirectional_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Distance*, 0);}
282 template <class _Tp, class _Distance>
283 inline _Distance* _STLP_CALL distance_type(const random_access_iterator<_Tp, _Distance>&) { return __STATIC_CAST(_Distance*, 0); }
284 # endif /* BASE_MATCH */
286 #endif /* _STLP_NO_ANACHRONISMS */
288 template <class _InputIterator, class _Distance>
289 inline void _STLP_CALL __distance(const _InputIterator& __first, const _InputIterator& __last,
290 _Distance& __n, const input_iterator_tag &) {
291 _InputIterator __it(__first);
292 while (__it != __last) { ++__it; ++__n; }
296 # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
297 template <class _ForwardIterator, class _Distance>
298 inline void _STLP_CALL __distance(const _ForwardIterator& __first, const _ForwardIterator& __last,
299 _Distance& __n, const forward_iterator_tag &) {
300 _ForwardIterator __it(__first);
301 while (__it != __last) { ++__first; ++__n; }
304 template <class _BidirectionalIterator, class _Distance>
305 _STLP_INLINE_LOOP void _STLP_CALL __distance(const _BidirectionalIterator& __first,
306 const _BidirectionalIterator& __last,
307 _Distance& __n, const bidirectional_iterator_tag &) {
308 _BidirectionalIterator __it(__first);
309 while (__it != __last) { ++__it; ++__n; }
313 template <class _RandomAccessIterator, class _Distance>
314 inline void _STLP_CALL __distance(const _RandomAccessIterator& __first,
315 const _RandomAccessIterator& __last,
316 _Distance& __n, const random_access_iterator_tag &) {
317 __n += __last - __first;
320 #ifndef _STLP_NO_ANACHRONISMS
321 template <class _InputIterator, class _Distance>
322 inline void _STLP_CALL distance(const _InputIterator& __first,
323 const _InputIterator& __last, _Distance& __n) {
324 __distance(__first, __last, __n, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
328 template <class _InputIterator>
329 inline _STLP_DIFFERENCE_TYPE(_InputIterator) _STLP_CALL
330 __distance(const _InputIterator& __first, const _InputIterator& __last, const input_iterator_tag &) {
331 _STLP_DIFFERENCE_TYPE(_InputIterator) __n = 0;
332 _InputIterator __it(__first);
333 while (__it != __last) {
339 # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
340 template <class _ForwardIterator>
341 inline _STLP_DIFFERENCE_TYPE(_ForwardIterator) _STLP_CALL
342 __distance(const _ForwardIterator& __first, const _ForwardIterator& __last,
343 const forward_iterator_tag &)
345 _STLP_DIFFERENCE_TYPE(_ForwardIterator) __n = 0;
346 _ForwardIterator __it(__first);
347 while (__it != __last) {
354 template <class _BidirectionalIterator>
355 _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_BidirectionalIterator) _STLP_CALL
356 __distance(const _BidirectionalIterator& __first,
357 const _BidirectionalIterator& __last,
358 const bidirectional_iterator_tag &) {
359 _STLP_DIFFERENCE_TYPE(_BidirectionalIterator) __n = 0;
360 _BidirectionalIterator __it(__first);
361 while (__it != __last) {
368 template <class _RandomAccessIterator>
369 inline _STLP_DIFFERENCE_TYPE(_RandomAccessIterator) _STLP_CALL
370 __distance(const _RandomAccessIterator& __first, const _RandomAccessIterator& __last,
371 const random_access_iterator_tag &) {
372 return __last - __first;
375 template <class _InputIterator>
376 inline _STLP_DIFFERENCE_TYPE(_InputIterator) _STLP_CALL
377 distance(_InputIterator __first, _InputIterator __last) {
378 return __distance(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
381 // fbp: those are being used for iterator/const_iterator definitions everywhere
383 struct _Nonconst_traits;
386 struct _Const_traits {
387 typedef _Tp value_type;
388 typedef const _Tp& reference;
389 typedef const _Tp* pointer;
390 typedef _Const_traits<_Tp> _ConstTraits;
391 typedef _Nonconst_traits<_Tp> _NonConstTraits;
395 struct _Nonconst_traits {
396 typedef _Tp value_type;
397 typedef _Tp& reference;
398 typedef _Tp* pointer;
399 typedef _Const_traits<_Tp> _ConstTraits;
400 typedef _Nonconst_traits<_Tp> _NonConstTraits;
404 * dums: A special iterator/const_iterator traits for set and multiset for which even
405 * the iterator is not mutable
408 struct _Nonconst_Const_traits;
411 struct _Const_Const_traits {
412 typedef _Tp value_type;
413 typedef const _Tp& reference;
414 typedef const _Tp* pointer;
415 typedef _Const_Const_traits<_Tp> _ConstTraits;
416 typedef _Nonconst_Const_traits<_Tp> _NonConstTraits;
420 struct _Nonconst_Const_traits {
421 typedef _Tp value_type;
422 typedef const _Tp& reference;
423 typedef const _Tp* pointer;
424 typedef _Const_Const_traits<_Tp> _ConstTraits;
425 typedef _Nonconst_Const_traits<_Tp> _NonConstTraits;
429 * A macro to generate a new iterator traits from one of the
430 * previous one. Changing the iterator traits type make iterators
431 * from different containers not comparable.
433 #define _STLP_CREATE_ITERATOR_TRAITS_BASE(Motif, Traits) \
434 template <class _Tp> \
436 template <class _Tp> \
437 struct _Const##Motif : public _STLP_STD::_Const_##Traits<_Tp> { \
438 typedef _Const##Motif<_Tp> _ConstTraits; \
439 typedef _##Motif<_Tp> _NonConstTraits; \
441 template <class _Tp> \
442 struct _##Motif : public _STLP_STD::_Nonconst_##Traits<_Tp> { \
443 typedef _Const##Motif<_Tp> _ConstTraits; \
444 typedef _##Motif<_Tp> _NonConstTraits; \
447 #define _STLP_CREATE_ITERATOR_TRAITS(Motif, Traits) \
448 _STLP_MOVE_TO_PRIV_NAMESPACE \
449 _STLP_CREATE_ITERATOR_TRAITS_BASE(Motif, Traits) \
450 _STLP_MOVE_TO_STD_NAMESPACE
452 #define _STLP_CREATE_HASH_ITERATOR_TRAITS(Motif, Traits) \
453 _STLP_MOVE_TO_PRIV_NAMESPACE \
454 _STLP_CREATE_ITERATOR_TRAITS_BASE(NonLocal##Motif, Traits) \
455 _STLP_CREATE_ITERATOR_TRAITS_BASE(Local##Motif, Traits) \
456 template <class _Tp> \
458 typedef _ConstNonLocal##Motif<_Tp> _ConstTraits; \
459 typedef _NonLocal##Motif<_Tp> _NonConstTraits; \
460 typedef _ConstLocal##Motif<_Tp> _ConstLocalTraits; \
461 typedef _Local##Motif<_Tp> _NonConstLocalTraits; \
463 _STLP_MOVE_TO_STD_NAMESPACE
466 # if defined (_STLP_BASE_TYPEDEF_BUG)
467 // this workaround is needed for SunPro 4.0.1
468 template <class _Traits>
469 struct __cnst_traits_aux : private _Traits {
470 typedef typename _Traits::value_type value_type;
472 # define __TRAITS_VALUE_TYPE(_Traits) __cnst_traits_aux<_Traits>::value_type
474 # define __TRAITS_VALUE_TYPE(_Traits) _Traits::value_type
478 #if defined (_STLP_MSVC)
480 template <class _InputIterator, class _Dist>
481 inline void _STLP_CALL _Distance(_InputIterator __first,
482 _InputIterator __last, _Dist& __n) {
483 __distance(__first, __last, __n, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
487 template <class _InputIter, class _Distance>
488 _STLP_INLINE_LOOP void _STLP_CALL
489 __advance(_InputIter& __i, _Distance __n, const input_iterator_tag &) {
493 // fbp : added output iterator tag variant
494 template <class _InputIter, class _Distance>
495 _STLP_INLINE_LOOP void _STLP_CALL
496 __advance(_InputIter& __i, _Distance __n, const output_iterator_tag &) {
500 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
501 template <class _ForwardIterator, class _Distance>
502 _STLP_INLINE_LOOP void _STLP_CALL
503 __advance(_ForwardIterator& i, _Distance n, const forward_iterator_tag &) {
508 template <class _BidirectionalIterator, class _Distance>
509 _STLP_INLINE_LOOP void _STLP_CALL
510 __advance(_BidirectionalIterator& __i, _Distance __n,
511 const bidirectional_iterator_tag &) {
518 template <class _RandomAccessIterator, class _Distance>
519 inline void _STLP_CALL
520 __advance(_RandomAccessIterator& __i, _Distance __n,
521 const random_access_iterator_tag &) {
525 template <class _InputIterator, class _Distance>
526 inline void _STLP_CALL advance(_InputIterator& __i, _Distance __n) {
527 __advance(__i, __n, _STLP_ITERATOR_CATEGORY(__i, _InputIterator));
532 #if defined (_STLP_DEBUG) && !defined (_STLP_DEBUG_H)
533 # include <stl/debug/_debug.h>
536 #endif /* _STLP_INTERNAL_ITERATOR_BASE_H */