7 files changed, 230 insertions, 4 deletions

diff --git a/include/list b/include/list
index d6583d2..a2fdc9b 100644
--- a/include/list
+++ b/include/list
@@ -171,10 +171,10 @@ class list {
     void clear();
 
     // Element access.
-    reference front() { return *begin(); }
-    const_reference front() const { return *begin(); }
-    reference back() { return *(end()--); }
-    const_reference back() const { return *(end()--); }
+    reference front() { return *iterator(mHead.mNext); }
+    const_reference front() const { return *iterator(mHead.mNext); }
+    reference back() { return *iterator(mHead.mPrev); }
+    const_reference back() const { return *iterator(mHead.mPrev); }
 
     // Iterators.
     iterator begin() { return iterator(mHead.mNext); }
@@ -187,6 +187,13 @@ class list {
     void push_front(const value_type& elt) { insert(begin(), elt); }
     void push_back(const value_type& elt) { insert(end(), elt); }
 
+    // Removes first element. Invalidated the iterators/references to begin.
+    void pop_front() { eraseAtPos(iterator(mHead.mNext)); }
+
+    // Removes last element. Invalidated the iterators/references to
+    // the last element.
+    void pop_back() { eraseAtPos(iterator(mHead.mPrev)); }
+
     bool empty() const { return mLength == 0; }
 
     // @eturn the number of elements in the list.
@@ -201,12 +208,28 @@ class list {
     // @return an iterator that points to the inserted element.
     iterator insert(iterator pos, const value_type& elt);
 
+    // Remove the element pointed by the iterator. Constant in time,
+    // calls once to _T's destructor.
+    // @param pos Iterator pointing to the elt to be removed.
+    // @return An iterator pointing to the next elt or end().
+    iterator erase(iterator position);
+
+    // 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);
+
   private:
     void init() {
         mHead.mNext = &mHead;
         mHead.mPrev = &mHead;
         mLength = 0;
     }
+
+    // Erase, don't return anything.
+    void eraseAtPos(iterator pos);
+
     size_type mLength;
     // mHead does not contain any data, it represents end().
     android::ListNodeBase mHead;
@@ -238,6 +261,32 @@ typename list<_T>::iterator list<_T>::insert(iterator pos, const value_type& elt
     }
 }
 
+template<typename _T>
+typename list<_T>::iterator list<_T>::erase(iterator pos) {
+    iterator res = iterator(pos.mNode->mNext);
+    eraseAtPos(pos);
+    return res;
+}
+
+template<typename _T>
+typename list<_T>::iterator list<_T>::erase(iterator first, iterator last) {
+    while (first != last) {
+        first = erase(first);  // erase returns an iterator to the next elt.
+    }
+    return last;
+}
+
+template<typename _T>
+void list<_T>::eraseAtPos(iterator pos) {
+    if (pos.mNode != &mHead) {
+        pos.mNode->unhook();
+        android::ListNode<_T>* node =
+                static_cast<android::ListNode<_T>*>(pos.mNode);
+        delete node;
+        --mLength;
+    }
+}
+
 }  // namespace std
 
 #endif  // ANDROID_ASTL_LIST__
diff --git a/include/string b/include/string
index 428d1db..9f9d146 100644
--- a/include/string
+++ b/include/string
@@ -30,6 +30,7 @@
 #ifndef ANDROID_ASTL_STRING__
 #define ANDROID_ASTL_STRING__
 
+#include <algorithm>
 #include <cstddef>
 #include <iterator>
 #include <char_traits.h>
@@ -161,6 +162,9 @@ class string
     string& append(const value_type *str, size_type pos, size_type n);
     string& append(const string& str);
 
+    template<typename _InputIterator>
+    string& append(_InputIterator first, _InputIterator last);
+
     // Comparison.
     // @return 0 if this==other, < 0 if this < other and > 0 if this > other.
     // Don't assume the values are -1, 0, 1
@@ -325,6 +329,37 @@ void swap(string& lhs, string& rhs);
 // I/O
 ostream& operator<<(ostream& os, const string& str);
 
+
+// Specialization of append(iterator, iterator) using string iterators
+// (const and non const).
+template<>
+string& string::append<__wrapper_iterator<const char *,string> >(
+    __wrapper_iterator<const char *,string> first,
+    __wrapper_iterator<const char *,string> last);
+template<>
+string& string::append<__wrapper_iterator<char *,string> >(
+    __wrapper_iterator<char *,string> first,
+    __wrapper_iterator<char *,string> last);
+
+// append(iterator,iterator) default implementation.
+template<typename _InputIterator>
+string& string::append(_InputIterator first, _InputIterator last) {
+    size_type dist = std::distance(first, last);
+    size_type new_len = mLength + dist;
+    if (new_len <= mLength) {
+        return *this;  // 0 / overflow
+    }
+    reserve(new_len);
+    if (new_len > mCapacity) {
+        return *this;  // memory allocation failed.
+    }
+    std::copy(first, last, mData + mLength);
+    mLength = new_len;
+    mData[mLength] = '\0';
+    return *this;
+}
+
+
 }  // namespace std
 
 #endif  // ANDROID_ASTL_STRING__
