home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _iterator_base.h < prev    next >
C/C++ Source or Header  |  2002-01-18  |  17KB  |  458 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Copyright (c) 1996-1998
  7.  * Silicon Graphics Computer Systems, Inc.
  8.  *
  9.  * Copyright (c) 1997
  10.  * Moscow Center for SPARC Technology
  11.  *
  12.  * Copyright (c) 1999 
  13.  * Boris Fomitchev
  14.  *
  15.  * This material is provided "as is", with absolutely no warranty expressed
  16.  * or implied. Any use is at your own risk.
  17.  *
  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.
  23.  *
  24.  */
  25.  
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29.  
  30. #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
  31. #define _STLP_INTERNAL_ITERATOR_BASE_H
  32.  
  33. #ifndef _STLP_CSTDDEF
  34. # include <cstddef>
  35. #endif
  36.  
  37. #ifndef __TYPE_TRAITS_H
  38. # include <stl/type_traits.h>
  39. #endif
  40.  
  41. _STLP_BEGIN_NAMESPACE
  42.  
  43. struct input_iterator_tag {};
  44. struct output_iterator_tag {};
  45. struct forward_iterator_tag : public input_iterator_tag {};
  46. struct bidirectional_iterator_tag : public forward_iterator_tag {};
  47. struct random_access_iterator_tag : public bidirectional_iterator_tag {};
  48.  
  49.  
  50. template <class _Category, class _Tp, __DFL_TMPL_PARAM(_Distance,ptrdiff_t),
  51.           __DFL_TMPL_PARAM(_Pointer,_Tp*), __DFL_TMPL_PARAM(_Reference,_Tp&) >
  52. struct iterator {
  53.   typedef _Category  iterator_category;
  54.   typedef _Tp        value_type;
  55.   typedef _Distance  difference_type;
  56.   typedef _Pointer   pointer;
  57.   typedef _Reference reference;
  58. };
  59. _STLP_TEMPLATE_NULL
  60. struct iterator<output_iterator_tag, void, void, void, void> {
  61.   typedef output_iterator_tag  iterator_category;
  62. #ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
  63.   typedef void                value_type;
  64.   typedef void                difference_type;
  65.   typedef void                pointer;
  66.   typedef void                reference;
  67. #endif
  68. };
  69.  
  70. # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  71. #  define _STLP_ITERATOR_CATEGORY(_It, _Tp) iterator_category(_It)
  72. #  define _STLP_DISTANCE_TYPE(_It, _Tp)     distance_type(_It)
  73. #  define _STLP_VALUE_TYPE(_It, _Tp)        value_type(_It)
  74. # else
  75. #  ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
  76. #   define _STLP_VALUE_TYPE(_It, _Tp)        (typename iterator_traits< _Tp >::value_type*)0
  77. #   define _STLP_DISTANCE_TYPE(_It, _Tp)     (typename iterator_traits< _Tp >::difference_type*)0
  78. #   if defined (__BORLANDC__) || defined (__SUNPRO_CC) || ( defined (__MWERKS__) && (__MWERKS__ <= 0x2303)) || ( defined (__sgi) && defined (_COMPILER_VERSION)) 
  79. #    define _STLP_ITERATOR_CATEGORY(_It, _Tp) iterator_traits< _Tp >::iterator_category()
  80. #   else
  81. #    define _STLP_ITERATOR_CATEGORY(_It, _Tp) typename iterator_traits< _Tp >::iterator_category()
  82. #   endif
  83. #  else
  84. #   define _STLP_ITERATOR_CATEGORY(_It, _Tp) __iterator_category(_It, _IsPtrType<_Tp>::_Ret())
  85. #   define _STLP_DISTANCE_TYPE(_It, _Tp)     (ptrdiff_t*)0
  86. #   define _STLP_VALUE_TYPE(_It, _Tp)        __value_type(_It, _IsPtrType<_Tp>::_Ret() )
  87. #  endif
  88. # endif
  89.  
  90. template <class _Iterator>
  91. struct iterator_traits {
  92.   typedef typename _Iterator::iterator_category iterator_category;
  93.   typedef typename _Iterator::value_type        value_type;
  94.   typedef typename _Iterator::difference_type   difference_type;
  95.   typedef typename _Iterator::pointer           pointer;
  96.   typedef typename _Iterator::reference         reference;
  97. };
  98.  
  99.  
  100. # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && ! defined (__SUNPRO_CC)
  101. #  define _STLP_DIFFERENCE_TYPE(_Iterator) typename iterator_traits<_Iterator>::difference_type
  102. # else
  103. #  define _STLP_DIFFERENCE_TYPE(_Iterator) ptrdiff_t
  104. # endif
  105.  
  106. # ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
  107.  
  108. // fbp : this order keeps gcc happy
  109. template <class _Tp>
  110. struct iterator_traits<const _Tp*> {
  111.   typedef random_access_iterator_tag iterator_category;
  112.   typedef _Tp                         value_type;
  113.   typedef ptrdiff_t                   difference_type;
  114.   typedef const _Tp*                  pointer;
  115.   typedef const _Tp&                  reference;
  116. };
  117.  
  118. template <class _Tp>
  119. struct iterator_traits<_Tp*> {
  120.   typedef random_access_iterator_tag iterator_category;
  121.   typedef _Tp                         value_type;
  122.   typedef ptrdiff_t                   difference_type;
  123.   typedef _Tp*                        pointer;
  124.   typedef _Tp&                        reference;
  125. };
  126.  
  127. #  if defined (__BORLANDC__)
  128. template <class _Tp>
  129. struct iterator_traits<_Tp* const> {
  130.   typedef random_access_iterator_tag iterator_category;
  131.   typedef _Tp                         value_type;
  132.   typedef ptrdiff_t                   difference_type;
  133.   typedef const _Tp*                  pointer;
  134.   typedef const _Tp&                  reference;
  135. };
  136. #  endif
  137.  
  138. # endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
  139.  
  140.  
  141. # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) \
  142.   || (defined (_STLP_SIMULATE_PARTIAL_SPEC_FOR_TYPE_TRAITS) && ! defined (_STLP_NO_ARROW_OPERATOR))
  143. #  define _STLP_POINTERS_SPECIALIZE( _TpP )
  144. #  define _STLP_DEFINE_ARROW_OPERATOR  pointer operator->() const { return &(operator*()); }
  145. # else 
  146. #  include <stl/_ptrs_specialize.h>
  147. # endif
  148.  
  149. # ifndef _STLP_USE_OLD_HP_ITERATOR_QUERIES
  150. // The overloaded functions iterator_category, distance_type, and
  151. // value_type are not part of the C++ standard.  (They have been
  152. // replaced by struct iterator_traits.)  They are included for
  153. // backward compatibility with the HP STL.
  154. // We introduce internal names for these functions.
  155.  
  156. #  ifdef  _STLP_CLASS_PARTIAL_SPECIALIZATION
  157.  
  158. template <class _Iter>
  159. inline typename iterator_traits<_Iter>::iterator_category __iterator_category(const _Iter&) {
  160.   typedef typename iterator_traits<_Iter>::iterator_category _Category;
  161.   return _Category();
  162. }
  163.  
  164. template <class _Iter>
  165. inline typename iterator_traits<_Iter>::difference_type* __distance_type(const _Iter&) {
  166.   typedef typename iterator_traits<_Iter>::difference_type _diff_type;
  167.   return __STATIC_CAST(_diff_type*,0);
  168. }
  169.  
  170. template <class _Iter>
  171. inline typename iterator_traits<_Iter>::value_type* __value_type(const _Iter&) {
  172.   typedef typename iterator_traits<_Iter>::value_type _value_type;
  173.   return __STATIC_CAST(_value_type*,0);
  174. }
  175.  
  176. # else
  177.  
  178. template <class _Iter>
  179. inline random_access_iterator_tag 
  180. __iterator_category(const _Iter&, const __true_type&) {
  181.   return random_access_iterator_tag();
  182. }
  183.  
  184. template <class _Iter>
  185. inline _STLP_TYPENAME_ON_RETURN_TYPE iterator_traits<_Iter>::iterator_category
  186. __iterator_category(const _Iter&, const __false_type&) {
  187.   typedef typename iterator_traits<_Iter>::iterator_category _Category;
  188.   return _Category();
  189. }
  190.  
  191.  
  192. template <class _Iter>
  193. inline ptrdiff_t* _STLP_CALL __distance_type(const _Iter&) { return (ptrdiff_t*)(0); }
  194.  
  195. template <class _Iter>
  196. inline _STLP_TYPENAME_ON_RETURN_TYPE iterator_traits<_Iter>::value_type* 
  197. __value_type(const _Iter&, const __false_type&) {
  198.   typedef typename iterator_traits<_Iter>::value_type _value_type;
  199.   return __STATIC_CAST(_value_type*,0);
  200. }
  201.  
  202. template <class _Tp>
  203. inline _Tp*  
  204. __value_type(const _Tp*, const __true_type&) {
  205.   return __STATIC_CAST(_Tp*, 0);
  206. }
  207.  
  208. # endif
  209.  
  210. #else /* old queries */
  211. template <class _Category, class _Tp, class _Distance, class _Pointer, class _Reference>
  212. inline _Category _STLP_CALL iterator_category(const iterator<_Category,_Tp,_Distance,_Pointer,_Reference>&) { return _Category(); }
  213. template <class _Category, class _Tp, class _Distance, class _Pointer, class _Reference>
  214. inline _Tp* _STLP_CALL value_type(const iterator<_Category,_Tp,_Distance,_Pointer,_Reference>&) { return (_Tp*)(0); }
  215. template <class _Category, class _Tp, class _Distance, class _Pointer, class _Reference>
  216. inline _Distance* _STLP_CALL distance_type(const iterator<_Category,_Tp,_Distance,_Pointer,_Reference>&) { return (_Distance*)(0); }
  217. template <class _Tp>
  218. inline random_access_iterator_tag _STLP_CALL iterator_category(const _Tp*) { return random_access_iterator_tag(); }
  219. template <class _Tp>
  220. inline _Tp* _STLP_CALL value_type(const _Tp*) { return (_Tp*)(0); }
  221. template <class _Tp>
  222. inline ptrdiff_t* _STLP_CALL distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
  223. #endif /* _STLP_USE_OLD_HP_ITERATOR_QUERIES */
  224.  
  225. # if ! defined (_STLP_NO_ANACHRONISMS)
  226. // The base classes input_iterator, output_iterator, forward_iterator,
  227. // bidirectional_iterator, and random_access_iterator are not part of
  228. // the C++ standard.  (They have been replaced by struct iterator.)
  229. // They are included for backward compatibility with the HP STL.
  230. template <class _Tp, class _Distance> struct input_iterator : 
  231.   public iterator <input_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
  232. struct output_iterator : public iterator <output_iterator_tag, void, void, void, void> {};
  233. template <class _Tp, class _Distance> struct forward_iterator :
  234.   public iterator<forward_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
  235. template <class _Tp, class _Distance> struct bidirectional_iterator :
  236.   public iterator<bidirectional_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
  237. template <class _Tp, class _Distance> struct random_access_iterator :
  238.   public iterator<random_access_iterator_tag, _Tp, _Distance, _Tp*, _Tp&> {};
  239.  
  240. # if defined (_STLP_BASE_MATCH_BUG) && defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
  241. template <class _Tp, class _Distance> 
  242. inline input_iterator_tag _STLP_CALL 
  243. iterator_category(const input_iterator<_Tp, _Distance>&) { return input_iterator_tag(); }
  244. inline output_iterator_tag _STLP_CALL
  245. iterator_category(const output_iterator&) { return output_iterator_tag(); }
  246. template <class _Tp, class _Distance> 
  247. inline forward_iterator_tag _STLP_CALL
  248. iterator_category(const forward_iterator<_Tp, _Distance>&) { return forward_iterator_tag(); }
  249. template <class _Tp, class _Distance> 
  250. inline bidirectional_iterator_tag _STLP_CALL 
  251. iterator_category(const bidirectional_iterator<_Tp, _Distance>&) { return bidirectional_iterator_tag(); }
  252. template <class _Tp, class _Distance> 
  253. inline random_access_iterator_tag _STLP_CALL
  254. iterator_category(const random_access_iterator<_Tp, _Distance>&) { return random_access_iterator_tag(); }
  255. template <class _Tp, class _Distance> 
  256. inline _Tp*  _STLP_CALL value_type(const input_iterator<_Tp, _Distance>&) { return (_Tp*)(0); }
  257. template <class _Tp, class _Distance> 
  258. inline _Tp* _STLP_CALL value_type(const forward_iterator<_Tp, _Distance>&) { return (_Tp*)(0); }
  259. template <class _Tp, class _Distance> 
  260. inline _Tp* _STLP_CALL value_type(const bidirectional_iterator<_Tp, _Distance>&) { return (_Tp*)(0); }
  261. template <class _Tp, class _Distance> 
  262. inline _Tp* _STLP_CALL value_type(const random_access_iterator<_Tp, _Distance>&) { return (_Tp*)(0); }
  263. template <class _Tp, class _Distance> 
  264. inline _Distance* _STLP_CALL distance_type(const input_iterator<_Tp, _Distance>&) { return (_Distance*)(0); }
  265. template <class _Tp, class _Distance> 
  266. inline _Distance* _STLP_CALL distance_type(const forward_iterator<_Tp, _Distance>&) { return (_Distance*)(0); }
  267. template <class _Tp, class _Distance> 
  268. inline _Distance* _STLP_CALL distance_type(const bidirectional_iterator<_Tp, _Distance>&) { return (_Distance*)(0);}
  269. template <class _Tp, class _Distance> 
  270. inline _Distance* _STLP_CALL distance_type(const random_access_iterator<_Tp, _Distance>&) { return (_Distance*)(0); }
  271. # endif /* BASE_MATCH */
  272.  
  273. #endif /* _STLP_NO_ANACHRONISMS */
  274.  
  275. template <class _InputIterator, class _Distance>
  276. inline void _STLP_CALL __distance(const _InputIterator& __first, const _InputIterator& __last,
  277.                   _Distance& __n, const input_iterator_tag &) {
  278.   _InputIterator __it(__first);
  279.   while (__it != __last) { ++__it; ++__n; }
  280. }
  281.  
  282. # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 
  283. template <class _ForwardIterator, class _Distance>
  284. inline void _STLP_CALL __distance(const _ForwardIterator& __first, const _ForwardIterator& __last,
  285.                   _Distance& __n, const forward_iterator_tag &) {
  286.   _ForwardIterator __it(__first);
  287.   while (__it != __last) { ++__first; ++__n; }
  288. }
  289.  
  290. template <class _BidirectionalIterator, class _Distance>
  291. _STLP_INLINE_LOOP void _STLP_CALL __distance(const _BidirectionalIterator& __first, 
  292.                          const _BidirectionalIterator& __last,
  293.                          _Distance& __n, const bidirectional_iterator_tag &) {
  294.   _BidirectionalIterator __it(__first);
  295.   while (__it != __last) { ++__it; ++__n; }
  296. }
  297. # endif
  298.  
  299. template <class _RandomAccessIterator, class _Distance>
  300. inline void _STLP_CALL __distance(const _RandomAccessIterator& __first, 
  301.                   const _RandomAccessIterator& __last, 
  302.                   _Distance& __n, const random_access_iterator_tag &) {
  303.   __n += __last - __first;
  304. }
  305.  
  306. #ifndef _STLP_NO_ANACHRONISMS 
  307. template <class _InputIterator, class _Distance>
  308. inline void _STLP_CALL distance(const _InputIterator& __first, 
  309.                 const _InputIterator& __last, _Distance& __n) {
  310.   __distance(__first, __last, __n, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
  311. }
  312. #endif
  313.  
  314. template <class _InputIterator>
  315. inline _STLP_DIFFERENCE_TYPE(_InputIterator) _STLP_CALL
  316. __distance(const _InputIterator& __first, const _InputIterator& __last, const input_iterator_tag &) {
  317.   _STLP_DIFFERENCE_TYPE(_InputIterator) __n = 0;
  318.   _InputIterator __it(__first);  
  319.   while (__it != __last) {
  320.     ++__it; ++__n;
  321.   }
  322.   return __n;
  323. }
  324.  
  325. # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 
  326. template <class _ForwardIterator>
  327. inline _STLP_DIFFERENCE_TYPE(_ForwardIterator) _STLP_CALL 
  328. __distance(const _ForwardIterator& __first, const _ForwardIterator& __last,
  329.            const forward_iterator_tag &)
  330. {
  331.   _STLP_DIFFERENCE_TYPE(_ForwardIterator) __n = 0;
  332.   _ForwardIterator __it(__first);
  333.   while (__it != __last) {
  334.     ++__it; ++__n;
  335.   }
  336.   return __n;
  337. }
  338.  
  339. template <class _BidirectionalIterator>
  340. _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_BidirectionalIterator) _STLP_CALL 
  341. __distance(const _BidirectionalIterator& __first, 
  342.            const _BidirectionalIterator& __last,
  343.            const bidirectional_iterator_tag &) {
  344.   _STLP_DIFFERENCE_TYPE(_BidirectionalIterator) __n = 0;
  345.   _BidirectionalIterator __it(__first);
  346.   while (__it != __last) {
  347.     ++__it; ++__n;
  348.   }
  349.   return __n;
  350. }
  351. # endif
  352.  
  353. template <class _RandomAccessIterator>
  354. inline _STLP_DIFFERENCE_TYPE(_RandomAccessIterator) _STLP_CALL
  355. __distance(const _RandomAccessIterator& __first, const _RandomAccessIterator& __last,
  356.            const random_access_iterator_tag &) {
  357.   return __last - __first;
  358. }
  359.  
  360. template <class _InputIterator>
  361. inline _STLP_DIFFERENCE_TYPE(_InputIterator) _STLP_CALL
  362. distance(const _InputIterator& __first, const _InputIterator& __last) {
  363.   return __distance(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));  
  364. }
  365.  
  366.  
  367. // fbp: those are being used for iterator/const_iterator definitions everywhere
  368. template <class _Tp>
  369. struct _Nonconst_traits;
  370.  
  371. template <class _Tp>
  372. struct _Const_traits {
  373.   typedef _Tp value_type;
  374.   typedef const _Tp&  reference;
  375.   typedef const _Tp*  pointer;
  376.   typedef _Nonconst_traits<_Tp> _Non_const_traits;
  377. };
  378.  
  379. template <class _Tp>
  380. struct _Nonconst_traits {
  381.   typedef _Tp value_type;
  382.   typedef _Tp& reference;
  383.   typedef _Tp* pointer;
  384.   typedef _Nonconst_traits<_Tp> _Non_const_traits;
  385. };
  386.  
  387. #  if defined (_STLP_BASE_TYPEDEF_BUG)
  388. // this workaround is needed for SunPro 4.0.1
  389. template <class _Traits>
  390. struct __cnst_traits_aux : private _Traits
  391. {
  392.   typedef typename _Traits::value_type value_type;
  393. };
  394. #  define __TRAITS_VALUE_TYPE(_Traits) __cnst_traits_aux<_Traits>::value_type
  395. #  else
  396. #  define __TRAITS_VALUE_TYPE(_Traits) _Traits::value_type
  397. #  endif
  398.  
  399. # if defined (_STLP_MSVC)
  400. // MSVC specific
  401. template <class _InputIterator, class _Dist>
  402. inline void  _STLP_CALL _Distance(_InputIterator __first, 
  403.               _InputIterator __last, _Dist& __n) {
  404.   __distance(__first, __last, __n, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
  405. }
  406. # endif
  407.  
  408. template <class _InputIter, class _Distance>
  409. _STLP_INLINE_LOOP void  _STLP_CALL __advance(_InputIter& __i, _Distance __n, const input_iterator_tag &) {
  410.   while (__n--) ++__i;
  411. }
  412.  
  413. // fbp : added output iterator tag variant
  414. template <class _InputIter, class _Distance>
  415. _STLP_INLINE_LOOP void  _STLP_CALL __advance(_InputIter& __i, _Distance __n, const output_iterator_tag &) {
  416.   while (__n--) ++__i;
  417. }
  418.  
  419. # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
  420. template <class _ForwardIterator, class _Distance>
  421. _STLP_INLINE_LOOP void _STLP_CALL __advance(_ForwardIterator& i, _Distance n, const forward_iterator_tag &) {
  422.     while (n--) ++i;
  423. }
  424. # endif
  425.  
  426. template <class _BidirectionalIterator, class _Distance>
  427. _STLP_INLINE_LOOP void _STLP_CALL __advance(_BidirectionalIterator& __i, _Distance __n, 
  428.                       const bidirectional_iterator_tag &) {
  429.   if (__n > 0)
  430.     while (__n--) ++__i;
  431.   else
  432.     while (__n++) --__i;
  433. }
  434.  
  435. template <class _RandomAccessIterator, class _Distance>
  436. inline void _STLP_CALL __advance(_RandomAccessIterator& __i, _Distance __n, 
  437.                       const random_access_iterator_tag &) {
  438.   __i += __n;
  439. }
  440.  
  441. template <class _InputIterator, class _Distance>
  442. inline void _STLP_CALL advance(_InputIterator& __i, _Distance __n) {
  443.   __advance(__i, __n, _STLP_ITERATOR_CATEGORY(__i, _InputIterator));
  444. }
  445.  
  446. _STLP_END_NAMESPACE
  447.  
  448. # if defined (_STLP_DEBUG) && ! defined (_STLP_DEBUG_H)
  449. #  include <stl/debug/_debug.h>
  450. # endif
  451.  
  452. #endif /* _STLP_INTERNAL_ITERATOR_BASE_H */
  453.  
  454.  
  455. // Local Variables:
  456. // mode:C++
  457. // End:
  458.