save about 50% of the import time for nearly empty ods documents

It seems that currently most of the time is spent iterating through all
the cells to get the optimal row height. We can easily optimize by using
mdds::flat_segment_tree.

Now we don't need to iterate through all cells and instead can work on
whole blocks.

Change-Id: Id9a0686490b0e91ad6552b428c38a9f6635a7938
Reviewed-on: https://gerrit.libreoffice.org/27856
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Markus Mohrhard <markus.mohrhard@googlemail.com>

7 files changed, 75 insertions, 38 deletions

diff --git a/sc/inc/rowheightcontext.hxx b/sc/inc/rowheightcontext.hxx
index f801ee466f29..d1a8f8ff68e4 100644
--- a/sc/inc/rowheightcontext.hxx
+++ b/sc/inc/rowheightcontext.hxx
@@ -18,11 +18,13 @@
 
 #include <vector>
 
+#include "segmenttree.hxx"
+
 namespace sc {
 
 class SC_DLLPUBLIC RowHeightContext
 {
-    std::vector<sal_uInt16> maHeights;
+    ScFlatUInt16RowSegments maHeights;
 
     double mfPPTX;
     double mfPPTY;
@@ -53,7 +55,7 @@ public:
     void setForceAutoSize( bool b );
     bool isForceAutoSize() const { return mbForceAutoSize;}
 
-    std::vector<sal_uInt16>& getHeightArray();
+    ScFlatUInt16RowSegments& getHeightArray();
 };
 
 }
diff --git a/sc/inc/segmenttree.hxx b/sc/inc/segmenttree.hxx
index 25eecec120f2..897b4dbf7239 100644
--- a/sc/inc/segmenttree.hxx
+++ b/sc/inc/segmenttree.hxx
@@ -135,6 +135,7 @@ public:
     ~ScFlatUInt16RowSegments();
 
     void setValue(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue);
+    void setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate);
     sal_uInt16 getValue(SCROW nRow);
     sal_uInt32 getSumValue(SCROW nRow1, SCROW nRow2);
     bool getRangeData(SCROW nRow, RangeData& rData);
diff --git a/sc/source/core/data/colorscale.cxx b/sc/source/core/data/colorscale.cxx
index da7f42e680fe..cfd6acf76645 100644
--- a/sc/source/core/data/colorscale.cxx
+++ b/sc/source/core/data/colorscale.cxx
@@ -956,6 +956,7 @@ ScIconSetInfo* ScIconSetFormat::GetIconSetInfo(const ScAddress& rAddr) const
         nValMax = CalcValue(nMin, nMax, itr);
         ++itr;
     }
