qqmlchangeset.cpp

Go to the documentation of this file.

// Copyright (C) 2016 The Qt Company Ltd.
// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
 
#include "qqmlchangeset_p.h"
 
QT_BEGIN_NAMESPACE
 
 
QQmlChangeSet::QQmlChangeSet()
    : m_difference(0)
{
}
 
QQmlChangeSet::QQmlChangeSet(const QQmlChangeSet &changeSet)
    : m_removes(changeSet.m_removes)
    , m_inserts(changeSet.m_inserts)
    , m_changes(changeSet.m_changes)
    , m_difference(changeSet.m_difference)
{
}
 
QQmlChangeSet::~QQmlChangeSet()
{
}
 
QQmlChangeSet &QQmlChangeSet::operator =(const QQmlChangeSet &changeSet)
{
    m_removes = changeSet.m_removes;
    m_inserts = changeSet.m_inserts;
    m_changes = changeSet.m_changes;
    m_difference = changeSet.m_difference;
    return *this;
}
 
void QQmlChangeSet::insert(int index, int count)
{
    insert(QVector<Change>() << Change(index, count));
}
 
void QQmlChangeSet::remove(int index, int count)
{
    QVector<Change> removes;
    removes.append(Change(index, count));
    remove(&removes, nullptr);
}
 
void QQmlChangeSet::move(int from, int to, int count, int moveId)
{
    QVector<Change> removes;
    removes.append(Change(from, count, moveId));
    QVector<Change> inserts;
    inserts.append(Change(to, count, moveId));
    remove(&removes, &inserts);
    insert(inserts);
}
 
void QQmlChangeSet::change(int index, int count)
{
    QVector<Change> changes;
    changes.append(Change(index, count));
    change(changes);
}
 
void QQmlChangeSet::apply(const QQmlChangeSet &changeSet)
{
    QVector<Change> r = changeSet.m_removes;
    QVector<Change> i = changeSet.m_inserts;
    QVector<Change> c = changeSet.m_changes;
    remove(&r, &i);
    insert(i);
    change(c);
}
 
void QQmlChangeSet::remove(const QVector<Change> &removes, QVector<Change> *inserts)
{
    QVector<Change> r = removes;
    remove(&r, inserts);
}
 
