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

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