diff --git a/include/vector b/include/vector
index 051da1d..b17cc70 100644
--- a/include/vector
+++ b/include/vector
@@ -132,6 +132,13 @@ class vector
     // @return A reference to the element.
     reference operator[](size_type index) { return *(mBegin + index); }
 
+    // 'at' is similar to operator[] except that it does check bounds.
+    const_reference at(const size_type index) const
+    { return index < mLength ? *( mBegin + index) : sDummy; }
+
+    reference at(const size_type index)
+    { return index < mLength ? *( mBegin + index) : sDummy; }
+
     iterator begin() { return iterator(mBegin); }
     iterator end() { return iterator(mBegin + mLength); }
 
@@ -217,6 +224,7 @@ class vector
     pointer mBegin;
     size_type mCapacity;
     size_type mLength;
+    static value_type sDummy;  // at() doen't throw exception and returns mDummy.
     static const size_type kExponentialFactor = 2;
     static const size_type kExponentialLimit = 256;
     static const size_type kLinearIncrement = 256;
@@ -234,6 +242,7 @@ class vector
 //
 // Invariant: mLength <= mCapacity <= max_size()
 
+
 template<typename _T>
 vector<_T>::vector()
         :mBegin(NULL), mCapacity(0), mLength(0) { }
@@ -490,6 +499,9 @@ void vector<_T>::deallocate()
     free(mBegin);
 }
 
+// Dummy element returned when at() is out of bound.
+template<typename _T> _T vector<_T>::sDummy;
+
 }  // namespace std
 
 #endif  // ANDROID_ASTL_VECTOR__
diff --git a/src/string.cpp b/src/string.cpp
index 5c04c8e..930e77d 100644
--- a/src/string.cpp
+++ b/src/string.cpp
@@ -337,6 +337,22 @@ string& string::append(const string& str)
     return *this;
 }
 
+// Specialization to append from other strings' iterators.
+template<>
+string& string::append<__wrapper_iterator<const char *,string> >(
+    __wrapper_iterator<const char *,string> first,
+    __wrapper_iterator<const char *,string> last) {
+    Append(&*first, std::distance(first, last));
+    return *this;
+}
+template<>
+string& string::append<__wrapper_iterator<char *,string> >(
+    __wrapper_iterator<char *,string> first,
+    __wrapper_iterator<char *,string> last) {
+    Append(&*first, std::distance(first, last));
+    return *this;
+}
+
 void string::push_back(const char c)
 {
     // Check we don't overflow.
diff --git a/tests/test_list.cpp b/tests/test_list.cpp
index 6cb9634..b017a29 100644
--- a/tests/test_list.cpp
+++ b/tests/test_list.cpp
@@ -115,6 +115,71 @@ bool testIterator()
     return true;
 }
 
