1 /***************************************************************************
2 * Copyright (C) 2005-2019 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 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *
19 ***************************************************************************/
21 #include "flatproxymodel.h"
24 #include <QItemSelection>
26 FlatProxyModel::FlatProxyModel(QObject* parent)
27 : QAbstractProxyModel(parent)
30 QModelIndex FlatProxyModel::mapFromSource(const QModelIndex& sourceIndex) const
32 if (!sourceIndex.isValid())
35 SourceItem* sourceItem = sourceToInternal(sourceIndex);
37 return createIndex(sourceItem->pos(), sourceIndex.column(), sourceItem);
40 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);
56 sourceParent = sourceModel()->index(sourceItem->sourceRow(), 0, sourceParent);
57 sourceItem = sourceItem->findChild(row);
61 qWarning() << "FlatProxyModel::mapToSource(): couldn't find source index for" << proxyIndex;
63 return {}; // make compilers happy :)
66 bool FlatProxyModel::_RangeRect::operator<(const FlatProxyModel::_RangeRect& other) const
68 if (left != other.left)
69 return left < other.left;
71 if (right != other.right)
72 return right < other.right;
75 return top < other.top;
78 return bottom < other.bottom;
81 QItemSelection FlatProxyModel::mapSelectionFromSource(const QItemSelection& sourceSelection) const
83 QList<_RangeRect> newRanges;
84 QHash<QModelIndex, SourceItem*> itemLookup;
85 // basics steps of the loop:
86 // 1. convert each source ItemSelectionRange to a mapped Range (internal one for easier post processing)
87 // 2. insert it into the list of previously mapped Ranges sorted by top location
88 for (int i = 0; i < sourceSelection.count(); i++) {
89 const QItemSelectionRange& currentRange = sourceSelection[i];
90 QModelIndex currentParent = currentRange.topLeft().parent();
91 Q_ASSERT(currentParent == currentRange.bottomRight().parent());
93 SourceItem* parentItem = nullptr;
94 if (!itemLookup.contains(currentParent)) {
95 parentItem = sourceToInternal(currentParent);
96 itemLookup[currentParent] = parentItem;
99 parentItem = itemLookup[currentParent];
102 _RangeRect newRange = {currentRange.topLeft().column(),
103 currentRange.bottomRight().column(),
104 currentRange.topLeft().row(),
105 currentRange.bottomRight().row(),
106 parentItem->child(currentRange.topLeft().row()),
107 parentItem->child(currentRange.bottomRight().row())};
109 if (newRanges.isEmpty()) {
110 newRanges << newRange;
114 _RangeRect& first = newRanges[0];
115 if (newRange < first) {
116 newRanges.prepend(newRange);
120 bool inserted = false;
121 for (int j = 0; j < newRanges.count() - 1; j++) {
122 _RangeRect& a = newRanges[j];
123 _RangeRect& b = newRanges[j + 1];
125 if (a < newRange && newRange < b) {
126 newRanges[j + 1] = newRange;
134 _RangeRect& last = newRanges[newRanges.count() - 1];
135 if (last < newRange) {
136 newRanges.append(newRange);
143 // we've got a sorted list of ranges now. so we can easily check if there is a possibility to merge
144 for (int i = newRanges.count() - 1; i > 0; i--) {
145 _RangeRect& a = newRanges[i - 1];
146 _RangeRect& b = newRanges[i];
147 if (a.left != b.left || a.right != b.right)
150 if (a.bottom < b.top - 1) {
154 // all merge checks passed!
155 if (b.bottom > a.bottom) {
157 a.bottomItem = b.bottomItem;
158 } // otherwise b is totally enclosed in a -> nothing to do but drop b.
159 newRanges.removeAt(i);
162 QItemSelection proxySelection;
163 for (int i = 0; i < newRanges.count(); i++) {
164 _RangeRect& r = newRanges[i];
165 proxySelection << QItemSelectionRange(createIndex(r.top, r.left, r.topItem), createIndex(r.bottom, r.right, r.bottomItem));
167 return proxySelection;
170 QItemSelection FlatProxyModel::mapSelectionToSource(const QItemSelection& proxySelection) const
172 QItemSelection sourceSelection;
174 for (int i = 0; i < proxySelection.count(); i++) {
175 const QItemSelectionRange& range = proxySelection[i];
177 SourceItem* topLeftItem = nullptr;
178 SourceItem* bottomRightItem = nullptr;
179 auto* currentItem = static_cast<SourceItem*>(range.topLeft().internalPointer());
180 int row = range.topLeft().row();
181 int left = range.topLeft().column();
182 int right = range.bottomRight().column();
183 while (currentItem && row <= range.bottomRight().row()) {
184 Q_ASSERT(currentItem->pos() == row);
186 topLeftItem = currentItem;
188 if (currentItem->parent() == topLeftItem->parent()) {
189 bottomRightItem = currentItem;
192 Q_ASSERT(topLeftItem && bottomRightItem);
193 sourceSelection << QItemSelectionRange(mapToSource(createIndex(topLeftItem->pos(), left, topLeftItem)),
194 mapToSource(createIndex(bottomRightItem->pos(), right, bottomRightItem)));
195 topLeftItem = nullptr;
196 bottomRightItem = nullptr;
200 currentItem = currentItem->next();
204 if (topLeftItem && bottomRightItem) { // there should be one range left.
205 sourceSelection << QItemSelectionRange(mapToSource(createIndex(topLeftItem->pos(), left, topLeftItem)),
206 mapToSource(createIndex(bottomRightItem->pos(), right, bottomRightItem)));
210 return sourceSelection;
213 void FlatProxyModel::setSourceModel(QAbstractItemModel* sourceModel)
215 if (QAbstractProxyModel::sourceModel()) {
216 disconnect(QAbstractProxyModel::sourceModel(), nullptr, this, nullptr);
219 QAbstractProxyModel::setSourceModel(sourceModel);
221 emit layoutAboutToBeChanged();
222 removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
223 insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
224 emit layoutChanged();
227 connect(sourceModel, &QAbstractItemModel::columnsAboutToBeInserted, this, &FlatProxyModel::on_columnsAboutToBeInserted);
228 connect(sourceModel, &QAbstractItemModel::columnsAboutToBeRemoved, this, &FlatProxyModel::on_columnsAboutToBeRemoved);
229 connect(sourceModel, &QAbstractItemModel::columnsInserted, this, &FlatProxyModel::on_columnsInserted);
230 connect(sourceModel, &QAbstractItemModel::columnsRemoved, this, &FlatProxyModel::on_columnsRemoved);
232 connect(sourceModel, &QAbstractItemModel::dataChanged, this, &FlatProxyModel::on_dataChanged);
233 // on_headerDataChanged(Qt::Orientation orientation, int first, int last)
235 connect(sourceModel, &QAbstractItemModel::layoutAboutToBeChanged, this, &FlatProxyModel::on_layoutAboutToBeChanged);
236 connect(sourceModel, &QAbstractItemModel::layoutChanged, this, &FlatProxyModel::on_layoutChanged);
238 connect(sourceModel, &QAbstractItemModel::modelAboutToBeReset, this, &FlatProxyModel::on_modelAboutToBeReset);
239 // void on_modelReset()
241 connect(sourceModel, &QAbstractItemModel::rowsAboutToBeInserted, this, &FlatProxyModel::on_rowsAboutToBeInserted);
242 connect(sourceModel, &QAbstractItemModel::rowsAboutToBeRemoved, this, &FlatProxyModel::on_rowsAboutToBeRemoved);
243 connect(sourceModel, &QAbstractItemModel::rowsInserted, this, &FlatProxyModel::on_rowsInserted);
244 connect(sourceModel, &QAbstractItemModel::rowsRemoved, this, &FlatProxyModel::on_rowsRemoved);
248 void FlatProxyModel::insertSubTree(const QModelIndex& source_idx, bool emitInsert)
250 SourceItem* newSubTree = new SourceItem(source_idx.row(), sourceToInternal(sourceModel()->parent(source_idx)));
252 if (newSubTree->parent()) {
253 newSubTree->setPos(newSubTree->parent()->pos() + source_idx.row() + 1);
255 SourceItem* lastItem = insertSubTreeHelper(newSubTree, newSubTree, source_idx);
258 Q_ASSERT(lastItem->next() == nullptr);
261 beginInsertRows(QModelIndex(), newSubTree->pos(), lastItem->pos());
263 if (newSubTree->parent()) {
264 if (newSubTree->parent()->childCount() > source_idx.row()) {
265 SourceItem* next = newSubTree->parent()->child(source_idx.row());
266 lastItem->setNext(next);
267 int nextPos = lastItem->pos() + 1;
269 next->setPos(nextPos);
274 if (source_idx.row() > 0) {
275 SourceItem* previous = newSubTree->parent()->child(source_idx.row() - 1);
276 while (previous->childCount() > 0) {
277 previous = previous->child(previous->childCount() - 1);
279 previous->setNext(newSubTree);
282 newSubTree->parent()->setNext(newSubTree);
286 _rootSourceItem = newSubTree;
293 FlatProxyModel::SourceItem* FlatProxyModel::insertSubTreeHelper(SourceItem* parentItem, SourceItem* lastItem_, const QModelIndex& source_idx)
295 SourceItem* lastItem = lastItem_;
296 SourceItem* newItem = nullptr;
297 for (int row = 0; row < sourceModel()->rowCount(source_idx); row++) {
298 newItem = new SourceItem(row, parentItem);
299 newItem->setPos(lastItem->pos() + 1);
300 lastItem->setNext(newItem);
301 lastItem = insertSubTreeHelper(newItem, newItem, sourceModel()->index(row, 0, source_idx));
306 void FlatProxyModel::removeSubTree(const QModelIndex& source_idx, bool emitRemove)
308 SourceItem* sourceItem = sourceToInternal(source_idx);
312 SourceItem* prevItem = sourceItem->parent();
313 if (sourceItem->sourceRow() > 0) {
314 prevItem = prevItem->child(sourceItem->sourceRow() - 1);
315 while (prevItem->childCount() > 0) {
316 prevItem = prevItem->child(prevItem->childCount() - 1);
320 SourceItem* lastItem = sourceItem;
321 while (lastItem->childCount() > 0) {
322 lastItem = lastItem->child(lastItem->childCount() - 1);
326 beginRemoveRows(QModelIndex(), sourceItem->pos(), lastItem->pos());
330 prevItem->setNext(lastItem->next());
331 nextPos = prevItem->pos() + 1;
334 SourceItem* nextItem = lastItem->next();
336 nextItem->setPos(nextPos);
338 nextItem = nextItem->next();
341 sourceItem->parent()->removeChild(sourceItem);
348 QModelIndex FlatProxyModel::index(int row, int column, const QModelIndex& parent) const
350 if (parent.isValid()) {
351 qWarning() << "FlatProxyModel::index() called with valid parent:" << parent;
355 if (!_rootSourceItem) {
356 qWarning() << "FlatProxyModel::index() while model has no root Item";
360 SourceItem* item = _rootSourceItem;
361 while (item->pos() != row) {
362 item = item->findChild(row);
364 qWarning() << "FlatProxyModel::index() no such row:" << row;
369 Q_ASSERT(item->pos() == row);
370 return createIndex(row, column, item);
373 QModelIndex FlatProxyModel::parent(const QModelIndex& index) const
376 // this is a flat model
380 int FlatProxyModel::rowCount(const QModelIndex& index) const
382 if (!_rootSourceItem)
388 SourceItem* item = _rootSourceItem;
389 while (item->childCount() > 0) {
390 item = item->child(item->childCount() - 1);
392 return item->pos() + 1;
395 int FlatProxyModel::columnCount(const QModelIndex& index) const
398 if (!sourceModel()) {
402 return sourceModel()->columnCount(QModelIndex());
406 FlatProxyModel::SourceItem* FlatProxyModel::sourceToInternal(const QModelIndex& sourceIndex) const
408 QList<int> childPath;
409 for (QModelIndex idx = sourceIndex; idx.isValid(); idx = sourceModel()->parent(idx)) {
410 childPath.prepend(idx.row());
413 Q_ASSERT(!sourceIndex.isValid() || !childPath.isEmpty());
415 SourceItem* item = _rootSourceItem;
416 for (int i = 0; i < childPath.count(); i++) {
417 item = item->child(childPath[i]);
422 void FlatProxyModel::on_columnsAboutToBeInserted(const QModelIndex& parent, int start, int end)
425 beginInsertColumns(QModelIndex(), start, end);
428 void FlatProxyModel::on_columnsAboutToBeRemoved(const QModelIndex& parent, int start, int end)
431 beginRemoveColumns(QModelIndex(), start, end);
434 void FlatProxyModel::on_columnsInserted(const QModelIndex& parent, int start, int end)
442 void FlatProxyModel::on_columnsRemoved(const QModelIndex& parent, int start, int end)
450 void FlatProxyModel::on_dataChanged(const QModelIndex& topLeft, const QModelIndex& bottomRight)
452 Q_ASSERT(sourceModel());
453 Q_ASSERT(sourceModel()->parent(topLeft) == sourceModel()->parent(bottomRight));
455 SourceItem* topLeftItem = sourceToInternal(topLeft);
456 Q_ASSERT(topLeftItem);
457 Q_ASSERT(topLeftItem->parent()->childCount() > bottomRight.row());
459 QModelIndex proxyTopLeft = createIndex(topLeftItem->pos(), topLeft.column(), topLeftItem);
460 QModelIndex proxyBottomRight = createIndex(topLeftItem->pos() + bottomRight.row() - topLeft.row(),
461 bottomRight.column(),
462 topLeftItem->parent()->child(bottomRight.row()));
463 emit dataChanged(proxyTopLeft, proxyBottomRight);
466 void FlatProxyModel::on_layoutAboutToBeChanged()
468 emit layoutAboutToBeChanged();
469 removeSubTree(QModelIndex(), false /* don't emit removeRows() */);
472 void FlatProxyModel::on_layoutChanged()
474 insertSubTree(QModelIndex(), false /* don't emit insertRows() */);
475 emit layoutChanged();
478 void FlatProxyModel::on_rowsAboutToBeInserted(const QModelIndex& parent, int start, int end)
480 Q_ASSERT(sourceModel());
481 Q_ASSERT(_rootSourceItem);
483 SourceItem* sourceItem = sourceToInternal(parent);
484 Q_ASSERT(sourceItem);
486 beginInsertRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
488 SourceItem* prevItem = sourceItem;
490 prevItem = sourceItem->child(start - 1);
491 while (prevItem->childCount() > 0) {
492 prevItem = prevItem->child(prevItem->childCount() - 1);
497 SourceItem* nextItem = prevItem->next();
499 SourceItem* newItem = nullptr;
500 int newPos = prevItem->pos() + 1;
501 for (int row = start; row <= end; row++) {
502 newItem = new SourceItem(row, sourceItem);
503 newItem->setPos(newPos);
505 prevItem->setNext(newItem);
508 prevItem->setNext(nextItem);
511 nextItem->setPos(newPos);
513 nextItem = nextItem->next();
517 void FlatProxyModel::on_rowsAboutToBeRemoved(const QModelIndex& parent, int start, int end)
519 Q_ASSERT(sourceModel());
520 Q_ASSERT(_rootSourceItem);
522 SourceItem* sourceItem = sourceToInternal(parent);
523 beginRemoveRows(QModelIndex(), sourceItem->pos() + start + 1, sourceItem->pos() + end + 1);
525 // sanity check - if that check fails our indexes would be messed up
526 for (int row = start; row <= end; row++) {
527 if (sourceItem->child(row)->childCount() > 0) {
528 qWarning() << "on_rowsAboutToBeRemoved(): sourceModel() removed rows which have children on their own!"
529 << sourceModel()->index(row, 0, parent);
535 void FlatProxyModel::on_rowsInserted(const QModelIndex& parent, int start, int end)
537 Q_ASSERT(sourceModel());
538 Q_ASSERT(_rootSourceItem);
540 SourceItem* sourceItem = sourceToInternal(parent);
541 Q_ASSERT(sourceItem);
542 Q_UNUSED(sourceItem);
544 // sanity check - if that check fails our indexes would be messed up
545 for (int row = start; row <= end; row++) {
546 QModelIndex child = sourceModel()->index(row, 0, parent);
547 if (sourceModel()->rowCount(child) > 0) {
548 qWarning() << "on_rowsInserted(): sourceModel() inserted rows which already have children on their own!" << child;
556 void FlatProxyModel::on_rowsRemoved(const QModelIndex& parent, int start, int end)
558 Q_ASSERT(sourceModel());
559 Q_ASSERT(_rootSourceItem);
561 SourceItem* sourceItem = sourceToInternal(parent);
562 Q_ASSERT(sourceItem);
564 SourceItem* prevItem = sourceItem;
566 prevItem = sourceItem->child(start - 1);
567 while (prevItem->childCount() > 0) {
568 prevItem = prevItem->child(prevItem->childCount() - 1);
573 SourceItem* nextItem = sourceItem->child(end)->next();
575 int newPos = prevItem->pos() + 1;
576 prevItem->setNext(nextItem);
579 nextItem->setPos(newPos);
581 nextItem = nextItem->next();
584 SourceItem* childItem;
585 for (int row = start; row <= end; row++) {
586 childItem = sourceItem->_childs.takeAt(start);
594 void FlatProxyModel::linkTest() const
596 qDebug() << "Checking FlatProxyModel for linklist integrity";
597 if (!_rootSourceItem)
601 SourceItem* item = _rootSourceItem;
603 qDebug() << item << ":" << item->pos() << "==" << pos;
604 Q_ASSERT(item->pos() == pos);
610 qDebug() << "Last item in linklist:" << item << item->pos();
612 int lastPos = item->pos();
613 item = _rootSourceItem;
614 while (item->childCount() > 0) {
615 item = item->child(item->childCount() - 1);
617 qDebug() << "Last item in tree:" << item << item->pos();
618 Q_ASSERT(lastPos == item->pos());
621 qDebug() << "success!";
624 void FlatProxyModel::completenessTest() const
626 qDebug() << "Checking FlatProxyModel for Completeness:";
628 checkChildCount(QModelIndex(), _rootSourceItem, pos);
629 qDebug() << "success!";
632 void FlatProxyModel::checkChildCount(const QModelIndex& index, const SourceItem* item, int& pos) const
637 qDebug() << index << "(Item:" << item << "):" << sourceModel()->rowCount(index) << "==" << item->childCount();
638 qDebug() << "ProxyPos:" << item->pos() << "==" << pos;
639 Q_ASSERT(sourceModel()->rowCount(index) == item->childCount());
641 for (int row = 0; row < sourceModel()->rowCount(index); row++) {
643 checkChildCount(sourceModel()->index(row, 0, index), item->child(row), pos);
647 // ========================================
649 // ========================================
650 FlatProxyModel::SourceItem::SourceItem(int row, SourceItem* parent)
654 parent->_childs.insert(row, this);
658 FlatProxyModel::SourceItem::~SourceItem()
660 for (int i = 0; i < childCount(); i++) {
666 int FlatProxyModel::SourceItem::sourceRow() const
671 return parent()->_childs.indexOf(const_cast<FlatProxyModel::SourceItem*>(this));
674 FlatProxyModel::SourceItem* FlatProxyModel::SourceItem::findChild(int proxyPos) const
676 Q_ASSERT(proxyPos > pos());
677 Q_ASSERT(_childs.count() > 0);
678 Q_ASSERT(proxyPos >= _childs[0]->pos());
681 int end = _childs.count() - 1;
683 while (end - start > 1) {
684 pivot = (end + start) / 2;
685 if (_childs[pivot]->pos() > proxyPos)
691 if (_childs[end]->pos() <= proxyPos)
694 return _childs[start];