Add support for filtering VisualDataModels.

Add a VisualDataGroup element which items within a VisualDataModel
can be assigned to. Setting the group property of a VisualDataModel
or one of its parts models will filter the items visible within a
view to just items belonging to that group.  By default all items
belong to an 'items' group.

The VisualDataModel attached object includes properties indicating
whether a item is a member of a group and its index in the group.

Task-number: QTBUG-21513 QTBUG-21515
Change-Id: If3df6a359a888a6f79923775d2f78076d5e7d2cf
Reviewed-on: http://codereview.qt-project.org/4115
Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com>
Reviewed-by: Martin Jones <martin.jones@nokia.com>

5 files changed, 1581 insertions, 4 deletions

diff --git a/src/declarative/util/qdeclarativechangeset.cpp b/src/declarative/util/qdeclarativechangeset.cpp
index 33757062a1..81cbe3e10a 100644
--- a/src/declarative/util/qdeclarativechangeset.cpp
+++ b/src/declarative/util/qdeclarativechangeset.cpp
@@ -45,6 +45,7 @@ QT_BEGIN_NAMESPACE
 
 QDeclarativeChangeSet::QDeclarativeChangeSet()
     : m_moveCounter(0)
+    , m_difference(0)
 {
 }
 
@@ -53,6 +54,7 @@ QDeclarativeChangeSet::QDeclarativeChangeSet(const QDeclarativeChangeSet &change
     , m_inserts(changeSet.m_inserts)
     , m_changes(changeSet.m_changes)
     , m_moveCounter(changeSet.m_moveCounter)
+    , m_difference(0)
 {
 }
 
@@ -66,6 +68,7 @@ QDeclarativeChangeSet &QDeclarativeChangeSet::operator =(const QDeclarativeChang
     m_inserts = changeSet.m_inserts;
     m_changes = changeSet.m_changes;
     m_moveCounter = changeSet.m_moveCounter;
+    m_difference = changeSet.m_difference;
     return *this;
 }
 
@@ -330,6 +333,7 @@ void QDeclarativeChangeSet::applyRemovals(QVector<Remove> &removals, QVector<Ins
     }
     for (; remove != m_removes.end(); ++remove)
         remove->index -= removeCount;
+    m_difference -= removeCount;
 }
 
 void QDeclarativeChangeSet::applyInsertions(QVector<Insert> &insertions)
@@ -354,6 +358,7 @@ void QDeclarativeChangeSet::applyInsertions(QVector<Insert> &insertions)
         if (insert == m_inserts.end()) {
             insert = m_inserts.insert(insert, *iit);
             ++insert;
+            insertCount += iit->count;
         } else {
             const int offset = index - insert->index;
             if (offset < 0 || (offset == 0 && (iit->moveId != -1 || insert->moveId != -1))) {
@@ -395,6 +400,7 @@ void QDeclarativeChangeSet::applyInsertions(QVector<Insert> &insertions)
         change->index += insertCount;
     for (; insert != m_inserts.end(); ++insert)
         insert->index += insertCount;
+    m_difference += insertCount;
 }
 
 void QDeclarativeChangeSet::applyChanges(QVector<Change> &changes)
diff --git a/src/declarative/util/qdeclarativechangeset_p.h b/src/declarative/util/qdeclarativechangeset_p.h
index 67533b02d5..b7554da503 100644
--- a/src/declarative/util/qdeclarativechangeset_p.h
+++ b/src/declarative/util/qdeclarativechangeset_p.h
@@ -103,10 +103,6 @@ public:
     };
 
     QDeclarativeChangeSet();
-    QDeclarativeChangeSet(
-            const QVector<Remove> &removals,
-            const QVector<Insert> &insertions,
-            const QVector<Change> &changes = QVector<Change>());
     QDeclarativeChangeSet(const QDeclarativeChangeSet &changeSet);
     ~QDeclarativeChangeSet();
 
@@ -138,8 +134,12 @@ public:
         m_inserts.clear();
         m_changes.clear();
         m_moveCounter = 0;
+        m_difference = 0;
     }
 
+    int moveCounter() const { return m_moveCounter; }
+    int difference() const { return m_difference; }
+
 private:
     void applyRemovals(QVector<Remove> &removals, QVector<Insert> &insertions);
     void applyInsertions(QVector<Insert> &insertions);
@@ -149,6 +149,7 @@ private:
     QVector<Insert> m_inserts;
     QVector<Change> m_changes;
     int m_moveCounter;
+    int m_difference;
 };
 
 inline uint qHash(const QDeclarativeChangeSet::MoveKey &key) { return qHash(qMakePair(key.moveId, key.offset)); }