+bool testErase() {
+    list<int> l;
+    for (int i = 0; i < 100; ++i) {
+        l.push_back(i);
+    }
+
+    // Deleting the first element.
+    list<int>::iterator val = l.erase(l.begin());
+    EXPECT_TRUE(l.size() == 99);
+    EXPECT_TRUE(*val == 1);
+
+    // Deleting the last should be a no op.
+    l.erase(l.end());
+    EXPECT_TRUE(l.size() == 99);
+
+    // Empty bay removing the last element;
+    while (l.size() > 0) {
+        val = l.erase(--l.end());
+    }
+
+    EXPECT_TRUE(l.size() == 0);
+    EXPECT_TRUE(val == l.end());
+
+    return true;
+}
+
+bool testEraseRange() {
+    list<int> l;
+    for (int i = 0; i < 100; ++i) {
+        l.push_back(i);
+    }
+    l.erase(l.begin(), l.end());
+    EXPECT_TRUE(l.size() == 0);
+    return true;
+}
+
+bool testPushPop() {
+    list<int> l;
+
+    l.push_front(10);
+    EXPECT_TRUE(l.front() == 10);
+    l.push_back(100);
+    EXPECT_TRUE(l.back() == 100);
+
+    l.push_front(1);
+    EXPECT_TRUE(l.front() == 1);
+    l.push_back(1000);
+    EXPECT_TRUE(l.back() == 1000);
+
+    l.pop_front();
+    EXPECT_TRUE(l.front() == 10);
+    l.pop_back();
+    EXPECT_TRUE(l.back() == 100);
+    l.pop_front();
+    EXPECT_TRUE(l.front() == 100);
+    EXPECT_TRUE(l.back() == 100);
+    l.pop_back();
+    EXPECT_TRUE(l.empty());
+    // all these are noops
+    l.pop_back();
+    l.pop_front();
+    l.pop_back();
+    return true;
+}
+
 }  // namespace android
 
 int main(int argc, char **argv)
@@ -123,5 +188,8 @@ int main(int argc, char **argv)
     FAIL_UNLESS(testSize);
     FAIL_UNLESS(testClear);
     FAIL_UNLESS(testIterator);
+    FAIL_UNLESS(testErase);
+    FAIL_UNLESS(testEraseRange);
+    FAIL_UNLESS(testPushPop);
     return kPassed;
 }
diff --git a/tests/test_string.cpp b/tests/test_string.cpp
index 0a9c1cc..f5c3d1a 100644
--- a/tests/test_string.cpp
+++ b/tests/test_string.cpp
@@ -34,6 +34,7 @@
 #include <climits>
 #include <cstring>
 #include <algorithm>
+#include <list>
 #include "common.h"
 
 
@@ -386,6 +387,42 @@ bool testAppend()
     str12.append(dummy, kMaxSizeT);
     EXPECT_TRUE(str12 == "original");
 
+    // Append iterator.
+    {
+        string str1("once upon ");
+        const string str2("a time");
+
+        str1.append(str2.begin(), str2.end());
+        EXPECT_TRUE(str1.size() == 16);
+        EXPECT_TRUE(str1 == "once upon a time");
+    }
+    {
+        string str1("once upon ");
+        string str2("a time");
+
+        str1.append(str2.begin(), str2.begin());
+        EXPECT_TRUE(str1.size() == 10);
+        EXPECT_TRUE(str1 == "once upon ");
+    }
+    {
+        string str1;
+        string str2("hello");
+
+        str1.append(str2.begin(), str2.end());
+        EXPECT_TRUE(str1.size() == 5);
+        EXPECT_TRUE(str1 == "hello");
+    }
+    {
+        string str1("hello ");
+        std::list<char> list1;
+        list1.push_back('w');
+        list1.push_back('o');
+        list1.push_back('r');
+        list1.push_back('l');
+        list1.push_back('d');
+        str1.append(list1.begin(), list1.end());
+        EXPECT_TRUE(str1 == "hello world");
+    }
     return true;
 }
 
diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp
index 8b85b97..95de15e 100644
--- a/tests/test_vector.cpp
+++ b/tests/test_vector.cpp
@@ -641,6 +641,14 @@ bool testEraseRange()
     return true;
 }
 
+// Valgrind should not barf when we access element out of bound.
+bool testAt() {
+    vector<int> vec;
+
+    vec.at(1000) = 0xdeadbeef;
+    EXPECT_TRUE(vec.at(1000) == 0xdeadbeef);
+    return true;
+}
 }  // namespace android
 
 int main(int argc, char **argv)
@@ -659,5 +667,6 @@ int main(int argc, char **argv)
     FAIL_UNLESS(testCtorDtorForNonPod);
     FAIL_UNLESS(testEraseElt);
     FAIL_UNLESS(testEraseRange);
+    FAIL_UNLESS(testAt);
     return kPassed;
 }