void QQmlChangeSet::remove(QVector<Change> *removes, QVector<Change> *inserts)
{
    int removeCount = 0;
    int insertCount = 0;
    QVector<Change>::iterator insert = m_inserts.begin();
    QVector<Change>::iterator change = m_changes.begin();
    QVector<Change>::iterator rit = removes->begin();
    for (; rit != removes->end(); ++rit) {
        int index = rit->index + removeCount;
        int count = rit->count;
 
        // Decrement the accumulated remove count from the indexes of any changes prior to the
        // current remove.
        for (; change != m_changes.end() && change->end() < rit->index; ++change)
            change->index -= removeCount;
        // Remove any portion of a change notification that intersects the current remove.
        for (; change != m_changes.end() && change->index > rit->end(); ++change) {
            change->count -= qMin(change->end(), rit->end()) - qMax(change->index, rit->index);
            if (change->count == 0) {
                change = m_changes.erase(change);
            } else if (rit->index < change->index) {
                change->index = rit->index;
            }
        }
 
        // Decrement the accumulated remove count from the indexes of any inserts prior to the
        // current remove.
        for (; insert != m_inserts.end() && insert->end() <= index; ++insert) {
            insertCount += insert->count;
            insert->index -= removeCount;
        }
 
        rit->index -= insertCount;
 
        // Remove any portion of a insert notification that intersects the current remove.
        while (insert != m_inserts.end() && insert->index < index + count) {
            int offset =  index - insert->index;
            const int difference = qMin(insert->end(), index + count) - qMax(insert->index, index);
 
            // If part of the remove or insert that precedes the intersection has a moveId create
            // a new delta for that portion and subtract the size of that delta from the current
            // one.
            if (offset < 0 && rit->moveId != -1) {
                rit = removes->insert(rit, Change(
                        rit->index, -offset, rit->moveId, rit->offset));
                ++rit;
                rit->count -= -offset;
                rit->offset += -offset;
                index += -offset;
                count -= -offset;
                removeCount += -offset;
                offset = 0;
            } else if (offset > 0 && insert->moveId != -1) {
                insert = m_inserts.insert(insert, Change(
                        insert->index - removeCount, offset, insert->moveId, insert->offset));
                ++insert;
                insert->index += offset;
                insert->count -= offset;
                insert->offset += offset;
                rit->index -= offset;
                insertCount += offset;
            }
 
            // If the current remove has a move id, find any inserts with the same move id and
            // replace the corresponding sections with the insert removed from the change set.
            if (rit->moveId != -1 && difference > 0 && inserts) {
                for (QVector<Change>::iterator iit = inserts->begin(); iit != inserts->end(); ++iit) {
                    if (iit->moveId != rit->moveId
                            || rit->offset > iit->offset + iit->count
                            || iit->offset > rit->offset + difference) {
                        continue;
                    }
                    // If the intersecting insert starts before the replacement one create
                    // a new insert for the portion prior to the replacement insert.
                    const int overlapOffset = rit->offset - iit->offset;
                    if (overlapOffset > 0) {
                        iit = inserts->insert(iit, Change(
                                iit->index, overlapOffset, iit->moveId, iit->offset));
                        ++iit;
                        iit->index += overlapOffset;
                        iit->count -= overlapOffset;
                        iit->offset += overlapOffset;
                    }
                    if (iit->offset >= rit->offset
                            && iit->offset + iit->count <= rit->offset + difference) {
                        // If the replacement insert completely encapsulates the existing
                        // one just change the moveId.
                        iit->moveId = insert->moveId;
                        iit->offset = insert->offset + qMax(0, -overlapOffset);
                    } else {
                        // Create a new insertion before the intersecting one with the number of intersecting
                        // items and remove that number from that insert.
                        const int count
                                = qMin(iit->offset + iit->count, rit->offset + difference)
                                - qMax(iit->offset, rit->offset);
                        iit = inserts->insert(iit, Change(
                                iit->index,
                                count,
                                insert->moveId,
                                insert->offset + qMax(0, -overlapOffset)));
                        ++iit;
                        iit->index += count;
                        iit->count -= count;
                        iit->offset += count;
                    }
                }
            }
 
            // Subtract the number of intersecting items from the current remove and insert.
            insert->count -= difference;
            insert->offset += difference;
            rit->count -= difference;
            rit->offset += difference;
 
            index += difference;
            count -= difference;
            removeCount += difference;
 
            if (insert->count == 0) {
                insert = m_inserts.erase(insert);
            } else if (rit->count == -offset || rit->count == 0) {
                insert->index += difference;
                break;
            } else {
                insert->index -= removeCount - difference;
                rit->index -= insert->count;
                insertCount += insert->count;
                ++insert;
            }
        }
        removeCount += rit->count;
    }
    for (; insert != m_inserts.end(); ++insert)
        insert->index -= removeCount;
 
    removeCount = 0;
    QVector<Change>::iterator remove = m_removes.begin();
    for (rit = removes->begin(); rit != removes->end(); ++rit) {
        if (rit->count == 0)
            continue;
        // Accumulate consecutive removes into a single delta before attempting to apply.
        for (QVector<Change>::iterator next = rit + 1; next != removes->end()
                && next->index == rit->index
                && next->moveId == -1
                && rit->moveId == -1; ++next) {
            next->count += rit->count;
            rit = next;
        }
        int index = rit->index + removeCount;
        // Decrement the accumulated remove count from the indexes of any inserts prior to the
        // current remove.
        for (; remove != m_removes.end() && index > remove->index; ++remove)
            remove->index -= removeCount;
        while (remove != m_removes.end() && index + rit->count >= remove->index) {
            int count = 0;
            const int offset = remove->index - index;
            QVector<Change>::iterator rend = remove;
            for (; rend != m_removes.end()
                    && rit->moveId == -1
                    && rend->moveId == -1
                    && index + rit->count >= rend->index; ++rend) {
                count += rend->count;
            }
            if (remove != rend) {
                // Accumulate all existing non-move removes that are encapsulated by or immediately
                // follow the current remove into it.
                int difference = 0;
                if (rend == m_removes.end()) {
                    difference = rit->count;
                } else if (rit->index + rit->count < rend->index - removeCount) {
                    difference = rit->count;
                } else if (rend->moveId != -1) {
                    difference = rend->index - removeCount - rit->index;
                    index += difference;
                }
                count += difference;
 
                rit->count -= difference;
                removeCount += difference;
                remove->index = rit->index;
                remove->count = count;
                remove = m_removes.erase(++remove, rend);
            } else {
                // Insert a remove for the portion of the unmergable current remove prior to the
                // point of intersection.
                if (offset > 0) {
                    remove = m_removes.insert(remove, Change(
                            rit->index, offset, rit->moveId, rit->offset));
                    ++remove;
                    rit->count -= offset;
                    rit->offset += offset;
                    removeCount += offset;
                    index += offset;
                }
                remove->index = rit->index;
 
                ++remove;
            }
        }
 
        if (rit->count > 0) {
            remove = m_removes.insert(remove, *rit);
            ++remove;
        }
        removeCount += rit->count;
    }
    for (; remove != m_removes.end(); ++remove)
        remove->index -= removeCount;
    m_difference -= removeCount;
}
 
