1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtQml module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qqmlchangeset_p.h"
41
42QT_BEGIN_NAMESPACE
43
44
45/*!
46 \class QQmlChangeSet
47 \brief The QQmlChangeSet class stores an ordered list of notifications about
48 changes to a linear data set.
49 \internal
50
51 QQmlChangeSet can be used to record a series of notifications about items in an indexed list
52 being inserted, removed, moved, and changed. Notifications in the set are re-ordered so that
53 all notifications of a single type are grouped together and sorted in order of ascending index,
54 with remove notifications preceding all others, followed by insert notification, and then
55 change notifications.
56
57 Moves in a change set are represented by a remove notification paired with an insert
58 notification by way of a shared unique moveId. Re-ordering may result in one or both of the
59 paired notifications being divided, when this happens the offset member of the notification
60 will indicate the relative offset of the divided notification from the beginning of the
61 original.
62*/
63
64/*!
65 Constructs an empty change set.
66*/
67
68QQmlChangeSet::QQmlChangeSet()
69 : m_difference(0)
70{
71}
72
73/*!
74 Constructs a copy of a \a changeSet.
75*/
76
77QQmlChangeSet::QQmlChangeSet(const QQmlChangeSet &changeSet)
78 : m_removes(changeSet.m_removes)
79 , m_inserts(changeSet.m_inserts)
80 , m_changes(changeSet.m_changes)
81 , m_difference(changeSet.m_difference)
82{
83}
84
85/*!
86 Destroys a change set.
87*/
88
89QQmlChangeSet::~QQmlChangeSet()
90{
91}
92
93/*!
94 Assigns the value of a \a changeSet to another.
95*/
96
97QQmlChangeSet &QQmlChangeSet::operator =(const QQmlChangeSet &changeSet)
98{
99 m_removes = changeSet.m_removes;
100 m_inserts = changeSet.m_inserts;
101 m_changes = changeSet.m_changes;
102 m_difference = changeSet.m_difference;
103 return *this;
104}
105
106/*!
107 Appends a notification that \a count items were inserted at \a index.
108*/
109
110void QQmlChangeSet::insert(int index, int count)
111{
112 insert(inserts: QVector<Change>() << Change(index, count));
113}
114
115/*!
116 Appends a notification that \a count items were removed at \a index.
117*/
118
119void QQmlChangeSet::remove(int index, int count)
120{
121 QVector<Change> removes;
122 removes.append(t: Change(index, count));
123 remove(removes: &removes, inserts: nullptr);
124}
125
126/*!
127 Appends a notification that \a count items were moved \a from one index \a to another.
128
129 The \a moveId must be unique across the lifetime of the change set and any related
130 change sets.
131*/
132
133void QQmlChangeSet::move(int from, int to, int count, int moveId)
134{
135 QVector<Change> removes;
136 removes.append(t: Change(from, count, moveId));
137 QVector<Change> inserts;
138 inserts.append(t: Change(to, count, moveId));
139 remove(removes: &removes, inserts: &inserts);
140 insert(inserts);
141}
142
143/*!
144 Appends a notification that \a count items were changed at \a index.
145*/
146
147void QQmlChangeSet::change(int index, int count)
148{
149 QVector<Change> changes;
150 changes.append(t: Change(index, count));
151 change(changes);
152}
153
154/*!
155 Applies the changes in a \a changeSet to another.
156*/
157
158void QQmlChangeSet::apply(const QQmlChangeSet &changeSet)
159{
160 QVector<Change> r = changeSet.m_removes;
161 QVector<Change> i = changeSet.m_inserts;
162 QVector<Change> c = changeSet.m_changes;
163 remove(removes: &r, inserts: &i);
164 insert(inserts: i);
165 change(changes: c);
166}
167
168/*!
169 Applies a list of \a removes to a change set.
170
171 If a remove contains a moveId then any intersecting insert in the set will replace the
172 corresponding intersection in the optional \a inserts list.
173*/
174
175void QQmlChangeSet::remove(const QVector<Change> &removes, QVector<Change> *inserts)
176{
177 QVector<Change> r = removes;
178 remove(removes: &r, inserts);
179}
180
181void QQmlChangeSet::remove(QVector<Change> *removes, QVector<Change> *inserts)
182{
183 int removeCount = 0;
184 int insertCount = 0;
185 QVector<Change>::iterator insert = m_inserts.begin();
186 QVector<Change>::iterator change = m_changes.begin();
187 QVector<Change>::iterator rit = removes->begin();
188 for (; rit != removes->end(); ++rit) {
189 int index = rit->index + removeCount;
190 int count = rit->count;
191
192 // Decrement the accumulated remove count from the indexes of any changes prior to the
193 // current remove.
194 for (; change != m_changes.end() && change->end() < rit->index; ++change)
195 change->index -= removeCount;
196 // Remove any portion of a change notification that intersects the current remove.
197 for (; change != m_changes.end() && change->index > rit->end(); ++change) {
198 change->count -= qMin(a: change->end(), b: rit->end()) - qMax(a: change->index, b: rit->index);
199 if (change->count == 0) {
200 change = m_changes.erase(pos: change);
201 } else if (rit->index < change->index) {
202 change->index = rit->index;
203 }
204 }
205
206 // Decrement the accumulated remove count from the indexes of any inserts prior to the
207 // current remove.
208 for (; insert != m_inserts.end() && insert->end() <= index; ++insert) {
209 insertCount += insert->count;
210 insert->index -= removeCount;
211 }
212
213 rit->index -= insertCount;
214
215 // Remove any portion of a insert notification that intersects the current remove.
216 while (insert != m_inserts.end() && insert->index < index + count) {
217 int offset = index - insert->index;
218 const int difference = qMin(a: insert->end(), b: index + count) - qMax(a: insert->index, b: index);
219
220 // If part of the remove or insert that precedes the intersection has a moveId create
221 // a new delta for that portion and subtract the size of that delta from the current
222 // one.
223 if (offset < 0 && rit->moveId != -1) {
224 rit = removes->insert(before: rit, t: Change(
225 rit->index, -offset, rit->moveId, rit->offset));
226 ++rit;
227 rit->count -= -offset;
228 rit->offset += -offset;
229 index += -offset;
230 count -= -offset;
231 removeCount += -offset;
232 offset = 0;
233 } else if (offset > 0 && insert->moveId != -1) {
234 insert = m_inserts.insert(before: insert, t: Change(
235 insert->index - removeCount, offset, insert->moveId, insert->offset));
236 ++insert;
237 insert->index += offset;
238 insert->count -= offset;
239 insert->offset += offset;
240 rit->index -= offset;
241 insertCount += offset;
242 }
243
244 // If the current remove has a move id, find any inserts with the same move id and
245 // replace the corresponding sections with the insert removed from the change set.
246 if (rit->moveId != -1 && difference > 0 && inserts) {
247 for (QVector<Change>::iterator iit = inserts->begin(); iit != inserts->end(); ++iit) {
248 if (iit->moveId != rit->moveId
249 || rit->offset > iit->offset + iit->count
250 || iit->offset > rit->offset + difference) {
251 continue;
252 }
253 // If the intersecting insert starts before the replacement one create
254 // a new insert for the portion prior to the replacement insert.
255 const int overlapOffset = rit->offset - iit->offset;
256 if (overlapOffset > 0) {
257 iit = inserts->insert(before: iit, t: Change(
258 iit->index, overlapOffset, iit->moveId, iit->offset));
259 ++iit;
260 iit->index += overlapOffset;
261 iit->count -= overlapOffset;
262 iit->offset += overlapOffset;
263 }
264 if (iit->offset >= rit->offset
265 && iit->offset + iit->count <= rit->offset + difference) {
266 // If the replacement insert completely encapsulates the existing
267 // one just change the moveId.
268 iit->moveId = insert->moveId;
269 iit->offset = insert->offset + qMax(a: 0, b: -overlapOffset);
270 } else {
271 // Create a new insertion before the intersecting one with the number of intersecting
272 // items and remove that number from that insert.
273 const int count
274 = qMin(a: iit->offset + iit->count, b: rit->offset + difference)
275 - qMax(a: iit->offset, b: rit->offset);
276 iit = inserts->insert(before: iit, t: Change(
277 iit->index,
278 count,
279 insert->moveId,
280 insert->offset + qMax(a: 0, b: -overlapOffset)));
281 ++iit;
282 iit->index += count;
283 iit->count -= count;
284 iit->offset += count;
285 }
286 }
287 }
288
289 // Subtract the number of intersecting items from the current remove and insert.
290 insert->count -= difference;
291 insert->offset += difference;
292 rit->count -= difference;
293 rit->offset += difference;
294
295 index += difference;
296 count -= difference;
297 removeCount += difference;
298
299 if (insert->count == 0) {
300 insert = m_inserts.erase(pos: insert);
301 } else if (rit->count == -offset || rit->count == 0) {
302 insert->index += difference;
303 break;
304 } else {
305 insert->index -= removeCount - difference;
306 rit->index -= insert->count;
307 insertCount += insert->count;
308 ++insert;
309 }
310 }
311 removeCount += rit->count;
312 }
313 for (; insert != m_inserts.end(); ++insert)
314 insert->index -= removeCount;
315
316 removeCount = 0;
317 QVector<Change>::iterator remove = m_removes.begin();
318 for (rit = removes->begin(); rit != removes->end(); ++rit) {
319 if (rit->count == 0)
320 continue;
321 // Accumulate consecutive removes into a single delta before attempting to apply.
322 for (QVector<Change>::iterator next = rit + 1; next != removes->end()
323 && next->index == rit->index
324 && next->moveId == -1
325 && rit->moveId == -1; ++next) {
326 next->count += rit->count;
327 rit = next;
328 }
329 int index = rit->index + removeCount;
330 // Decrement the accumulated remove count from the indexes of any inserts prior to the
331 // current remove.
332 for (; remove != m_removes.end() && index > remove->index; ++remove)
333 remove->index -= removeCount;
334 while (remove != m_removes.end() && index + rit->count >= remove->index) {
335 int count = 0;
336 const int offset = remove->index - index;
337 QVector<Change>::iterator rend = remove;
338 for (; rend != m_removes.end()
339 && rit->moveId == -1
340 && rend->moveId == -1
341 && index + rit->count >= rend->index; ++rend) {
342 count += rend->count;
343 }
344 if (remove != rend) {
345 // Accumulate all existing non-move removes that are encapsulated by or immediately
346 // follow the current remove into it.
347 int difference = 0;
348 if (rend == m_removes.end()) {
349 difference = rit->count;
350 } else if (rit->index + rit->count < rend->index - removeCount) {
351 difference = rit->count;
352 } else if (rend->moveId != -1) {
353 difference = rend->index - removeCount - rit->index;
354 index += difference;
355 }
356 count += difference;
357
358 rit->count -= difference;
359 removeCount += difference;
360 remove->index = rit->index;
361 remove->count = count;
362 remove = m_removes.erase(abegin: ++remove, aend: rend);
363 } else {
364 // Insert a remove for the portion of the unmergable current remove prior to the
365 // point of intersection.
366 if (offset > 0) {
367 remove = m_removes.insert(before: remove, t: Change(
368 rit->index, offset, rit->moveId, rit->offset));
369 ++remove;
370 rit->count -= offset;
371 rit->offset += offset;
372 removeCount += offset;
373 index += offset;
374 }
375 remove->index = rit->index;
376
377 ++remove;
378 }
379 }
380
381 if (rit->count > 0) {
382 remove = m_removes.insert(before: remove, x: *rit);
383 ++remove;
384 }
385 removeCount += rit->count;
386 }
387 for (; remove != m_removes.end(); ++remove)
388 remove->index -= removeCount;
389 m_difference -= removeCount;
390}
391
392/*!
393 Applies a list of \a inserts to a change set.
394*/
395
396void QQmlChangeSet::insert(const QVector<Change> &inserts)
397{
398 int insertCount = 0;
399 QVector<Change>::iterator insert = m_inserts.begin();
400 QVector<Change>::iterator change = m_changes.begin();
401 for (QVector<Change>::const_iterator iit = inserts.begin(); iit != inserts.end(); ++iit) {
402 if (iit->count == 0)
403 continue;
404 int index = iit->index - insertCount;
405
406 Change current = *iit;
407 // Accumulate consecutive inserts into a single delta before attempting to insert.
408 for (QVector<Change>::const_iterator next = iit + 1; next != inserts.end()
409 && next->index == iit->index + iit->count
410 && next->moveId == -1
411 && iit->moveId == -1; ++next) {
412 current.count += next->count;
413 iit = next;
414 }
415
416 // Increment the index of any changes before the current insert by the accumlated insert
417 // count.
418 for (; change != m_changes.end() && change->index >= index; ++change)
419 change->index += insertCount;
420 // If the current insert index is in the middle of a change split it in two at that
421 // point and increment the index of the latter half.
422 if (change != m_changes.end() && change->index < index + iit->count) {
423 int offset = index - change->index;
424 change = m_changes.insert(before: change, t: Change(change->index + insertCount, offset));
425 ++change;
426 change->index += iit->count + offset;
427 change->count -= offset;
428 }
429
430 // Increment the index of any inserts before the current insert by the accumlated insert
431 // count.
432 for (; insert != m_inserts.end() && index > insert->index + insert->count; ++insert)
433 insert->index += insertCount;
434 if (insert == m_inserts.end()) {
435 insert = m_inserts.insert(before: insert, x: current);
436 ++insert;
437 } else {
438 const int offset = index - insert->index;
439
440 if (offset < 0) {
441 // If the current insert is before an existing insert and not adjacent just insert
442 // it into the list.
443 insert = m_inserts.insert(before: insert, x: current);
444 ++insert;
445 } else if (iit->moveId == -1 && insert->moveId == -1) {
446 // If neither the current nor existing insert has a moveId add the current insert
447 // to the existing one.
448 if (offset < insert->count) {
449 insert->index -= current.count;
450 insert->count += current.count;
451 } else {
452 insert->index += insertCount;
453 insert->count += current.count;
454 ++insert;
455 }
456 } else if (offset < insert->count) {
457 // If either insert has a moveId then split the existing insert and insert the
458 // current one in the middle.
459 if (offset > 0) {
460 insert = m_inserts.insert(before: insert, t: Change(
461 insert->index + insertCount, offset, insert->moveId, insert->offset));
462 ++insert;
463 insert->index += offset;
464 insert->count -= offset;
465 insert->offset += offset;
466 }
467 insert = m_inserts.insert(before: insert, x: current);
468 ++insert;
469 } else {
470 insert->index += insertCount;
471 ++insert;
472 insert = m_inserts.insert(before: insert, x: current);
473 ++insert;
474 }
475 }
476 insertCount += current.count;
477 }
478 for (; insert != m_inserts.end(); ++insert)
479 insert->index += insertCount;
480 m_difference += insertCount;
481}
482
483/*!
484 Applies a combined list of \a removes and \a inserts to a change set. This is equivalent
485 calling \l remove() followed by \l insert() with the same lists.
486*/
487
488void QQmlChangeSet::move(const QVector<Change> &removes, const QVector<Change> &inserts)
489{
490 QVector<Change> r = removes;
491 QVector<Change> i = inserts;
492 remove(removes: &r, inserts: &i);
493 insert(inserts: i);
494}
495
496/*!
497 Applies a list of \a changes to a change set.
498*/
499
500void QQmlChangeSet::change(const QVector<Change> &changes)
501{
502 QVector<Change> c = changes;
503 change(changes: &c);
504}
505
506void QQmlChangeSet::change(QVector<Change> *changes)
507{
508 QVector<Change>::iterator insert = m_inserts.begin();
509 QVector<Change>::iterator change = m_changes.begin();
510 for (QVector<Change>::iterator cit = changes->begin(); cit != changes->end(); ++cit) {
511 for (; insert != m_inserts.end() && insert->end() < cit->index; ++insert) {}
512 for (; insert != m_inserts.end() && insert->index < cit->end(); ++insert) {
513 const int offset = insert->index - cit->index;
514 const int count = cit->count + cit->index - insert->index - insert->count;
515 if (offset == 0) {
516 cit->index = insert->index + insert->count;
517 cit->count = count;
518 } else {
519 cit = changes->insert(before: ++cit, t: Change(insert->index + insert->count, count));
520 --cit;
521 cit->count = offset;
522 }
523 }
524
525 for (; change != m_changes.end() && change->index + change->count < cit->index; ++change) {}
526 if (change == m_changes.end() || change->index > cit->index + cit->count) {
527 if (cit->count > 0) {
528 change = m_changes.insert(before: change, x: *cit);
529 ++change;
530 }
531 } else {
532 if (cit->index < change->index) {
533 change->count += change->index - cit->index;
534 change->index = cit->index;
535 }
536
537 if (cit->index + cit->count > change->index + change->count) {
538 change->count = cit->index + cit->count - change->index;
539 QVector<Change>::iterator cbegin = change;
540 QVector<Change>::iterator cend = ++cbegin;
541 for (; cend != m_changes.end() && cend->index <= change->index + change->count; ++cend) {
542 if (cend->index + cend->count > change->index + change->count)
543 change->count = cend->index + cend->count - change->index;
544 }
545 if (cbegin != cend) {
546 change = m_changes.erase(abegin: cbegin, aend: cend);
547 --change;
548 }
549 }
550 }
551 }
552}
553
554/*!
555 Prints the contents of a change \a set to the \a debug stream.
556*/
557
558QDebug operator <<(QDebug debug, const QQmlChangeSet &set)
559{
560 debug.nospace() << "QQmlChangeSet(";
561 const QVector<QQmlChangeSet::Change> &removes = set.removes();
562 for (const QQmlChangeSet::Change &remove : removes)
563 debug << remove;
564 const QVector<QQmlChangeSet::Change> &inserts = set.inserts();
565 for (const QQmlChangeSet::Change &insert : inserts)
566 debug << insert;
567 const QVector<QQmlChangeSet::Change> &changes = set.changes();
568 for (const QQmlChangeSet::Change &change : changes)
569 debug << change;
570 return debug.nospace() << ')';
571}
572
573/*!
574 Prints a \a change to the \a debug stream.
575*/
576
577QDebug operator <<(QDebug debug, const QQmlChangeSet::Change &change)
578{
579 return (debug.nospace() << "Change(" << change.index << ',' << change.count << ')').space();
580}
581
582QT_END_NAMESPACE
583
584

source code of qtdeclarative/src/qmlmodels/qqmlchangeset.cpp