Implementation of vector::erase.

Added std::copy, needed to shift the element down during an erase call.

Squashed commit of the following:

commit e534509bd709350e585f722e525eb2b63ade5831
Author: Nicolas Catania <niko@google.com>
Date:   Mon Feb 1 10:38:21 2010 -0800

    implementation of std::copy

commit f94dad514c54c66da85d9492452610285b5ee446
Author: Nicolas Catania <niko@google.com>
Date:   Sun Jan 31 14:58:15 2010 -0800

    Added support for erase.
    Erase element and erase range of elements.

3 files changed, 131 insertions, 2 deletions

diff --git a/include/algorithm b/include/algorithm
index e1930a1..bfa1c0d 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -32,6 +32,7 @@
 
 #include <cstddef>
 #include <cstring>
+#include <iterator>
 #include <type_traits.h>
 #ifndef ANDROID_ASTL_TYPE_TRAITS_H__
 #error "Wrong file included!"
@@ -45,6 +46,7 @@ namespace std {
 // - swap
 // - fill
 // - fill_n
+// - copy
 // - equal
 
 template<typename _T> inline const _T& min(const _T& left, const _T& right)
@@ -66,6 +68,63 @@ template<typename _T> inline void swap(_T& left, _T& right)
     right = tmp;
 }
 
+
+// Basic iterators, loop over the elements, we don't know how many
+// elements we need to copy. See the random access specialization
+// below.
+template<typename _Category>
+struct copy_move {
+    template<typename _InputIterator, typename _OutputIterator>
+    static _OutputIterator
+    __copy_move(_InputIterator first, _InputIterator last, _OutputIterator res) {
+        for (; first != last; ++res, ++first) {
+            *res = *first;
+        }
+        return res;
+    }
+};
+
+// For random access iterators, we know how many elements we have to
+// copy (random iterators support operator-).
+template<>
+struct copy_move<random_access_iterator_tag> {
+    template<typename _InputIterator, typename _OutputIterator>
+    static _OutputIterator
+    __copy_move(_InputIterator first, _InputIterator last, _OutputIterator res) {
+        typedef typename iterator_traits<_InputIterator>::difference_type
+                difference_type;
+
+        for (difference_type n = last - first; n > 0; --n) {
+            *res = *first;
+            ++first;
+            ++res;
+        }
+        return res;
+    }
+};
+
+// TODO: for simple case and wrapper iterator, should degrade to memmove.
+
+// copy elements in the range [first, last) into the range [result,
+// result + (last - first)) starting from first and proceeding to
+// last.
+//
+// For each non negative n < (last - first) performs:
+// *(result + n) = *(first + n)
+// @require result should not be in the [first, last) range.
+// @return result + (last - first)
+template<typename _InputIterator, typename _OutputIterator>
+inline _OutputIterator
+copy(_InputIterator first, _InputIterator last, _OutputIterator res) {
+    typedef typename iterator_traits<_InputIterator>::iterator_category
+            _Category;
+
+    return copy_move<_Category>::__copy_move(
+        android::iter<_InputIterator>::base(first),
+        android::iter<_InputIterator>::base(last),
+        res);
+}
+
 // fill the range [begin, end) with copies of value, return nothing.
 // fill_n the range [begin, begin + n) with copies of value, return
 // the pointer at begin + n.
@@ -73,7 +132,6 @@ template<typename _T> inline void swap(_T& left, _T& right)
 // TODO: fill and fill_n should take forward and output iterators for
 // begin and end params. Fix this when iterator are defined.
 
-
 template<bool> struct __fill
 {
     template<typename _T> static void fill(_T *begin, const _T *end,
@@ -236,5 +294,4 @@ inline bool equal(_InputIterator1 begin1, _InputIterator1 end1,
 
 }  // namespace std
 
-
 #endif
diff --git a/include/iterator b/include/iterator
index 23d409f..2f02ae1 100644
--- a/include/iterator
+++ b/include/iterator
@@ -31,6 +31,7 @@
 #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
@@ -92,10 +93,12 @@ struct iterator_traits<const _T*>
 
 // 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;
@@ -213,6 +216,32 @@ 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 {
diff --git a/include/vector b/include/vector
index bc9bbdd..051da1d 100644
--- a/include/vector
+++ b/include/vector
@@ -147,6 +147,18 @@ class vector
     // the internal buffer: you need to call reserve() to recover it.
     void pop_back();
 
+    // Remove the element pointed by the iterator.
+    // Expensive since the remaining elts must be shifted around.
+    // @param pos Iterator pointing to the elt to be removed.
+    // @return An iterator pointing to the next elt or end().
+    iterator erase(iterator pos);
+
+    // Remove a range of elements [first, last)
+    // @param first Iterator pointing to the first element to be removed.
+    // @param last Iterator pointing to one past the last element to be removed.
+    // @return An iterator pointing to the elt next to 'last' or end().
+    iterator erase(iterator first, iterator last);
+
     // Empty the vector on return. Release the internal buffer. Length
     // and capacity are both 0 on return. If you want to keep the
     // internal buffer around for reuse, call 'resize'/'erase' instead.
@@ -328,6 +340,37 @@ void vector<_T>::pop_back()
 }
 
 template<typename _T>
+typename vector<_T>::iterator
+vector<_T>::erase(iterator pos) {
+    if (mLength) {
+        std::copy(pos + 1, end(), pos);
+        --mLength;
+        if (!is_pod<value_type>::value) {
+            end()->~_T();
+        }
+    }
+    return pos;
+}
+
+template<typename _T>
+typename vector<_T>::iterator
+vector<_T>::erase(iterator first, iterator last) {
+    difference_type len = std::distance(first, last);
+    if (len > 0) {
+        last = std::copy(last, end(), first);
+
+        if (!is_pod<value_type>::value) {
+            while (last != end()) {
+                last->~_T();
+                ++last;
+            }
+        }
+        mLength -= len;
+    }
+    return first;
+}
+
+template<typename _T>
 void vector<_T>::clear()
 {
     if(mBegin)