Use mdds::flat_segment_tree to store row flags.

Much less memory footprint & better scalability.

Change-Id: Idef9afe5fa6e247e59fb949d4c9955fab4f669dc

4 files changed, 99 insertions, 68 deletions

diff --git a/sc/inc/dpcachetable.hxx b/sc/inc/dpcachetable.hxx
index 5f29711b15ed..c0d06250a6ee 100644
--- a/sc/inc/dpcachetable.hxx
+++ b/sc/inc/dpcachetable.hxx
@@ -38,7 +38,8 @@
 #include <boost/unordered_set.hpp>
 #include <boost/shared_ptr.hpp>
 
-class Date;
+#include <mdds/flat_segment_tree.hpp>
+
 class ScDPItemData;
 class ScDPCache;
 class ScDocument;
@@ -132,7 +133,7 @@ public:
     /** Check whether a specified row is active or not.  When a row is active,
         it is used in calculation of the results data.  A row becomes inactive
         when it is filtered out by page field. */
-    bool isRowActive(sal_Int32 nRow) const;
+    bool isRowActive(sal_Int32 nRow, sal_Int32* pLastRow = NULL) const;
 
     /** Set filter on/off flag to each row to control visibility.  The caller
         must ensure that the table is filled before calling this function. */
@@ -175,11 +176,15 @@ private:
     bool isRowQualified(sal_Int32 nRow, const ::std::vector<Criterion>& rCriteria, const ::boost::unordered_set<sal_Int32>& rRepeatIfEmptyDims) const;
 
 private:
+    typedef mdds::flat_segment_tree<SCROW, bool> RowFlagType;
+
     /** unique field entires for each field (column). */
     ::std::vector< ::std::vector<SCROW> > maFieldEntries;
 
-    /** Row flags. The first row below the header row has the index of 0. */
-    ::std::vector<RowFlag> maRowFlags;
+    /** Rows visible by standard filter query. */
+    RowFlagType maShowByFilter;
+    /** Rows visible by page dimension filtering. */
+    RowFlagType maShowByPage;
 
     const ScDPCache* mpCache;
 };
diff --git a/sc/source/core/data/dpcachetable.cxx b/sc/source/core/data/dpcachetable.cxx
index 7c5a41f6a430..11ac85fac2e9 100644
--- a/sc/source/core/data/dpcachetable.cxx
+++ b/sc/source/core/data/dpcachetable.cxx
@@ -125,7 +125,7 @@ ScDPCacheTable::Criterion::Criterion() :
 // ----------------------------------------------------------------------------
 
 ScDPCacheTable::ScDPCacheTable(const ScDPCache* pCache) :
-    mpCache(pCache)
+    maShowByFilter(0, MAXROW+1, false), maShowByPage(0, MAXROW+1, true), mpCache(pCache)
 {
 }
 
