Keep track of empty broadcaster segments, and delete them all in one go.

This massively speeds up the deletion of a large group of adjacent formula
cells. As an example, on machine, deletion of formula cells over B2:B109101
(109100 cells in total) got reduced from 4.7 seconds to 0.09 seconds).

Change-Id: Ib72da42a6644421601111907cf7c899d828c2996

11 files changed, 217 insertions, 1 deletions

diff --git a/sc/Library_sc.mk b/sc/Library_sc.mk
index 79a553d2559a..8c2f8d5dd8df 100644
--- a/sc/Library_sc.mk
+++ b/sc/Library_sc.mk
@@ -95,6 +95,7 @@ $(eval $(call gb_Library_add_exception_objects,sc,\
 	sc/source/core/data/column2 \
 	sc/source/core/data/column3 \
 	sc/source/core/data/columniterator \
+	sc/source/core/data/columnspanset \
 	sc/source/core/data/compressedarray \
 	sc/source/core/data/colorscale \
 	sc/source/core/data/conditio \
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 88950318af23..9ee830b49157 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -474,6 +474,7 @@ public:
 
     SvtBroadcaster* GetBroadcaster( SCROW nRow );
     const SvtBroadcaster* GetBroadcaster( SCROW nRow ) const;
+    void DeleteBroadcasters( SCROW nRow1, SCROW nRow2 );
 
 private:
     void DeleteRange(
diff --git a/sc/inc/columnspanset.hxx b/sc/inc/columnspanset.hxx
new file mode 100644
index 000000000000..afd17977add9
--- /dev/null
+++ b/sc/inc/columnspanset.hxx
@@ -0,0 +1,53 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#ifndef SC_COLUMNSPANSET_HXX
+#define SC_COLUMNSPANSET_HXX
+
+#include "address.hxx"
+
+#include <vector>
+#include <mdds/flat_segment_tree.hpp>
+#include <boost/noncopyable.hpp>
+
+namespace sc {
+
+/**
+ * Structure that stores segments of boolean flags per column, and perform
+ * custom action on those segments.
+ */
+class ColumnSpanSet : boost::noncopyable
+{
+    typedef mdds::flat_segment_tree<SCROW, bool> ColumnSpansType;
+    typedef std::vector<ColumnSpansType*> TableType;
+    typedef std::vector<TableType*> DocType;
+
+    DocType maDoc;
+
+public:
+    class Action
+    {
+    public:
+        virtual ~Action() = 0;
+        virtual void execute(const ScAddress& rPos, SCROW nLength, bool bVal) = 0;
+    };
+
+    ~ColumnSpanSet();
+
+    void set(SCCOL nCol, SCROW nRow, SCTAB nTab, bool bVal);
+
+    void executeFromTop(Action& ac) const;
+    void executeFromBottom(Action& ac) const;
+};
+
+}
+
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index eeec34935a81..0c59a6750cdf 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1958,6 +1958,7 @@ public:
 
     SvtBroadcaster* GetBroadcaster( const ScAddress& rPos );
     const SvtBroadcaster* GetBroadcaster( const ScAddress& rPos ) const;
+    void DeleteBroadcasters( const ScAddress& rTopPos, SCROW nLength );
 
 private: // CLOOK-Impl-methods
 
diff --git a/sc/inc/listenercontext.hxx b/sc/inc/listenercontext.hxx
index 584671342444..2fc55a769821 100644
--- a/sc/inc/listenercontext.hxx
+++ b/sc/inc/listenercontext.hxx
@@ -11,14 +11,18 @@
 #define SC_LISTENERCONTEXT_HXX
 
 #include "address.hxx"
+#include "columnspanset.hxx"
+
+#include <boost/noncopyable.hpp>
 
 class ScDocument;
 
 namespace sc {
 
-class EndListeningContext
+class EndListeningContext : boost::noncopyable
 {
     ScDocument& mrDoc;
+    ColumnSpanSet maSet;
 public:
     EndListeningContext(ScDocument& rDoc);
     ScDocument& getDoc();
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index f805cf43f294..543bdc9861d4 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -834,6 +834,7 @@ public:
 
     SvtBroadcaster* GetBroadcaster( SCCOL nCol, SCROW nRow );
     const SvtBroadcaster* GetBroadcaster( SCCOL nCol, SCROW nRow ) const;
+    void DeleteBroadcasters( SCCOL nCol, SCROW nRow1, SCROW nRow2 );
 
     /** Replace behaves differently to the Search; adjust the rCol and rRow accordingly.
 
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 8b383841e05a..ea0aac3946ce 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1518,6 +1518,11 @@ const SvtBroadcaster* ScColumn::GetBroadcaster(SCROW nRow) const
     return maBroadcasters.get<SvtBroadcaster*>(nRow);
 }
 
+void ScColumn::DeleteBroadcasters( SCROW nRow1, SCROW nRow2 )
+{
+    maBroadcasters.set_empty(nRow1, nRow2);
+}
+
 sal_uInt16 ScColumn::GetTextWidth(SCROW nRow) const
 {
     return maCellTextAttrs.get<sc::CellTextAttr>(nRow).mnTextWidth;
diff --git a/sc/source/core/data/columnspanset.cxx b/sc/source/core/data/columnspanset.cxx
new file mode 100644
index 000000000000..de785395e4c0
--- /dev/null
+++ b/sc/source/core/data/columnspanset.cxx
@@ -0,0 +1,115 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include "columnspanset.hxx"
+#include "stlalgorithm.hxx"
+
+#include <algorithm>
+
+namespace sc {
+
+ColumnSpanSet::Action::~Action() {}
+
+ColumnSpanSet::~ColumnSpanSet()
+{
+    DocType::iterator itTab = maDoc.begin(), itTabEnd = maDoc.end();
+    for (; itTab != itTabEnd; ++itTab)
+    {
+        TableType* pTab = *itTab;
+        if (!pTab)
+            continue;
+
+        std::for_each(pTab->begin(), pTab->end(), ScDeleteObjectByPtr<ColumnSpansType>());
+        delete pTab;
+    }
+}
+
+void ColumnSpanSet::set(SCCOL nCol, SCROW nRow, SCTAB nTab, bool bVal)
+{
+    if (!ValidTab(nTab) || !ValidCol(nCol) || !ValidRow(nRow))
+        return;
+
+    if (static_cast<size_t>(nTab) >= maDoc.size())
+        maDoc.resize(nTab+1, NULL);
+
+    if (!maDoc[nTab])
+        maDoc[nTab] = new TableType;
+
+    TableType& rTab = *maDoc[nTab];
+    if (static_cast<size_t>(nCol) >= rTab.size())
+        rTab.resize(nCol+1, NULL);
+
+    if (!rTab[nCol])
+        rTab[nCol] = new ColumnSpansType(0, MAXROW+1, false);
+
+    ColumnSpansType& rCol = *rTab[nCol];
+    rCol.insert_back(nRow, nRow+1, bVal);
+}
+
+void ColumnSpanSet::executeFromTop(Action& ac) const
+{
+    for (size_t nTab = 0; nTab < maDoc.size(); ++nTab)
+    {
+        if (!maDoc[nTab])
+            continue;
+
+        const TableType& rTab = *maDoc[nTab];
+        for (size_t nCol = 0; nCol < rTab.size(); ++nCol)
+        {
+            if (!rTab[nCol])
+                continue;
+
+            ColumnSpansType& rCol = *rTab[nCol];
+            ColumnSpansType::const_iterator it = rCol.begin(), itEnd = rCol.end();
+            SCROW nRow1, nRow2;
+            nRow1 = it->first;
+            for (++it; it != itEnd; ++it)
+            {
+                nRow2 = it->first-1;
+                bool bVal = it->second;
+                ac.execute(ScAddress(nCol, nRow1, nTab), nRow2-nRow1+1, bVal);
+
+                nRow1 = nRow2+1; // for the next iteration.
+            }
+        }
+    }
+}
+
+void ColumnSpanSet::executeFromBottom(Action& ac) const
+{
+    for (size_t nTab = 0; nTab < maDoc.size(); ++nTab)
+    {
+        if (!maDoc[nTab])
+            continue;
+
+        const TableType& rTab = *maDoc[nTab];
+        for (size_t nCol = 0; nCol < rTab.size(); ++nCol)
+        {
+            if (!rTab[nCol])
+                continue;
+
+            ColumnSpansType& rCol = *rTab[nCol];
+            ColumnSpansType::const_reverse_iterator it = rCol.rbegin(), itEnd = rCol.rend();
+            SCROW nRow1, nRow2;
+            nRow2 = it->first-1;
+            for (++it; it != itEnd; ++it)
+            {
+                nRow1 = it->first;
+                bool bVal = it->second;
+                ac.execute(ScAddress(nCol, nRow1, nTab), nRow2-nRow1+1, bVal);
+
+                nRow2 = nRow1-1; // for the next iteration.
+            }
+        }
+    }
+}
+
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index d0ec99d834f0..e265c917141c 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -2222,6 +2222,14 @@ const SvtBroadcaster* ScDocument::GetBroadcaster( const ScAddress& rPos ) const
     return maTabs[rPos.Tab()]->GetBroadcaster(rPos.Col(), rPos.Row());
 }
 
+void ScDocument::DeleteBroadcasters( const ScAddress& rTopPos, SCROW nLength )
+{
+    if (!TableExists(rTopPos.Tab()) || nLength <= 0)
+        return;
+
+    maTabs[rTopPos.Tab()]->DeleteBroadcasters(rTopPos.Col(), rTopPos.Row(), rTopPos.Row()+nLength-1);
+}
+
 bool ScDocument::TableExists( SCTAB nTab ) const
 {
     return ValidTab(nTab) && static_cast<size_t>(nTab) < maTabs.size() && maTabs[nTab];
diff --git a/sc/source/core/data/listenercontext.cxx b/sc/source/core/data/listenercontext.cxx
index 439f09b8ef9a..4d8afb3ddc08 100644
--- a/sc/source/core/data/listenercontext.cxx
+++ b/sc/source/core/data/listenercontext.cxx
@@ -12,6 +12,22 @@
 
 namespace sc {
 
+namespace {
+
+class PurgeAction : public ColumnSpanSet::Action
+{
+    ScDocument& mrDoc;
+public:
+    PurgeAction(ScDocument& rDoc) : mrDoc(rDoc) {}
+    virtual void execute(const ScAddress& rPos, SCROW nLength, bool bVal)
+    {
+        if (bVal)
+            mrDoc.DeleteBroadcasters(rPos, nLength);
+    };
+};
+
+}
+
 EndListeningContext::EndListeningContext(ScDocument& rDoc) : mrDoc(rDoc) {}
 
 ScDocument& EndListeningContext::getDoc()
@@ -21,10 +37,13 @@ ScDocument& EndListeningContext::getDoc()
 
 void EndListeningContext::addEmptyBroadcasterPosition(SCCOL nCol, SCROW nRow, SCTAB nTab)
 {
+    maSet.set(nCol, nRow, nTab, true);
 }
 
 void EndListeningContext::purgeEmptyBroadcasters()
 {
+    PurgeAction aAction(mrDoc);
+    maSet.executeFromBottom(aAction);
 }
 
 }
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 57315b7ab712..4c50eaf6ddba 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2168,6 +2168,14 @@ SvtBroadcaster* ScTable::GetBroadcaster( SCCOL nCol, SCROW nRow )
     return aCol[nCol].GetBroadcaster(nRow);
 }
 
+void ScTable::DeleteBroadcasters( SCCOL nCol, SCROW nRow1, SCROW nRow2 )
+{
+    if (!ValidCol(nCol))
+        return;
+
+    aCol[nCol].DeleteBroadcasters(nRow1, nRow2);
+}
+
 const SvtBroadcaster* ScTable::GetBroadcaster( SCCOL nCol, SCROW nRow ) const
 {
     if (!ValidColRow(nCol, nRow))