Reimplement ScMarkData::GetMarkedRowSpans() to use flat_segment_tree directly.

Change-Id: I90a1d4b3ae2e6aff9a7926b5842bc85ac172683d

8 files changed, 123 insertions, 35 deletions

diff --git a/sc/inc/columnspanset.hxx b/sc/inc/columnspanset.hxx
index 62e96a8a41bd..7da98967ad28 100644
--- a/sc/inc/columnspanset.hxx
+++ b/sc/inc/columnspanset.hxx
@@ -33,6 +33,14 @@ struct RowSpan
     RowSpan(SCROW nRow1, SCROW nRow2);
 };
 
+struct ColRowSpan
+{
+    SCCOLROW mnStart;
+    SCCOLROW mnEnd;
+
+    ColRowSpan(SCCOLROW nStart, SCCOLROW nEnd);
+};
+
 /**
  * Structure that stores segments of boolean flags per column, and perform
  * custom action on those segments.
diff --git a/sc/inc/fstalgorithm.hxx b/sc/inc/fstalgorithm.hxx
new file mode 100644
index 000000000000..6b3385c5aa0d
--- /dev/null
+++ b/sc/inc/fstalgorithm.hxx
@@ -0,0 +1,52 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#ifndef SC_FSTALGORITHM_HXX
+#define SC_FSTALGORITHM_HXX
+
+#include <mdds/flat_segment_tree.hpp>
+#include <vector>
+
+namespace sc {
+
+/**
+ * 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'
+ * value.
+ */
+template<typename _Key, typename _Span>
+std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree )
+{
+    typedef mdds::flat_segment_tree<_Key,bool> FstType;
+
+    std::vector<_Span> aSpans;
+
+    typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
+    _Key nLastPos = it->first;
+    bool bLastVal = it->second;
+    for (++it; it != itEnd; ++it)
+    {
+        _Key nThisPos = it->first;
+        bool bThisVal = it->second;
+
+        if (bLastVal)
+            aSpans.push_back(_Span(nLastPos, nThisPos-1));
+
+        nLastPos = nThisPos;
+        bLastVal = bThisVal;
+    }
+
+    return aSpans;
+}
+
+}
+
+#endif
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/markdata.hxx b/sc/inc/markdata.hxx
index 943419d62308..0a5b19fc9bde 100644
--- a/sc/inc/markdata.hxx
+++ b/sc/inc/markdata.hxx
@@ -29,6 +29,7 @@
 namespace sc {
 
 struct RowSpan;
+struct ColRowSpan;
 
 }
 
@@ -109,7 +110,7 @@ public:
     SCCOLROW    GetMarkColumnRanges( SCCOLROW* pRanges );
     SCCOLROW    GetMarkRowRanges( SCCOLROW* pRanges );
 
-    void GetMarkedRowSpans( SCTAB nTab, std::vector<sc::RowSpan>& rSpans );
+    std::vector<sc::ColRowSpan> GetMarkedRowSpans( SCTAB nTab ) const;
 
     bool        IsColumnMarked( SCCOL nCol ) const;
     bool        IsRowMarked( SCROW nRow ) const;
diff --git a/sc/qa/unit/ucalc.cxx b/sc/qa/unit/ucalc.cxx
index 5811dc06c865..8341ef9515f0 100644
--- a/sc/qa/unit/ucalc.cxx
+++ b/sc/qa/unit/ucalc.cxx
@@ -55,6 +55,7 @@
 #include "editutil.hxx"
 #include <asciiopt.hxx>
 #include <impex.hxx>
+#include <columnspanset.hxx>
 
 #include "formula/IFunctionDescription.hxx"
 
@@ -608,6 +609,38 @@ void Test::testRangeList()
     m_pDoc->DeleteTab(0);
 }
 
