QT_BEGIN_NAMESPACE
+/*!
+ \class QQuickListCompositor
+ \brief The QQuickListCompositor class provides a lookup table for filtered, or re-ordered list
+ indexes.
+ \internal
+
+ QQuickListCompositor is intended as an aid for developing proxy models. It doesn't however
+ directly proxy a list or model, instead a range of indexes from one or many lists can be
+ inserted into the compositor and then categorized and shuffled around and it will manage the
+ task of translating from an index in the combined space into an index in a particular list.
+
+ Within a compositor indexes are categorized into groups where a group is a sub-set of the
+ total indexes referenced by the compositor, each with an address space ranging from 0 to
+ the number of indexes in the group - 1. Group memberships are independent of each other with
+ the one exception that items always retain the same order so if an index is moved within a
+ group, its position in other groups will change as well.
+
+ The iterator classes encapsulate information about a specific position in a compositor group.
+ This includes a source list, the index of an item within that list and the groups that item
+ is a member of. The iterator for a specific position in a group can be retrieved with the
+ find() function and the addition and subtraction operators of the iterators can be used to
+ navigate to adjacent items in the same group.
+
+ Items can be added to the compositor with the append() and insert() functions, group
+ membership can be changed with the setFlags() and clearFlags() functions, and the position
+ of items in the compositor can be changed with the move() function. Each of these functions
+ optionally returns a list of the changes made to indexes within each group which can then
+ be propagated to view so that it can correctly refresh its contents; e.g. 3 items
+ removed at index 6, and 5 items inserted at index 1. The notification changes are always
+ ordered from the start of the list to the end and accumulate, so if 5 items are removed at
+ index 4, one is skipped and then 3 move are removed, the changes returned are 5 items removed
+ at index 4, followed by 3 items removed at index 4.
+
+ When the contents of a source list change, the mappings within the compositor can be updated
+ with the listItemsInserted(), listItemsRemoved(), listItemsMoved(), and listItemsChanged()
+ functions. Like the direct manipulation functions these too return a list of group indexes
+ affected by the change. If items are removed from a source list they are also removed from
+ any groups they belong to with the one exception being items belonging to the \l Cache group.
+ When items belonging to this group are removed the list, index, and other group membership
+ information are discarded but Cache membership is retained until explicitly removed. This
+ allows the cache index to be retained until cached resources for that item are actually
+ released.
+
+ Internally the index mapping is stored as a list of Range objects, each has a list identifier,
+ a start index, a count, and a set of flags which represent group membership and some other
+ properties. The group index of a range is the sum of all preceding ranges that are members of
+ that group. To avoid the inefficiency of iterating over potentially all ranges when looking
+ for a specific index, each time a lookup is done the range and its indexes are cached and the
+ next lookup is done relative to this. This works out to near constant time in most relevant
+ use cases because successive index lookups are most frequently adjacent. The total number of
+ ranges is often quite small, which helps as well. If there is a need for faster random access
+ then a skip list like index may be an appropriate addition.
+
+ \sa VisualDataModel
+*/
+
#ifdef QT_QML_VERIFY_MINIMAL
#define QT_QML_VERIFY_INTEGRITY
+/*
+ Diagnostic to verify there are no consecutive ranges, or that the compositor contains the
+ most compact representation possible.
+
+ Returns false and prints a warning if any range has a starting index equal to the end
+ (index + count) index of the previous range, and both ranges also have the same flags and list
+ property.
+
+ If there are no consecutive ranges this will return true.
+*/
+
static bool qt_verifyMinimal(
const QQuickListCompositor::iterator &begin,
const QQuickListCompositor::iterator &end)
return true;
}
+/*
+ Diagnostic to verify the integrity of a compositor.
+
+ Per range this verifies there are no invalid range combinations, that non-append ranges have
+ positive non-zero counts, and that list ranges have non-negative indexes.
+
+ Accumulatively this verifies that the cached total group counts match the sum of counts
+ of member ranges.
+*/
+
static bool qt_verifyIntegrity(
const QQuickListCompositor::iterator &begin,
const QQuickListCompositor::iterator &end,
QQuickListCompositor::iterator &QQuickListCompositor::iterator::operator +=(int difference)
{
- Q_ASSERT(difference >= 0);
- while (!(range->flags & groupFlag)) {
- incrementIndexes(range->count - offset);
- offset = 0;
- range = range->next;
- }
+ // Update all indexes to the start of the range.
decrementIndexes(offset);
+
+ // If the iterator group isn't a member of the current range ignore the current offset.
+ if (!(range->flags & groupFlag))
+ offset = 0;
+
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;
-}
-QQuickListCompositor::iterator &QQuickListCompositor::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) {
+ // Iterate backwards looking for a range with a positive offset.
+ while (offset <= 0 && range->previous->flags) {
range = range->previous;
if (range->flags & groupFlag)
offset += range->count;
decrementIndexes(range->count);
}
- incrementIndexes(offset);
- return *this;
-}
-QQuickListCompositor::insert_iterator &QQuickListCompositor::insert_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
- || (offset == range->count && !range->append() && offset > 0)
- || (!(range->flags & groupFlag) && offset > 0)) {
- Q_ASSERT(range->flags);
+ // Iterate forwards looking for the first range which contains both the offset and the
+ // iterator group.
+ while (range->flags && (offset >= range->count || !(range->flags & groupFlag))) {
if (range->flags & groupFlag)
offset -= range->count;
incrementIndexes(range->count);
range = range->next;
}
+
+ // Update all the indexes to inclue the remaining offset.
incrementIndexes(offset);
+
return *this;
}
-QQuickListCompositor::insert_iterator &QQuickListCompositor::insert_iterator::operator -=(int difference)
+QQuickListCompositor::insert_iterator &QQuickListCompositor::insert_iterator::operator +=(int difference)
{
- Q_ASSERT(difference >= 0);
- while (!(range->flags & groupFlag) && range->previous->flags) {
- decrementIndexes(offset);
+ iterator::operator +=(difference);
+
+ // If the previous range contains the append flag move the iterator to the tail of the previous
+ // range so that appended appear after the insert position.
+ if (offset == 0 && range->previous->append()) {
range = range->previous;
- offset = (range->flags & (GroupMask | CacheFlag)) ? range->count : 0;
- }
- 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;
- }
+ offset = range->inGroup() ? range->count : 0;
}
return *this;
}
+
+/*!
+ Constructs an empty list compositor.
+*/
+
QQuickListCompositor::QQuickListCompositor()
: m_end(m_ranges.next, 0, Default, 2)
, m_cacheIt(m_end)
, m_groupCount(2)
, m_defaultFlags(PrependFlag | DefaultFlag)
, m_removeFlags(AppendFlag | PrependFlag | GroupMask)
+ , m_moveId(0)
{
}
+/*!
+ Destroys a list compositor.
+*/
+
QQuickListCompositor::~QQuickListCompositor()
{
for (Range *next, *range = m_ranges.next; range != &m_ranges; range = next) {
}
}
+/*!
+ Inserts a range with the given source \a list, start \a index, \a count and \a flags, in front
+ of the existing range \a before.
+*/
+
inline QQuickListCompositor::Range *QQuickListCompositor::insert(
Range *before, void *list, int index, int count, uint flags)
{
return new Range(before, list, index, count, flags);
}
+/*!
+ Erases a \a range from the compositor.
+
+ Returns a pointer to the next range in the compositor.
+*/
+
inline QQuickListCompositor::Range *QQuickListCompositor::erase(
Range *range)
{
return next;
}
+/*!
+ Sets the the number (\a count) of possible groups that items may belong to in a compositor.
+*/
+
void QQuickListCompositor::setGroupCount(int count)
{
m_groupCount = count;
m_cacheIt = m_end;
}
+/*!
+ Returns the number of items that belong to a \a group.
+*/
+
int QQuickListCompositor::count(Group group) const
{
return m_end.index[group];
}
+/*!
+ Returns an iterator representing the item at \a index in a \a group.
+
+ The index must be between 0 and count(group) - 1.
+*/
+
QQuickListCompositor::iterator QQuickListCompositor::find(Group group, int index)
{
QT_QML_TRACE_LISTCOMPOSITOR(<< group << 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;
- }
+ m_cacheIt += offset;
}
Q_ASSERT(m_cacheIt.index[group] == index);
Q_ASSERT(m_cacheIt->inGroup(group));
return m_cacheIt;
}
+/*!
+ Returns an iterator representing the item at \a index in a \a group.
+
+ The index must be between 0 and count(group) - 1.
+*/
+
QQuickListCompositor::iterator QQuickListCompositor::find(Group group, int index) const
{
return const_cast<QQuickListCompositor *>(this)->find(group, index);
}
+/*!
+ Returns an iterator representing an insert position in front of the item at \a index in a
+ \a group.
+
+ The iterator for an insert position can sometimes resolve to a different Range than a regular
+ iterator. This is because when items are inserted on a boundary between Ranges, if the first
+ range has the Append flag set then the items should be inserted into that range to ensure
+ that the append position for the existing range remains after the insert position.
+
+ The index must be between 0 and count(group) - 1.
+*/
+
QQuickListCompositor::insert_iterator QQuickListCompositor::findInsertPosition(Group group, int index)
{
QT_QML_TRACE_LISTCOMPOSITOR(<< group << index)
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;
- }
+ it += offset;
}
Q_ASSERT(it.index[group] == index);
return it;
}
-QQuickListCompositor::iterator QQuickListCompositor::begin(Group group)
-{
- QT_QML_TRACE_LISTCOMPOSITOR(<< group)
- m_cacheIt = iterator(m_ranges.next, 0, group, m_groupCount);
- m_cacheIt += 0;
- return m_cacheIt;
-}
+/*!
+ Appends a range of \a count indexes starting at \a index from a \a list into a compositor
+ with the given \a flags.
+
+ If supplied the \a inserts list will be populated with the positions of the inserted items
+ in each group.
+*/
void QQuickListCompositor::append(
void *list, int index, int count, uint flags, QVector<Insert> *inserts)
insert(m_end, list, index, count, flags, inserts);
}
+/*!
+ Inserts a range of \a count indexes starting at \a index from a \a list with the given \a flags
+ into a \a group at index \a before.
+
+ If supplied the \a inserts list will be populated with the positions of items inserted into
+ each group.
+*/
+
void QQuickListCompositor::insert(
Group group, int before, void *list, int index, int count, uint flags, QVector<Insert> *inserts)
{
insert(findInsertPosition(group, before), list, index, count, flags, inserts);
}
+/*!
+ Inserts a range of \a count indexes starting at \a index from a \a list with the given \a flags
+ into a compositor at position \a before.
+
+ If supplied the \a inserts list will be populated with the positions of items inserted into
+ each group.
+*/
+
QQuickListCompositor::iterator QQuickListCompositor::insert(
iterator before, void *list, int index, int count, uint flags, QVector<Insert> *inserts)
{
inserts->append(Insert(before, count, flags & GroupMask));
}
if (before.offset > 0) {
+ // Inserting into the middle of a range. Split it two and update the iterator so it's
+ // positioned at the start of the second half.
*before = insert(
*before, before->list, before->index, before.offset, before->flags & ~AppendFlag)->next;
before->index += 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)) {
+ // The insert arguments represent a continuation of the previous range so increment
+ // its count instead of inserting a new range.
before->previous->count += count;
before.incrementIndexes(count, flags);
} else {
&& before->list == before->next->list
&& before->flags == before->next->flags
&& (!list || before->end() == before->next->index)) {
+ // The current range and the next are continuous so add their counts and delete one.
before->next->index = before->index;
before->next->count += before->count;
*before = erase(*before);
return before;
}
+/*!
+ Sets the given flags \a flags on \a count items belonging to \a group starting at the position
+ identified by \a fromGroup and the index \a from.
+
+ If supplied the \a inserts list will be populated with insert notifications for affected groups.
+*/
+
void QQuickListCompositor::setFlags(
Group fromGroup, int from, int count, Group group, int flags, QVector<Insert> *inserts)
{
- QT_QML_TRACE_LISTCOMPOSITOR(<< group << index << count << flags)
+ QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << count << group << flags)
setFlags(find(fromGroup, from), count, group, flags, inserts);
}
+/*!
+ Sets the given flags \a flags on \a count items belonging to \a group starting at the position
+ \a from.
+
+ If supplied the \a inserts list will be populated with insert notifications for affected groups.
+*/
+
void QQuickListCompositor::setFlags(
iterator from, int count, Group group, uint flags, QVector<Insert> *inserts)
{
return;
if (from != group) {
+ // Skip to the next full range if the start one is not a member of the target group.
from.incrementIndexes(from->count - from.offset);
from.offset = 0;
*from = from->next;
} else if (from.offset > 0) {
+ // If the start position is mid range split off the portion unaffected.
*from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
from->index += from.offset;
from->count -= from.offset;
for (; count > 0; *from = from->next) {
if (from != from.group) {
+ // Skip ranges that are not members of the target group.
from.incrementIndexes(from->count);
continue;
}
+ // Find the number of items affected in the current range.
const int difference = qMin(count, from->count);
count -= difference;
+ // Determine the actual changes made to the range and increment counts accordingly.
const uint insertFlags = ~from->flags & flags;
const uint setFlags = (from->flags | flags) & ~AppendFlag;
if (insertFlags && inserts)
&& from->previous->list == from->list
&& (!from->list || from->previous->end() == from->index)
&& from->previous->flags == setFlags) {
+ // If the additional flags make the current range a continuation of the previous
+ // then move the affected items over to the previous range.
from->previous->count += difference;
from->index += difference;
from->count -= difference;
if (from->count == 0) {
+ // Delete the current range if it is now empty, preserving the append flag
+ // in the previous range.
if (from->append())
from->previous->flags |= AppendFlag;
*from = erase(*from)->previous;
break;
}
} else if (!insertFlags) {
+ // No new flags, so roll onto the next range.
from.incrementIndexes(from->count - difference);
continue;
} else if (difference < from->count) {
+ // Create a new range with the updated flags, and remove the affected items
+ // from the current range.
*from = insert(*from, from->list, from->index, difference, setFlags)->next;
from->index += difference;
from->count -= difference;
} else {
+ // The whole range is affected so simply update the flags.
from->flags |= flags;
continue;
}
&& from->previous->list == from->list
&& (!from->list || from->previous->end() == from->index)
&& from->previous->flags == (from->flags & ~AppendFlag)) {
+ // If the following range is now a continuation, merge it with its previous range.
from.offset = from->previous->count;
from->previous->count += from->count;
from->previous->flags = from->flags;
QT_QML_VERIFY_LISTCOMPOSITOR
}
+/*!
+ Clears the given flags \a flags on \a count items belonging to \a group starting at the position
+ \a from.
+
+ If supplied the \a removes list will be populated with remove notifications for affected groups.
+*/
+
void QQuickListCompositor::clearFlags(
Group fromGroup, int from, int count, Group group, uint flags, QVector<Remove> *removes)
{
- QT_QML_TRACE_LISTCOMPOSITOR(<< group << index << count << flags)
+ QT_QML_TRACE_LISTCOMPOSITOR(<< fromGroup << from << count << group << flags)
clearFlags(find(fromGroup, from), count, group, flags, removes);
}
+/*!
+ Clears the given flags \a flags on \a count items belonging to \a group starting at the position
+ identified by \a fromGroup and the index \a from.
+
+ If supplied the \a removes list will be populated with remove notifications for affected groups.
+*/
+
void QQuickListCompositor::clearFlags(
iterator from, int count, Group group, uint flags, QVector<Remove> *removes)
{
const bool clearCache = flags & CacheFlag;
if (from != group) {
+ // Skip to the next full range if the start one is not a member of the target group.
from.incrementIndexes(from->count - from.offset);
from.offset = 0;
*from = from->next;
} else if (from.offset > 0) {
+ // If the start position is mid range split off the portion unaffected.
*from = insert(*from, from->list, from->index, from.offset, from->flags & ~AppendFlag)->next;
from->index += from.offset;
from->count -= from.offset;
for (; count > 0; *from = from->next) {
if (from != group) {
+ // Skip ranges that are not members of the target group.
from.incrementIndexes(from->count);
continue;
}
+ // Find the number of items affected in the current range.
const int difference = qMin(count, from->count);
count -= difference;
+
+ // Determine the actual changes made to the range and decrement counts accordingly.
const uint removeFlags = from->flags & flags & ~(AppendFlag | PrependFlag);
const uint clearedFlags = from->flags & ~(flags | AppendFlag | UnresolvedFlag);
if (removeFlags && removes) {
&& from->previous->list == from->list
&& (!from->list || clearedFlags == CacheFlag || from->previous->end() == from->index)
&& from->previous->flags == clearedFlags) {
+ // If the removed flags make the current range a continuation of the previous
+ // then move the affected items over to the previous range.
from->previous->count += difference;
from->index += difference;
from->count -= difference;
if (from->count == 0) {
+ // Delete the current range if it is now empty, preserving the append flag
if (from->append())
from->previous->flags |= AppendFlag;
*from = erase(*from)->previous;
from.incrementIndexes(from->count);
}
} else if (difference < from->count) {
+ // Create a new range with the reduced flags, and remove the affected items from
+ // the current range.
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) {
+ // The whole range is affected so simply update the flags.
from->flags &= ~flags;
} else {
+ // All flags have been removed from the range so remove it.
*from = erase(*from)->previous;
}
}
&& from->previous->list == from->list
&& (!from->list || from->previous->end() == from->index)
&& from->previous->flags == (from->flags & ~AppendFlag)) {
+ // If the following range is now a continuation, merge it with its previous range.
from.offset = from->previous->count;
from->previous->count += from->count;
from->previous->flags = from->flags;
QT_QML_VERIFY_LISTCOMPOSITOR
}
-void QQuickListCompositor::removeList(void *list, QVector<Remove> *removes, bool destroyed)
-{
- QT_QML_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_QML_VERIFY_LISTCOMPOSITOR
-}
-
bool QQuickListCompositor::verifyMoveTo(
Group fromGroup, int from, Group toGroup, int to, int count, Group group) const
{
return to >= 0 && to + count <= m_end.index[toGroup];
}
+/*!
+ \internal
+
+ Moves \a count items belonging to \a moveGroup from the index \a from in \a fromGroup
+ to the index \a to in \a toGroup.
+
+ If \a removes and \a inserts are not null they will be populated with per group notifications
+ of the items moved.
+ */
+
void QQuickListCompositor::move(
Group fromGroup,
int from,
Group toGroup,
int to,
int count,
- Group group,
+ Group moveGroup,
QVector<Remove> *removes,
QVector<Insert> *inserts)
{
QT_QML_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, group));
+ Q_ASSERT(count > 0);
+ Q_ASSERT(from >=0);
+ Q_ASSERT(verifyMoveTo(fromGroup, from, toGroup, to, count, moveGroup));
+ // Find the position of the first item to move.
iterator fromIt = find(fromGroup, from);
- if (fromIt != group) {
+
+ if (fromIt != moveGroup) {
+ // If the range at the from index doesn't contain items from the move group; skip
+ // to the next range.
fromIt.incrementIndexes(fromIt->count - fromIt.offset);
fromIt.offset = 0;
*fromIt = fromIt->next;
} else if (fromIt.offset > 0) {
+ // If the range at the from index contains items from the move group and the index isn't
+ // at the start of the range; split the range at the index and move the iterator to start
+ // of the second range.
*fromIt = insert(
*fromIt, fromIt->list, fromIt->index, fromIt.offset, fromIt->flags & ~AppendFlag)->next;
fromIt->index += fromIt.offset;
fromIt.offset = 0;
}
+ // Remove count items belonging to the move group from the list.
Range movedFlags;
- for (int moveId = 0; count > 0;) {
- if (fromIt != group) {
+ for (int moveId = m_moveId; count > 0;) {
+ if (fromIt != moveGroup) {
+ // Skip ranges not containing items from the move group.
fromIt.incrementIndexes(fromIt->count);
*fromIt = fromIt->next;
continue;
}
int difference = qMin(count, fromIt->count);
+ // Create a new static range containing the moved items from an existing range.
new Range(
&movedFlags,
fromIt->list,
fromIt->index,
difference,
fromIt->flags & ~(PrependFlag | AppendFlag));
+ // Remove moved items from the count, the existing range, and a remove notification.
if (removes)
- removes->append(Remove(fromIt, difference, fromIt->flags, moveId++));
+ removes->append(Remove(fromIt, difference, fromIt->flags, ++moveId));
count -= difference;
fromIt->count -= difference;
+ // If the existing range contains the prepend flag replace the removed items with
+ // a placeholder range for new items inserted into the source model.
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) {
+ // Grow the previous range instead of creating a new one if possible.
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 the existing range has no items remaining; remove it from the list.
if (fromIt->append())
fromIt->previous->flags |= AppendFlag;
*fromIt = erase(*fromIt);
+ // If the ranges before and after the removed range can be joined, do so.
if (*fromIt != m_ranges.next && fromIt->flags == PrependFlag
&& fromIt->previous != &m_ranges
&& fromIt->previous->flags == PrependFlag
}
}
+ // Try and join the range following the removed items to the range preceding it.
if (*fromIt != m_ranges.next
&& *fromIt != &m_ranges
&& fromIt->previous->list == fromIt->list
*fromIt = erase(*fromIt)->previous;
}
+ // Find the destination position of the move.
insert_iterator toIt = fromIt;
toIt.setGroup(toGroup);
+
const int difference = to - toIt.index[toGroup];
- if (difference > 0)
- toIt += difference;
- else
- toIt -= -difference;
+ toIt += difference;
+ // If the insert position is part way through a range; split it and move the iterator to the
+ // start of the second range.
if (toIt.offset > 0) {
*toIt = insert(*toIt, toIt->list, toIt->index, toIt.offset, toIt->flags & ~AppendFlag)->next;
toIt->index += toIt.offset;
toIt.offset = 0;
}
+ // Insert the moved ranges before the insert iterator, growing the previous range if that
+ // is an option.
for (Range *range = movedFlags.previous; range != &movedFlags; range = range->previous) {
if (*toIt != &m_ranges
&& range->list == toIt->list
}
}
+ // Try and join the range after the inserted ranges to the last range inserted.
if (*toIt != m_ranges.next
&& toIt->previous->list == toIt->list
&& (!toIt->list || (toIt->previous->end() == toIt->index && toIt->previous->flags == (toIt->flags & ~AppendFlag)))) {
toIt->previous->flags = toIt->flags;
*toIt = erase(*toIt)->previous;
}
+ // Create insert notification for the ranges moved.
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)
+ if (inserts) {
+ insert.moveId = ++m_moveId;
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_QML_VERIFY_LISTCOMPOSITOR
}
+/*!
+ Clears the contents of a compositor.
+*/
+
void QQuickListCompositor::clear()
{
QT_QML_TRACE_LISTCOMPOSITOR( )
QT_QML_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->flags == CacheFlag) {
+ // Skip ranges that don't reference list.
it.incrementIndexes(it->count);
continue;
} else if (it->flags & MovedFlag) {
+ // Skip ranges that were already moved in listItemsRemoved.
it->flags &= ~MovedFlag;
it.incrementIndexes(it->count);
continue;
if ((offset > 0 && offset < it->count)
|| (offset == 0 && it->prepend())
|| (offset == it->count && it->append())) {
+ // The insert index is within the current range.
if (it->prepend()) {
+ // The range has the prepend flag set so we insert new items into the range.
uint flags = m_defaultFlags;
if (insertion.isMove()) {
+ // If the insert was part of a move replace the default flags with
+ // the flags from the source range.
for (QVector<MovedFlags>::const_iterator move = movedFlags->begin();
move != movedFlags->end();
++move) {
}
}
if (flags & ~(AppendFlag | PrependFlag)) {
+ // If any items are added to groups append an insert notification.
Insert translatedInsert(it, insertion.count, flags, insertion.moveId);
for (int i = 0; i < m_groupCount; ++i) {
if (it->inGroup(i))
translatedInsertions->append(translatedInsert);
}
if ((it->flags & ~AppendFlag) == flags) {
+ // Accumulate items on the current range it its flags are the same as
+ // the insert flags.
it->count += insertion.count;
} else if (offset == 0
&& it->previous != &m_ranges
&& it->previous->list == list
&& it->previous->end() == insertion.index
&& it->previous->flags == flags) {
+ // Attempt to append to the previous range if the insert position is at
+ // the start of the current range.
it->previous->count += insertion.count;
it->index += insertion.count;
it.incrementIndexes(insertion.count);
} else {
if (offset > 0) {
+ // Divide the current range at the insert position.
it.incrementIndexes(offset);
*it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
}
+ // Insert a new range, and increment the start index of the current range.
*it = insert(*it, it->list, insertion.index, insertion.count, flags)->next;
it.incrementIndexes(insertion.count, flags);
it->index += offset + insertion.count;
}
m_end.incrementIndexes(insertion.count, flags);
} else {
+ // The range doesn't have the prepend flag set so split the range into parts;
+ // one before the insert position and one after the last inserted item.
if (offset > 0) {
*it = insert(*it, it->list, it->index, offset, it->flags)->next;
it->index += offset;
it->index += insertion.count;
}
} else if (offset <= 0) {
+ // The insert position was before the current range so increment the start index.
it->index += insertion.count;
}
}
QT_QML_VERIFY_LISTCOMPOSITOR
}
+/*!
+ Updates the contents of a compositor when \a count items are inserted into a \a list at
+ \a index.
+
+ This corrects the indexes of each range for that list in the compositor, splitting the range
+ in two if the insert index is in the middle of that range. If a range at the insert position
+ has the Prepend flag set then a new range will be inserted at that position with the groups
+ specified in defaultGroups(). If the insert index corresponds to the end of a range with
+ the Append flag set a new range will be inserted before the end of the append range.
+
+ The \a translatedInsertions list is populated with insert notifications for affected
+ groups.
+*/
+
void QQuickListCompositor::listItemsInserted(
void *list, int index, int count, QVector<Insert> *translatedInsertions)
{
void *list,
QVector<QQuickChangeSet::Remove> *removals,
QVector<QQuickChangeSet::Insert> *insertions,
- QVector<MovedFlags> *movedFlags, int moveId)
+ QVector<MovedFlags> *movedFlags)
{
QT_QML_TRACE_LISTCOMPOSITOR(<< list << *removals)
for (iterator it(m_ranges.next, 0, Default, m_groupCount); *it != &m_ranges; *it = it->next) {
if (it->list != list || it->flags == CacheFlag) {
+ // Skip ranges that don't reference list.
it.incrementIndexes(it->count);
continue;
}
int relativeIndex = removal->index - it->index;
int itemsRemoved = removal->count;
if (relativeIndex + removal->count > 0 && relativeIndex < it->count) {
+ // If the current range intersects the remove; remove the intersecting items.
const int offset = qMax(0, relativeIndex);
int removeCount = qMin(it->count, relativeIndex + removal->count) - offset;
it->count -= removeCount;
translatedRemoval.index[i] += offset;
}
if (removal->isMove()) {
+ // If the removal was part of a move find the corresponding insert.
QVector<QQuickChangeSet::Insert>::iterator insertion = insertions->begin();
for (; insertion != insertions->end() && insertion->moveId != removal->moveId;
++insertion) {}
Q_ASSERT(insertion->count == removal->count);
if (relativeIndex < 0) {
- int splitMoveId = ++moveId;
+ // If the remove started before the current range, split it and the
+ // corresponding insert so we're only working with intersecting part.
+ int splitMoveId = ++m_moveId;
removal = removals->insert(removal, QQuickChangeSet::Remove(
removal->index, -relativeIndex, splitMoveId));
++removal;
}
if (it->prepend()) {
+ // If the current range has the prepend flag preserve its flags to transfer
+ // to its new location.
removeFlags |= it->flags & CacheFlag;
- translatedRemoval.moveId = ++moveId;
- movedFlags->append(MovedFlags(moveId, it->flags & ~AppendFlag));
+ translatedRemoval.moveId = ++m_moveId;
+ movedFlags->append(MovedFlags(m_moveId, it->flags & ~AppendFlag));
if (removeCount < removal->count) {
+ // If the remove doesn't encompass all of the current range,
+ // split it and the corresponding insert.
removal = removals->insert(removal, QQuickChangeSet::Remove(
removal->index, removeCount, translatedRemoval.moveId));
++removal;
insertion->index += removeCount;
insertion->count -= removeCount;
} else {
+ // If there's no need to split the move simply replace its moveId
+ // with that of the translated move.
removal->moveId = translatedRemoval.moveId;
insertion->moveId = translatedRemoval.moveId;
}
} else {
+ // If the current range doesn't have prepend flags then insert a new range
+ // with list indexes from the corresponding insert location. The MoveFlag
+ // is to notify listItemsInserted that it can skip evaluation of that range.
if (offset > 0) {
*it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
it->index += offset;
} else {
*it = insert(*it, it->list, insertion->index, removeCount, it->flags | MovedFlag)->next;
}
+ // Clear the changed flags as the item hasn't been removed.
translatedRemoval.flags = 0;
removeFlags = 0;
}
} else if (it->inCache()) {
+ // If not moving and the current range has the cache flag, insert a new range
+ // with just the cache flag set to retain caching information for the removed
+ // range.
if (offset > 0) {
*it = insert(*it, it->list, it->index, offset, it->flags & ~AppendFlag)->next;
it->index += offset;
translatedRemovals->append(translatedRemoval);
m_end.decrementIndexes(removeCount, removeFlags);
if (it->count == 0 && !it->append()) {
+ // Erase empty non-append ranges.
*it = erase(*it)->previous;
removed = true;
} else if (relativeIndex <= 0) {
+ // If the remove started before the current range move the start index of
+ // the range to the remove index.
it->index = removal->index;
}
} else if (relativeIndex < 0) {
+ // If the remove was before the current range decrement the start index by the
+ // number of items removed.
it->index -= itemsRemoved;
if (it->previous != &m_ranges
&& it->previous->list == it->list
&& it->previous->end() == it->index
&& it->previous->flags == (it->flags & ~AppendFlag)) {
+ // Compress ranges made continuous by the removal of separating ranges.
it.decrementIndexes(it->previous->count);
it->previous->count += it->count;
it->previous->flags = it->flags;
}
}
if (it->flags == CacheFlag && it->next->flags == CacheFlag && it->next->list == it->list) {
+ // Compress consecutive cache only ranges.
it.index[Cache] += it->next->count;
it->count += it->next->count;
erase(it->next);
QT_QML_VERIFY_LISTCOMPOSITOR
}
+
+/*!
+ Updates the contents of a compositor when \a count items are removed from a \a list at
+ \a index.
+
+ Ranges that intersect the specified range are removed from the compositor and the indexes of
+ ranges after index + count are updated.
+
+ The \a translatedRemovals list is populated with remove notifications for the affected
+ groups.
+*/
+
+
void QQuickListCompositor::listItemsRemoved(
void *list, int index, int count, QVector<Remove> *translatedRemovals)
{
QVector<QQuickChangeSet::Remove> removals;
removals.append(QQuickChangeSet::Remove(index, count));
- listItemsRemoved(translatedRemovals, list, &removals, 0, 0, 0);
+ listItemsRemoved(translatedRemovals, list, &removals, 0, 0);
}
+/*!
+ Updates the contents of a compositor when \a count items are removed from a \a list at
+ \a index.
+
+ Ranges that intersect the specified range are removed from the compositor and the indexes of
+ ranges after index + count are updated.
+
+ The \a translatedRemovals and translatedInserts lists are populated with move
+ notifications for the affected groups.
+*/
+
void QQuickListCompositor::listItemsMoved(
void *list,
int from,
removals.append(QQuickChangeSet::Remove(from, count, 0));
insertions.append(QQuickChangeSet::Insert(to, count, 0));
- listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags, 0);
+ listItemsRemoved(translatedRemovals, list, &removals, &insertions, &movedFlags);
listItemsInserted(translatedInsertions, list, insertions, &movedFlags);
}
}
}
+
+/*!
+ Translates the positions of \a count changed items at \a index in a \a list.
+
+ The \a translatedChanges list is populated with change notifications for the
+ affected groups.
+*/
+
void QQuickListCompositor::listItemsChanged(
void *list, int index, int count, QVector<Change> *translatedChanges)
{
listItemsChanged(translatedChanges, list, changes);
}
-void QQuickListCompositor::listChanged(
- void *list,
- const QQuickChangeSet &changeSet,
- QVector<Remove> *translatedRemovals,
- QVector<Insert> *translatedInsertions,
- QVector<Change> *translatedChanges)
-{
- QVector<QQuickChangeSet::Remove> removals = changeSet.removes();
- QVector<QQuickChangeSet::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 QQuickListCompositor::transition(
Group from,
Group to,
}
}
+/*!
+ \internal
+ Writes the name of \a group to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor::Group &group)
{
switch (group) {
}
+/*!
+ \internal
+ Writes the contents of \a range to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor::Range &range)
{
(debug.nospace()
<< "Range("
- << range.list) << " "
- << range.index << " "
- << range.count << " "
- << (range.isUnresolved() ? "U" : "0")
- << (range.append() ? "A" : "0")
- << (range.prepend() ? "P" : "0");
+ << range.list) << ' '
+ << range.index << ' '
+ << range.count << ' '
+ << (range.isUnresolved() ? 'U' : '0')
+ << (range.append() ? 'A' : '0')
+ << (range.prepend() ? 'P' : '0');
for (int i = QQuickListCompositor::MaximumGroupCount - 1; i >= 2; --i)
- debug << (range.inGroup(i) ? "1" : "0");
+ debug << (range.inGroup(i) ? '1' : '0');
return (debug
- << (range.inGroup(QQuickListCompositor::Default) ? "D" : "0")
- << (range.inGroup(QQuickListCompositor::Cache) ? "C" : "0"));
+ << (range.inGroup(QQuickListCompositor::Default) ? 'D' : '0')
+ << (range.inGroup(QQuickListCompositor::Cache) ? 'C' : '0'));
}
static void qt_print_indexes(QDebug &debug, int count, const int *indexes)
debug << indexes[i];
}
+/*!
+ \internal
+ Writes the contents of \a it to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor::iterator &it)
{
(debug.nospace() << "iterator(" << it.group).space() << "offset:" << it.offset;
qt_print_indexes(debug, it.groupCount, it.index);
- return ((debug << **it).nospace() << ")").space();
+ return ((debug << **it).nospace() << ')').space();
}
static QDebug qt_print_change(QDebug debug, const char *name, const QQuickListCompositor::Change &change)
{
- debug.nospace() << name << "(" << change.moveId << " " << change.count << " ";
+ debug.nospace() << name << '(' << change.moveId << ' ' << change.count << ' ';
for (int i = QQuickListCompositor::MaximumGroupCount - 1; i >= 2; --i)
- debug << (change.inGroup(i) ? "1" : "0");
- debug << (change.inGroup(QQuickListCompositor::Default) ? "D" : "0")
- << (change.inGroup(QQuickListCompositor::Cache) ? "C" : "0");
+ debug << (change.inGroup(i) ? '1' : '0');
+ debug << (change.inGroup(QQuickListCompositor::Default) ? 'D' : '0')
+ << (change.inGroup(QQuickListCompositor::Cache) ? 'C' : '0');
int i = QQuickListCompositor::MaximumGroupCount - 1;
for (; i >= 0 && !change.inGroup(i); --i) {}
for (; i >= 0; --i)
- debug << " " << change.index[i];
- return (debug << ")").maybeSpace();
+ debug << ' ' << change.index[i];
+ return (debug << ')').maybeSpace();
}
+/*!
+ \internal
+ Writes the contents of \a change to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor::Change &change)
{
return qt_print_change(debug, "Change", change);
}
+/*!
+ \internal
+ Writes the contents of \a remove to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor::Remove &remove)
{
return qt_print_change(debug, "Remove", remove);
}
+/*!
+ \internal
+ Writes the contents of \a insert to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor::Insert &insert)
{
return qt_print_change(debug, "Insert", insert);
}
+/*!
+ \internal
+ Writes the contents of \a list to \a debug.
+*/
+
QDebug operator <<(QDebug debug, const QQuickListCompositor &list)
{
int indexes[QQuickListCompositor::MaximumGroupCount];
debug.nospace() << "QQuickListCompositor(";
qt_print_indexes(debug, list.m_groupCount, list.m_end.index);
for (QQuickListCompositor::Range *range = list.m_ranges.next; range != &list.m_ranges; range = range->next) {
- (debug << "\n").space();
+ (debug << '\n').space();
qt_print_indexes(debug, list.m_groupCount, indexes);
- debug << " " << *range;
+ debug << ' ' << *range;
for (int i = 0; i < list.m_groupCount; ++i) {
if (range->inGroup(i))
indexes[i] += range->count;
}
}
- return (debug << ")").maybeSpace();
+ return (debug << ')').maybeSpace();
}
QT_END_NAMESPACE