sc/source/core/data/attarray.cxx | 48 +++++++++++++++++++++++----------------
1 file changed, 29 insertions(+), 19 deletions(-)
New commits:
commit 4ba06560e33f17ca1ed72ad722c80eae5ffd4277
Author: Serge Krot <serge.k...@cib.de>
AuthorDate: Mon Oct 8 10:29:30 2018 +0200
Commit: Katarina Behrens <katarina.behr...@cib.de>
CommitDate: Tue Oct 9 12:09:34 2018 +0200
sc: Enhance binary search for ScAttrArray
Change-Id: Idf417c452dbbadbede0e3f0860cce7a8a6fd308e
Reviewed-on: https://gerrit.libreoffice.org/61517
Tested-by: Jenkins
Reviewed-by: Katarina Behrens <katarina.behr...@cib.de>
diff --git a/sc/source/core/data/attarray.cxx b/sc/source/core/data/attarray.cxx
index b9ecb05568ef..5c3d5a7153ab 100644
--- a/sc/source/core/data/attarray.cxx
+++ b/sc/source/core/data/attarray.cxx
@@ -191,6 +191,9 @@ bool ScAttrArray::Concat(SCSIZE nPos)
* 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
@@ -202,33 +205,40 @@ bool ScAttrArray::Search( SCROW nRow, SCSIZE& nIndex )
const
nIndex = it - mvData.begin();
return it != mvData.end(); */
+ if (mvData.size() == 1)
+ {
+ nIndex = 0;
+ return true;
+ }
+
long nHi = static_cast<long>(mvData.size()) - 1;
long i = 0;
- bool bFound = (mvData.size() == 1);
long nLo = 0;
- long nStartRow = 0;
- while ( !bFound && nLo <= nHi )
+
+ while ( nLo <= nHi )
{
i = (nLo + nHi) / 2;
- if (i > 0)
- nStartRow = static_cast<long>(mvData[i - 1].nEndRow);
- else
- nStartRow = -1;
- const long nEndRow = static_cast<long>(mvData[i].nEndRow);
- if (nEndRow < static_cast<long>(nRow))
- nLo = ++i;
+
+ if (mvData[i].nEndRow < nRow)
+ {
+ // If [nRow] greater, ignore left half
+ nLo = i + 1;
+ }
+ else if ((i > 0) && (mvData[i - 1].nEndRow >= nRow))
+ {
+ // If [nRow] is smaller, ignore right half
+ nHi = i - 1;
+ }
else
- if (nStartRow >= static_cast<long>(nRow))
- nHi = --i;
- else
- bFound = true;
+ {
+ // found
+ nIndex=static_cast<SCSIZE>(i);
+ return true;
+ }
}
- if (bFound)
- nIndex=static_cast<SCSIZE>(i);
- else
- nIndex=0;
- return bFound;
+ nIndex=0;
+ return false;
}
const ScPatternAttr* ScAttrArray::GetPattern( SCROW nRow ) const
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
