src/quick/util/qdeclarativechangeset.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtDeclarative module of the Qt Toolkit.
   7 **
   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.
  16 **
  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.
  20 **
  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.
  28 **
  29 ** Other Usage
  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.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qdeclarativechangeset_p.h"
  43
  44 QT_BEGIN_NAMESPACE
  45
  46 QDeclarativeChangeSet::QDeclarativeChangeSet()
  47     : m_moveCounter(0)
  48     , m_difference(0)
  49 {
  50 }
  51
  52 QDeclarativeChangeSet::QDeclarativeChangeSet(const QDeclarativeChangeSet &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)
  57     , m_difference(0)
  58 {
  59 }
  60
  61 QDeclarativeChangeSet::~QDeclarativeChangeSet()
  62 {
  63 }
  64
  65 QDeclarativeChangeSet &QDeclarativeChangeSet::operator =(const QDeclarativeChangeSet &changeSet)
  66 {
  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;
  72     return *this;
  73 }
  74
  75 void QDeclarativeChangeSet::insert(int index, int count)
  76 {
  77     applyInsertions(QVector<Insert>() << Insert(index, count));
  78 }
  79
  80 void QDeclarativeChangeSet::remove(int index, int count)
  81 {
  82     QVector<Insert> i;
  83     applyRemovals(QVector<Remove>() << Remove(index, count), i);
  84 }
  85
  86 void QDeclarativeChangeSet::move(int from, int to, int count)
  87 {
  88     apply(QVector<Remove>() << Remove(from, count, -2), QVector<Insert>() << Insert(to, count, -2));
  89 }
  90
  91 void QDeclarativeChangeSet::change(int index, int count)
  92 {
  93     applyChanges(QVector<Change>() << Change(index, count));
  94 }
  95
  96 void QDeclarativeChangeSet::apply(const QDeclarativeChangeSet &changeSet)
  97 {
  98     apply(changeSet.m_removes, changeSet.m_inserts, changeSet.m_changes);
  99 }
 100
 101 void QDeclarativeChangeSet::apply(const QVector<Remove> &removals)
 102 {
 103     QVector<Remove> r = removals;
 104     QVector<Insert> i;
 105     applyRemovals(r, i);
 106 }
 107
 108 void QDeclarativeChangeSet::apply(const QVector<Insert> &insertions)
 109 {
 110     QVector<Insert> i = insertions;
 111     applyInsertions(i);
 112 }
 113
 114 void QDeclarativeChangeSet::apply(const QVector<Change> &changes)
 115 {
 116     QVector<Change> c = changes;
 117     applyChanges(c);
 118 }
 119
 120 void QDeclarativeChangeSet::apply(const QVector<Remove> &removals, const QVector<Insert> &insertions, const QVector<Change> &changes)
 121 {
 122     QVector<Remove> r = removals;
 123     QVector<Insert> i = insertions;
 124     QVector<Change> c = changes;
 125     applyRemovals(r, i);
 126     applyInsertions(i);
 127     applyChanges(c);
 128 }
 129
 130 void QDeclarativeChangeSet::applyRemovals(QVector<Remove> &removals, QVector<Insert> &insertions)
 131 {
 132     int removeCount = 0;
 133     int insertCount = 0;
 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;
 140
 141         QVector<Insert>::iterator iit = insertions.begin();
 142         for (; rit->moveId != -1 && iit != insertions.end() && iit->moveId != rit->moveId; ++iit) {}
 143
 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))
 146                 break;
 147             if (nrit->moveId != -1) {
 148                 QVector<Insert>::iterator niit = iit + 1;
 149                 if (niit->moveId != nrit->moveId || niit->index != iit->index + iit->count)
 150                     break;
 151                 niit->index = iit->index;
 152                 niit->count += iit->count;
 153                 iit = insertions.erase(iit);
 154             }
 155             nrit->count += rit->count;
 156             rit = removals.erase(rit);
 157         }
 158
 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;
 166             }
 167         }
 168         for (; insert != m_inserts.end() && insert->end() <= index; ++insert) {
 169             insertCount += insert->count;
 170             insert->index -= removeCount;
 171         }
 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));
 184                     ++iit;
 185                     iit->index += -offset;
 186                     iit->count -= -offset;
 187                     rit = removals.insert(rit, Remove(rit->index, -offset, moveId));
 188                     ++rit;
 189                     rit->count -= -offset;
 190                 }
 191
 192                 if (offset > 0) {
 193                     const int moveId = m_moveCounter++;
 194                     insert = m_inserts.insert(insert, Insert(insert->index, offset, moveId));
 195                     ++insert;
 196                     insert->index += offset;
 197                     insert->count -= offset;
 198                     remove = m_removes.insert(remove, Remove(remove->index, offset, moveId));
 199                     ++remove;
 200                     remove->count -= offset;
 201                     rit->index -= offset;
 202                     index += offset;
 203                     count -= offset;
 204                 }
 205
 206                 if (remove->count == difference) {
 207                     remove->moveId = moveId;
 208                 } else {
 209                     remove = m_removes.insert(remove, Remove(remove->index, difference, moveId));
 210                     ++remove;
 211                     remove->count -= difference;
 212                 }
 213             } else if (rit->moveId != -1 && offset > 0) {
 214                 const int moveId = m_moveCounter++;
 215                 iit = insertions.insert(iit, Insert(iit->index, offset, moveId));
 216                 ++iit;
 217                 iit->index += offset;
 218                 iit->count -= offset;
 219                 rit = removals.insert(rit, Remove(rit->index, offset, moveId));
 220                 ++rit;
 221                 rit->count -= offset;
 222                 index += offset;
 223                 count -= offset;
 224             }
 225
 226             if (rit->moveId != -1 && difference > 0) {
 227                 iit = insertions.insert(iit, Insert(
 228                         iit->index, difference, insert->moveId != -1 ? moveId : -1));
 229                 ++iit;
 230                 iit->index += difference;
 231                 iit->count -= difference;
 232             }
 233
 234             insert->count -= difference;
 235             rit->count -= difference;
 236             if (insert->count == 0) {
 237                 insert = m_inserts.erase(insert);
 238                 --insert;
 239             } else if (index <= insert->index) {
 240                 insert->index = rit->index;
 241             } else {
 242                 rit->index -= insert->count;
 243             }
 244             index += difference;
 245             count -= difference;
 246             removeCount += difference;
 247         }
 248         rit->index -= insertCount;
 249         removeCount += rit->count;
 250
 251         if (rit->count == 0) {
 252             if (rit->moveId != -1 && iit->count == 0)
 253                 insertions.erase(iit);
 254             rit = removals.erase(rit);
 255             --rit;
 256         } else if (rit->moveId != -1) {
 257             const int moveId = m_moveCounter++;
 258             rit->moveId = moveId;
 259             iit->moveId = moveId;
 260         }
 261     }
 262     for (; change != m_changes.end(); ++change)
 263         change->index -= removeCount;
 264     for (; insert != m_inserts.end(); ++insert)
 265         insert->index -= removeCount;
 266
 267     removeCount = 0;
 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) {
 276             int count = 0;
 277             const int offset = remove->index - index - removeCount;
 278             QVector<Remove>::iterator rend = remove;
 279             for (; rend != m_removes.end()
 280                     && rit->moveId == -1
 281                     && rend->moveId == -1
 282                     && rit->index + rit->count >= rend->index; ++rend) {
 283                 count += rend->count;
 284             }
 285             if (remove != rend) {
 286                 const int difference = rend == m_removes.end() || rit->index + rit->count < rend->index - removeCount
 287                         ? rit->count
 288                         : offset;
 289                 count += difference;
 290
 291                 index += difference;
 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) {
 298                 if (offset > 0) {
 299                     const int moveId = m_moveCounter++;
 300                     iit = insertions.insert(iit, Insert(iit->index, offset, moveId));
 301                     ++iit;
 302                     iit->index += offset;
 303                     iit->count -= offset;
 304                     remove = m_removes.insert(remove, Remove(rit->index, offset, moveId));
 305                     ++remove;
 306                     rit->count -= offset;
 307                     removeCount += offset;
 308                 }
 309                 remove->index = rit->index;
 310                 index += offset;
 311
 312                 ++remove;
 313             } else {
 314                 if (offset > 0) {
 315                     remove = m_removes.insert(remove, Remove(rit->index, offset));
 316                     ++remove;
 317                     rit->count -= offset;
 318                     removeCount += offset;
 319                 }
 320                 remove->index = rit->index;
 321                 index += offset;
 322
 323                 ++remove;
 324             }
 325             index += count;
 326         }
 327
 328         if (rit->count > 0) {
 329             remove = m_removes.insert(remove, *rit);
 330             ++remove;
 331         }
 332         removeCount += rit->count;
 333     }
 334     for (; remove != m_removes.end(); ++remove)
 335         remove->index -= removeCount;
 336     m_difference -= removeCount;
 337 }
 338
 339 void QDeclarativeChangeSet::applyInsertions(QVector<Insert> &insertions)
 340 {
 341     int insertCount = 0;
 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));
 352                 ++change;
 353                 change->index += count + offset;
 354                 change->count -= offset;
 355         }
 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);
 360             ++insert;
 361             insertCount += iit->count;
 362         } else {
 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);
 366                 ++insert;
 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));
 373                 ++insert;
 374                 insert->index += offset;
 375                 insert->count -= offset;
 376                 insert = m_inserts.insert(insert, *iit);
 377                 ++insert;
 378
 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;
 385                     } else {
 386                         remove = m_removes.insert(remove, Remove(remove->index, offset, moveId));
 387                         ++remove;
 388                         remove->count -= offset;
 389                     }
 390                 }
 391             } else {
 392                 ++insert;
 393                 insert = m_inserts.insert(insert, *iit);
 394                 ++insert;
 395             }
 396             insertCount += iit->count;
 397         }
 398     }
 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;
 404 }
 405
 406 void QDeclarativeChangeSet::applyChanges(QVector<Change> &changes)
 407 {
 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;
 415             if (offset == 0) {
 416                 cit->index = insert->index + insert->count;
 417                 cit->count = count;
 418             } else {
 419                 cit = changes.insert(++cit, Change(insert->index + insert->count, count));
 420                 --cit;
 421                 cit->count = offset;
 422             }
 423         }
 424
 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);
 429                 ++change;
 430             }
 431         } else {
 432             if (cit->index < change->index) {
 433                 change->count += change->index - cit->index;
 434                 change->index = cit->index;
 435             }
 436
 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;
 444                 }
 445                 if (rbegin != rend) {
 446                     change = m_changes.erase(rbegin, rend);
 447                     --change;
 448                 }
 449             }
 450         }
 451     }
 452 }
 453
 454 QDebug operator <<(QDebug debug, const QDeclarativeChangeSet &set)
 455 {
 456     debug.nospace() << "QDeclarativeChangeSet(";
 457     foreach (const QDeclarativeChangeSet::Remove &remove, set.removes()) debug << remove;
 458     foreach (const QDeclarativeChangeSet::Insert &insert, set.inserts()) debug << insert;
 459     foreach (const QDeclarativeChangeSet::Change &change, set.changes()) debug << change;
 460     return debug.nospace() << ")";
 461 }
 462
 463 QDebug operator <<(QDebug debug, const QDeclarativeChangeSet::Remove &remove)
 464 {
 465     return (debug.nospace() << "Remove(" << remove.index << "," << remove.count << "," << remove.moveId << ")").space();
 466 }
 467
 468 QDebug operator <<(QDebug debug, const QDeclarativeChangeSet::Insert &insert)
 469 {
 470     return (debug.nospace() << "Insert(" << insert.index << "," << insert.count << "," << insert.moveId << ")").space();
 471 }
 472
 473 QDebug operator <<(QDebug debug, const QDeclarativeChangeSet::Change &change)
 474 {
 475     return (debug.nospace() << "Change(" << change.index << "," << change.count << ")").space();
 476 }
 477
 478 QT_END_NAMESPACE
 479