Optimize ScViewFunc::GetSelectionScriptType().

This change reduces the duration of this method from somewhere in the
ballpark of 10 seconds down to a tiny fraction of a second.

Change-Id: I0278dc06a4f134b43cd08bd94693b6dec4893f1f

13 files changed, 210 insertions, 69 deletions

diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index a697bede5b00..f1584b11f837 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -446,6 +446,8 @@ public:
     void SetTextWidth(SCROW nRow, sal_uInt16 nWidth);
 
     sal_uInt8 GetScriptType( SCROW nRow ) const;
+    sal_uInt8 GetRangeScriptType( sc::CellTextAttrStoreType::iterator& itPos, SCROW nRow1, SCROW nRow2 );
+
     void SetScriptType( SCROW nRow, sal_uInt8 nType );
 
     size_t GetFormulaHash( SCROW nRow ) const;
@@ -464,6 +466,8 @@ public:
     void DeleteBroadcasters( SCROW nRow1, SCROW nRow2 );
 
 private:
+    void UpdateScriptType( sc::CellTextAttr& rAttr, SCROW nRow );
+
     void DeleteRange(
         SCSIZE nStartIndex, SCSIZE nEndIndex, sal_uInt16 nDelFlag, std::vector<SCROW>& rDeletedRows );
 
diff --git a/sc/inc/columnspanset.hxx b/sc/inc/columnspanset.hxx
index afd17977add9..35d94bf8e789 100644
--- a/sc/inc/columnspanset.hxx
+++ b/sc/inc/columnspanset.hxx
@@ -30,17 +30,21 @@ class ColumnSpanSet : boost::noncopyable
 
     DocType maDoc;
 
+    ColumnSpansType& getColumnSpans(SCTAB nTab, SCCOL nCol);
+
 public:
     class Action
     {
     public:
         virtual ~Action() = 0;
+        virtual void startColumn(SCTAB nTab, SCCOL nCol);
         virtual void execute(const ScAddress& rPos, SCROW nLength, bool bVal) = 0;
     };
 
     ~ColumnSpanSet();
 
-    void set(SCCOL nCol, SCROW nRow, SCTAB nTab, bool bVal);
+    void set(SCTAB nTab, SCCOL nCol, SCROW nRow, bool bVal);
+    void set(SCTAB nTab, SCCOL nCol, SCROW nRow1, SCROW nRow2, bool bVal);
 
     void executeFromTop(Action& ac) const;
     void executeFromBottom(Action& ac) const;
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index e2ea7e3c5cfe..5f63d85a5586 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -1277,6 +1277,9 @@ public:
     SC_DLLPUBLIC sal_uInt8          GetStringScriptType( const OUString& rString );
     SC_DLLPUBLIC sal_uInt8 GetCellScriptType( const ScAddress& rPos, sal_uLong nNumberFormat );
     SC_DLLPUBLIC sal_uInt8 GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab );
+    sal_uInt8 GetRangeScriptType(
+        sc::ColumnBlockPosition& rBlockPos, const ScAddress& rPos, SCROW nLength );
+    sal_uInt8 GetRangeScriptType( const ScRangeList& rRanges );
 
     bool            HasDetectiveOperations() const;
     void            AddDetectiveOperation( const ScDetOpData& rData );
diff --git a/sc/inc/listenercontext.hxx b/sc/inc/listenercontext.hxx
index 2fc55a769821..36f26d82871e 100644
--- a/sc/inc/listenercontext.hxx
+++ b/sc/inc/listenercontext.hxx
@@ -27,7 +27,7 @@ public:
     EndListeningContext(ScDocument& rDoc);
     ScDocument& getDoc();
 
-    void addEmptyBroadcasterPosition(SCCOL nCol, SCROW nRow, SCTAB nTab);
+    void addEmptyBroadcasterPosition(SCTAB nTab, SCCOL nCol, SCROW nRow);
     void purgeEmptyBroadcasters();
 };
 
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 00255fe2c248..333eb9ae7e87 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -829,6 +829,8 @@ public:
     sal_uInt8 GetScriptType( SCCOL nCol, SCROW nRow ) const;
     void SetScriptType( SCCOL nCol, SCROW nRow, sal_uInt8 nType );
 
