29#include <document.hxx>
38#include <progress.hxx>
55#include <osl/diagnose.h>
62template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
66 , nStopOnMismatch( nStopOnMismatchDisabled )
67 , nTestEqualCondition( nTestEqualConditionDisabled )
68 , bAdvanceQuery( false )
69 , bIgnoreMismatchOnLeadingStrings( false )
79 for (
i = 0; (
i <
nCount) && (maParam.GetEntry(
i).bDoQuery); ++
i)
84 bool bNumber =
mrContext.GetFormatTable()->IsNumberFormat(
90template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
93 assert(nTab < rDoc.GetTableCount() &&
"index out of bounds, FIX IT");
97 const bool bSingleQueryItem = rEntry.
GetQueryItems().size() == 1;
99 bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings &&
101 bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
103 ((maParam.bByRow && nRow == maParam.nRow1) ||
104 (!maParam.bByRow && nCol == maParam.nCol1));
105 bool bTestEqualCondition =
false;
107 (nTestEqualCondition ? &bTestEqualCondition :
nullptr));
112 assert( !bAllStringIgnore );
113 assert( !bIgnoreMismatchOnLeadingStrings );
114 assert( nStopOnMismatch == nStopOnMismatchDisabled );
115 assert( nTestEqualCondition == nTestEqualConditionDisabled );
116 bAllStringIgnore =
false;
117 bIgnoreMismatchOnLeadingStrings =
false;
118 nStopOnMismatch = nStopOnMismatchDisabled;
119 nTestEqualCondition = nTestEqualConditionDisabled;
121 assert( bAdvanceQuery );
122 bAdvanceQuery =
true;
125 ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
128 bool bNextColumn = maCurPos.first == pCol->
maCells.end();
131 if (nRow > maParam.nRow2)
140 if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
144 AdvanceQueryParamEntryField();
145 nFirstQueryField = rEntry.
nField;
147 pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
153 bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
171 if(HandleItemFound())
190 (nCol ==
static_cast<SCCOL>(nFirstQueryField) ? &aCell :
nullptr)))
192 if ( nTestEqualCondition && bTestEqualCondition )
193 nTestEqualCondition |= nTestEqualConditionMatched;
194 if ( aCell.isEmpty())
196 if( HandleItemFound())
201 else if ( nStopOnMismatch )
206 if ( nTestEqualCondition && bTestEqualCondition )
208 nTestEqualCondition |= nTestEqualConditionMatched;
209 nStopOnMismatch |= nStopOnMismatchOccurred;
213 if (bFirstStringIgnore)
215 if (aCell.hasString())
227 nStopOnMismatch |= nStopOnMismatchOccurred;
234 bFirstStringIgnore =
false;
238template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
242 AccessBase::InitPos();
247 AccessBase::InitPosStart();
249 SCROW beforeRow = -1;
253 if( BinarySearch( nCol ))
262 if( BinarySearch( nCol,
true ))
269 else if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
270 && rDoc.IsEmptyData(nCol, maParam.nRow1, nCol, maParam.nRow2, nTab))
275 lastRow = maParam.nRow2;
280 if( BinarySearch( nCol ))
283 AccessBase::InitPosFinish( beforeRow, lastRow );
287template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
290 SCSIZE nEntries = maParam.GetEntryCount();
291 for (
SCSIZE j = 0; j < nEntries; j++ )
296 if ( rEntry.
nField < rDoc.MaxCol() )
300 assert(!
"AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL");
310template<
typename Iter>
311void incBlock(std::pair<Iter, size_t>& rPos)
318template<
typename Iter>
319void decBlock(std::pair<Iter, size_t>& rPos)
323 rPos.second = rPos.first->size - 1;
328template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
331 assert(maParam.GetEntry(0).bDoQuery && !maParam.GetEntry(1).bDoQuery
332 && maParam.GetEntry(0).GetQueryItems().size() == 1 );
336 assert(maParam.bByRow);
339 || maParam.GetEntry(0).eOp ==
SC_EQUAL);
343 assert(nTab < rDoc.GetTableCount() &&
"index out of bounds, FIX IT");
345 nRow = maParam.nRow1;
347 if (nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
350 ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
360 bool bForceStr = bByString && ( rEntry.
eOp ==
SC_EQUAL || forEqual );
361 bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString;
362 bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
363 !maParam.bHasHeader && bByString;
365 if (maParam.bHasHeader)
368 if (bFirstStringIgnore)
370 sc::CellStoreType::const_position_type aPos = pCol->
maCells.position(nRow);
387 sc::CellStoreType::const_position_type startPos = pCol->
maCells.position(nRow);
393 while (startPos.first != pCol->
maCells.end()
401 if(startPos.first == pCol->
maCells.end())
403 nRow = startPos.first->position + startPos.second;
404 if (nRow > maParam.nRow2)
407 auto aIndexer = MakeBinarySearchIndexer(pCol->
maCells, nRow, maParam.nRow2);
408 if (!aIndexer.isValid())
411 size_t nLo = aIndexer.getLowIndex();
412 size_t nHi = aIndexer.getHighIndex();
413 BinarySearchCellType aCellData;
417 size_t nLastInRange = nLo;
418 double fLastInRangeValue = bAscending ?
419 -(::std::numeric_limits<double>::max()) :
420 ::std::numeric_limits<double>::max();
421 OUString aLastInRangeString;
423 aLastInRangeString = OUString(u
'\xFFFF');
425 aCellData = aIndexer.getCell(nLastInRange);
429 sal_uInt32 nFormat = pCol->
GetNumberFormat(mrContext, aCellData.second);
431 aLastInRangeString =
aStr;
451 std::optional<size_t> found;
453 bool orderBroken =
false;
454 while (nLo <= nHi && !bDone)
456 size_t nMid = (nLo+nHi)/2;
459 aCellData = aIndexer.getCell(i);
460 aCell = aCellData.first;
461 bool bStr = bForceStr || aCell.
hasString();
466 if (!bStr && !bByString)
478 if ((nCellVal < rItem.
mfVal) && !::rtl::math::approxEqual(
479 nCellVal, rItem.
mfVal))
484 if (fLastInRangeValue <= nCellVal)
486 fLastInRangeValue = nCellVal;
489 else if (fLastInRangeValue >= nCellVal)
497 else if ((nCellVal > rItem.
mfVal) && !::rtl::math::approxEqual(
498 nCellVal, rItem.
mfVal))
503 if (fLastInRangeValue >= nCellVal)
505 fLastInRangeValue = nCellVal;
508 else if (fLastInRangeValue <= nCellVal)
517 else if (bStr && bByString)
519 sal_uInt32 nFormat = pCol->
GetNumberFormat(mrContext, aCellData.second);
523 if (nRes < 0 && bAscending)
525 sal_Int32 nTmp = rCollator.
compareString( aLastInRangeString,
529 aLastInRangeString = aCellStr;
539 else if (nRes > 0 && !bAscending)
541 sal_Int32 nTmp = rCollator.
compareString( aLastInRangeString,
545 aLastInRangeString = aCellStr;
556 else if (!bStr && bByString)
623 nLo = aIndexer.getLowIndex();
637 isInRange = nLo != aIndexer.getLowIndex();
647 aCellData = aIndexer.getCell(nLo);
648 if (nLo <= nHi && aCellData.second <= maParam.nRow2)
650 nRow = aCellData.second;
651 maCurPos = aIndexer.getPosition(nLo);
656 nRow = maParam.nRow2 + 1;
658 maCurPos.first = pCol->
maCells.end();
660 maCurPos.second = maCurPos.first->size - 1;
666template< ScQueryCellIteratorAccess accessType >
673 nFoundCol = rDoc.MaxCol()+1;
674 nFoundRow = rDoc.MaxRow()+1;
675 SetStopOnMismatch(
true );
676 SetTestEqualCondition(
true );
677 bIgnoreMismatchOnLeadingStrings =
true;
680 bool bBinary = maParam.bByRow &&
686 if (BinarySearch( maParam.nCol1 ))
690 maParam.mbRangeLookup =
false;
703 PositionType aPosSave;
707 nFoundCol = GetCol();
708 nFoundRow = GetRow();
710 if (IsEqualConditionFulfilled())
718 if (!bNext && !IsEqualConditionFulfilled())
722 SCCOL nColDiff = nCol - nFoundCol;
726 if (maParam.mbRangeLookup)
731 maParam.mbRangeLookup =
false;
733 if (bAdvanceQuery && nColDiff)
735 SCSIZE nEntries = maParam.GetEntryCount();
736 for (
SCSIZE j=0; j < nEntries; ++j)
741 if (rEntry.
nField - nColDiff >= 0)
742 rEntry.
nField -= nColDiff;
745 assert(!
"FindEqualOrSortedLastInRange: rEntry.nField -= nColDiff < 0");
755 nFoundCol = rDoc.MaxCol()+1;
756 nFoundRow = rDoc.MaxRow()+1;
761 if ( IsEqualConditionFulfilled() )
764 SCSIZE nEntries = maParam.GetEntryCount();
765 for (
SCSIZE j = 0; j < nEntries; j++ )
770 switch ( rEntry.
eOp )
785 PositionType aPosSave;
786 bIgnoreMismatchOnLeadingStrings =
false;
787 SetTestEqualCondition(
false );
790 nFoundCol = GetCol();
791 nFoundRow = GetRow();
802 StoppedOnMismatch() )
806 SCSIZE nEntries = maParam.GetEntryCount();
807 for (
SCSIZE j = 0; j < nEntries; j++ )
812 switch ( rEntry.
eOp )
827 SetStopOnMismatch(
false );
828 SetTestEqualCondition(
false );
834 PositionType aPosSave;
837 nFoundCol = GetCol();
838 nFoundRow = GetRow();
840 SetStopOnMismatch(
true );
847 return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
864 nRow = maParam.nRow1;
865 if (maParam.bHasHeader && maParam.bByRow)
867 const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
868 maCurPos = rCol.
maCells.position(nRow);
873 if (maCurPos.second + 1 < maCurPos.first->size)
889 nRow = maCurPos.first->position;
903 typedef std::map<size_t, sc::CellStoreType::const_iterator>
BlockMapType;
926 sc::CellStoreType::const_position_type aLoPos =
mrCells.position(nStartRow);
928 assert(aLoPos.first != rCells.end());
930 SCROW nFirstRow = aLoPos.first->position;
931 SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1;
933 if (nFirstRow > nEndRow)
942 if (nFirstRow < nStartRow)
951 if (nEndRow < nLastRow)
953 assert(nEndRow >= nFirstRow);
956 maBlockMap.emplace(aLoPos.first->size, aLoPos.first);
962 sc::CellStoreType::const_position_type aHiPos =
mrCells.position(aLoPos.first, nEndRow);
969 SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size - 1;
970 if (nBlockEndRow < nStartRow)
981 sc::CellStoreType::const_iterator itBlk = aLoPos.first;
982 while (itBlk != aHiPos.first)
997 assert(itBlk !=
mrCells.end());
1000 assert(itBlk == aHiPos.first);
1001 nPos += itBlk->size;
1005 BlockMapType::const_reverse_iterator ri =
maBlockMap.rbegin();
1011 sc::CellStoreType::const_position_type getPosition(
size_t nIndex )
const
1017 sc::CellStoreType::const_position_type aRet(
mrCells.end(), 0);
1019 BlockMapType::const_iterator it =
maBlockMap.upper_bound(nIndex);
1023 sc::CellStoreType::const_iterator itBlk = it->second;
1024 size_t nBlkIndex = it->first - itBlk->size;
1025 assert(nBlkIndex <= nIndex);
1026 assert(nIndex < it->first);
1028 size_t nOffset =
nIndex - nBlkIndex;
1030 aRet.second = nOffset;
1034 BinarySearchCellType getCell(
size_t nIndex )
const
1036 BinarySearchCellType aRet;
1039 sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
1040 if (aPos.first ==
mrCells.end())
1044 aRet.second = aPos.first->position + aPos.second;
1048 size_t getLowIndex()
const {
return mnLowIndex; }
1050 size_t getHighIndex()
const {
return mnHighIndex; }
1052 bool isValid()
const {
return mbValid; }
1059 return NonEmptyCellIndexer(rCells, nStartRow, nEndRow);
1077 sortedCache = &cache;
1086 ScRange aSortedRangeRange( nCol, maParam.nRow1, nTab, nCol, maParam.nRow2, nTab );
1088 SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange, maParam, &
mrContext ));
1096 pColumn = &rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1099 sortedCachePos = beforeRow >= 0 ? sortedCache->indexForRow(beforeRow) + 1 : 0;
1100 sortedCachePosLast = sortedCache->indexForRow(lastRow);
1101 if(sortedCachePos <= sortedCachePosLast)
1103 nRow = sortedCache->rowForIndex(sortedCachePos);
1104 maCurPos = pColumn->maCells.position(nRow);
1109 sortedCachePos = sortedCachePosLast = 0;
1110 maCurPos.first = pColumn->maCells.end();
1111 maCurPos.second = 0;
1117 if(sortedCachePos < sortedCachePosLast)
1120 nRow = sortedCache->rowForIndex(sortedCachePos);
1122 if constexpr (!fast)
1126 if(maCurPos.first != pColumn->maCells.end() &&
o3tl::make_unsigned(nRow) >= maCurPos.first->position
1128 maCurPos.second = nRow - maCurPos.first->position;
1130 maCurPos = pColumn->maCells.position(nRow);
1138 maCurPos.first = pColumn->maCells.end();
1139 maCurPos.second = 0;
1164 if( row >= startRow && row <= endRow )
1173 :
mSortedRows( makeSortedRows( cache, startRow, endRow ))
1187 sc::CellStoreType::const_position_type getPosition(
size_t nIndex )
const
1191 return mCells.position(row);
1194 BinarySearchCellType getCell(
size_t nIndex )
const
1196 BinarySearchCellType aRet;
1199 sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
1200 if (aPos.first ==
mCells.end())
1204 aRet.second = aPos.first->position + aPos.second;
1208 size_t getLowIndex()
const {
return mLowIndex; }
1210 size_t getHighIndex()
const {
return mHighIndex; }
1212 bool isValid()
const {
return mValid; }
1219 return SortedCacheIndexer(rCells, nStartRow, nEndRow, sortedCache);
1248 static bool inUnitTest = getenv(
"LO_TESTNAME") !=
nullptr;
1283 getThisResult =
true;
1287template< ScQueryCellIteratorAccess accessType >
1290 getThisResult =
false;
1292 return getThisResult;
1295template< ScQueryCellIteratorAccess accessType >
1298 assert(nTab < rDoc.GetTableCount() &&
"index out of bounds, FIX IT");
1299 nCol = maParam.nCol1;
1304template< ScQueryCellIteratorAccess accessType >
1308 if ( nStopOnMismatch )
1309 nStopOnMismatch = nStopOnMismatchEnabled;
1310 if ( nTestEqualCondition )
1311 nTestEqualCondition = nTestEqualConditionEnabled;
1350template< ScQueryCellIteratorAccess accessType >
1354 SetAdvanceQueryParamEntryField(
true );
1355 assert(nTab < rDoc.GetTableCount() &&
"try to access index out of bounds, FIX IT");
1356 maParam.nCol1 = rDoc.ClampToAllocatedColumns(nTab, maParam.nCol1);
1357 maParam.nCol2 = rDoc.ClampToAllocatedColumns(nTab, maParam.nCol2);
1358 nCol = maParam.nCol1;
1362 return countIfCount;
1378 assert(nTab < rDoc.GetTableCount() &&
"try to access index out of bounds, FIX IT");
1379 sal_uInt64
count = 0;
1381 for(
SCCOL col : rDoc.GetAllocatedColumnsRange(nTab, maParam.nCol1, maParam.nCol2))
1384 nRow = maParam.nRow1;
1385 ScRange aSortedRangeRange( col, maParam.nRow1, nTab, col, maParam.nRow2, nTab);
1386 ScQueryOp& op = maParam.GetEntry(0).eOp;
1387 SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange, maParam, &mrContext ));
1398 size_t lastNonMatching = sortedCache->indexForRow(nRow);
1401 size_t lastMatching = sortedCache->indexForRow(nRow);
1402 assert(lastMatching >= lastNonMatching);
1403 count += lastMatching - lastNonMatching;
1420 size_t lastMatching = sortedCache->indexForRow(nRow) + 1;
1421 count += lastMatching;
1423 else if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
1424 && rDoc.IsEmptyData(col, maParam.nRow1, col, maParam.nRow2, nTab))
1428 count += maParam.nRow2 - maParam.nRow1 + 1;
1437 count += sortedCache->indexForRow(nRow) + 1;
1440 if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
1441 && maParam.nCol2 >= rDoc.GetAllocatedColumnsCount( nTab ))
1443 count += (maParam.nCol2 - rDoc.GetAllocatedColumnsCount( nTab ))
1444 * ( maParam.nRow2 - maParam.nRow1 + 1 );
size_t SCSIZE
size_t typedef to be able to find places where code was changed from USHORT to size_t and is used to ...
const NodeContext & mrContext
sal_Int32 compareString(const OUString &s1, const OUString &s2) const
sc::CellStoreType maCells
sal_uInt32 GetNumberFormat(const ScInterpreterContext &rContext, SCROW nRow) const
static bool CanBeUsed(ScDocument &rDoc, const ScQueryParam &aParam, SCTAB nTab, const ScFormulaCell *cell, const ScComplexRefData *refData, ScInterpreterContext &context)
SC_DLLPUBLIC ScColumnsRange GetAllocatedColumnsRange(SCTAB nTab, SCCOL nColBegin, SCCOL nColEnd) const
ScSortedRangeCache & GetSortedRangeCache(const ScRange &rRange, const ScQueryParam ¶m, ScInterpreterContext *pContext)
static SC_DLLPUBLIC CollatorWrapper & GetCollator()
case-insensitive collator
sal_uInt8 nStopOnMismatch
bool BinarySearch(SCCOL col, bool forEqual=false)
sal_uInt8 nTestEqualCondition
ScQueryCellIteratorBase(ScDocument &rDocument, ScInterpreterContext &rContext, SCTAB nTable, const ScQueryParam &aParam, bool bMod)
void SetAdvanceQueryParamEntryField(bool bVal)
void AdvanceQueryParamEntryField()
static bool CanBeUsed(ScDocument &rDoc, const ScQueryParam &aParam, SCTAB nTab, const ScFormulaCell *cell, const ScComplexRefData *refData, ScInterpreterContext &context)
bool FindEqualOrSortedLastInRange(SCCOL &nFoundCol, SCROW &nFoundRow)
In a range assumed to be sorted find either the last of a sequence of equal entries or the last being...
bool isMatchWholeCell(ScQueryOp eOp) const
bool ValidQuery(SCROW nRow, const ScRefCellValue *pCell=nullptr, sc::TableColumnBlockPositionSet *pBlockPos=nullptr)
Sorted cache for one range used with interpreter functions such as VLOOKUP and MATCH.
bool isValid() const
Returns if the cache is usable.
const std::vector< SCROW > & sortedRows() const
const ScRange & getRange() const
OUString getString() const
constexpr std::enable_if< std::is_signed< T1 >::value &&std::is_signed< T2 >::value, bool >::type isInRange(T2 value)
constexpr std::enable_if_t< std::is_signed_v< T >, std::make_unsigned_t< T > > make_unsigned(T value)
const mdds::mtv::element_t element_type_edittext
ScRefCellValue toRefCell(const sc::CellStoreType::const_iterator &itPos, size_t nOffset)
mdds::mtv::soa::multi_type_vector< CellFunc, CellStoreTrait > CellStoreType
const mdds::mtv::element_t element_type_string
const mdds::mtv::element_t element_type_empty
std::vector< SCROW > mSortedRowsCopy
const std::vector< SCROW > & mSortedRows
std::map< size_t, sc::CellStoreType::const_iterator > BlockMapType
const sc::CellStoreType & mCells
const sc::CellStoreType & mrCells
static bool CanBeUsedForSorterCache(ScDocument &rDoc, const ScQueryParam &rParam, SCTAB nTab, const ScFormulaCell *cell, const ScComplexRefData *refData, ScInterpreterContext &context)
Complex reference (a range) into the sheet.
svl::SharedString maString
Each instance of this struct represents a single filtering criteria.
const Item & GetQueryItem() const
QueryItemsType & GetQueryItems()
SC_DLLPUBLIC const ScQueryEntry & GetEntry(SCSIZE n) const
utl::SearchParam::SearchType eSearchType
bool mbRangeLookup
for spreadsheet functions like MATCH, LOOKUP, HLOOKUP, VLOOKUP
This is very similar to ScCellValue, except that it references the original value instead of copying ...
ScFormulaCell * getFormula() const
sal_Int32 SCCOLROW
a type capable of holding either SCCOL or SCROW
ScQueryCellIteratorAccess