Better algorithm to (re-)populate the cache.

With my test document, this brings the reload time down from 30 seconds
to 19 seconds.  I was expecting a much better outcome, but this is still
better than the current.

3 files changed, 135 insertions, 2 deletions

diff --git a/sc/inc/dpitemdata.hxx b/sc/inc/dpitemdata.hxx
index 10363bea48c5..e30eae3c156c 100644
--- a/sc/inc/dpitemdata.hxx
+++ b/sc/inc/dpitemdata.hxx
@@ -93,6 +93,8 @@ public:
 
     // exact equality
     bool operator==(const ScDPItemData& r) const;
+    bool operator!=(const ScDPItemData& r) const;
+    bool operator< (const ScDPItemData& r) const;
 
     ScDPItemData& operator= (const ScDPItemData& r);
 
diff --git a/sc/source/core/data/dpcache.cxx b/sc/source/core/data/dpcache.cxx
index dba8ef9b157a..caa51233ae43 100644
--- a/sc/source/core/data/dpcache.cxx
+++ b/sc/source/core/data/dpcache.cxx
@@ -320,6 +320,112 @@ void initFromCell(ScDocument* pDoc, SCCOL nCol, SCROW nRow, SCTAB nTab, ScDPItem
     }
 }
 
+struct Bucket
+{
+    ScDPItemData maValue;
+    SCROW mnOrderIndex;
+    SCROW mnDataIndex;
+    Bucket(const ScDPItemData& rValue, SCROW nOrder, SCROW nData) :
+        maValue(rValue), mnOrderIndex(nOrder), mnDataIndex(nData) {}
+};
+
+struct LessByValue : std::binary_function<Bucket, Bucket, bool>
+{
+    bool operator() (const Bucket& left, const Bucket& right) const
+    {
+        return left.maValue < right.maValue;
+    }
+};
+
+struct LessByDataIndex : std::binary_function<Bucket, Bucket, bool>
+{
+    bool operator() (const Bucket& left, const Bucket& right) const
+    {
+        return left.mnDataIndex < right.mnDataIndex;
+    }
+};
+
+struct EqualByValue : std::binary_function<Bucket, Bucket, bool>
+{
+    bool operator() (const Bucket& left, const Bucket& right) const
+    {
+        return left.maValue == right.maValue;
+    }
+};
+
+class PushBackValue : std::unary_function<Bucket, void>
+{
+    ScDPCache::ItemsType& mrItems;
+public:
+    PushBackValue(ScDPCache::ItemsType& _items) : mrItems(_items) {}
+    void operator() (const Bucket& v)
+    {
+        mrItems.push_back(v.maValue);
+    }
+};
+
+class PushBackOrderIndex : std::unary_function<Bucket, void>
+{
+    ScDPCache::IndexArrayType& mrData;
+public:
+    PushBackOrderIndex(ScDPCache::IndexArrayType& _items) : mrData(_items) {}
+    void operator() (const Bucket& v)
+    {
+        mrData.push_back(v.mnOrderIndex);
+    }
+};
+
+void processBuckets(std::vector<Bucket>& aBuckets, ScDPCache::Field& rField)
+{
+    if (aBuckets.empty())
+        return;
+
+    // Sort by the value.
+    std::sort(aBuckets.begin(), aBuckets.end(), LessByValue());
+
+    {
+        // Set order index such that unique values have identical index value.
+        SCROW nCurIndex = 0;
+        std::vector<Bucket>::iterator it = aBuckets.begin(), itEnd = aBuckets.end();
+        ScDPItemData aPrev = it->maValue;
+        it->mnOrderIndex = nCurIndex;
+        for (++it; it != itEnd; ++it)
+        {
+            if (aPrev != it->maValue)
+                ++nCurIndex;
+
+            it->mnOrderIndex = nCurIndex;
+            aPrev = it->maValue;
+        }
+    }
+
+    // Re-sort the bucket this time by the data index.
+    std::sort(aBuckets.begin(), aBuckets.end(), LessByDataIndex());
+
+    // Copy the order index series into the field object.
+    rField.maData.reserve(aBuckets.size());
+    std::for_each(aBuckets.begin(), aBuckets.end(), PushBackOrderIndex(rField.maData));
+
+    // Sort by the value again.
+    std::sort(aBuckets.begin(), aBuckets.end(), LessByValue());
+
+    // Unique by value.
+    std::vector<Bucket>::iterator itUniqueEnd =
+        std::unique(aBuckets.begin(), aBuckets.end(), EqualByValue());
+
+    // Copy the unique values into items.
+    std::vector<Bucket>::iterator itBeg = aBuckets.begin();
+    size_t nLen = distance(itBeg, itUniqueEnd);
+    rField.maItems.reserve(nLen);
+    std::for_each(itBeg, itUniqueEnd, PushBackValue(rField.maItems));
+
+    // The items are actually already sorted.  So, just insert a sequence
+    // of integers from 0 and up.
+    rField.maGlobalOrder.reserve(nLen);
+    for (size_t i = 0; i < nLen; ++i)
+        rField.maGlobalOrder.push_back(i);
+}
+
 }
 
 bool ScDPCache::InitFromDoc(ScDocument* pDoc, const ScRange& rRange)
@@ -350,12 +456,27 @@ bool ScDPCache::InitFromDoc(ScDocument* pDoc, const ScRange& rRange)
     for (sal_uInt16 nCol = nStartCol; nCol <= nEndCol; ++nCol)
     {
         AddLabel(createLabelString(pDoc, nCol, nStartRow, nDocTab));
-        for (SCROW nRow = nStartRow + 1; nRow <= nEndRow; ++nRow)
+        Field& rField = maFields[nCol];
+        std::vector<Bucket> aBuckets;
+        aBuckets.reserve(nEndRow-nStartRow); // skip the topmost label cell.
+
+        // Push back all original values.
+        SCROW nOffset = nStartRow + 1;
+        for (SCROW i = 0, n = nEndRow-nStartRow; i < n; ++i)
         {
+            SCROW nRow = i + nOffset;
             sal_uLong nNumFormat = 0;
             initFromCell(pDoc, nCol, nRow, nDocTab, aData, nNumFormat);
-            AddData(nCol - nStartCol, aData, nNumFormat);
+            aBuckets.push_back(Bucket(aData, 0, i));
+
+            if (!aData.IsEmpty())
+            {
+                maEmptyRows.insert_back(nRow, nRow+1, false);
+                rField.mnNumFormat = nNumFormat;
+            }
         }
+
+        processBuckets(aBuckets, rField);
     }
 
     PostInit();
diff --git a/sc/source/core/data/dpitemdata.cxx b/sc/source/core/data/dpitemdata.cxx
index 43c01cbcb096..5b89aef6e3b6 100644
--- a/sc/source/core/data/dpitemdata.cxx
+++ b/sc/source/core/data/dpitemdata.cxx
@@ -211,6 +211,16 @@ bool ScDPItemData::operator== (const ScDPItemData& r) const
     return GetString() == r.GetString();
 }
 
+bool ScDPItemData::operator!= (const ScDPItemData& r) const
+{
+    return !operator== (r);
+}
+
+bool ScDPItemData::operator< (const ScDPItemData& r) const
+{
+    return Compare(*this, r) == -1;
+}
+
 ScDPItemData& ScDPItemData::operator= (const ScDPItemData& r)
 {
     meType = r.meType;