+    sal_uInt8 GetRangeScriptType( sc::ColumnBlockPosition& rBlockPos, SCCOL nCol, SCROW nRow1, SCROW nRow2 );
+
     size_t GetFormulaHash( SCCOL nCol, SCROW nRow ) const;
 
     ScFormulaVectorState GetFormulaVectorState( SCCOL nCol, SCROW nRow ) const;
diff --git a/sc/source/core/data/column.cxx b/sc/source/core/data/column.cxx
index 704bdffc02e8..77bf89a87bfb 100644
--- a/sc/source/core/data/column.cxx
+++ b/sc/source/core/data/column.cxx
@@ -2296,9 +2296,6 @@ bool ScColumn::HasEditCells(SCROW nStartRow, SCROW nEndRow, SCROW& rFirst)
     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)
     {
@@ -2313,51 +2310,7 @@ bool ScColumn::HasEditCells(SCROW nStartRow, SCROW nEndRow, SCROW& rFirst)
             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;
-                }
-            }
-        }
-
+        sal_uInt8 nScriptType = GetRangeScriptType(itAttrPos, nRow, nRow);
         if (IsAmbiguousScriptNonZero(nScriptType))
         {
             rFirst = nRow;
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 6b91f284253f..c27f506c8067 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -1603,6 +1603,70 @@ sal_uInt8 ScColumn::GetScriptType( SCROW nRow ) const
     return maCellTextAttrs.get<sc::CellTextAttr>(nRow).mnScriptType;
 }
 
+sal_uInt8 ScColumn::GetRangeScriptType(
+    sc::CellTextAttrStoreType::iterator& itPos, SCROW nRow1, SCROW nRow2 )
+{
+    if (!ValidRow(nRow1) || !ValidRow(nRow2) || nRow1 > nRow2)
+        return 0;
+
+    SCROW nRow = nRow1;
+    std::pair<sc::CellTextAttrStoreType::iterator,size_t> aRet =
+        maCellTextAttrs.position(itPos, nRow1);
+
+    itPos = aRet.first; // Track the position of cell text attribute array.
+
+    sal_uInt8 nScriptType = 0;
+
+    if (itPos->type == sc::element_type_celltextattr)
+    {
+        sc::custom_celltextattr_block::iterator it = sc::custom_celltextattr_block::begin(*itPos->data);
+        sc::custom_celltextattr_block::iterator itEnd = sc::custom_celltextattr_block::end(*itPos->data);
+        std::advance(it, aRet.second);
+        for (; it != itEnd; ++it, ++nRow)
+        {
+            if (nRow > nRow2)
+                return nScriptType;
+
+            sc::CellTextAttr& rVal = *it;
+            UpdateScriptType(rVal, nRow);
+            nScriptType |= rVal.mnScriptType;
+        }
+    }
+    else
+    {
+        // Skip this whole block.
+        nRow += itPos->size - aRet.second;
+    }
+
+    while (nRow <= nRow2)
+    {
+        ++itPos;
+        if (itPos == maCellTextAttrs.end())
+            return nScriptType;
+
+        if (itPos->type != sc::element_type_celltextattr)
+        {
+            // Skip this whole block.
+            nRow += itPos->size;
+            continue;
+        }
+
+        sc::custom_celltextattr_block::iterator it = sc::custom_celltextattr_block::begin(*itPos->data);
+        sc::custom_celltextattr_block::iterator itEnd = sc::custom_celltextattr_block::end(*itPos->data);
+        for (; it != itEnd; ++it, ++nRow)
+        {
+            if (nRow > nRow2)
+                return nScriptType;
+
+            sc::CellTextAttr& rVal = *it;
+            UpdateScriptType(rVal, nRow);
+            nScriptType |= rVal.mnScriptType;
+        }
+    }
+
+    return nScriptType;
+}
+
 void ScColumn::SetScriptType( SCROW nRow, sal_uInt8 nType )
 {
     if (!ValidRow(nRow))
@@ -1999,7 +2063,7 @@ void ScColumn::EndListening( sc::EndListeningContext& rCxt, SCROW nRow, SvtListe
     rListener.EndListening(*pBC);
     if (!pBC->HasListeners())
         // There is no more listeners for this cell. Add it to the purge list for later purging.
-        rCxt.addEmptyBroadcasterPosition(nCol, nRow, nTab);
+        rCxt.addEmptyBroadcasterPosition(nTab, nCol, nRow);
 }
 
 void ScColumn::CompileDBFormula()
diff --git a/sc/source/core/data/column3.cxx b/sc/source/core/data/column3.cxx
index 2939edb97db8..a29f7916fe27 100644
--- a/sc/source/core/data/column3.cxx
+++ b/sc/source/core/data/column3.cxx
@@ -275,6 +275,43 @@ void ScColumn::DeleteRow( SCROW nStartRow, SCSIZE nSize )
     pDocument->SetAutoCalc( bOldAutoCalc );
 }
 
