Speed up ScColumn::HasEditCells() by keeping track of block position.

Use block position hint to avoid re-starting search in the cell text
attribute array.  This change alone cuts additional 10 seconds off of
the previously mentioned use case, by reducing the duration of
HasEditCells() call from the previous ~10 seconds to a tiny fraction
of a second.

Change-Id: Id9f951cd235a88928c900619b6b66d7b8a057e0c

7 files changed, 121 insertions, 26 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index edf362fb23ad..a697bede5b00 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -268,7 +268,7 @@ public:
     void        MoveTo(SCROW nStartRow, SCROW nEndRow, ScColumn& rCol);
 
 
-    bool               HasEditCells(SCROW nStartRow, SCROW nEndRow, SCROW& rFirst) const;
+    bool HasEditCells(SCROW nStartRow, SCROW nEndRow, SCROW& rFirst);
 
     bool SetString(
         SCROW nRow, SCTAB nTab, const String& rString, formula::FormulaGrammar::AddressConvention eConv,
@@ -411,7 +411,7 @@ public:
     void GetOptimalHeight(
         SCROW nStartRow, SCROW nEndRow, sal_uInt16* pHeight, OutputDevice* pDev,
         double nPPTX, double nPPTY, const Fraction& rZoomX, const Fraction& rZoomY,
-        bool bShrink, sal_uInt16 nMinHeight, SCROW nMinStart) const;
+        bool bShrink, sal_uInt16 nMinHeight, SCROW nMinStart);
 
                 /// Including current, may return -1
     SCsROW      GetNextUnprotected( SCROW nRow, bool bUp ) const;
diff --git a/sc/inc/conditio.hxx b/sc/inc/conditio.hxx
index 9e7e14d224c2..87cfcc30446d 100644
--- a/sc/inc/conditio.hxx
+++ b/sc/inc/conditio.hxx
@@ -455,6 +455,7 @@ public:
     bool    CheckAllEntries();
 
     ScConditionalFormat* GetFormat( sal_uInt32 nKey );
+    const ScConditionalFormat* GetFormat( sal_uInt32 nKey ) const;
 
     void    CompileAll();
     void    CompileXML();
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index c511cf04e3af..e2ea7e3c5cfe 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1267,6 +1267,9 @@ public:
 
     SC_DLLPUBLIC ScConditionalFormat* GetCondFormat( SCCOL nCol, SCROW nRow, SCTAB nTab ) const;
     SC_DLLPUBLIC const SfxItemSet*  GetCondResult( SCCOL nCol, SCROW nRow, SCTAB nTab ) const;
+    const SfxItemSet* GetCondResult(
+        ScRefCellValue& rCell, const ScAddress& rPos, const ScConditionalFormatList& rList,
+        const std::vector<sal_uInt32>& rIndex ) const;
     const SfxPoolItem*  GetEffItem( SCCOL nCol, SCROW nRow, SCTAB nTab, sal_uInt16 nWhich ) const;
 
     SC_DLLPUBLIC const ::com::sun::star::uno::Reference< ::com::sun::star::i18n::XBreakIterator >& GetBreakIterator();
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index 0e42ff146163..704bdffc02e8 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -33,6 +33,7 @@
 #include "globalnames.hxx"
 #include "cellvalue.hxx"
 #include "tokenarray.hxx"
+#include "cellform.hxx"
 
 #include <svl/poolcach.hxx>
 #include <svl/zforlist.hxx>
@@ -2286,25 +2287,89 @@ void ScColumn::ResetChanged( SCROW nStartRow, SCROW nEndRow )
 }
 
 
