Span update after row and column insertion and removal in QTableView.

The feature had not been implemented yet. Auto-test and benchmark included.
As a bonus, single cell spans are no longer added to the span collection.

Reviewed-by: Thierry
Task-number: 245327
Task-number: QTBUG-3610

3 files changed, 426 insertions, 3 deletions

diff --git a/src/gui/itemviews/qtableview.cpp b/src/gui/itemviews/qtableview.cpp
index f1ffaa6..15bd445 100644
--- a/src/gui/itemviews/qtableview.cpp
+++ b/src/gui/itemviews/qtableview.cpp
@@ -191,6 +191,359 @@ QList<QSpanCollection::Span *> QSpanCollection::spansInRect(int x, int y, int w,
     return list.toList();
 }
 
+#undef DEBUG_SPAN_UPDATE
+
+#ifdef DEBUG_SPAN_UPDATE
+QDebug operator<<(QDebug str, const QSpanCollection::Span &span)
+{
+    str << "(" << span.top() << "," << span.left() << "," << span.bottom() << "," << span.right() << ")";
+    return str;
+}
+#endif
+
+/** \internal
+* Updates the span collection after row insertion.
+*/
+void QSpanCollection::updateInsertedRows(int start, int end)
+{
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << Q_FUNC_INFO;
+    qDebug() << start << end;
+    qDebug() << index;
+#endif
+    if (spans.isEmpty())
+        return;
+
+    int delta = end - start + 1;
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("Before");
+#endif
+    for (SpanList::iterator it = spans.begin(); it != spans.end(); ++it) {
+        Span *span = *it;
+#ifdef DEBUG_SPAN_UPDATE
+        qDebug() << span << *span;
+#endif
+        if (span->m_bottom < start)
+            continue;
+        if (span->m_top >= start)
+            span->m_top += delta;
+        span->m_bottom += delta;
+    }
+
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("After");
+    foreach (QSpanCollection::Span *span, spans)
+        qDebug() << span << *span;
+#endif
+
+    for (Index::iterator it_y = index.begin(); it_y != index.end(); ) {
+        int y = -it_y.key();
+        if (y < start) {
+            ++it_y;
+            continue;
+        }
+
+        index.insert(-y - delta, it_y.value());
+        it_y = index.erase(it_y);
+    }
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << index;
+#endif
+}
+
+/** \internal
+* Updates the span collection after column insertion.
+*/
+void QSpanCollection::updateInsertedColumns(int start, int end)
+{
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << Q_FUNC_INFO;
+    qDebug() << start << end;
+    qDebug() << index;
+#endif
+    if (spans.isEmpty())
+        return;
+
+    int delta = end - start + 1;
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("Before");
+#endif
+    for (SpanList::iterator it = spans.begin(); it != spans.end(); ++it) {
+        Span *span = *it;
+#ifdef DEBUG_SPAN_UPDATE
+        qDebug() << span << *span;
+#endif
+        if (span->m_right < start)
+            continue;
+        if (span->m_left >= start)
+            span->m_left += delta;
+        span->m_right += delta;
+    }
+
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("After");
+    foreach (QSpanCollection::Span *span, spans)
+        qDebug() << span << *span;
+#endif
+
+    for (Index::iterator it_y = index.begin(); it_y != index.end(); ++it_y) {
+        SubIndex &subindex = it_y.value();
+        for (SubIndex::iterator it = subindex.begin(); it != subindex.end(); ) {
+            int x = -it.key();
+            if (x < start) {
+                ++it;
+                continue;
+            }
+            subindex.insert(-x - delta, it.value());
+            it = subindex.erase(it);
+        }
+    }
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << index;
+#endif
+}
+
+/** \internal
+* Cleans a subindex from to be deleted spans. The update argument is used
+* to move the spans inside the subindex, in case their anchor changed.
+* \return true if no span in this subindex starts at y, and should thus be deleted.
+*/
+bool QSpanCollection::cleanSpanSubIndex(QSpanCollection::SubIndex &subindex, int y, bool update)
+{
+    if (subindex.isEmpty())
+        return true;
+
+    bool should_be_deleted = true;
+    SubIndex::iterator it = subindex.end();
+    do {
+        --it;
+        int x = -it.key();
+        Span *span = it.value();
+        if (span->will_be_deleted) {
+            it = subindex.erase(it);
+            continue;
+        }
+        if (update && span->m_left != x) {
+            subindex.insert(-span->m_left, span);
+            it = subindex.erase(it);
+        }
+        if (should_be_deleted && span->m_top == y)
+            should_be_deleted = false;
+    } while (it != subindex.begin());
+
+    return should_be_deleted;
+}
+
+/** \internal
+* Updates the span collection after row removal.
+*/
+void QSpanCollection::updateRemovedRows(int start, int end)
+{
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << Q_FUNC_INFO;
+    qDebug() << start << end;
+    qDebug() << index;
+#endif
+    if (spans.isEmpty())
+        return;
+
+    SpanList spansToBeDeleted;
+    int delta = end - start + 1;
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("Before");
+#endif
+    for (SpanList::iterator it = spans.begin(); it != spans.end(); ) {
+        Span *span = *it;
+#ifdef DEBUG_SPAN_UPDATE
+        qDebug() << span << *span;
+#endif
+        if (span->m_bottom < start) {
+            ++it;
+            continue;
+        }
+        if (span->m_top < start) {
+            if (span->m_bottom <= end)
+                span->m_bottom = start - 1;
+            else
+                span->m_bottom -= delta;
+        } else {
+            if (span->m_bottom > end) {
+                if (span->m_top <= end)
+                    span->m_top = start;
+                else
+                    span->m_top -= delta;
+                span->m_bottom -= delta;
+            } else {
+                span->will_be_deleted = true;
+            }
+        }
+        if (span->m_top == span->m_bottom && span->m_left == span->m_right)
+            span->will_be_deleted = true;
+        if (span->will_be_deleted) {
+            spansToBeDeleted.append(span);
+            it = spans.erase(it);
+        } else {
+            ++it;
+        }
+    }
+
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("After");
+    foreach (QSpanCollection::Span *span, spans)
+        qDebug() << span << *span;
+#endif
+    if (spans.isEmpty()) {
+        qDeleteAll(spansToBeDeleted);
+        index.clear();
+        return;
+    }
+
+    Index::iterator it_y = index.end();
+    do {
+        --it_y;
+        int y = -it_y.key();
+        SubIndex &subindex = it_y.value();
+        if (y < start) {
+            if (cleanSpanSubIndex(subindex, y))
+                it_y = index.erase(it_y);
+        } else if (y >= start && y <= end) {
+            bool span_at_start = false;
+            SubIndex spansToBeMoved;
+            for (SubIndex::iterator it = subindex.begin(); it != subindex.end(); ++it) {
+                Span *span = it.value();
+                if (span->will_be_deleted)
+                    continue;
+                if (!span_at_start && span->m_top == start)
+                    span_at_start = true;
+                spansToBeMoved.insert(it.key(), span);
+            }
+
+            if (y == start && span_at_start)
+                subindex.clear();
+            else
+                it_y = index.erase(it_y);
+
+            if (span_at_start) {
+                Index::iterator it_start;
+                if (y == start)
+                    it_start = it_y;
+                else {
+                    it_start = index.find(-start);
+                    if (it_start == index.end())
+                        it_start = index.insert(-start, SubIndex());
+                }
+                SubIndex &start_subindex = it_start.value();
+                for (SubIndex::iterator it = spansToBeMoved.begin(); it != spansToBeMoved.end(); ++it)
+                    start_subindex.insert(it.key(), it.value());
+            }
+        } else {
+            if (y == end + 1) {
+                Index::iterator it_top = index.find(-y + delta);
+                if (it_top == index.end())
+                    it_top = index.insert(-y + delta, SubIndex());
+                for (SubIndex::iterator it = subindex.begin(); it != subindex.end(); ) {
+                    Span *span = it.value();
+                    if (!span->will_be_deleted)
+                        it_top.value().insert(it.key(), span);
+                    ++it;
+                }
+            } else {
+                index.insert(-y + delta, subindex);
+            }
+            it_y = index.erase(it_y);
+        }
+    } while (it_y != index.begin());
+
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << index;
+    qDebug("Deleted");
+    foreach (QSpanCollection::Span *span, spansToBeDeleted)
+        qDebug() << span << *span;
+#endif
+    qDeleteAll(spansToBeDeleted);
+}
+
+/** \internal
+* Updates the span collection after column removal.
+*/
+void QSpanCollection::updateRemovedColumns(int start, int end)
+{
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << Q_FUNC_INFO;
+    qDebug() << start << end;
+    qDebug() << index;
+#endif
+    if (spans.isEmpty())
+        return;
+
+    SpanList toBeDeleted;
+    int delta = end - start + 1;
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("Before");
+#endif
+    for (SpanList::iterator it = spans.begin(); it != spans.end(); ) {
+        Span *span = *it;
+#ifdef DEBUG_SPAN_UPDATE
+        qDebug() << span << *span;
+#endif
+        if (span->m_right < start) {
+            ++it;
+            continue;
+        }
+        if (span->m_left < start) {
+            if (span->m_right <= end)
+                span->m_right = start - 1;
+            else
+                span->m_right -= delta;
+        } else {
+            if (span->m_right > end) {
+                if (span->m_left <= end)
+                    span->m_left = start;
+                else
+                    span->m_left -= delta;
+                span->m_right -= delta;
+            } else {
+                span->will_be_deleted = true;
+            }
+        }
+        if (span->m_top == span->m_bottom && span->m_left == span->m_right)
+            span->will_be_deleted = true;
+        if (span->will_be_deleted) {
+            toBeDeleted.append(span);
+            it = spans.erase(it);
+        } else {
+            ++it;
+        }
+    }
+
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug("After");
+    foreach (QSpanCollection::Span *span, spans)
+        qDebug() << span << *span;
+#endif
+    if (spans.isEmpty()) {
+        qDeleteAll(toBeDeleted);
+        index.clear();
+        return;
+    }
+
+    for (Index::iterator it_y = index.begin(); it_y != index.end(); ) {
+        int y = -it_y.key();
+        if (cleanSpanSubIndex(it_y.value(), y, true))
+            it_y = index.erase(it_y);
+        else
+            ++it_y;
+    }
+
+#ifdef DEBUG_SPAN_UPDATE
+    qDebug() << index;
+    qDebug("Deleted");
+    foreach (QSpanCollection::Span *span, toBeDeleted)
+        qDebug() << span << *span;
+#endif
+    qDeleteAll(toBeDeleted);
+}
+
 class QTableCornerButton : public QAbstractButton
 {
     Q_OBJECT
@@ -299,6 +652,9 @@ void QTableViewPrivate::setSpan(int row, int column, int rowSpan, int columnSpan
         sp->m_right = column + columnSpan - 1;
         spans.updateSpan(sp, old_height);
         return;
+    } else if (rowSpan == 1 && columnSpan == 1) {
+        qWarning() << "QTableView::setSpan: single cell span won't be added";
+        return;
     }
     sp = new QSpanCollection::Span(row, column, rowSpan, columnSpan);
     spans.addSpan(sp);
@@ -460,6 +816,46 @@ void QTableViewPrivate::drawAndClipSpans(const QRegion &area, QPainter *painter,
 
 /*!
   \internal
+  Updates spans after row insertion.
+*/
+void QTableViewPrivate::_q_updateSpanInsertedRows(const QModelIndex &parent, int start, int end)
+{
+    Q_UNUSED(parent)
+    spans.updateInsertedRows(start, end);
+}
+
+/*!
+  \internal
+  Updates spans after column insertion.
+*/
+void QTableViewPrivate::_q_updateSpanInsertedColumns(const QModelIndex &parent, int start, int end)
+{
+    Q_UNUSED(parent)
+    spans.updateInsertedColumns(start, end);
+}
+
+/*!
+  \internal
+  Updates spans after row removal.
+*/
+void QTableViewPrivate::_q_updateSpanRemovedRows(const QModelIndex &parent, int start, int end)
+{
+    Q_UNUSED(parent)
+    spans.updateRemovedRows(start, end);
+}
+
+/*!
+  \internal
+  Updates spans after column removal.
+*/
+void QTableViewPrivate::_q_updateSpanRemovedColumns(const QModelIndex &parent, int start, int end)
+{
+    Q_UNUSED(parent)
+    spans.updateRemovedColumns(start, end);
+}
+
+/*!
+  \internal
   Draws a table cell.
 */
 void QTableViewPrivate::drawCell(QPainter *painter, const QStyleOptionViewItemV4 &option, const QModelIndex &index)
@@ -629,6 +1025,14 @@ QTableView::~QTableView()
 void QTableView::setModel(QAbstractItemModel *model)
 {
     Q_D(QTableView);
+    connect(model, SIGNAL(rowsInserted(QModelIndex,int,int)),
+            this, SLOT(_q_updateSpanInsertedRows(QModelIndex,int,int)));
+    connect(model, SIGNAL(columnsInserted(QModelIndex,int,int)),
+            this, SLOT(_q_updateSpanInsertedColumns(QModelIndex,int,int)));
+    connect(model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
+            this, SLOT(_q_updateSpanRemovedRows(QModelIndex,int,int)));
+    connect(model, SIGNAL(columnsRemoved(QModelIndex,int,int)),
+            this, SLOT(_q_updateSpanRemovedColumns(QModelIndex,int,int)));
     d->verticalHeader->setModel(model);
     d->horizontalHeader->setModel(model);
     QAbstractItemView::setModel(model);
diff --git a/src/gui/itemviews/qtableview.h b/src/gui/itemviews/qtableview.h
index a08d6a9..541c419 100644
--- a/src/gui/itemviews/qtableview.h
+++ b/src/gui/itemviews/qtableview.h
@@ -182,6 +182,10 @@ private:
     Q_DISABLE_COPY(QTableView)
     Q_PRIVATE_SLOT(d_func(), void _q_selectRow(int))
     Q_PRIVATE_SLOT(d_func(), void _q_selectColumn(int))
+    Q_PRIVATE_SLOT(d_func(), void _q_updateSpanInsertedRows(QModelIndex,int,int))
+    Q_PRIVATE_SLOT(d_func(), void _q_updateSpanInsertedColumns(QModelIndex,int,int))
+    Q_PRIVATE_SLOT(d_func(), void _q_updateSpanRemovedRows(QModelIndex,int,int))
+    Q_PRIVATE_SLOT(d_func(), void _q_updateSpanRemovedColumns(QModelIndex,int,int))
 };
 
 #endif // QT_NO_TABLEVIEW
diff --git a/src/gui/itemviews/qtableview_p.h b/src/gui/itemviews/qtableview_p.h
index 36a3ece..c785bd7 100644
--- a/src/gui/itemviews/qtableview_p.h
+++ b/src/gui/itemviews/qtableview_p.h
@@ -54,6 +54,7 @@
 //
 
 #include <QtCore/QList>
+#include <QtCore/QLinkedList>
 #include <QtCore/QMap>
 #include <QtCore/QSet>
 #include <QtCore/QDebug>
@@ -82,10 +83,11 @@ public:
         int m_left;
         int m_bottom;
         int m_right;
+        bool will_be_deleted;
         Span()
-        : m_top(-1), m_left(-1), m_bottom(-1), m_right(-1) { }
+        : m_top(-1), m_left(-1), m_bottom(-1), m_right(-1), will_be_deleted(false) { }
         Span(int row, int column, int rowCount, int columnCount)
-        : m_top(row), m_left(column), m_bottom(row+rowCount-1), m_right(column+columnCount-1) { }
+        : m_top(row), m_left(column), m_bottom(row+rowCount-1), m_right(column+columnCount-1), will_be_deleted(false) { }
         inline int top() const { return m_top; }
         inline int left() const { return m_left; }
         inline int bottom() const { return m_bottom; }
@@ -105,12 +107,20 @@ public:
     void clear();
     QList<Span *> spansInRect(int x, int y, int w, int h) const;
 
-    QList<Span *> spans; //lists of all spans
+    void updateInsertedRows(int start, int end);
+    void updateInsertedColumns(int start, int end);
+    void updateRemovedRows(int start, int end);
+    void updateRemovedColumns(int start, int end);
+
+    typedef QLinkedList<Span *> SpanList;
+    SpanList spans; //lists of all spans
 private:
     //the indexes are negative so the QMap::lowerBound do what i need.
     typedef QMap<int, Span *> SubIndex;
     typedef QMap<int, SubIndex> Index;
     Index index;
+
+    bool cleanSpanSubIndex(SubIndex &subindex, int end, bool update = false);
 };
 
 Q_DECLARE_TYPEINFO ( QSpanCollection::Span, Q_MOVABLE_TYPE);
@@ -227,6 +237,11 @@ public:
 
     void selectRow(int row, bool anchor);
     void selectColumn(int column, bool anchor);
+
+    void _q_updateSpanInsertedRows(const QModelIndex &parent, int start, int end);
+    void _q_updateSpanInsertedColumns(const QModelIndex &parent, int start, int end);
+    void _q_updateSpanRemovedRows(const QModelIndex &parent, int start, int end);
+    void _q_updateSpanRemovedColumns(const QModelIndex &parent, int start, int end);
 };
 
 QT_END_NAMESPACE