+void ScColumn::UpdateScriptType( sc::CellTextAttr& rAttr, SCROW nRow )
+{
+    if (rAttr.mnScriptType != SC_SCRIPTTYPE_UNKNOWN)
+        // Already updated. Nothing to do.
+        return;
+
+    // Script type not yet determined. Determine the real script
+    // type, and store it.
+    const ScPatternAttr* pPattern = GetPattern(nRow);
+    if (!pPattern)
+        return;
+
+    ScRefCellValue aCell;
+    ScAddress aPos(nCol, nRow, nTab);
+    aCell.assign(*pDocument, aPos);
+
+    const SfxItemSet* pCondSet = NULL;
+    ScConditionalFormatList* pCFList = pDocument->GetCondFormList(nTab);
+    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);
+    }
+
+    SvNumberFormatter* pFormatter = pDocument->GetFormatTable();
+
+    OUString aStr;
+    Color* pColor;
+    sal_uLong nFormat = pPattern->GetNumberFormat(pFormatter, pCondSet);
+    ScCellFormat::GetString(aCell, nFormat, aStr, &pColor, *pFormatter);
+
+    // Store the real script type to the array.
+    rAttr.mnScriptType = pDocument->GetStringScriptType(aStr);
+}
+
 namespace {
 
 bool isDate(const ScDocument& rDoc, const ScColumn& rCol, SCROW nRow)
diff --git a/sc/source/core/data/columnspanset.cxx b/sc/source/core/data/columnspanset.cxx
index de785395e4c0..ea4f7060dbc6 100644
--- a/sc/source/core/data/columnspanset.cxx
+++ b/sc/source/core/data/columnspanset.cxx
@@ -15,6 +15,7 @@
 namespace sc {
 
 ColumnSpanSet::Action::~Action() {}
+void ColumnSpanSet::Action::startColumn(SCTAB /*nTab*/, SCCOL /*nCol*/) {}
 
 ColumnSpanSet::~ColumnSpanSet()
 {
@@ -30,11 +31,8 @@ ColumnSpanSet::~ColumnSpanSet()
     }
 }
 
-void ColumnSpanSet::set(SCCOL nCol, SCROW nRow, SCTAB nTab, bool bVal)
+ColumnSpanSet::ColumnSpansType& ColumnSpanSet::getColumnSpans(SCTAB nTab, SCCOL nCol)
 {
-    if (!ValidTab(nTab) || !ValidCol(nCol) || !ValidRow(nRow))
-        return;
-
     if (static_cast<size_t>(nTab) >= maDoc.size())
         maDoc.resize(nTab+1, NULL);
 
@@ -48,10 +46,27 @@ void ColumnSpanSet::set(SCCOL nCol, SCROW nRow, SCTAB nTab, bool bVal)
     if (!rTab[nCol])
         rTab[nCol] = new ColumnSpansType(0, MAXROW+1, false);
 
-    ColumnSpansType& rCol = *rTab[nCol];
+    return *rTab[nCol];
+}
+
+void ColumnSpanSet::set(SCTAB nTab, SCCOL nCol, SCROW nRow, bool bVal)
+{
+    if (!ValidTab(nTab) || !ValidCol(nCol) || !ValidRow(nRow))
+        return;
+
+    ColumnSpansType& rCol = getColumnSpans(nTab, nCol);
     rCol.insert_back(nRow, nRow+1, bVal);
 }
 
+void ColumnSpanSet::set(SCTAB nTab, SCCOL nCol, SCROW nRow1, SCROW nRow2, bool bVal)
+{
+    if (!ValidTab(nTab) || !ValidCol(nCol) || !ValidRow(nRow1) || !ValidRow(nRow2))
+        return;
+
+    ColumnSpansType& rCol = getColumnSpans(nTab, nCol);
+    rCol.insert_back(nRow1, nRow2+1, bVal);
+}
+
 void ColumnSpanSet::executeFromTop(Action& ac) const
 {
     for (size_t nTab = 0; nTab < maDoc.size(); ++nTab)
@@ -65,6 +80,7 @@ void ColumnSpanSet::executeFromTop(Action& ac) const
             if (!rTab[nCol])
                 continue;
 
+            ac.startColumn(nTab, nCol);
             ColumnSpansType& rCol = *rTab[nCol];
             ColumnSpansType::const_iterator it = rCol.begin(), itEnd = rCol.end();
             SCROW nRow1, nRow2;
@@ -94,6 +110,7 @@ void ColumnSpanSet::executeFromBottom(Action& ac) const
             if (!rTab[nCol])
                 continue;
 
+            ac.startColumn(nTab, nCol);
             ColumnSpansType& rCol = *rTab[nCol];
             ColumnSpansType::const_reverse_iterator it = rCol.rbegin(), itEnd = rCol.rend();
             SCROW nRow1, nRow2;
diff --git a/sc/source/core/data/documen6.cxx b/sc/source/core/data/documen6.cxx
index bd55fc4931b4..819b7a572bcc 100644
--- a/sc/source/core/data/documen6.cxx
+++ b/sc/source/core/data/documen6.cxx
@@ -33,6 +33,8 @@
 #include "poolhelp.hxx"
 #include "attrib.hxx"
 #include "globalnames.hxx"
+#include "columnspanset.hxx"
+#include "table.hxx"
 
 using namespace com::sun::star;
 
@@ -153,4 +155,60 @@ sal_uInt8 ScDocument::GetScriptType( SCCOL nCol, SCROW nRow, SCTAB nTab )
     return GetCellScriptType(aPos, nFormat);
 }
 
+namespace {
+
+class ScriptTypeAggregator : public sc::ColumnSpanSet::Action
+{
+    ScDocument& mrDoc;
+    sc::ColumnBlockPosition maBlockPos;
+    sal_uInt8 mnScriptType;
+
+public:
+    ScriptTypeAggregator(ScDocument& rDoc) : mrDoc(rDoc), mnScriptType(0) {}
+
+    virtual void startColumn(SCTAB nTab, SCCOL nCol)
+    {
+        mrDoc.InitColumnBlockPosition(maBlockPos, nTab, nCol);
+    }
+
+    virtual void execute(const ScAddress& rPos, SCROW nLength, bool bVal)
+    {
+        if (!bVal)
+            return;
+
+        mnScriptType |= mrDoc.GetRangeScriptType(maBlockPos, rPos, nLength);
+    };
+
+    sal_uInt8 getScriptType() const { return mnScriptType; }
+};
+
+}
+
+sal_uInt8 ScDocument::GetRangeScriptType(
+    sc::ColumnBlockPosition& rBlockPos, const ScAddress& rPos, SCROW nLength )
+{
+    if (!TableExists(rPos.Tab()))
+        return 0;
+
+    return maTabs[rPos.Tab()]->GetRangeScriptType(rBlockPos, rPos.Col(), rPos.Row(), rPos.Row()+nLength-1);
+}
+
+sal_uInt8 ScDocument::GetRangeScriptType( const ScRangeList& rRanges )
+{
+    sc::ColumnSpanSet aSet;
+    for (size_t i = 0, n = rRanges.size(); i < n; ++i)
+    {
+        const ScRange& rRange = *rRanges[i];
+        SCTAB nTab = rRange.aStart.Tab();
+        SCROW nRow1 = rRange.aStart.Row();
+        SCROW nRow2 = rRange.aEnd.Row();
+        for (SCCOL nCol = rRange.aStart.Col(); nCol <= rRange.aEnd.Col(); ++nCol)
+            aSet.set(nTab, nCol, nRow1, nRow2, true);
+    }
+
+    ScriptTypeAggregator aAction(*this);
+    aSet.executeFromTop(aAction);
+    return aAction.getScriptType();
+}
+
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/source/core/data/listenercontext.cxx b/sc/source/core/data/listenercontext.cxx
index 4d8afb3ddc08..a288494ef163 100644
--- a/sc/source/core/data/listenercontext.cxx
+++ b/sc/source/core/data/listenercontext.cxx
@@ -35,9 +35,9 @@ ScDocument& EndListeningContext::getDoc()
     return mrDoc;
 }
 