+void Test::testMarkData()
+{
+    ScMarkData aMarkData;
+
+    // Empty mark. Nothing is selected.
+    std::vector<sc::ColRowSpan> aSpans = aMarkData.GetMarkedRowSpans(0);
+    CPPUNIT_ASSERT_MESSAGE("Span should be empty.", aSpans.empty());
+
+    // Select B3:F7.
+    aMarkData.SetMarkArea(ScRange(1,2,0,5,6,0));
+    aSpans = aMarkData.GetMarkedRowSpans(0);
+    CPPUNIT_ASSERT_MESSAGE("There should be one selected row span.", aSpans.size() == 1);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(2), aSpans[0].mnStart);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(6), aSpans[0].mnEnd);
+
+    // Select A11:B13.
+    aMarkData.SetMultiMarkArea(ScRange(0,10,0,1,12,0));
+    aSpans = aMarkData.GetMarkedRowSpans(0);
+    CPPUNIT_ASSERT_MESSAGE("There should be 2 selected row spans.", aSpans.size() == 2);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(2), aSpans[0].mnStart);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(6), aSpans[0].mnEnd);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(10), aSpans[1].mnStart);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(12), aSpans[1].mnEnd);
+
+    // Select C8:C10.
+    aMarkData.SetMultiMarkArea(ScRange(2,7,0,2,9,0));
+    aSpans = aMarkData.GetMarkedRowSpans(0);
+    CPPUNIT_ASSERT_MESSAGE("There should be one selected row span.", aSpans.size() == 1);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(2), aSpans[0].mnStart);
+    CPPUNIT_ASSERT_EQUAL(static_cast<SCCOLROW>(12), aSpans[0].mnEnd);
+}
+
 void Test::testInput()
 {
     OUString aTabName("foo");
diff --git a/sc/qa/unit/ucalc.hxx b/sc/qa/unit/ucalc.hxx
index 48234e5c94a3..6bbaad0157a3 100644
--- a/sc/qa/unit/ucalc.hxx
+++ b/sc/qa/unit/ucalc.hxx
@@ -82,6 +82,7 @@ public:
     void testCollator();
     void testSharedStringPool();
     void testRangeList();
+    void testMarkData();
     void testInput();
     void testDocStatistics();
 
@@ -320,6 +321,7 @@ public:
     CPPUNIT_TEST(testCollator);
     CPPUNIT_TEST(testSharedStringPool);
     CPPUNIT_TEST(testRangeList);
+    CPPUNIT_TEST(testMarkData);
     CPPUNIT_TEST(testInput);
     CPPUNIT_TEST(testDocStatistics);
     CPPUNIT_TEST(testDataEntries);
diff --git a/sc/source/core/data/columnspanset.cxx b/sc/source/core/data/columnspanset.cxx
index efa51b5a2707..1aa57ba11c94 100644
--- a/sc/source/core/data/columnspanset.cxx
+++ b/sc/source/core/data/columnspanset.cxx
@@ -15,6 +15,7 @@
 #include "mtvfunctions.hxx"
 #include "markdata.hxx"
 #include "rangelst.hxx"
+#include <fstalgorithm.hxx>
 
 #include <algorithm>
 
@@ -22,6 +23,8 @@ namespace sc {
 
 RowSpan::RowSpan(SCROW nRow1, SCROW nRow2) : mnRow1(nRow1), mnRow2(nRow2) {}
 
+ColRowSpan::ColRowSpan(SCCOLROW nStart, SCCOLROW nEnd) : mnStart(nStart), mnEnd(nEnd) {}
+
 ColumnSpanSet::ColumnType::ColumnType(SCROW nStart, SCROW nEnd, bool bInit) :
     maSpans(nStart, nEnd+1, bInit), miPos(maSpans.begin()) {}
 
@@ -262,22 +265,7 @@ void SingleColumnSpanSet::getRows(std::vector<SCROW> &rRows) const
 
 void SingleColumnSpanSet::getSpans(SpansType& rSpans) const
 {
-    SpansType aSpans;
-    ColumnSpansType::const_iterator it = maSpans.begin(), itEnd = maSpans.end();
-    SCROW nLastRow = it->first;
-    bool bLastVal = it->second;
-    for (++it; it != itEnd; ++it)
-    {
-        SCROW nThisRow = it->first;
-        bool bThisVal = it->second;
-
-        if (bLastVal)
-            aSpans.push_back(RowSpan(nLastRow, nThisRow-1));
-
-        nLastRow = nThisRow;
-        bLastVal = bThisVal;
-    }
-
+    SpansType aSpans = toSpanArray<SCROW,RowSpan>(maSpans);
     rSpans.swap(aSpans);
 }
 
diff --git a/sc/source/core/data/markdata.cxx b/sc/source/core/data/markdata.cxx
index 556df504ca3a..37693777a8c1 100644
--- a/sc/source/core/data/markdata.cxx
+++ b/sc/source/core/data/markdata.cxx
@@ -21,6 +21,9 @@
 #include "markarr.hxx"
 #include "rangelst.hxx"
 #include <columnspanset.hxx>
+#include <fstalgorithm.hxx>
+
+#include <mdds/flat_segment_tree.hpp>
 
 // STATIC DATA -----------------------------------------------------------
 
@@ -548,24 +551,24 @@ SCCOLROW ScMarkData::GetMarkRowRanges( SCCOLROW* pRanges )
     return nRangeCnt;
 }
 
-void ScMarkData::GetMarkedRowSpans( SCTAB nTab, std::vector<sc::RowSpan>& rSpans )
+std::vector<sc::ColRowSpan> ScMarkData::GetMarkedRowSpans( SCTAB nTab ) const
 {
-    std::vector<sc::RowSpan> aSpans;
+    typedef mdds::flat_segment_tree<SCCOLROW, bool> SpansType;
 
-    if (bMarked)
-        MarkToMulti();
+    ScRangeList aRanges = GetMarkedRanges();
+    SpansType aSpans(0, MAXROW+1, false);
+    SpansType::const_iterator itPos = aSpans.begin();
 
-    if (!bMultiMarked)
+    for (size_t i = 0, n = aRanges.size(); i < n; ++i)
     {
-        rSpans.swap(aSpans);
-        return;
-    }
+        const ScRange& r = *aRanges[i];
+        if (r.aStart.Tab() != nTab)
+            continue;
 
-    sc::SingleColumnSpanSet aMarkedRows;
-    for (SCCOL nCol = aMultiRange.aStart.Col(); nCol <= aMultiRange.aEnd.Col(); ++nCol)
-        aMarkedRows.scan(*this, nTab, nCol);
+        itPos = aSpans.insert(itPos, r.aStart.Row(), r.aEnd.Row()+1, true).first;
+    }
 
-    aMarkedRows.getSpans(rSpans);
+    return sc::toSpanArray<SCCOLROW,sc::ColRowSpan>(aSpans);
 }
 
 bool ScMarkData::IsAllMarked( const ScRange& rRange ) const
