1 /***************************************************************************
2 * Copyright (C) 2005-08 by the Quassel Project *
3 * devel@quassel-irc.org *
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. *
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. *
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 ***************************************************************************/
21 #include "flatproxymodel.h"
23 #include <QItemSelection>
26 FlatProxyModel::FlatProxyModel(QObject *parent)
27 : QAbstractProxyModel(parent),
32 QModelIndex FlatProxyModel::mapFromSource(const QModelIndex &sourceIndex) const {
33 if(!sourceIndex.isValid())
36 SourceItem *sourceItem = sourceToInternal(sourceIndex);
38 return createIndex(sourceItem->pos(), sourceIndex.column(), sourceItem);
41 QModelIndex FlatProxyModel::mapToSource(const QModelIndex &proxyIndex) const {
42 if(!proxyIndex.isValid())
45 Q_ASSERT(proxyIndex.model() == this);
46 Q_ASSERT(_rootSourceItem);
48 int row = proxyIndex.row();
49 QModelIndex sourceParent;
50 SourceItem *sourceItem = _rootSourceItem->findChild(row);
52 if(sourceItem->pos() == row) {
53 return sourceModel()->index(sourceItem->sourceRow(), proxyIndex.column(), sourceParent);
55 sourceParent = sourceModel()->index(sourceItem->sourceRow(), 0, sourceParent);
56 sourceItem = sourceItem->findChild(row);
60 qWarning() << "FlatProxyModel::mapToSource(): couldn't find source index for" << proxyIndex;
62 return QModelIndex(); // make compilers happy :)
65 bool FlatProxyModel::_RangeRect::operator<(const FlatProxyModel::_RangeRect &other) const {
66 if(left != other.left)
67 return left < other.left;
69 if(right != other.right)
70 return right < other.right;
73 return top < other.top;
76 return bottom < other.bottom;
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 ¤tRange = sourceSelection[i];
87 QModelIndex currentParent = currentRange.topLeft().parent();
88 Q_ASSERT(currentParent == currentRange.bottomRight().parent());
90 SourceItem *parentItem = 0;
91 if(!itemLookup.contains(currentParent)) {
92 parentItem = sourceToInternal(currentParent);
93 itemLookup[currentParent] = parentItem;
95 parentItem = itemLookup[currentParent];
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()) };
102 if(newRanges.isEmpty()) {
103 newRanges << newRange;
107 _RangeRect &first = newRanges[0];
108 if(newRange < first) {
109 newRanges.prepend(newRange);
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];
118 if(a < newRange && newRange < b) {
119 newRanges[j + 1] = newRange;
127 _RangeRect &last = newRanges[newRanges.count() - 1];
128 if(last < newRange) {
129 newRanges.append(newRange);
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)
143 if(a.bottom < b.top - 1) {
147 // all merge checks passed!
148 if(b.bottom > a.bottom) {
150 a.bottomItem = b.bottomItem;
151 } // otherwise b is totally enclosed in a -> nothing to do but drop b.
152 newRanges.removeAt(i);
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));
160 return proxySelection;
163 QItemSelection FlatProxyModel::mapSelectionToSource(const QItemSelection &proxySelection) const {
164 QItemSelection sourceSelection;
166 for(int i = 0; i < proxySelection.count(); i++) {
167 const QItemSelectionRange &range = proxySelection[i];
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);
178 topLeftItem = currentItem;
180 if(currentItem->parent() == topLeftItem->parent()) {
181 bottomRightItem = currentItem;
183 Q_ASSERT(topLeftItem && bottomRightItem);
184 sourceSelection << QItemSelectionRange(mapToSource(createIndex(topLeftItem->pos(), left, topLeftItem)), mapToSource(createIndex(bottomRightItem->pos(), right, bottomRightItem)));
190 currentItem = currentItem->next();
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)));
198 return sourceSelection;
201 void FlatProxyModel::setSourceModel(QAbstractItemModel *sourceModel) {
202 if(QAbstractProxyModel::sourceModel()) {
203 disconnect(QAbstractProxyModel::sourceModel(), 0, this, 0);
206 QAbstractProxyModel::setSourceModel(sourceModel);
208 emit layoutAboutToBeChanged();
209 removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
210 insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
211 emit layoutChanged();
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)));
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)
227 connect(sourceModel, SIGNAL(layoutAboutToBeChanged()),
228 this, SLOT(on_layoutAboutToBeChanged()));
229 connect(sourceModel, SIGNAL(layoutChanged()),
230 this, SLOT(on_layoutChanged()));
232 connect(sourceModel, SIGNAL(modelAboutToBeReset()),
233 this, SLOT(on_modelAboutToBeReset()));
234 // void on_modelReset()
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)));
248 void FlatProxyModel::insertSubTree(const QModelIndex &source_idx, bool emitInsert) {
249 SourceItem *newSubTree = new SourceItem(source_idx.row(), sourceToInternal(sourceModel()->parent(source_idx)));
251 if(newSubTree->parent()) {
252 newSubTree->setPos(newSubTree->parent()->pos() + source_idx.row() + 1);
254 SourceItem *lastItem = insertSubTreeHelper(newSubTree, newSubTree, source_idx);
257 Q_ASSERT(lastItem->next() == 0);
260 beginInsertRows(QModelIndex(), newSubTree->pos(), lastItem->pos());
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;
268 next->setPos(nextPos);
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);
278 previous->setNext(newSubTree);
280 newSubTree->parent()->setNext(newSubTree);
283 _rootSourceItem = newSubTree;
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));
302 void FlatProxyModel::removeSubTree(const QModelIndex &source_idx, bool emitRemove) {
303 SourceItem *sourceItem = sourceToInternal(source_idx);
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);
315 SourceItem *lastItem = sourceItem;
316 while(lastItem->childCount() > 0) {
317 lastItem = lastItem->child(lastItem->childCount() - 1);
321 beginRemoveRows(QModelIndex(), sourceItem->pos(), lastItem->pos());
325 prevItem->setNext(lastItem->next());
326 nextPos = prevItem->pos() + 1;
329 SourceItem *nextItem = lastItem->next();
331 nextItem->setPos(nextPos);
333 nextItem = nextItem->next();
336 sourceItem->parent()->removeChild(sourceItem);
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();
349 if(!_rootSourceItem) {
350 qWarning() << "FlatProxyModel::index() while model has no root Item";
351 return QModelIndex();
354 SourceItem *item = _rootSourceItem;
355 while(item->pos() != row) {
356 item = item->findChild(row);
358 qWarning() << "FlatProxyModel::index() no such row:" << row;
359 return QModelIndex();
363 Q_ASSERT(item->pos() == row);
364 return createIndex(row, column, item);
367 QModelIndex FlatProxyModel::parent(const QModelIndex &index) const {
369 // this is a flat model
370 return QModelIndex();
373 int FlatProxyModel::rowCount(const QModelIndex &index) const {
380 SourceItem *item = _rootSourceItem;
381 while(item->childCount() > 0) {
382 item = item->child(item->childCount() - 1);
384 return item->pos() + 1;
387 int FlatProxyModel::columnCount(const QModelIndex &index) const {
392 return sourceModel()->columnCount(QModelIndex());
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());
403 Q_ASSERT(!sourceIndex.isValid() || !childPath.isEmpty());
405 SourceItem *item = _rootSourceItem;
406 for(int i = 0; i < childPath.count(); i++) {
407 item = item->child(childPath[i]);
412 void FlatProxyModel::on_columnsAboutToBeInserted(const QModelIndex &parent, int start, int end) {
414 beginInsertColumns(QModelIndex(), start, end);
417 void FlatProxyModel::on_columnsAboutToBeRemoved(const QModelIndex &parent, int start, int end) {
419 beginRemoveColumns(QModelIndex(), start, end);
422 void FlatProxyModel::on_columnsInserted(const QModelIndex &parent, int start, int end) {
430 void FlatProxyModel::on_columnsRemoved(const QModelIndex &parent, int start, int end) {
437 void FlatProxyModel::on_dataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight) {
438 Q_ASSERT(sourceModel());
439 Q_ASSERT(sourceModel()->parent(topLeft) == sourceModel()->parent(bottomRight));
441 SourceItem *topLeftItem = sourceToInternal(topLeft);
442 Q_ASSERT(topLeftItem);
443 Q_ASSERT(topLeftItem->parent()->childCount() > bottomRight.row());
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);
450 void FlatProxyModel::on_layoutAboutToBeChanged() {
451 emit layoutAboutToBeChanged();
452 removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
455 void FlatProxyModel::on_layoutChanged() {
456 insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
457 emit layoutChanged();
460 void FlatProxyModel::on_rowsAboutToBeInserted(const QModelIndex &parent, int start, int end) {
461 Q_ASSERT(sourceModel());
462 Q_ASSERT(_rootSourceItem);
464 SourceItem *sourceItem = sourceToInternal(parent);
465 Q_ASSERT(sourceItem);
467 beginInsertRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
469 SourceItem *prevItem = sourceItem;
471 prevItem = sourceItem->child(start - 1);
472 while(prevItem->childCount() > 0) {
473 prevItem = prevItem->child(prevItem->childCount() - 1);
478 SourceItem *nextItem = prevItem->next();
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);
486 prevItem->setNext(newItem);
489 prevItem->setNext(nextItem);
492 nextItem->setPos(newPos);
494 nextItem = nextItem->next();
499 void FlatProxyModel::on_rowsAboutToBeRemoved(const QModelIndex &parent, int start, int end) {
500 Q_ASSERT(sourceModel());
501 Q_ASSERT(_rootSourceItem);
503 SourceItem *sourceItem = sourceToInternal(parent);
504 beginRemoveRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
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);
515 void FlatProxyModel::on_rowsInserted(const QModelIndex &parent, int start, int end) {
516 Q_ASSERT(sourceModel());
517 Q_ASSERT(_rootSourceItem);
519 SourceItem *sourceItem = sourceToInternal(parent);
520 Q_ASSERT(sourceItem);
521 Q_UNUSED(sourceItem);
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;
535 void FlatProxyModel::on_rowsRemoved(const QModelIndex &parent, int start, int end) {
536 Q_ASSERT(sourceModel());
537 Q_ASSERT(_rootSourceItem);
539 SourceItem *sourceItem = sourceToInternal(parent);
540 Q_ASSERT(sourceItem);
542 SourceItem *prevItem = sourceItem;
544 prevItem = sourceItem->child(start - 1);
545 while(prevItem->childCount() > 0) {
546 prevItem = prevItem->child(prevItem->childCount() - 1);
551 SourceItem *nextItem = sourceItem->child(end)->next();
553 int newPos = prevItem->pos() + 1;
554 prevItem->setNext(nextItem);
557 nextItem->setPos(newPos);
559 nextItem = nextItem->next();
562 SourceItem *childItem;
563 for(int row = start; row <= end; row++) {
564 childItem = sourceItem->_childs.takeAt(start);
572 void FlatProxyModel::linkTest() const {
573 qDebug() << "Checking FlatProxyModel for linklist integrity";
578 SourceItem *item = _rootSourceItem;
580 qDebug() << item << ":" << item->pos() << "==" << pos;
581 Q_ASSERT(item->pos() == pos);
587 qDebug() << "Last item in linklist:" << item << item->pos();
589 int lastPos = item->pos();
590 item = _rootSourceItem;
591 while(item->childCount() > 0) {
592 item = item->child(item->childCount() - 1);
594 qDebug() << "Last item in tree:" << item << item->pos();
595 Q_ASSERT(lastPos == item->pos());
598 qDebug() << "success!";
601 void FlatProxyModel::completenessTest() const {
602 qDebug() << "Checking FlatProxyModel for Completeness:";
604 checkChildCount(QModelIndex(), _rootSourceItem, pos);
605 qDebug() << "success!";
608 void FlatProxyModel::checkChildCount(const QModelIndex &index, const SourceItem *item, int &pos) const {
612 qDebug() << index << "(Item:" << item << "):" << sourceModel()->rowCount(index) << "==" << item->childCount();
613 qDebug() << "ProxyPos:" << item->pos() << "==" << pos;
614 Q_ASSERT(sourceModel()->rowCount(index) == item->childCount());
616 for(int row = 0; row < sourceModel()->rowCount(index); row++) {
618 checkChildCount(sourceModel()->index(row, 0, index), item->child(row), pos);
622 // ========================================
624 // ========================================
625 FlatProxyModel::SourceItem::SourceItem(int row, SourceItem *parent)
631 parent->_childs.insert(row, this);
635 FlatProxyModel::SourceItem::~SourceItem() {
636 for(int i = 0; i < childCount(); i++) {
642 int FlatProxyModel::SourceItem::sourceRow() const {
646 return parent()->_childs.indexOf(const_cast<FlatProxyModel::SourceItem *>(this));
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());
655 int end = _childs.count() - 1;
657 while(end - start > 1) {
658 pivot = (end + start) / 2;
659 if(_childs[pivot]->pos() > proxyPos)
665 if(_childs[end]->pos() <= proxyPos)
668 return _childs[start];