Improve filtering performance to an acceptable level.

Note: this change requires mdds 0.5.0.

7 files changed, 71 insertions, 50 deletions

diff --git a/sc/inc/segmenttree.hxx b/sc/inc/segmenttree.hxx
index edbcd4f0e19a..f46e87373dbc 100644
--- a/sc/inc/segmenttree.hxx
+++ b/sc/inc/segmenttree.hxx
@@ -75,13 +75,14 @@ public:
     ScFlatBoolRowSegments(const ScFlatBoolRowSegments& r);
     ~ScFlatBoolRowSegments();
 
-    void setTrue(SCROW nRow1, SCROW nRow2);
-    void setFalse(SCROW nRow1, SCROW nRow2);
+    bool setTrue(SCROW nRow1, SCROW nRow2);
+    bool setFalse(SCROW nRow1, SCROW nRow2);
     bool getValue(SCROW nRow);
     bool getRangeData(SCROW nRow, RangeData& rData);
     void removeSegment(SCROW nRow1, SCROW nRow2);
     void insertSegment(SCROW nRow, SCROW nSize, bool bSkipStartBoundary);
 
+    void enableTreeSearch(bool bEnable);
     SCROW findLastNotOf(bool bValue) const;
 
 private:
@@ -103,12 +104,13 @@ public:
     ScFlatBoolColSegments(const ScFlatBoolColSegments& r);
     ~ScFlatBoolColSegments();
 
-    void setTrue(SCCOL nCol1, SCCOL nCol2);
-    void setFalse(SCCOL nCol1, SCCOL nCol2);
+    bool setTrue(SCCOL nCol1, SCCOL nCol2);
+    bool setFalse(SCCOL nCol1, SCCOL nCol2);
     bool getRangeData(SCCOL nCol, RangeData& rData);
     void removeSegment(SCCOL nCol1, SCCOL nCol2);
     void insertSegment(SCCOL nCol, SCCOL nSize, bool bSkipStartBoundary);
 
+    void enableTreeSearch(bool bEnable);
     void setInsertFromBack(bool bInsertFromBack);
 
 private:
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 87ba63fdcc2e..7267a35b4c5c 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -730,8 +730,8 @@ public:
     bool        HasHiddenRows(SCROW nStartRow, SCROW nEndRow) const;
     bool        ColHidden(SCCOL nCol, SCCOL& rLastCol) const;
     bool        ColHidden(SCCOL nCol, SCCOL* pFirstCol = NULL, SCCOL* pLastCol = NULL) const;
-    void        SetRowHidden(SCROW nStartRow, SCROW nEndRow, bool bHidden);
-    void        SetColHidden(SCCOL nStartCol, SCCOL nEndCol, bool bHidden);
+    bool        SetRowHidden(SCROW nStartRow, SCROW nEndRow, bool bHidden);
+    bool        SetColHidden(SCCOL nStartCol, SCCOL nEndCol, bool bHidden);
     void        CopyColHidden(ScTable& rTable, SCCOL nStartCol, SCCOL nEndCol);
     void        CopyRowHidden(ScTable& rTable, SCROW nStartRow, SCROW nEndRow);
     void        CopyRowHeight(ScTable& rSrcTable, SCROW nStartRow, SCROW nEndRow, SCROW nSrcOffset);
diff --git a/sc/source/core/data/segmenttree.cxx b/sc/source/core/data/segmenttree.cxx
index 86e903780eb1..9d302844cbe5 100644
--- a/sc/source/core/data/segmenttree.cxx
+++ b/sc/source/core/data/segmenttree.cxx
@@ -57,7 +57,7 @@ public:
     ScFlatSegmentsImpl(const ScFlatSegmentsImpl& r);
     ~ScFlatSegmentsImpl();
 
-    void setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
+    bool setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue);
     ValueType getValue(SCCOLROW nPos);
     ExtValueType getSumValue(SCCOLROW nPos1, SCCOLROW nPos2);
     bool getRangeData(SCCOLROW nPos, RangeData& rData);
@@ -111,12 +111,16 @@ ScFlatSegmentsImpl<_ValueType, _ExtValueType>::~ScFlatSegmentsImpl()
 }
 
 template<typename _ValueType, typename _ExtValueType>
