src/quick/util/qquicklistcompositor.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtQml module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qquicklistcompositor_p.h"
  43
  44 #include <QtCore/qvarlengtharray.h>
  45
  46 //#define QT_QML_VERIFY_MINIMAL
  47 //#define QT_QML_VERIFY_INTEGRITY
  48
  49 QT_BEGIN_NAMESPACE
  50
  51 /*!
  52     \class QQuickListCompositor
  53     \brief The QQuickListCompositor class provides a lookup table for filtered, or re-ordered list
  54     indexes.
  55     \internal
  56
  57     QQuickListCompositor is intended as an aid for developing proxy models.  It doesn't however
  58     directly proxy a list or model, instead a range of indexes from one or many lists can be
  59     inserted into the compositor and then categorized and shuffled around and it will manage the
  60     task of translating from an index in the combined space into an index in a particular list.
  61
  62     Within a compositor indexes are categorized into groups where a group is a sub-set of the
  63     total indexes referenced by the compositor, each with an address space ranging from 0 to
  64     the number of indexes in the group - 1.  Group memberships are independent of each other with
  65     the one exception that items always retain the same order so if an index is moved within a
  66     group, its position in other groups will change as well.
  67
  68     The iterator classes encapsulate information about a specific position in a compositor group.
  69     This includes a source list, the index of an item within that list and the groups that item
  70     is a member of.  The iterator for a specific position in a group can be retrieved with the
  71     find() function and the addition and subtraction operators of the iterators can be used to
  72     navigate to adjacent items in the same group.
  73
  74     Items can be added to the compositor with the append() and insert() functions, group
  75     membership can be changed with the setFlags() and clearFlags() functions, and the position
  76     of items in the compositor can be changed with the move() function.  Each of these functions
  77     optionally returns a list of the changes made to indexes within each group which can then
  78     be propagated to view so that it can correctly refresh its contents; e.g. 3 items
  79     removed at index 6, and 5 items inserted at index 1.  The notification changes are always
  80     ordered from the start of the list to the end and accumulate, so if 5 items are removed at
  81     index 4, one is skipped and then 3 move are removed, the changes returned are 5 items removed
  82     at index 4, followed by 3 items removed at index 4.
  83
  84     When the contents of a source list change, the mappings within the compositor can be updated
  85     with the listItemsInserted(), listItemsRemoved(), listItemsMoved(), and listItemsChanged()
  86     functions.  Like the direct manipulation functions these too return a list of group indexes
  87     affected by the change.  If items are removed from a source list they are also removed from
  88     any groups they belong to with the one exception being items belonging to the \l Cache group.
  89     When items belonging to this group are removed the list, index, and other group membership
  90     information are discarded but Cache membership is retained until explicitly removed.  This
  91     allows the cache index to be retained until cached resources for that item are actually
  92     released.
  93
  94     Internally the index mapping is stored as a list of Range objects, each has a list identifier,
  95     a start index, a count, and a set of flags which represent group membership and some other
  96     properties.  The group index of a range is the sum of all preceding ranges that are members of
  97     that group.  To avoid the inefficiency of iterating over potentially all ranges when looking
  98     for a specific index, each time a lookup is done the range and its indexes are cached and the
  99     next lookup is done relative to this.   This works out to near constant time in most relevant
 100     use cases because successive index lookups are most frequently adjacent.  The total number of
 101     ranges is often quite small, which helps as well. If there is a need for faster random access
 102     then a skip list like index may be an appropriate addition.
 103
 104     \sa VisualDataModel
 105 */
 106
 107 #ifdef QT_QML_VERIFY_MINIMAL
 108 #define QT_QML_VERIFY_INTEGRITY
 109 /*
 110     Diagnostic to verify there are no consecutive ranges, or that the compositor contains the
 111     most compact representation possible.
 112
 113     Returns false and prints a warning if any range has a starting index equal to the end
 114     (index + count) index of the previous range, and both ranges also have the same flags and list
 115     property.
 116
 117     If there are no consecutive ranges this will return true.
 118 */
 119
 120 static bool qt_verifyMinimal(
 121         const QQuickListCompositor::iterator &begin,
 122         const QQuickListCompositor::iterator &end)
 123 {
 124     bool minimal = true;
 125     int index = 0;
 126
 127     for (const QQuickListCompositor::Range *range = begin->next; range != *end; range = range->next, ++index) {
 128         if (range->previous->list == range->list
 129                 && range->previous->flags == (range->flags & ~QQuickListCompositor::AppendFlag)
 130                 && range->previous->end() == range->index) {
 131             qWarning() << index << "Consecutive ranges";
 132             qWarning() << *range->previous;
 133             qWarning() << *range;
 134             minimal = false;
 135         }
 136     }
 137
 138     return minimal;
 139 }
 140
 141 #endif
 142
 143 #ifdef QT_QML_VERIFY_INTEGRITY
 144 static bool qt_printInfo(const QQuickListCompositor &compositor)
 145 {
 146     qWarning() << compositor;
 147     return true;
 148 }
 149
 150 /*
 151     Diagnostic to verify the integrity of a compositor.
 152
 153     Per range this verifies there are no invalid range combinations, that non-append ranges have
 154     positive non-zero counts, and that list ranges have non-negative indexes.
 155
 156     Accumulatively this verifies that the cached total group counts match the sum of counts
 157     of member ranges.
 158 */
 159
 160 static bool qt_verifyIntegrity(
 161         const QQuickListCompositor::iterator &begin,
 162         const QQuickListCompositor::iterator &end,
 163         const QQuickListCompositor::iterator &cachedIt)
 164 {
 165     bool valid = true;
 166
 167     int index = 0;
 168     QQuickListCompositor::iterator it;
 169     for (it = begin; *it != *end; *it = it->next) {
 170         if (it->count == 0 && !it->append()) {
 171             qWarning() << index << "Empty non-append range";
 172             valid = false;
 173         }
 174         if (it->count < 0) {
 175             qWarning() << index << "Negative count";
 176             valid = false;
 177         }
 178         if (it->list && it->flags != QQuickListCompositor::CacheFlag && it->index < 0) {
 179             qWarning() << index <<"Negative index";
 180             valid = false;
 181         }
 182         if (it->previous->next != it.range) {
 183             qWarning() << index << "broken list: it->previous->next != it.range";
 184             valid = false;
 185         }
 186         if (it->next->previous != it.range) {
 187             qWarning() << index << "broken list: it->next->previous != it.range";
 188             valid = false;
 189         }
 190         if (*it == *cachedIt) {
 191             for (int i = 0; i < end.groupCount; ++i) {
 192                 int groupIndex = it.index[i];
 193                 if (cachedIt->flags & (1 << i))
 194                     groupIndex += cachedIt.offset;
 195                 if (groupIndex != cachedIt.index[i]) {
 196                     qWarning() << index
 197                             << "invalid cached index"
 198                             << QQuickListCompositor::Group(i)
 199                             << "Expected:"
 200                             << groupIndex
 201                             << "Actual"
 202                             << cachedIt.index[i]
 203                             << cachedIt;
 204                     valid = false;
 205                 }
 206             }
 207         }
 208         it.incrementIndexes(it->count);
 209         ++index;
 210     }
 211
 212     for (int i = 0; i < end.groupCount; ++i) {
 213         if (end.index[i] != it.index[i]) {
 214             qWarning() << "Group" << i << "count invalid. Expected:" << end.index[i] << "Actual:" << it.index[i];
 215             valid = false;
 216         }
 217     }
 218     return valid;
 219 }
 220 #endif
 221
 222 #if defined(QT_QML_VERIFY_MINIMAL)
 223 #   define QT_QML_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!(qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \
 224             && qt_verifyMinimal(iterator(m_ranges.next, 0, Default, m_groupCount), m_end)) \
 225             && qt_printInfo(*this)));
 226 #elif defined(QT_QML_VERIFY_INTEGRITY)
 227 #   define QT_QML_VERIFY_LISTCOMPOSITOR Q_ASSERT(!(!qt_verifyIntegrity(iterator(m_ranges.next, 0, Default, m_groupCount), m_end, m_cacheIt) \
 228             && qt_printInfo(*this)));
 229 #else
 230 #   define QT_QML_VERIFY_LISTCOMPOSITOR
 231 #endif
 232
 233 //#define QT_QML_TRACE_LISTCOMPOSITOR(args) qDebug() << m_end.index[1] << m_end.index[0] << Q_FUNC_INFO args;
 234 #define QT_QML_TRACE_LISTCOMPOSITOR(args)
 235
 236 QQuickListCompositor::iterator &QQuickListCompositor::iterator::operator +=(int difference)
 237 {
 238     // Update all indexes to the start of the range.
 239     decrementIndexes(offset);
 240
 241     // If the iterator group isn't a member of the current range ignore the current offset.
 242     if (!(range->flags & groupFlag))
 243         offset = 0;
 244
 245     offset += difference;
 246
 247     // Iterate backwards looking for a range with a positive offset.
 248     while (offset <= 0 && range->previous->flags) {
 249         range = range->previous;
 250         if (range->flags & groupFlag)
 251             offset += range->count;
 252         decrementIndexes(range->count);
 253     }
 254
 255     // Iterate forwards looking for the first range which contains both the offset and the
 256     // iterator group.
 257     while (range->flags && (offset >= range->count || !(range->flags & groupFlag))) {
 258         if (range->flags & groupFlag)
 259             offset -= range->count;
 260         incrementIndexes(range->count);
 261         range = range->next;
 262     }
 263
 264     // Update all the indexes to inclue the remaining offset.
 265     incrementIndexes(offset);
 266
 267     return *this;
 268 }
 269
 270 QQuickListCompositor::insert_iterator &QQuickListCompositor::insert_iterator::operator +=(int difference)
 271 {
 272     iterator::operator +=(difference);
 273
 274     // If the previous range contains the append flag move the iterator to the tail of the previous
 275     // range so that appended appear after the insert position.
 276     if (offset == 0 && range->previous->append()) {
 277         range = range->previous;
 278         offset = range->inGroup() ? range->count : 0;
 279     }
 280
 281     return *this;
 282 }
 283
 284
 285 /*!
 286     Constructs an empty list compositor.
 287 */
 288
 289 QQuickListCompositor::QQuickListCompositor()
 290     : m_end(m_ranges.next, 0, Default, 2)
 291     , m_cacheIt(m_end)
 292     , m_groupCount(2)
 293     , m_defaultFlags(PrependFlag | DefaultFlag)
 294     , m_removeFlags(AppendFlag | PrependFlag | GroupMask)
 295     , m_moveId(0)
 296 {
 297 }
 298
 299 /*!
 300     Destroys a list compositor.
 301 */
 302
 303 QQuickListCompositor::~QQuickListCompositor()
 304 {
 305     for (Range *next, *range = m_ranges.next; range != &m_ranges; range = next) {
 306         next = range->next;
 307         delete range;
 308     }
 309 }
 310
 311 /*!
 312     Inserts a range with the given source \a list, start \a index, \a count and \a flags, in front
 313     of the existing range \a before.
 314 */
 315
 316 inline QQuickListCompositor::Range *QQuickListCompositor::insert(
 317         Range *before, void *list, int index, int count, uint flags)
 318 {
 319     return new Range(before, list, index, count, flags);
 320 }
 321
 322 /*!
 323     Erases a \a range from the compositor.
 324
 325     Returns a pointer to the next range in the compositor.
 326 */
 327
 328 inline QQuickListCompositor::Range *QQuickListCompositor::erase(
 329         Range *range)
 330 {
 331     Range *next = range->next;
 332     next->previous = range->previous;
 333     next->previous->next = range->next;
 334     delete range;
 335     return next;
 336 }
 337
 338 /*!
 339     Sets the the number (\a count) of possible groups that items may belong to in a compositor.
 340 */
 341
 342 void QQuickListCompositor::setGroupCount(int count)
 343 {
 344     m_groupCount = count;
 345     m_end = iterator(&m_ranges, 0, Default, m_groupCount);
 346     m_cacheIt = m_end;
 347 }
 348
 349 /*!
 350     Returns the number of items that belong to a \a group.
 351 */
 352
 353 int QQuickListCompositor::count(Group group) const
 354 {
 355     return m_end.index[group];
 356 }
 357
 358 /*!
 359     Returns an iterator representing the item at \a index in a \a group.
 360
 361     The index must be between 0 and count(group) - 1.
 362 */
 363
 364 QQuickListCompositor::iterator QQuickListCompositor::find(Group group, int index)
 365 {
 366     QT_QML_TRACE_LISTCOMPOSITOR(<< group << index)
 367     Q_ASSERT(index >=0 && index < count(group));
 368     if (m_cacheIt == m_end) {
 369         m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
 370         m_cacheIt += index;
 371     } else {
 372         const int offset = index - m_cacheIt.index[group];
 373         m_cacheIt.setGroup(group);
 374         m_cacheIt += offset;
 375     }
 376     Q_ASSERT(m_cacheIt.index[group] == index);
 377     Q_ASSERT(m_cacheIt->inGroup(group));
 378     QT_QML_VERIFY_LISTCOMPOSITOR
 379     return m_cacheIt;
 380 }
 381
 382 /*!
 383     Returns an iterator representing the item at \a index in a \a group.
 384
 385     The index must be between 0 and count(group) - 1.
 386 */
 387
 388 QQuickListCompositor::iterator QQuickListCompositor::find(Group group, int index) const
 389 {
 390     return const_cast<QQuickListCompositor *>(this)->find(group, index);
 391 }
 392
 393 /*!
 394     Returns an iterator representing an insert position in front of the item at \a index in a
 395     \a group.
 396
 397     The iterator for an insert position can sometimes resolve to a different Range than a regular
 398     iterator.  This is because when items are inserted on a boundary between Ranges, if the first
 399     range has the Append flag set then the items should be inserted into that range to ensure
 400     that the append position for the existing range remains after the insert position.
 401
 402     The index must be between 0 and count(group) - 1.
 403 */
 404
 405 QQuickListCompositor::insert_iterator QQuickListCompositor::findInsertPosition(Group group, int index)
 406 {
 407     QT_QML_TRACE_LISTCOMPOSITOR(<< group << index)
 408     Q_ASSERT(index >=0 && index <= count(group));
 409     insert_iterator it;
 410     if (m_cacheIt == m_end) {
 411         it = iterator(m_ranges.next, 0, group, m_groupCount);
 412         it += index;
 413     } else {
 414         const int offset = index - m_cacheIt.index[group];
 415         it = m_cacheIt;
 416         it.setGroup(group);
 417         it += offset;
 418     }
 419     Q_ASSERT(it.index[group] == index);
 420     return it;
 421 }
 422
 423 /*!
 424     Appends a range of \a count indexes starting at \a index from a \a list into a compositor
 425     with the given \a flags.
 426
 427     If supplied the \a inserts list will be populated with the positions of the inserted items
 428     in each group.
 429 */
 430
 431 void QQuickListCompositor::append(
 432         void *list, int index, int count, uint flags, QVector<Insert> *inserts)
 433 {
 434     QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count << flags)
 435     insert(m_end, list, index, count, flags, inserts);
 436 }
 437
 438 /*!
 439     Inserts a range of \a count indexes starting at \a index from a \a list with the given \a flags
 440     into a \a group at index \a before.
 441
 442     If supplied the \a inserts list will be populated with the positions of items inserted into
 443     each group.
 444 */
 445
 446 void QQuickListCompositor::insert(
 447         Group group, int before, void *list, int index, int count, uint flags, QVector<Insert> *inserts)
 448 {
 449     QT_QML_TRACE_LISTCOMPOSITOR(<< group << before << list << index << count << flags)
 450     insert(findInsertPosition(group, before), list, index, count, flags, inserts);
 451 }
 452
 453 /*!
 454     Inserts a range of \a count indexes starting at \a index from a \a list with the given \a flags
 455     into a compositor at position \a before.
 456
 457     If supplied the \a inserts list will be populated with the positions of items inserted into
 458     each group.
 459 */
 460
 461 QQuickListCompositor::iterator QQuickListCompositor::insert(
 462         iterator before, void *list, int index, int count, uint flags, QVector<Insert> *inserts)
 463 {
 464     QT_QML_TRACE_LISTCOMPOSITOR(<< before << list << index << count << flags)
 465     if (inserts) {
 466         inserts->append(Insert(before, count, flags & GroupMask));
 467     }
 468     if (before.offset > 0) {
 469         // Inserting into the middle of a range.  Split it two and update the iterator so it's
 470         // positioned at the start of the second half.
 471         *before = insert(
 472                 *before, before->list, before->index, before.offset, before->flags & ~AppendFlag)->next;
 473         before->index += before.offset;
 474         before->count -= before.offset;
 475         before.offset = 0;
 476     }
 477
 478
 479     if (!(flags & AppendFlag) && *before != m_ranges.next
 480             && before->previous->list == list
 481             && before->previous->flags == flags
 482             && (!list || before->previous->end() == index)) {
 483         // The insert arguments represent a continuation of the previous range so increment
 484         // its count instead of inserting a new range.
 485         before->previous->count += count;
 486         before.incrementIndexes(count, flags);
 487     } else {
 488         *before = insert(*before, list, index, count, flags);
 489         before.offset = 0;
 490     }
 491
 492     if (!(flags & AppendFlag) && before->next != &m_ranges
 493             && before->list == before->next->list
 494             && before->flags == before->next->flags
 495             && (!list || before->end() == before->next->index)) {
 496         // The current range and the next are continuous so add their counts and delete one.
 497         before->next->index = before->index;
 498         before->next->count += before->count;
 499         *before = erase(*before);
 500     }
 501
 502     m_end.incrementIndexes(count, flags);
 503     m_cacheIt = before;
 504     QT_QML_VERIFY_LISTCOMPOSITOR
 505     return before;
 506 }
 507
 508 /*!
 509     Sets the given flags \a flags on \a count items belonging to \a group starting at the position
 510     identified by \a fromGroup and the index \a from.
 511
 512     If supplied the \a inserts list will be populated with insert notifications for affected groups.
 513 */
 514
 515 void QQuickListCompositor::setFlags(
 516         Group fromGroup, int from, int count, Group group, int flags, QVector<Insert> *inserts)
 517 {
 518     QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << count << group << flags)
 519     setFlags(find(fromGroup, from), count, group, flags, inserts);
 520 }
 521
 522 /*!
 523     Sets the given flags \a flags on \a count items belonging to \a group starting at the position
 524     \a from.
 525
 526     If supplied the \a inserts list will be populated with insert notifications for affected groups.
 527 */
 528
 529 void QQuickListCompositor::setFlags(
 530         iterator from, int count, Group group, uint flags, QVector<Insert> *inserts)
 531 {
 532     QT_QML_TRACE_LISTCOMPOSITOR(<< from << count << flags)
 533     if (!flags || !count)
 534         return;
 535
 536     if (from != group) {
 537         // Skip to the next full range if the start one is not a member of the target group.
 538         from.incrementIndexes(from->count - from.offset);
 539         from.offset = 0;
 540         *from = from->next;
 541     } else if (from.offset > 0) {
 542         // If the start position is mid range split off the portion unaffected.
 543         *from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
 544         from->index += from.offset;
 545         from->count -= from.offset;
 546         from.offset = 0;
 547     }
 548
 549     for (; count > 0; *from = from->next) {
 550         if (from != from.group) {
 551             // Skip ranges that are not members of the target group.
 552             from.incrementIndexes(from->count);
 553             continue;
 554         }
 555         // Find the number of items affected in the current range.
 556         const int difference = qMin(count, from->count);
 557         count -= difference;
 558
 559         // Determine the actual changes made to the range and increment counts accordingly.
 560         const uint insertFlags = ~from->flags & flags;
 561         const uint setFlags = (from->flags | flags) & ~AppendFlag;
 562         if (insertFlags && inserts)
 563             inserts->append(Insert(from, difference, insertFlags | (from->flags & CacheFlag)));
 564         m_end.incrementIndexes(difference, insertFlags);
 565         from.incrementIndexes(difference, setFlags);
 566
 567         if (from->previous != &m_ranges
 568                 && from->previous->list == from->list
 569                 && (!from->list || from->previous->end() == from->index)
 570                 && from->previous->flags == setFlags) {
 571             // If the additional flags make the current range a continuation of the previous
 572             // then move the affected items over to the previous range.
 573             from->previous->count += difference;
 574             from->index += difference;
 575             from->count -= difference;
 576             if (from->count == 0) {
 577                 // Delete the current range if it is now empty, preserving the append flag
 578                 // in the previous range.
 579                 if (from->append())
 580                     from->previous->flags |= AppendFlag;
 581                 *from = erase(*from)->previous;
 582                 continue;
 583             } else {
 584                 break;
 585             }
 586         } else if (!insertFlags) {
 587             // No new flags, so roll onto the next range.
 588             from.incrementIndexes(from->count - difference);
 589             continue;
 590         } else if (difference < from->count) {
 591             // Create a new range with the updated flags, and remove the affected items
 592             // from the current range.
 593             *from = insert(*from, from->list, from->index, difference, setFlags)->next;
 594             from->index += difference;
 595             from->count -= difference;
 596         } else {
 597             // The whole range is affected so simply update the flags.
 598             from->flags |= flags;
 599             continue;
 600         }
 601         from.incrementIndexes(from->count);
 602     }
 603
 604     if (from->previous != &m_ranges
 605             && from->previous->list == from->list
 606             && (!from->list || from->previous->end() == from->index)
 607             && from->previous->flags == (from->flags & ~AppendFlag)) {
 608         // If the following range is now a continuation, merge it with its previous range.
 609         from.offset = from->previous->count;
 610         from->previous->count += from->count;
 611         from->previous->flags = from->flags;
 612         *from = erase(*from)->previous;
 613     }
 614     m_cacheIt = from;
 615     QT_QML_VERIFY_LISTCOMPOSITOR
 616 }
 617
 618 /*!
 619     Clears the given flags \a flags on \a count items belonging to \a group starting at the position
 620     \a from.
 621
 622     If supplied the \a removes list will be populated with remove notifications for affected groups.
 623 */
 624
 625 void QQuickListCompositor::clearFlags(
 626         Group fromGroup, int from, int count, Group group, uint flags, QVector<Remove> *removes)
 627 {
 628     QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << count << group << flags)
 629     clearFlags(find(fromGroup, from), count, group, flags, removes);
 630 }
 631
 632 /*!
 633     Clears the given flags \a flags on \a count items belonging to \a group starting at the position
 634     identified by \a fromGroup and the index \a from.
 635
 636     If supplied the \a removes list will be populated with remove notifications for affected groups.
 637 */
 638
 639 void QQuickListCompositor::clearFlags(
 640         iterator from, int count, Group group, uint flags, QVector<Remove> *removes)
 641 {
 642     QT_QML_TRACE_LISTCOMPOSITOR(<< from << count << flags)
 643     if (!flags || !count)
 644         return;
 645
 646     const bool clearCache = flags & CacheFlag;
 647
 648     if (from != group) {
 649         // Skip to the next full range if the start one is not a member of the target group.
 650         from.incrementIndexes(from->count - from.offset);
 651         from.offset = 0;
 652         *from = from->next;
 653     } else if (from.offset > 0) {
 654         // If the start position is mid range split off the portion unaffected.
 655         *from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
 656         from->index += from.offset;
 657         from->count -= from.offset;
 658         from.offset = 0;
 659     }
 660
 661     for (; count > 0; *from = from->next) {
 662         if (from != group) {
 663             // Skip ranges that are not members of the target group.
 664             from.incrementIndexes(from->count);
 665             continue;
 666         }
 667         // Find the number of items affected in the current range.
 668         const int difference = qMin(count, from->count);
 669         count -= difference;
 670
 671
 672         // Determine the actual changes made to the range and decrement counts accordingly.
 673         const uint removeFlags = from->flags & flags & ~(AppendFlag | PrependFlag);
 674         const uint clearedFlags = from->flags & ~(flags | AppendFlag | UnresolvedFlag);
 675         if (removeFlags && removes) {
 676             const int maskedFlags = clearCache
 677                     ? (removeFlags & ~CacheFlag)
 678                     : (removeFlags | (from->flags & CacheFlag));
 679             if (maskedFlags)
 680                 removes->append(Remove(from, difference, maskedFlags));
 681         }
 682         m_end.decrementIndexes(difference, removeFlags);
 683         from.incrementIndexes(difference, clearedFlags);
 684
 685         if (from->previous != &m_ranges
 686                 && from->previous->list == from->list
 687                 && (!from->list || clearedFlags == CacheFlag || from->previous->end() == from->index)
 688                 && from->previous->flags == clearedFlags) {
 689             // If the removed flags make the current range a continuation of the previous
 690             // then move the affected items over to the previous range.
 691             from->previous->count += difference;
 692             from->index += difference;
 693             from->count -= difference;
 694             if (from->count == 0) {
 695                 // Delete the current range if it is now empty, preserving the append flag
 696                 if (from->append())
 697                     from->previous->flags |= AppendFlag;
 698                 *from = erase(*from)->previous;
 699             } else {
 700                 from.incrementIndexes(from->count);
 701             }
 702         } else if (difference < from->count) {
 703             // Create a new range with the reduced flags, and remove the affected items from
 704             // the current range.
 705             if (clearedFlags)
 706                 *from = insert(*from, from->list, from->index, difference, clearedFlags)->next;
 707             from->index += difference;
 708             from->count -= difference;
 709             from.incrementIndexes(from->count);
 710         } else if (clearedFlags) {
 711             // The whole range is affected so simply update the flags.
 712             from->flags &= ~flags;
 713         } else {
 714             // All flags have been removed from the range so remove it.
 715             *from = erase(*from)->previous;
 716         }
 717     }
 718
 719     if (*from != &m_ranges && from->previous != &m_ranges
 720             && from->previous->list == from->list
 721             && (!from->list || from->previous->end() == from->index)
 722             && from->previous->flags == (from->flags & ~AppendFlag)) {
 723         // If the following range is now a continuation, merge it with its previous range.
 724         from.offset = from->previous->count;
 725         from->previous->count += from->count;
 726         from->previous->flags = from->flags;
 727         *from = erase(*from)->previous;
 728     }
 729     m_cacheIt = from;
 730     QT_QML_VERIFY_LISTCOMPOSITOR
 731 }
 732
 733 bool QQuickListCompositor::verifyMoveTo(
 734         Group fromGroup, int from, Group toGroup, int to, int count, Group group) const
 735 {
 736     if (group != toGroup) {
 737         // determine how many items from the destination group intersect with the source group.
 738         iterator fromIt = find(fromGroup, from);
 739
 740         int intersectingCount = 0;
 741
 742         for (; count > 0; *fromIt = fromIt->next) {
 743             if (*fromIt == &m_ranges)
 744                 return false;
 745             if (!fromIt->inGroup(group))
 746                 continue;
 747             if (fromIt->inGroup(toGroup))
 748                 intersectingCount += qMin(count, fromIt->count - fromIt.offset);
 749             count -= fromIt->count - fromIt.offset;
 750             fromIt.offset = 0;
 751         }
 752         count = intersectingCount;
 753     }
 754
 755     return to >= 0 && to + count <= m_end.index[toGroup];
 756 }
 757
 758 /*!
 759     \internal
 760
 761     Moves \a count items belonging to \a moveGroup from the index \a from in \a fromGroup
 762     to the index \a to in \a toGroup.
 763
 764     If \a removes and \a inserts are not null they will be populated with per group notifications
 765     of the items moved.
 766  */
 767
 768 void QQuickListCompositor::move(
 769         Group fromGroup,
 770         int from,
 771         Group toGroup,
 772         int to,
 773         int count,
 774         Group moveGroup,
 775         QVector<Remove> *removes,
 776         QVector<Insert> *inserts)
 777 {
 778     QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << toGroup << to << count)
 779     Q_ASSERT(count > 0);
 780     Q_ASSERT(from >=0);
 781     Q_ASSERT(verifyMoveTo(fromGroup, from, toGroup, to, count, moveGroup));
 782
 783     // Find the position of the first item to move.
 784     iterator fromIt = find(fromGroup, from);
 785
 786     if (fromIt != moveGroup) {
 787         // If the range at the from index doesn't contain items from the move group; skip
 788         // to the next range.
 789         fromIt.incrementIndexes(fromIt->count - fromIt.offset);
 790         fromIt.offset = 0;
 791         *fromIt = fromIt->next;
 792     } else if (fromIt.offset > 0) {
 793         // If the range at the from index contains items from the move group and the index isn't
 794         // at the start of the range; split the range at the index and move the iterator to start
 795         // of the second range.
 796         *fromIt = insert(
 797                 *fromIt, fromIt->list, fromIt->index, fromIt.offset, fromIt->flags & ~AppendFlag)->next;
 798         fromIt->index += fromIt.offset;
 799         fromIt->count -= fromIt.offset;
 800         fromIt.offset = 0;
 801     }
 802
 803     // Remove count items belonging to the move group from the list.
 804     Range movedFlags;
 805     for (int moveId = m_moveId; count > 0;) {
 806         if (fromIt != moveGroup) {
 807             // Skip ranges not containing items from the move group.
 808             fromIt.incrementIndexes(fromIt->count);
 809             *fromIt = fromIt->next;
 810             continue;
 811         }
 812         int difference = qMin(count, fromIt->count);
 813
 814         // Create a new static range containing the moved items from an existing range.
 815         new Range(
 816                 &movedFlags,
 817                 fromIt->list,
 818                 fromIt->index,
 819                 difference,
 820                 fromIt->flags & ~(PrependFlag | AppendFlag));
 821         // Remove moved items from the count, the existing range, and a remove notification.
 822         if (removes)
 823             removes->append(Remove(fromIt, difference, fromIt->flags, ++moveId));
 824         count -= difference;
 825         fromIt->count -= difference;
 826
 827         // If the existing range contains the prepend flag replace the removed items with
 828         // a placeholder range for new items inserted into the source model.
 829         int removeIndex = fromIt->index;
 830         if (fromIt->prepend()
 831                 && fromIt->previous != &m_ranges
 832                 && fromIt->previous->flags == PrependFlag
 833                 && fromIt->previous->list == fromIt->list
 834                 && fromIt->previous->end() == fromIt->index) {
 835             // Grow the previous range instead of creating a new one if possible.
 836             fromIt->previous->count += difference;
 837         } else if (fromIt->prepend()) {
 838             *fromIt = insert(*fromIt, fromIt->list, removeIndex, difference, PrependFlag)->next;
 839         }
 840         fromIt->index += difference;
 841
 842         if (fromIt->count == 0) {
 843             // If the existing range has no items remaining; remove it from the list.
 844             if (fromIt->append())
 845                 fromIt->previous->flags |= AppendFlag;
 846             *fromIt = erase(*fromIt);
 847
 848             // If the ranges before and after the removed range can be joined, do so.
 849             if (*fromIt != m_ranges.next && fromIt->flags == PrependFlag
 850                     && fromIt->previous != &m_ranges
 851                     && fromIt->previous->flags == PrependFlag
 852                     && fromIt->previous->list == fromIt->list
 853                     && fromIt->previous->end() == fromIt->index) {
 854                 fromIt.incrementIndexes(fromIt->count);
 855                 fromIt->previous->count += fromIt->count;
 856                 *fromIt = erase(*fromIt);
 857             }
 858         } else if (count > 0) {
 859             *fromIt = fromIt->next;
 860         }
 861     }
 862
 863     // Try and join the range following the removed items to the range preceding it.
 864     if (*fromIt != m_ranges.next
 865             && *fromIt != &m_ranges
 866             && fromIt->previous->list == fromIt->list
 867             && (!fromIt->list || fromIt->previous->end() == fromIt->index)
 868             && fromIt->previous->flags == (fromIt->flags & ~AppendFlag)) {
 869         if (fromIt == fromIt.group)
 870             fromIt.offset = fromIt->previous->count;
 871         fromIt.offset = fromIt->previous->count;
 872         fromIt->previous->count += fromIt->count;
 873         fromIt->previous->flags = fromIt->flags;
 874         *fromIt = erase(*fromIt)->previous;
 875     }
 876
 877     // Find the destination position of the move.
 878     insert_iterator toIt = fromIt;
 879     toIt.setGroup(toGroup);
 880
 881     const int difference = to - toIt.index[toGroup];
 882     toIt += difference;
 883
 884     // If the insert position is part way through a range; split it and move the iterator to the
 885     // start of the second range.
 886     if (toIt.offset > 0) {
 887         *toIt = insert(*toIt, toIt->list, toIt->index, toIt.offset, toIt->flags & ~AppendFlag)->next;
 888         toIt->index += toIt.offset;
 889         toIt->count -= toIt.offset;
 890         toIt.offset = 0;
 891     }
 892
 893     // Insert the moved ranges before the insert iterator, growing the previous range if that
 894     // is an option.
 895     for (Range *range = movedFlags.previous; range != &movedFlags; range = range->previous) {
 896         if (*toIt != &m_ranges
 897                 && range->list == toIt->list
 898                 && (!range->list || range->end() == toIt->index)
 899                 && range->flags == (toIt->flags & ~AppendFlag)) {
 900             toIt->index -= range->count;
 901             toIt->count += range->count;
 902         } else {
 903             *toIt = insert(*toIt, range->list, range->index, range->count, range->flags);
 904         }
 905     }
 906
 907     // Try and join the range after the inserted ranges to the last range inserted.
 908     if (*toIt != m_ranges.next
 909             && toIt->previous->list == toIt->list
 910             && (!toIt->list || (toIt->previous->end() == toIt->index && toIt->previous->flags == (toIt->flags & ~AppendFlag)))) {
 911         toIt.offset = toIt->previous->count;
 912         toIt->previous->count += toIt->count;
 913         toIt->previous->flags = toIt->flags;
 914         *toIt = erase(*toIt)->previous;
 915     }
 916     // Create insert notification for the ranges moved.
 917     Insert insert(toIt, 0, 0, 0);
 918     for (Range *next, *range = movedFlags.next; range != &movedFlags; range = next) {
 919         insert.count = range->count;
 920         insert.flags = range->flags;
 921         if (inserts) {
 922             insert.moveId = ++m_moveId;
 923             inserts->append(insert);
 924         }
 925         for (int i = 0; i < m_groupCount; ++i) {
 926             if (insert.inGroup(i))
 927                 insert.index[i] += range->count;
 928         }
 929
 930         next = range->next;
 931         delete range;
 932     }
 933
 934     m_cacheIt = toIt;
 935
 936     QT_QML_VERIFY_LISTCOMPOSITOR
 937 }
 938
 939 /*!
 940     Clears the contents of a compositor.
 941 */
 942
 943 void QQuickListCompositor::clear()
 944 {
 945     QT_QML_TRACE_LISTCOMPOSITOR( )
 946     for (Range *range = m_ranges.next; range != &m_ranges; range = erase(range)) {}
 947     m_end = iterator(m_ranges.next, 0, Default, m_groupCount);
 948     m_cacheIt = m_end;
 949 }
 950
 951 void QQuickListCompositor::listItemsInserted(
 952         QVector<Insert> *translatedInsertions,
 953         void *list,
 954         const QVector<QQuickChangeSet::Insert> &insertions,
 955         const QVector<MovedFlags> *movedFlags)
 956 {
 957     QT_QML_TRACE_LISTCOMPOSITOR(<< list << insertions)
 958     for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
 959         if (it->list != list || it->flags == CacheFlag) {
 960             // Skip ranges that don't reference list.
 961             it.incrementIndexes(it->count);
 962             continue;
 963         } else if (it->flags & MovedFlag) {
 964             // Skip ranges that were already moved in listItemsRemoved.
 965             it->flags &= ~MovedFlag;
 966             it.incrementIndexes(it->count);
 967             continue;
 968         }
 969         foreach (const QQuickChangeSet::Insert &insertion, insertions) {
 970             int offset = insertion.index - it->index;
 971             if ((offset > 0 && offset < it->count)
 972                     || (offset == 0 && it->prepend())
 973                     || (offset == it->count && it->append())) {
 974                 // The insert index is within the current range.
 975                 if (it->prepend()) {
 976                     // The range has the prepend flag set so we insert new items into the range.
 977                     uint flags = m_defaultFlags;
 978                     if (insertion.isMove()) {
 979                         // If the insert was part of a move replace the default flags with
 980                         // the flags from the source range.
 981                         for (QVector<MovedFlags>::const_iterator move = movedFlags->begin();
 982                                 move != movedFlags->end();
 983                                 ++move) {
 984                             if (move->moveId == insertion.moveId) {
 985                                 flags = move->flags;
 986                                 break;
 987                             }
 988                         }
 989                     }
 990                     if (flags & ~(AppendFlag | PrependFlag)) {
 991                         // If any items are added to groups append an insert notification.
 992                         Insert translatedInsert(it, insertion.count, flags, insertion.moveId);
 993                         for (int i = 0; i < m_groupCount; ++i) {
 994                             if (it->inGroup(i))
 995                                 translatedInsert.index[i] += offset;
 996                         }
 997                         translatedInsertions->append(translatedInsert);
 998                     }
 999                     if ((it->flags & ~AppendFlag) == flags) {
1000                         // Accumulate items on the current range it its flags are the same as
1001                         // the insert flags.
1002                         it->count += insertion.count;
1003                     } else if (offset == 0
1004                             && it->previous != &m_ranges
1005                             && it->previous->list == list
1006                             && it->previous->end() == insertion.index
1007                             && it->previous->flags == flags) {
1008                         // Attempt to append to the previous range if the insert position is at
1009                         // the start of the current range.
1010                         it->previous->count += insertion.count;
1011                         it->index += insertion.count;
1012                         it.incrementIndexes(insertion.count);
1013                     } else {
1014                         if (offset > 0) {
1015                             // Divide the current range at the insert position.
1016                             it.incrementIndexes(offset);
1017                             *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
1018                         }
1019                         // Insert a new range, and increment the start index of the current range.
1020                         *it = insert(*it, it->list, insertion.index, insertion.count, flags)->next;
1021                         it.incrementIndexes(insertion.count, flags);
1022                         it->index += offset + insertion.count;
1023                         it->count -= offset;
1024                     }
1025                     m_end.incrementIndexes(insertion.count, flags);
1026                 } else {
1027                     // The range doesn't have the prepend flag set so split the range into parts;
1028                     // one before the insert position and one after the last inserted item.
1029                     if (offset > 0) {
1030                         *it = insert(*it, it->list, it->index, offset, it->flags)->next;
1031                         it->index += offset;
1032                         it->count -= offset;
1033                     }
1034                     it->index += insertion.count;
1035                 }
1036             } else if (offset <= 0) {
1037                 // The insert position was before the current range so increment the start index.
1038                 it->index += insertion.count;
1039             }
1040         }
1041         it.incrementIndexes(it->count);
1042     }
1043     m_cacheIt = m_end;
1044     QT_QML_VERIFY_LISTCOMPOSITOR
1045 }
1046
1047 /*!
1048     Updates the contents of a compositor when \a count items are inserted into a \a list at
1049     \a index.
1050
1051     This corrects the indexes of each range for that list in the compositor, splitting the range
1052     in two if the insert index is in the middle of that range.  If a range at the insert position
1053     has the Prepend flag set then a new range will be inserted at that position with the groups
1054     specified in defaultGroups().  If the insert index corresponds to the end of a range with
1055     the Append flag set a new range will be inserted before the end of the append range.
1056
1057     The \a translatedInsertions list is populated with insert notifications for affected
1058     groups.
1059 */
1060
1061 void QQuickListCompositor::listItemsInserted(
1062         void *list, int index, int count, QVector<Insert> *translatedInsertions)
1063 {
1064     QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count)
1065     Q_ASSERT(count > 0);
1066
1067     QVector<QQuickChangeSet::Insert> insertions;
1068     insertions.append(QQuickChangeSet::Insert(index, count));
1069
1070     listItemsInserted(translatedInsertions, list, insertions);
1071 }
1072
1073 void QQuickListCompositor::listItemsRemoved(
1074         QVector<Remove> *translatedRemovals,
1075         void *list,
1076         QVector<QQuickChangeSet::Remove> *removals,
1077         QVector<QQuickChangeSet::Insert> *insertions,
1078         QVector<MovedFlags> *movedFlags)
1079 {
1080     QT_QML_TRACE_LISTCOMPOSITOR(<< list << *removals)
1081
1082     for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
1083         if (it->list != list || it->flags == CacheFlag) {
1084             // Skip ranges that don't reference list.
1085             it.incrementIndexes(it->count);
1086             continue;
1087         }
1088         bool removed = false;
1089         for (QVector<QQuickChangeSet::Remove>::iterator removal = removals->begin();
1090                 !removed && removal != removals->end();
1091                 ++removal) {
1092             int relativeIndex = removal->index - it->index;
1093             int itemsRemoved = removal->count;
1094             if (relativeIndex + removal->count > 0 && relativeIndex < it->count) {
1095                 // If the current range intersects the remove; remove the intersecting items.
1096                 const int offset = qMax(0, relativeIndex);
1097                 int removeCount = qMin(it->count, relativeIndex + removal->count) - offset;
1098                 it->count -= removeCount;
1099                 int removeFlags = it->flags & m_removeFlags;
1100                 Remove translatedRemoval(it, removeCount, it->flags);
1101                 for (int i = 0; i < m_groupCount; ++i) {
1102                     if (it->inGroup(i))
1103                         translatedRemoval.index[i] += offset;
1104                 }
1105                 if (removal->isMove()) {
1106                     // If the removal was part of a move find the corresponding insert.
1107                     QVector<QQuickChangeSet::Insert>::iterator insertion = insertions->begin();
1108                     for (; insertion != insertions->end() && insertion->moveId != removal->moveId;
1109                             ++insertion) {}
1110                     Q_ASSERT(insertion != insertions->end());
1111                     Q_ASSERT(insertion->count == removal->count);
1112
1113                     if (relativeIndex < 0) {
1114                         // If the remove started before the current range, split it and the
1115                         // corresponding insert so we're only working with intersecting part.
1116                         int splitMoveId = ++m_moveId;
1117                         removal = removals->insert(removal, QQuickChangeSet::Remove(
1118                                 removal->index, -relativeIndex, splitMoveId));
1119                         ++removal;
1120                         removal->count -= -relativeIndex;
1121                         insertion = insertions->insert(insertion, QQuickChangeSet::Insert(
1122                                 insertion->index, -relativeIndex, splitMoveId));
1123                         ++insertion;
1124                         insertion->index += -relativeIndex;
1125                         insertion->count -= -relativeIndex;
1126                     }
1127
1128                     if (it->prepend()) {
1129                         // If the current range has the prepend flag preserve its flags to transfer
1130                         // to its new location.
1131                         removeFlags |= it->flags & CacheFlag;
1132                         translatedRemoval.moveId = ++m_moveId;
1133                         movedFlags->append(MovedFlags(m_moveId, it->flags & ~AppendFlag));
1134
1135                         if (removeCount < removal->count) {
1136                             // If the remove doesn't encompass all of the current range,
1137                             // split it and the corresponding insert.
1138                             removal = removals->insert(removal, QQuickChangeSet::Remove(
1139                                     removal->index, removeCount, translatedRemoval.moveId));
1140                             ++removal;
1141                             insertion = insertions->insert(insertion, QQuickChangeSet::Insert(
1142                                     insertion->index, removeCount, translatedRemoval.moveId));
1143                             ++insertion;
1144
1145                             removal->count -= removeCount;
1146                             insertion->index += removeCount;
1147                             insertion->count -= removeCount;
1148                         } else {
1149                             // If there's no need to split the move simply replace its moveId
1150                             // with that of the translated move.
1151                             removal->moveId = translatedRemoval.moveId;
1152                             insertion->moveId = translatedRemoval.moveId;
1153                         }
1154                     } else {
1155                         // If the current range doesn't have prepend flags then insert a new range
1156                         // with list indexes from the corresponding insert location.  The MoveFlag
1157                         // is to notify listItemsInserted that it can skip evaluation of that range.
1158                         if (offset > 0) {
1159                             *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
1160                             it->index += offset;
1161                             it->count -= offset;
1162                             it.incrementIndexes(offset);
1163                         }
1164                         if (it->previous != &m_ranges
1165                                 && it->previous->list == it->list
1166                                 && it->end() == insertion->index
1167                                 && it->previous->flags == (it->flags | MovedFlag)) {
1168                             it->previous->count += removeCount;
1169                         } else {
1170                             *it = insert(*it, it->list, insertion->index, removeCount, it->flags | MovedFlag)->next;
1171                         }
1172                         // Clear the changed flags as the item hasn't been removed.
1173                         translatedRemoval.flags = 0;
1174                         removeFlags = 0;
1175                     }
1176                 } else if (it->inCache()) {
1177                     // If not moving and the current range has the cache flag, insert a new range
1178                     // with just the cache flag set to retain caching information for the removed
1179                     // range.
1180                     if (offset > 0) {
1181                         *it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
1182                         it->index += offset;
1183                         it->count -= offset;
1184                         it.incrementIndexes(offset);
1185                     }
1186                     if (it->previous != &m_ranges
1187                             && it->previous->list == it->list
1188                             && it->previous->flags == CacheFlag) {
1189                         it->previous->count += removeCount;
1190                     } else {
1191                         *it = insert(*it, it->list, -1, removeCount, CacheFlag)->next;
1192                     }
1193                     it.index[Cache] += removeCount;
1194                 }
1195                 if (removeFlags & GroupMask)
1196                     translatedRemovals->append(translatedRemoval);
1197                 m_end.decrementIndexes(removeCount, removeFlags);
1198                 if (it->count == 0 && !it->append()) {
1199                     // Erase empty non-append ranges.
1200                     *it = erase(*it)->previous;
1201                     removed = true;
1202                 } else if (relativeIndex <= 0) {
1203                     // If the remove started before the current range move the start index of
1204                     // the range to the remove index.
1205                     it->index = removal->index;
1206                 }
1207             } else if (relativeIndex < 0) {
1208                 // If the remove was before the current range decrement the start index by the
1209                 // number of items removed.
1210                 it->index -= itemsRemoved;
1211
1212                 if (it->previous != &m_ranges
1213                         && it->previous->list == it->list
1214                         && it->previous->end() == it->index
1215                         && it->previous->flags == (it->flags & ~AppendFlag)) {
1216                     // Compress ranges made continuous by the removal of separating ranges.
1217                     it.decrementIndexes(it->previous->count);
1218                     it->previous->count += it->count;
1219                     it->previous->flags = it->flags;
1220                     *it = erase(*it)->previous;
1221                 }
1222             }
1223         }
1224         if (it->flags == CacheFlag && it->next->flags == CacheFlag && it->next->list == it->list) {
1225             // Compress consecutive cache only ranges.
1226             it.index[Cache] += it->next->count;
1227             it->count += it->next->count;
1228             erase(it->next);
1229         } else if (!removed) {
1230             it.incrementIndexes(it->count);
1231         }
1232     }
1233     m_cacheIt = m_end;
1234     QT_QML_VERIFY_LISTCOMPOSITOR
1235 }
1236
1237
1238 /*!
1239     Updates the contents of a compositor when \a count items are removed from a \a list at
1240     \a index.
1241
1242     Ranges that intersect the specified range are removed from the compositor and the indexes of
1243     ranges after index + count are updated.
1244
1245     The \a translatedRemovals list is populated with remove notifications for the affected
1246     groups.
1247 */
1248
1249
1250 void QQuickListCompositor::listItemsRemoved(
1251         void *list, int index, int count, QVector<Remove> *translatedRemovals)
1252 {
1253     QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count)
1254     Q_ASSERT(count >= 0);
1255
1256     QVector<QQuickChangeSet::Remove> removals;
1257     removals.append(QQuickChangeSet::Remove(index, count));
1258     listItemsRemoved(translatedRemovals, list, &removals, 0, 0);
1259 }
1260
1261 /*!
1262     Updates the contents of a compositor when \a count items are removed from a \a list at
1263     \a index.
1264
1265     Ranges that intersect the specified range are removed from the compositor and the indexes of
1266     ranges after index + count are updated.
1267
1268     The \a translatedRemovals and translatedInserts lists are populated with move
1269     notifications for the affected groups.
1270 */
1271
1272 void QQuickListCompositor::listItemsMoved(
1273         void *list,
1274         int from,
1275         int to,
1276         int count,
1277         QVector<Remove> *translatedRemovals,
1278         QVector<Insert> *translatedInsertions)
1279 {
1280     QT_QML_TRACE_LISTCOMPOSITOR(<< list << from << to << count)
1281     Q_ASSERT(count >= 0);
1282
1283     QVector<QQuickChangeSet::Remove> removals;
1284     QVector<QQuickChangeSet::Insert> insertions;
1285     QVector<MovedFlags> movedFlags;
1286     removals.append(QQuickChangeSet::Remove(from, count, 0));
1287     insertions.append(QQuickChangeSet::Insert(to, count, 0));
1288
1289     listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags);
1290     listItemsInserted(translatedInsertions, list, insertions, &movedFlags);
1291 }
1292
1293 void QQuickListCompositor::listItemsChanged(
1294         QVector<Change> *translatedChanges,
1295         void *list,
1296         const QVector<QQuickChangeSet::Change> &changes)
1297 {
1298     QT_QML_TRACE_LISTCOMPOSITOR(<< list << changes)
1299     for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
1300         if (it->list != list || it->flags == CacheFlag) {
1301             it.incrementIndexes(it->count);
1302             continue;
1303         } else if (!it->inGroup()) {
1304             continue;
1305         }
1306         foreach (const QQuickChangeSet::Change &change, changes) {
1307             const int offset = change.index - it->index;
1308             if (offset + change.count > 0 && offset < it->count) {
1309                 const int changeOffset = qMax(0, offset);
1310                 const int changeCount = qMin(it->count, offset + change.count) - changeOffset;
1311
1312                 Change translatedChange(it, changeCount, it->flags);
1313                 for (int i = 0; i < m_groupCount; ++i) {
1314                     if (it->inGroup(i))
1315                         translatedChange.index[i] += changeOffset;
1316                 }
1317                 translatedChanges->append(translatedChange);
1318             }
1319         }
1320         it.incrementIndexes(it->count);
1321     }
1322 }
1323
1324
1325 /*!
1326     Translates the positions of \a count changed items at \a index in a \a list.
1327
1328     The \a translatedChanges list is populated with change notifications for the
1329     affected groups.
1330 */
1331
1332 void QQuickListCompositor::listItemsChanged(
1333         void *list, int index, int count, QVector<Change> *translatedChanges)
1334 {
1335     QT_QML_TRACE_LISTCOMPOSITOR(<< list << index << count)
1336     Q_ASSERT(count >= 0);
1337     QVector<QQuickChangeSet::Change> changes;
1338     changes.append(QQuickChangeSet::Change(index, count));
1339     listItemsChanged(translatedChanges, list, changes);
1340 }
1341
1342 void QQuickListCompositor::transition(
1343         Group from,
1344         Group to,
1345         QVector<QQuickChangeSet::Remove> *removes,
1346         QVector<QQuickChangeSet::Insert> *inserts)
1347 {
1348     int removeCount = 0;
1349     for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
1350         if (it == from && it != to) {
1351             removes->append(QQuickChangeSet::Remove(it.index[from]- removeCount, it->count));
1352             removeCount += it->count;
1353         } else if (it != from && it == to) {
1354             inserts->append(QQuickChangeSet::Insert(it.index[to], it->count));
1355         }
1356         it.incrementIndexes(it->count);
1357     }
1358 }
1359
1360 /*!
1361     \internal
1362     Writes the name of \a group to \a debug.
1363 */
1364
1365 QDebug operator <<(QDebug debug, const QQuickListCompositor::Group &group)
1366 {
1367     switch (group) {
1368     case QQuickListCompositor::Cache:   return debug << "Cache";
1369     case QQuickListCompositor::Default: return debug << "Default";
1370     default: return (debug.nospace() << "Group" << int(group)).space();
1371     }
1372
1373 }
1374
1375 /*!
1376     \internal
1377     Writes the contents of \a range to \a debug.
1378 */
1379
1380 QDebug operator <<(QDebug debug, const QQuickListCompositor::Range &range)
1381 {
1382     (debug.nospace()
1383             << "Range("
1384             << range.list) << ' '
1385             << range.index << ' '
1386             << range.count << ' '
1387             << (range.isUnresolved() ? 'U' : '0')
1388             << (range.append() ? 'A' : '0')
1389             << (range.prepend() ? 'P' : '0');
1390     for (int i = QQuickListCompositor::MaximumGroupCount - 1; i >= 2; --i)
1391         debug << (range.inGroup(i) ? '1' : '0');
1392     return (debug
1393             << (range.inGroup(QQuickListCompositor::Default) ? 'D' : '0')
1394             << (range.inGroup(QQuickListCompositor::Cache) ? 'C' : '0'));
1395 }
1396
1397 static void qt_print_indexes(QDebug &debug, int count, const int *indexes)
1398 {
1399     for (int i = count - 1; i >= 0; --i)
1400         debug << indexes[i];
1401 }
1402
1403 /*!
1404     \internal
1405     Writes the contents of \a it to \a debug.
1406 */
1407
1408 QDebug operator <<(QDebug debug, const QQuickListCompositor::iterator &it)
1409 {
1410     (debug.nospace() << "iterator(" << it.group).space() << "offset:" << it.offset;
1411     qt_print_indexes(debug, it.groupCount, it.index);
1412     return ((debug << **it).nospace() << ')').space();
1413 }
1414
1415 static QDebug qt_print_change(QDebug debug, const char *name, const QQuickListCompositor::Change &change)
1416 {
1417     debug.nospace() << name << '(' << change.moveId << ' ' << change.count << ' ';
1418     for (int i = QQuickListCompositor::MaximumGroupCount - 1; i >= 2; --i)
1419         debug << (change.inGroup(i) ? '1' : '0');
1420     debug << (change.inGroup(QQuickListCompositor::Default) ? 'D' : '0')
1421             << (change.inGroup(QQuickListCompositor::Cache) ? 'C' : '0');
1422     int i = QQuickListCompositor::MaximumGroupCount - 1;
1423     for (; i >= 0 && !change.inGroup(i); --i) {}
1424     for (; i >= 0; --i)
1425         debug << ' ' << change.index[i];
1426     return (debug << ')').maybeSpace();
1427 }
1428
1429 /*!
1430     \internal
1431     Writes the contents of \a change to \a debug.
1432 */
1433
1434 QDebug operator <<(QDebug debug, const QQuickListCompositor::Change &change)
1435 {
1436     return qt_print_change(debug, "Change", change);
1437 }
1438
1439 /*!
1440     \internal
1441     Writes the contents of \a remove to \a debug.
1442 */
1443
1444 QDebug operator <<(QDebug debug, const QQuickListCompositor::Remove &remove)
1445 {
1446     return qt_print_change(debug, "Remove", remove);
1447 }
1448
1449 /*!
1450     \internal
1451     Writes the contents of \a insert to \a debug.
1452 */
1453
1454 QDebug operator <<(QDebug debug, const QQuickListCompositor::Insert &insert)
1455 {
1456     return qt_print_change(debug, "Insert", insert);
1457 }
1458
1459 /*!
1460     \internal
1461     Writes the contents of \a list to \a debug.
1462 */
1463
1464 QDebug operator <<(QDebug debug, const QQuickListCompositor &list)
1465 {
1466     int indexes[QQuickListCompositor::MaximumGroupCount];
1467     for (int i = 0; i < QQuickListCompositor::MaximumGroupCount; ++i)
1468         indexes[i] = 0;
1469     debug.nospace() << "QQuickListCompositor(";
1470     qt_print_indexes(debug, list.m_groupCount, list.m_end.index);
1471     for (QQuickListCompositor::Range *range = list.m_ranges.next; range != &list.m_ranges; range = range->next) {
1472         (debug << '\n').space();
1473         qt_print_indexes(debug, list.m_groupCount, indexes);
1474         debug << ' ' << *range;
1475
1476         for (int i = 0; i < list.m_groupCount; ++i) {
1477             if (range->inGroup(i))
1478                 indexes[i] += range->count;
1479         }
1480     }
1481     return (debug << ')').maybeSpace();
1482 }
1483
1484 QT_END_NAMESPACE