sc/source/core/data/attarray.cxx | 62 +++++++++++++++++++++++++++------------ 1 file changed, 43 insertions(+), 19 deletions(-)
New commits: commit 6818e8601402d006b85f1818f353fbbace6a6f62 Author: Serge Krot <[email protected]> AuthorDate: Mon Oct 8 10:29:30 2018 +0200 Commit: Thorsten Behrens <[email protected]> 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 <[email protected]> Reviewed-on: https://gerrit.libreoffice.org/62748 Reviewed-by: Thorsten Behrens <[email protected]> Tested-by: Thorsten Behrens <[email protected]> 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 _______________________________________________ Libreoffice-commits mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
