1 /* 2 * 3 * Copyright 2009, The Android Open Source Project 4 * Copyright (c) 1994 5 * Hewlett-Packard Company 6 * 7 * Permission to use, copy, modify, distribute and sell this software 8 * and its documentation for any purpose is hereby granted without fee, 9 * provided that the above copyright notice appear in all copies and 10 * that both that copyright notice and this permission notice appear 11 * in supporting documentation. Hewlett-Packard Company makes no 12 * representations about the suitability of this software for any 13 * purpose. It is provided "as is" without express or implied warranty. 14 * 15 * 16 * Copyright (c) 1996-1998 17 * Silicon Graphics Computer Systems, Inc. 18 * 19 * Permission to use, copy, modify, distribute and sell this software 20 * and its documentation for any purpose is hereby granted without fee, 21 * provided that the above copyright notice appear in all copies and 22 * that both that copyright notice and this permission notice appear 23 * in supporting documentation. Silicon Graphics makes no 24 * representations about the suitability of this software for any 25 * purpose. It is provided "as is" without express or implied warranty. 26 */ 27 28 /* NOTE: This is an internal header file, included by other STL headers. 29 * You should not attempt to use it directly. 30 */ 31 32 #ifndef __SGI_STL_INTERNAL_ITERATOR_BASE_H 33 #define __SGI_STL_INTERNAL_ITERATOR_BASE_H 34 35 // This file contains all of the general iterator-related utilities. 36 // The internal file stl_iterator.h contains predefined iterators, 37 // such as front_insert_iterator and istream_iterator. 38 39 #include <concept_checks.h> 40 41 struct input_iterator_tag {}; 42 struct output_iterator_tag {}; 43 struct forward_iterator_tag : public input_iterator_tag {}; 44 struct bidirectional_iterator_tag : public forward_iterator_tag {}; 45 struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 46 47 // The base classes input_iterator, output_iterator, forward_iterator, 48 // bidirectional_iterator, and random_access_iterator are not part of 49 // the C++ standard. (They have been replaced by struct iterator.) 50 // They are included for backward compatibility with the HP STL. 51 52 template <class _Tp, class _Distance> struct input_iterator { 53 typedef input_iterator_tag iterator_category; 54 typedef _Tp value_type; 55 typedef _Distance difference_type; 56 typedef _Tp* pointer; 57 typedef _Tp& reference; 58 }; 59 60 struct output_iterator { 61 typedef output_iterator_tag iterator_category; 62 typedef void value_type; 63 typedef void difference_type; 64 typedef void pointer; 65 typedef void reference; 66 }; 67 68 template <class _Tp, class _Distance> struct forward_iterator { 69 typedef forward_iterator_tag iterator_category; 70 typedef _Tp value_type; 71 typedef _Distance difference_type; 72 typedef _Tp* pointer; 73 typedef _Tp& reference; 74 }; 75 76 77 template <class _Tp, class _Distance> struct bidirectional_iterator { 78 typedef bidirectional_iterator_tag iterator_category; 79 typedef _Tp value_type; 80 typedef _Distance difference_type; 81 typedef _Tp* pointer; 82 typedef _Tp& reference; 83 }; 84 85 template <class _Tp, class _Distance> struct random_access_iterator { 86 typedef random_access_iterator_tag iterator_category; 87 typedef _Tp value_type; 88 typedef _Distance difference_type; 89 typedef _Tp* pointer; 90 typedef _Tp& reference; 91 }; 92 93 template <class _Category, class _Tp, class _Distance = ptrdiff_t, 94 class _Pointer = _Tp*, class _Reference = _Tp&> 95 struct iterator { 96 typedef _Category iterator_category; 97 typedef _Tp value_type; 98 typedef _Distance difference_type; 99 typedef _Pointer pointer; 100 typedef _Reference reference; 101 }; 102 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; 110 }; 111 112 template <class _Tp> 113 struct iterator_traits<_Tp*> { 114 typedef random_access_iterator_tag iterator_category; 115 typedef _Tp value_type; 116 typedef ptrdiff_t difference_type; 117 typedef _Tp* pointer; 118 typedef _Tp& reference; 119 }; 120 121 template <class _Tp> 122 struct iterator_traits<const _Tp*> { 123 typedef random_access_iterator_tag iterator_category; 124 typedef _Tp value_type; 125 typedef ptrdiff_t difference_type; 126 typedef const _Tp* pointer; 127 typedef const _Tp& reference; 128 }; 129 130 // The overloaded functions iterator_category, distance_type, and 131 // value_type are not part of the C++ standard. (They have been 132 // replaced by struct iterator_traits.) They are included for 133 // backward compatibility with the HP STL. 134 135 // We introduce internal names for these functions. 136 137 template <class _Iter> 138 inline typename iterator_traits<_Iter>::iterator_category 139 __iterator_category(const _Iter&) 140 { 141 typedef typename iterator_traits<_Iter>::iterator_category _Category; 142 return _Category(); 143 } 144 145 template <class _Iter> 146 inline typename iterator_traits<_Iter>::difference_type* 147 __distance_type(const _Iter&) 148 { 149 return static_cast<typename iterator_traits<_Iter>::difference_type*>(0); 150 } 151 152 template <class _Iter> 153 inline typename iterator_traits<_Iter>::value_type* 154 __value_type(const _Iter&) 155 { 156 return static_cast<typename iterator_traits<_Iter>::value_type*>(0); 157 } 158 159 template <class _Iter> 160 inline typename iterator_traits<_Iter>::iterator_category 161 iterator_category(const _Iter& __i) { return __iterator_category(__i); } 162 163 164 template <class _Iter> 165 inline typename iterator_traits<_Iter>::difference_type* 166 distance_type(const _Iter& __i) { return __distance_type(__i); } 167 168 template <class _Iter> 169 inline typename iterator_traits<_Iter>::value_type* 170 value_type(const _Iter& __i) { return __value_type(__i); } 171 172 #define __ITERATOR_CATEGORY(__i) __iterator_category(__i) 173 #define __DISTANCE_TYPE(__i) __distance_type(__i) 174 #define __VALUE_TYPE(__i) __value_type(__i) 175 176 template <class _InputIterator, class _Distance> 177 inline void __distance(_InputIterator __first, _InputIterator __last, 178 _Distance& __n, input_iterator_tag) 179 { 180 while (__first != __last) { ++__first; ++__n; } 181 } 182 183 template <class _RandomAccessIterator, class _Distance> 184 inline void __distance(_RandomAccessIterator __first, 185 _RandomAccessIterator __last, 186 _Distance& __n, random_access_iterator_tag) 187 { 188 __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); 189 __n += __last - __first; 190 } 191 192 template <class _InputIterator, class _Distance> 193 inline void distance(_InputIterator __first, 194 _InputIterator __last, _Distance& __n) 195 { 196 __STL_REQUIRES(_InputIterator, _InputIterator); 197 __distance(__first, __last, __n, iterator_category(__first)); 198 } 199 200 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 201 202 template <class _InputIterator> 203 inline typename iterator_traits<_InputIterator>::difference_type 204 __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag) 205 { 206 typename iterator_traits<_InputIterator>::difference_type __n = 0; 207 while (__first != __last) { 208 ++__first; ++__n; 209 } 210 return __n; 211 } 212 213 template <class _RandomAccessIterator> 214 inline typename iterator_traits<_RandomAccessIterator>::difference_type 215 __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, 216 random_access_iterator_tag) { 217 __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); 218 return __last - __first; 219 } 220 221 template <class _InputIterator> 222 inline typename iterator_traits<_InputIterator>::difference_type 223 distance(_InputIterator __first, _InputIterator __last) { 224 typedef typename iterator_traits<_InputIterator>::iterator_category 225 _Category; 226 __STL_REQUIRES(_InputIterator, _InputIterator); 227 return __distance(__first, __last, _Category()); 228 } 229 230 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 231 232 template <class _InputIter, class _Distance> 233 inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) { 234 while (__n--) ++__i; 235 } 236 237 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 238 #pragma set woff 1183 239 #endif 240 241 template <class _BidirectionalIterator, class _Distance> 242 inline void __advance(_BidirectionalIterator& __i, _Distance __n, 243 bidirectional_iterator_tag) { 244 __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator); 245 if (__n >= 0) 246 while (__n--) ++__i; 247 else 248 while (__n++) --__i; 249 } 250 251 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 252 #pragma reset woff 1183 253 #endif 254 255 template <class _RandomAccessIterator, class _Distance> 256 inline void __advance(_RandomAccessIterator& __i, _Distance __n, 257 random_access_iterator_tag) { 258 __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); 259 __i += __n; 260 } 261 262 template <class _InputIterator, class _Distance> 263 inline void advance(_InputIterator& __i, _Distance __n) { 264 __STL_REQUIRES(_InputIterator, _InputIterator); 265 __advance(__i, __n, iterator_category(__i)); 266 } 267 268 #endif /* __SGI_STL_INTERNAL_ITERATOR_BASE_H */ 269 270 271 272 // Local Variables: 273 // mode:C++ 274 // End: 275