sc/inc/queryiter.hxx | 18 -
sc/source/core/data/queryiter.cxx | 381 +++++++++++++++++++-------------------
2 files changed, 198 insertions(+), 201 deletions(-)
New commits:
commit 4d2bd386837524fd9f74f827f59ac3dfc64b3a6a
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Mon Apr 25 13:23:08 2022 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Tue May 10 16:22:26 2022 +0200
BinarySearch() can be in ScQueryCellIteratorBase
Change-Id: I89d7e58a9706526aa2871dba1e4f922ff94562a6
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134094
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 ae7b8066c57b..c2378bca6aa2 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -85,6 +85,13 @@ protected:
SCCOL GetCol() const { return nCol; }
SCROW GetRow() const { return nRow; }
+ /* 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). Check these
things before
+ invocation! Delivers a starting point, continue with e.g. GetThis() and
GetNext()
+ afterwards. Introduced for FindEqualOrSortedLastInRange(). */
+ bool BinarySearch();
+
public:
ScQueryCellIteratorBase(ScDocument& rDocument, const
ScInterpreterContext& rContext, SCTAB nTable,
const ScQueryParam& aParam, bool
bMod);
@@ -140,17 +147,6 @@ protected:
// The generic query iterator, used e.g. by VLOOKUP.
class ScQueryCellIterator : public ScQueryCellIteratorBase<
ScQueryCellIteratorType::Generic >
{
- /* 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). Check these things before
- invocation! Delivers a starting point, continue with
- GetThis() and GetNext() afterwards. Introduced for
- FindEqualOrSortedLastInRange()
- */
- bool BinarySearch();
-
bool GetThis();
public:
diff --git a/sc/source/core/data/queryiter.cxx
b/sc/source/core/data/queryiter.cxx
index 9f0ada59a521..040dfdfc403d 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -287,195 +287,6 @@ void ScQueryCellIteratorBase< iteratorType
>::AdvanceQueryParamEntryField()
}
}
-bool ScQueryCellIterator::FindEqualOrSortedLastInRange( SCCOL& nFoundCol,
- SCROW& nFoundRow )
-{
- // Set and automatically reset mpParam->mbRangeLookup when returning. We
- // could use comphelper::FlagRestorationGuard, but really, that one is
- // overengineered for this simple purpose here.
- struct BoolResetter
- {
- bool& mr;
- bool mb;
- BoolResetter( bool& r, bool b ) : mr(r), mb(r) { r = b; }
- ~BoolResetter() { mr = mb; }
- } aRangeLookupResetter( maParam.mbRangeLookup, true);
-
- nFoundCol = rDoc.MaxCol()+1;
- nFoundRow = rDoc.MaxRow()+1;
- SetStopOnMismatch( true ); // assume sorted keys
- SetTestEqualCondition( true );
- bIgnoreMismatchOnLeadingStrings = true;
- bool bLiteral = maParam.eSearchType ==
utl::SearchParam::SearchType::Normal &&
- maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString;
- bool bBinary = maParam.bByRow &&
- (bLiteral || maParam.GetEntry(0).GetQueryItem().meType ==
ScQueryEntry::ByValue) &&
- (maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp
== SC_GREATER_EQUAL);
- bool bFound = false;
- if (bBinary)
- {
- if (BinarySearch())
- {
- // BinarySearch() already positions correctly and only needs real
- // query comparisons afterwards, skip the verification check below.
- maParam.mbRangeLookup = false;
- bFound = GetThis();
- }
- }
- else
- {
- bFound = GetFirst();
- }
- if (bFound)
- {
- // First equal entry or last smaller than (greater than) entry.
- PositionType aPosSave;
- bool bNext = false;
- do
- {
- nFoundCol = GetCol();
- nFoundRow = GetRow();
- aPosSave = maCurPos;
- if (IsEqualConditionFulfilled())
- break;
- bNext = GetNext();
- }
- while (bNext);
-
- // There may be no pNext but equal condition fulfilled if regular
- // expressions are involved. Keep the found entry and proceed.
- if (!bNext && !IsEqualConditionFulfilled())
- {
- // Step back to last in range and adjust position markers for
- // GetNumberFormat() or similar.
- SCCOL nColDiff = nCol - nFoundCol;
- nCol = nFoundCol;
- nRow = nFoundRow;
- maCurPos = aPosSave;
- if (maParam.mbRangeLookup)
- {
- // Verify that the found entry does not only fulfill the range
- // lookup but also the real query, i.e. not numeric was found
- // if query is ByString and vice versa.
- maParam.mbRangeLookup = false;
- // Step back the last field advance if GetNext() did one.
- if (bAdvanceQuery && nColDiff)
- {
- SCSIZE nEntries = maParam.GetEntryCount();
- for (SCSIZE j=0; j < nEntries; ++j)
- {
- ScQueryEntry& rEntry = maParam.GetEntry( j );
- if (rEntry.bDoQuery)
- {
- if (rEntry.nField - nColDiff >= 0)
- rEntry.nField -= nColDiff;
- else
- {
- assert(!"FindEqualOrSortedLastInRange:
rEntry.nField -= nColDiff < 0");
- }
- }
- else
- break; // for
- }
- }
- // Check it.
- if (!GetThis())
- {
- nFoundCol = rDoc.MaxCol()+1;
- nFoundRow = rDoc.MaxRow()+1;
- }
- }
- }
- }
- if ( IsEqualConditionFulfilled() )
- {
- // Position on last equal entry.
- SCSIZE nEntries = maParam.GetEntryCount();
- for ( SCSIZE j = 0; j < nEntries; j++ )
- {
- ScQueryEntry& rEntry = maParam.GetEntry( j );
- if ( rEntry.bDoQuery )
- {
- switch ( rEntry.eOp )
- {
- case SC_LESS_EQUAL :
- case SC_GREATER_EQUAL :
- rEntry.eOp = SC_EQUAL;
- break;
- default:
- {
- // added to avoid warnings
- }
- }
- }
- else
- break; // for
- }
- PositionType aPosSave;
- bIgnoreMismatchOnLeadingStrings = false;
- SetTestEqualCondition( false );
- do
- {
- nFoundCol = GetCol();
- nFoundRow = GetRow();
- aPosSave = maCurPos;
- } while (GetNext());
-
- // Step back conditions are the same as above
- nCol = nFoundCol;
- nRow = nFoundRow;
- maCurPos = aPosSave;
- return true;
- }
- if ( (maParam.eSearchType != utl::SearchParam::SearchType::Normal) &&
- StoppedOnMismatch() )
- {
- // Assume found entry to be the last value less than respectively
- // greater than the query. But keep on searching for an equal match.
- SCSIZE nEntries = maParam.GetEntryCount();
- for ( SCSIZE j = 0; j < nEntries; j++ )
- {
- ScQueryEntry& rEntry = maParam.GetEntry( j );
- if ( rEntry.bDoQuery )
- {
- switch ( rEntry.eOp )
- {
- case SC_LESS_EQUAL :
- case SC_GREATER_EQUAL :
- rEntry.eOp = SC_EQUAL;
- break;
- default:
- {
- // added to avoid warnings
- }
- }
- }
- else
- break; // for
- }
- SetStopOnMismatch( false );
- SetTestEqualCondition( false );
- if (GetNext())
- {
- // Last of a consecutive area, avoid searching the entire parameter
- // range as it is a real performance bottleneck in case of regular
- // expressions.
- PositionType aPosSave;
- do
- {
- nFoundCol = GetCol();
- nFoundRow = GetRow();
- aPosSave = maCurPos;
- SetStopOnMismatch( true );
- } while (GetNext());
- nCol = nFoundCol;
- nRow = nFoundRow;
- maCurPos = aPosSave;
- }
- }
- return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
-}
-
namespace {
template<typename Iter>
@@ -691,7 +502,8 @@ public:
}
-bool ScQueryCellIterator::BinarySearch()
+template< ScQueryCellIteratorType iteratorType >
+bool ScQueryCellIteratorBase< iteratorType >::BinarySearch()
{
// TODO: This will be extremely slow with mdds::multi_type_vector.
@@ -960,6 +772,195 @@ bool ScQueryCellIterator::BinarySearch()
}
+bool ScQueryCellIterator::FindEqualOrSortedLastInRange( SCCOL& nFoundCol,
+ SCROW& nFoundRow )
+{
+ // Set and automatically reset mpParam->mbRangeLookup when returning. We
+ // could use comphelper::FlagRestorationGuard, but really, that one is
+ // overengineered for this simple purpose here.
+ struct BoolResetter
+ {
+ bool& mr;
+ bool mb;
+ BoolResetter( bool& r, bool b ) : mr(r), mb(r) { r = b; }
+ ~BoolResetter() { mr = mb; }
+ } aRangeLookupResetter( maParam.mbRangeLookup, true);
+
+ nFoundCol = rDoc.MaxCol()+1;
+ nFoundRow = rDoc.MaxRow()+1;
+ SetStopOnMismatch( true ); // assume sorted keys
+ SetTestEqualCondition( true );
+ bIgnoreMismatchOnLeadingStrings = true;
+ bool bLiteral = maParam.eSearchType ==
utl::SearchParam::SearchType::Normal &&
+ maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString;
+ bool bBinary = maParam.bByRow &&
+ (bLiteral || maParam.GetEntry(0).GetQueryItem().meType ==
ScQueryEntry::ByValue) &&
+ (maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp
== SC_GREATER_EQUAL);
+ bool bFound = false;
+ if (bBinary)
+ {
+ if (BinarySearch())
+ {
+ // BinarySearch() already positions correctly and only needs real
+ // query comparisons afterwards, skip the verification check below.
+ maParam.mbRangeLookup = false;
+ bFound = GetThis();
+ }
+ }
+ else
+ {
+ bFound = GetFirst();
+ }
+ if (bFound)
+ {
+ // First equal entry or last smaller than (greater than) entry.
+ PositionType aPosSave;
+ bool bNext = false;
+ do
+ {
+ nFoundCol = GetCol();
+ nFoundRow = GetRow();
+ aPosSave = maCurPos;
+ if (IsEqualConditionFulfilled())
+ break;
+ bNext = GetNext();
+ }
+ while (bNext);
+
+ // There may be no pNext but equal condition fulfilled if regular
+ // expressions are involved. Keep the found entry and proceed.
+ if (!bNext && !IsEqualConditionFulfilled())
+ {
+ // Step back to last in range and adjust position markers for
+ // GetNumberFormat() or similar.
+ SCCOL nColDiff = nCol - nFoundCol;
+ nCol = nFoundCol;
+ nRow = nFoundRow;
+ maCurPos = aPosSave;
+ if (maParam.mbRangeLookup)
+ {
+ // Verify that the found entry does not only fulfill the range
+ // lookup but also the real query, i.e. not numeric was found
+ // if query is ByString and vice versa.
+ maParam.mbRangeLookup = false;
+ // Step back the last field advance if GetNext() did one.
+ if (bAdvanceQuery && nColDiff)
+ {
+ SCSIZE nEntries = maParam.GetEntryCount();
+ for (SCSIZE j=0; j < nEntries; ++j)
+ {
+ ScQueryEntry& rEntry = maParam.GetEntry( j );
+ if (rEntry.bDoQuery)
+ {
+ if (rEntry.nField - nColDiff >= 0)
+ rEntry.nField -= nColDiff;
+ else
+ {
+ assert(!"FindEqualOrSortedLastInRange:
rEntry.nField -= nColDiff < 0");
+ }
+ }
+ else
+ break; // for
+ }
+ }
+ // Check it.
+ if (!GetThis())
+ {
+ nFoundCol = rDoc.MaxCol()+1;
+ nFoundRow = rDoc.MaxRow()+1;
+ }
+ }
+ }
+ }
+ if ( IsEqualConditionFulfilled() )
+ {
+ // Position on last equal entry.
+ SCSIZE nEntries = maParam.GetEntryCount();
+ for ( SCSIZE j = 0; j < nEntries; j++ )
+ {
+ ScQueryEntry& rEntry = maParam.GetEntry( j );
+ if ( rEntry.bDoQuery )
+ {
+ switch ( rEntry.eOp )
+ {
+ case SC_LESS_EQUAL :
+ case SC_GREATER_EQUAL :
+ rEntry.eOp = SC_EQUAL;
+ break;
+ default:
+ {
+ // added to avoid warnings
+ }
+ }
+ }
+ else
+ break; // for
+ }
+ PositionType aPosSave;
+ bIgnoreMismatchOnLeadingStrings = false;
+ SetTestEqualCondition( false );
+ do
+ {
+ nFoundCol = GetCol();
+ nFoundRow = GetRow();
+ aPosSave = maCurPos;
+ } while (GetNext());
+
+ // Step back conditions are the same as above
+ nCol = nFoundCol;
+ nRow = nFoundRow;
+ maCurPos = aPosSave;
+ return true;
+ }
+ if ( (maParam.eSearchType != utl::SearchParam::SearchType::Normal) &&
+ StoppedOnMismatch() )
+ {
+ // Assume found entry to be the last value less than respectively
+ // greater than the query. But keep on searching for an equal match.
+ SCSIZE nEntries = maParam.GetEntryCount();
+ for ( SCSIZE j = 0; j < nEntries; j++ )
+ {
+ ScQueryEntry& rEntry = maParam.GetEntry( j );
+ if ( rEntry.bDoQuery )
+ {
+ switch ( rEntry.eOp )
+ {
+ case SC_LESS_EQUAL :
+ case SC_GREATER_EQUAL :
+ rEntry.eOp = SC_EQUAL;
+ break;
+ default:
+ {
+ // added to avoid warnings
+ }
+ }
+ }
+ else
+ break; // for
+ }
+ SetStopOnMismatch( false );
+ SetTestEqualCondition( false );
+ if (GetNext())
+ {
+ // Last of a consecutive area, avoid searching the entire parameter
+ // range as it is a real performance bottleneck in case of regular
+ // expressions.
+ PositionType aPosSave;
+ do
+ {
+ nFoundCol = GetCol();
+ nFoundRow = GetRow();
+ aPosSave = maCurPos;
+ SetStopOnMismatch( true );
+ } while (GetNext());
+ nCol = nFoundCol;
+ nRow = nFoundRow;
+ maCurPos = aPosSave;
+ }
+ }
+ return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
+}
+
template<>
bool ScQueryCellIteratorBase< ScQueryCellIteratorType::Generic
>::HandleItemFound()
{
