QVarLenghtArray: Implement more API from QVector

... for consistency and to allow easy replacement of one by the other.

In particular this change allows to use QVarLenghtArray inside foreach

Reviewed-by: Gabriel
Task-number: QTBUG-14010

3 files changed, 544 insertions, 0 deletions

diff --git a/src/corelib/tools/qvarlengtharray.h b/src/corelib/tools/qvarlengtharray.h
index 4a6bb4b..3882323 100644
--- a/src/corelib/tools/qvarlengtharray.h
+++ b/src/corelib/tools/qvarlengtharray.h
@@ -44,7 +44,10 @@
 
 #include <QtCore/qcontainerfwd.h>
 #include <QtCore/qglobal.h>
+#include <QtCore/qalgorithms.h>
+
 #include <new>
+#include <string.h>
 
 QT_BEGIN_HEADER
 
@@ -123,6 +126,18 @@ public:
         }
     }
     void append(const T *buf, int size);
+    inline QVarLengthArray<T, Prealloc> &operator<<(const T &t)
+    { append(t); return *this; }
+    inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
+    { append(t); return *this; }
+
+    void prepend(const T &t);
+    void insert(int i, const T &t);
+    void insert(int i, int n, const T &t);
+    void replace(int i, const T &t);
+    void remove(int i);
+    void remove(int i, int n);
+
 
     inline T *data() { return ptr; }
     inline const T *data() const { return ptr; }
@@ -135,6 +150,21 @@ public:
     typedef const value_type &const_reference;
     typedef qptrdiff difference_type;
 
+
+    typedef T* iterator;
+    typedef const T* const_iterator;
+
+    inline iterator begin() { return ptr; }
+    inline const_iterator begin() const { return ptr; }
+    inline const_iterator constBegin() const { return ptr; }
+    inline iterator end() { return ptr + s; }
+    inline const_iterator end() const { return ptr + s; }
+    inline const_iterator constEnd() const { return ptr + s; }
+    iterator insert(iterator before, int n, const T &x);
+    inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
+    iterator erase(iterator begin, iterator end);
+    inline iterator erase(iterator pos) { return erase(pos, pos+1); }
+
 private:
     friend class QPodList<T, Prealloc>;
     void realloc(int size, int alloc);
@@ -272,6 +302,100 @@ Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defau
     return (i < 0 || i >= size()) ? defaultValue : at(i);
 }
 
