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 724e92d6bfa9900e40546df5c05da44e9d33b856
Author: Serge Krot <serge.k...@cib.de>
AuthorDate: Thu Oct 4 15:20:05 2018 +0200
Commit: Katarina Behrens <katarina.behr...@cib.de>
CommitDate: Fri Oct 5 10:40:54 2018 +0200
sc: Enhance binary search for ScMarkArray
Change-Id: I0fe6a0b8987fb3c3229c5aabcbf056cfb365650c
Reviewed-on: https://gerrit.libreoffice.org/61373
Tested-by: Jenkins
Reviewed-by: Katarina Behrens <katarina.behr...@cib.de>
diff --git a/sc/inc/markmulti.hxx b/sc/inc/markmulti.hxx
index a8482048a48b..ee92da37ce61 100644
--- a/sc/inc/markmulti.hxx
+++ b/sc/inc/markmulti.hxx
@@ -57,7 +57,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 0c393e934b77..6e00e4bf163d 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 d398ffd456fe..f9c5fdc3299a 100644
--- a/sc/source/core/data/markarr.cxx
+++ b/sc/source/core/data/markarr.cxx
@@ -58,40 +58,41 @@ void ScMarkArray::Reset( bool bMarked, SCSIZE nNeeded )
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 = static_cast<long>(pData[i - 1].nRow);
- else
- nStartRow = -1;
- long nEndRow = static_cast<long>(pData[i].nRow);
- if (nEndRow < static_cast<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 >= static_cast<long>(nRow))
- nHi = --i;
- else
- bFound = true;
+ {
+ // found
+ nIndex=static_cast<SCSIZE>(i);
+ return true;
+ }
}
}
- else
- bFound = false;
- if (bFound)
- nIndex=static_cast<SCSIZE>(i);
- else
- nIndex=0;
- return bFound;
+ // not found
+ nIndex=0;
+ return false;
}
bool ScMarkArray::GetMark( SCROW nRow ) const
_______________________________________________
Libreoffice-commits mailing list
libreoffice-comm...@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/libreoffice-commits