+
     if(nVal >= nValMax)
         ++nIndex;
 
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index d3ed5e4385cf..cae1ff55e051 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -785,7 +785,7 @@ static sal_uInt16 lcl_GetAttribHeight( const ScPatternAttr& rPattern, sal_uInt16
 void ScColumn::GetOptimalHeight(
     sc::RowHeightContext& rCxt, SCROW nStartRow, SCROW nEndRow, sal_uInt16 nMinHeight, SCROW nMinStart )
 {
-    std::vector<sal_uInt16>& rHeights = rCxt.getHeightArray();
+    ScFlatUInt16RowSegments& rHeights = rCxt.getHeightArray();
     ScAttrIterator aIter( pAttrArray, nStartRow, nEndRow );
 
     SCROW nStart = -1;
@@ -887,9 +887,8 @@ void ScColumn::GetOptimalHeight(
                 if ( nDefHeight <= nMinHeight && nStdEnd >= nMinStart )
                     nStdEnd = (nMinStart>0) ? nMinStart-1 : 0;
 
-                for (SCROW nRow = nStart; nRow <= nStdEnd; ++nRow)
-                    if (nDefHeight > rHeights[nRow-nStartRow])
-                        rHeights[nRow-nStartRow] = nDefHeight;
+                if (nStart <= nStdEnd)
+                    rHeights.setValueIf(nStart, nStdEnd, nDefHeight, [=](sal_uInt16 nRowHeight){ return nDefHeight > nRowHeight; });
 
                 if ( bStdOnly )
                 {
@@ -910,22 +909,22 @@ void ScColumn::GetOptimalHeight(
                             {
                                 if ( nCjkHeight == 0 )
                                     nCjkHeight = lcl_GetAttribHeight( *pPattern, ATTR_CJK_FONT_HEIGHT );
-                                if (nCjkHeight > rHeights[nRow-nStartRow])
-                                    rHeights[nRow-nStartRow] = nCjkHeight;
+                                if (nCjkHeight > rHeights.getValue(nRow))
+                                    rHeights.setValue(nRow, nRow, nCjkHeight);
                             }
                             else if ( nScript == SvtScriptType::COMPLEX )
                             {
                                 if ( nCtlHeight == 0 )
                                     nCtlHeight = lcl_GetAttribHeight( *pPattern, ATTR_CTL_FONT_HEIGHT );
-                                if (nCtlHeight > rHeights[nRow-nStartRow])
-                                    rHeights[nRow-nStartRow] = nCtlHeight;
+                                if (nCtlHeight > rHeights.getValue(nRow))
+                                    rHeights.setValue(nRow, nRow, nCtlHeight);
                             }
                             else
                             {
                                 if ( nLatHeight == 0 )
                                     nLatHeight = lcl_GetAttribHeight( *pPattern, ATTR_FONT_HEIGHT );
-                                if (nLatHeight > rHeights[nRow-nStartRow])
-                                    rHeights[nRow-nStartRow] = nLatHeight;
+                                if (nLatHeight > rHeights.getValue(nRow))
+                                    rHeights.setValue(nRow, nRow, nLatHeight);
                             }
                         }
                     }
@@ -951,8 +950,8 @@ void ScColumn::GetOptimalHeight(
                                     ( GetNeededSize( nRow, rCxt.getOutputDevice(), rCxt.getPPTX(), rCxt.getPPTY(),
                                                         rCxt.getZoomX(), rCxt.getZoomY(), false, aOptions,
                                                         &pPattern) / rCxt.getPPTY() );
-                            if (nHeight > rHeights[nRow-nStartRow])
-                                rHeights[nRow-nStartRow] = nHeight;
+                            if (nHeight > rHeights.getValue(nRow))
+                                rHeights.setValue(nRow, nRow, nHeight);
                             // Pattern changed due to calculation? => sync.
                             if (pPattern != pOldPattern)
                             {
diff --git a/sc/source/core/data/rowheightcontext.cxx b/sc/source/core/data/rowheightcontext.cxx
index 46f3c6dad9ca..4cba0b9d9f17 100644
--- a/sc/source/core/data/rowheightcontext.cxx
+++ b/sc/source/core/data/rowheightcontext.cxx
@@ -14,6 +14,7 @@ namespace sc {
 RowHeightContext::RowHeightContext(
     double fPPTX, double fPPTY, const Fraction& rZoomX, const Fraction& rZoomY,
     OutputDevice* pOutDev ) :
+    maHeights(0),
     mfPPTX(fPPTX), mfPPTY(fPPTY),
     maZoomX(rZoomX), maZoomY(rZoomY),
     mpOutDev(pOutDev),
@@ -32,7 +33,7 @@ void RowHeightContext::setForceAutoSize( bool b )
     mbForceAutoSize = b;
 }
 
-std::vector<sal_uInt16>& RowHeightContext::getHeightArray()
+ScFlatUInt16RowSegments& RowHeightContext::getHeightArray()
 {
     return maHeights;
 }
diff --git a/sc/source/core/data/segmenttree.cxx b/sc/source/core/data/segmenttree.cxx
index 7159d9c00537..98b2929167cc 100644
--- a/sc/source/core/data/segmenttree.cxx
+++ b/sc/source/core/data/segmenttree.cxx
@@ -45,6 +45,7 @@ public:
     ~ScFlatSegmentsImpl();
 
     bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
+    void setValueIf(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue, const std::function<bool(ValueType)>& rPredicate);
     ValueType getValue(SCCOLROW nPos);
     ExtValueType getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
     bool getRangeData(SCCOLROW nPos, RangeData& rData);
@@ -100,6 +101,25 @@ bool ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValue(SCCOLROW nPos1, SCC
 }
 
 template<typename ValueType_, typename ExtValueType_>
+void ScFlatSegmentsImpl<ValueType_, ExtValueType_>::setValueIf(SCCOLROW nPos1, SCCOLROW nPos2,
+        ValueType nValue, const std::function<bool(ValueType)>& rPredicate)
+{
+    SCCOLROW nCurrentStartRow = nPos1;
+    while (nCurrentStartRow <= nPos2)
+    {
+        RangeData aRangeData;
+        getRangeData(nCurrentStartRow, aRangeData);
+        if (rPredicate(aRangeData.mnValue))
+        {
+            setValue(nPos1, std::min<SCCOLROW>(nPos2, aRangeData.mnPos2), nValue);
+        }
+
+        // even if nPos2 is bigger than nPos2 this should terminate the loop
+        nCurrentStartRow = aRangeData.mnPos2 + 1;
+    }
+}
+
+template<typename ValueType_, typename ExtValueType_>
 typename ScFlatSegmentsImpl<ValueType_, ExtValueType_>::ValueType ScFlatSegmentsImpl<ValueType_, ExtValueType_>::getValue(SCCOLROW nPos)
 {
     ValueType nValue = 0;
@@ -516,4 +536,9 @@ void ScFlatUInt16RowSegments::enableTreeSearch(bool bEnable)
     mpImpl->enableTreeSearch(bEnable);
 }
 
+void ScFlatUInt16RowSegments::setValueIf(SCROW nRow1, SCROW nRow2, sal_uInt16 nValue, const std::function<bool(sal_uInt16)>& rPredicate)
+{
+    mpImpl->setValueIf(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2), nValue, rPredicate);
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 597901d96d09..f884dc3c80c3 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -86,23 +86,28 @@ void GetOptimalHeightsInColumn(
 {
     assert(nStartRow <= nEndRow);
 
-    SCSIZE nCount = static_cast<SCSIZE>(nEndRow-nStartRow+1);
-
     //  first, one time over the whole range
     //  (with the last column in the hope that they most likely still are
     //  on standard format)
 
-    std::vector<sal_uInt16>& rHeights = rCxt.getHeightArray();
 
     rCol[MAXCOL].GetOptimalHeight(rCxt, nStartRow, nEndRow, 0, 0);
 
     //  from there search for the standard height that is in use in the lower part
 
-    sal_uInt16 nMinHeight = rHeights[nCount-1];
-    SCSIZE nPos = nCount-1;
-    while ( nPos && rHeights[nPos-1] >= nMinHeight )
-        --nPos;
-    SCROW nMinStart = nStartRow + nPos;
+    ScFlatUInt16RowSegments& rHeights = rCxt.getHeightArray();
+    sal_uInt16 nMinHeight = rHeights.getValue(nEndRow);
+    SCSIZE nPos = nEndRow-1;
+    ScFlatUInt16RowSegments::RangeData aRangeData;
+    while ( nPos && rHeights.getRangeData(nPos-1, aRangeData) )
+    {
+        if (aRangeData.mnValue >= nMinHeight)
+            nPos = std::max<SCSIZE>(0, aRangeData.mnRow1);
+        else
+            break;
+    }
+
+    SCROW nMinStart = nPos;
 
     sal_uLong nWeightedCount = 0;
     for (SCCOL nCol=0; nCol<MAXCOL; nCol++)     // MAXCOL already above
@@ -164,20 +169,19 @@ bool SetOptimalHeightsToRows(
     OptimalHeightsFuncObjBase& rFuncObj,
     ScBitMaskCompressedArray<SCROW, sal_uInt8>* pRowFlags, SCROW nStartRow, SCROW nEndRow )
 {
-    SCSIZE nCount = static_cast<SCSIZE>(nEndRow-nStartRow+1);
     bool bChanged = false;
     SCROW nRngStart = 0;
     SCROW nRngEnd = 0;
     sal_uInt16 nLast = 0;
     sal_uInt16 nExtraHeight = rCxt.getExtraHeight();
-    for (SCSIZE i=0; i<nCount; i++)
+    for (SCSIZE i = nStartRow; i <= static_cast<SCSIZE>(nEndRow); i++)
     {
         size_t nIndex;
         SCROW nRegionEndRow;
-        sal_uInt8 nRowFlag = pRowFlags->GetValue( nStartRow+i, nIndex, nRegionEndRow );
+        sal_uInt8 nRowFlag = pRowFlags->GetValue( i, nIndex, nRegionEndRow );
         if ( nRegionEndRow > nEndRow )
             nRegionEndRow = nEndRow;
-        SCSIZE nMoreRows = nRegionEndRow - ( nStartRow+i );     // additional equal rows after first
+        SCSIZE nMoreRows = nRegionEndRow - i;     // additional equal rows after first
 
         bool bAutoSize = ((nRowFlag & CR_MANUALSIZE) == 0);
         if (bAutoSize || rCxt.isForceAutoSize())
@@ -185,17 +189,22 @@ bool SetOptimalHeightsToRows(
             if (nExtraHeight)
             {
                 if (bAutoSize)
-                    pRowFlags->SetValue( nStartRow+i, nRegionEndRow, nRowFlag | CR_MANUALSIZE);
+                    pRowFlags->SetValue( i, nRegionEndRow, nRowFlag | CR_MANUALSIZE);
             }
             else if (!bAutoSize)
-                pRowFlags->SetValue( nStartRow+i, nRegionEndRow, nRowFlag & ~CR_MANUALSIZE);
+                pRowFlags->SetValue( i, nRegionEndRow, nRowFlag & ~CR_MANUALSIZE);
 
             for (SCSIZE nInner = i; nInner <= i + nMoreRows; ++nInner)
             {
                 if (nLast)
                 {
-                    if (rCxt.getHeightArray()[nInner] + nExtraHeight == nLast)
-                        nRngEnd = nStartRow+nInner;
+                    ScFlatUInt16RowSegments::RangeData aRangeData;
+                    rCxt.getHeightArray().getRangeData(nInner, aRangeData);
+                    if (aRangeData.mnValue + nExtraHeight == nLast)
+                    {
+                        nRngEnd = std::min<SCSIZE>(i + nMoreRows, aRangeData.mnRow2);
+                        nInner = aRangeData.mnRow2;
+                    }
                     else
                     {
                         bChanged |= rFuncObj(nRngStart, nRngEnd, nLast);
@@ -204,9 +213,9 @@ bool SetOptimalHeightsToRows(
                 }
                 if (!nLast)
                 {
-                    nLast = rCxt.getHeightArray()[nInner] + rCxt.getExtraHeight();
-                    nRngStart = nStartRow+nInner;
-                    nRngEnd = nStartRow+nInner;
+                    nLast = rCxt.getHeightArray().getValue(nInner) + rCxt.getExtraHeight();
+                    nRngStart = nInner;
+                    nRngEnd = nInner;
                 }
             }
         }
@@ -480,10 +489,9 @@ bool ScTable::SetOptimalHeight(
 
     ScProgress* pProgress = GetProgressBar(nCount, GetWeightedCount(), pOuterProgress, pDocument);
 
-    rCxt.getHeightArray().resize(nCount, 0);
-
     GetOptimalHeightsInColumn(rCxt, aCol, nStartRow, nEndRow, pProgress, nProgressStart);
 
+    rCxt.getHeightArray().enableTreeSearch(true);
     SetRowHeightRangeFunc aFunc(this, rCxt.getPPTX(), rCxt.getPPTY());
     bool bChanged = SetOptimalHeightsToRows(rCxt, aFunc, pRowFlags, nStartRow, nEndRow);
 
@@ -507,11 +515,11 @@ void ScTable::SetOptimalHeightOnly(
 
     ScProgress* pProgress = GetProgressBar(nCount, GetWeightedCount(), pOuterProgress, pDocument);
 
-    rCxt.getHeightArray().resize(nCount, 0);
-
     GetOptimalHeightsInColumn(rCxt, aCol, nStartRow, nEndRow, pProgress, nProgressStart);
 
     SetRowHeightOnlyFunc aFunc(this);
+
+    rCxt.getHeightArray().enableTreeSearch(true);
     SetOptimalHeightsToRows(rCxt, aFunc, pRowFlags, nStartRow, nEndRow);
 
     if ( pProgress != pOuterProgress )