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 | |
42 | QT_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 | |
68 | QQmlChangeSet::QQmlChangeSet() |
69 | : m_difference(0) |
70 | { |
71 | } |
72 | |
73 | /*! |
74 | Constructs a copy of a \a changeSet. |
75 | */ |
76 | |
77 | QQmlChangeSet::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 | |
89 | QQmlChangeSet::~QQmlChangeSet() |
90 | { |
91 | } |
92 | |
93 | /*! |
94 | Assigns the value of a \a changeSet to another. |
95 | */ |
96 | |
97 | QQmlChangeSet &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 | |
110 | void 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 | |
119 | void 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 | |
133 | void 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 | |
147 | void 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 | |
158 | void 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 | |
175 | void QQmlChangeSet::remove(const QVector<Change> &removes, QVector<Change> *inserts) |
176 | { |
177 | QVector<Change> r = removes; |
178 | remove(removes: &r, inserts); |
179 | } |
180 | |
181 | void 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 | |
396 | void 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 | |
488 | void 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 | |
500 | void QQmlChangeSet::change(const QVector<Change> &changes) |
501 | { |
502 | QVector<Change> c = changes; |
503 | change(changes: &c); |
504 | } |
505 | |
506 | void 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 | |
558 | QDebug 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 | |
577 | QDebug operator <<(QDebug debug, const QQmlChangeSet::Change &change) |
578 | { |
579 | return (debug.nospace() << "Change(" << change.index << ',' << change.count << ')').space(); |
580 | } |
581 | |
582 | QT_END_NAMESPACE |
583 | |
584 | |