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. 39namespace std { 40 41// Tags for the various iterator categories. Only input and forward 42// iterators are supported. 43struct input_iterator_tag {}; 44struct output_iterator_tag {}; 45struct forward_iterator_tag : public input_iterator_tag {}; 46struct bidirectional_iterator_tag : public forward_iterator_tag {}; 47struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 48 49template<typename _Category, typename _T, typename _Distance = ptrdiff_t, 50 typename _Pointer = _T*, typename _Reference = _T&> 51struct 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. 62template<typename _Iterator> 63struct 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. 74template<typename _T> 75struct 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 84template<typename _T> 85struct 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. 97template<typename _Iterator, typename _Container> 98class __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 169template<typename _IteratorL, typename _IteratorR, typename _Container> 170inline bool 171operator==(const __wrapper_iterator<_IteratorL, _Container>& lhs, 172 const __wrapper_iterator<_IteratorR, _Container>& rhs) 173{ return lhs.base() == rhs.base(); } 174 175template<typename _Iterator, typename _Container> 176inline bool 177operator==(const __wrapper_iterator<_Iterator, _Container>& lhs, 178 const __wrapper_iterator<_Iterator, _Container>& rhs) 179{ return lhs.base() == rhs.base(); } 180 181template<typename _IteratorL, typename _IteratorR, typename _Container> 182inline bool 183operator!=(const __wrapper_iterator<_IteratorL, _Container>& lhs, 184 const __wrapper_iterator<_IteratorR, _Container>& rhs) 185{ return lhs.base() != rhs.base(); } 186 187template<typename _Iterator, typename _Container> 188inline bool 189operator!=(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<>. 194template<typename _Iterator, typename _Container> 195inline __wrapper_iterator<_Iterator, _Container> 196operator+(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 202template<typename _Iterator, typename _Container> 203inline typename __wrapper_iterator<_Iterator, _Container>::difference_type 204operator-(const __wrapper_iterator<_Iterator, _Container>& lhs, 205 const __wrapper_iterator<_Iterator, _Container>& rhs) 206{ return lhs.base() - rhs.base(); } 207 208} // namespace std 209 210namespace android { 211 212// Shorthand to return the catogory of an iterator. Not part of the 213// STL -> android namespace. 214template<typename _Iterator> 215inline typename std::iterator_traits<_Iterator>::iterator_category 216iterator_category(const _Iterator&) 217{ return typename std::iterator_traits<_Iterator>::iterator_category(); } 218 219// Detect wrapper iterators. 220template<typename _T> 221struct is_wrapper_iterator: public std::false_type { }; 222 223template<typename _Iterator, typename _Container> 224struct 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). 232template<typename _Iterator, 233 bool _IsWrapper = is_wrapper_iterator<_Iterator>::value> 234struct iter { 235 static _Iterator base(_Iterator it) { return it; } 236}; 237 238template<typename _Iterator> 239struct iter<_Iterator, true> { 240 static typename _Iterator::iterator_type base(_Iterator it) { 241 return it.base(); 242 } 243}; 244 245} // namespace android 246 247namespace std { 248 249// Utilities: distance(). 250 251template<typename _InputIterator> 252inline typename iterator_traits<_InputIterator>::difference_type 253distance(_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. 265template<typename _RandomAccessIterator> 266inline typename iterator_traits<_RandomAccessIterator>::difference_type 267distance(_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 */ 279template<typename _InputIterator> 280inline typename iterator_traits<_InputIterator>::difference_type 281distance(_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