[Libreoffice-commits] core.git: Branch 'distro/lhm/libreoffice-5-2+backports' - sc/inc sc/qa sc/source

Libreoffice Gerrit user logerrit at kemper.freedesktop.org
Thu Nov 1 18:33:05 UTC 2018


 sc/inc/markmulti.hxx            |    2 
 sc/qa/unit/mark_test.cxx        |  105 +++++++++++++++++++++++++++++++++++++++-
 sc/source/core/data/markarr.cxx |   47 +++++++++--------
 3 files changed, 129 insertions(+), 25 deletions(-)

New commits:
commit 22e5e094575fa3147fa8c8b93491e867f306752f
Author:     Serge Krot <Serge.Krot at cib.de>
AuthorDate: Thu Oct 4 15:20:05 2018 +0200
Commit:     Thorsten Behrens <Thorsten.Behrens at CIB.de>
CommitDate: Thu Nov 1 19:32:39 2018 +0100

    sc: Enhance binary search for ScMarkArray
    
    Change-Id: I0fe6a0b8987fb3c3229c5aabcbf056cfb365650c
    Reviewed-on: https://gerrit.libreoffice.org/61373
    Tested-by: Jenkins
    Reviewed-by: Katarina Behrens <Katarina.Behrens at cib.de>
    Reviewed-on: https://gerrit.libreoffice.org/62746
    Reviewed-by: Thorsten Behrens <Thorsten.Behrens at CIB.de>
    Tested-by: Thorsten Behrens <Thorsten.Behrens at CIB.de>

diff --git a/sc/inc/markmulti.hxx b/sc/inc/markmulti.hxx
index 22f0ee5d1dad..4e284ed76263 100644
--- a/sc/inc/markmulti.hxx
+++ b/sc/inc/markmulti.hxx
@@ -58,7 +58,7 @@ public:
     void SetMarkArea( SCCOL nStartCol, SCCOL nEndCol, SCROW nStartRow, SCROW nEndRow, bool bMark );
     bool IsRowMarked( SCROW nRow ) const;
     bool IsRowRangeMarked( SCROW nStartRow, SCROW nEndRow ) const;
-    bool IsEmpty() const { return ( !aMultiSelContainer.size() && !aRowSel.HasMarks() ); }
+    bool IsEmpty() const { return ( aMultiSelContainer.empty() && !aRowSel.HasMarks() ); }
     ScMarkArray GetMarkArray( SCCOL nCol ) const;
     void Clear();
     void MarkAllCols( SCROW nStartRow, SCROW nEndRow );
diff --git a/sc/qa/unit/mark_test.cxx b/sc/qa/unit/mark_test.cxx
index 957d5fe5b780..0b292f1377cd 100644
--- a/sc/qa/unit/mark_test.cxx
+++ b/sc/qa/unit/mark_test.cxx
@@ -97,6 +97,8 @@ public:
     void testDeleteTabBeforeSelected();
     void testDeleteTabAfterSelected();
 
+    void testScMarkArraySearch();
+
     CPPUNIT_TEST_SUITE(Test);
     CPPUNIT_TEST(testSimpleMark_Simple);
     CPPUNIT_TEST(testSimpleMark_Column);
@@ -107,10 +109,11 @@ public:
     CPPUNIT_TEST(testInsertTabAfterSelected);
     CPPUNIT_TEST(testDeleteTabBeforeSelected);
     CPPUNIT_TEST(testDeleteTabAfterSelected);
+    CPPUNIT_TEST(testScMarkArraySearch);
     CPPUNIT_TEST_SUITE_END();
 
 private:
-
+    void testScMarkArraySearch_check(ScMarkArray & ar, SCROW nRow, bool expectStatus, SCSIZE nIndexExpect);
 };
 
 static void lcl_GetSortedRanges( const ScRangeList& rRangeList, ScRangeList& rRangeListOut )
@@ -846,6 +849,106 @@ void Test::testDeleteTabAfterSelected()
     CPPUNIT_ASSERT_EQUAL(SCTAB(0), aMark.GetFirstSelected());
 }
 
