1 /* -*- c++ -*- */ 2 /* 3 * Copyright (C) 2010 The Android Open Source Project 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in 13 * the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 20 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS 23 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 #ifndef ANDROID_ASTL_ITERATOR__ 31 #define ANDROID_ASTL_ITERATOR__ 32 33 #include <cstddef> 34 #include <type_traits.h> 35 36 // Iterators are a generalization of pointers to allow programs to 37 // work with different data structures (containers) in a uniform 38 // manner. 39 namespace std { 40 41 // Tags for the various iterator categories. Only input and forward 42 // iterators are supported. 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 template<typename _Category, typename _T, typename _Distance = ptrdiff_t, 50 typename _Pointer = _T*, typename _Reference = _T&> 51 struct iterator 52 { 53 typedef _Category iterator_category; // See tags above. 54 typedef _T value_type; 55 typedef _Distance difference_type; // Distance between iterators. 56 typedef _Pointer pointer; 57 typedef _Reference reference; 58 }; 59 60 // Generic version, simply forward the typedef to the iterator 61 // template argument. 62 template<typename _Iterator> 63 struct iterator_traits 64 { 65 typedef typename _Iterator::iterator_category iterator_category; 66 typedef typename _Iterator::value_type value_type; 67 typedef typename _Iterator::difference_type difference_type; 68 typedef typename _Iterator::pointer pointer; 69 typedef typename _Iterator::reference reference; 70 }; 71 72 // Specialization for pointers and const pointers. These are random 73 // access iterators. 74 template<typename _T> 75 struct iterator_traits<_T*> 76 { 77 typedef random_access_iterator_tag iterator_category; 78 typedef _T value_type; 79 typedef ptrdiff_t difference_type; 80 typedef _T* pointer; 81 typedef _T& reference; 82 }; 83 84 template<typename _T> 85 struct iterator_traits<const _T*> 86 { 87 typedef random_access_iterator_tag iterator_category; 88 typedef _T value_type; 89 typedef ptrdiff_t difference_type; 90 typedef const _T* pointer; 91 typedef const _T& reference; 92 }; 93 94 // Wrap an interator that is not a class (e.g pointer) into an 95 // iterator that is a class. 96 // TODO: move this definition in the android ns. 97 template<typename _Iterator, typename _Container> 98 class __wrapper_iterator 99 { 100 public: 101 typedef _Iterator iterator_type; 102 typedef typename iterator_traits<_Iterator>::iterator_category 103 iterator_category; 104 typedef typename iterator_traits<_Iterator>::value_type value_type; 105 typedef typename iterator_traits<_Iterator>::difference_type 106 difference_type; 107 typedef typename iterator_traits<_Iterator>::reference reference; 108 typedef typename iterator_traits<_Iterator>::pointer pointer; 109 110 __wrapper_iterator() : mCurrent(_Iterator()) { } 111 explicit __wrapper_iterator(const _Iterator& i) : mCurrent(i) { } 112 113 // Allow iterator to const_iterator conversion 114 template<typename _Iter> 115 __wrapper_iterator(const __wrapper_iterator<_Iter, _Container>& i) 116 : mCurrent(i.base()) { } 117 118 // Forward iterator requirements 119 reference operator*() const { return *mCurrent; } 120 pointer operator->() const { return mCurrent; } 121 __wrapper_iterator& operator++() { 122 ++mCurrent; 123 return *this; 124 } 125 __wrapper_iterator operator++(int) { 126 return __wrapper_iterator(mCurrent++); 127 } 128 129 // Bidirectional iterator requirements 130 __wrapper_iterator& operator--() { 131 --mCurrent; 132 return *this; 133 } 134 __wrapper_iterator operator--(int) { 135 return __wrapper_iterator(mCurrent--); 136 } 137 138 // Random access iterator requirements 139 reference operator[](const difference_type& n) const { 140 return mCurrent[n]; 141 } 142 143 __wrapper_iterator& operator+=(const difference_type& n) { 144 mCurrent += n; 145 return *this; 146 } 147 148 __wrapper_iterator operator+(const difference_type& n) const { 149 return __wrapper_iterator(mCurrent + n); 150 } 151 152 __wrapper_iterator& operator-=(const difference_type& n) { 153 mCurrent -= n; return *this; 154 } 155 156 __wrapper_iterator operator-(const difference_type& n) const { 157 return __wrapper_iterator(mCurrent - n); 158 } 159 160 const _Iterator& base() const { 161 return mCurrent; 162 } 163 164 private: 165 _Iterator mCurrent; 166 }; 167 168 // Forward iterator requirements 169 template<typename _IteratorL, typename _IteratorR, typename _Container> 170 inline bool 171 operator==(const __wrapper_iterator<_IteratorL, _Container>& lhs, 172 const __wrapper_iterator<_IteratorR, _Container>& rhs) 173 { return lhs.base() == rhs.base(); } 174 175 template<typename _Iterator, typename _Container> 176 inline bool 177 operator==(const __wrapper_iterator<_Iterator, _Container>& lhs, 178 const __wrapper_iterator<_Iterator, _Container>& rhs) 179 { return lhs.base() == rhs.base(); } 180 181 template<typename _IteratorL, typename _IteratorR, typename _Container> 182 inline bool 183 operator!=(const __wrapper_iterator<_IteratorL, _Container>& lhs, 184 const __wrapper_iterator<_IteratorR, _Container>& rhs) 185 { return lhs.base() != rhs.base(); } 186 187 template<typename _Iterator, typename _Container> 188 inline bool 189 operator!=(const __wrapper_iterator<_Iterator, _Container>& lhs, 190 const __wrapper_iterator<_Iterator, _Container>& rhs) 191 { return lhs.base() != rhs.base(); } 192 193 // operator+ so we support 100 + iterator<>. 194 template<typename _Iterator, typename _Container> 195 inline __wrapper_iterator<_Iterator, _Container> 196 operator+(typename __wrapper_iterator<_Iterator, _Container>::difference_type n, 197 const __wrapper_iterator<_Iterator, _Container>& i) 198 { return __wrapper_iterator<_Iterator, _Container>(i.base() + n); } 199 200 // operator- : diff is supported on iterators. 201 202 template<typename _Iterator, typename _Container> 203 inline typename __wrapper_iterator<_Iterator, _Container>::difference_type 204 operator-(const __wrapper_iterator<_Iterator, _Container>& lhs, 205 const __wrapper_iterator<_Iterator, _Container>& rhs) 206 { return lhs.base() - rhs.base(); } 207 208 } // namespace std 209 210 namespace android { 211 212 // Shorthand to return the catogory of an iterator. Not part of the 213 // STL -> android namespace. 214 template<typename _Iterator> 215 inline typename std::iterator_traits<_Iterator>::iterator_category 216 iterator_category(const _Iterator&) 217 { return typename std::iterator_traits<_Iterator>::iterator_category(); } 218 219 // Detect wrapper iterators. 220 template<typename _T> 221 struct is_wrapper_iterator: public std::false_type { }; 222 223 template<typename _Iterator, typename _Container> 224 struct is_wrapper_iterator<std::__wrapper_iterator<_Iterator, _Container> >: 225 public std::true_type { }; 226 227 // iter::base 228 // 229 // For wrapper iterators, android::iter::base(it) returns a pointer 230 // (it.base()) which is going to match implementation(s) that use 231 // pointers (e.g memmove). 232 template<typename _Iterator, 233 bool _IsWrapper = is_wrapper_iterator<_Iterator>::value> 234 struct iter { 235 static _Iterator base(_Iterator it) { return it; } 236 }; 237 238 template<typename _Iterator> 239 struct iter<_Iterator, true> { 240 static typename _Iterator::iterator_type base(_Iterator it) { 241 return it.base(); 242 } 243 }; 244 245 } // namespace android 246 247 namespace std { 248 249 // Utilities: distance(). 250 251 template<typename _InputIterator> 252 inline typename iterator_traits<_InputIterator>::difference_type 253 distance(_InputIterator first, _InputIterator last, 254 input_iterator_tag) // Match input iterators. 255 { 256 typename iterator_traits<_InputIterator>::difference_type dist = 0; 257 while (first != last) { 258 ++first; 259 ++dist; 260 } 261 return dist; 262 } 263 264 // Random access iterator: equivalent to mem pointer arithmetic. 265 template<typename _RandomAccessIterator> 266 inline typename iterator_traits<_RandomAccessIterator>::difference_type 267 distance(_RandomAccessIterator first, _RandomAccessIterator last, 268 random_access_iterator_tag) // Match random access iterators. 269 { 270 return last - first; 271 } 272 273 /** 274 * Iterator arithmetic. 275 * @param first An input iterator. 276 * @param last An input iterator. 277 * @return The distance between them. 278 */ 279 template<typename _InputIterator> 280 inline typename iterator_traits<_InputIterator>::difference_type 281 distance(_InputIterator first, _InputIterator last) 282 { 283 // The correct implementation (above) will be called based on the 284 // iterator's category. 285 return distance(first, last, android::iterator_category(first)); 286 } 287 288 } // namespace std 289 290 #endif // ANDROID_ASTL_ITERATOR__ 291
