Added std::distance.

4 files changed, 180 insertions, 6 deletions

diff --git a/include/iterator b/include/iterator
index 3dee58f..23d409f 100644
--- a/include/iterator
+++ b/include/iterator
@@ -166,32 +166,32 @@ class __wrapper_iterator
 template<typename _IteratorL, typename _IteratorR, typename _Container>
 inline bool
 operator==(const __wrapper_iterator<_IteratorL, _Container>& lhs,
-	       const __wrapper_iterator<_IteratorR, _Container>& rhs)
+           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)
+           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)
+           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)
+           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)
+          const __wrapper_iterator<_Iterator, _Container>& i)
 { return __wrapper_iterator<_Iterator, _Container>(i.base() + n); }
 
 // operator- : diff is supported on iterators.
@@ -199,9 +199,62 @@ operator+(typename __wrapper_iterator<_Iterator, _Container>::difference_type n,
 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)
+          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(); }
+
+}  // 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
 
diff --git a/tests/Android.mk b/tests/Android.mk
index b1efe6b..3d90faa 100644
--- a/tests/Android.mk
+++ b/tests/Android.mk
@@ -65,6 +65,7 @@ sources := \
     test_functional.cpp \
     test_ios_base.cpp \
     test_ios_pos_types.cpp \
+    test_iterator.cpp \
     test_limits.cpp \
     test_set.cpp \
     test_string.cpp \
diff --git a/tests/test_iterator.cpp b/tests/test_iterator.cpp
new file mode 100644
index 0000000..ed6e327
--- /dev/null
+++ b/tests/test_iterator.cpp
@@ -0,0 +1,118 @@
+/*
+ * Copyright (C) 2009 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.
+ */
+
+#include "../include/iterator"
+#ifndef ANDROID_ASTL_ITERATOR__
+#error "Wrong header included!!"
+#endif
+#include "common.h"
+
+namespace android {
+
+// Iterators used in tests.
+struct Input {
+    typedef std::input_iterator_tag iterator_category;
+    typedef int                     value_type;
+    typedef ptrdiff_t               difference_type;
+    typedef int*                    pointer;
+    typedef int&                    reference;
+};
+
+struct Forward {
+    typedef std::forward_iterator_tag iterator_category;
+    typedef int                       value_type;
+    typedef ptrdiff_t                 difference_type;
+    typedef int*                      pointer;
+    typedef int&                      reference;
+};
+
+struct Bidirectional {
+    typedef std::bidirectional_iterator_tag iterator_category;
+    typedef int                             value_type;
+    typedef ptrdiff_t                       difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+};
+
+struct Random {
+    typedef std::random_access_iterator_tag iterator_category;
+    typedef int                             value_type;
+    typedef ptrdiff_t                       difference_type;
+    typedef int*                            pointer;
+    typedef int&                            reference;
+};
+
+// Enum and helper functions to map an iterator tag to an int.
+enum Category {UNKNOWN, INPUT, FORWARD, BIDIRECTIONAL, RANDOM};
+
+template<typename _Category>
+Category category(_Category) {
+    return UNKNOWN;
+}
+
+template<>
+Category
+category<std::input_iterator_tag>(std::input_iterator_tag) {
+    return INPUT;
+}
+
+template<>
+Category
+category<std::forward_iterator_tag>(std::forward_iterator_tag) {
+    return FORWARD;
+}
+
+template<>
+Category
+category<std::bidirectional_iterator_tag>(std::bidirectional_iterator_tag) {
+    return BIDIRECTIONAL;
+}
+
+template<>
+Category
+category<std::random_access_iterator_tag>(std::random_access_iterator_tag) {
+    return RANDOM;
+}
+
+// Check if the custom method to get the category works as expected.
+bool testCategory()
+{
+    EXPECT_TRUE(category(android::iterator_category(Input())) == INPUT);
+    EXPECT_TRUE(category(android::iterator_category(Forward())) == FORWARD);
+    EXPECT_TRUE(category(android::iterator_category(Bidirectional())) == BIDIRECTIONAL);
+    EXPECT_TRUE(category(android::iterator_category(Random())) == RANDOM);
+    return true;
+}
+
+}  // namespace android
+
+int main(int argc, char **argv)
+{
+    FAIL_UNLESS(testCategory);
+    return kPassed;
+}
diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp
index cf3b7c7..122557b 100644
--- a/tests/test_vector.cpp
+++ b/tests/test_vector.cpp
@@ -328,6 +328,8 @@ bool testIterators()
         EXPECT_TRUE(vec1.begin() + 100 == vec1.end());
 
         EXPECT_TRUE(vec1.end() - vec1.begin() == 100);
+        EXPECT_TRUE(std::distance(vec1.begin(), vec1.end()) == 100);
+        EXPECT_TRUE(std::distance(vec1.end(), vec1.begin()) == -100);
 
         for (vector<int>::const_iterator i = vec1.begin();
              i != vec1.end(); ++i) {