Do the same thing for CopyToDocument.

This removes O(n^2) slowness from undo and redo of a large array of
cells with empty cells in between.

Change-Id: Id87c8ac8986c97ddf305f849a4752f0f92cc5899

5 files changed, 74 insertions, 29 deletions

diff --git a/sc/source/core/data/clipcontext.cxx b/sc/source/core/data/clipcontext.cxx
index 8a02cea1dad2..8777aa3487b7 100644
--- a/sc/source/core/data/clipcontext.cxx
+++ b/sc/source/core/data/clipcontext.cxx
@@ -117,6 +117,9 @@ bool CopyToClipContext::isCloneNotes() const
     return mbCloneNotes;
 }
 
+CopyToDocContext::CopyToDocContext(ScDocument& rDoc) : ClipContextBase(rDoc) {}
+CopyToDocContext::~CopyToDocContext() {}
+
 }
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index 9fb640673d02..d196223d3cc8 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -1368,6 +1368,7 @@ void ScColumn::CopyCellToDocument( SCROW nSrcRow, SCROW nDestRow, ScColumn& rDes
 }
 
 void ScColumn::CopyToColumn(
+    sc::CopyToDocContext& rCxt,
     SCROW nRow1, SCROW nRow2, sal_uInt16 nFlags, bool bMarked, ScColumn& rColumn,
     const ScMarkData* pMarkData, bool bAsLink) const
 {
@@ -1381,7 +1382,7 @@ void ScColumn::CopyToColumn(
             while ( aIter.Next( nStart, nEnd ) && nStart <= nRow2 )
             {
                 if ( nEnd >= nRow1 )
-                    CopyToColumn( std::max(nRow1,nStart), std::min(nRow2,nEnd),
+                    CopyToColumn(rCxt, std::max(nRow1,nStart), std::min(nRow2,nEnd),
                                     nFlags, false, rColumn, pMarkData, bAsLink );
             }
         }
@@ -1443,6 +1444,7 @@ void ScColumn::CopyToColumn(
                     // Special case to allow removing of cell instances.  A
                     // string cell with empty content is used to indicate an
                     // empty cell.
+                    sc::ColumnBlockPosition* p = rCxt.getBlockPosition(nTab, nCol);
                     if (pNew->GetCellType() == CELLTYPE_STRING)
                     {
                         OUString aStr = static_cast<ScStringCell*>(pNew)->GetString();
@@ -1450,11 +1452,21 @@ void ScColumn::CopyToColumn(
                             // A string cell with empty string.  Delete the cell itself.
                             rColumn.Delete(maItems[i].nRow);
                         else
+                        {
                             // non-empty string cell
-                            rColumn.Insert(maItems[i].nRow, pNew);
+                            if (p)
+                                rColumn.Insert(*p, maItems[i].nRow, pNew);
+                            else
+                                rColumn.Insert(maItems[i].nRow, pNew);
+                        }
                     }
                     else
-                        rColumn.Insert(maItems[i].nRow, pNew);
+                    {
+                        if (p)
+                            rColumn.Insert(*p, maItems[i].nRow, pNew);
+                        else
+                            rColumn.Insert(maItems[i].nRow, pNew);
+                    }
                 }
             }
         }
@@ -1466,13 +1478,15 @@ void ScColumn::UndoToColumn(
     SCROW nRow1, SCROW nRow2, sal_uInt16 nFlags, bool bMarked, ScColumn& rColumn,
     const ScMarkData* pMarkData) const
 {
+    sc::CopyToDocContext aCxt(*rColumn.pDocument);
+    aCxt.setTabRange(rColumn.nTab, rColumn.nTab);
     if (nRow1 > 0)
-        CopyToColumn( 0, nRow1-1, IDF_FORMULA, false, rColumn );
+        CopyToColumn(aCxt, 0, nRow1-1, IDF_FORMULA, false, rColumn);
 
-    CopyToColumn( nRow1, nRow2, nFlags, bMarked, rColumn, pMarkData );      //! bMarked ????
+    CopyToColumn(aCxt, nRow1, nRow2, nFlags, bMarked, rColumn, pMarkData);      //! bMarked ????
 
     if (nRow2 < MAXROW)
-        CopyToColumn( nRow2+1, MAXROW, IDF_FORMULA, false, rColumn );
+        CopyToColumn(aCxt, nRow2+1, MAXROW, IDF_FORMULA, false, rColumn);
 }
 
 
@@ -1501,7 +1515,8 @@ void ScColumn::CopyUpdated( const ScColumn& rPosCol, ScColumn& rDestCol ) const
 void ScColumn::CopyScenarioFrom( const ScColumn& rSrcCol )
 {
     //  This is the scenario table, the data is copied into it
-
+    sc::CopyToDocContext aCxt(*pDocument);
+    aCxt.setTabRange(nTab, nTab);
     ScAttrIterator aAttrIter( pAttrArray, 0, MAXROW );
     SCROW nStart = -1, nEnd = -1;
     const ScPatternAttr* pPattern = aAttrIter.Next( nStart, nEnd );
@@ -1511,7 +1526,7 @@ void ScColumn::CopyScenarioFrom( const ScColumn& rSrcCol )
         {
             DeleteArea( nStart, nEnd, IDF_CONTENTS );
             ((ScColumn&)rSrcCol).
-                CopyToColumn( nStart, nEnd, IDF_CONTENTS, false, *this );
+                CopyToColumn(aCxt, nStart, nEnd, IDF_CONTENTS, false, *this);
 
             //  UpdateUsed not needed, already done in TestCopyScenario (obsolete comment ?)
 
@@ -1532,7 +1547,8 @@ void ScColumn::CopyScenarioFrom( const ScColumn& rSrcCol )
 void ScColumn::CopyScenarioTo( ScColumn& rDestCol ) const
 {
     //  This is the scenario table, the data is copied to the other
-
+    sc::CopyToDocContext aCxt(*rDestCol.pDocument);
+    aCxt.setTabRange(rDestCol.nTab, rDestCol.nTab);
     ScAttrIterator aAttrIter( pAttrArray, 0, MAXROW );
     SCROW nStart = -1, nEnd = -1;
     const ScPatternAttr* pPattern = aAttrIter.Next( nStart, nEnd );
@@ -1542,7 +1558,7 @@ void ScColumn::CopyScenarioTo( ScColumn& rDestCol ) const
         {
             rDestCol.DeleteArea( nStart, nEnd, IDF_CONTENTS );
             ((ScColumn*)this)->
-                CopyToColumn( nStart, nEnd, IDF_CONTENTS, false, rDestCol );
+                CopyToColumn(aCxt, nStart, nEnd, IDF_CONTENTS, false, rDestCol);
 
             //  UpdateUsed not needed, is already done in TestCopyScenario (obsolete comment ?)
 
diff --git a/sc/source/core/data/documen2.cxx b/sc/source/core/data/documen2.cxx
index 5a45fda988f7..0229c52ddeb1 100644
--- a/sc/source/core/data/documen2.cxx
+++ b/sc/source/core/data/documen2.cxx
@@ -86,6 +86,7 @@
 #include "macromgr.hxx"
 #include "cell.hxx"
 #include "formulacell.hxx"
+#include "clipcontext.hxx"
 
 using namespace com::sun::star;
 
@@ -855,8 +856,10 @@ bool ScDocument::CopyTab( SCTAB nOldPos, SCTAB nNewPos, const ScMarkData* pOnlyM
     }
     if (bValid)
     {
+        sc::CopyToDocContext aCxt(*this);
+        aCxt.setTabRange(nNewPos, nNewPos);
         SetNoListening( true );     // noch nicht bei CopyToTable/Insert
-        maTabs[nOldPos]->CopyToTable(0, 0, MAXCOL, MAXROW, IDF_ALL, (pOnlyMarked != NULL),
+        maTabs[nOldPos]->CopyToTable(aCxt, 0, 0, MAXCOL, MAXROW, IDF_ALL, (pOnlyMarked != NULL),
                                         maTabs[nNewPos], pOnlyMarked );
         maTabs[nNewPos]->SetTabBgColor(maTabs[nOldPos]->GetTabBgColor());
 
@@ -961,10 +964,12 @@ sal_uLong ScDocument::TransferTab( ScDocument* pSrcDoc, SCTAB nSrcPos,
         {
             NumFmtMergeHandler aNumFmtMergeHdl(this, pSrcDoc);
 
+            sc::CopyToDocContext aCxt(*this);
+            aCxt.setTabRange(nDestPos, nDestPos);
             nDestPos = std::min(nDestPos, (SCTAB)(GetTableCount() - 1));
             {   // scope for bulk broadcast
                 ScBulkBroadcast aBulkBroadcast( pBASM);
-                pSrcDoc->maTabs[nSrcPos]->CopyToTable(0, 0, MAXCOL, MAXROW,
+                pSrcDoc->maTabs[nSrcPos]->CopyToTable(aCxt, 0, 0, MAXCOL, MAXROW,
                         ( bResultsOnly ? IDF_ALL & ~IDF_FORMULA : IDF_ALL),
                         false, maTabs[nDestPos] );
                 maTabs[nDestPos]->CopyConditionalFormat(0, 0, MAXCOL, MAXROW,
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index 7fb04a95656f..ce3efddfa689 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -1841,13 +1841,15 @@ void ScDocument::CopyToDocument(SCCOL nCol1, SCROW nRow1, SCTAB nTab1,
         pDestDoc->aDocName = aDocName;
     if (ValidTab(nTab1) && ValidTab(nTab2))
     {
+        sc::CopyToDocContext aCxt(*pDestDoc);
+        aCxt.setTabRange(nTab1, nTab2);
         bool bOldAutoCalc = pDestDoc->GetAutoCalc();
         pDestDoc->SetAutoCalc( false );     // avoid multiple calculations
         SCTAB nMinSizeBothTabs = static_cast<SCTAB>(std::min(maTabs.size(), pDestDoc->maTabs.size()));
         for (SCTAB i = nTab1; i <= nTab2 && i < nMinSizeBothTabs; i++)
         {
             if (maTabs[i] && pDestDoc->maTabs[i])
-                maTabs[i]->CopyToTable( nCol1, nRow1, nCol2, nRow2, nFlags,
+                maTabs[i]->CopyToTable(aCxt, nCol1, nRow1, nCol2, nRow2, nFlags,
                                       bOnlyMarked, pDestDoc->maTabs[i], pMarks,
                                       false, bColRowFlags );
         }
@@ -1897,13 +1899,19 @@ void ScDocument::CopyToDocument(const ScRange& rRange,
         pDestDoc->aDocName = aDocName;
     bool bOldAutoCalc = pDestDoc->GetAutoCalc();
     pDestDoc->SetAutoCalc( false );     // avoid multiple calculations
+    sc::CopyToDocContext aCxt(*pDestDoc);
+    aCxt.setTabRange(aNewRange.aStart.Tab(), aNewRange.aEnd.Tab());
     SCTAB nMinSizeBothTabs = static_cast<SCTAB>(std::min(maTabs.size(), pDestDoc->maTabs.size()));
     for (SCTAB i = aNewRange.aStart.Tab(); i <= aNewRange.aEnd.Tab() && i < nMinSizeBothTabs; i++)
-        if (maTabs[i] && pDestDoc->maTabs[i])
-            maTabs[i]->CopyToTable(aNewRange.aStart.Col(), aNewRange.aStart.Row(),
-                                 aNewRange.aEnd.Col(), aNewRange.aEnd.Row(),
-                                 nFlags, bOnlyMarked, pDestDoc->maTabs[i],
-                                 pMarks, false, bColRowFlags);
+    {
+        if (!TableExists(i) || !pDestDoc->TableExists(i))
+            continue;
+
+        maTabs[i]->CopyToTable(aCxt, aNewRange.aStart.Col(), aNewRange.aStart.Row(),
+                               aNewRange.aEnd.Col(), aNewRange.aEnd.Row(),
+                               nFlags, bOnlyMarked, pDestDoc->maTabs[i],
+                               pMarks, false, bColRowFlags);
+    }
     pDestDoc->SetAutoCalc( bOldAutoCalc );
 }
 
@@ -2867,6 +2875,8 @@ void ScDocument::FillTab( const ScRange& rSrcArea, const ScMarkData& rMark,
         bool bOldAutoCalc = GetAutoCalc();
         SetAutoCalc( false );                   // avoid multiple calculations
 
+        sc::CopyToDocContext aCxt(*this);
+        aCxt.setTabRange(rMark.GetFirstSelected(), rMark.GetLastSelected());
         SCTAB nCount = static_cast<SCTAB>(maTabs.size());
         ScMarkData::const_iterator itr = rMark.begin(), itrEnd = rMark.end();
         for (; itr != itrEnd && *itr < nCount; ++itr)
@@ -2882,11 +2892,13 @@ void ScDocument::FillTab( const ScRange& rSrcArea, const ScMarkData& rMark,
                     }
                     else
                         pMixDoc->AddUndoTab( i, i );
-                    maTabs[i]->CopyToTable( nStartCol,nStartRow, nEndCol,nEndRow,
+                    sc::CopyToDocContext aMixCxt(*pMixDoc);
+                    aMixCxt.setTabRange(i, i);
+                    maTabs[i]->CopyToTable(aMixCxt, nStartCol,nStartRow, nEndCol,nEndRow,
                                             IDF_CONTENTS, false, pMixDoc->maTabs[i] );
                 }
                 maTabs[i]->DeleteArea( nStartCol,nStartRow, nEndCol,nEndRow, nDelFlags);
-                maTabs[nSrcTab]->CopyToTable( nStartCol,nStartRow, nEndCol,nEndRow,
+                maTabs[nSrcTab]->CopyToTable(aCxt, nStartCol,nStartRow, nEndCol,nEndRow,
                                                  nFlags, false, maTabs[i], NULL, bAsLink );
 
                 if (bDoMix)
@@ -2928,6 +2940,8 @@ void ScDocument::FillTabMarked( SCTAB nSrcTab, const ScMarkData& rMark,
         SCCOL nEndCol = aArea.aEnd.Col();
         SCROW nEndRow = aArea.aEnd.Row();
 
+        sc::CopyToDocContext aCxt(*this);
+        aCxt.setTabRange(rMark.GetFirstSelected(), rMark.GetLastSelected());
         SCTAB nCount = static_cast<SCTAB>(maTabs.size());
         ScMarkData::const_iterator itr = rMark.begin(), itrEnd = rMark.end();
         for (; itr != itrEnd && *itr < nCount; ++itr)
@@ -2943,12 +2957,15 @@ void ScDocument::FillTabMarked( SCTAB nSrcTab, const ScMarkData& rMark,
                     }
                     else
                         pMixDoc->AddUndoTab( i, i );
-                    maTabs[i]->CopyToTable( nStartCol,nStartRow, nEndCol,nEndRow,
+
+                    sc::CopyToDocContext aMixCxt(*pMixDoc);
+                    aMixCxt.setTabRange(i, i);
+                    maTabs[i]->CopyToTable(aMixCxt, nStartCol,nStartRow, nEndCol,nEndRow,
                                             IDF_CONTENTS, true, pMixDoc->maTabs[i], &rMark );
                 }
 
                 maTabs[i]->DeleteSelection( nDelFlags, rMark );
-                maTabs[nSrcTab]->CopyToTable( nStartCol,nStartRow, nEndCol,nEndRow,
+                maTabs[nSrcTab]->CopyToTable(aCxt, nStartCol,nStartRow, nEndCol,nEndRow,
                                              nFlags, true, maTabs[i], &rMark, bAsLink );
 
                 if (bDoMix)
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index d1605c7f2c03..1a59fca25df8 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -406,9 +406,11 @@ void ScTable::InsertCol( SCCOL nStartCol, SCROW nStartRow, SCROW nEndRow, SCSIZE
         nWhichArray[1] = ATTR_CONDITIONAL;
         nWhichArray[2] = 0;
 
+        sc::CopyToDocContext aCxt(*pDocument);
+        aCxt.setTabRange(nTab, nTab);
         for (SCSIZE i=0; i<nSize; i++)
         {
-            aCol[nStartCol-1].CopyToColumn( nStartRow, nEndRow, IDF_ATTRIB,
+            aCol[nStartCol-1].CopyToColumn(aCxt, nStartRow, nEndRow, IDF_ATTRIB,
                                                 false, aCol[nStartCol+i] );
             aCol[nStartCol+i].RemoveFlags( nStartRow, nEndRow,
                                                 SC_MF_HOR | SC_MF_VER | SC_MF_AUTO );
@@ -1018,17 +1020,17 @@ void ScTable::StartListeningInArea( SCCOL nCol1, SCROW nRow1,
 }
 
 
-void ScTable::CopyToTable(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
-                            sal_uInt16 nFlags, bool bMarked, ScTable* pDestTab,
-                            const ScMarkData* pMarkData,
-                            bool bAsLink, bool bColRowFlags)
+void ScTable::CopyToTable(
+    sc::CopyToDocContext& rCxt, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
+    sal_uInt16 nFlags, bool bMarked, ScTable* pDestTab, const ScMarkData* pMarkData,
+    bool bAsLink, bool bColRowFlags )
 {
     if (!ValidColRow(nCol1, nRow1) || !ValidColRow(nCol2, nRow2))
         return;
 
     if (nFlags)
         for (SCCOL i = nCol1; i <= nCol2; i++)
-            aCol[i].CopyToColumn(nRow1, nRow2, nFlags, bMarked,
+            aCol[i].CopyToColumn(rCxt, nRow1, nRow2, nFlags, bMarked,
                                 pDestTab->aCol[i], pMarkData, bAsLink);
 
     if (!bColRowFlags)      // Spaltenbreiten/Zeilenhoehen/Flags
@@ -1158,13 +1160,15 @@ void ScTable::UndoToTable(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
         bool bWidth  = (nRow1==0 && nRow2==MAXROW && pColWidth && pDestTab->pColWidth);
         bool bHeight = (nCol1==0 && nCol2==MAXCOL && mpRowHeights && pDestTab->mpRowHeights);
 
+        sc::CopyToDocContext aCopyCxt(*pDestTab->pDocument);
+        aCopyCxt.setTabRange(pDestTab->nTab, pDestTab->nTab);
         for ( SCCOL i = 0; i <= MAXCOL; i++)
         {
             if ( i >= nCol1 && i <= nCol2 )
                 aCol[i].UndoToColumn(nRow1, nRow2, nFlags, bMarked, pDestTab->aCol[i],
                                         pMarkData);
             else
-                aCol[i].CopyToColumn(0, MAXROW, IDF_FORMULA, false, pDestTab->aCol[i]);
+                aCol[i].CopyToColumn(aCopyCxt, 0, MAXROW, IDF_FORMULA, false, pDestTab->aCol[i]);
         }
 
         //remove old notes