iterator revision b6e436eb559cdcf43e21f6617dc0a3d90c7b89b6 
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
35// Iterators are a generalization of pointers to allow programs to
36// work with different data structures (containers) in a uniform
37// manner.
38namespace std {
39
40// Tags for the various iterator categories. Only input and forward
41// iterators are supported.
42struct input_iterator_tag {};
43struct output_iterator_tag {};
44struct forward_iterator_tag : public input_iterator_tag {};
45struct bidirectional_iterator_tag : public forward_iterator_tag {};
46struct random_access_iterator_tag : public bidirectional_iterator_tag {};
47
48template<typename _Category, typename _T, typename _Distance = ptrdiff_t,
49         typename _Pointer = _T*, typename _Reference = _T&>
50struct iterator
51{
52    typedef _Category  iterator_category;  // See tags above.
53    typedef _T         value_type;
54    typedef _Distance  difference_type;  // Distance between iterators.
55    typedef _Pointer   pointer;
56    typedef _Reference reference;
57};
58
59// Generic version, simply forward the typedef to the iterator
60// template argument.
61template<typename _Iterator>
62struct iterator_traits
63{
64    typedef typename _Iterator::iterator_category iterator_category;
65    typedef typename _Iterator::value_type        value_type;
66    typedef typename _Iterator::difference_type   difference_type;
67    typedef typename _Iterator::pointer           pointer;
68    typedef typename _Iterator::reference         reference;
69};
70
71// Specialization for pointers and const pointers. These are random
72// access iterators.
73template<typename _T>
74struct iterator_traits<_T*>
75{
76    typedef random_access_iterator_tag iterator_category;
77    typedef _T                         value_type;
78    typedef ptrdiff_t                  difference_type;
79    typedef _T*                        pointer;
80    typedef _T&                        reference;
81};
82
83template<typename _T>
84struct iterator_traits<const _T*>
85{
86    typedef random_access_iterator_tag iterator_category;
87    typedef _T                         value_type;
88    typedef ptrdiff_t                  difference_type;
89    typedef const _T*                  pointer;
90    typedef const _T&                  reference;
91};
92
93// Wrap an interator that is not a class (e.g pointer) into an
94// iterator that is a class.
95template<typename _Iterator, typename _Container>
96class __wrapper_iterator
97{
98  public:
99    typedef typename iterator_traits<_Iterator>::iterator_category
100    iterator_category;
101    typedef typename iterator_traits<_Iterator>::value_type value_type;
102    typedef typename iterator_traits<_Iterator>::difference_type
103    difference_type;
104    typedef typename iterator_traits<_Iterator>::reference reference;
105    typedef typename iterator_traits<_Iterator>::pointer pointer;
106
107    __wrapper_iterator() : mCurrent(_Iterator()) { }
108    explicit __wrapper_iterator(const _Iterator& i) : mCurrent(i) { }
109
110    // Allow iterator to const_iterator conversion
111    template<typename _Iter>
112    __wrapper_iterator(const __wrapper_iterator<_Iter, _Container>& i)
113        : mCurrent(i.base()) { }
114
115    // Forward iterator requirements
116    reference operator*() const { return *mCurrent; }
117    pointer operator->() const { return mCurrent; }
118    __wrapper_iterator& operator++() {
119        ++mCurrent;
120        return *this;
121    }
122    __wrapper_iterator operator++(int) {
123        return __wrapper_iterator(mCurrent++);
124    }
125
126    // Bidirectional iterator requirements
127    __wrapper_iterator& operator--() {
128        --mCurrent;
129        return *this;
130    }
131    __wrapper_iterator operator--(int) {
132        return __wrapper_iterator(mCurrent--);
133    }
134
135    // Random access iterator requirements
136    reference operator[](const difference_type& n) const {
137        return mCurrent[n];
138    }
139
140    __wrapper_iterator& operator+=(const difference_type& n) {
141        mCurrent += n;
142        return *this;
143    }
144
145    __wrapper_iterator operator+(const difference_type& n) const {
146        return __wrapper_iterator(mCurrent + n);
147    }
148
149    __wrapper_iterator& operator-=(const difference_type& n) {
150        mCurrent -= n; return *this;
151    }
152
153    __wrapper_iterator operator-(const difference_type& n) const {
154        return __wrapper_iterator(mCurrent - n);
155    }
156
157    const _Iterator& base() const {
158        return mCurrent;
159    }
160
161  private:
162    _Iterator mCurrent;
163};
164
165// Forward iterator requirements
166template<typename _IteratorL, typename _IteratorR, typename _Container>
167inline bool
168operator==(const __wrapper_iterator<_IteratorL, _Container>& lhs,
169           const __wrapper_iterator<_IteratorR, _Container>& rhs)
170{ return lhs.base() == rhs.base(); }
171
172template<typename _Iterator, typename _Container>
173inline bool
174operator==(const __wrapper_iterator<_Iterator, _Container>& lhs,
175           const __wrapper_iterator<_Iterator, _Container>& rhs)
176{ return lhs.base() == rhs.base(); }
177
178template<typename _IteratorL, typename _IteratorR, typename _Container>
179inline bool
180operator!=(const __wrapper_iterator<_IteratorL, _Container>& lhs,
181           const __wrapper_iterator<_IteratorR, _Container>& rhs)
182{ return lhs.base() != rhs.base(); }
183
184template<typename _Iterator, typename _Container>
185inline bool
186operator!=(const __wrapper_iterator<_Iterator, _Container>& lhs,
187           const __wrapper_iterator<_Iterator, _Container>& rhs)
188{ return lhs.base() != rhs.base(); }
189
190// operator+ so we support 100 + iterator<>.
191template<typename _Iterator, typename _Container>
192inline __wrapper_iterator<_Iterator, _Container>
193operator+(typename __wrapper_iterator<_Iterator, _Container>::difference_type n,
194          const __wrapper_iterator<_Iterator, _Container>& i)
195{ return __wrapper_iterator<_Iterator, _Container>(i.base() + n); }
196
197// operator- : diff is supported on iterators.
198
199template<typename _Iterator, typename _Container>
200inline typename __wrapper_iterator<_Iterator, _Container>::difference_type
201operator-(const __wrapper_iterator<_Iterator, _Container>& lhs,
202          const __wrapper_iterator<_Iterator, _Container>& rhs)
203{ return lhs.base() - rhs.base(); }
204
205}  // namespace std
206
207namespace android {
208
209// Shorthand to return the catogory of an iterator. Not part of the
210// STL -> android namespace.
211template<typename _Iterator>
212inline typename std::iterator_traits<_Iterator>::iterator_category
213iterator_category(const _Iterator&)
214{ return typename std::iterator_traits<_Iterator>::iterator_category(); }
215
216}  // namespace android
217
218namespace std {
219
220// Utilities: distance().
221
222template<typename _InputIterator>
223inline typename iterator_traits<_InputIterator>::difference_type
224distance(_InputIterator first, _InputIterator last,
225         input_iterator_tag)  // Match input iterators.
226{
227    typename iterator_traits<_InputIterator>::difference_type dist = 0;
228    while (first != last) {
229        ++first;
230        ++dist;
231    }
232    return dist;
233}
234
235// Random access iterator: equivalent to mem pointer arithmetic.
236template<typename _RandomAccessIterator>
237inline typename iterator_traits<_RandomAccessIterator>::difference_type
238distance(_RandomAccessIterator first, _RandomAccessIterator last,
239         random_access_iterator_tag)  // Match random access iterators.
240{
241    return last - first;
242}
243
244/**
245 * Iterator arithmetic.
246 * @param first An input iterator.
247 * @param last  An input iterator.
248 * @return The distance between them.
249 */
250template<typename _InputIterator>
251inline typename iterator_traits<_InputIterator>::difference_type
252distance(_InputIterator first, _InputIterator last)
253{
254    // The correct implementation (above) will be called based on the
255    // iterator's category.
256    return distance(first, last, android::iterator_category(first));
257}
258
259}  // namespace std
260
261#endif  // ANDROID_ASTL_ITERATOR__
262