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

4 files changed, 239 insertions, 46 deletions

diff --git a/sc/source/core/data/cellvalues.cxx b/sc/source/core/data/cellvalues.cxx
index 423fa26a15d5..38ce4e8631e1 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 37a082ed04ba..2698f0b5f647 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 4b7bde22aece..bb6148fa2e61 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
+            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);
+        }
+
+        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" );
+                // 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 );
         }
-        if(pProgress)
-            pProgress->SetStateOnPercent( nPos );
     }
 }
 
diff --git a/sc/source/core/data/table7.cxx b/sc/source/core/data/table7.cxx
index 48aa0a49ec4b..928c1092db05 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))