-void EndListeningContext::addEmptyBroadcasterPosition(SCCOL nCol, SCROW nRow, SCTAB nTab)
+void EndListeningContext::addEmptyBroadcasterPosition(SCTAB nTab, SCCOL nCol, SCROW nRow)
 {
-    maSet.set(nCol, nRow, nTab, true);
+    maSet.set(nTab, nCol, nRow, true);
 }
 
 void EndListeningContext::purgeEmptyBroadcasters()
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 4c50eaf6ddba..d1654a6d6ffc 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2097,6 +2097,15 @@ void ScTable::SetScriptType( SCCOL nCol, SCROW nRow, sal_uInt8 nType )
     aCol[nCol].SetScriptType(nRow, nType);
 }
 
+sal_uInt8 ScTable::GetRangeScriptType(
+    sc::ColumnBlockPosition& rBlockPos, SCCOL nCol, SCROW nRow1, SCROW nRow2 )
+{
+    if (!ValidCol(nCol))
+        return 0;
+
+    return aCol[nCol].GetRangeScriptType(rBlockPos.miCellTextAttrPos, nRow1, nRow2);
+}
+
 size_t ScTable::GetFormulaHash( SCCOL nCol, SCROW nRow ) const
 {
     if (!ValidCol(nCol))
diff --git a/sc/source/ui/view/viewfunc.cxx b/sc/source/ui/view/viewfunc.cxx
index e114c99bfbb2..631e09936394 100644
--- a/sc/source/ui/view/viewfunc.cxx
+++ b/sc/source/ui/view/viewfunc.cxx
@@ -823,17 +823,7 @@ sal_uInt8 ScViewFunc::GetSelectionScriptType()
     {
         ScRangeList aRanges;
         rMark.FillRangeListWithMarks( &aRanges, false );
-        size_t nCount = aRanges.size();
-        for ( size_t i=0; i < nCount; i++ )
-        {
-            ScRange aRange = *aRanges[i];
-            ScCellIterator aIter( pDoc, aRange );
-            for (bool bHas = aIter.first(); bHas; bHas = aIter.next())
-            {
-                nScript |= pDoc->GetScriptType(
-                    aIter.GetPos().Col(), aIter.GetPos().Row(), aIter.GetPos().Tab());
-            }
-        }
+        nScript = pDoc->GetRangeScriptType(aRanges);
     }
 
     if (nScript == 0)