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

7 files changed, 254 insertions, 46 deletions

diff --git a/sc/inc/cellvalues.hxx b/sc/inc/cellvalues.hxx
index d84553fbdce6..37eac7cd133f 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 717da5ef3273..084461e65668 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 ef4340c6316c..ab3526d4e375 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 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))