Handle reordering of row hidden and filtered flags during sort.

Only when the "keep query" flag is set.

Change-Id: Ia799f62ec53a08cfd92e93c546965002c030b324

3 files changed, 162 insertions, 36 deletions

diff --git a/sc/inc/fstalgorithm.hxx b/sc/inc/fstalgorithm.hxx
index 20972ef05641..8a50ae0f4a45 100644
--- a/sc/inc/fstalgorithm.hxx
+++ b/sc/inc/fstalgorithm.hxx
@@ -15,6 +15,35 @@
 
 namespace sc {
 
+template<typename _Key, typename _Span>
+void buildSpan(
+    std::vector<_Span>& rSpans,
+    typename mdds::flat_segment_tree<_Key,bool>::const_iterator it,
+    typename mdds::flat_segment_tree<_Key,bool>::const_iterator itEnd, const _Key* pStart )
+{
+    _Key nLastPos = it->first;
+    bool bLastVal = it->second;
+    for (++it; it != itEnd; ++it)
+    {
+        _Key nThisPos = it->first;
+        bool bThisVal = it->second;
+
+        if (bLastVal)
+        {
+            _Key nIndex1 = nLastPos;
+            _Key nIndex2 = nThisPos-1;
+
+            if (!pStart || *pStart < nIndex1)
+                rSpans.push_back(_Span(nIndex1, nIndex2));
+            else if (*pStart <= nIndex2)
+                rSpans.push_back(_Span(*pStart, nIndex2));
+        }
+
+        nLastPos = nThisPos;
+        bLastVal = bThisVal;
+    }
+}
+
 /**
  * Convert a flat_segment_tree structure whose value type is boolean, into
  * an array of ranges that corresponds with the segments that have a 'true'
@@ -28,20 +57,29 @@ std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree
     std::vector<_Span> aSpans;
 
     typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
-    _Key nLastPos = it->first;
-    bool bLastVal = it->second;
-    for (++it; it != itEnd; ++it)
-    {
-        _Key nThisPos = it->first;
-        bool bThisVal = it->second;
+    buildSpan<_Key,_Span>(aSpans, it, itEnd, NULL);
+    return aSpans;
+}
 
-        if (bLastVal)
-            aSpans.push_back(_Span(nLastPos, nThisPos-1));
+template<typename _Key, typename _Span>
+std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree, _Key nStartPos )
+{
+    typedef mdds::flat_segment_tree<_Key,bool> FstType;
 
-        nLastPos = nThisPos;
-        bLastVal = bThisVal;
-    }
+    std::vector<_Span> aSpans;
+    if (!rTree.is_tree_valid())
+        return aSpans;
+
+    bool bThisVal = false;
+    std::pair<typename FstType::const_iterator, bool> r =
+        rTree.search_tree(nStartPos, bThisVal);
+
+    if (!r.second)
+        // Tree search failed.
+        return aSpans;
 
+    typename FstType::const_iterator it = r.first, itEnd = rTree.end();
+    buildSpan<_Key,_Span>(aSpans, it, itEnd, &nStartPos);
     return aSpans;
 }
 
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index 413152eadd1c..b29bb8dfeb0c 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -1011,7 +1011,7 @@ private:
         ScRefCellValue& rCell2, SCCOL nCell2Col, SCROW nCell2Row ) const;
     short       Compare(SCCOLROW nIndex1, SCCOLROW nIndex2) const;
     short       Compare( ScSortInfoArray*, SCCOLROW nIndex1, SCCOLROW nIndex2) const;
-    ScSortInfoArray*    CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 );
+    ScSortInfoArray* CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2, bool bKeepQuery );
     void        QuickSort( ScSortInfoArray*, SCsCOLROW nLo, SCsCOLROW nHi);
     void        SortReorder( ScSortInfoArray*, ScProgress* );
 
diff --git a/sc/source/core/data/table3.cxx b/sc/source/core/data/table3.cxx
index b1a40d0e40b4..a672303acc5c 100644
--- a/sc/source/core/data/table3.cxx
+++ b/sc/source/core/data/table3.cxx
@@ -57,6 +57,7 @@
 #include "mtvcellfunc.hxx"
 #include "columnspanset.hxx"
 #include <stlalgorithm.hxx>
+#include <fstalgorithm.hxx>
 #include <listenercontext.hxx>
 #include <sharedformula.hxx>
 
@@ -234,8 +235,17 @@ public:
         Cell() : mpAttr(NULL), mpBroadcaster(NULL), mpNote(NULL), mpPattern(NULL) {}
     };
 
-    typedef std::vector<Cell> RowType;
-    typedef std::vector<RowType*> RowsType;
+    struct Row
+    {
+        std::vector<Cell> maCells;
+
+        bool mbHidden:1;
+        bool mbFiltered:1;
+
+        Row( size_t nColSize ) : maCells(nColSize, Cell()), mbHidden(false), mbFiltered(false) {}
+    };
+
+    typedef std::vector<Row*> RowsType;
 
 private:
     boost::scoped_ptr<RowsType> mpRows; /// row-wise data table for sort by row operation.
@@ -246,21 +256,24 @@ private:
     SCCOLROW        mnLastIndex; /// index of last non-empty cell position.
     sal_uInt16      nUsedSorts;
 
+    bool mbKeepQuery;
+
 public:
     ScSortInfoArray( sal_uInt16 nSorts, SCCOLROW nInd1, SCCOLROW nInd2 ) :
-            pppInfo( new ScSortInfo**[nSorts]),
-            nCount( nInd2 - nInd1 + 1 ), nStart( nInd1 ),
-            mnLastIndex(nInd2),
-            nUsedSorts( nSorts )
+        pppInfo( new ScSortInfo**[nSorts]),
+        nCount( nInd2 - nInd1 + 1 ), nStart( nInd1 ),
+        mnLastIndex(nInd2),
+        nUsedSorts(nSorts),
+        mbKeepQuery(false)
+    {
+        for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
         {
-            for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
-            {
-                ScSortInfo** ppInfo = new ScSortInfo* [nCount];
-                for ( SCSIZE j = 0; j < nCount; j++ )
-                    ppInfo[j] = new ScSortInfo;
-                pppInfo[nSort] = ppInfo;
-            }
+            ScSortInfo** ppInfo = new ScSortInfo* [nCount];
+            for ( SCSIZE j = 0; j < nCount; j++ )
+                ppInfo[j] = new ScSortInfo;
+            pppInfo[nSort] = ppInfo;
         }
+    }
 
     ~ScSortInfoArray()
     {
@@ -274,9 +287,13 @@ public:
         delete[] pppInfo;
 
         if (mpRows)
-            std::for_each(mpRows->begin(), mpRows->end(), ScDeleteObjectByPtr<RowType>());
+            std::for_each(mpRows->begin(), mpRows->end(), ScDeleteObjectByPtr<Row>());
     }
 
+    void SetKeepQuery( bool b ) { mbKeepQuery = b; }
+
+    bool IsKeepQuery() const { return mbKeepQuery; }
+
     ScSortInfo* Get( sal_uInt16 nSort, SCCOLROW nInd )
                     { return (pppInfo[nSort])[ nInd - nStart ]; }
 
@@ -311,7 +328,7 @@ public:
         mpRows.reset(new RowsType);
         mpRows->reserve(nRowSize);
         for (size_t i = 0; i < nRowSize; ++i)
-            mpRows->push_back(new RowType(nColSize, Cell()));
+            mpRows->push_back(new Row(nColSize));
 
         return *mpRows;
     }
@@ -322,12 +339,14 @@ public:
     }
 };
 
-ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
+ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2, bool bKeepQuery )
 {
     sal_uInt16 nUsedSorts = 1;
     while ( nUsedSorts < aSortParam.GetSortKeyCount() && aSortParam.maKeyState[nUsedSorts].bDoSort )
         nUsedSorts++;
     ScSortInfoArray* pArray = new ScSortInfoArray( nUsedSorts, nInd1, nInd2 );
+    pArray->SetKeepQuery(bKeepQuery);
+
     if ( aSortParam.bByRow )
     {
         for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
@@ -355,8 +374,8 @@ ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
             rCol.InitBlockPosition(aBlockPos);
             for (SCROW nRow = nInd1; nRow <= nInd2; ++nRow)
             {
-                ScSortInfoArray::RowType& rRow = *rRows[nRow-nInd1];
-                ScSortInfoArray::Cell& rCell = rRow[nCol-aSortParam.nCol1];
+                ScSortInfoArray::Row& rRow = *rRows[nRow-nInd1];
+                ScSortInfoArray::Cell& rCell = rRow.maCells[nCol-aSortParam.nCol1];
 
                 rCell.maCell = rCol.GetCellValue(aBlockPos, nRow);
                 rCell.mpAttr = rCol.GetCellTextAttr(aBlockPos, nRow);
@@ -367,6 +386,16 @@ ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
                     rCell.mpPattern = rCol.GetPattern(nRow);
             }
         }
+
+        if (bKeepQuery)
+        {
+            for (SCROW nRow = nInd1; nRow <= nInd2; ++nRow)
+            {
+                ScSortInfoArray::Row& rRow = *rRows[nRow-nInd1];
+                rRow.mbHidden = RowHidden(nRow);
+                rRow.mbFiltered = RowFiltered(nRow);
+            }
+        }
     }
     else
     {
@@ -389,6 +418,7 @@ namespace {
 
 struct SortedColumn : boost::noncopyable
 {
+
     sc::CellStoreType maCells;
     sc::CellTextAttrStoreType maCellTextAttrs;
     sc::BroadcasterStoreType maBroadcasters;
@@ -401,6 +431,32 @@ struct SortedColumn : boost::noncopyable
         maCellNotes(nTopEmptyRows) {}
 };
 
+struct SortedRowFlags
+{
+    typedef mdds::flat_segment_tree<SCROW,bool> FlagsType;
+
+    FlagsType maRowsHidden;
+    FlagsType maRowsFiltered;
+    FlagsType::const_iterator miPosHidden;
+    FlagsType::const_iterator miPosFiltered;
+
+    SortedRowFlags() :
+        maRowsHidden(0, MAXROWCOUNT, false),
+        maRowsFiltered(0, MAXROWCOUNT, false),
+        miPosHidden(maRowsHidden.begin()),
+        miPosFiltered(maRowsFiltered.begin()) {}
+
+    void setRowHidden( SCROW nRow, bool b )
+    {
+        miPosHidden = maRowsHidden.insert(miPosHidden, nRow, nRow+1, b).first;
+    }
+
+    void setRowFiltered( SCROW nRow, bool b )
+    {
+        miPosFiltered = maRowsFiltered.insert(miPosFiltered, nRow, nRow+1, b).first;
+    }
+};
+
 }
 
 bool ScTable::IsSortCollatorGlobal() const
@@ -461,6 +517,7 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
 
         size_t nColCount = aSortParam.nCol2 - aSortParam.nCol1 + 1;
         boost::ptr_vector<SortedColumn> aSortedCols; // storage for copied cells.
+        SortedRowFlags aRowFlags;
         aSortedCols.reserve(nColCount);
         for (size_t i = 0; i < nColCount; ++i)
         {
@@ -472,12 +529,12 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
 
         for (size_t i = 0; i < pRows->size(); ++i)
         {
-            ScSortInfoArray::RowType* pRow = (*pRows)[i];
-            for (size_t j = 0; j < pRow->size(); ++j)
+            ScSortInfoArray::Row* pRow = (*pRows)[i];
+            for (size_t j = 0; j < pRow->maCells.size(); ++j)
             {
                 ScAddress aCellPos(aSortParam.nCol1 + j, nRow1 + i, nTab);
 
-                ScSortInfoArray::Cell& rCell = (*pRow)[j];
+                ScSortInfoArray::Cell& rCell = pRow->maCells[j];
 
                 sc::CellStoreType& rCellStore = aSortedCols.at(j).maCells;
                 switch (rCell.maCell.meType)
@@ -539,6 +596,14 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
                     aCol[aCellPos.Col()].SetPattern(aCellPos.Row(), *rCell.mpPattern, true);
             }
 
+            if (pArray->IsKeepQuery())
+            {
+                // Hidden and filtered flags are first converted to segments.
+                SCROW nRow = nRow1 + i;
+                aRowFlags.setRowHidden(nRow, pRow->mbHidden);
+                aRowFlags.setRowFiltered(nRow, pRow->mbFiltered);
+            }
+
             if (pProgress)
                 pProgress->SetStateOnPercent(i);
         }
@@ -583,6 +648,29 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
             aCol[nThisCol].CellStorageModified();
         }
 
+        if (pArray->IsKeepQuery())
+        {
+            aRowFlags.maRowsHidden.build_tree();
+            aRowFlags.maRowsFiltered.build_tree();
+
+            // Remove all flags in the range first.
+            SetRowHidden(nRow1, nRow2, false);
+            SetRowFiltered(nRow1, nRow2, false);
+
+            std::vector<sc::RowSpan> aSpans =
+                sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsHidden, nRow1);
+
+            std::vector<sc::RowSpan>::const_iterator it = aSpans.begin(), itEnd = aSpans.end();
+            for (; it != itEnd; ++it)
+                SetRowHidden(it->mnRow1, it->mnRow2, true);
+
+            aSpans = sc::toSpanArray<SCROW,sc::RowSpan>(aRowFlags.maRowsFiltered, nRow1);
+
+            it = aSpans.begin(), itEnd = aSpans.end();
+            for (; it != itEnd; ++it)
+                SetRowFiltered(it->mnRow1, it->mnRow2, true);
+        }
+
         // Attach all formula cells within sorted range, to have them start listening again.
         sc::StartListeningContext aStartListenCxt(*pDocument);
         AttachFormulaCells(
@@ -906,7 +994,7 @@ void ScTable::Sort(const ScSortParam& rSortParam, bool bKeepQuery, ScProgress* p
             if(pProgress)
                 pProgress->SetState( 0, nLastRow-nRow1 );
 
-            boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nRow1, nLastRow));
+            boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nRow1, nLastRow, bKeepQuery));
 
             if ( nLastRow - nRow1 > 255 )
                 DecoladeRow(pArray.get(), nRow1, nLastRow);
@@ -931,7 +1019,7 @@ void ScTable::Sort(const ScSortParam& rSortParam, bool bKeepQuery, ScProgress* p
             if(pProgress)
                 pProgress->SetState( 0, nLastCol-nCol1 );
 
-            boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nCol1, nLastCol));
+            boost::scoped_ptr<ScSortInfoArray> pArray(CreateSortInfoArray(nCol1, nLastCol, bKeepQuery));
 
             QuickSort(pArray.get(), nCol1, nLastCol);
             SortReorder(pArray.get(), pProgress);
@@ -1932,7 +2020,7 @@ void ScTable::TopTenQuery( ScQueryParam& rParam )
                     bSortCollatorInitialized = true;
                     InitSortCollator( aLocalSortParam );
                 }
-                ScSortInfoArray* pArray = CreateSortInfoArray( nRow1, rParam.nRow2 );
+                ScSortInfoArray* pArray = CreateSortInfoArray(nRow1, rParam.nRow2, bGlobalKeepQuery);
                 DecoladeRow( pArray, nRow1, rParam.nRow2 );
                 QuickSort( pArray, nRow1, rParam.nRow2 );
                 ScSortInfo** ppInfo = pArray->GetFirstArray();