-void ScFlatSegmentsImpl<_ValueType, _ExtValueType>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
+bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::setValue(SCCOLROW nPos1, SCCOLROW nPos2, ValueType nValue)
 {
+    ::std::pair<typename fst_type::const_iterator, bool> ret;
     if (mbInsertFromBack)
-        maSegments.insert_back(nPos1, nPos2+1, nValue);
+        ret = maSegments.insert_back(nPos1, nPos2+1, nValue);
     else
-        maSegments.insert_front(nPos1, nPos2+1, nValue);
+        ret = maSegments.insert(maItr, nPos1, nPos2+1, nValue);
+
+    maItr = ret.first;
+    return ret.second;
 }
 
 template<typename _ValueType, typename _ExtValueType>
@@ -182,8 +186,13 @@ bool ScFlatSegmentsImpl<_ValueType, _ExtValueType>::getRangeData(SCCOLROW nPos,
     else
     {
         // Conduct leaf-node only search.  Faster when searching between range insertion.
-        if (!maSegments.search(nPos, nValue, &nPos1, &nPos2))
+        ::std::pair<typename fst_type::const_iterator, bool> ret =
+            maSegments.search(maItr, nPos, nValue, &nPos1, &nPos2);
+
+        if (!ret.second)
             return false;
+
+        maItr = ret.first;
     }
 
     rData.mnPos1 = nPos1;
@@ -268,18 +277,18 @@ public:
     {
     }
 
-    void setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
-    void setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
+    bool setTrue(SCCOLROW nPos1, SCCOLROW nPos2);
+    bool setFalse(SCCOLROW nPos1, SCCOLROW nPos2);
 };
 
-void ScFlatBoolSegmentsImpl::setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
+bool ScFlatBoolSegmentsImpl::setTrue(SCCOLROW nPos1, SCCOLROW nPos2)
 {
-    setValue(nPos1, nPos2, true);
+    return setValue(nPos1, nPos2, true);
 }
 
-void ScFlatBoolSegmentsImpl::setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
+bool ScFlatBoolSegmentsImpl::setFalse(SCCOLROW nPos1, SCCOLROW nPos2)
 {
-    setValue(nPos1, nPos2, false);
+    return setValue(nPos1, nPos2, false);
 }
 
 // ============================================================================
@@ -362,14 +371,14 @@ ScFlatBoolRowSegments::~ScFlatBoolRowSegments()
 {
 }
 
