Basic implementation of iterators.

Added basic iterator support for strings.

3 files changed, 236 insertions, 3 deletions

diff --git a/include/iterator b/include/iterator
new file mode 100644
index 0000000..b983a1c
--- /dev/null
+++ b/include/iterator
@@ -0,0 +1,192 @@
+/* -*- 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>
+
+// 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.
+template<typename _Iterator, typename _Container>
+class __wrapper_iterator
+{
+  public:
+    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(); }
+
+}  // namespace std
+
+#endif  // ANDROID_ASTL_ITERATOR__
diff --git a/include/string b/include/string
index f1cfe93..6215bf3 100644
--- a/include/string
+++ b/include/string
@@ -31,6 +31,7 @@
 #define ANDROID_ASTL_STRING__
 
 #include <cstddef>
+#include <iterator>
 
 namespace std {
 
@@ -47,14 +48,21 @@ namespace std {
 // allocation parameter.
 // . The implementation is not optimized in any way (no copy on write support),
 // temporary instance may be expensive.
-// . Currently there is no support for iterators.
+// . Currently there is limited support for iterators.
 //
 
 class string
 {
   public:
-    typedef size_t size_type;
-    typedef char   value_type;
+    typedef size_t            size_type;
+    typedef char              value_type;
+    typedef ptrdiff_t         difference_type;
+    typedef value_type&       reference;
+    typedef const value_type& const_reference;
+    typedef value_type*       pointer;
+    typedef const value_type* const_pointer;
+    typedef __wrapper_iterator<pointer,string>  iterator;
+    typedef __wrapper_iterator<const_pointer,string> const_iterator;
 
     static const size_type npos = static_cast<size_type>(-1);
 
@@ -241,6 +249,12 @@ class string
     // starting position.
     size_type find(const value_type *str, size_type pos = 0) const;
 
+    // Iterators
+    iterator begin() {return iterator(mData);}
+    const_iterator begin() const {return const_iterator(mData);}
+    iterator end() {return iterator(mData + mLength);}
+    const_iterator end() const {return const_iterator(mData + mLength);}
+
   private:
     bool SafeMalloc(size_type n);
     void SafeRealloc(size_type n);
diff --git a/tests/test_string.cpp b/tests/test_string.cpp
index bd69a46..60c02aa 100644
--- a/tests/test_string.cpp
+++ b/tests/test_string.cpp
@@ -867,6 +867,31 @@ bool testErase()
   return true;
 }
 
+// Checks an iterator can be cast to a const one.
+bool testConstIterator()
+{
+    string s("a string");
+    string::iterator i = s.begin();
+    string::const_iterator ci = s.begin();
+    return true;
+}
+
+bool testForwardIterator()
+{
+    string s("a string");
+    char chars[] = "a string";
+    string::iterator iter = s.begin();
+    for (int i = 0; iter != s.end(); ++i) {
+        EXPECT_TRUE(*iter == chars[i]);
+        ++iter;
+    }
+    EXPECT_TRUE(iter == s.end());
+
+    string empty;
+    EXPECT_TRUE(empty.begin() == empty.end());
+    return true;
+}
+
 }  // namespace android
 
 int main(int argc, char **argv)
@@ -891,5 +916,7 @@ int main(int argc, char **argv)
     FAIL_UNLESS(testCapacity);
     FAIL_UNLESS(testClear);
     FAIL_UNLESS(testErase);
+    FAIL_UNLESS(testConstIterator);
+    FAIL_UNLESS(testForwardIterator);
     return kPassed;
 }