@@ -152,29 +152,26 @@ void ScDPCacheTable::fillTable(
     if (nRowCount <= 0 || nColCount <= 0)
         return;
 
-    maRowFlags.clear();
-    maRowFlags.reserve(nRowCount);
+    maShowByFilter.clear();
+    maShowByPage.clear();
 
     // Process the non-empty data rows.
     for (SCROW nRow = 0; nRow < nDataSize; ++nRow)
     {
-        maRowFlags.push_back(RowFlag());
         if (!getCache()->ValidQuery(nRow, rQuery))
             continue;
 
         if (bIgnoreEmptyRows && getCache()->IsRowEmpty(nRow))
             continue;
 
-        maRowFlags.back().mbShowByFilter = true;
+        maShowByFilter.insert_back(nRow, nRow+1, true);
     }
 
     // Process the trailing empty rows.
-    for (SCROW nRow = nDataSize; nRow < nRowCount; ++nRow)
-    {
-        maRowFlags.push_back(RowFlag());
-        if (!bIgnoreEmptyRows)
-            maRowFlags.back().mbShowByFilter = true;
-    }
+    if (!bIgnoreEmptyRows)
+        maShowByFilter.insert_back(nDataSize, nRowCount, true);
+
+    maShowByFilter.build_tree();
 
     // Initialize field entries container.
     maFieldEntries.clear();
@@ -189,11 +186,25 @@ void ScDPCacheTable::fillTable(
             continue;
 
         std::vector<SCROW> aAdded(nMemCount, -1);
-
+        bool bShow = false;
+        SCROW nEndSegment = -1;
         for (SCROW nRow = 0; nRow < nRowCount; ++nRow)
         {
-            if (!maRowFlags[nRow].mbShowByFilter)
+            if (nRow > nEndSegment)
+            {
+                if (!maShowByFilter.search_tree(nRow, bShow, NULL, &nEndSegment))
+                {
+                    OSL_FAIL("Tree search failed!");
+                    continue;
+                }
+                --nEndSegment; // End position is not inclusive. Move back one.
+            }
+
+            if (!bShow)
+            {
+                nRow = nEndSegment;
                 continue;
+            }
 
             SCROW nIndex = getCache()->GetItemDataId(nCol, nRow, bRepeatIfEmpty);
             SCROW nOrder = getOrder(nCol, nIndex);
@@ -214,63 +225,66 @@ void ScDPCacheTable::fillTable()
    if (nRowCount <= 0 || nColCount <= 0)
         return;
 
-    maRowFlags.clear();
-    maRowFlags.reserve(nRowCount);
-
-    for (SCROW nRow = 0; nRow < nRowCount; ++nRow)
-    {
-        maRowFlags.push_back(RowFlag());
-        maRowFlags.back().mbShowByFilter = true;
-    }
-
-    // Initialize field entries container.
-    maFieldEntries.clear();
-    maFieldEntries.reserve(nColCount);
-
-    // Data rows
-    for (SCCOL nCol = 0; nCol < nColCount; ++nCol)
-    {
-        maFieldEntries.push_back( vector<SCROW>() );
-        SCROW nMemCount = getCache()->GetDimMemberCount( nCol );
-        if (!nMemCount)
-            continue;
-
-        std::vector<SCROW> aAdded(nMemCount, -1);
-
-        for (SCROW nRow = 0; nRow < nRowCount; ++nRow)
-        {
-            SCROW nIndex = getCache()->GetItemDataId(nCol, nRow, false);
-            SCROW nOrder = getOrder(nCol, nIndex);
-            aAdded[nOrder] = nIndex;
-        }
-        for (SCROW nRow = 0; nRow < nMemCount; ++nRow)
-        {
-            if (aAdded[nRow] != -1)
-                maFieldEntries.back().push_back(aAdded[nRow]);
-        }
-    }
+   maShowByFilter.clear();
+   maShowByPage.clear();
+   maShowByFilter.insert_front(0, nRowCount, true);
+
+   // Initialize field entries container.
+   maFieldEntries.clear();
+   maFieldEntries.reserve(nColCount);
+
+   // Data rows
+   for (SCCOL nCol = 0; nCol < nColCount; ++nCol)
+   {
+       maFieldEntries.push_back( vector<SCROW>() );
+       SCROW nMemCount = getCache()->GetDimMemberCount( nCol );
+       if (!nMemCount)
+           continue;
+
+       std::vector<SCROW> aAdded(nMemCount, -1);
+
+       for (SCROW nRow = 0; nRow < nRowCount; ++nRow)
+       {
+           SCROW nIndex = getCache()->GetItemDataId(nCol, nRow, false);
+           SCROW nOrder = getOrder(nCol, nIndex);
+           aAdded[nOrder] = nIndex;
+       }
+       for (SCROW nRow = 0; nRow < nMemCount; ++nRow)
+       {
+           if (aAdded[nRow] != -1)
+               maFieldEntries.back().push_back(aAdded[nRow]);
+       }
+   }
 }
 
-bool ScDPCacheTable::isRowActive(sal_Int32 nRow) const
+bool ScDPCacheTable::isRowActive(sal_Int32 nRow, sal_Int32* pLastRow) const
 {
-    if (nRow < 0 || static_cast<size_t>(nRow) >= maRowFlags.size())
-        // row index out of bound
-        return false;
+    bool bFilter = false, bPage = true;
+    SCROW nLastRowFilter = MAXROW, nLastRowPage = MAXROW;
+    maShowByFilter.search_tree(nRow, bFilter, NULL, &nLastRowFilter);
+    maShowByPage.search_tree(nRow, bPage, NULL, &nLastRowPage);
+    if (pLastRow)
+    {
+        // Return the last row of current segment.
+        *pLastRow = nLastRowFilter < nLastRowPage ? nLastRowFilter : nLastRowPage;
+        *pLastRow -= 1; // End position is not inclusive. Move back one.
+    }
 
-    return maRowFlags[nRow].isActive();
+    return bFilter && bPage;
 }
 
 void ScDPCacheTable::filterByPageDimension(const vector<Criterion>& rCriteria, const boost::unordered_set<sal_Int32>& rRepeatIfEmptyDims)
 {
-    sal_Int32 nRowSize = getRowSize();
-    if (nRowSize != static_cast<sal_Int32>(maRowFlags.size()))
+    SCROW nRowSize = getRowSize();
+
+    maShowByPage.clear();
+    for (SCROW nRow = 0; nRow < nRowSize; ++nRow)
     {
-        // sizes of the two tables differ!
-        return;
+        bool bShow = isRowQualified(nRow, rCriteria, rRepeatIfEmptyDims);
+        maShowByPage.insert_back(nRow, nRow+1, bShow);
     }
 
-    for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow)
-        maRowFlags[nRow].mbShowByPage = isRowQualified(nRow, rCriteria, rRepeatIfEmptyDims);
+    maShowByPage.build_tree();
 }
 
 const ScDPItemData* ScDPCacheTable::getCell(SCCOL nCol, SCROW nRow, bool bRepeatIfEmpty) const
@@ -340,12 +354,15 @@ void ScDPCacheTable::filterTable(const vector<Criterion>& rCriteria, Sequence< S
     }
     tableData.push_back(headerRow);
 
-
     for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow)
     {
-        if (!maRowFlags[nRow].isActive())
+        sal_Int32 nLastRow;
+        if (!isRowActive(nRow, &nLastRow))
+        {
             // This row is filtered out.
+            nRow = nLastRow;
             continue;
+        }
 
         if (!isRowQualified(nRow, rCriteria, rRepeatIfEmptyDims))
             continue;
@@ -385,7 +402,8 @@ SCROW ScDPCacheTable::getOrder(long nDim, SCROW nIndex) const
 void ScDPCacheTable::clear()
 {
     maFieldEntries.clear();
-    maRowFlags.clear();
+    maShowByFilter.clear();
+    maShowByPage.clear();
 }
 
 bool ScDPCacheTable::empty() const
diff --git a/sc/source/core/data/dpgroup.cxx b/sc/source/core/data/dpgroup.cxx
index 232f7fc9a1e2..aba278556336 100644
--- a/sc/source/core/data/dpgroup.cxx
+++ b/sc/source/core/data/dpgroup.cxx
@@ -762,8 +762,12 @@ void ScDPGroupTableData::CalcResults(CalcInfo& rInfo, bool bAutoShow)
     sal_Int32 nRowSize = rCacheTable.getRowSize();
     for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow)
     {
-        if (!rCacheTable.isRowActive(nRow))
+        sal_Int32 nLastRow;
+        if (!rCacheTable.isRowActive(nRow, &nLastRow))
+        {
+            nRow = nLastRow;
             continue;
+        }
 
         CalcRowData aData;
         FillRowDataFromCacheTable(nRow, rCacheTable, rInfo, aData);
diff --git a/sc/source/core/data/dptabdat.cxx b/sc/source/core/data/dptabdat.cxx
index 39f1b4f31ef0..f150d8d3ef23 100644
--- a/sc/source/core/data/dptabdat.cxx
+++ b/sc/source/core/data/dptabdat.cxx
@@ -221,8 +221,12 @@ void ScDPTableData::CalcResultsFromCacheTable(const ScDPCacheTable& rCacheTable,
     sal_Int32 nRowSize = rCacheTable.getRowSize();
     for (sal_Int32 nRow = 0; nRow < nRowSize; ++nRow)
     {
-        if (!rCacheTable.isRowActive(nRow))
+        sal_Int32 nLastRow;
+        if (!rCacheTable.isRowActive(nRow, &nLastRow))
+        {
+            nRow = nLastRow;
             continue;
+        }
 
         CalcRowData aData;
         FillRowDataFromCacheTable(nRow, rCacheTable, rInfo, aData);