src/uisupport/flatproxymodel.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2005-2015 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         if (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
 212     return sourceSelection;
 213 }
 214
 215
 216 void FlatProxyModel::setSourceModel(QAbstractItemModel *sourceModel)
 217 {
 218     if (QAbstractProxyModel::sourceModel()) {
 219         disconnect(QAbstractProxyModel::sourceModel(), 0, this, 0);
 220     }
 221
 222     QAbstractProxyModel::setSourceModel(sourceModel);
 223
 224     emit layoutAboutToBeChanged();
 225     removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
 226     insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
 227     emit layoutChanged();
 228
 229     if (sourceModel) {
 230         connect(sourceModel, SIGNAL(columnsAboutToBeInserted(const QModelIndex &, int, int)),
 231             this, SLOT(on_columnsAboutToBeInserted(const QModelIndex &, int, int)));
 232         connect(sourceModel, SIGNAL(columnsAboutToBeRemoved(const QModelIndex &, int, int)),
 233             this, SLOT(on_columnsAboutToBeRemoved(const QModelIndex &, int, int)));
 234         connect(sourceModel, SIGNAL(columnsInserted(const QModelIndex &, int, int)),
 235             this, SLOT(on_columnsInserted(const QModelIndex &, int, int)));
 236         connect(sourceModel, SIGNAL(columnsRemoved(const QModelIndex &, int, int)),
 237             this, SLOT(on_columnsRemoved(const QModelIndex &, int, int)));
 238
 239         connect(sourceModel, SIGNAL(dataChanged(const QModelIndex &, const QModelIndex &)),
 240             this, SLOT(on_dataChanged(const QModelIndex &, const QModelIndex &)));
 241         // on_headerDataChanged(Qt::Orientation orientation, int first, int last)
 242
 243         connect(sourceModel, SIGNAL(layoutAboutToBeChanged()),
 244             this, SLOT(on_layoutAboutToBeChanged()));
 245         connect(sourceModel, SIGNAL(layoutChanged()),
 246             this, SLOT(on_layoutChanged()));
 247
 248         connect(sourceModel, SIGNAL(modelAboutToBeReset()),
 249             this, SLOT(on_modelAboutToBeReset()));
 250         // void on_modelReset()
 251
 252         connect(sourceModel, SIGNAL(rowsAboutToBeInserted(const QModelIndex &, int, int)),
 253             this, SLOT(on_rowsAboutToBeInserted(const QModelIndex &, int, int)));
 254         connect(sourceModel, SIGNAL(rowsAboutToBeRemoved(const QModelIndex &, int, int)),
 255             this, SLOT(on_rowsAboutToBeRemoved(const QModelIndex &, int, int)));
 256         connect(sourceModel, SIGNAL(rowsInserted(const QModelIndex &, int, int)),
 257             this, SLOT(on_rowsInserted(const QModelIndex &, int, int)));
 258         connect(sourceModel, SIGNAL(rowsRemoved(const QModelIndex &, int, int)),
 259             this, SLOT(on_rowsRemoved(const QModelIndex &, int, int)));
 260     }
 261 }
 262
 263
 264 void FlatProxyModel::insertSubTree(const QModelIndex &source_idx, bool emitInsert)
 265 {
 266     SourceItem *newSubTree = new SourceItem(source_idx.row(), sourceToInternal(sourceModel()->parent(source_idx)));
 267
 268     if (newSubTree->parent()) {
 269         newSubTree->setPos(newSubTree->parent()->pos() + source_idx.row() + 1);
 270     }
 271     SourceItem *lastItem = insertSubTreeHelper(newSubTree, newSubTree, source_idx);
 272
 273     Q_ASSERT(lastItem);
 274     Q_ASSERT(lastItem->next() == 0);
 275
 276     if (emitInsert)
 277         beginInsertRows(QModelIndex(), newSubTree->pos(), lastItem->pos());
 278
 279     if (newSubTree->parent()) {
 280         if (newSubTree->parent()->childCount() > source_idx.row()) {
 281             SourceItem *next = newSubTree->parent()->child(source_idx.row());
 282             lastItem->setNext(next);
 283             int nextPos = lastItem->pos() + 1;
 284             while (next) {
 285                 next->setPos(nextPos);
 286                 next = next->next();
 287                 nextPos++;
 288             }
 289         }
 290         if (source_idx.row() > 0) {
 291             SourceItem *previous = newSubTree->parent()->child(source_idx.row() - 1);
 292             while (previous->childCount() > 0) {
 293                 previous = previous->child(previous->childCount() - 1);
 294             }
 295             previous->setNext(newSubTree);
 296         }
 297         else {
 298             newSubTree->parent()->setNext(newSubTree);
 299         }
 300     }
 301     else {
 302         _rootSourceItem = newSubTree;
 303     }
 304
 305     if (emitInsert)
 306         endInsertRows();
 307 }
 308
 309
 310 FlatProxyModel::SourceItem *FlatProxyModel::insertSubTreeHelper(SourceItem *parentItem, SourceItem *lastItem_, const QModelIndex &source_idx)
 311 {
 312     SourceItem *lastItem = lastItem_;
 313     SourceItem *newItem = 0;
 314     for (int row = 0; row < sourceModel()->rowCount(source_idx); row++) {
 315         newItem = new SourceItem(row, parentItem);
 316         newItem->setPos(lastItem->pos() + 1);
 317         lastItem->setNext(newItem);
 318         lastItem = insertSubTreeHelper(newItem, newItem, sourceModel()->index(row, 0, source_idx));
 319     }
 320     return lastItem;
 321 }
 322
 323
 324 void FlatProxyModel::removeSubTree(const QModelIndex &source_idx, bool emitRemove)
 325 {
 326     SourceItem *sourceItem = sourceToInternal(source_idx);
 327     if (!sourceItem)
 328         return;
 329
 330     SourceItem *prevItem = sourceItem->parent();
 331     if (sourceItem->sourceRow() > 0) {
 332         prevItem = prevItem->child(sourceItem->sourceRow() - 1);
 333         while (prevItem->childCount() > 0) {
 334             prevItem = prevItem->child(prevItem->childCount() - 1);
 335         }
 336     }
 337
 338     SourceItem *lastItem = sourceItem;
 339     while (lastItem->childCount() > 0) {
 340         lastItem = lastItem->child(lastItem->childCount() - 1);
 341     }
 342
 343     if (emitRemove)
 344         beginRemoveRows(QModelIndex(), sourceItem->pos(), lastItem->pos());
 345
 346     int nextPos = 0;
 347     if (prevItem) {
 348         prevItem->setNext(lastItem->next());
 349         nextPos = prevItem->pos() + 1;
 350     }
 351
 352     SourceItem *nextItem = lastItem->next();
 353     while (nextItem) {
 354         nextItem->setPos(nextPos);
 355         nextPos++;
 356         nextItem = nextItem->next();
 357     }
 358
 359     sourceItem->parent()->removeChild(sourceItem);
 360     delete sourceItem;
 361
 362     if (emitRemove)
 363         endRemoveRows();
 364 }
 365
 366
 367 QModelIndex FlatProxyModel::index(int row, int column, const QModelIndex &parent) const
 368 {
 369     if (parent.isValid()) {
 370         qWarning() << "FlatProxyModel::index() called with valid parent:" << parent;
 371         return QModelIndex();
 372     }
 373
 374     if (!_rootSourceItem) {
 375         qWarning() << "FlatProxyModel::index() while model has no root Item";
 376         return QModelIndex();
 377     }
 378
 379     SourceItem *item = _rootSourceItem;
 380     while (item->pos() != row) {
 381         item = item->findChild(row);
 382         if (!item) {
 383             qWarning() << "FlatProxyModel::index() no such row:" << row;
 384             return QModelIndex();
 385         }
 386     }
 387
 388     Q_ASSERT(item->pos() == row);
 389     return createIndex(row, column, item);
 390 }
 391
 392
 393 QModelIndex FlatProxyModel::parent(const QModelIndex &index) const
 394 {
 395     Q_UNUSED(index)
 396     // this is a flat model
 397     return QModelIndex();
 398 }
 399
 400
 401 int FlatProxyModel::rowCount(const QModelIndex &index) const
 402 {
 403     if (!_rootSourceItem)
 404         return 0;
 405
 406     if (index.isValid())
 407         return 0;
 408
 409     SourceItem *item = _rootSourceItem;
 410     while (item->childCount() > 0) {
 411         item = item->child(item->childCount() - 1);
 412     }
 413     return item->pos() + 1;
 414 }
 415
 416
 417 int FlatProxyModel::columnCount(const QModelIndex &index) const
 418 {
 419     Q_UNUSED(index)
 420     if (!sourceModel()) {
 421         return 0;
 422     }
 423     else {
 424         return sourceModel()->columnCount(QModelIndex());
 425     }
 426 }
 427
 428
 429 FlatProxyModel::SourceItem *FlatProxyModel::sourceToInternal(const QModelIndex &sourceIndex) const
 430 {
 431     QList<int> childPath;
 432     for (QModelIndex idx = sourceIndex; idx.isValid(); idx = sourceModel()->parent(idx)) {
 433         childPath.prepend(idx.row());
 434     }
 435
 436     Q_ASSERT(!sourceIndex.isValid() || !childPath.isEmpty());
 437
 438     SourceItem *item = _rootSourceItem;
 439     for (int i = 0; i < childPath.count(); i++) {
 440         item = item->child(childPath[i]);
 441     }
 442     return item;
 443 }
 444
 445
 446 void FlatProxyModel::on_columnsAboutToBeInserted(const QModelIndex &parent, int start, int end)
 447 {
 448     Q_UNUSED(parent);
 449     beginInsertColumns(QModelIndex(), start, end);
 450 }
 451
 452
 453 void FlatProxyModel::on_columnsAboutToBeRemoved(const QModelIndex &parent, int start, int end)
 454 {
 455     Q_UNUSED(parent);
 456     beginRemoveColumns(QModelIndex(), start, end);
 457 }
 458
 459
 460 void FlatProxyModel::on_columnsInserted(const QModelIndex &parent, int start, int end)
 461 {
 462     Q_UNUSED(parent);
 463     Q_UNUSED(start);
 464     Q_UNUSED(end);
 465     endInsertColumns();
 466 }
 467
 468
 469 void FlatProxyModel::on_columnsRemoved(const QModelIndex &parent, int start, int end)
 470 {
 471     Q_UNUSED(parent);
 472     Q_UNUSED(start);
 473     Q_UNUSED(end);
 474     endRemoveRows();
 475 }
 476
 477
 478 void FlatProxyModel::on_dataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight)
 479 {
 480     Q_ASSERT(sourceModel());
 481     Q_ASSERT(sourceModel()->parent(topLeft) == sourceModel()->parent(bottomRight));
 482
 483     SourceItem *topLeftItem = sourceToInternal(topLeft);
 484     Q_ASSERT(topLeftItem);
 485     Q_ASSERT(topLeftItem->parent()->childCount() > bottomRight.row());
 486
 487     QModelIndex proxyTopLeft = createIndex(topLeftItem->pos(), topLeft.column(), topLeftItem);
 488     QModelIndex proxyBottomRight = createIndex(topLeftItem->pos() + bottomRight.row() - topLeft.row(), bottomRight.column(), topLeftItem->parent()->child(bottomRight.row()));
 489     emit dataChanged(proxyTopLeft, proxyBottomRight);
 490 }
 491
 492
 493 void FlatProxyModel::on_layoutAboutToBeChanged()
 494 {
 495     emit layoutAboutToBeChanged();
 496     removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
 497 }
 498
 499
 500 void FlatProxyModel::on_layoutChanged()
 501 {
 502     insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
 503     emit layoutChanged();
 504 }
 505
 506
 507 void FlatProxyModel::on_rowsAboutToBeInserted(const QModelIndex &parent, int start, int end)
 508 {
 509     Q_ASSERT(sourceModel());
 510     Q_ASSERT(_rootSourceItem);
 511
 512     SourceItem *sourceItem = sourceToInternal(parent);
 513     Q_ASSERT(sourceItem);
 514
 515     beginInsertRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
 516
 517     SourceItem *prevItem = sourceItem;
 518     if (start > 0) {
 519         prevItem = sourceItem->child(start - 1);
 520         while (prevItem->childCount() > 0) {
 521             prevItem = prevItem->child(prevItem->childCount() - 1);
 522         }
 523     }
 524     Q_ASSERT(prevItem);
 525
 526     SourceItem *nextItem = prevItem->next();
 527
 528     SourceItem *newItem = 0;
 529     int newPos = prevItem->pos() + 1;
 530     for (int row = start; row <= end; row++) {
 531         newItem = new SourceItem(row, sourceItem);
 532         newItem->setPos(newPos);
 533         newPos++;
 534         prevItem->setNext(newItem);
 535         prevItem = newItem;
 536     }
 537     prevItem->setNext(nextItem);
 538
 539     while (nextItem) {
 540         nextItem->setPos(newPos);
 541         newPos++;
 542         nextItem = nextItem->next();
 543     }
 544 }
 545
 546
 547 void FlatProxyModel::on_rowsAboutToBeRemoved(const QModelIndex &parent, int start, int end)
 548 {
 549     Q_ASSERT(sourceModel());
 550     Q_ASSERT(_rootSourceItem);
 551
 552     SourceItem *sourceItem = sourceToInternal(parent);
 553     beginRemoveRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
 554
 555     // sanity check - if that check fails our indexes would be messed up
 556     for (int row = start; row <= end; row++) {
 557         if (sourceItem->child(row)->childCount() > 0) {
 558             qWarning() << "on_rowsAboutToBeRemoved(): sourceModel() removed rows which have children on their own!" << sourceModel()->index(row, 0, parent);
 559             Q_ASSERT(false);
 560         }
 561     }
 562 }
 563
 564
 565 void FlatProxyModel::on_rowsInserted(const QModelIndex &parent, int start, int end)
 566 {
 567     Q_ASSERT(sourceModel());
 568     Q_ASSERT(_rootSourceItem);
 569
 570     SourceItem *sourceItem = sourceToInternal(parent);
 571     Q_ASSERT(sourceItem);
 572     Q_UNUSED(sourceItem);
 573
 574     // sanity check - if that check fails our indexes would be messed up
 575     for (int row = start; row <= end; row++) {
 576         QModelIndex child = sourceModel()->index(row, 0, parent);
 577         if (sourceModel()->rowCount(child) > 0) {
 578             qWarning() << "on_rowsInserted(): sourceModel() inserted rows which already have children on their own!" << child;
 579             Q_ASSERT(false);
 580         }
 581     }
 582
 583     endInsertRows();
 584 }
 585
 586
 587 void FlatProxyModel::on_rowsRemoved(const QModelIndex &parent, int start, int end)
 588 {
 589     Q_ASSERT(sourceModel());
 590     Q_ASSERT(_rootSourceItem);
 591
 592     SourceItem *sourceItem = sourceToInternal(parent);
 593     Q_ASSERT(sourceItem);
 594
 595     SourceItem *prevItem = sourceItem;
 596     if (start > 0) {
 597         prevItem = sourceItem->child(start - 1);
 598         while (prevItem->childCount() > 0) {
 599             prevItem = prevItem->child(prevItem->childCount() - 1);
 600         }
 601     }
 602     Q_ASSERT(prevItem);
 603
 604     SourceItem *nextItem = sourceItem->child(end)->next();
 605
 606     int newPos = prevItem->pos() + 1;
 607     prevItem->setNext(nextItem);
 608
 609     while (nextItem) {
 610         nextItem->setPos(newPos);
 611         newPos++;
 612         nextItem = nextItem->next();
 613     }
 614
 615     SourceItem *childItem;
 616     for (int row = start; row <= end; row++) {
 617         childItem = sourceItem->_childs.takeAt(start);
 618         delete childItem;
 619     }
 620
 621     endRemoveRows();
 622 }
 623
 624
 625 // integrity Tets
 626 void FlatProxyModel::linkTest() const
 627 {
 628     qDebug() << "Checking FlatProxyModel for linklist integrity";
 629     if (!_rootSourceItem)
 630         return;
 631
 632     int pos = -1;
 633     SourceItem *item = _rootSourceItem;
 634     while (true) {
 635         qDebug() << item << ":" << item->pos() << "==" << pos;
 636         Q_ASSERT(item->pos() == pos);
 637         pos++;
 638         if (!item->next())
 639             break;
 640         item = item->next();
 641     }
 642     qDebug() << "Last item in linklist:" << item << item->pos();
 643
 644     int lastPos = item->pos();
 645     item = _rootSourceItem;
 646     while (item->childCount() > 0) {
 647         item = item->child(item->childCount() - 1);
 648     }
 649     qDebug() << "Last item in tree:" << item << item->pos();
 650     Q_ASSERT(lastPos == item->pos());
 651     Q_UNUSED(lastPos);
 652
 653     qDebug() << "success!";
 654 }
 655
 656
 657 void FlatProxyModel::completenessTest() const
 658 {
 659     qDebug() << "Checking FlatProxyModel for Completeness:";
 660     int pos = -1;
 661     checkChildCount(QModelIndex(), _rootSourceItem, pos);
 662     qDebug() << "success!";
 663 }
 664
 665
 666 void FlatProxyModel::checkChildCount(const QModelIndex &index, const SourceItem *item, int &pos) const
 667 {
 668     if (!sourceModel())
 669         return;
 670
 671     qDebug() << index  << "(Item:" << item << "):" << sourceModel()->rowCount(index) << "==" << item->childCount();
 672     qDebug() << "ProxyPos:" << item->pos() << "==" << pos;
 673     Q_ASSERT(sourceModel()->rowCount(index) == item->childCount());
 674
 675     for (int row = 0; row < sourceModel()->rowCount(index); row++) {
 676         pos++;
 677         checkChildCount(sourceModel()->index(row, 0, index), item->child(row), pos);
 678     }
 679 }
 680
 681
 682 // ========================================
 683 //  SourceItem
 684 // ========================================
 685 FlatProxyModel::SourceItem::SourceItem(int row, SourceItem *parent)
 686     : _parent(parent),
 687     _pos(-1),
 688     _next(0)
 689 {
 690     if (parent) {
 691         parent->_childs.insert(row, this);
 692     }
 693 }
 694
 695
 696 FlatProxyModel::SourceItem::~SourceItem()
 697 {
 698     for (int i = 0; i < childCount(); i++) {
 699         delete child(i);
 700     }
 701     _childs.clear();
 702 }
 703
 704
 705 int FlatProxyModel::SourceItem::sourceRow() const
 706 {
 707     if (!parent())
 708         return -1;
 709     else
 710         return parent()->_childs.indexOf(const_cast<FlatProxyModel::SourceItem *>(this));
 711 }
 712
 713
 714 FlatProxyModel::SourceItem *FlatProxyModel::SourceItem::findChild(int proxyPos) const
 715 {
 716     Q_ASSERT(proxyPos > pos());
 717     Q_ASSERT(_childs.count() > 0);
 718     Q_ASSERT(proxyPos >= _childs[0]->pos());
 719
 720     int start = 0;
 721     int end = _childs.count() - 1;
 722     int pivot;
 723     while (end - start > 1) {
 724         pivot = (end + start) / 2;
 725         if (_childs[pivot]->pos() > proxyPos)
 726             end = pivot;
 727         else
 728             start = pivot;
 729     }
 730
 731     if (_childs[end]->pos() <= proxyPos)
 732         return _childs[end];
 733     else
 734         return _childs[start];
 735 }