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

[Libreoffice Gerrit user]

 sc/source/core/data/attarray.cxx |   62 +++++++++++++++++++++++++++------------
 1 file changed, 43 insertions(+), 19 deletions(-)

New commits:
commit 6818e8601402d006b85f1818f353fbbace6a6f62
Author:     Serge Krot <Serge.Krot at cib.de>
AuthorDate: Mon Oct 8 10:29:30 2018 +0200
Commit:     Thorsten Behrens <Thorsten.Behrens at CIB.de>
CommitDate: Thu Nov 1 19:33:19 2018 +0100

    sc: Enhance binary search for ScAttrArray
    
    Change-Id: Idf417c452dbbadbede0e3f0860cce7a8a6fd308e
    Reviewed-on: https://gerrit.libreoffice.org/61517
    Tested-by: Jenkins
    Reviewed-by: Katarina Behrens <Katarina.Behrens at cib.de>
    Reviewed-on: https://gerrit.libreoffice.org/62748
    Reviewed-by: Thorsten Behrens <Thorsten.Behrens at CIB.de>
    Tested-by: Thorsten Behrens <Thorsten.Behrens at CIB.de>

diff --git a/sc/source/core/data/attarray.cxx b/sc/source/core/data/attarray.cxx
index d22b868f0a22..8bee60392acc 100644
--- a/sc/source/core/data/attarray.cxx
+++ b/sc/source/core/data/attarray.cxx
@@ -170,35 +170,59 @@ bool ScAttrArray::Concat(SCSIZE nPos)
     return bRet;
 }
 
+/*
+ * nCount is the number of runs of different attribute combinations;
+ * no attribute in a column => nCount==1, one attribute somewhere => nCount == 3
+ * (ie. one run with no attribute + one attribute + another run with no attribute)
+ * so a range of identical attributes is only one entry in ScAttrArray.
+ *
+ * Iterative implementation of Binary Search
+ * The same implementation was used inside ScMarkArray::Search().
+ */
+
 bool ScAttrArray::Search( SCROW nRow, SCSIZE& nIndex ) const
 {
+/*    auto it = std::lower_bound(mvData.begin(), mvData.end(), nRow,
+                [] (const ScAttrEntry &r1, SCROW nRow)
+                { return r1.nEndRow < nRow; } );
+    if (it != mvData.end())
+        nIndex = it - mvData.begin();
+    return it != mvData.end(); */
+
+    if (nCount == 1)
+    {
+        nIndex = 0;
+        return true;
+    }
+
     long nHi = static_cast<long>(nCount) - 1;
     long i = 0;
-    bool bFound = (nCount == 1);
     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;
-        const 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;
+        }
     }
 
-    if (bFound)
-        nIndex=(SCSIZE)i;
-    else
-        nIndex=0;
-    return bFound;
+    nIndex=0;
+    return false;
 }
 
 const ScPatternAttr* ScAttrArray::GetPattern( SCROW nRow ) const