tdf#89436 fix ScHorizontalAttrIterator performance

(cherry picked from master:
d619d23a1f641fc910723cc32c4d8c8d9a8f3681 add unit test
8e9540d3d4909c6dd45c9efa294f565d9735a0d9 fix indices
dd4bd0ee74fae3d7e3a16e018021da173152571b fix condition + cleanup
a5ab0e3a8b1cb7c06072229e1c4d956eb81fa002 handle skipping empty rows
4de4f1fd1125bc8cf6059cf143bb76d1ab212434 fix ScHorizontalAttrIterator performance)

Change-Id: Ieda6f3171c5e81d1029746fedd320d7caa7db676
Reviewed-on: https://gerrit.libreoffice.org/14526
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Eike Rathke <erack@redhat.com>

4 files changed, 74 insertions, 17 deletions

diff --git a/sc/inc/dociter.hxx b/sc/inc/dociter.hxx
index 2230b81c9c8e..65023b0434dd 100644
--- a/sc/inc/dociter.hxx
+++ b/sc/inc/dociter.hxx
@@ -487,11 +487,14 @@ private:
     SCROW                   nEndRow;
 
     SCROW*                  pNextEnd;
+    SCCOL*                  pPrevColEnd;
     SCSIZE*                 pIndices;
     const ScPatternAttr**   ppPatterns;
     SCCOL                   nCol;
     SCROW                   nRow;
     bool                    bRowEmpty;
+    bool                    bRepeatedRow;
+    SCROW                   nMinNextEnd;
 
 public:
             ScHorizontalAttrIterator( ScDocument* pDocument, SCTAB nTable,
diff --git a/sc/qa/unit/ucalc.cxx b/sc/qa/unit/ucalc.cxx
index 49027cf34383..ce5efc2daf11 100644
--- a/sc/qa/unit/ucalc.cxx
+++ b/sc/qa/unit/ucalc.cxx
@@ -1223,6 +1223,40 @@ void Test::testValueIterator()
     m_pDoc->DeleteTab(0);
 }
 
