Avoid using SwapRow() when sorting.
Instead, build a data table prior to sorting, swap rows in this data table
as we sort, then transfer the results back to the document in one step. This
significantly speeds up the sort performance.
Formula cells are yet to be handled. I'll work on that next.
Change-Id: I59bde1a243dc8940411d1a33eef147671b060cd0
diff --git a/sc/inc/cellvalues.hxx b/sc/inc/cellvalues.hxx
index d84553f..37eac7c 100644
--- a/sc/inc/cellvalues.hxx
+++ b/sc/inc/cellvalues.hxx
@@ -13,10 +13,12 @@
#include <address.hxx>
class ScColumn;
struct ScRefCellValue;
namespace sc {
struct CellValuesImpl;
struct CellTextAttr;
/**
* Think of this as a mini-ScColumn like storage that only stores cell
@@ -33,10 +35,21 @@ public:
CellValues();
~CellValues();
/**
* Transfer values from specified column. The transferred segment in the
* source column becomes empty after this call.
*
* @param rCol source column to transfer values from.
* @param nRow top row position in the source column.
* @param nLen length of the segment to transfer.
*/
void transferFrom( ScColumn& rCol, SCROW nRow, size_t nLen );
void transferTo( ScColumn& rCol, SCROW nRow );
void copyTo( ScColumn& rCol, SCROW nRow ) const;
void assign( const std::vector<double>& rVals );
void append( ScRefCellValue& rVal, const CellTextAttr* pAttr );
size_t size() const;
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index 717da5e..084461e 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -566,6 +566,7 @@ public:
void RegroupFormulaCells();
void TransferCellValuesTo( SCROW nRow, size_t nLen, sc::CellValues& rDest );
void TransferCellValuesFrom( SCROW nRow, sc::CellValues& rSrc );
void CopyCellValuesFrom( SCROW nRow, const sc::CellValues& rSrc );
#if DEBUG_COLUMN_STORAGE
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index ef4340c..ab3526d 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -916,6 +916,7 @@ public:
SCCOL nColDelta, SCROW nRowDelta );
void TransferCellValuesTo( SCCOL nCol, SCROW nRow, size_t nLen, sc::CellValues& rDest );
void TransferCellValuesFrom( SCCOL nCol, SCROW nRow, sc::CellValues& rSrc );
void CopyCellValuesFrom( SCCOL nCol, SCROW nRow, const sc::CellValues& rSrc );
#if DEBUG_COLUMN_STORAGE
diff --git a/sc/source/core/data/cellvalues.cxx b/sc/source/core/data/cellvalues.cxx
index 423fa26..38ce4e8 100644
--- a/sc/source/core/data/cellvalues.cxx
+++ b/sc/source/core/data/cellvalues.cxx
@@ -9,6 +9,7 @@
#include <cellvalues.hxx>
#include <column.hxx>
#include <cellvalue.hxx>
#include <cassert>
#include <boost/noncopyable.hpp>
@@ -37,6 +38,15 @@ void CellValues::transferFrom( ScColumn& rCol, SCROW nRow, size_t nLen )
rCol.maCellTextAttrs.transfer(nRow, nRow+nLen-1, mpImpl->maCellTextAttrs, 0);
}
void CellValues::transferTo( ScColumn& rCol, SCROW nRow )
{
assert(mpImpl->maCells.size() == mpImpl->maCellTextAttrs.size());
size_t nLen = mpImpl->maCells.size();
mpImpl->maCells.transfer(0, nLen-1, rCol.maCells, nRow);
mpImpl->maCellTextAttrs.transfer(0, nLen-1, rCol.maCellTextAttrs, nRow);
}
void CellValues::copyTo( ScColumn& rCol, SCROW nRow ) const
{
copyCellsTo(rCol, nRow);
@@ -54,6 +64,55 @@ void CellValues::assign( const std::vector<double>& rVals )
mpImpl->maCellTextAttrs.set(0, aDefaults.begin(), aDefaults.end());
}
void CellValues::append( ScRefCellValue& rVal, const CellTextAttr* pAttr )
{
assert(mpImpl->maCells.size() == mpImpl->maCellTextAttrs.size());
size_t n = mpImpl->maCells.size();
bool bAppendAttr = true;
switch (rVal.meType)
{
case CELLTYPE_STRING:
{
mpImpl->maCells.resize(n+1);
mpImpl->maCells.set(n, *rVal.mpString);
}
break;
case CELLTYPE_VALUE:
{
mpImpl->maCells.resize(n+1);
mpImpl->maCells.set(n, rVal.mfValue);
}
break;
case CELLTYPE_EDIT:
{
mpImpl->maCells.resize(n+1);
mpImpl->maCells.set(n, rVal.mpEditText->Clone());
}
break;
case CELLTYPE_FORMULA:
{
mpImpl->maCells.resize(n+1);
// TODO : Handle this.
}
default:
bAppendAttr = false;
}
if (bAppendAttr)
{
mpImpl->maCellTextAttrs.resize(n+1);
if (pAttr)
mpImpl->maCellTextAttrs.set(n, *pAttr);
else
mpImpl->maCellTextAttrs.set(n, CellTextAttr());
}
}
size_t CellValues::size() const
{
assert(mpImpl->maCells.size() == mpImpl->maCellTextAttrs.size());
diff --git a/sc/source/core/data/column4.cxx b/sc/source/core/data/column4.cxx
index 37a082e..2698f0b 100644
--- a/sc/source/core/data/column4.cxx
+++ b/sc/source/core/data/column4.cxx
@@ -289,6 +289,31 @@ void ScColumn::TransferCellValuesTo( SCROW nRow, size_t nLen, sc::CellValues& rD
BroadcastCells(aRows, SC_HINT_DATACHANGED);
}
void ScColumn::TransferCellValuesFrom( SCROW nRow, sc::CellValues& rSrc )
{
if (!ValidRow(nRow))
return;
SCROW nLastRow = nRow + rSrc.size() - 1;
if (nLastRow > MAXROW)
// Out of bound. Do nothing
return;
sc::CellStoreType::position_type aPos = maCells.position(nRow);
DetachFormulaCells(aPos, rSrc.size());
rSrc.transferTo(*this, nRow);
CellStorageModified();
std::vector<SCROW> aRows;
aRows.reserve(rSrc.size());
for (SCROW i = nRow; i <= nLastRow; ++i)
aRows.push_back(i);
BroadcastCells(aRows, SC_HINT_DATACHANGED);
}
void ScColumn::CopyCellValuesFrom( SCROW nRow, const sc::CellValues& rSrc )
{
if (!ValidRow(nRow))
diff --git a/sc/source/core/data/table3.cxx b/sc/source/core/data/table3.cxx
index 4b7bde2..bb6148f 100644
--- a/sc/source/core/data/table3.cxx
+++ b/sc/source/core/data/table3.cxx
@@ -56,6 +56,8 @@
#include "tokenarray.hxx"
#include "mtvcellfunc.hxx"
#include "columnspanset.hxx"
#include <stlalgorithm.hxx>
#include <cellvalues.hxx>
#include "svl/sharedstringpool.hxx"
@@ -63,6 +65,8 @@
#include <boost/scoped_ptr.hpp>
#include <boost/scoped_array.hpp>
#include <boost/unordered_set.hpp>
#include <boost/noncopyable.hpp>
#include <boost/ptr_container/ptr_vector.hpp>
using namespace ::com::sun::star;
@@ -215,9 +219,24 @@ IMPL_FIXEDMEMPOOL_NEWDEL( ScSortInfo )
// END OF STATIC DATA -----------------------------------------------------
class ScSortInfoArray
class ScSortInfoArray : boost::noncopyable
{
public:
struct Cell
{
ScRefCellValue maCell;
const sc::CellTextAttr* mpAttr;
Cell() : mpAttr(NULL) {}
};
typedef std::vector<Cell> RowType;
typedef std::vector<RowType*> RowsType;
private:
boost::scoped_ptr<RowsType> mpRows; /// row-wise data table for sort by row operation.
ScSortInfo*** pppInfo;
SCSIZE nCount;
SCCOLROW nStart;
@@ -237,35 +256,64 @@ public:
pppInfo[nSort] = ppInfo;
}
}
~ScSortInfoArray()
{
for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
{
ScSortInfo** ppInfo = pppInfo[nSort];
for ( SCSIZE j = 0; j < nCount; j++ )
delete ppInfo[j];
delete [] ppInfo;
}
delete[] pppInfo;
}
~ScSortInfoArray()
{
for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
{
ScSortInfo** ppInfo = pppInfo[nSort];
for ( SCSIZE j = 0; j < nCount; j++ )
delete ppInfo[j];
delete [] ppInfo;
}
delete[] pppInfo;
if (mpRows)
std::for_each(mpRows->begin(), mpRows->end(), ScDeleteObjectByPtr<RowType>());
}
ScSortInfo* Get( sal_uInt16 nSort, SCCOLROW nInd )
{ return (pppInfo[nSort])[ nInd - nStart ]; }
void Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
{
SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
{
ScSortInfo** ppInfo = pppInfo[nSort];
ScSortInfo* pTmp = ppInfo[n1];
ppInfo[n1] = ppInfo[n2];
ppInfo[n2] = pTmp;
}
}
void Swap( SCCOLROW nInd1, SCCOLROW nInd2 )
{
SCSIZE n1 = static_cast<SCSIZE>(nInd1 - nStart);
SCSIZE n2 = static_cast<SCSIZE>(nInd2 - nStart);
for ( sal_uInt16 nSort = 0; nSort < nUsedSorts; nSort++ )
{
ScSortInfo** ppInfo = pppInfo[nSort];
ScSortInfo* pTmp = ppInfo[n1];
ppInfo[n1] = ppInfo[n2];
ppInfo[n2] = pTmp;
}
if (mpRows)
{
// Swap rows in data table.
RowsType& rRows = *mpRows;
std::swap(rRows[nInd1], rRows[nInd2]);
}
}
sal_uInt16 GetUsedSorts() const { return nUsedSorts; }
ScSortInfo** GetFirstArray() const { return pppInfo[0]; }
SCCOLROW GetStart() const { return nStart; }
SCSIZE GetCount() const { return nCount; }
RowsType& InitDataRows( size_t nRowSize, size_t nColSize )
{
mpRows.reset(new RowsType);
mpRows->reserve(nRowSize);
for (size_t i = 0; i < nRowSize; ++i)
mpRows->push_back(new RowType(nColSize, Cell()));
return *mpRows;
}
RowsType* GetDataRows()
{
return mpRows.get();
}
};
ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
@@ -290,6 +338,25 @@ ScSortInfoArray* ScTable::CreateSortInfoArray( SCCOLROW nInd1, SCCOLROW nInd2 )
pInfo->nOrg = nRow;
}
}
// Filll row-wise data table.
ScSortInfoArray::RowsType& rRows = pArray->InitDataRows(
aSortParam.nRow2 - aSortParam.nRow1 + 1, aSortParam.nCol2 - aSortParam.nCol1 + 1);
for (SCCOL nCol = aSortParam.nCol1; nCol <= aSortParam.nCol2; ++nCol)
{
ScColumn& rCol = aCol[nCol];
sc::ColumnBlockConstPosition aBlockPos;
rCol.InitBlockPosition(aBlockPos);
for (SCROW nRow = aSortParam.nRow1; nRow <= aSortParam.nRow2; ++nRow)
{
ScSortInfoArray::RowType& rRow = *rRows[nRow-aSortParam.nRow1];
ScSortInfoArray::Cell& rCell = rRow[nCol-aSortParam.nCol1];
rCell.maCell = rCol.GetCellValue(aBlockPos, nRow);
rCell.mpAttr = rCol.GetCellTextAttr(aBlockPos, nRow);
}
}
}
else
{
@@ -348,35 +415,69 @@ void ScTable::DestroySortCollator()
void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
{
bool bByRow = aSortParam.bByRow;
SCSIZE nCount = pArray->GetCount();
size_t nCount = pArray->GetCount();
SCCOLROW nStart = pArray->GetStart();
ScSortInfo** ppInfo = pArray->GetFirstArray();
::std::vector<ScSortInfo*> aTable(nCount);
SCSIZE nPos;
for ( nPos = 0; nPos < nCount; nPos++ )
aTable[ppInfo[nPos]->nOrg - nStart] = ppInfo[nPos];
SCCOLROW nDest = nStart;
for ( nPos = 0; nPos < nCount; nPos++, nDest++ )
if (aSortParam.bByRow)
{
SCCOLROW nOrg = ppInfo[nPos]->nOrg;
if ( nDest != nOrg )
ScSortInfoArray::RowsType* pRows = pArray->GetDataRows();
assert(pRows); // In sort-by-row mode we must have data rows already populated.
// Cells in the data rows only reference values in the document. Make
// a copy before updating the document.
size_t nColCount = aSortParam.nCol2 - aSortParam.nCol1 + 1;
boost::ptr_vector<sc::CellValues> aSortedCols;
aSortedCols.reserve(nColCount);
for (size_t i = 0; i < nColCount; ++i)
aSortedCols.push_back(new sc::CellValues);
for (size_t i = 0; i < pRows->size(); ++i)
{
if ( bByRow )
SwapRow( nDest, nOrg );
else
SwapCol( static_cast<SCCOL>(nDest), static_cast<SCCOL>(nOrg) );
// neue Position des weggeswapten eintragen
ScSortInfo* p = ppInfo[nPos];
p->nOrg = nDest;
::std::swap(p, aTable[nDest-nStart]);
p->nOrg = nOrg;
::std::swap(p, aTable[nOrg-nStart]);
OSL_ENSURE( p == ppInfo[nPos], "SortReorder: nOrg MisMatch" );
ScSortInfoArray::RowType* pRow = (*pRows)[i];
for (size_t nCol = 0; nCol < pRow->size(); ++nCol)
{
ScSortInfoArray::Cell& rCell = (*pRow)[nCol];
sc::CellValues& rStore = aSortedCols.at(nCol);
rStore.append(rCell.maCell, rCell.mpAttr);
}
if (pProgress)
pProgress->SetStateOnPercent(i);
}
if(pProgress)
pProgress->SetStateOnPercent( nPos );
for (size_t i = 0, n = aSortedCols.size(); i < n; ++i)
{
sc::CellValues& rSortedCol = aSortedCols[i];
TransferCellValuesFrom(i+aSortParam.nCol1, aSortParam.nRow1, rSortedCol);
}
}
else
{
std::vector<ScSortInfo*> aTable(nCount);
SCSIZE nPos;
for ( nPos = 0; nPos < nCount; nPos++ )
aTable[ppInfo[nPos]->nOrg - nStart] = ppInfo[nPos];
SCCOLROW nDest = nStart;
for ( nPos = 0; nPos < nCount; nPos++, nDest++ )
{
SCCOLROW nOrg = ppInfo[nPos]->nOrg;
if ( nDest != nOrg )
{
SwapCol( static_cast<SCCOL>(nDest), static_cast<SCCOL>(nOrg) );
// neue Position des weggeswapten eintragen
ScSortInfo* p = ppInfo[nPos];
p->nOrg = nDest;
::std::swap(p, aTable[nDest-nStart]);
p->nOrg = nOrg;
::std::swap(p, aTable[nOrg-nStart]);
OSL_ENSURE( p == ppInfo[nPos], "SortReorder: nOrg MisMatch" );
}
if(pProgress)
pProgress->SetStateOnPercent( nPos );
}
}
}
diff --git a/sc/source/core/data/table7.cxx b/sc/source/core/data/table7.cxx
index 48aa0a4..928c109 100644
--- a/sc/source/core/data/table7.cxx
+++ b/sc/source/core/data/table7.cxx
@@ -72,6 +72,14 @@ void ScTable::TransferCellValuesTo( SCCOL nCol, SCROW nRow, size_t nLen, sc::Cel
aCol[nCol].TransferCellValuesTo(nRow, nLen, rDest);
}
void ScTable::TransferCellValuesFrom( SCCOL nCol, SCROW nRow, sc::CellValues& rSrc )
{
if (!ValidCol(nCol))
return;
aCol[nCol].TransferCellValuesFrom(nRow, rSrc);
}
void ScTable::CopyCellValuesFrom( SCCOL nCol, SCROW nRow, const sc::CellValues& rSrc )
{
if (!ValidCol(nCol))
