src/uisupport/flatproxymodel.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2005-2018 by the Quassel Project                        *
   3  *   devel@quassel-irc.org                                                 *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) version 3.                                           *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15  *   You should have received a copy of the GNU General Public License     *
  16  *   along with this program; if not, write to the                         *
  17  *   Free Software Foundation, Inc.,                                       *
  18  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.         *
  19  ***************************************************************************/
  20
  21 #include "flatproxymodel.h"
  22
  23 #include <QDebug>
  24 #include <QItemSelection>
  25
  26 FlatProxyModel::FlatProxyModel(QObject* parent)
  27     : QAbstractProxyModel(parent)
  28 {}
  29
  30 QModelIndex FlatProxyModel::mapFromSource(const QModelIndex& sourceIndex) const
  31 {
  32     if (!sourceIndex.isValid())
  33         return {};
  34
  35     SourceItem* sourceItem = sourceToInternal(sourceIndex);
  36     Q_ASSERT(sourceItem);
  37     return createIndex(sourceItem->pos(), sourceIndex.column(), sourceItem);
  38 }
  39
  40 QModelIndex FlatProxyModel::mapToSource(const QModelIndex& proxyIndex) const
  41 {
  42     if (!proxyIndex.isValid())
  43         return {};
  44
  45     Q_ASSERT(proxyIndex.model() == this);
  46     Q_ASSERT(_rootSourceItem);
  47
  48     int row = proxyIndex.row();
  49     QModelIndex sourceParent;
  50     SourceItem* sourceItem = _rootSourceItem->findChild(row);
  51     while (sourceItem) {
  52         if (sourceItem->pos() == row) {
  53             return sourceModel()->index(sourceItem->sourceRow(), proxyIndex.column(), sourceParent);
  54         }
  55         else {
  56             sourceParent = sourceModel()->index(sourceItem->sourceRow(), 0, sourceParent);
  57             sourceItem = sourceItem->findChild(row);
  58         }
  59     }
  60
  61     qWarning() << "FlatProxyModel::mapToSource(): couldn't find source index for" << proxyIndex;
  62     Q_ASSERT(false);
  63     return {};  // make compilers happy :)
  64 }
  65
  66 bool FlatProxyModel::_RangeRect::operator<(const FlatProxyModel::_RangeRect& other) const
  67 {
  68     if (left != other.left)
  69         return left < other.left;
  70
  71     if (right != other.right)
  72         return right < other.right;
  73
  74     if (top != other.top)
  75         return top < other.top;
  76
  77     // top == other.top
  78     return bottom < other.bottom;
  79 }
  80
  81 QItemSelection FlatProxyModel::mapSelectionFromSource(const QItemSelection& sourceSelection) const
  82 {
  83     QList<_RangeRect> newRanges;
  84     QHash<QModelIndex, SourceItem*> itemLookup;
  85     // basics steps of the loop:
  86     // 1. convert each source ItemSelectionRange to a mapped Range (internal one for easier post processing)
  87     // 2. insert it into the list of previously mapped Ranges sorted by top location
  88     for (int i = 0; i < sourceSelection.count(); i++) {
  89         const QItemSelectionRange& currentRange = sourceSelection[i];
  90         QModelIndex currentParent = currentRange.topLeft().parent();
  91         Q_ASSERT(currentParent == currentRange.bottomRight().parent());
  92
  93         SourceItem* parentItem = nullptr;
  94         if (!itemLookup.contains(currentParent)) {
  95             parentItem = sourceToInternal(currentParent);
  96             itemLookup[currentParent] = parentItem;
  97         }
  98         else {
  99             parentItem = itemLookup[currentParent];
 100         }
 101
 102         _RangeRect newRange = {currentRange.topLeft().column(),
 103                                currentRange.bottomRight().column(),
 104                                currentRange.topLeft().row(),
 105                                currentRange.bottomRight().row(),
 106                                parentItem->child(currentRange.topLeft().row()),
 107                                parentItem->child(currentRange.bottomRight().row())};
 108
 109         if (newRanges.isEmpty()) {
 110             newRanges << newRange;
 111             continue;
 112         }
 113
 114         _RangeRect& first = newRanges[0];
 115         if (newRange < first) {
 116             newRanges.prepend(newRange);
 117             continue;
 118         }
 119
 120         bool inserted = false;
 121         for (int j = 0; j < newRanges.count() - 1; j++) {
 122             _RangeRect& a = newRanges[j];
 123             _RangeRect& b = newRanges[j + 1];
 124
 125             if (a < newRange && newRange < b) {
 126                 newRanges[j + 1] = newRange;
 127                 inserted = true;
 128                 break;
 129             }
 130         }
 131         if (inserted)
 132             continue;
 133
 134         _RangeRect& last = newRanges[newRanges.count() - 1];
 135         if (last < newRange) {
 136             newRanges.append(newRange);
 137             continue;
 138         }
 139
 140         Q_ASSERT(false);
 141     }
 142
 143     // we've got a sorted list of ranges now. so we can easily check if there is a possibility to merge
 144     for (int i = newRanges.count() - 1; i > 0; i--) {
 145         _RangeRect& a = newRanges[i - 1];
 146         _RangeRect& b = newRanges[i];
 147         if (a.left != b.left || a.right != b.right)
 148             continue;
 149
 150         if (a.bottom < b.top - 1) {
 151             continue;
 152         }
 153
 154         // all merge checks passed!
 155         if (b.bottom > a.bottom) {
 156             a.bottom = b.bottom;
 157             a.bottomItem = b.bottomItem;
 158         }  // otherwise b is totally enclosed in a -> nothing to do but drop b.
 159         newRanges.removeAt(i);
 160     }
 161
 162     QItemSelection proxySelection;
 163     for (int i = 0; i < newRanges.count(); i++) {
 164         _RangeRect& r = newRanges[i];
 165         proxySelection << QItemSelectionRange(createIndex(r.top, r.left, r.topItem), createIndex(r.bottom, r.right, r.bottomItem));
 166     }
 167     return proxySelection;
 168 }
 169
 170 QItemSelection FlatProxyModel::mapSelectionToSource(const QItemSelection& proxySelection) const
 171 {
 172     QItemSelection sourceSelection;
 173
 174     for (int i = 0; i < proxySelection.count(); i++) {
 175         const QItemSelectionRange& range = proxySelection[i];
 176
 177         SourceItem* topLeftItem = nullptr;
 178         SourceItem* bottomRightItem = nullptr;
 179         auto* currentItem = static_cast<SourceItem*>(range.topLeft().internalPointer());
 180         int row = range.topLeft().row();
 181         int left = range.topLeft().column();
 182         int right = range.bottomRight().column();
 183         while (currentItem && row <= range.bottomRight().row()) {
 184             Q_ASSERT(currentItem->pos() == row);
 185             if (!topLeftItem)
 186                 topLeftItem = currentItem;
 187
 188             if (currentItem->parent() == topLeftItem->parent()) {
 189                 bottomRightItem = currentItem;
 190             }
 191             else {
 192                 Q_ASSERT(topLeftItem && bottomRightItem);
 193                 sourceSelection << QItemSelectionRange(mapToSource(createIndex(topLeftItem->pos(), left, topLeftItem)),
 194                                                        mapToSource(createIndex(bottomRightItem->pos(), right, bottomRightItem)));
 195                 topLeftItem = nullptr;
 196                 bottomRightItem = nullptr;
 197             }
 198
 199             // update loop vars
 200             currentItem = currentItem->next();
 201             row++;
 202         }
 203
 204         if (topLeftItem && bottomRightItem) {  // there should be one range left.
 205             sourceSelection << QItemSelectionRange(mapToSource(createIndex(topLeftItem->pos(), left, topLeftItem)),
 206                                                    mapToSource(createIndex(bottomRightItem->pos(), right, bottomRightItem)));
 207         }
 208     }
 209
 210     return sourceSelection;
 211 }
 212
 213 void FlatProxyModel::setSourceModel(QAbstractItemModel* sourceModel)
 214 {
 215     if (QAbstractProxyModel::sourceModel()) {
 216         disconnect(QAbstractProxyModel::sourceModel(), nullptr, this, nullptr);
 217     }
 218
 219     QAbstractProxyModel::setSourceModel(sourceModel);
 220
 221     emit layoutAboutToBeChanged();
 222     removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
 223     insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
 224     emit layoutChanged();
 225
 226     if (sourceModel) {
 227         connect(sourceModel, &QAbstractItemModel::columnsAboutToBeInserted, this, &FlatProxyModel::on_columnsAboutToBeInserted);
 228         connect(sourceModel, &QAbstractItemModel::columnsAboutToBeRemoved, this, &FlatProxyModel::on_columnsAboutToBeRemoved);
 229         connect(sourceModel, &QAbstractItemModel::columnsInserted, this, &FlatProxyModel::on_columnsInserted);
 230         connect(sourceModel, &QAbstractItemModel::columnsRemoved, this, &FlatProxyModel::on_columnsRemoved);
 231
 232         connect(sourceModel, &QAbstractItemModel::dataChanged, this, &FlatProxyModel::on_dataChanged);
 233         // on_headerDataChanged(Qt::Orientation orientation, int first, int last)
 234
 235         connect(sourceModel, &QAbstractItemModel::layoutAboutToBeChanged, this, &FlatProxyModel::on_layoutAboutToBeChanged);
 236         connect(sourceModel, &QAbstractItemModel::layoutChanged, this, &FlatProxyModel::on_layoutChanged);
 237
 238         connect(sourceModel, &QAbstractItemModel::modelAboutToBeReset, this, &FlatProxyModel::on_modelAboutToBeReset);
 239         // void on_modelReset()
 240
 241         connect(sourceModel, &QAbstractItemModel::rowsAboutToBeInserted, this, &FlatProxyModel::on_rowsAboutToBeInserted);
 242         connect(sourceModel, &QAbstractItemModel::rowsAboutToBeRemoved, this, &FlatProxyModel::on_rowsAboutToBeRemoved);
 243         connect(sourceModel, &QAbstractItemModel::rowsInserted, this, &FlatProxyModel::on_rowsInserted);
 244         connect(sourceModel, &QAbstractItemModel::rowsRemoved, this, &FlatProxyModel::on_rowsRemoved);
 245     }
 246 }
 247
 248 void FlatProxyModel::insertSubTree(const QModelIndex& source_idx, bool emitInsert)
 249 {
 250     SourceItem* newSubTree = new SourceItem(source_idx.row(), sourceToInternal(sourceModel()->parent(source_idx)));
 251
 252     if (newSubTree->parent()) {
 253         newSubTree->setPos(newSubTree->parent()->pos() + source_idx.row() + 1);
 254     }
 255     SourceItem* lastItem = insertSubTreeHelper(newSubTree, newSubTree, source_idx);
 256
 257     Q_ASSERT(lastItem);
 258     Q_ASSERT(lastItem->next() == nullptr);
 259
 260     if (emitInsert)
 261         beginInsertRows(QModelIndex(), newSubTree->pos(), lastItem->pos());
 262
 263     if (newSubTree->parent()) {
 264         if (newSubTree->parent()->childCount() > source_idx.row()) {
 265             SourceItem* next = newSubTree->parent()->child(source_idx.row());
 266             lastItem->setNext(next);
 267             int nextPos = lastItem->pos() + 1;
 268             while (next) {
 269                 next->setPos(nextPos);
 270                 next = next->next();
 271                 nextPos++;
 272             }
 273         }
 274         if (source_idx.row() > 0) {
 275             SourceItem* previous = newSubTree->parent()->child(source_idx.row() - 1);
 276             while (previous->childCount() > 0) {
 277                 previous = previous->child(previous->childCount() - 1);
 278             }
 279             previous->setNext(newSubTree);
 280         }
 281         else {
 282             newSubTree->parent()->setNext(newSubTree);
 283         }
 284     }
 285     else {
 286         _rootSourceItem = newSubTree;
 287     }
 288
 289     if (emitInsert)
 290         endInsertRows();
 291 }
 292
 293 FlatProxyModel::SourceItem* FlatProxyModel::insertSubTreeHelper(SourceItem* parentItem, SourceItem* lastItem_, const QModelIndex& source_idx)
 294 {
 295     SourceItem* lastItem = lastItem_;
 296     SourceItem* newItem = nullptr;
 297     for (int row = 0; row < sourceModel()->rowCount(source_idx); row++) {
 298         newItem = new SourceItem(row, parentItem);
 299         newItem->setPos(lastItem->pos() + 1);
 300         lastItem->setNext(newItem);
 301         lastItem = insertSubTreeHelper(newItem, newItem, sourceModel()->index(row, 0, source_idx));
 302     }
 303     return lastItem;
 304 }
 305
 306 void FlatProxyModel::removeSubTree(const QModelIndex& source_idx, bool emitRemove)
 307 {
 308     SourceItem* sourceItem = sourceToInternal(source_idx);
 309     if (!sourceItem)
 310         return;
 311
 312     SourceItem* prevItem = sourceItem->parent();
 313     if (sourceItem->sourceRow() > 0) {
 314         prevItem = prevItem->child(sourceItem->sourceRow() - 1);
 315         while (prevItem->childCount() > 0) {
 316             prevItem = prevItem->child(prevItem->childCount() - 1);
 317         }
 318     }
 319
 320     SourceItem* lastItem = sourceItem;
 321     while (lastItem->childCount() > 0) {
 322         lastItem = lastItem->child(lastItem->childCount() - 1);
 323     }
 324
 325     if (emitRemove)
 326         beginRemoveRows(QModelIndex(), sourceItem->pos(), lastItem->pos());
 327
 328     int nextPos = 0;
 329     if (prevItem) {
 330         prevItem->setNext(lastItem->next());
 331         nextPos = prevItem->pos() + 1;
 332     }
 333
 334     SourceItem* nextItem = lastItem->next();
 335     while (nextItem) {
 336         nextItem->setPos(nextPos);
 337         nextPos++;
 338         nextItem = nextItem->next();
 339     }
 340
 341     sourceItem->parent()->removeChild(sourceItem);
 342     delete sourceItem;
 343
 344     if (emitRemove)
 345         endRemoveRows();
 346 }
 347
 348 QModelIndex FlatProxyModel::index(int row, int column, const QModelIndex& parent) const
 349 {
 350     if (parent.isValid()) {
 351         qWarning() << "FlatProxyModel::index() called with valid parent:" << parent;
 352         return {};
 353     }
 354
 355     if (!_rootSourceItem) {
 356         qWarning() << "FlatProxyModel::index() while model has no root Item";
 357         return {};
 358     }
 359
 360     SourceItem* item = _rootSourceItem;
 361     while (item->pos() != row) {
 362         item = item->findChild(row);
 363         if (!item) {
 364             qWarning() << "FlatProxyModel::index() no such row:" << row;
 365             return {};
 366         }
 367     }
 368
 369     Q_ASSERT(item->pos() == row);
 370     return createIndex(row, column, item);
 371 }
 372
 373 QModelIndex FlatProxyModel::parent(const QModelIndex& index) const
 374 {
 375     Q_UNUSED(index)
 376     // this is a flat model
 377     return {};
 378 }
 379
 380 int FlatProxyModel::rowCount(const QModelIndex& index) const
 381 {
 382     if (!_rootSourceItem)
 383         return 0;
 384
 385     if (index.isValid())
 386         return 0;
 387
 388     SourceItem* item = _rootSourceItem;
 389     while (item->childCount() > 0) {
 390         item = item->child(item->childCount() - 1);
 391     }
 392     return item->pos() + 1;
 393 }
 394
 395 int FlatProxyModel::columnCount(const QModelIndex& index) const
 396 {
 397     Q_UNUSED(index)
 398     if (!sourceModel()) {
 399         return 0;
 400     }
 401     else {
 402         return sourceModel()->columnCount(QModelIndex());
 403     }
 404 }
 405
 406 FlatProxyModel::SourceItem* FlatProxyModel::sourceToInternal(const QModelIndex& sourceIndex) const
 407 {
 408     QList<int> childPath;
 409     for (QModelIndex idx = sourceIndex; idx.isValid(); idx = sourceModel()->parent(idx)) {
 410         childPath.prepend(idx.row());
 411     }
 412
 413     Q_ASSERT(!sourceIndex.isValid() || !childPath.isEmpty());
 414
 415     SourceItem* item = _rootSourceItem;
 416     for (int i = 0; i < childPath.count(); i++) {
 417         item = item->child(childPath[i]);
 418     }
 419     return item;
 420 }
 421
 422 void FlatProxyModel::on_columnsAboutToBeInserted(const QModelIndex& parent, int start, int end)
 423 {
 424     Q_UNUSED(parent);
 425     beginInsertColumns(QModelIndex(), start, end);
 426 }
 427
 428 void FlatProxyModel::on_columnsAboutToBeRemoved(const QModelIndex& parent, int start, int end)
 429 {
 430     Q_UNUSED(parent);
 431     beginRemoveColumns(QModelIndex(), start, end);
 432 }
 433
 434 void FlatProxyModel::on_columnsInserted(const QModelIndex& parent, int start, int end)
 435 {
 436     Q_UNUSED(parent);
 437     Q_UNUSED(start);
 438     Q_UNUSED(end);
 439     endInsertColumns();
 440 }
 441
 442 void FlatProxyModel::on_columnsRemoved(const QModelIndex& parent, int start, int end)
 443 {
 444     Q_UNUSED(parent);
 445     Q_UNUSED(start);
 446     Q_UNUSED(end);
 447     endRemoveRows();
 448 }
 449
 450 void FlatProxyModel::on_dataChanged(const QModelIndex& topLeft, const QModelIndex& bottomRight)
 451 {
 452     Q_ASSERT(sourceModel());
 453     Q_ASSERT(sourceModel()->parent(topLeft) == sourceModel()->parent(bottomRight));
 454
 455     SourceItem* topLeftItem = sourceToInternal(topLeft);
 456     Q_ASSERT(topLeftItem);
 457     Q_ASSERT(topLeftItem->parent()->childCount() > bottomRight.row());
 458
 459     QModelIndex proxyTopLeft = createIndex(topLeftItem->pos(), topLeft.column(), topLeftItem);
 460     QModelIndex proxyBottomRight = createIndex(topLeftItem->pos() + bottomRight.row() - topLeft.row(),
 461                                                bottomRight.column(),
 462                                                topLeftItem->parent()->child(bottomRight.row()));
 463     emit dataChanged(proxyTopLeft, proxyBottomRight);
 464 }
 465
 466 void FlatProxyModel::on_layoutAboutToBeChanged()
 467 {
 468     emit layoutAboutToBeChanged();
 469     removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
 470 }
 471
 472 void FlatProxyModel::on_layoutChanged()
 473 {
 474     insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
 475     emit layoutChanged();
 476 }
 477
 478 void FlatProxyModel::on_rowsAboutToBeInserted(const QModelIndex& parent, int start, int end)
 479 {
 480     Q_ASSERT(sourceModel());
 481     Q_ASSERT(_rootSourceItem);
 482
 483     SourceItem* sourceItem = sourceToInternal(parent);
 484     Q_ASSERT(sourceItem);
 485
 486     beginInsertRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
 487
 488     SourceItem* prevItem = sourceItem;
 489     if (start > 0) {
 490         prevItem = sourceItem->child(start - 1);
 491         while (prevItem->childCount() > 0) {
 492             prevItem = prevItem->child(prevItem->childCount() - 1);
 493         }
 494     }
 495     Q_ASSERT(prevItem);
 496
 497     SourceItem* nextItem = prevItem->next();
 498
 499     SourceItem* newItem = nullptr;
 500     int newPos = prevItem->pos() + 1;
 501     for (int row = start; row <= end; row++) {
 502         newItem = new SourceItem(row, sourceItem);
 503         newItem->setPos(newPos);
 504         newPos++;
 505         prevItem->setNext(newItem);
 506         prevItem = newItem;
 507     }
 508     prevItem->setNext(nextItem);
 509
 510     while (nextItem) {
 511         nextItem->setPos(newPos);
 512         newPos++;
 513         nextItem = nextItem->next();
 514     }
 515 }
 516
 517 void FlatProxyModel::on_rowsAboutToBeRemoved(const QModelIndex& parent, int start, int end)
 518 {
 519     Q_ASSERT(sourceModel());
 520     Q_ASSERT(_rootSourceItem);
 521
 522     SourceItem* sourceItem = sourceToInternal(parent);
 523     beginRemoveRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
 524
 525     // sanity check - if that check fails our indexes would be messed up
 526     for (int row = start; row <= end; row++) {
 527         if (sourceItem->child(row)->childCount() > 0) {
 528             qWarning() << "on_rowsAboutToBeRemoved(): sourceModel() removed rows which have children on their own!"
 529                        << sourceModel()->index(row, 0, parent);
 530             Q_ASSERT(false);
 531         }
 532     }
 533 }
 534
 535 void FlatProxyModel::on_rowsInserted(const QModelIndex& parent, int start, int end)
 536 {
 537     Q_ASSERT(sourceModel());
 538     Q_ASSERT(_rootSourceItem);
 539
 540     SourceItem* sourceItem = sourceToInternal(parent);
 541     Q_ASSERT(sourceItem);
 542     Q_UNUSED(sourceItem);
 543
 544     // sanity check - if that check fails our indexes would be messed up
 545     for (int row = start; row <= end; row++) {
 546         QModelIndex child = sourceModel()->index(row, 0, parent);
 547         if (sourceModel()->rowCount(child) > 0) {
 548             qWarning() << "on_rowsInserted(): sourceModel() inserted rows which already have children on their own!" << child;
 549             Q_ASSERT(false);
 550         }
 551     }
 552
 553     endInsertRows();
 554 }
 555
 556 void FlatProxyModel::on_rowsRemoved(const QModelIndex& parent, int start, int end)
 557 {
 558     Q_ASSERT(sourceModel());
 559     Q_ASSERT(_rootSourceItem);
 560
 561     SourceItem* sourceItem = sourceToInternal(parent);
 562     Q_ASSERT(sourceItem);
 563
 564     SourceItem* prevItem = sourceItem;
 565     if (start > 0) {
 566         prevItem = sourceItem->child(start - 1);
 567         while (prevItem->childCount() > 0) {
 568             prevItem = prevItem->child(prevItem->childCount() - 1);
 569         }
 570     }
 571     Q_ASSERT(prevItem);
 572
 573     SourceItem* nextItem = sourceItem->child(end)->next();
 574
 575     int newPos = prevItem->pos() + 1;
 576     prevItem->setNext(nextItem);
 577
 578     while (nextItem) {
 579         nextItem->setPos(newPos);
 580         newPos++;
 581         nextItem = nextItem->next();
 582     }
 583
 584     SourceItem* childItem;
 585     for (int row = start; row <= end; row++) {
 586         childItem = sourceItem->_childs.takeAt(start);
 587         delete childItem;
 588     }
 589
 590     endRemoveRows();
 591 }
 592
 593 // integrity Tets
 594 void FlatProxyModel::linkTest() const
 595 {
 596     qDebug() << "Checking FlatProxyModel for linklist integrity";
 597     if (!_rootSourceItem)
 598         return;
 599
 600     int pos = -1;
 601     SourceItem* item = _rootSourceItem;
 602     while (true) {
 603         qDebug() << item << ":" << item->pos() << "==" << pos;
 604         Q_ASSERT(item->pos() == pos);
 605         pos++;
 606         if (!item->next())
 607             break;
 608         item = item->next();
 609     }
 610     qDebug() << "Last item in linklist:" << item << item->pos();
 611
 612     int lastPos = item->pos();
 613     item = _rootSourceItem;
 614     while (item->childCount() > 0) {
 615         item = item->child(item->childCount() - 1);
 616     }
 617     qDebug() << "Last item in tree:" << item << item->pos();
 618     Q_ASSERT(lastPos == item->pos());
 619     Q_UNUSED(lastPos);
 620
 621     qDebug() << "success!";
 622 }
 623
 624 void FlatProxyModel::completenessTest() const
 625 {
 626     qDebug() << "Checking FlatProxyModel for Completeness:";
 627     int pos = -1;
 628     checkChildCount(QModelIndex(), _rootSourceItem, pos);
 629     qDebug() << "success!";
 630 }
 631
 632 void FlatProxyModel::checkChildCount(const QModelIndex& index, const SourceItem* item, int& pos) const
 633 {
 634     if (!sourceModel())
 635         return;
 636
 637     qDebug() << index << "(Item:" << item << "):" << sourceModel()->rowCount(index) << "==" << item->childCount();
 638     qDebug() << "ProxyPos:" << item->pos() << "==" << pos;
 639     Q_ASSERT(sourceModel()->rowCount(index) == item->childCount());
 640
 641     for (int row = 0; row < sourceModel()->rowCount(index); row++) {
 642         pos++;
 643         checkChildCount(sourceModel()->index(row, 0, index), item->child(row), pos);
 644     }
 645 }
 646
 647 // ========================================
 648 //  SourceItem
 649 // ========================================
 650 FlatProxyModel::SourceItem::SourceItem(int row, SourceItem* parent)
 651     : _parent(parent)
 652 {
 653     if (parent) {
 654         parent->_childs.insert(row, this);
 655     }
 656 }
 657
 658 FlatProxyModel::SourceItem::~SourceItem()
 659 {
 660     for (int i = 0; i < childCount(); i++) {
 661         delete child(i);
 662     }
 663     _childs.clear();
 664 }
 665
 666 int FlatProxyModel::SourceItem::sourceRow() const
 667 {
 668     if (!parent())
 669         return -1;
 670     else
 671         return parent()->_childs.indexOf(const_cast<FlatProxyModel::SourceItem*>(this));
 672 }
 673
 674 FlatProxyModel::SourceItem* FlatProxyModel::SourceItem::findChild(int proxyPos) const
 675 {
 676     Q_ASSERT(proxyPos > pos());
 677     Q_ASSERT(_childs.count() > 0);
 678     Q_ASSERT(proxyPos >= _childs[0]->pos());
 679
 680     int start = 0;
 681     int end = _childs.count() - 1;
 682     int pivot;
 683     while (end - start > 1) {
 684         pivot = (end + start) / 2;
 685         if (_childs[pivot]->pos() > proxyPos)
 686             end = pivot;
 687         else
 688             start = pivot;
 689     }
 690
 691     if (_childs[end]->pos() <= proxyPos)
 692         return _childs[end];
 693     else
 694         return _childs[start];
 695 }