+void Test::testHorizontalAttrIterator()
+{
+    m_pDoc->InsertTab(0, "Test");
+
+    // Set the background color of B2:C3 to blue
+    ScPatternAttr aCellBackColor(m_pDoc->GetPool());
+    aCellBackColor.GetItemSet().Put(SvxBrushItem(COL_BLUE, ATTR_BACKGROUND));
+    m_pDoc->ApplyPatternAreaTab(1, 1, 2, 2, 0, aCellBackColor);
+
+    // some numeric data
+    for (SCCOL i = 1; i <= 4; ++i)
+        for (SCROW j = 1; j <= 4; ++j)
+            m_pDoc->SetValue(ScAddress(i,j,0), i*10+j);
+
+    {
+        const int aChecks[][3] = { {1, 2, 1}, {1, 2, 2} };
+        size_t nCheckLen = SAL_N_ELEMENTS(aChecks);
+
+        ScHorizontalAttrIterator aIter(m_pDoc, 0, 0, 0, 3, 3);
+        SCCOL nCol1, nCol2;
+        SCROW nRow;
+        size_t nCheckPos = 0;
+        for (const ScPatternAttr* pAttr = aIter.GetNext(nCol1, nCol2, nRow); pAttr; pAttr = aIter.GetNext(nCol1, nCol2, nRow), ++nCheckPos)
+        {
+              CPPUNIT_ASSERT_MESSAGE("Iteration longer than expected.", nCheckPos < nCheckLen);
+              CPPUNIT_ASSERT_EQUAL(aChecks[nCheckPos][0], static_cast<int>(nCol1));
+              CPPUNIT_ASSERT_EQUAL(aChecks[nCheckPos][1], static_cast<int>(nCol2));
+              CPPUNIT_ASSERT_EQUAL(aChecks[nCheckPos][2], static_cast<int>(nRow));
+        }
+    }
+
+    m_pDoc->DeleteTab(0);
+}
+
 namespace {
 
 bool broadcasterShifted(const ScDocument& rDoc, const ScAddress& rFrom, const ScAddress& rTo)
diff --git a/sc/qa/unit/ucalc.hxx b/sc/qa/unit/ucalc.hxx
index 19b3b5f31952..28e0e013d33e 100644
--- a/sc/qa/unit/ucalc.hxx
+++ b/sc/qa/unit/ucalc.hxx
@@ -184,6 +184,7 @@ public:
 
     void testHorizontalIterator();
     void testValueIterator();
+    void testHorizontalAttrIterator();
 
     /**
      * Basic test for formula dependency tracking.
@@ -486,6 +487,7 @@ public:
     CPPUNIT_TEST(testFuncNOW);
     CPPUNIT_TEST(testHorizontalIterator);
     CPPUNIT_TEST(testValueIterator);
+    CPPUNIT_TEST(testHorizontalAttrIterator);
     CPPUNIT_TEST(testFormulaDepTracking);
     CPPUNIT_TEST(testFormulaDepTracking2);
     CPPUNIT_TEST(testFormulaDepTracking3);
diff --git a/sc/source/core/data/dociter.cxx b/sc/source/core/data/dociter.cxx
index 2c5a59710f4a..92406345caa2 100644
--- a/sc/source/core/data/dociter.cxx
+++ b/sc/source/core/data/dociter.cxx
@@ -2235,12 +2235,14 @@ ScHorizontalAttrIterator::ScHorizontalAttrIterator( ScDocument* pDocument, SCTAB
     nRow = nStartRow;
     nCol = nStartCol;
     bRowEmpty = false;
+    bRepeatedRow = false;
 
     pIndices    = new SCSIZE[nEndCol-nStartCol+1];
     pNextEnd    = new SCROW[nEndCol-nStartCol+1];
+    pPrevColEnd = new SCCOL[nEndCol-nStartCol+1];
     ppPatterns  = new const ScPatternAttr*[nEndCol-nStartCol+1];
 
-    SCROW nSkipTo = MAXROW;
+    nMinNextEnd = MAXROW;
     bool bEmpty = true;
     for (i=nStartCol; i<=nEndCol; i++)
     {
@@ -2253,22 +2255,23 @@ ScHorizontalAttrIterator::ScHorizontalAttrIterator( ScDocument* pDocument, SCTAB
 
         const ScPatternAttr* pPattern = pArray->pData[nIndex].pPattern;
         SCROW nThisEnd = pArray->pData[nIndex].nRow;
+
+        if ( nThisEnd < nMinNextEnd )
+            nMinNextEnd = nThisEnd; // nMinNextEnd can be set here already
+
         if ( IsDefaultItem( pPattern ) )
-        {
             pPattern = NULL;
-            if ( nThisEnd < nSkipTo )
-                nSkipTo = nThisEnd; // nSkipTo can be set here already
-        }
         else
             bEmpty = false; // Found attributes
 
         pIndices[nPos] = nIndex;
         pNextEnd[nPos] = nThisEnd;
+        pPrevColEnd[nPos] = MAXCOL+1; // only for OSL_ENSURE
         ppPatterns[nPos] = pPattern;
     }
 
     if (bEmpty)
-        nRow = nSkipTo; // Skip until end of next section
+        nRow = nMinNextEnd; // Skip until end of next section
 
     bRowEmpty = bEmpty;
 }
@@ -2277,6 +2280,7 @@ ScHorizontalAttrIterator::~ScHorizontalAttrIterator()
 {
     delete[] ppPatterns;
     delete[] pNextEnd;
+    delete[] pPrevColEnd;
     delete[] pIndices;
 }
 
@@ -2297,19 +2301,37 @@ const ScPatternAttr* ScHorizontalAttrIterator::GetNext( SCCOL& rCol1, SCCOL& rCo
                 const ScPatternAttr* pPat = ppPatterns[nCol-nStartCol];
                 rRow = nRow;
                 rCol1 = nCol;
-                while ( nCol < nEndCol && ppPatterns[nCol+1-nStartCol] == pPat )
-                    ++nCol;
+                if ( bRepeatedRow )
+                {
+                    OSL_ENSURE( pPrevColEnd[nCol-nStartCol] < MAXCOL+1, "missing stored data" );
+                    nCol = pPrevColEnd[nCol-nStartCol]; // use the result stored before
+                }
+                else
+                {
+                    while ( nCol < nEndCol && ( ppPatterns[nCol+1-nStartCol] == pPat) )
+                        ++nCol;
+                    // store the result to avoid the previous very expensive comparisons
+                    pPrevColEnd[rCol1-nStartCol] = nCol;
+                }
                 rCol2 = nCol;
                 ++nCol; // Count up for next call
                 return pPat; // Found it!
             }
+
+            bRepeatedRow = true; // we can use the stored row data next time
         }
 
         // Next row
         ++nRow;
         if ( nRow > nEndRow ) // Already at the end?
             return NULL; // Found nothing
+        nCol = nStartCol; // Start at the left again
 
+        if ( bRepeatedRow && nRow <= nMinNextEnd ) // use only the stored data of the previous row
+           continue;
+
+        bRepeatedRow = false;
+        nMinNextEnd = MAXROW;
         bool bEmpty = true;
         SCCOL i;
 
@@ -2344,19 +2366,15 @@ const ScPatternAttr* ScHorizontalAttrIterator::GetNext( SCCOL& rCol1, SCCOL& rCo
             }
             else if ( ppPatterns[nPos] )
                 bEmpty = false; // Area not at the end yet
+
+            if ( nMinNextEnd > pNextEnd[nPos] )
+                nMinNextEnd = pNextEnd[nPos];
+
         }
 
         if (bEmpty)
-        {
-            SCCOL nCount = nEndCol-nStartCol+1;
-            SCROW nSkipTo = pNextEnd[0]; // Search next end of area
-            for (i=1; i<nCount; i++)
-                if ( pNextEnd[i] < nSkipTo )
-                    nSkipTo = pNextEnd[i];
-            nRow = nSkipTo; // Skip empty rows
-        }
+            nRow = nMinNextEnd; // Skip empty rows
         bRowEmpty = bEmpty;
-        nCol = nStartCol; // Start at the left again
     }
 }