diff options
author | Serge Krot <Serge.Krot@cib.de> | 2018-10-08 10:29:30 +0200 |
---|---|---|
committer | Thorsten Behrens <Thorsten.Behrens@CIB.de> | 2018-11-28 00:42:59 +0100 |
commit | 2cbe3a7afbb31f05e5f66a7cf2493ad43c596141 (patch) | |
tree | 2fbb1168d2bd4273ebaa00e68139490636fbf810 | |
parent | a7b4f64e388dd2954eb0f8f5b4181614d5a26de1 (diff) |
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@cib.de>
-rw-r--r-- | sc/source/core/data/attarray.cxx | 48 |
1 files changed, 29 insertions, 19 deletions
diff --git a/sc/source/core/data/attarray.cxx b/sc/source/core/data/attarray.cxx index 3330cf14c10e..813cc6562543 100644 --- a/sc/source/core/data/attarray.cxx +++ b/sc/source/core/data/attarray.cxx @@ -190,6 +190,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 @@ -201,33 +204,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 |