1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtQml module of the Qt Toolkit.
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
42 #include "qquickchangeset_p.h"
46 QQuickChangeSet::QQuickChangeSet()
52 QQuickChangeSet::QQuickChangeSet(const QQuickChangeSet &changeSet)
53 : m_removes(changeSet.m_removes)
54 , m_inserts(changeSet.m_inserts)
55 , m_changes(changeSet.m_changes)
56 , m_moveCounter(changeSet.m_moveCounter)
61 QQuickChangeSet::~QQuickChangeSet()
65 QQuickChangeSet &QQuickChangeSet::operator =(const QQuickChangeSet &changeSet)
67 m_removes = changeSet.m_removes;
68 m_inserts = changeSet.m_inserts;
69 m_changes = changeSet.m_changes;
70 m_moveCounter = changeSet.m_moveCounter;
71 m_difference = changeSet.m_difference;
75 void QQuickChangeSet::insert(int index, int count)
77 applyInsertions(QVector<Insert>() << Insert(index, count));
80 void QQuickChangeSet::remove(int index, int count)
83 applyRemovals(QVector<Remove>() << Remove(index, count), i);
86 void QQuickChangeSet::move(int from, int to, int count)
88 apply(QVector<Remove>() << Remove(from, count, -2), QVector<Insert>() << Insert(to, count, -2));
91 void QQuickChangeSet::change(int index, int count)
93 applyChanges(QVector<Change>() << Change(index, count));
96 void QQuickChangeSet::apply(const QQuickChangeSet &changeSet)
98 apply(changeSet.m_removes, changeSet.m_inserts, changeSet.m_changes);
101 void QQuickChangeSet::apply(const QVector<Remove> &removals)
103 QVector<Remove> r = removals;
108 void QQuickChangeSet::apply(const QVector<Insert> &insertions)
110 QVector<Insert> i = insertions;
114 void QQuickChangeSet::apply(const QVector<Change> &changes)
116 QVector<Change> c = changes;
120 void QQuickChangeSet::apply(const QVector<Remove> &removals, const QVector<Insert> &insertions, const QVector<Change> &changes)
122 QVector<Remove> r = removals;
123 QVector<Insert> i = insertions;
124 QVector<Change> c = changes;
130 void QQuickChangeSet::applyRemovals(QVector<Remove> &removals, QVector<Insert> &insertions)
134 QVector<Insert>::iterator insert = m_inserts.begin();
135 QVector<Change>::iterator change = m_changes.begin();
136 QVector<Remove>::iterator rit = removals.begin();
137 for (; rit != removals.end(); ++rit) {
138 int index = rit->index + removeCount;
139 int count = rit->count;
141 QVector<Insert>::iterator iit = insertions.begin();
142 for (; rit->moveId != -1 && iit != insertions.end() && iit->moveId != rit->moveId; ++iit) {}
144 for (QVector<Remove>::iterator nrit = rit + 1; nrit != removals.end(); nrit = rit + 1) {
145 if (nrit->index != rit->index || (rit->moveId == -1) != (nrit->moveId == -1))
147 if (nrit->moveId != -1) {
148 QVector<Insert>::iterator niit = iit + 1;
149 if (niit->moveId != nrit->moveId || niit->index != iit->index + iit->count)
151 niit->index = iit->index;
152 niit->count += iit->count;
153 iit = insertions.erase(iit);
155 nrit->count += rit->count;
156 rit = removals.erase(rit);
159 for (; change != m_changes.end() && change->end() < rit->index; ++change) {}
160 for (; change != m_changes.end() && change->index > rit->end(); ++change) {
161 change->count -= qMin(change->end(), rit->end()) - qMax(change->index, rit->index);
162 if (change->count == 0) {
163 change = m_changes.erase(change);
164 } else if (rit->index < change->index) {
165 change->index = rit->index;
168 for (; insert != m_inserts.end() && insert->end() <= index; ++insert) {
169 insertCount += insert->count;
170 insert->index -= removeCount;
172 for (; insert != m_inserts.end() && insert->index < index + count; ++insert) {
173 const int offset = insert->index - index;
174 const int difference = qMin(insert->end(), index + count) - qMax(insert->index, index);
175 const int moveId = rit->moveId != -1 ? m_moveCounter++ : -1;
176 if (insert->moveId != -1) {
177 QVector<Remove>::iterator remove = m_removes.begin();
178 for (; remove != m_removes.end() && remove->moveId != insert->moveId; ++remove) {}
179 Q_ASSERT(remove != m_removes.end());
180 const int offset = index - insert->index;
181 if (rit->moveId != -1 && offset < 0) {
182 const int moveId = m_moveCounter++;
183 iit = insertions.insert(iit, Insert(iit->index, -offset, moveId));
185 iit->index += -offset;
186 iit->count -= -offset;
187 rit = removals.insert(rit, Remove(rit->index, -offset, moveId));
189 rit->count -= -offset;
193 const int moveId = m_moveCounter++;
194 insert = m_inserts.insert(insert, Insert(insert->index, offset, moveId));
196 insert->index += offset;
197 insert->count -= offset;
198 remove = m_removes.insert(remove, Remove(remove->index, offset, moveId));
200 remove->count -= offset;
201 rit->index -= offset;
206 if (remove->count == difference) {
207 remove->moveId = moveId;
209 remove = m_removes.insert(remove, Remove(remove->index, difference, moveId));
211 remove->count -= difference;
213 } else if (rit->moveId != -1 && offset > 0) {
214 const int moveId = m_moveCounter++;
215 iit = insertions.insert(iit, Insert(iit->index, offset, moveId));
217 iit->index += offset;
218 iit->count -= offset;
219 rit = removals.insert(rit, Remove(rit->index, offset, moveId));
221 rit->count -= offset;
226 if (rit->moveId != -1 && difference > 0) {
227 iit = insertions.insert(iit, Insert(
228 iit->index, difference, insert->moveId != -1 ? moveId : -1));
230 iit->index += difference;
231 iit->count -= difference;
234 insert->count -= difference;
235 rit->count -= difference;
236 if (insert->count == 0) {
237 insert = m_inserts.erase(insert);
239 } else if (index <= insert->index) {
240 insert->index = rit->index;
242 rit->index -= insert->count;
246 removeCount += difference;
248 rit->index -= insertCount;
249 removeCount += rit->count;
251 if (rit->count == 0) {
252 if (rit->moveId != -1 && iit->count == 0)
253 insertions.erase(iit);
254 rit = removals.erase(rit);
256 } else if (rit->moveId != -1) {
257 const int moveId = m_moveCounter++;
258 rit->moveId = moveId;
259 iit->moveId = moveId;
262 for (; change != m_changes.end(); ++change)
263 change->index -= removeCount;
264 for (; insert != m_inserts.end(); ++insert)
265 insert->index -= removeCount;
268 QVector<Remove>::iterator remove = m_removes.begin();
269 for (rit = removals.begin(); rit != removals.end(); ++rit) {
270 QVector<Insert>::iterator iit = insertions.begin();
271 int index = rit->index + removeCount;
272 for (; rit->moveId != -1 && iit != insertions.end() && iit->moveId != rit->moveId; ++iit) {}
273 for (; remove != m_removes.end() && index > remove->index; ++remove)
274 remove->index -= removeCount;
275 while (remove != m_removes.end() && index + rit->count > remove->index) {
277 const int offset = remove->index - index - removeCount;
278 QVector<Remove>::iterator rend = remove;
279 for (; rend != m_removes.end()
281 && rend->moveId == -1
282 && rit->index + rit->count >= rend->index; ++rend) {
283 count += rend->count;
285 if (remove != rend) {
286 const int difference = rend == m_removes.end() || rit->index + rit->count < rend->index - removeCount
292 rit->count -= difference;
293 removeCount += difference;
294 remove->index = rit->index;
295 remove->count = count;
296 remove = m_removes.erase(++remove, rend);
297 } else if (rit->moveId != -1) {
299 const int moveId = m_moveCounter++;
300 iit = insertions.insert(iit, Insert(iit->index, offset, moveId));
302 iit->index += offset;
303 iit->count -= offset;
304 remove = m_removes.insert(remove, Remove(rit->index, offset, moveId));
306 rit->count -= offset;
307 removeCount += offset;
309 remove->index = rit->index;
315 remove = m_removes.insert(remove, Remove(rit->index, offset));
317 rit->count -= offset;
318 removeCount += offset;
320 remove->index = rit->index;
328 if (rit->count > 0) {
329 remove = m_removes.insert(remove, *rit);
332 removeCount += rit->count;
334 for (; remove != m_removes.end(); ++remove)
335 remove->index -= removeCount;
336 m_difference -= removeCount;
339 void QQuickChangeSet::applyInsertions(QVector<Insert> &insertions)
342 QVector<Insert>::iterator insert = m_inserts.begin();
343 QVector<Change>::iterator change = m_changes.begin();
344 for (QVector<Insert>::iterator iit = insertions.begin(); iit != insertions.end(); ++iit) {
345 int index = iit->index - insertCount;
346 int count = iit->count;
347 for (; change != m_changes.end() && change->index >= index; ++change)
348 change->index += insertCount;
349 if (change != m_changes.end() && change->index < index + count) {
350 int offset = index - change->index;
351 change = m_changes.insert(change, Change(change->index + insertCount, offset));
353 change->index += count + offset;
354 change->count -= offset;
356 for (; insert != m_inserts.end() && iit->index > insert->index + insert->count; ++insert)
357 insert->index += insertCount;
358 if (insert == m_inserts.end()) {
359 insert = m_inserts.insert(insert, *iit);
361 insertCount += iit->count;
363 const int offset = index - insert->index;
364 if (offset < 0 || (offset == 0 && (iit->moveId != -1 || insert->moveId != -1))) {
365 insert = m_inserts.insert(insert, *iit);
367 } else if (iit->moveId == -1 && insert->moveId == -1) {
368 insert->index -= iit->count;
369 insert->count += iit->count;
370 } else if (offset < insert->count) {
371 const int moveId = insert->moveId != -1 ? m_moveCounter++ : -1;
372 insert = m_inserts.insert(insert, Insert(insert->index + insertCount, offset, moveId));
374 insert->index += offset;
375 insert->count -= offset;
376 insert = m_inserts.insert(insert, *iit);
379 if (insert->moveId != -1) {
380 QVector<Remove>::iterator remove = m_removes.begin();
381 for (; remove != m_removes.end() && remove->moveId != insert->moveId; ++remove) {}
382 Q_ASSERT(remove != m_removes.end());
383 if (remove->count == offset) {
384 remove->moveId = moveId;
386 remove = m_removes.insert(remove, Remove(remove->index, offset, moveId));
388 remove->count -= offset;
393 insert = m_inserts.insert(insert, *iit);
396 insertCount += iit->count;
399 for (; change != m_changes.end(); ++change)
400 change->index += insertCount;
401 for (; insert != m_inserts.end(); ++insert)
402 insert->index += insertCount;
403 m_difference += insertCount;
406 void QQuickChangeSet::applyChanges(QVector<Change> &changes)
408 QVector<Insert>::iterator insert = m_inserts.begin();
409 QVector<Change>::iterator change = m_changes.begin();
410 for (QVector<Change>::iterator cit = changes.begin(); cit != changes.end(); ++cit) {
411 for (; insert != m_inserts.end() && insert->end() < cit->index; ++insert) {}
412 for (; insert != m_inserts.end() && insert->index < cit->end(); ++insert) {
413 const int offset = insert->index - cit->index;
414 const int count = cit->count + cit->index - insert->index - insert->count;
416 cit->index = insert->index + insert->count;
419 cit = changes.insert(++cit, Change(insert->index + insert->count, count));
425 for (; change != m_changes.end() && change->index + change->count < cit->index; ++change) {}
426 if (change == m_changes.end() || change->index > cit->index + cit->count) {
427 if (cit->count > 0) {
428 change = m_changes.insert(change, *cit);
432 if (cit->index < change->index) {
433 change->count += change->index - cit->index;
434 change->index = cit->index;
437 if (cit->index + cit->count > change->index + change->count) {
438 change->count = cit->index + cit->count - change->index;
439 QVector<Change>::iterator rbegin = change;
440 QVector<Change>::iterator rend = ++rbegin;
441 for (; rend != m_changes.end() && rend->index <= change->index + change->count; ++rend) {
442 if (rend->index + rend->count > change->index + change->count)
443 change->count = rend->index + rend->count - change->index;
445 if (rbegin != rend) {
446 change = m_changes.erase(rbegin, rend);
454 QDebug operator <<(QDebug debug, const QQuickChangeSet &set)
456 debug.nospace() << "QQuickChangeSet(";
457 foreach (const QQuickChangeSet::Remove &remove, set.removes()) debug << remove;
458 foreach (const QQuickChangeSet::Insert &insert, set.inserts()) debug << insert;
459 foreach (const QQuickChangeSet::Change &change, set.changes()) debug << change;
460 return debug.nospace() << ")";
463 QDebug operator <<(QDebug debug, const QQuickChangeSet::Remove &remove)
465 return (debug.nospace() << "Remove(" << remove.index << "," << remove.count << "," << remove.moveId << ")").space();
468 QDebug operator <<(QDebug debug, const QQuickChangeSet::Insert &insert)
470 return (debug.nospace() << "Insert(" << insert.index << "," << insert.count << "," << insert.moveId << ")").space();
473 QDebug operator <<(QDebug debug, const QQuickChangeSet::Change &change)
475 return (debug.nospace() << "Change(" << change.index << "," << change.count << ")").space();