Added erase to list.

2 files changed, 121 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/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;
 }