-void ScFlatBoolRowSegments::setTrue(SCROW nRow1, SCROW nRow2)
+bool ScFlatBoolRowSegments::setTrue(SCROW nRow1, SCROW nRow2)
 {
-    mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
+    return mpImpl->setTrue(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 }
 
-void ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
+bool ScFlatBoolRowSegments::setFalse(SCROW nRow1, SCROW nRow2)
 {
-    mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
+    return mpImpl->setFalse(static_cast<SCCOLROW>(nRow1), static_cast<SCCOLROW>(nRow2));
 }
 
 bool ScFlatBoolRowSegments::getValue(SCROW nRow)
@@ -399,6 +408,11 @@ void ScFlatBoolRowSegments::insertSegment(SCROW nRow, SCROW nSize, bool bSkipSta
     mpImpl->insertSegment(static_cast<SCCOLROW>(nRow), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
 }
 
+void ScFlatBoolRowSegments::enableTreeSearch(bool bEnable)
+{
+    mpImpl->enableTreeSearch(bEnable);
+}
+
 SCROW ScFlatBoolRowSegments::findLastNotOf(bool bValue) const
 {
     return static_cast<SCROW>(mpImpl->findLastNotOf(bValue));
@@ -420,14 +434,14 @@ ScFlatBoolColSegments::~ScFlatBoolColSegments()
 {
 }
 
-void ScFlatBoolColSegments::setTrue(SCCOL nCol1, SCCOL nCol2)
+bool ScFlatBoolColSegments::setTrue(SCCOL nCol1, SCCOL nCol2)
 {
-    mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
+    return mpImpl->setTrue(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 }
 
-void ScFlatBoolColSegments::setFalse(SCCOL nCol1, SCCOL nCol2)
+bool ScFlatBoolColSegments::setFalse(SCCOL nCol1, SCCOL nCol2)
 {
-    mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
+    return mpImpl->setFalse(static_cast<SCCOLROW>(nCol1), static_cast<SCCOLROW>(nCol2));
 }
 
 bool ScFlatBoolColSegments::getRangeData(SCCOL nCol, RangeData& rData)
@@ -452,6 +466,11 @@ void ScFlatBoolColSegments::insertSegment(SCCOL nCol, SCCOL nSize, bool bSkipSta
     mpImpl->insertSegment(static_cast<SCCOLROW>(nCol), static_cast<SCCOLROW>(nSize), bSkipStartBoundary);
 }
 
+void ScFlatBoolColSegments::enableTreeSearch(bool bEnable)
+{
+    mpImpl->enableTreeSearch(bEnable);
+}
+
 void ScFlatBoolColSegments::setInsertFromBack(bool bInsertFromBack)
 {
     mpImpl->setInsertFromBack(bInsertFromBack);
diff --git a/sc/source/core/data/table2.cxx b/sc/source/core/data/table2.cxx
index f18cb15bbcfc..bc58b90b1522 100644
--- a/sc/source/core/data/table2.cxx
+++ b/sc/source/core/data/table2.cxx
@@ -778,29 +778,19 @@ void ScTable::CopyToTable(SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2,
                     // Hidden flags.
                     for (SCROW i = nRow1; i <= nRow2; ++i)
                     {
-                        SCROW nThisLastRow, nDestLastRow;
-                        bool bThisHidden = RowHidden(i, NULL, &nThisLastRow);
-                        bool bDestHidden = pDestTab->RowHidden(i, NULL, &nDestLastRow);
-
-                        // If the segment sizes differ, we take the shorter segment of the two.
-                        SCROW nLastRow = ::std::min(nThisLastRow, nDestLastRow);
+                        SCROW nLastRow;
+                        bool bHidden = RowHidden(i, NULL, &nLastRow);
                         if (nLastRow >= nRow2)
                             // the last row shouldn't exceed the upper bound the caller specified.
                             nLastRow = nRow2;
-
-                        pDestTab->SetRowHidden(i, nLastRow, bThisHidden);
-
-                        bool bThisHiddenChange = (bThisHidden != bDestHidden);
-                        if (bThisHiddenChange && pCharts)
-                        {
+                        bool bHiddenChanged = pDestTab->SetRowHidden(i, nLastRow, bHidden);
+                        if (bHiddenChanged && pCharts)
                             // Hidden flags differ.
                             pCharts->SetRangeDirty(ScRange(0, i, nTab, MAXCOL, nLastRow, nTab));
-                        }
 
-                        if (bThisHiddenChange)
+                        if (bHiddenChanged)
                             bFlagChange = true;
 
-                        // Jump to the last row of the identical flag segment.
                         i = nLastRow;
                     }
 
diff --git a/sc/source/core/data/table3.cxx b/sc/source/core/data/table3.cxx
index 403c793cf9b0..c147c262cf9c 100644
--- a/sc/source/core/data/table3.cxx
+++ b/sc/source/core/data/table3.cxx
@@ -60,6 +60,7 @@
 #include "cellform.hxx"
 #include "postit.hxx"
 #include "queryparam.hxx"
+#include "segmenttree.hxx"
 
 #include <vector>
 
@@ -1617,6 +1618,8 @@ static void lcl_PrepareQuery( ScDocument* pDoc, ScTable* pTab, ScQueryParam& rPa
 
 SCSIZE ScTable::Query(ScQueryParam& rParamOrg, BOOL bKeepSub)
 {
+    mpHiddenRows->enableTreeSearch(false);
+
     ScQueryParam    aParam( rParamOrg );
     ScStrCollection aScStrCollection;
     StrData*        pStrData = NULL;
@@ -1722,6 +1725,7 @@ SCSIZE ScTable::Query(ScQueryParam& rParamOrg, BOOL bKeepSub)
 
     delete[] pSpecial;
     SetDrawPageSize();
+    mpHiddenRows->enableTreeSearch(true);
     return nCount;
 }
 
diff --git a/sc/source/core/data/table5.cxx b/sc/source/core/data/table5.cxx
index 04c43a2eaf27..c4a472b99dce 100644
--- a/sc/source/core/data/table5.cxx
+++ b/sc/source/core/data/table5.cxx
@@ -602,20 +602,26 @@ bool ScTable::ColHidden(SCCOL nCol, SCCOL* pFirstCol, SCCOL* pLastCol) const
     return aData.mbValue;
 }
 
-void ScTable::SetRowHidden(SCROW nStartRow, SCROW nEndRow, bool bHidden)
+bool ScTable::SetRowHidden(SCROW nStartRow, SCROW nEndRow, bool bHidden)
 {
+    bool bChanged = false;
     if (bHidden)
-        mpHiddenRows->setTrue(nStartRow, nEndRow);
+        bChanged = mpHiddenRows->setTrue(nStartRow, nEndRow);
     else
-        mpHiddenRows->setFalse(nStartRow, nEndRow);
+        bChanged = mpHiddenRows->setFalse(nStartRow, nEndRow);
+
+    return bChanged;
 }
 
-void ScTable::SetColHidden(SCCOL nStartCol, SCCOL nEndCol, bool bHidden)
+bool ScTable::SetColHidden(SCCOL nStartCol, SCCOL nEndCol, bool bHidden)
 {
+    bool bChanged = false;
     if (bHidden)
-        mpHiddenCols->setTrue(nStartCol, nEndCol);
+        bChanged = mpHiddenCols->setTrue(nStartCol, nEndCol);
     else
-        mpHiddenCols->setFalse(nStartCol, nEndCol);
+        bChanged = mpHiddenCols->setFalse(nStartCol, nEndCol);
+
+    return bChanged;
 }
 
 void ScTable::CopyColHidden(ScTable& rTable, SCCOL nStartCol, SCCOL nEndCol)
diff --git a/sc/source/filter/excel/colrowst.cxx b/sc/source/filter/excel/colrowst.cxx
index 1a2308068a3c..aa63702c3921 100644
--- a/sc/source/filter/excel/colrowst.cxx
+++ b/sc/source/filter/excel/colrowst.cxx
@@ -143,7 +143,7 @@ void XclImpColRowSettings::SetHeight( SCROW nScRow, sal_uInt16 nHeight )
     bool bDefHeight = ::get_flag( nHeight, EXC_ROW_FLAGDEFHEIGHT ) || (nRawHeight == 0);
     maRowHeights.insert_back(nScRow, nScRow+1, nRawHeight);
     sal_uInt8 nFlagVal = 0;
-    if (!maRowFlags.search(nScRow, nFlagVal))
+    if (!maRowFlags.search(nScRow, nFlagVal).second)
         return;
 
     ::set_flag(nFlagVal, EXC_COLROW_USED);
@@ -166,7 +166,7 @@ void XclImpColRowSettings::SetRowSettings( SCROW nScRow, sal_uInt16 nHeight, sal
     SetHeight(nScRow, nHeight);
 
     sal_uInt8 nFlagVal = 0;
-    if (!maRowFlags.search(nScRow, nFlagVal))
+    if (!maRowFlags.search(nScRow, nFlagVal).second)
         return;
 
     if (::get_flag(nFlags, EXC_ROW_UNSYNCED))
@@ -184,7 +184,7 @@ void XclImpColRowSettings::SetManualRowHeight( SCROW nScRow )
         return;
 
     sal_uInt8 nFlagVal = 0;
-    if (!maRowFlags.search(nScRow, nFlagVal))
+    if (!maRowFlags.search(nScRow, nFlagVal).second)
         return;
 
     ::set_flag(nFlagVal, EXC_COLROW_MAN);
@@ -325,7 +325,7 @@ void XclImpColRowSettings::ConvertHiddenFlags( SCTAB nScTab )
     if (nLastXLRow < MAXROW)
     {
         bool bHidden = false;
-        if (!maHiddenRows.search(nLastXLRow, bHidden))
+        if (!maHiddenRows.search(nLastXLRow, bHidden).second)
             return;
 
         maHiddenRows.insert_back(nLastXLRow, MAXROWCOUNT, bHidden);