+void Test::testScMarkArraySearch_check(ScMarkArray & ar, SCROW nRow, bool expectStatus, SCSIZE nIndexExpect)
+{
+    SCSIZE nIndex = 0;
+    bool status = ar.Search(nRow, nIndex);
+    CPPUNIT_ASSERT_EQUAL(expectStatus, status);
+    CPPUNIT_ASSERT_EQUAL(nIndexExpect, nIndex);
+}
+
+void Test::testScMarkArraySearch()
+{
+    // empty
+    {
+        ScMarkArray ar;
+        testScMarkArraySearch_check(ar, -1, false, 0);
+        testScMarkArraySearch_check(ar, 100, false, 0);
+    }
+
+    // one range
+    {
+        ScMarkArray ar;
+        ar.SetMarkArea(10, 20, true);
+
+        // 0-9,10-20,21+
+
+        testScMarkArraySearch_check(ar, -100, true, 0);
+        testScMarkArraySearch_check(ar, -1, true, 0);
+
+        testScMarkArraySearch_check(ar, 0,  true, 0);
+        testScMarkArraySearch_check(ar, 5,  true, 0);
+        testScMarkArraySearch_check(ar, 9,  true, 0);
+        testScMarkArraySearch_check(ar, 10, true, 1);
+        testScMarkArraySearch_check(ar, 11, true, 1);
+        testScMarkArraySearch_check(ar, 19, true, 1);
+        testScMarkArraySearch_check(ar, 20, true, 1);
+        testScMarkArraySearch_check(ar, 21, true, 2);
+        testScMarkArraySearch_check(ar, 22, true, 2);
+    }
+
+    // three ranges
+    {
+        ScMarkArray ar;
+        ar.SetMarkArea(10, 20, true);
+        ar.SetMarkArea(21, 30, true);
+        ar.SetMarkArea(50, 100, true);
+
+        // 0-9,10-30,31-49,50-100,101+
+
+        testScMarkArraySearch_check(ar, -100, true, 0);
+        testScMarkArraySearch_check(ar, -1, true, 0);
+
+        testScMarkArraySearch_check(ar, 5,  true, 0);
+        testScMarkArraySearch_check(ar, 15, true, 1);
+        testScMarkArraySearch_check(ar, 25, true, 1);
+        testScMarkArraySearch_check(ar, 35, true, 2);
+        testScMarkArraySearch_check(ar, 55, true, 3);
+        testScMarkArraySearch_check(ar, 20, true, 1);
+        testScMarkArraySearch_check(ar, 21, true, 1);
+    }
+
+    // three single-row ranges
+    {
+        ScMarkArray ar;
+        ar.SetMarkArea(4, 4, true);
+        ar.SetMarkArea(6, 6, true);
+        ar.SetMarkArea(8, 8, true);
+
+        testScMarkArraySearch_check(ar, -100, true, 0);
+        testScMarkArraySearch_check(ar, -1, true, 0);
+
+        testScMarkArraySearch_check(ar, 3,  true, 0);
+        testScMarkArraySearch_check(ar, 4, true, 1);
+        testScMarkArraySearch_check(ar, 5, true, 2);
+        testScMarkArraySearch_check(ar, 6, true, 3);
+        testScMarkArraySearch_check(ar, 7, true, 4);
+        testScMarkArraySearch_check(ar, 8, true, 5);
+        testScMarkArraySearch_check(ar, 9, true, 6);
+        testScMarkArraySearch_check(ar, 10, true, 6);
+    }
+
+    // one range
+    {
+        ScMarkArray ar;
+        ar.SetMarkArea(10, MAXROW, true);
+
+        // 0-10,11+
+
+        testScMarkArraySearch_check(ar, -100, true, 0);
+        testScMarkArraySearch_check(ar, -1, true, 0);
+
+        testScMarkArraySearch_check(ar, 0,  true, 0);
+        testScMarkArraySearch_check(ar, 5,  true, 0);
+        testScMarkArraySearch_check(ar, 9,  true, 0);
+        testScMarkArraySearch_check(ar, 10, true, 1);
+        testScMarkArraySearch_check(ar, 11, true, 1);
+        testScMarkArraySearch_check(ar, 12, true, 1);
+        testScMarkArraySearch_check(ar, 200, true, 1);
+        testScMarkArraySearch_check(ar, MAXROW, true, 1);
+    }
+}
+
 CPPUNIT_TEST_SUITE_REGISTRATION(Test);
 
 CPPUNIT_PLUGIN_IMPLEMENT();
diff --git a/sc/source/core/data/markarr.cxx b/sc/source/core/data/markarr.cxx
index 4a5021301f59..b7e0e8beb227 100644
--- a/sc/source/core/data/markarr.cxx
+++ b/sc/source/core/data/markarr.cxx
@@ -60,40 +60,41 @@ void ScMarkArray::Reset( bool bMarked )
     pData[0].bMarked = bMarked;
 }
 
+// Iterative implementation of Binary Search
 bool ScMarkArray::Search( SCROW nRow, SCSIZE& nIndex ) const
 {
-    long    nHi         = static_cast<long>(nCount) - 1;
-    long    i           = 0;
-    bool    bFound      = (nCount == 1);
     if (pData)
     {
+        long    nHi         = static_cast<long>(nCount) - 1;
+        long    i           = 0;
         long    nLo         = 0;
-        long    nStartRow   = 0;
-        while ( !bFound && nLo <= nHi )
+
+        while ( nLo <= nHi )
         {
             i = (nLo + nHi) / 2;
-            if (i > 0)
-                nStartRow = (long) pData[i - 1].nRow;
-            else
-                nStartRow = -1;
-            long nEndRow = (long) pData[i].nRow;
-            if (nEndRow < (long) nRow)
-                nLo = ++i;
+
+            if (pData[i].nRow < nRow)
+            {
+                // If [nRow] greater, ignore left half
+                nLo = i + 1;
+            }
+            else if ((i > 0) && (pData[i - 1].nRow >= nRow))
+            {
+                // If [nRow] is smaller, ignore right half
+                nHi = i - 1;
+            }
             else
-                if (nStartRow >= (long) nRow)
-                    nHi = --i;
-                else
-                    bFound = true;
+            {
+                // found
+                nIndex=static_cast<SCSIZE>(i);
+                return true;
+            }
         }
     }
-    else
-        bFound = false;
 
-    if (bFound)
-        nIndex=(SCSIZE)i;
-    else
-        nIndex=0;
-    return bFound;
+    // not found
+    nIndex=0;
+    return false;
 }
 
 bool ScMarkArray::GetMark( SCROW nRow ) const


More information about the Libreoffice-commits mailing list