diff --git a/sc/source/ui/view/viewfun2.cxx b/sc/source/ui/view/viewfun2.cxx
index 2a0b118179b7..00e0462c0436 100644
--- a/sc/source/ui/view/viewfun2.cxx
+++ b/sc/source/ui/view/viewfun2.cxx
@@ -109,12 +109,13 @@ sal_Bool ScViewFunc::AdjustBlockHeight( sal_Bool bPaint, ScMarkData* pMarkData )
         pMarkData = &GetViewData()->GetMarkData();
 
     ScDocument* pDoc = pDocSh->GetDocument();
-    std::vector<sc::RowSpan> aMarkedRows;
-    pMarkData->GetMarkedRowSpans(GetViewData()->GetTabNo(), aMarkedRows);
+    std::vector<sc::ColRowSpan> aMarkedRows =
+        pMarkData->GetMarkedRowSpans(GetViewData()->GetTabNo());
+
     if (aMarkedRows.empty())
     {
         SCROW nCurRow = GetViewData()->GetCurY();
-        aMarkedRows.push_back(sc::RowSpan(nCurRow, nCurRow));
+        aMarkedRows.push_back(sc::ColRowSpan(nCurRow, nCurRow));
     }
 
     double nPPTX = GetViewData()->GetPPTX();
@@ -138,11 +139,11 @@ sal_Bool ScViewFunc::AdjustBlockHeight( sal_Bool bPaint, ScMarkData* pMarkData )
         SCTAB nTab = *itr;
         bool bChanged = false;
         SCROW nPaintY = 0;
-        std::vector<sc::RowSpan>::const_iterator itRows = aMarkedRows.begin(), itRowsEnd = aMarkedRows.end();
+        std::vector<sc::ColRowSpan>::const_iterator itRows = aMarkedRows.begin(), itRowsEnd = aMarkedRows.end();
         for (; itRows != itRowsEnd; ++itRows)
         {
-            SCROW nStartNo = itRows->mnRow1;
-            SCROW nEndNo = itRows->mnRow2;
+            SCROW nStartNo = itRows->mnStart;
+            SCROW nEndNo = itRows->mnEnd;
             if (pDoc->SetOptimalHeight(aCxt, nStartNo, nEndNo, nTab))
             {
                 if (!bChanged)