void QQmlChangeSet::insert(const QVector<Change> &inserts)
{
    int insertCount = 0;
    QVector<Change>::iterator insert = m_inserts.begin();
    QVector<Change>::iterator change = m_changes.begin();
    for (QVector<Change>::const_iterator iit = inserts.begin(); iit != inserts.end(); ++iit) {
        if (iit->count == 0)
            continue;
        int index = iit->index - insertCount;
 
        Change current = *iit;
        // Accumulate consecutive inserts into a single delta before attempting to insert.
        for (QVector<Change>::const_iterator next = iit + 1; next != inserts.end()
                && next->index == iit->index + iit->count
                && next->moveId == -1
                && iit->moveId == -1; ++next) {
            current.count += next->count;
            iit = next;
        }
 
        // Increment the index of any changes before the current insert by the accumlated insert
        // count.
        for (; change != m_changes.end() && change->index >= index; ++change)
            change->index += insertCount;
        // If the current insert index is in the middle of a change split it in two at that
        // point and increment the index of the latter half.
        if (change != m_changes.end() && change->index < index + iit->count) {
                int offset = index - change->index;
                change = m_changes.insert(change, Change(change->index + insertCount, offset));
                ++change;
                change->index += iit->count + offset;
                change->count -= offset;
        }
 
        // Increment the index of any inserts before the current insert by the accumlated insert
        // count.
        for (; insert != m_inserts.end() && index > insert->index + insert->count; ++insert)
            insert->index += insertCount;
        if (insert == m_inserts.end()) {
            insert = m_inserts.insert(insert, current);
            ++insert;
        } else {
            const int offset = index - insert->index;
 
            if (offset < 0) {
                // If the current insert is before an existing insert and not adjacent just insert
                // it into the list.
                insert = m_inserts.insert(insert, current);
                ++insert;
            } else if (iit->moveId == -1 && insert->moveId == -1) {
                // If neither the current nor existing insert has a moveId add the current insert
                // to the existing one.
                if (offset < insert->count) {
                    insert->index -= current.count;
                    insert->count += current.count;
                } else {
                    insert->index += insertCount;
                    insert->count += current.count;
                    ++insert;
                }
            } else if (offset < insert->count) {
                // If either insert has a moveId then split the existing insert and insert the
                // current one in the middle.
                if (offset > 0) {
                    insert = m_inserts.insert(insert, Change(
                            insert->index + insertCount, offset, insert->moveId, insert->offset));
                    ++insert;
                    insert->index += offset;
                    insert->count -= offset;
                    insert->offset += offset;
                }
                insert = m_inserts.insert(insert, current);
                ++insert;
            } else {
                insert->index += insertCount;
                ++insert;
                insert = m_inserts.insert(insert, current);
                ++insert;
            }
        }
        insertCount += current.count;
    }
    for (; insert != m_inserts.end(); ++insert)
        insert->index += insertCount;
    m_difference += insertCount;
}
 