+template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
+{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
+  insert(begin() + i, 1, t); }
+template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::insert(int i, int n, const T &t)
+{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
+  insert(begin() + i, n, t); }
+template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::remove(int i, int n)
+{ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= s, "QVarLengthArray::remove", "index out of range");
+  erase(begin() + i, begin() + i + n); }
+template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::remove(int i)
+{ Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
+  erase(begin() + i, begin() + i + 1); }
+template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
+{ insert(begin(), 1, t); }
+
+template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
+{
+    Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::replace", "index out of range");
+    const T copy(t);
+    data()[i] = copy;
+}
+
+
+template <class T, int Prealloc>
+Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(iterator before, size_type n, const T &t)
+{
+    int offset = int(before - ptr);
+    if (n != 0) {
+        resize(s + n);
+        const T copy(t);
+        if (QTypeInfo<T>::isStatic) {
+            T *b = ptr + offset;
+            T *j = ptr + s;
+            T *i = j - n;
+            while (i != b)
+                *--j = *--i;
+            i = b + n;
+            while (i != b)
+                *--i = copy;
+        } else {
+            T *b = ptr + offset;
+            T *i = b + n;
+            memmove(i, b, (s - offset - n) * sizeof(T));
+            while (i != b)
+                new (--i) T(copy);
+        }
+    }
+    return ptr + offset;
+}
+
+template <class T, int Prealloc>
+Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::erase(iterator abegin, iterator aend)
+{
+    int f = int(abegin - ptr);
+    int l = int(aend - ptr);
+    int n = l - f;
+    if (QTypeInfo<T>::isComplex) {
+        qCopy(ptr + l, ptr + s, ptr + f);
+        T *i = ptr + s;
+        T *b = ptr + s - n;
+        while (i != b) {
+            --i;
+            i->~T();
+        }
+    } else {
+        memmove(ptr + f, ptr + l, (s - l) * sizeof(T));
+    }
+    s -= n;
+    return ptr + f;
+}
+
+template <typename T, int Prealloc1, int Prealloc2>
+bool operator==(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
+{
+    if (l.size() != r.size())
+        return false;
+    for (int i = 0; i < l.size(); i++) {
+        if (l.at(i) != r.at(i))
+            return false;
+    }
+    return true;
+}
+
+template <typename T, int Prealloc1, int Prealloc2>
+bool operator!=(const QVarLengthArray<T, Prealloc1> &l, const QVarLengthArray<T, Prealloc2> &r)
+{
+    return !(l == r);
+}
 
 QT_END_NAMESPACE
 
diff --git a/src/corelib/tools/qvarlengtharray.qdoc b/src/corelib/tools/qvarlengtharray.qdoc
index 6f91bcc..4d5d5d1 100644
--- a/src/corelib/tools/qvarlengtharray.qdoc
+++ b/src/corelib/tools/qvarlengtharray.qdoc
@@ -337,3 +337,211 @@
     Typedef for const T &. Provided for STL compatibility.
 */
 
+/*! \fn void QVarLengthArray::prepend(const T &value)
+
+    \since 4.8
+    Inserts \a value at the beginning of the array.
+
+
+    This is the same as vector.insert(0, \a value).
+
+    For large arrays, this operation can be slow (\l{linear time}),
+    because it requires moving all the items in the vector by one
+    position further in memory. If you want a container class that
+    provides a fast prepend() function, use QList or QLinkedList
+    instead.
+
+    \sa append(), insert()
+*/
+
+/*! \fn void QVarLengthArray::replace(int i, const T &value)
+
+    \since 4.8
+    Replaces the item at index position \a i with \a value.
+
+    \a i must be a valid index position in the array (i.e., 0 <= \a
+    i < size()).
+
+    \sa operator[](), remove()
+*/
+
+/*! \fn void QVarLengthArray::remove(int i)
+
+    \overload
+    \since 4.8
+
+    Removes the element at index position \a i.
+
+    \sa insert(), replace()
+*/
+
+/*! \fn void QVarLengthArray::remove(int i, int count)
+
+    \overload
+    \since 4.8
+
+    Removes \a count elements from the middle of the array, starting at
+    index position \a i.
+
+    \sa insert(), replace()
+*/
+
+/*! \fn QVarLengthArray::iterator QVarLengthArray::begin()
+    \since 4.8
+
+    Returns an \l{STL-style iterator} pointing to the first item in
+    the array.
+
+    \sa constBegin(), end()
+*/
+
+/*! \fn QVarLengthArray::const_iterator QVarLengthArray::begin() const
+    \since 4.8
+    \overload
+*/
+
+/*! \fn QVarLengthArray::const_iterator QVarLengthArray::constBegin() const
+    \since 4.8
+
+    Returns a const \l{STL-style iterator} pointing to the first item
+    in the array.
+
+    \sa begin(), constEnd()
+*/
+
+/*! \fn QVarLengthArray::iterator QVarLengthArray::end()
+    \since 4.8
+
+    Returns an \l{STL-style iterator} pointing to the imaginary item
+    after the last item in the array.
+
+    \sa begin(), constEnd()
+*/
+
+/*! \fn QVarLengthArray::const_iterator QVarLengthArray::end() const
+    \since 4.8
+
+    \overload
+*/
+
+/*! \fn QVarLengthArray::const_iterator QVarLengthArray::constEnd() const
+    \since 4.8
+
+    Returns a const \l{STL-style iterator} pointing to the imaginary
+    item after the last item in the array.
+
+    \sa constBegin(), end()
+*/
+
+/*! \fn QVarLengthArray::iterator QVarLengthArray::erase(iterator pos)
+    \since 4.8
+
+    Removes the item pointed to by the iterator \a pos from the
+    vector, and returns an iterator to the next item in the vector
+    (which may be end()).
+
+    \sa insert(), remove()
+*/
+
+/*! \fn QVarLengthArray::iterator QVarLengthArray::erase(iterator begin, iterator end)
+
+    \overload
+    \since 4.8
+
+    Removes all the items from \a begin up to (but not including) \a
+    end. Returns an iterator to the same item that \a end referred to
+    before the call.
+*/
+
+/*! \fn void QVarLengthArray::insert(int i, const T &value)
+    \since 4.8
+
+    Inserts \a value at index position \a i in the array. If \a i is
+    0, the value is prepended to the vector. If \a i is size(), the
+    value is appended to the vector.
+
+    For large arrays, this operation can be slow (\l{linear time}),
+    because it requires moving all the items at indexes \a i and
+    above by one position further in memory. If you want a container
+    class that provides a fast insert() function, use QLinkedList
+    instead.
+
+    \sa remove()
+*/
+
+/*! \fn void QVarLengthArray::insert(int i, int count, const T &value)
+
+    \overload
+    \since 4.8
+
+    Inserts \a count copies of \a value at index position \a i in the
+    vector.
+*/
+
+/*! \fn QVarLengthArray::iterator QVarLengthArray::insert(iterator before, const T &value)
+
+    \overload
+    \since 4.8
+
+    Inserts \a value in front of the item pointed to by the iterator
+    \a before. Returns an iterator pointing at the inserted item.
+*/
+
+/*! \fn QVarLengthArray::iterator QVarLengthArray::insert(iterator before, int count, const T &value)
+
+    \since 4.8
+    Inserts \a count copies of \a value in front of the item pointed to
+    by the iterator \a before. Returns an iterator pointing at the
+    first of the inserted items.
+*/
+
+
+
+/*! \fn bool operator==(const QVarLengthArray<T, Prealloc1> &left, const QVarLengthArray<T, Prealloc2> &right)
+
+    \relates QVarLengthArray
+    \since 4.8
+    Returns true if the two array are equal;
+
+    Two arrays are considered equal if they contain the same values
+    in the same order.
+
+    This function requires the value type to have an implementation
+    of \c operator==().
+
+    \sa operator!=()
+*/
+
+/*! \fn bool operator!=(const QVarLengthArray<T, Prealloc1> &left, const QVarLengthArray<T, Prealloc2> &right)
+
+    \relates QVarLengthArray
+    \since 4.8
+    Returns true if the two array are different;
+
+    Two arrays are considered equal if they contain the same values
+    in the same order.
+
+    This function requires the value type to have an implementation
+    of \c operator==().
+
+    \sa operator==()
+*/
+
+/*! \fn QVarLengthArray &QVarLengthArray::operator<<(const T &value)
+
+    \since 4.8
+    Appends \a value to the array and returns a reference to this
+    vector.
+
+    \sa append(), operator+=()
+*/
+
+/*! \fn QVarLengthArray &QVarLengthArray::operator+=(const T &value)
+
+    \since 4.8
+    Appends \a value to the array and returns a reference to this
+    vector.
+
+    \sa append(), operator<<()
+*/
+
diff --git a/tests/auto/collections/tst_collections.cpp b/tests/auto/collections/tst_collections.cpp
index 0adceee..263c478 100644
--- a/tests/auto/collections/tst_collections.cpp
+++ b/tests/auto/collections/tst_collections.cpp
@@ -166,6 +166,9 @@ private slots:
     void forwardDeclared();
     void alignment();
     void QTBUG13079_collectionInsideCollection();
+
+    void foreach_2();
+    void insert_remove_loop();
 };
 
 struct LargeStatic {
@@ -3707,5 +3710,214 @@ void tst_Collections::QTBUG13079_collectionInsideCollection()
 #endif
 }
 
