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