void QQmlChangeSet::move(const QVector<Change> &removes, const QVector<Change> &inserts)
{
    QVector<Change> r = removes;
    QVector<Change> i = inserts;
    remove(&r, &i);
    insert(i);
}
 
void QQmlChangeSet::change(const QVector<Change> &changes)
{
    QVector<Change> c = changes;
    change(&c);
}
 
void QQmlChangeSet::change(QVector<Change> *changes)
{
    QVector<Change>::iterator insert = m_inserts.begin();
    QVector<Change>::iterator change = m_changes.begin();
    for (QVector<Change>::iterator cit = changes->begin(); cit != changes->end(); ++cit) {
        for (; insert != m_inserts.end() && insert->end() < cit->index; ++insert) {}
        for (; insert != m_inserts.end() && insert->index < cit->end(); ++insert) {
            const int offset = insert->index - cit->index;
            const int count = cit->count + cit->index - insert->index - insert->count;
            if (offset == 0) {
                cit->index = insert->index + insert->count;
                cit->count = count;
            } else {
                cit = changes->insert(++cit, Change(insert->index + insert->count, count));
                --cit;
                cit->count = offset;
            }
        }
 
        for (; change != m_changes.end() && change->index + change->count < cit->index; ++change) {}
        if (change == m_changes.end() || change->index > cit->index + cit->count) {
            if (cit->count > 0) {
                change = m_changes.insert(change, *cit);
                ++change;
            }
        } else {
            if (cit->index < change->index) {
                change->count += change->index - cit->index;
                change->index = cit->index;
            }
 
            if (cit->index + cit->count > change->index + change->count) {
                change->count = cit->index + cit->count - change->index;
                QVector<Change>::iterator cbegin = change;
                QVector<Change>::iterator cend = ++cbegin;
                for (; cend != m_changes.end() && cend->index <= change->index + change->count; ++cend) {
                    if (cend->index + cend->count > change->index + change->count)
                        change->count = cend->index + cend->count - change->index;
                }
                if (cbegin != cend) {
                    change = m_changes.erase(cbegin, cend);
                    --change;
                }
            }
        }
    }
}
 
QDebug operator <<(QDebug debug, const QQmlChangeSet &set)
{
    QDebugStateSaver stateSaver(debug);
    debug.nospace() << "QQmlChangeSet(";
    const QVector<QQmlChangeSet::Change> &removes = set.removes();
    for (const QQmlChangeSet::Change &remove : removes)
        debug << remove << ' ';
    const QVector<QQmlChangeSet::Change> &inserts = set.inserts();
    for (const QQmlChangeSet::Change &insert : inserts)
        debug << insert << ' ';
    const QVector<QQmlChangeSet::Change> &changes = set.changes();
    for (const QQmlChangeSet::Change &change : changes)
        debug << change << ' ';
    return debug.nospace() << ')';
}
 
QDebug operator <<(QDebug debug, const QQmlChangeSet::Change &change)
{
    QDebugStateSaver stateSaver(debug);
    return debug.nospace() << "Change(" << change.index << ',' << change.count << ')';
}
 
QT_END_NAMESPACE