+template<class Container> void foreach_test_arrays(const Container &container)
+{
+    typedef typename Container::value_type T;
+    int i = 0;
+    QSet <T> set;
+    foreach(const T & val, container) {
+        QVERIFY( val == container[i] );
+        set << val;
+        i++;
+    }
+    QCOMPARE(set.count(), container.count());
+
+    //modify the container while iterating.
+    Container c2 = container;
+    Container c3;
+    i = 0;
+    foreach (T val, c2) {
+        c3 << val;
+        c2.insert((i * 89) % c2.size(), T() );
+        QVERIFY( val == container.at(i) );
+        val = T();
+        i++;
+    }
+    QVERIFY(c3 == container);
+}
+
+
+void tst_Collections::foreach_2()
+{
+    QStringList strlist = QString::fromLatin1("a,b,c,d,e,f,g,h,ih,kl,mn,op,qr,st,uvw,xyz").split(",");
+    foreach_test_arrays(strlist);
+    foreach_test_arrays(QList<QString>(strlist));
+    foreach_test_arrays(strlist.toVector());
+
+    QList<int> intlist;
+    intlist << 1 << 2 << 3 << 4 <<5 << 6 << 7 << 8 << 9;
+    foreach_test_arrays(intlist);
+    foreach_test_arrays(intlist.toVector());
+
+    QVarLengthArray<int> varl1;
+    QVarLengthArray<int, 3> varl2;
+    QVarLengthArray<int, 10> varl3;
+    foreach(int i, intlist) {
+        varl1 << i;
+        varl2 << i;
+        varl3 << i;
+    }
+    QCOMPARE(varl1.count(), intlist.count());
+    QCOMPARE(varl2.count(), intlist.count());
+    QCOMPARE(varl3.count(), intlist.count());
+    foreach_test_arrays(varl1);
+    foreach_test_arrays(varl2);
+    foreach_test_arrays(varl3);
+
+    QVarLengthArray<QString> varl4;
+    QVarLengthArray<QString, 3> varl5;
+    QVarLengthArray<QString, 18> varl6;
+    foreach(const QString &str, strlist) {
+        varl4 << str;
+        varl5 << str;
+        varl6 << str;
+    }
+    QCOMPARE(varl4.count(), strlist.count());
+    QCOMPARE(varl5.count(), strlist.count());
+    QCOMPARE(varl6.count(), strlist.count());
+    foreach_test_arrays(varl4);
+    foreach_test_arrays(varl5);
+    foreach_test_arrays(varl6);
+}
+
+struct IntOrString
+{
+    int val;
+    IntOrString(int v) : val(v) { }
+    IntOrString(const QString &v) : val(v.toInt()) { }
+    operator int() { return val; }
+    operator QString() { return QString::number(val); }
+#ifndef QT_NO_STL
+    operator std::string() { return QString::number(val).toStdString(); }
+    IntOrString(const std::string &v) : val(QString::fromStdString(v).toInt()) { }
+#endif
+};
+
+template<class Container> void insert_remove_loop_impl()
+{
+    typedef typename Container::value_type T;
+    Container t;
+    t.append(T(IntOrString(1)));
+    t << (T(IntOrString(2)));
+    t += (T(IntOrString(3)));
+    t.prepend(T(IntOrString(4)));
+    t.insert(2, 3 , T(IntOrString(5)));
+    t.insert(4, T(IntOrString(6)));
+    t.insert(t.begin() + 2, T(IntOrString(7)));
+    t.insert(t.begin() + 5, 3,  T(IntOrString(8)));
+    int expect1[] = { 4 , 1 , 7, 5 , 5 , 8, 8, 8, 6, 5, 2 , 3 };
+    QCOMPARE(size_t(t.count()), sizeof(expect1)/sizeof(int));
+    for (int i = 0; i < t.count(); i++) {
+        QCOMPARE(t[i], T(IntOrString(expect1[i])));
+    }
+
+    Container compare_test1 = t;
+    t.replace(5, T(IntOrString(9)));
+    Container compare_test2 = t;
+    QVERIFY(!(compare_test1 == t));
+    QVERIFY( (compare_test1 != t));
+    QVERIFY( (compare_test2 == t));
+    QVERIFY(!(compare_test2 != t));
+    t.remove(7);
+    t.remove(2, 3);
+    int expect2[] = { 4 , 1 , 9, 8, 6, 5, 2 , 3 };
+    QCOMPARE(size_t(t.count()), sizeof(expect2)/sizeof(int));
+    for (int i = 0; i < t.count(); i++) {
+        QCOMPARE(t[i], T(IntOrString(expect2[i])));
+    }
+
+    for (typename Container::iterator it = t.begin(); it != t.end(); ) {
+        if ( int(IntOrString(*it)) % 2 )
+            ++it;
+        else
+            it = t.erase(it);
+    }
+
+    int expect3[] = { 1 , 9, 5, 3 };
+    QCOMPARE(size_t(t.count()), sizeof(expect3)/sizeof(int));
+    for (int i = 0; i < t.count(); i++) {
+        QCOMPARE(t[i], T(IntOrString(expect3[i])));
+    }
+
+    t.erase(t.begin() + 1, t.end() - 1);
+
+    int expect4[] = { 1 , 3 };
+    QCOMPARE(size_t(t.count()), sizeof(expect4)/sizeof(int));
+    for (int i = 0; i < t.count(); i++) {
+        QCOMPARE(t[i], T(IntOrString(expect4[i])));
+    }
+
+    t << T(IntOrString(10)) << T(IntOrString(11)) << T(IntOrString(12)) << T(IntOrString(13));
+    t << T(IntOrString(14)) << T(IntOrString(15)) << T(IntOrString(16)) << T(IntOrString(17));
+    t << T(IntOrString(18)) << T(IntOrString(19)) << T(IntOrString(20)) << T(IntOrString(21));
+    for (typename Container::iterator it = t.begin(); it != t.end(); ++it) {
+        int iv = int(IntOrString(*it));
+        if ( iv % 2 ) {
+            it = t.insert(it, T(IntOrString(iv * iv)));
+            it = t.insert(it + 2, T(IntOrString(iv * iv + 1)));
+        }
+    }
+
+    int expect5[] = { 1, 1, 2, 3*3, 3, 3*3+1, 10, 11*11, 11, 11*11+1, 12 , 13*13, 13, 13*13+1, 14,
+                      15*15, 15, 15*15+1, 16 , 17*17, 17, 17*17+1 ,18 , 19*19, 19, 19*19+1, 20, 21*21, 21, 21*21+1 };
+    QCOMPARE(size_t(t.count()), sizeof(expect5)/sizeof(int));
+    for (int i = 0; i < t.count(); i++) {
+        QCOMPARE(t[i], T(IntOrString(expect5[i])));
+    }
+}
+
+
+//Add insert(int, int, T) so it has the same interface as QVector and QVarLengthArray for the test.
+template<typename T>
+struct ExtList : QList<T> {
+    using QList<T>::insert;
+    void insert(int before, int n, const T&x) {
+        while (n--) {
+            this->insert(before, x );
+        }
+    }
+    void insert(typename QList<T>::iterator before, int n, const T&x) {
+        while (n--) {
+            this->insert(before, x );
+        }
+    }
+
+    void remove(int i) {
+        this->removeAt(i);
+    }
+    void remove(int i, int n) {
+        while (n--) {
+            this->removeAt(i);
+        }
+    }
+};
+
+void tst_Collections::insert_remove_loop()
+{
+    insert_remove_loop_impl<ExtList<int> >();
+    insert_remove_loop_impl<ExtList<QString> >();
+    insert_remove_loop_impl<QVector<int> >();
+    insert_remove_loop_impl<QVector<QString> >();
+    insert_remove_loop_impl<QVarLengthArray<int> >();
+    insert_remove_loop_impl<QVarLengthArray<QString> >();
+    insert_remove_loop_impl<QVarLengthArray<int, 10> >();
+    insert_remove_loop_impl<QVarLengthArray<QString, 10> >();
+    insert_remove_loop_impl<QVarLengthArray<int, 3> >();
+    insert_remove_loop_impl<QVarLengthArray<QString, 3> >();
+    insert_remove_loop_impl<QVarLengthArray<int, 15> >();
+    insert_remove_loop_impl<QVarLengthArray<QString, 15> >();
+
+#ifndef QT_NO_STL
+    insert_remove_loop_impl<ExtList<std::string> >();
+    insert_remove_loop_impl<QVector<std::string> >();
+    insert_remove_loop_impl<QVarLengthArray<std::string> >();
+    insert_remove_loop_impl<QVarLengthArray<std::string, 10> >();
+    insert_remove_loop_impl<QVarLengthArray<std::string, 3> >();
+    insert_remove_loop_impl<QVarLengthArray<std::string, 15> >();
+#endif
+}
+
+
+
 QTEST_APPLESS_MAIN(tst_Collections)
 #include "tst_collections.moc"