diff --git a/src/declarative/util/qdeclarativelistcompositor.cpp b/src/declarative/util/qdeclarativelistcompositor.cpp
new file mode 100644
index 0000000000..8fd4ec44dd
--- /dev/null
+++ b/src/declarative/util/qdeclarativelistcompositor.cpp
@@ -0,0 +1,1198 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtDeclarative module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qdeclarativelistcompositor_p.h"
+
+#include <QtCore/qvarlengtharray.h>
+
+//#define QT_DECLARATIVE_VERIFY_MINIMAL
+//#define QT_DECLARATIVE_VERIFY_INTEGRITY
+
+#ifdef QT_DECLARATIVE_VERIFY_MINIMAL
+#define QT_DECLARATIVE_VERIFY_INTEGRITY
+static bool qt_verifyMinimal(
+        const QDeclarativeListCompositor::iterator &begin,
+        const QDeclarativeListCompositor::iterator &end)
+{
+    bool minimal = true;
+    int index = 0;
+
+    for (const QDeclarativeListCompositor::Range *range = begin->next; range != end; range = range->next, ++index) {
+        if (range->previous->list == range->list
+                && range->previous->flags == (range->flags & ~QDeclarativeListCompositor::AppendFlag)
+                && range->previous->end() == range->index) {
+            qWarning() << index << "Consecutive ranges";
+            qWarning() << *range->previous;
+            qWarning() << *range;
+            minimal = false;
+        }
+    }
+
+    return minimal;
+}
+
+#endif
+
+#ifdef QT_DECLARATIVE_VERIFY_INTEGRITY
+static bool qt_printInfo(const QDeclarativeListCompositor &compositor)
+{
+    qWarning() << compositor;
+    return true;
+}
+
+static bool qt_verifyIntegrity(
+        const QDeclarativeListCompositor::iterator &begin,
+        const QDeclarativeListCompositor::iterator &end,
+        const QDeclarativeListCompositor::iterator &cachedIt)
+{
+    bool valid = true;
+
+    int index = 0;
+    QDeclarativeListCompositor::iterator it;
+    for (it = begin; *it != *end; *it = it->next) {
+        if (it->count == 0 && !it->append()) {
+            qWarning() << index << "Empty non-append range";
+            valid = false;
+        }
+        if (it->count < 0) {
+            qWarning() << index << "Negative count";
+            valid = false;
+        }
+        if (it->list && it->flags != QDeclarativeListCompositor::CacheFlag && it->index < 0) {
+            qWarning() << index <<"Negative index";
+            valid = false;
+        }
+        if (it->previous->next != it.range) {
+            qWarning() << index << "broken list: it->previous->next != it.range";
+            valid = false;
+        }
+        if (it->next->previous != it.range) {
+            qWarning() << index << "broken list: it->next->previous != it.range";
+            valid = false;
+        }
+        if (*it == *cachedIt) {
+            for (int i = 0; i < end.groupCount; ++i) {
+                int groupIndex = it.index[i];
+                if (cachedIt->flags & (1 << i))
+                    groupIndex += cachedIt.offset;
+                if (groupIndex != cachedIt.index[i]) {
+                    qWarning() << index
+                            << "invalid cached index"
+                            << QDeclarativeListCompositor::Group(i)
+                            << "Expected:"
+                            << groupIndex
+                            << "Actual"
+                            << cachedIt.index[i]
+                            << cachedIt;
+                    valid = false;
+                }
+            }
+        }
+        it.incrementIndexes(it->count);
+        ++index;
+    }
+
+    for (int i = 0; i < end.groupCount; ++i) {
+        if (end.index[i] != it.index[i]) {
+            qWarning() << "Group" << i << "count invalid. Expected:" << end.index[i] << "Actual:" << it.index[i];
+            valid = false;
+        }
+    }
+    return valid;
+}
+#endif
+
+#if defined(QT_DECLARATIVE_VERIFY_MINIMAL)
+#   define QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!(qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \
+            && qt_verifyMinimal(iterator(m_ranges.next, 0, Default, m_groupCount), m_end)) \
+            && qt_printInfo(*this)));
+#elif defined(QT_DECLARATIVE_VERIFY_INTEGRITY)
+#   define QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \
+            && qt_printInfo(*this)));
+#else
+#   define QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+#endif
+
+//#define QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(args) qDebug() << m_end.index[1] << m_end.index[0] << Q_FUNC_INFO args;
+#define QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(args)
+
+QDeclarativeListCompositor::iterator &QDeclarativeListCompositor::iterator::operator ++()
+{
+    while (!(range->flags & groupFlag)) {
+        incrementIndexes(range->count - offset);
+        offset = 0;
+        range = range->next;
+    }
+    incrementIndexes(1);
+    if (++offset == range->count) {
+        while (!((range = range->next)->flags & groupFlag))
+            incrementIndexes(range->count);
+        offset = 0;
+    }
+    return *this;
+}
+
+QDeclarativeListCompositor::iterator &QDeclarativeListCompositor::iterator::operator +=(int difference)
+{
+    Q_ASSERT(difference >= 0);
+    while (!(range->flags & groupFlag)) {
+        incrementIndexes(range->count - offset);
+        offset = 0;
+        range = range->next;
+    }
+    decrementIndexes(offset);
+    offset += difference;
+    while (offset >= range->count || !(range->flags & groupFlag)) {
+        if (range->flags & groupFlag)
+            offset -= range->count;
+        incrementIndexes(range->count);
+        range = range->next;
+    }
+    incrementIndexes(offset);
+    return *this;
+}
+
+QDeclarativeListCompositor::iterator &QDeclarativeListCompositor::iterator::operator -=(int difference)
+{
+    Q_ASSERT(difference >= 0);
+    while (!(range->flags & groupFlag)) {
+        decrementIndexes(offset);
+        range = range->previous;
+        offset = range->count;
+    }
+    decrementIndexes(offset);
+    offset -= difference;
+    while (offset < 0) {
+        range = range->previous;
+        if (range->flags & groupFlag)
+            offset += range->count;
+        decrementIndexes(range->count);
+    }
+    incrementIndexes(offset);
+    return *this;
+}
+
+QDeclarativeListCompositor::insert_iterator &QDeclarativeListCompositor::insert_iterator::operator ++()
+{
+    while (!(range->flags & groupFlag)) {
+        incrementIndexes(range->count - offset);
+        offset = 0;
+        range = range->next;
+    }
+    incrementIndexes(1);
+    if (++offset == range->count && !range->append()) {
+        while (!((range = range->next)->flags & groupFlag) ){
+            incrementIndexes(range->count);
+        }
+        offset = 0;
+    }
+    return *this;
+}
+
+QDeclarativeListCompositor::insert_iterator &QDeclarativeListCompositor::insert_iterator::operator +=(int difference)
+{
+    Q_ASSERT(difference >= 0);
+    while (!(range->flags & groupFlag) && range->flags & GroupMask) {
+        incrementIndexes(range->count - offset);
+        offset = 0;
+        range = range->next;
+    }
+    decrementIndexes(offset);
+    offset += difference;
+    while (offset > range->count
+            || (offset == range->count && !range->append() && offset > 0)
+            || (!(range->flags & groupFlag) && offset > 0)) {
+        if (range->flags & groupFlag)
+            offset -= range->count;
+        incrementIndexes(range->count);
+        range = range->next;
+    }
+    incrementIndexes(offset);
+    return *this;
+}
+
+QDeclarativeListCompositor::insert_iterator &QDeclarativeListCompositor::insert_iterator::operator -=(int difference)
+{
+    Q_ASSERT(difference >= 0);
+    while (!(range->flags & groupFlag) && range->flags & GroupMask) {
+        decrementIndexes(offset);
+        range = range->previous;
+        offset = range->count;
+    }
+    decrementIndexes(offset);
+    offset -= difference;
+    while (offset < 0) {
+        range = range->previous;
+        if (range->flags & groupFlag)
+            offset += range->count;
+        decrementIndexes(range->count);
+    }
+    incrementIndexes(offset);
+    for (Range *previous = range->previous; offset == 0 && previous->prepend(); previous = previous->previous) {
+        if (previous->append() && previous->inGroup()) {
+            offset = previous->count;
+            range = previous;
+        } else if (!previous->inGroup()) {
+            break;
+        }
+    }
+
+    return *this;
+}
+
+QDeclarativeListCompositor::QDeclarativeListCompositor()
+    : m_end(m_ranges.next, 0, Default, 2)
+    , m_cacheIt(m_end)
+    , m_groupCount(2)
+    , m_defaultFlags(PrependFlag | DefaultFlag)
+{
+}
+
+QDeclarativeListCompositor::~QDeclarativeListCompositor()
+{
+    for (Range *next, *range = m_ranges.next; range != &m_ranges; range = next) {
+        next = range->next;
+        delete range;
+    }
+}
+
+inline QDeclarativeListCompositor::Range *QDeclarativeListCompositor::insert(
+        Range *before, void *list, int index, int count, int flags)
+{
+    return new Range(before, list, index, count, flags);
+}
+
+inline QDeclarativeListCompositor::Range *QDeclarativeListCompositor::erase(
+        Range *range)
+{
+    Range *next = range->next;
+    next->previous = range->previous;
+    next->previous->next = range->next;
+    delete range;
+    return next;
+}
+
+void QDeclarativeListCompositor::setGroupCount(int count)
+{
+    m_groupCount = count;
+    m_end = iterator(&m_ranges, 0, Default, m_groupCount);
+    m_cacheIt = m_end;
+}
+
+int QDeclarativeListCompositor::count(Group group) const
+{
+    return m_end.index[group];
+}
+
+QDeclarativeListCompositor::iterator QDeclarativeListCompositor::find(Group group, int index)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index)
+    Q_ASSERT(index >=0 && index < count(group));
+    if (m_cacheIt == m_end) {
+        m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
+        m_cacheIt += index;
+    } else {
+        const int offset = index - m_cacheIt.index[group];
+        m_cacheIt.setGroup(group);
+        if (offset > 0) {
+            m_cacheIt += offset;
+        } else if (offset < 0) {
+            m_cacheIt -= -offset;
+        } else if (offset == 0) {
+            m_cacheIt -= 0;
+            m_cacheIt += 0;
+        }
+    }
+    Q_ASSERT(m_cacheIt.index[group] == index);
+    Q_ASSERT(m_cacheIt->inGroup(group));
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+    return m_cacheIt;
+}
+
+QDeclarativeListCompositor::iterator QDeclarativeListCompositor::find(Group group, int index) const
+{
+    return const_cast<QDeclarativeListCompositor *>(this)->find(group, index);
+}
+
+QDeclarativeListCompositor::insert_iterator QDeclarativeListCompositor::findInsertPosition(Group group, int index)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index)
+    Q_ASSERT(index >=0 && index <= count(group));
+    insert_iterator it;
+    if (m_cacheIt == m_end) {
+        m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
+        it += index;
+    } else {
+        const int offset = index - m_cacheIt.index[group];
+        it = m_cacheIt;
+        it.setGroup(group);
+        if (offset > 0) {
+            it += offset;
+        } else if (offset < 0) {
+            it -= -offset;
+        } else if (offset == 0) {
+            it -= 0;
+            it += 0;
+        }
+    }
+    Q_ASSERT(it.index[group] == index);
+    return it;
+}
+
+QDeclarativeListCompositor::iterator QDeclarativeListCompositor::begin(Group group)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group)
+    m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
+    m_cacheIt += 0;
+    return m_cacheIt;
+}
+
+void QDeclarativeListCompositor::append(
+        void *list, int index, int count, int flags, QVector<Insert> *inserts)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count << flags)
+    insert(m_end, list, index, count, flags, inserts);
+}
+
+void QDeclarativeListCompositor::insert(
+        Group group, int before, void *list, int index, int count, int flags, QVector<Insert> *inserts)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << before << list << index << count << flags)
+    insert(findInsertPosition(group, before), list, index, count, flags, inserts);
+}
+
+QDeclarativeListCompositor::iterator QDeclarativeListCompositor::insert(
+        iterator before, void *list, int index, int count, int flags, QVector<Insert> *inserts)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< before << list << index << count << flags)
+    if (inserts) {
+        inserts->append(Insert(before, count, flags & GroupMask));
+    }
+    if (before.offset > 0) {
+        *before = insert(
+                *before, before->list, before->index, before.offset, before->flags & ~AppendFlag)->next;
+        before->index += before.offset;
+        before->count -= before.offset;
+        before.offset = 0;
+    }
+
+    if (!(flags & AppendFlag) && *before != m_ranges.next
+            && before->previous->list == list
+            && before->previous->flags == flags
+            && (!list || before->previous->end() == index)) {
+        before->previous->count += count;
+        before.incrementIndexes(count, flags);
+    } else {
+        *before = insert(*before, list, index, count, flags);
+        before.offset = 0;
+    }
+
+    if (!(flags & AppendFlag) && before->next != &m_ranges
+            && before->list == before->next->list
+            && before->flags == before->next->flags
+            && (!list || before->end() == before->next->index)) {
+        before->next->index = before->index;
+        before->next->count += before->count;
+        *before = erase(*before);
+    }
+
+    m_end.incrementIndexes(count, flags);
+    m_cacheIt = before;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+    return before;
+}
+
+void QDeclarativeListCompositor::setFlags(
+        Group group, int index, int count, int flags, QVector<Insert> *inserts)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index << count << flags)
+    setFlags(find(group, index), count, flags, inserts);
+}
+
+void QDeclarativeListCompositor::setFlags(
+        iterator from, int count, int flags, QVector<Insert> *inserts)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< from << count << flags)
+    if (!flags || !count)
+        return;
+
+    if (from.offset > 0) {
+        *from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
+        from->index += from.offset;
+        from->count -= from.offset;
+        from.offset = 0;
+    }
+
+    for (; count > 0; *from = from->next) {
+        if (from != from.group) {
+            from.incrementIndexes(from->count);
+            continue;
+        }
+        const int difference = qMin(count, from->count);
+        count -= difference;
+
+        const int insertFlags = ~from->flags & flags;
+        const int setFlags = (from->flags | flags) & ~AppendFlag;
+        if (insertFlags && inserts)
+            inserts->append(Insert(from, difference, insertFlags | (from->flags & CacheFlag)));
+        m_end.incrementIndexes(difference, insertFlags);
+        from.incrementIndexes(difference, setFlags);
+
+        if (from->previous != &m_ranges
+                && from->previous->list == from->list
+                && (!from->list || from->previous->end() == from->index)
+                && from->previous->flags == setFlags) {
+            from->previous->count += difference;
+            from->index += difference;
+            from->count -= difference;
+            if (from->count == 0) {
+                if (from->append())
+                    from->previous->flags |= AppendFlag;
+                *from = erase(*from)->previous;
+                continue;
+            }
+        } else if (difference < from->count) {
+            *from = insert(*from, from->list, from->index, difference, setFlags)->next;
+            from->index += difference;
+            from->count -= difference;
+        } else {
+            from->flags |= flags;
+            continue;
+        }
+        from.incrementIndexes(from->count);
+    }
+
+    if (from->previous != &m_ranges
+            && from->previous->list == from->list
+            && (!from->list || from->previous->end() == from->index)
+            && from->previous->flags == (from->flags & ~AppendFlag)) {
+        from.offset = from->previous->count;
+        from->previous->count += from->count;
+        from->previous->flags = from->flags;
+        *from = erase(*from)->previous;
+    }
+    m_cacheIt = from;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+}
+
+void QDeclarativeListCompositor::clearFlags(
+        Group group, int index, int count, int flags, QVector<Remove> *removes)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< group << index << count << flags)
+    clearFlags(find(group, index), count, flags, removes);
+}
+
+void QDeclarativeListCompositor::clearFlags(
+        iterator from, int count, int flags, QVector<Remove> *removes)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< from << count << flags)
+    if (!flags || !count)
+        return;
+
+    const bool clearCache = flags & CacheFlag;
+
+    if (from.offset > 0) {
+        *from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
+        from->index += from.offset;
+        from->count -= from.offset;
+        from.offset = 0;
+    }
+
+    for (; count > 0; *from = from->next) {
+        if (from != from.group) {
+            from.incrementIndexes(from->count);
+            continue;
+        }
+        const int difference = qMin(count, from->count);
+        count -= difference;
+
+        const int removeFlags = from->flags & flags;
+        const int clearedFlags = from->flags & ~(flags | AppendFlag);
+        if (removeFlags && removes) {
+            const int maskedFlags = clearCache
+                    ? (removeFlags & ~CacheFlag)
+                    : (removeFlags | (from->flags & CacheFlag));
+            removes->append(Remove(from, difference, maskedFlags));
+        }
+        m_end.decrementIndexes(difference, removeFlags);
+        from.incrementIndexes(difference, clearedFlags);
+
+        if (from->previous != &m_ranges
+                && from->previous->list == from->list
+                && (!from->list || clearedFlags == CacheFlag || from->previous->end() == from->index)
+                && from->previous->flags == clearedFlags) {
+            from->previous->count += difference;
+            from->index += difference;
+            from->count -= difference;
+            if (from->count == 0) {
+                if (from->append())
+                    from->previous->flags |= AppendFlag;
+                *from = erase(*from)->previous;
+            } else {
+                from.incrementIndexes(from->count);
+            }
+        } else if (difference < from->count) {
+            if (clearedFlags)
+                *from = insert(*from, from->list, from->index, difference, clearedFlags)->next;
+            from->index += difference;
+            from->count -= difference;
+            from.incrementIndexes(from->count);
+        } else if (clearedFlags) {
+            from->flags &= ~flags;
+        } else {
+            *from = erase(*from)->previous;
+        }
+    }
+
+    if (*from != &m_ranges && from->previous != &m_ranges
+            && from->previous->list == from->list
+            && (!from->list || from->previous->end() == from->index)
+            && from->previous->flags == (from->flags & ~AppendFlag)) {
+        from.offset = from->previous->count;
+        from->previous->count += from->count;
+        from->previous->flags = from->flags;
+        *from = erase(*from)->previous;
+    }
+    m_cacheIt = from;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+}
+
+void QDeclarativeListCompositor::removeList(void *list, QVector<Remove> *removes, bool destroyed)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << destroyed)
+    for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
+        if (it->list == list) {
+            const int flags = it->flags & (GroupMask | CacheFlag);
+            if (flags) {
+                removes->append(Remove(it, it->count, flags));
+                m_end.decrementIndexes(it->count, flags);
+            }
+            if (destroyed)
+                it->list = 0;
+            if (it->inCache()) {
+                it->flags = CacheFlag;
+                it.cacheIndex += it->count;
+            } else {
+                *it = erase(*it)->previous;
+            }
+        } else {
+            it.incrementIndexes(it->count);
+        }
+    }
+    m_cacheIt = m_end;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+}
+
+bool QDeclarativeListCompositor::verifyMoveTo(
+        Group fromGroup, int from, Group toGroup, int to, int count) const
+{
+    if (fromGroup != toGroup) {
+        // determine how many items from the destination group intersect with the source group.
+        iterator fromIt = find(fromGroup, from);
+
+        int intersectingCount = 0;
+
+        for (; count > 0; *fromIt = fromIt->next) {
+            if (*fromIt == &m_ranges)
+                return false;
+            if (!fromIt->inGroup(fromGroup))
+                continue;
+            if (fromIt->inGroup(toGroup))
+                intersectingCount += qMin(count, fromIt->count - fromIt.offset);
+            count -= fromIt->count - fromIt.offset;
+            fromIt.offset = 0;
+        }
+        count = intersectingCount;
+    }
+
+    return to >= 0 && to + count <= m_end.index[toGroup];
+}
+
+void QDeclarativeListCompositor::move(
+        Group fromGroup,
+        int from,
+        Group toGroup,
+        int to,
+        int count,
+        QVector<Remove> *removes,
+        QVector<Insert> *inserts)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< fromGroup << from << toGroup << to << count)
+    Q_ASSERT(count != 0);
+    Q_ASSERT(from >=0 && from + count <= m_end.index[toGroup]);
+    Q_ASSERT(verifyMoveTo(fromGroup, from, toGroup, to, count));
+
+    iterator fromIt = find(fromGroup, from);
+    if (fromIt.offset > 0) {
+        *fromIt = insert(
+                *fromIt, fromIt->list, fromIt->index, fromIt.offset, fromIt->flags & ~AppendFlag)->next;
+        fromIt->index += fromIt.offset;
+        fromIt->count -= fromIt.offset;
+        fromIt.offset = 0;
+    }
+
+    Range movedFlags;
+    for (int moveId = 0; count > 0;) {
+        if (fromIt != fromIt.group) {
+            fromIt.incrementIndexes(fromIt->count);
+            *fromIt = fromIt->next;
+            continue;
+        }
+        int difference = qMin(count, fromIt->count);
+
+        new Range(
+                &movedFlags,
+                fromIt->list,
+                fromIt->index,
+                difference,
+                fromIt->flags & ~(PrependFlag | AppendFlag));
+        if (removes)
+            removes->append(Remove(fromIt, difference, fromIt->flags, moveId++));
+        count -= difference;
+        fromIt->count -= difference;
+
+        int removeIndex = fromIt->index;
+        if (fromIt->prepend()
+                && fromIt->previous != &m_ranges
+                && fromIt->previous->flags == PrependFlag
+                && fromIt->previous->list == fromIt->list
+                && fromIt->previous->end() == fromIt->index) {
+            fromIt->previous->count += difference;
+        } else if (fromIt->prepend()) {
+            *fromIt = insert(*fromIt, fromIt->list, removeIndex, difference, PrependFlag)->next;
+        }
+        fromIt->index += difference;
+
+        if (fromIt->count == 0) {
+            if (fromIt->append())
+                fromIt->previous->flags |= AppendFlag;
+            *fromIt = erase(*fromIt);
+        } else if (count > 0) {
+            *fromIt = fromIt->next;
+        }
+    }
+
+    if (*fromIt != m_ranges.next
+            && *fromIt != &m_ranges
+            && fromIt->previous->list == fromIt->list
+            && (!fromIt->list || fromIt->previous->end() == fromIt->index)
+            && fromIt->previous->flags == (fromIt->flags & ~AppendFlag)) {
+        if (fromIt == fromIt.group)
+            fromIt.offset = fromIt->previous->count;
+        fromIt.offset = fromIt->previous->count;
+        fromIt->previous->count += fromIt->count;
+        fromIt->previous->flags = fromIt->flags;
+        *fromIt = erase(*fromIt)->previous;
+    }
+
+    insert_iterator toIt = fromIt;
+    toIt.setGroup(toGroup);
+    const int difference = to - toIt.index[toGroup];
+    if (difference > 0)
+        toIt += difference;
+    else
+        toIt -= -difference;
+
+    if (toIt.offset > 0) {
+        *toIt = insert(*toIt, toIt->list, toIt->index, toIt.offset, toIt->flags & ~AppendFlag)->next;
+        toIt->index += toIt.offset;
+        toIt->count -= toIt.offset;
+        toIt.offset = 0;
+    }
+
+    for (Range *range = movedFlags.previous; range != &movedFlags; range = range->previous) {
+        if (*toIt != &m_ranges
+                && range->list == toIt->list
+                && (!range->list || range->end() == toIt->index)
+                && range->flags == (toIt->flags & ~AppendFlag)) {
+            toIt->index -= range->count;
+            toIt->count += range->count;
+        } else {
+            *toIt = insert(*toIt, range->list, range->index, range->count, range->flags);
+        }
+    }
+
+    if (*toIt != m_ranges.next
+            && toIt->previous->list == toIt->list
+            && (!toIt->list || (toIt->previous->end() == toIt->index && toIt->previous->flags == (toIt->flags & ~AppendFlag)))) {
+        toIt.offset = toIt->previous->count;
+        toIt->previous->count += toIt->count;
+        toIt->previous->flags = toIt->flags;
+        *toIt = erase(*toIt)->previous;
+    }
+    Insert insert(toIt, 0, 0, 0);
+    for (Range *next, *range = movedFlags.next; range != &movedFlags; range = next) {
+        insert.count = range->count;
+        insert.flags = range->flags;
+        if (inserts)
+            inserts->append(insert);
+        for (int i = 0; i < m_groupCount; ++i) {
+            if (insert.inGroup(i))
+                insert.index[i] += range->count;
+        }
+        ++insert.moveId;
+        next = range->next;
+        delete range;
+    }
+
+    m_cacheIt = toIt;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+}
+
+void QDeclarativeListCompositor::clear()
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR( )
+    for (Range *range = m_ranges.next; range != &m_ranges; range = erase(range)) {}
+    m_end = iterator(m_ranges.next, 0, Default, m_groupCount);
+    m_cacheIt = m_end;
+}
+
+void QDeclarativeListCompositor::listItemsInserted(
+        QVector<Insert> *translatedInsertions,
+        void *list,
+        const QVector<QDeclarativeChangeSet::Insert> &insertions,
+        const QVector<MovedFlags> *movedFlags)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << insertions)
+    for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
+        if (it->list != list) {
+            it.incrementIndexes(it->count);
+            continue;
+        } else if (it->flags & MovedFlag) {
+            it->flags &= ~MovedFlag;
+            it.incrementIndexes(it->count);
+            continue;
+        }
+        foreach (const QDeclarativeChangeSet::Insert &insertion, insertions) {
+            int offset = insertion.index - it->index;
+            if ((offset > 0 && offset < it->count)
+                    || (offset == 0 && it->prepend())
+                    || (offset == it->count && it->append())) {
+                if (it->prepend()) {
+                    int flags = m_defaultFlags;
+                    if (insertion.isMove()) {
+                        for (QVector<MovedFlags>::const_iterator move = movedFlags->begin();
+                                move != movedFlags->end();
+                                ++move) {
+                            if (move->moveId == insertion.moveId) {
+                                flags = move->flags;
+                                break;
+                            }
+                        }
+                    }
+                    Insert translatedInsert(it, insertion.count, flags, insertion.moveId);
+                    for (int i = 0; i < m_groupCount; ++i) {
+                        if (it->inGroup(i))
+                            translatedInsert.index[i] += offset;
+                    }
+                    translatedInsertions->append(translatedInsert);
+                    if ((it->flags & ~AppendFlag) == flags) {
+                        it->count += insertion.count;
+                    } else {
+                        if (offset > 0) {
+                            it.incrementIndexes(offset);
+                            *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
+                        }
+                        *it = insert(*it, it->list, insertion.index, insertion.count, flags)->next;
+                        it.incrementIndexes(insertion.count, flags);
+                        it->index += offset + insertion.count;
+                        it->count -= offset;
+                    }
+                    m_end.incrementIndexes(insertion.count, flags);
+                } else {
+                    if (offset > 0) {
+                        *it = insert(*it, it->list, it->index, offset, it->flags)->next;
+                        it->index += offset;
+                        it->count -= offset;
+                    }
+                    it->index += insertion.count;
+                }
+            } else if (offset <= 0) {
+                it->index += insertion.count;
+            }
+        }
+        it.incrementIndexes(it->count);
+    }
+    m_cacheIt = m_end;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+}
+
+void QDeclarativeListCompositor::listItemsInserted(
+        void *list, int index, int count, QVector<Insert> *translatedInsertions)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count)
+    Q_ASSERT(count > 0);
+
+    QVector<QDeclarativeChangeSet::Insert> insertions;
+    insertions.append(QDeclarativeChangeSet::Insert(index, count));
+
+    listItemsInserted(translatedInsertions, list, insertions);
+}
+
+void QDeclarativeListCompositor::listItemsRemoved(
+        QVector<Remove> *translatedRemovals,
+        void *list,
+        QVector<QDeclarativeChangeSet::Remove> *removals,
+        QVector<QDeclarativeChangeSet::Insert> *insertions,
+        QVector<MovedFlags> *movedFlags, int moveId)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << *removals)
+
+    for (iterator it(m_ranges.next, 0, Default, m_groupCount);
+            *it != &m_ranges && !removals->isEmpty();
+            *it = it->next) {
+        if (it->list != list) {
+            it.incrementIndexes(it->count);
+            continue;
+        }
+        bool removed = false;
+        for (QVector<QDeclarativeChangeSet::Remove>::iterator removal = removals->begin();
+                !removed && removal != removals->end();
+                ++removal) {
+            int relativeIndex = removal->index - it->index;
+            int itemsRemoved = removal->count;
+            if (relativeIndex + removal->count > 0 && relativeIndex < it->count) {
+                const int offset = qMax(0, relativeIndex);
+                int removeCount = qMin(it->count, relativeIndex + removal->count) - offset;
+                it->count -= removeCount;
+                int removeFlags = it->flags & RemoveFlags;
+                Remove translatedRemoval(it, removeCount, it->flags);
+                for (int i = 0; i < m_groupCount; ++i) {
+                    if (it->inGroup(i))
+                        translatedRemoval.index[i] += offset;
+                }
+                if (removal->isMove()) {
+                    QVector<QDeclarativeChangeSet::Insert>::iterator insertion = insertions->begin();
+                    for (; insertion != insertions->end() && insertion->moveId != removal->moveId;
+                            ++insertion) {}
+                    Q_ASSERT(insertion != insertions->end());
+                    Q_ASSERT(insertion->count == removal->count);
+
+                    if (relativeIndex < 0) {
+                        int splitMoveId = ++moveId;
+                        removal = removals->insert(removal, QDeclarativeChangeSet::Remove(
+                                removal->index, -relativeIndex, splitMoveId));
+                        ++removal;
+                        removal->count -= -relativeIndex;
+                        insertion = insertions->insert(insertion, QDeclarativeChangeSet::Insert(
+                                insertion->index, -relativeIndex, splitMoveId));
+                        ++insertion;
+                        insertion->index += -relativeIndex;
+                        insertion->count -= -relativeIndex;
+                    }
+
+                    if (it->prepend()) {
+                        removeFlags |= it->flags & CacheFlag;
+                        translatedRemoval.moveId = ++moveId;
+                        movedFlags->append(MovedFlags(moveId, it->flags & ~AppendFlag));
+
+                        removal = removals->insert(removal, QDeclarativeChangeSet::Remove(
+                                removal->index, removeCount, translatedRemoval.moveId));
+                        ++removal;
+                        insertion = insertions->insert(insertion, QDeclarativeChangeSet::Insert(
+                                insertion->index, removeCount, translatedRemoval.moveId));
+                        ++insertion;
+
+                        removal->count -= removeCount;
+                        insertion->index += removeCount;
+                        insertion->count -= removeCount;
+                        if (removal->count == 0) {
+                            removal = removals->erase(removal);
+                            insertion = insertions->erase(insertion);
+                            --removal;
+                            --insertion;
+                        }
+                    } else {
+                        if (offset > 0) {
+                            *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
+                            it->index += offset;
+                            it->count -= offset;
+                            it.incrementIndexes(offset);
+                        }
+                        if (it->previous != &m_ranges
+                                && it->previous->list == it->list
+                                && it->end() == insertion->index
+                                && it->previous->flags == (it->flags | MovedFlag)) {
+                            it->previous->count += removeCount;
+                        } else {
+                            *it = insert(*it, it->list, insertion->index, removeCount, it->flags | MovedFlag)->next;
+                        }
+                        translatedRemoval.flags = 0;
+                        removeFlags = 0;
+                    }
+                } else if (it->inCache()) {
+                    if (offset > 0) {
+                        *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
+                        it->index += offset;
+                        it->count -= offset;
+                        it.incrementIndexes(offset);
+                    }
+                    if (it->previous != &m_ranges
+                            && it->previous->list == it->list
+                            && it->previous->flags == CacheFlag) {
+                        it->previous->count += removeCount;
+                    } else {
+                        *it = insert(*it, it->list, -1, removeCount, CacheFlag)->next;
+                    }
+                }
+                if (removeFlags & GroupMask)
+                    translatedRemovals->append(translatedRemoval);
+                m_end.decrementIndexes(removeCount, removeFlags);
+                if (it->count == 0 && !it->append()) {
+                    *it = erase(*it)->previous;
+                    removed = true;
+                } else if (relativeIndex <= 0) {
+                    it->index = removal->index;
+                }
+            } else if (relativeIndex < 0) {
+                it->index -= itemsRemoved;
+            }
+        }
+        if (it->next != &m_ranges
+                && it->list == it->next->list
+                && (it->flags == CacheFlag || it->end() == it->next->index)
+                && it->flags == (it->next->flags & ~AppendFlag)) {
+            it->count += it->next->count;
+            it->flags = it->next->flags;
+            erase(it->next);
+            *it = it->previous;
+        } else if (!removed) {
+            it.incrementIndexes(it->count);
+        }
+    }
+    m_cacheIt = m_end;
+    QT_DECLARATIVE_VERIFY_LISTCOMPOSITOR
+}
+
+void QDeclarativeListCompositor::listItemsRemoved(
+        void *list, int index, int count, QVector<Remove> *translatedRemovals)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count)
+    Q_ASSERT(count >= 0);
+
+    QVector<QDeclarativeChangeSet::Remove> removals;
+    removals.append(QDeclarativeChangeSet::Remove(index, count));
+    listItemsRemoved(translatedRemovals, list, &removals, 0, 0, 0);
+}
+
+void QDeclarativeListCompositor::listItemsMoved(
+        void *list,
+        int from,
+        int to,
+        int count,
+        QVector<Remove> *translatedRemovals,
+        QVector<Insert> *translatedInsertions)
+{
+
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << from << to << count)
+    Q_ASSERT(count >= 0);
+
+    QVector<QDeclarativeChangeSet::Remove> removals;
+    QVector<QDeclarativeChangeSet::Insert> insertions;
+    QVector<MovedFlags> movedFlags;
+    removals.append(QDeclarativeChangeSet::Remove(from, count, 0));
+    insertions.append(QDeclarativeChangeSet::Insert(to, count, 0));
+
+    listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags, 0);
+    listItemsInserted(translatedInsertions, list, insertions, &movedFlags);
+}
+
+void QDeclarativeListCompositor::listItemsChanged(
+        QVector<Change> *translatedChanges,
+        void *list,
+        const QVector<QDeclarativeChangeSet::Change> &changes)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << changes)
+    for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
+        if (!it->inGroup()) {
+            continue;
+        } else if (it->list != list) {
+            it.incrementIndexes(it->count);
+            continue;
+        }
+        foreach (const QDeclarativeChangeSet::Change &change, changes) {
+            const int offset = change.index - it->index;
+            if (offset + change.count > 0 && offset < it->count) {
+                const int changeOffset = qMax(0, offset);
+                const int changeCount = qMin(it->count, offset + change.count) - changeOffset;
+
+                Change translatedChange(it, changeCount, it->flags);
+                for (int i = 0; i < m_groupCount; ++i) {
+                    if (it->inGroup(i))
+                        translatedChange.index[i] += changeOffset;
+                }
+                translatedChanges->append(translatedChange);
+            }
+        }
+        it.incrementIndexes(it->count);
+    }
+}
+
+void QDeclarativeListCompositor::listItemsChanged(
+        void *list, int index, int count, QVector<Change> *translatedChanges)
+{
+    QT_DECLARATIVE_TRACE_LISTCOMPOSITOR(<< list << index << count)
+    Q_ASSERT(count >= 0);
+    QVector<QDeclarativeChangeSet::Change> changes;
+    changes.append(QDeclarativeChangeSet::Change(index, count));
+    listItemsChanged(translatedChanges, list, changes);
+}
+
+void QDeclarativeListCompositor::listChanged(
+        void *list,
+        const QDeclarativeChangeSet &changeSet,
+        QVector<Remove> *translatedRemovals,
+        QVector<Insert> *translatedInsertions,
+        QVector<Change> *translatedChanges)
+{
+    QVector<QDeclarativeChangeSet::Remove> removals = changeSet.removes();
+    QVector<QDeclarativeChangeSet::Insert> insertions = changeSet.inserts();
+    QVector<MovedFlags> movedFlags;
+    listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags, changeSet.moveCounter());
+    listItemsInserted(translatedInsertions, list, insertions, &movedFlags);
+    listItemsChanged(translatedChanges, list, changeSet.changes());
+}
+
+void QDeclarativeListCompositor::transition(
+        Group from,
+        Group to,
+        QVector<QDeclarativeChangeSet::Remove> *removes,
+        QVector<QDeclarativeChangeSet::Insert> *inserts)
+{
+    int removeCount = 0;
+    for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
+        if (it == from && it != to) {
+            removes->append(QDeclarativeChangeSet::Remove(it.index[from]- removeCount, it->count));
+            removeCount += it->count;
+        } else if (it != from && it == to) {
+            inserts->append(QDeclarativeChangeSet::Insert(it.index[to], it->count));
+        }
+        it.incrementIndexes(it->count);
+    }
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Group &group)
+{
+    switch (group) {
+    case QDeclarativeListCompositor::Cache:   return debug << "Cache";
+    case QDeclarativeListCompositor::Default: return debug << "Default";
+    default: return (debug.nospace() << "Group" << int(group)).space();
+    }
+
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Range &range)
+{
+    (debug.nospace()
+            << "Range("
+            << range.list) << " "
+            << range.index << " "
+            << range.count << " "
+            << (range.append() ? "A" : "0")
+            << (range.prepend() ? "P" : "0");
+    for (int i = QDeclarativeListCompositor::MaximumGroupCount - 1; i >= 2; --i)
+        debug << (range.inGroup(i) ? "1" : "0");
+    return (debug
+            << (range.inGroup(QDeclarativeListCompositor::Default) ? "D" : "0")
+            << (range.inGroup(QDeclarativeListCompositor::Cache) ? "C" : "0"));
+}
+
+static void qt_print_indexes(QDebug &debug, int count, const int *indexes)
+{
+    for (int i = count - 1; i >= 0; --i)
+        debug << indexes[i];
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::iterator &it)
+{
+    (debug.nospace() << "iterator(" << it.group).space() << "offset:" << it.offset;
+    qt_print_indexes(debug, it.groupCount, it.index);
+    return ((debug << **it).nospace() << ")").space();
+}
+
+static QDebug qt_print_change(QDebug debug, const char *name, const QDeclarativeListCompositor::Change &change)
+{
+    debug.nospace() << name << "(" << change.moveId << " " << change.count << " ";
+    for (int i = QDeclarativeListCompositor::MaximumGroupCount - 1; i >= 2; --i)
+        debug << (change.inGroup(i) ? "1" : "0");
+    debug << (change.inGroup(QDeclarativeListCompositor::Default) ? "D" : "0")
+            << (change.inGroup(QDeclarativeListCompositor::Cache) ? "C" : "0");
+    int i = QDeclarativeListCompositor::MaximumGroupCount - 1;
+    for (; i >= 0 && !change.inGroup(i); --i) {}
+    for (; i >= 0; --i)
+        debug << " " << change.index[i];
+    return (debug << ")").maybeSpace();
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Change &change)
+{
+    return qt_print_change(debug, "Change", change);
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Remove &remove)
+{
+    return qt_print_change(debug, "Remove", remove);
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Insert &insert)
+{
+    return qt_print_change(debug, "Insert", insert);
+}
+
+QDebug operator <<(QDebug debug, const QDeclarativeListCompositor &list)
+{
+    int indexes[QDeclarativeListCompositor::MaximumGroupCount];
+    for (int i = 0; i < QDeclarativeListCompositor::MaximumGroupCount; ++i)
+        indexes[i] = 0;
+    debug.nospace() << "QDeclarativeListCompositor(";
+    qt_print_indexes(debug, list.m_groupCount, list.m_end.index);
+    for (QDeclarativeListCompositor::Range *range = list.m_ranges.next; range != &list.m_ranges; range = range->next) {
+        (debug << "\n").space();
+        qt_print_indexes(debug, list.m_groupCount, indexes);
+        debug << " " << *range;
+
+        for (int i = 0; i < list.m_groupCount; ++i) {
+            if (range->inGroup(i))
+                indexes[i] += range->count;
+        }
+    }
+    return (debug << ")").maybeSpace();
+}
diff --git a/src/declarative/util/qdeclarativelistcompositor_p.h b/src/declarative/util/qdeclarativelistcompositor_p.h
new file mode 100644
index 0000000000..cd2d9b3f5f
--- /dev/null
+++ b/src/declarative/util/qdeclarativelistcompositor_p.h
@@ -0,0 +1,370 @@
+/****************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtDeclarative module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QDECLARATIVELISTCOMPOSITOR_P_H
+#define QDECLARATIVELISTCOMPOSITOR_P_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists purely as an
+// implementation detail.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <QtCore/qglobal.h>
+#include <QtCore/qvector.h>
+
+#include <private/qdeclarativechangeset_p.h>
+
+#include <QtCore/qdebug.h>
+
+QT_BEGIN_NAMESPACE
+
+class Q_AUTOTEST_EXPORT QDeclarativeListCompositor
+{
+public:
+    enum { MaximumGroupCount = 10 };
+
+    enum Group
+    {
+        Cache   = 0,
+        Default = 1
+    };
+
+    enum Flag
+    {
+        CacheFlag   = 0x000001,
+        DefaultFlag = 0x000002,
+        GroupMask   = 0x00FFFE,
+        PrependFlag = 0x100000,
+        AppendFlag  = 0x200000,
+        MovedFlag   = 0x400000,
+        RemoveFlags = GroupMask | PrependFlag | AppendFlag
+    };
+
+    class Range
+    {
+    public:
+        Range() : next(this), previous(this), list(0), index(0), count(0), flags(0) {}
+        Range(Range *next, void *list, int index, int count, uint flags)
+            : next(next), previous(next->previous), list(list), index(index), count(count), flags(flags) {
+            next->previous = this; previous->next = this; }
+
+        Range *next;
+        Range *previous;
+        void *list;
+        int index;
+        int count;
+        int flags;
+
+        inline int start() const { return index; }
+        inline int end() const { return index + count; }
+
+        inline int groups() const { return flags & GroupMask; }
+
+        inline bool inGroup() const { return flags & GroupMask; }
+        inline bool inCache() const { return flags & CacheFlag; }
+        inline bool inGroup(int group) const { return flags & (1 << group); }
+
+        inline bool prepend() const { return flags & PrependFlag; }
+        inline bool append() const { return flags & AppendFlag; }
+    };
+
+    class Q_AUTOTEST_EXPORT iterator
+    {
+    public:
+        inline iterator();
+        inline iterator(const iterator &it);
+        inline iterator(Range *range, int offset, Group group, int groupCount);
+        inline ~iterator() {}
+
+        bool operator ==(const iterator &it) const { return range == it.range && offset == it.offset; }
+        bool operator !=(const iterator &it) const { return range != it.range || offset != it.offset; }
+
+        bool operator ==(Group group) const { return range->flags & (1 << group); }
+        bool operator !=(Group group) const { return !(range->flags & (1 << group)); }
+
+        Range *&operator *() { return range; }
+        Range * const &operator *() const { return range; }
+        Range *operator ->() { return range; }
+        const Range *operator ->() const { return range; }
+
+        iterator &operator ++();
+        iterator &operator +=(int difference);
+        iterator &operator -=(int difference);
+
+        template<typename T> T *list() const { return static_cast<T *>(range->list); }
+        int modelIndex() const { return range->index + offset; }
+
+        void incrementIndexes(int difference) { incrementIndexes(difference, range->flags); }
+        void decrementIndexes(int difference) { decrementIndexes(difference, range->flags); }
+
+        inline void incrementIndexes(int difference, int flags);
+        inline void decrementIndexes(int difference, int flags);
+
+        void setGroup(Group g) { group = g; groupFlag = 1 << g; }
+
+        Range *range;
+        int offset;
+        Group group;
+        int groupFlag;
+        int groupCount;
+        union {
+            struct {
+                int cacheIndex;
+            };
+            int index[MaximumGroupCount];
+        };
+    };
+
+    class Q_AUTOTEST_EXPORT insert_iterator : public iterator
+    {
+    public:
+        inline insert_iterator() {}
+        inline insert_iterator(const iterator &it) : iterator(it) {}
+        inline insert_iterator(Range *, int, Group, int);
+        inline ~insert_iterator() {}
+
+        insert_iterator &operator ++();
+        insert_iterator &operator +=(int difference);
+        insert_iterator &operator -=(int difference);
+    };
+
+    struct Change
+    {
+        inline Change() {}
+        inline Change(iterator it, int count, int flags, int moveId = -1);
+        int count;
+        int flags;
+        int moveId;
+        union {
+            struct {
+                int cacheIndex;
+            };
+            int index[MaximumGroupCount];
+        };
+
+        inline bool isMove() const { return moveId >= 0; }
+        inline bool inCache() const { return flags & CacheFlag; }
+        inline bool inGroup() const { return flags & GroupMask; }
+        inline bool inGroup(int group) const { return flags & (CacheFlag << group); }
+
+        inline int groups() const { return flags & GroupMask; }
+    };
+
+    struct Insert : public Change
+    {
+        Insert() {}
+        Insert(iterator it, int count, int flags, int moveId = -1)
+            : Change(it, count, flags, moveId) {}
+    };
+
+    struct Remove : public Change
+    {
+        Remove() {}
+        Remove(iterator it, int count, int flags, int moveId = -1)
+            : Change(it, count, flags, moveId) {}
+    };
+
+    QDeclarativeListCompositor();
+    ~QDeclarativeListCompositor();
+
+    int defaultGroups() const { return m_defaultFlags & ~PrependFlag; }
+    void setDefaultGroups(int groups) { m_defaultFlags = groups | PrependFlag; }
+    void setDefaultGroup(Group group) { m_defaultFlags |= (1 << group); }
+    void clearDefaultGroup(Group group) { m_defaultFlags &= ~(1 << group); }
+    void setGroupCount(int count);
+
+    int count(Group group) const;
+    iterator find(Group group, int index);
+    iterator find(Group group, int index) const;
+    insert_iterator findInsertPosition(Group group, int index);
+
+    iterator begin(Group group);
+    const iterator &end() { return m_end; }
+
+    void append(void *list, int index, int count, int flags, QVector<Insert> *inserts = 0);
+    void insert(Group group, int before, void *list, int index, int count, int flags, QVector<Insert> *inserts = 0);
+    iterator insert(iterator before, void *list, int index, int count, int flags, QVector<Insert> *inserts = 0);
+
+    void setFlags(Group group, int index, int count, int flags, QVector<Insert> *inserts = 0);
+    void setFlags(iterator from, int count, int flags, QVector<Insert> *inserts = 0);
+
+    void clearFlags(Group group, int index, int count, int flags, QVector<Remove> *removals = 0);
+    void clearFlags(iterator from, int count, int flags, QVector<Remove> *removals = 0);
+
+    void removeList(void *list, QVector<Remove> *removals, bool destroyed);
+
+    bool verifyMoveTo(Group fromGroup, int from, Group toGroup, int to, int count) const;
+
+    void move(
+            Group fromGroup,
+            int from,
+            Group toGroup,
+            int to,
+            int count,
+            QVector<Remove> *removals = 0,
+            QVector<Insert> *inserts = 0);
+    void clear();
+
+    void listItemsInserted(void *list, int index, int count, QVector<Insert> *inserts);
+    void listItemsRemoved(void *list, int index, int count, QVector<Remove> *removals);
+    void listItemsMoved(void *list, int from, int to, int count, QVector<Remove> *removals, QVector<Insert> *inserts);
+    void listItemsChanged(void *list, int index, int count, QVector<Change> *changes);
+    void listChanged(
+            void *list,
+            const QDeclarativeChangeSet &changeSet,
+            QVector<Remove> *removals,
+            QVector<Insert> *inserts,
+            QVector<Change> *changes);
+
+    void transition(
+            Group from,
+            Group to,
+            QVector<QDeclarativeChangeSet::Remove> *removes,
+            QVector<QDeclarativeChangeSet::Insert> *inserts);
+
+private:
+    Range m_ranges;
+    iterator m_end;
+    iterator m_cacheIt;
+    int m_groupCount;
+    int m_defaultFlags;
+
+    inline Range *insert(Range *before, void *list, int index, int count, int flags);
+    inline Range *erase(Range *range);
+
+    struct MovedFlags
+    {
+        MovedFlags() {}
+        MovedFlags(int moveId, int flags) : moveId(moveId), flags(flags) {}
+
+        int moveId;
+        int flags;
+    };
+
+    void listItemsRemoved(
+            QVector<Remove> *translatedRemovals,
+            void *list,
+            QVector<QDeclarativeChangeSet::Remove> *removals,
+            QVector<QDeclarativeChangeSet::Insert> *insertions = 0,
+            QVector<MovedFlags> *movedFlags = 0,
+            int moveId = 0);
+    void listItemsInserted(
+            QVector<Insert> *translatedInsertions,
+            void *list,
+            const QVector<QDeclarativeChangeSet::Insert> &insertions,
+            const QVector<MovedFlags> *movedFlags = 0);
+    void listItemsChanged(
+            QVector<Change> *translatedChanges,
+            void *list,
+            const QVector<QDeclarativeChangeSet::Change> &changes);
+
+    friend Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor &list);
+};
+
+inline QDeclarativeListCompositor::iterator::iterator()
+    : range(0), offset(0), group(Default), groupCount(0) {}
+inline QDeclarativeListCompositor::iterator::iterator(const iterator &it)
+    : range(it.range)
+    , offset(it.offset)
+    , group(it.group)
+    , groupFlag(it.groupFlag)
+    , groupCount(it.groupCount)
+{
+    for (int i = 0; i < groupCount; ++i)
+        index[i] = it.index[i];
+}
+
+inline QDeclarativeListCompositor::iterator::iterator(
+        Range *range, int offset, Group group, int groupCount)
+    : range(range)
+    , offset(offset)
+    , group(group)
+    , groupFlag(1 << group)
+    , groupCount(groupCount)
+{
+    for (int i = 0; i < groupCount; ++i)
+        index[i] = 0;
+}
+
+inline void QDeclarativeListCompositor::iterator::incrementIndexes(int difference, int flags)
+{
+    for (int i = 0; i < groupCount; ++i) {
+        if (flags & (1 << i))
+            index[i] += difference;
+    }
+}
+
+inline void QDeclarativeListCompositor::iterator::decrementIndexes(int difference, int flags)
+{
+    for (int i = 0; i < groupCount; ++i) {
+        if (flags & (1 << i))
+            index[i] -= difference;
+    }
+}
+
+inline QDeclarativeListCompositor::insert_iterator::insert_iterator(
+        Range *range, int offset, Group group, int groupCount)
+    : iterator(range, offset, group, groupCount) {}
+
+inline QDeclarativeListCompositor::Change::Change(iterator it, int count, int flags, int moveId)
+    : count(count), flags(flags), moveId(moveId)
+{
+    for (int i = 0; i < MaximumGroupCount; ++i)
+        index[i] = it.index[i];
+}
+
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Group &group);
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Range &range);
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::iterator &it);
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Change &change);
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Remove &remove);
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor::Insert &insert);
+Q_AUTOTEST_EXPORT QDebug operator <<(QDebug debug, const QDeclarativeListCompositor &list);
+
+QT_END_NAMESPACE
+
+#endif
diff --git a/src/declarative/util/util.pri b/src/declarative/util/util.pri
index ddd702609c..ae67a8618d 100644
--- a/src/declarative/util/util.pri
+++ b/src/declarative/util/util.pri
@@ -29,6 +29,7 @@ SOURCES += \
     $$PWD/qdeclarativelistmodelworkeragent.cpp \
     $$PWD/qdeclarativepath.cpp \
     $$PWD/qdeclarativechangeset.cpp \
+    $$PWD/qdeclarativelistcompositor.cpp \
     $$PWD/qlistmodelinterface.cpp \
     $$PWD/qdeclarativepathinterpolator.cpp \
     $$PWD/qdeclarativesvgparser.cpp
@@ -67,6 +68,7 @@ HEADERS += \
     $$PWD/qdeclarativepath_p.h \
     $$PWD/qdeclarativepath_p_p.h \
     $$PWD/qdeclarativechangeset_p.h \
+    $$PWD/qdeclarativelistcompositor_p.h \
     $$PWD/qlistmodelinterface_p.h \
     $$PWD/qdeclarativepathinterpolator_p.h \
     $$PWD/qdeclarativesvgparser_p.h