src/uisupport/flatproxymodel.cpp

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