[Libreoffice-commits] core.git: Branch 'private/kohei/calc-sort-fix' - sc/inc sc/source
Kohei Yoshida
kohei.yoshida at collabora.com
Mon Apr 21 21:37:04 PDT 2014
sc/inc/fstalgorithm.hxx | 60 ++++++++++++++----
sc/inc/table.hxx | 2
sc/source/core/data/table3.cxx | 136 +++++++++++++++++++++++++++++++++--------
3 files changed, 162 insertions(+), 36 deletions(-)
New commits:
commit 08ea01dd7e7314b971910857fdb87225e39d13e2
Author: Kohei Yoshida <kohei.yoshida at collabora.com>
Date: Tue Apr 22 00:36:40 2014 -0400
Handle reordering of row hidden and filtered flags during sort.
Only when the "keep query" flag is set.
Change-Id: Ia799f62ec53a08cfd92e93c546965002c030b324
diff --git a/sc/inc/fstalgorithm.hxx b/sc/inc/fstalgorithm.hxx
index 6b3385c..7ba30bc 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 79b30f9..34059f7 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 b1a40d0..a672303 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();
More information about the Libreoffice-commits
mailing list