blob: 2f02ae179dbaf891abaf57d25219bffcf4e16a0f [file] [log] [blame]
/* -*- c++ -*- */
/*
* Copyright (C) 2010 The Android Open Source Project
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#ifndef ANDROID_ASTL_ITERATOR__
#define ANDROID_ASTL_ITERATOR__
#include <cstddef>
#include <type_traits.h>
// Iterators are a generalization of pointers to allow programs to
// work with different data structures (containers) in a uniform
// manner.
namespace std {
// Tags for the various iterator categories. Only input and forward
// iterators are supported.
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
template<typename _Category, typename _T, typename _Distance = ptrdiff_t,
typename _Pointer = _T*, typename _Reference = _T&>
struct iterator
{
typedef _Category iterator_category; // See tags above.
typedef _T value_type;
typedef _Distance difference_type; // Distance between iterators.
typedef _Pointer pointer;
typedef _Reference reference;
};
// Generic version, simply forward the typedef to the iterator
// template argument.
template<typename _Iterator>
struct iterator_traits
{
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
// Specialization for pointers and const pointers. These are random
// access iterators.
template<typename _T>
struct iterator_traits<_T*>
{
typedef random_access_iterator_tag iterator_category;
typedef _T value_type;
typedef ptrdiff_t difference_type;
typedef _T* pointer;
typedef _T& reference;
};
template<typename _T>
struct iterator_traits<const _T*>
{
typedef random_access_iterator_tag iterator_category;
typedef _T value_type;
typedef ptrdiff_t difference_type;
typedef const _T* pointer;
typedef const _T& reference;
};
// Wrap an interator that is not a class (e.g pointer) into an
// iterator that is a class.
// TODO: move this definition in the android ns.
template<typename _Iterator, typename _Container>
class __wrapper_iterator
{
public:
typedef _Iterator iterator_type;
typedef typename iterator_traits<_Iterator>::iterator_category
iterator_category;
typedef typename iterator_traits<_Iterator>::value_type value_type;
typedef typename iterator_traits<_Iterator>::difference_type
difference_type;
typedef typename iterator_traits<_Iterator>::reference reference;
typedef typename iterator_traits<_Iterator>::pointer pointer;
__wrapper_iterator() : mCurrent(_Iterator()) { }
explicit __wrapper_iterator(const _Iterator& i) : mCurrent(i) { }
// Allow iterator to const_iterator conversion
template<typename _Iter>
__wrapper_iterator(const __wrapper_iterator<_Iter, _Container>& i)
: mCurrent(i.base()) { }
// Forward iterator requirements
reference operator*() const { return *mCurrent; }
pointer operator->() const { return mCurrent; }
__wrapper_iterator& operator++() {
++mCurrent;
return *this;
}
__wrapper_iterator operator++(int) {
return __wrapper_iterator(mCurrent++);
}
// Bidirectional iterator requirements
__wrapper_iterator& operator--() {
--mCurrent;
return *this;
}
__wrapper_iterator operator--(int) {
return __wrapper_iterator(mCurrent--);
}
// Random access iterator requirements
reference operator[](const difference_type& n) const {
return mCurrent[n];
}
__wrapper_iterator& operator+=(const difference_type& n) {
mCurrent += n;
return *this;
}
__wrapper_iterator operator+(const difference_type& n) const {
return __wrapper_iterator(mCurrent + n);
}
__wrapper_iterator& operator-=(const difference_type& n) {
mCurrent -= n; return *this;
}
__wrapper_iterator operator-(const difference_type& n) const {
return __wrapper_iterator(mCurrent - n);
}
const _Iterator& base() const {
return mCurrent;
}
private:
_Iterator mCurrent;
};
// Forward iterator requirements
template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator==(const __wrapper_iterator<_IteratorL, _Container>& lhs,
const __wrapper_iterator<_IteratorR, _Container>& rhs)
{ return lhs.base() == rhs.base(); }
template<typename _Iterator, typename _Container>
inline bool
operator==(const __wrapper_iterator<_Iterator, _Container>& lhs,
const __wrapper_iterator<_Iterator, _Container>& rhs)
{ return lhs.base() == rhs.base(); }
template<typename _IteratorL, typename _IteratorR, typename _Container>
inline bool
operator!=(const __wrapper_iterator<_IteratorL, _Container>& lhs,
const __wrapper_iterator<_IteratorR, _Container>& rhs)
{ return lhs.base() != rhs.base(); }
template<typename _Iterator, typename _Container>
inline bool
operator!=(const __wrapper_iterator<_Iterator, _Container>& lhs,
const __wrapper_iterator<_Iterator, _Container>& rhs)
{ return lhs.base() != rhs.base(); }
// operator+ so we support 100 + iterator<>.
template<typename _Iterator, typename _Container>
inline __wrapper_iterator<_Iterator, _Container>
operator+(typename __wrapper_iterator<_Iterator, _Container>::difference_type n,
const __wrapper_iterator<_Iterator, _Container>& i)
{ return __wrapper_iterator<_Iterator, _Container>(i.base() + n); }
// operator- : diff is supported on iterators.
template<typename _Iterator, typename _Container>
inline typename __wrapper_iterator<_Iterator, _Container>::difference_type
operator-(const __wrapper_iterator<_Iterator, _Container>& lhs,
const __wrapper_iterator<_Iterator, _Container>& rhs)
{ return lhs.base() - rhs.base(); }
} // namespace std
namespace android {
// Shorthand to return the catogory of an iterator. Not part of the
// STL -> android namespace.
template<typename _Iterator>
inline typename std::iterator_traits<_Iterator>::iterator_category
iterator_category(const _Iterator&)
{ return typename std::iterator_traits<_Iterator>::iterator_category(); }
// Detect wrapper iterators.
template<typename _T>
struct is_wrapper_iterator: public std::false_type { };
template<typename _Iterator, typename _Container>
struct is_wrapper_iterator<std::__wrapper_iterator<_Iterator, _Container> >:
public std::true_type { };
// iter::base
//
// For wrapper iterators, android::iter::base(it) returns a pointer
// (it.base()) which is going to match implementation(s) that use
// pointers (e.g memmove).
template<typename _Iterator,
bool _IsWrapper = is_wrapper_iterator<_Iterator>::value>
struct iter {
static _Iterator base(_Iterator it) { return it; }
};
template<typename _Iterator>
struct iter<_Iterator, true> {
static typename _Iterator::iterator_type base(_Iterator it) {
return it.base();
}
};
} // namespace android
namespace std {
// Utilities: distance().
template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator first, _InputIterator last,
input_iterator_tag) // Match input iterators.
{
typename iterator_traits<_InputIterator>::difference_type dist = 0;
while (first != last) {
++first;
++dist;
}
return dist;
}
// Random access iterator: equivalent to mem pointer arithmetic.
template<typename _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
distance(_RandomAccessIterator first, _RandomAccessIterator last,
random_access_iterator_tag) // Match random access iterators.
{
return last - first;
}
/**
* Iterator arithmetic.
* @param first An input iterator.
* @param last An input iterator.
* @return The distance between them.
*/
template<typename _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator first, _InputIterator last)
{
// The correct implementation (above) will be called based on the
// iterator's category.
return distance(first, last, android::iterator_category(first));
}
} // namespace std
#endif // ANDROID_ASTL_ITERATOR__