-bool ScColumn::HasEditCells(SCROW nStartRow, SCROW nEndRow, SCROW& rFirst) const
+bool ScColumn::HasEditCells(SCROW nStartRow, SCROW nEndRow, SCROW& rFirst)
 {
     //  used in GetOptimalHeight - ambiguous script type counts as edit cell
 
-    SCROW nRow = 0;
-    SCSIZE nIndex;
-    Search(nStartRow,nIndex);
-    while ( (nIndex < maItems.size()) ? ((nRow=maItems[nIndex].nRow) <= nEndRow) : false )
+    std::vector<ColEntry>::const_iterator itCell = Search(nStartRow);
+    std::vector<ColEntry>::const_iterator itCellEnd = maItems.end();
+    if (itCell == itCellEnd)
+        return false;
+
+    SvNumberFormatter* pFormatter = pDocument->GetFormatTable();
+    ScConditionalFormatList* pCFList = pDocument->GetCondFormList(nTab);
+
+    sc::CellTextAttrStoreType::iterator itAttrPos = maCellTextAttrs.begin();
+    for (; itCell != itCellEnd && itCell->nRow <= nEndRow; ++itCell)
     {
-        ScBaseCell* pCell = maItems[nIndex].pCell;
+        ScBaseCell* pCell = itCell->pCell;
+        SCROW nRow = itCell->nRow;
         CellType eCellType = pCell->GetCellType();
-        if ( eCellType == CELLTYPE_EDIT ||
-             IsAmbiguousScriptNonZero( pDocument->GetScriptType(nCol, nRow, nTab) ) ||
-             ((eCellType == CELLTYPE_FORMULA) && ((ScFormulaCell*)pCell)->IsMultilineResult()) )
+
+        // See if this is a real edit cell.
+        if (eCellType == CELLTYPE_EDIT)
+        {
+            rFirst = nRow;
+            return true;
+        }
+
+        // Check the script type next.
+        std::pair<sc::CellTextAttrStoreType::iterator,size_t> itPos =
+            maCellTextAttrs.position(itAttrPos, nRow);
+
+        sal_uInt16 nScriptType = 0;
+        itAttrPos = itPos.first; // Track the position of cell text attribute array.
+        if (itAttrPos->type == sc::element_type_celltextattr)
+        {
+            sc::CellTextAttr& rVal =
+                sc::custom_celltextattr_block::at(*itAttrPos->data, itPos.second);
+            nScriptType = rVal.mnScriptType;
+
+            if (nScriptType == SC_SCRIPTTYPE_UNKNOWN)
+            {
+                // Script type not yet determined. Determine the real script
+                // type, and store it.
+                const ScPatternAttr* pPattern = GetPattern(nRow);
+                if (pPattern)
+                {
+                    ScRefCellValue aCell;
+                    ScAddress aPos(nCol, nRow, nTab);
+                    aCell.assign(*pDocument, aPos);
+
+                    const SfxItemSet* pCondSet = NULL;
+                    if (pCFList)
+                    {
+                        const ScCondFormatItem& rItem =
+                            static_cast<const ScCondFormatItem&>(pPattern->GetItem(ATTR_CONDITIONAL));
+                        const std::vector<sal_uInt32>& rData = rItem.GetCondFormatData();
+                        pCondSet = pDocument->GetCondResult(aCell, aPos, *pCFList, rData);
+                    }
+
+                    OUString aStr;
+                    Color* pColor;
+                    sal_uLong nFormat = pPattern->GetNumberFormat(pFormatter, pCondSet);
+                    ScCellFormat::GetString(aCell, nFormat, aStr, &pColor, *pFormatter);
+                    nScriptType = pDocument->GetStringScriptType(aStr);
+
+                    if (nScriptType && nScriptType != SC_SCRIPTTYPE_UNKNOWN)
+                        // Store the real script type to the array.
+                        rVal.mnScriptType = nScriptType;
+                }
+            }
+        }
+
+        if (IsAmbiguousScriptNonZero(nScriptType))
+        {
+            rFirst = nRow;
+            return true;
+        }
+
+        // Lastly, see if this is a formula cell with multi-line result.
+        if (eCellType == CELLTYPE_FORMULA && static_cast<ScFormulaCell*>(pCell)->IsMultilineResult())
         {
             rFirst = nRow;
             return true;
         }
-        ++nIndex;
     }
 
     return false;
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 7ad37625a2fc..6b91f284253f 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -683,7 +683,7 @@ static sal_uInt16 lcl_GetAttribHeight( const ScPatternAttr& rPattern, sal_uInt16
 void ScColumn::GetOptimalHeight(
     SCROW nStartRow, SCROW nEndRow, sal_uInt16* pHeight, OutputDevice* pDev,
     double nPPTX, double nPPTY, const Fraction& rZoomX, const Fraction& rZoomY,
-    bool bShrink, sal_uInt16 nMinHeight, SCROW nMinStart) const
+    bool bShrink, sal_uInt16 nMinHeight, SCROW nMinStart)
 {
     ScAttrIterator aIter( pAttrArray, nStartRow, nEndRow );
 
diff --git a/sc/source/core/data/conditio.cxx b/sc/source/core/data/conditio.cxx
index e889a9372b45..88028cf317f3 100644
--- a/sc/source/core/data/conditio.cxx
+++ b/sc/source/core/data/conditio.cxx
@@ -2134,6 +2134,18 @@ ScConditionalFormat* ScConditionalFormatList::GetFormat( sal_uInt32 nKey )
     return NULL;
 }
 
+const ScConditionalFormat* ScConditionalFormatList::GetFormat( sal_uInt32 nKey ) const
+{
+    //! binaer suchen
+
+    for ( const_iterator itr = begin(); itr != end(); ++itr)
+        if (itr->GetKey() == nKey)
+            return &(*itr);
+
+    SAL_WARN("sc", "ScConditionalFormatList: Entry not found");
+    return NULL;
+}
+
 void ScConditionalFormatList::CompileAll()
 {
     for( iterator itr = begin(); itr != end(); ++itr)
diff --git a/sc/source/core/data/documen4.cxx b/sc/source/core/data/documen4.cxx
index fa5f79edee73..90a5d9abff78 100644
--- a/sc/source/core/data/documen4.cxx
+++ b/sc/source/core/data/documen4.cxx
@@ -661,28 +661,42 @@ const SfxPoolItem* ScDocument::GetEffItem(
 
 const SfxItemSet* ScDocument::GetCondResult( SCCOL nCol, SCROW nRow, SCTAB nTab ) const
 {
-    const ScPatternAttr* pPattern = GetPattern( nCol, nRow, nTab );
-    const std::vector<sal_uInt32>& rIndex = static_cast<const ScCondFormatItem&>(pPattern->GetItem(ATTR_CONDITIONAL)).GetCondFormatData();
     ScConditionalFormatList* pFormatList = GetCondFormList(nTab);
-    for(std::vector<sal_uInt32>::const_iterator itr = rIndex.begin(), itrEnd = rIndex.end();
-            itr != itrEnd; ++itr)
+    if (!pFormatList)
+        return NULL;
+
+    ScAddress aPos(nCol, nRow, nTab);
+    ScRefCellValue aCell;
+    aCell.assign(const_cast<ScDocument&>(*this), aPos);
+    const ScPatternAttr* pPattern = GetPattern( nCol, nRow, nTab );
+    const std::vector<sal_uInt32>& rIndex =
+        static_cast<const ScCondFormatItem&>(pPattern->GetItem(ATTR_CONDITIONAL)).GetCondFormatData();
+
+    return GetCondResult(aCell, aPos, *pFormatList, rIndex);
+}
+
+const SfxItemSet* ScDocument::GetCondResult(
+    ScRefCellValue& rCell, const ScAddress& rPos, const ScConditionalFormatList& rList,
+    const std::vector<sal_uInt32>& rIndex ) const
+{
+    std::vector<sal_uInt32>::const_iterator itr = rIndex.begin(), itrEnd = rIndex.end();
+    for (; itr != itrEnd; ++itr)
     {
-        ScConditionalFormat* pForm = pFormatList->GetFormat(*itr);
-        if(!pForm)
+        const ScConditionalFormat* pForm = rList.GetFormat(*itr);
+        if (!pForm)
             continue;
 
-        ScAddress aPos(nCol, nRow, nTab);
-        ScRefCellValue aCell;
-        aCell.assign(const_cast<ScDocument&>(*this), aPos);
-        const OUString& aStyle = pForm->GetCellStyle(aCell, aPos);
+        const OUString& aStyle = pForm->GetCellStyle(rCell, rPos);
         if (!aStyle.isEmpty())
         {
-            SfxStyleSheetBase* pStyleSheet = xPoolHelper->GetStylePool()->Find( aStyle, SFX_STYLE_FAMILY_PARA );
-            if ( pStyleSheet )
+            SfxStyleSheetBase* pStyleSheet =
+                xPoolHelper->GetStylePool()->Find(aStyle, SFX_STYLE_FAMILY_PARA);
+
+            if (pStyleSheet)
                 return &pStyleSheet->GetItemSet();
+
             // if style is not there, treat like no condition
         }
-
     }
 
     return NULL;