src/uisupport/flatproxymodel.cpp

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