sc/inc/queryiter.hxx | 6 +-
sc/qa/unit/ucalc_sort.cxx | 80 ++++++++++++++++++++++++++++++++++++++
sc/source/core/data/queryiter.cxx | 54 ++++++++++++++++++-------
3 files changed, 121 insertions(+), 19 deletions(-)
New commits:
commit e2f8e5cf7cf9c7b2812ffbcd48ec21dc994339d6
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Fri May 6 10:22:50 2022 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Tue May 10 16:24:55 2022 +0200
make BinarySearch() work for SC_EQUAL, SC_LESS, SC_GREATER
Change-Id: I296686709688a9e3f2cda0864d73c79a17e33f49
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134099
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lu...@collabora.com>
diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
index e247a471db65..847241124a2e 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -140,9 +140,9 @@ protected:
void PerformQuery();
/* Only works if no regular expression is involved, only searches for rows
in one column,
- and only the first query entry is considered with simple conditions
SC_LESS_EQUAL
- (sorted ascending) or SC_GREATER_EQUAL (sorted descending). Delivers a
starting point,
- continue with e.g. GetThis() and GetNext() afterwards. Introduced
+ and only the first query entry is considered with simple conditions
SC_LESS,SC_LESS_EQUAL,
+ SC_EQUAL (sorted ascending) or SC_GREATER,SC_GREATER_EQUAL (sorted
descending). Delivers
+ a starting point, continue with e.g. GetThis() and GetNext()
afterwards. Introduced
for FindEqualOrSortedLastInRange(). */
bool BinarySearch();
diff --git a/sc/qa/unit/ucalc_sort.cxx b/sc/qa/unit/ucalc_sort.cxx
index 698cbb1bde97..e99b0a38cec3 100644
--- a/sc/qa/unit/ucalc_sort.cxx
+++ b/sc/qa/unit/ucalc_sort.cxx
@@ -2102,6 +2102,18 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 5
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(2), it.GetRow());
+ }
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 5
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
+ }
{
// Descending, this should return the last 5.
@@ -2114,6 +2126,12 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(6), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, descendingCol,
SC_GREATER, 5 );
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow());
+ }
{
// There's no 6, so this should return the last 5.
@@ -2126,6 +2144,18 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 6
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
+ }
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 6
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(8), it.GetRow());
+ }
{
// Descending, there's no 6, so this should return the last 9.
@@ -2138,6 +2168,12 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, descendingCol,
SC_GREATER, 6 );
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(1), it.GetRow());
+ }
{
// All values are larger than 0, so this should be an error.
@@ -2150,6 +2186,18 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 0
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow());
+ }
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL, 0
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow());
+ }
{
// Descending, all values are larger than 0, so this should return the
last item.
@@ -2162,6 +2210,12 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, descendingCol,
SC_GREATER, 0 );
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
+ }
{
// All values are smaller than 10, so this should return the last item.
@@ -2174,6 +2228,18 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_LESS, 10
);
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
+ }
+ {
+ ScQueryParam param = makeSearchParam( range, ascendingCol, SC_EQUAL,
10 );
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
+ }
{
// Descending, all values are smaller than 10, so this should be an
error.
@@ -2186,6 +2252,12 @@ void TestSort::testQueryBinarySearch()
CPPUNIT_ASSERT(it.BinarySearch());
CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow());
}
+ {
+ ScQueryParam param = makeSearchParam( range, descendingCol,
SC_GREATER, 10 );
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ CPPUNIT_ASSERT_EQUAL(SCROW(0), it.GetRow());
+ }
{
// Search as ascending but use descending range (=search will not
work).
@@ -2203,6 +2275,14 @@ void TestSort::testQueryBinarySearch()
// CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
}
+ {
+ // SC_EQUAL with descending is considered an error.
+ ScQueryParam param = makeSearchParam( range, descendingCol, SC_EQUAL,
9 );
+ TestQueryIterator it( *m_pDoc, m_pDoc->GetNonThreadedContext(), 0,
param, false );
+ CPPUNIT_ASSERT(it.BinarySearch());
+ // CPPUNIT_ASSERT_EQUAL(SCROW(10), it.GetRow());
+ }
+
m_pDoc->DeleteTab(0);
}
diff --git a/sc/source/core/data/queryiter.cxx
b/sc/source/core/data/queryiter.cxx
index 60d62ad2da60..73a700f108f8 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -283,7 +283,9 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
assert(maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString
|| maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue);
assert(maParam.bByRow);
- assert(maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp
== SC_GREATER_EQUAL);
+ assert(maParam.GetEntry(0).eOp == SC_LESS || maParam.GetEntry(0).eOp ==
SC_LESS_EQUAL
+ || maParam.GetEntry(0).eOp == SC_GREATER || maParam.GetEntry(0).eOp ==
SC_GREATER_EQUAL
+ || maParam.GetEntry(0).eOp == SC_EQUAL);
// TODO: This will be extremely slow with mdds::multi_type_vector.
@@ -301,7 +303,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
SvNumberFormatter& rFormatter = *(mrContext.GetFormatTable());
const ScQueryEntry& rEntry = maParam.GetEntry(0);
const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
- bool bLessEqual = rEntry.eOp == SC_LESS_EQUAL;
+ bool bAscending = rEntry.eOp == SC_LESS || rEntry.eOp == SC_LESS_EQUAL ||
rEntry.eOp == SC_EQUAL;
bool bByString = rItem.meType == ScQueryEntry::ByString;
bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString;
bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
@@ -323,7 +325,9 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
sal_Int32 nTmp = rCollator.compareString(aCellStr,
rEntry.GetQueryItem().maString.getString());
if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) ||
(rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) ||
- (rEntry.eOp == SC_EQUAL && nTmp != 0))
+ (rEntry.eOp == SC_EQUAL && nTmp != 0) ||
+ (rEntry.eOp == SC_LESS && nTmp >= 0) ||
+ (rEntry.eOp == SC_GREATER && nTmp <= 0))
++nRow;
}
}
@@ -361,11 +365,11 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
// range isn't strictly sorted.
size_t nLastInRange = nLo;
size_t nFirstLastInRange = nLastInRange;
- double fLastInRangeValue = bLessEqual ?
+ double fLastInRangeValue = bAscending ?
-(::std::numeric_limits<double>::max()) :
::std::numeric_limits<double>::max();
OUString aLastInRangeString;
- if (!bLessEqual)
+ if (!bAscending)
aLastInRangeString = OUString(u'\xFFFF');
aCellData = aIndexer.getCell(nLastInRange);
@@ -424,7 +428,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
nCellVal, rItem.mfVal))
{
nRes = -1;
- if (bLessEqual)
+ if (bAscending)
{
if (fLastInRangeValue <= nCellVal)
{
@@ -443,7 +447,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
nCellVal, rItem.mfVal))
{
nRes = 1;
- if (!bLessEqual)
+ if (!bAscending)
{
if (fLastInRangeValue >= nCellVal)
{
@@ -465,7 +469,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat,
rFormatter, rDoc);
nRes = rCollator.compareString(aCellStr,
rEntry.GetQueryItem().maString.getString());
- if (nRes < 0 && bLessEqual)
+ if (nRes < 0 && bAscending)
{
sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
aCellStr);
@@ -481,7 +485,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
bDone = true;
}
}
- else if (nRes > 0 && !bLessEqual)
+ else if (nRes > 0 && !bAscending)
{
sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
aCellStr);
@@ -501,18 +505,18 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
else if (!bStr && bByString)
{
nRes = -1; // numeric < string
- if (bLessEqual)
+ if (bAscending)
nLastInRange = i;
}
else // if (bStr && !bByString)
{
nRes = 1; // string > numeric
- if (!bLessEqual)
+ if (!bAscending)
nLastInRange = i;
}
if (nRes < 0)
{
- if (bLessEqual)
+ if (bAscending)
nLo = nMid + 1;
else // assumed to be SC_GREATER_EQUAL
{
@@ -524,7 +528,7 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
}
else if (nRes > 0)
{
- if (bLessEqual)
+ if (bAscending)
{
if (nMid > 0)
nHi = nMid - 1;
@@ -536,9 +540,27 @@ bool ScQueryCellIteratorBase< accessType, queryType
>::BinarySearch()
}
else
{
- found = i;
- // But keep searching to find the last matching one.
- nLo = nMid + 1;
+ if(rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_GREATER_EQUAL
|| rEntry.eOp == SC_EQUAL)
+ {
+ found = i;
+ nLastInRange = i;
+ // But keep searching to find the last matching one.
+ nLo = nMid + 1;
+ }
+ else if (bAscending)
+ {
+ if (nMid > 0)
+ nHi = nMid - 1;
+ else
+ bDone = true;
+ }
+ else
+ {
+ if (nMid > 0)
+ nHi = nMid - 1;
+ else
+ bDone = true;
+ }
}
}
