make query iterator's BinarySearch() find the last matching item

If the code found a matching value, it didn't bother finding
the last one in the range if there were several adjacent ones.

Change-Id: Ie1f4c7bd3dcbd2aaf653f5b74e159902de4cf93d
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134098
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

2 files changed, 18 insertions, 15 deletions

diff --git a/sc/qa/unit/ucalc_sort.cxx b/sc/qa/unit/ucalc_sort.cxx
index ca4b9c319e80..698cbb1bde97 100644
--- a/sc/qa/unit/ucalc_sort.cxx
+++ b/sc/qa/unit/ucalc_sort.cxx
@@ -2100,7 +2100,7 @@ void TestSort::testQueryBinarySearch()
         ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS_EQUAL, 5 );
         TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false );
         CPPUNIT_ASSERT(it.BinarySearch());
-        // CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
+        CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
     }
 
     {
@@ -2112,7 +2112,7 @@ void TestSort::testQueryBinarySearch()
         ScQueryParam param = makeSearchParam( range, descendingCol, SC_GREATER_EQUAL, 5 );
         TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false );
         CPPUNIT_ASSERT(it.BinarySearch());
-        // CPPUNIT_ASSERT_EQUAL(SCROW(6), it.GetRow());
+        CPPUNIT_ASSERT_EQUAL(SCROW(6), it.GetRow());
     }
 
     {
@@ -2124,7 +2124,7 @@ void TestSort::testQueryBinarySearch()
         ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS_EQUAL, 6 );
         TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false );
         CPPUNIT_ASSERT(it.BinarySearch());
-        // CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
+        CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
     }
 
     {
@@ -2136,7 +2136,7 @@ void TestSort::testQueryBinarySearch()
         ScQueryParam param = makeSearchParam( range, descendingCol, SC_GREATER_EQUAL, 6 );
         TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false );
         CPPUNIT_ASSERT(it.BinarySearch());
-        // CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow());
+        CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow());
     }
 
     {
@@ -2172,7 +2172,7 @@ void TestSort::testQueryBinarySearch()
         ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS_EQUAL, 10 );
         TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0, param, false );
         CPPUNIT_ASSERT(it.BinarySearch());
-        // CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
+        CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
     }
 
     {
diff --git a/sc/source/core/data/queryiter.cxx b/sc/source/core/data/queryiter.cxx
index ec88e35ff6a5..60d62ad2da60 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -394,7 +394,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
     }
 
     sal_Int32 nRes = 0;
-    bool bFound = false;
+    std::optional<size_t> found;
     bool bDone = false;
     while (nLo <= nHi && !bDone)
     {
@@ -426,12 +426,12 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
                 nRes = -1;
                 if (bLessEqual)
                 {
-                    if (fLastInRangeValue < nCellVal)
+                    if (fLastInRangeValue <= nCellVal)
                     {
                         fLastInRangeValue = nCellVal;
                         nLastInRange = i;
                     }
-                    else if (fLastInRangeValue > nCellVal)
+                    else if (fLastInRangeValue >= nCellVal)
                     {
                         // not strictly sorted, continue with GetThis()
                         nLastInRange = nFirstLastInRange;
@@ -445,12 +445,12 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
                 nRes = 1;
                 if (!bLessEqual)
                 {
-                    if (fLastInRangeValue > nCellVal)
+                    if (fLastInRangeValue >= nCellVal)
                     {
                         fLastInRangeValue = nCellVal;
                         nLastInRange = i;
                     }
-                    else if (fLastInRangeValue < nCellVal)
+                    else if (fLastInRangeValue <= nCellVal)
                     {
                         // not strictly sorted, continue with GetThis()
                         nLastInRange = nFirstLastInRange;
@@ -469,7 +469,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
             {
                 sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
                         aCellStr);
-                if (nTmp < 0)
+                if (nTmp <= 0)
                 {
                     aLastInRangeString = aCellStr;
                     nLastInRange = i;
@@ -485,7 +485,7 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
             {
                 sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
                         aCellStr);
-                if (nTmp > 0)
+                if (nTmp >= 0)
                 {
                     aLastInRangeString = aCellStr;
                     nLastInRange = i;
@@ -536,12 +536,15 @@ bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch()
         }
         else
         {
-            nLo = i;
-            bDone = bFound = true;
+            found = i;
+            // But keep searching to find the last matching one.
+            nLo = nMid + 1;
         }
     }
 
-    if (!bFound)
+    if (found)
+        nLo = *found;
+    else
     {
         // If all hits didn't result in a moving limit there's something
         // strange, e.g. data range not properly sorted, or only identical