Apply sorted patterns as ranges instead of row-by-row.

This scrapes off additional 2.2 seconds.

Change-Id: I08ae67f45946721d722be7183270d7bcf01f96b0

2 files changed, 86 insertions, 3 deletions

diff --git a/sc/inc/fstalgorithm.hxx b/sc/inc/fstalgorithm.hxx
index 8a50ae0f4a45..08d68d4e7812 100644
--- a/sc/inc/fstalgorithm.hxx
+++ b/sc/inc/fstalgorithm.hxx
@@ -44,6 +44,35 @@ void buildSpan(
     }
 }
 
+template<typename _Key, typename _Val, typename _Span>
+void buildSpanWithValue(
+    std::vector<_Span>& rSpans,
+    typename mdds::flat_segment_tree<_Key,_Val>::const_iterator it,
+    typename mdds::flat_segment_tree<_Key,_Val>::const_iterator itEnd, const _Key* pStart )
+{
+    _Key nLastPos = it->first;
+    _Val nLastVal = it->second;
+    for (++it; it != itEnd; ++it)
+    {
+        _Key nThisPos = it->first;
+        _Val nThisVal = it->second;
+
+        if (nLastVal)
+        {
+            _Key nIndex1 = nLastPos;
+            _Key nIndex2 = nThisPos-1;
+
+            if (!pStart || *pStart < nIndex1)
+                rSpans.push_back(_Span(nIndex1, nIndex2, nLastVal));
+            else if (*pStart <= nIndex2)
+                rSpans.push_back(_Span(*pStart, nIndex2, nLastVal));
+        }
+
+        nLastPos = nThisPos;
+        nLastVal = nThisVal;
+    }
+}
+
 /**
  * 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'
@@ -61,6 +90,25 @@ std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree
     return aSpans;
 }
 
+/**
+ * Convert a flat_segment_tree structure into an array of ranges with
+ * values.  Only those ranges whose value is evaluated to be true will be
+ * included.  The value type must be something that supports bool operator.
+ * The span type must support a constructor that takes a start key, an end
+ * key and a value in this order.
+ */
+template<typename _Key, typename _Val, typename _Span>
+std::vector<_Span> toSpanArrayWithValue( const mdds::flat_segment_tree<_Key,_Val>& rTree )
+{
+    typedef mdds::flat_segment_tree<_Key,_Val> FstType;
+
+    std::vector<_Span> aSpans;
+
+    typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
+    buildSpanWithValue<_Key,_Val,_Span>(aSpans, it, itEnd, NULL);
+    return aSpans;
+}
+
 template<typename _Key, typename _Span>
 std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree, _Key nStartPos )
 {
diff --git a/sc/source/core/data/table3.cxx b/sc/source/core/data/table3.cxx
index 77ecb69b3ec4..bedbb6235c8f 100644
--- a/sc/source/core/data/table3.cxx
+++ b/sc/source/core/data/table3.cxx
@@ -69,6 +69,7 @@
 #include <boost/unordered_set.hpp>
 #include <boost/noncopyable.hpp>
 #include <boost/ptr_container/ptr_vector.hpp>
+#include <mdds/flat_segment_tree.hpp>
 
 using namespace ::com::sun::star;
 
@@ -422,17 +423,28 @@ namespace {
 
 struct SortedColumn : boost::noncopyable
 {
+    typedef mdds::flat_segment_tree<SCROW, const ScPatternAttr*> PatRangeType;
 
     sc::CellStoreType maCells;
     sc::CellTextAttrStoreType maCellTextAttrs;
     sc::BroadcasterStoreType maBroadcasters;
     sc::CellNoteStoreType maCellNotes;
 
+    PatRangeType maPatterns;
+    PatRangeType::const_iterator miPatternPos;
+
     SortedColumn( size_t nTopEmptyRows ) :
         maCells(nTopEmptyRows),
         maCellTextAttrs(nTopEmptyRows),
         maBroadcasters(nTopEmptyRows),
-        maCellNotes(nTopEmptyRows) {}
+        maCellNotes(nTopEmptyRows),
+        maPatterns(0, MAXROWCOUNT, NULL),
+        miPatternPos(maPatterns.begin()) {}
+
+    void setPattern( SCROW nRow, const ScPatternAttr* pPat )
+    {
+        miPatternPos = maPatterns.insert(miPatternPos, nRow, nRow+1, pPat).first;
+    }
 };
 
 struct SortedRowFlags
@@ -461,6 +473,16 @@ struct SortedRowFlags
     }
 };
 
+struct PatternSpan
+{
+    SCROW mnRow1;
+    SCROW mnRow2;
+    const ScPatternAttr* mpPattern;
+
+    PatternSpan( SCROW nRow1, SCROW nRow2, const ScPatternAttr* pPat ) :
+        mnRow1(nRow1), mnRow2(nRow2), mpPattern(pPat) {}
+};
+
 }
 
 bool ScTable::IsSortCollatorGlobal() const
@@ -595,9 +617,8 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
                 else
                     rNoteStore.push_back_empty();
 
-                // Set formats to the document directly.
                 if (rCell.mpPattern)
-                    aCol[aCellPos.Col()].SetPattern(aCellPos.Row(), *rCell.mpPattern, true);
+                    aSortedCols.at(j).setPattern(aCellPos.Row(), rCell.mpPattern);
             }
 
             if (pArray->IsKeepQuery())
@@ -649,6 +670,20 @@ void ScTable::SortReorder( ScSortInfoArray* pArray, ScProgress* pProgress )
                 aCol[nThisCol].UpdateNoteCaptions(nRow1, nRow2);
             }
 
+            {
+                // Get all row spans where the pattern is not NULL.
+                std::vector<PatternSpan> aSpans =
+                    sc::toSpanArrayWithValue<SCROW,const ScPatternAttr*,PatternSpan>(
+                        aSortedCols[i].maPatterns);
+
+                std::vector<PatternSpan>::iterator it = aSpans.begin(), itEnd = aSpans.end();
+                for (; it != itEnd; ++it)
+                {
+                    assert(it->mpPattern); // should never be NULL.
+                    aCol[nThisCol].SetPatternArea(it->mnRow1, it->mnRow2, *it->mpPattern, true);
+                }
+            }
+
             aCol[nThisCol].CellStorageModified();
         }