diff options
| -rw-r--r-- | include/algorithm | 61 | ||||
| -rw-r--r-- | include/iterator | 29 | ||||
| -rw-r--r-- | include/vector | 43 | ||||
| -rw-r--r-- | tests/test_algorithm.cpp | 16 | ||||
| -rw-r--r-- | tests/test_iterator.cpp | 11 | ||||
| -rw-r--r-- | tests/test_string.cpp | 15 | ||||
| -rw-r--r-- | tests/test_vector.cpp | 152 |
7 files changed, 322 insertions, 5 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) diff --git a/tests/test_algorithm.cpp b/tests/test_algorithm.cpp index e00bb67..8fd554d 100644 --- a/tests/test_algorithm.cpp +++ b/tests/test_algorithm.cpp @@ -134,6 +134,21 @@ bool testEqual() return true; } +bool testCopy() +{ + { + int data[] = {1,2,3,4,5,6}; + std::copy(data + 2, data + 5, data); + EXPECT_TRUE(data[0] == 3); + EXPECT_TRUE(data[1] == 4); + EXPECT_TRUE(data[2] == 5); + EXPECT_TRUE(data[3] == 4); + EXPECT_TRUE(data[4] == 5); + EXPECT_TRUE(data[5] == 6); + } + return true; +} + } // namespace android int main(int argc, char **argv) @@ -144,5 +159,6 @@ int main(int argc, char **argv) FAIL_UNLESS(testFill); FAIL_UNLESS(testFill_N); FAIL_UNLESS(testEqual); + FAIL_UNLESS(testCopy); return kPassed; } diff --git a/tests/test_iterator.cpp b/tests/test_iterator.cpp index ed6e327..cc9c510 100644 --- a/tests/test_iterator.cpp +++ b/tests/test_iterator.cpp @@ -109,10 +109,21 @@ bool testCategory() return true; } +typedef std::__wrapper_iterator<int *, int *> WrapperIterator; + +// Check we can distinguish wrapper iterators. +bool testWrapperIterator() +{ + EXPECT_FALSE(android::is_wrapper_iterator<android::Random>::value); + EXPECT_TRUE(android::is_wrapper_iterator<android::WrapperIterator>::value); + return true; +} + } // namespace android int main(int argc, char **argv) { FAIL_UNLESS(testCategory); + FAIL_UNLESS(testWrapperIterator); return kPassed; } diff --git a/tests/test_string.cpp b/tests/test_string.cpp index 337d879..d06f88e 100644 --- a/tests/test_string.cpp +++ b/tests/test_string.cpp @@ -33,6 +33,7 @@ #endif #include <climits> #include <cstring> +#include <algorithm> #include "common.h" @@ -615,6 +616,19 @@ bool testAssignment() return true; } +bool testCopy() +{ + string data[] = {"one", "two", "three", "four", "five", "six"}; + std::copy(data + 2, data + 5, data); + EXPECT_TRUE(data[0] == "three"); + EXPECT_TRUE(data[1] == "four"); + EXPECT_TRUE(data[2] == "five"); + EXPECT_TRUE(data[3] == "four"); + EXPECT_TRUE(data[4] == "five"); + EXPECT_TRUE(data[5] == "six"); + return true; +} + bool testConcat() { @@ -915,6 +929,7 @@ int main(int argc, char **argv) FAIL_UNLESS(testAppendOperator); FAIL_UNLESS(testConcat); FAIL_UNLESS(testAssignment); + FAIL_UNLESS(testCopy); FAIL_UNLESS(testReserve); FAIL_UNLESS(testCompare); FAIL_UNLESS(testAccessor); diff --git a/tests/test_vector.cpp b/tests/test_vector.cpp index 88dd466..6279e97 100644 --- a/tests/test_vector.cpp +++ b/tests/test_vector.cpp @@ -88,6 +88,7 @@ template<typename T> struct A { A() {mChunk = new T[2046];} A(const A<T>& a) {mChunk = new T[2046];} virtual ~A() {delete [] mChunk;} + A& operator=(const A& o) { return *this;} T *mChunk; }; @@ -96,6 +97,7 @@ struct B { B() {mChunk = new char[2046];} B(const B& b) {mChunk = new char[2046];} virtual ~B() {delete [] mChunk;} + B& operator=(const B& o) { return *this;} char *mChunk; }; @@ -512,6 +514,151 @@ bool testCtorDtorForNonPod() EXPECT_TRUE(CtorDtorCounter::mDtorCount == 201); return true; } + +bool testEraseElt() +{ + { + vector<B> empty; + vector<B>::iterator res = empty.erase(empty.end()); + EXPECT_TRUE(res == empty.end()); + EXPECT_TRUE(empty.empty()); + } + { + vector<B> one; + one.push_back(B()); + EXPECT_TRUE(!one.empty()); + + vector<B>::iterator res = one.erase(one.begin()); + EXPECT_TRUE(res == one.end()); + + EXPECT_TRUE(one.begin() == one.end()); + EXPECT_TRUE(one.empty()); + } + { + vector<B> two; + two.push_back(B()); + two.push_back(B()); + + vector<B>::iterator res = two.erase(two.begin()); + + EXPECT_TRUE(res == two.begin()); + EXPECT_TRUE(res != two.end()); + + EXPECT_TRUE(two.begin() != two.end()); + EXPECT_TRUE(two.size() == 1); + } + { + vector<int> vec; + for (int i = 0; i < 20; ++i) vec.push_back(i); + vector<int>::iterator pos; + + pos = vec.erase(vec.begin() + 2); // removes '2' + EXPECT_TRUE(*pos == 3); // returns '3' + + pos = vec.erase(vec.begin() + 18); // removes '19' now @ pos 18 + EXPECT_TRUE(pos == vec.end()); // returns end() + EXPECT_TRUE(*(--pos) == 18); // last one is now '18' + } + { + vector<std::string> vec; + + vec.push_back("first"); + vec.push_back("second"); + vec.push_back("third"); + vec.push_back("fourth"); + + vector<std::string>::iterator pos; + pos = vec.erase(vec.begin() + 1); // removes 'second' + EXPECT_TRUE(vec.size() == 3); + EXPECT_TRUE(*pos == "third"); + EXPECT_TRUE(vec[0] == "first"); + EXPECT_TRUE(vec[1] == "third"); + EXPECT_TRUE(vec[2] == "fourth"); + } + return true; +} + +bool testEraseRange() +{ + { + vector<B> empty; + vector<B>::iterator res = empty.erase(empty.begin(), empty.end()); + EXPECT_TRUE(res == empty.end()); + EXPECT_TRUE(empty.empty()); + EXPECT_TRUE(empty.size() == 0); + } + { + vector<B> one; + one.push_back(B()); + EXPECT_TRUE(!one.empty()); + + vector<B>::iterator res = one.erase(one.begin(), one.end()); + EXPECT_TRUE(res == one.end()); + + EXPECT_TRUE(one.begin() == one.end()); + EXPECT_TRUE(one.empty()); + } + { + vector<B> two; + two.push_back(B()); + two.push_back(B()); + + // erase the 1st one. + vector<B>::iterator res = two.erase(two.begin(), two.begin() + 1); + + EXPECT_TRUE(res == two.begin()); + EXPECT_TRUE(res != two.end()); + + EXPECT_TRUE(two.begin() != two.end()); + EXPECT_TRUE(two.size() == 1); + } + { + vector<B> two; + two.push_back(B()); + two.push_back(B()); + + // erase range is empty. + vector<B>::iterator res = two.erase(two.begin(), two.begin()); + + EXPECT_TRUE(res == two.begin()); + EXPECT_TRUE(res != two.end()); + + EXPECT_TRUE(two.begin() != two.end()); + EXPECT_TRUE(two.size() == 2); + } + + { + vector<int> vec; + for (int i = 0; i < 20; ++i) vec.push_back(i); + vector<int>::iterator pos; + + pos = vec.erase(vec.begin() + 2, vec.begin() + 3); // removes '2' + EXPECT_TRUE(*pos == 3); // returns '3' + + pos = vec.erase(vec.begin() + 18, vec.end()); // removes '19' now @ pos 18 + EXPECT_TRUE(pos == vec.end()); // returns end() + EXPECT_TRUE(*(--pos) == 18); // last one is now '18' + } + { + vector<std::string> vec; + + vec.push_back("first"); + vec.push_back("second"); + vec.push_back("third"); + vec.push_back("fourth"); + + vector<std::string>::iterator pos; + pos = vec.erase(vec.begin() + 1, vec.begin() + 3); // removes 'second' and third. + EXPECT_TRUE(vec.size() == 2); + EXPECT_TRUE(*pos == "fourth"); + EXPECT_TRUE(vec[0] == "first"); + EXPECT_TRUE(vec[1] == "fourth"); + pos = vec.erase(vec.begin(), vec.end()); // clears the vector + EXPECT_TRUE(vec.empty()); + } + return true; +} + } // namespace android int main(int argc, char **argv) @@ -519,17 +666,16 @@ int main(int argc, char **argv) FAIL_UNLESS(testConstructorInt); FAIL_UNLESS(testConstructorString); FAIL_UNLESS(testConstructorClass); - FAIL_UNLESS(testConstructorRepeat); FAIL_UNLESS(testConstructorIterator); FAIL_UNLESS(testReserve); FAIL_UNLESS(testPushBack); FAIL_UNLESS(testPopBack); FAIL_UNLESS(testResize); -#if(0) FAIL_UNLESS(testSwap); FAIL_UNLESS(testIterators); FAIL_UNLESS(testCtorDtorForNonPod); -#endif + FAIL_UNLESS(testEraseElt); + FAIL_UNLESS(testEraseRange); return kPassed; } |