Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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 <bits/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.