sc/source/core/data/queryiter.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <queryiter.hxx>
  21 #include <rtl/math.hxx>
  22
  23 #include <comphelper/flagguard.hxx>
  24 #include <o3tl/safeint.hxx>
  25 #include <svl/numformat.hxx>
  26
  27 #include <global.hxx>
  28 #include <document.hxx>
  29 #include <table.hxx>
  30 #include <column.hxx>
  31 #include <formulacell.hxx>
  32 #include <cellform.hxx>
  33 #include <queryparam.hxx>
  34 #include <queryentry.hxx>
  35 #include <cellvalue.hxx>
  36 #include <queryevaluator.hxx>
  37 #include <rangecache.hxx>
  38 #include <refdata.hxx>
  39
  40 #include <svl/sharedstring.hxx>
  41 #include <unotools/collatorwrapper.hxx>
  42
  43 #include <limits>
  44 #include <vector>
  45
  46 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
  47 ScQueryCellIteratorBase< accessType, queryType >::ScQueryCellIteratorBase(ScDocument& rDocument,
  48     ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam& rParam, bool bMod, bool bReverse )
  49     : AccessBase( rDocument, rContext, rParam, bReverse )
  50     , nStopOnMismatch( nStopOnMismatchDisabled )
  51     , nTestEqualCondition( nTestEqualConditionDisabled )
  52     , nSortedBinarySearch( nBinarySearchDisabled )
  53     , bAdvanceQuery( false )
  54     , bIgnoreMismatchOnLeadingStrings( false )
  55     , nSearchOpCode( SC_OPCODE_NONE )
  56     , nBestFitCol(SCCOL_MAX)
  57     , nBestFitRow(SCROW_MAX)
  58 {
  59     nTab = nTable;
  60     nCol = !bReverse ? maParam.nCol1 : maParam.nCol2;
  61     nRow = !bReverse ? maParam.nRow1 : maParam.nRow2;
  62     SCSIZE i;
  63     if (!bMod) // Or else it's already inserted
  64         return;
  65
  66     SCSIZE nCount = maParam.GetEntryCount();
  67     for (i = 0; (i < nCount) && (maParam.GetEntry(i).bDoQuery); ++i)
  68     {
  69         ScQueryEntry& rEntry = maParam.GetEntry(i);
  70         ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
  71         sal_uInt32 nIndex = 0;
  72         bool bNumber = mrContext.NFIsNumberFormat(
  73             rItem.maString.getString(), nIndex, rItem.mfVal);
  74         rItem.meType = bNumber ? ScQueryEntry::ByValue : ScQueryEntry::ByString;
  75     }
  76 }
  77
  78 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
  79 void ScQueryCellIteratorBase< accessType, queryType >::PerformQuery()
  80 {
  81     assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
  82     const ScQueryEntry& rEntry = maParam.GetEntry(0);
  83     const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
  84
  85     const bool bSingleQueryItem = rEntry.GetQueryItems().size() == 1;
  86     SCCOLROW nFirstQueryField = rEntry.nField;
  87     bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings &&
  88         rItem.meType != ScQueryEntry::ByString;
  89     bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
  90         !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString &&
  91         ((maParam.bByRow && nRow == maParam.nRow1) ||
  92          (!maParam.bByRow && nCol == maParam.nCol1));
  93     bool bTestEqualCondition = false;
  94     const bool bNewSearchFunction = nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH;
  95     ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam, &mrContext,
  96         (nTestEqualCondition ? &bTestEqualCondition : nullptr), bNewSearchFunction);
  97     if( queryType == ScQueryCellIteratorType::CountIf )
  98     {
  99         // These are not used for COUNTIF, so should not be set, make the compiler
 100         // explicitly aware of it so that the relevant parts are optimized away.
 101         assert( !bAllStringIgnore );
 102         assert( !bIgnoreMismatchOnLeadingStrings );
 103         assert( nStopOnMismatch == nStopOnMismatchDisabled );
 104         assert( nTestEqualCondition == nTestEqualConditionDisabled );
 105         bAllStringIgnore = false;
 106         bIgnoreMismatchOnLeadingStrings = false;
 107         nStopOnMismatch = nStopOnMismatchDisabled;
 108         nTestEqualCondition = nTestEqualConditionDisabled;
 109         // This one is always set.
 110         assert( bAdvanceQuery );
 111         bAdvanceQuery = true;
 112     }
 113
 114     const ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 115     while (true)
 116     {
 117         bool bNextColumn = maCurPos.first == pCol->maCells.end();
 118         if (!bNextColumn)
 119         {
 120             if ((!mbReverseSearch && nRow > maParam.nRow2) || (mbReverseSearch && nRow < maParam.nRow1))
 121                 bNextColumn = true;
 122         }
 123
 124         if (bNextColumn)
 125         {
 126             do
 127             {
 128                 if (!mbReverseSearch)
 129                 {
 130                     ++nCol;
 131                     if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
 132                         return;
 133                 }
 134                 else
 135                 {
 136                     --nCol;
 137                     if (nCol < maParam.nCol1 || nCol < static_cast<SCCOL>(0))
 138                         return;
 139                 }
 140                 if ( bAdvanceQuery )
 141                 {
 142                     AdvanceQueryParamEntryField();
 143                     nFirstQueryField = rEntry.nField;
 144                 }
 145                 pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 146             }
 147             while (!rItem.mbMatchEmpty && pCol->IsEmptyData());
 148
 149             InitPos();
 150
 151             bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
 152                 !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString &&
 153                 maParam.bByRow;
 154         }
 155
 156         if (maCurPos.first->type == sc::element_type_empty)
 157         {
 158             if (rItem.mbMatchEmpty && bSingleQueryItem)
 159             {
 160                 // This shortcut, instead of determining if any SC_OR query
 161                 // exists or this query is SC_AND'ed (which wouldn't make
 162                 // sense, but..) and evaluating them in ValidQuery(), is
 163                 // possible only because the interpreter is the only caller
 164                 // that sets mbMatchEmpty and there is only one item in those
 165                 // cases.
 166                 // XXX this would have to be reworked if other filters used it
 167                 // in different manners and evaluation would have to be done in
 168                 // ValidQuery().
 169                 if(HandleItemFound())
 170                     return;
 171                 !mbReverseSearch ? IncPos() : DecPos();
 172                 continue;
 173             }
 174             else
 175             {
 176                 !mbReverseSearch ? IncBlock() : DecBlock();
 177                 continue;
 178             }
 179         }
 180
 181         ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second);
 182
 183         if (bAllStringIgnore && aCell.hasString())
 184             !mbReverseSearch ? IncPos() : DecPos();
 185         else
 186         {
 187             if ( queryEvaluator.ValidQuery( nRow,
 188                     (nCol == static_cast<SCCOL>(nFirstQueryField) ? &aCell : nullptr)))
 189             {
 190                 if ( nTestEqualCondition && bTestEqualCondition )
 191                     nTestEqualCondition |= nTestEqualConditionMatched;
 192                 if ( aCell.isEmpty())
 193                     return;
 194
 195                 // XLookUp/XMatch: Forward/asc/backward/desc search for best fit value, except if we have an exact match
 196                 if (bNewSearchFunction &&
 197                     (rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_GREATER_EQUAL) &&
 198                     (nBestFitCol != nCol || nBestFitRow != nRow))
 199                 {
 200                     bool bNumSearch = rItem.meType == ScQueryEntry::ByValue && aCell.hasNumeric();
 201                     bool bStringSearch = rItem.meType == ScQueryEntry::ByString && aCell.hasString();
 202                     if (bNumSearch || bStringSearch)
 203                     {
 204                         if (nTestEqualCondition == nTestEqualConditionFulfilled || (nBestFitCol == SCCOL_MAX && nBestFitRow == SCROW_MAX))
 205                             HandleBestFitItemFound(nCol, nRow);
 206                         else
 207                         {
 208                             ScAddress aBFAddr(nBestFitCol, nBestFitRow, nTab);
 209                             ScRefCellValue aBFCell(rDoc, aBFAddr);
 210                             ScQueryParam aParamTmp(maParam);
 211                             ScQueryEntry& rEntryTmp = aParamTmp.GetEntry(0);
 212
 213                             if (rEntry.eOp == SC_LESS_EQUAL)
 214                                 rEntryTmp.eOp = SC_GREATER;
 215                             else if (rEntry.eOp == SC_GREATER_EQUAL)
 216                                 rEntryTmp.eOp = SC_LESS;
 217
 218                             ScQueryEntry::Item& rItemTmp = rEntryTmp.GetQueryItem();
 219                             if (bNumSearch)
 220                                 rItemTmp.mfVal = aBFCell.getValue();
 221                             else if (bStringSearch)
 222                                 rItemTmp.maString = svl::SharedString(aBFCell.getString(&rDoc));
 223
 224                             ScQueryEvaluator queryEvaluatorTmp(rDoc, *rDoc.maTabs[nTab], aParamTmp, &mrContext, nullptr, bNewSearchFunction);
 225                             if (queryEvaluatorTmp.ValidQuery(nRow, (nCol == static_cast<SCCOL>(nFirstQueryField) ? &aCell : nullptr)))
 226                                 HandleBestFitItemFound(nCol, nRow);
 227                             else
 228                             {
 229                                 !mbReverseSearch ? IncPos() : DecPos();
 230                                 continue;
 231                             }
 232                         }
 233                     }
 234                     else
 235                     {
 236                         !mbReverseSearch ? IncPos() : DecPos();
 237                         continue;
 238                     }
 239                 }
 240                 if (HandleItemFound())
 241                     return;
 242                 !mbReverseSearch ? IncPos() : DecPos();
 243                 continue;
 244             }
 245             else if ( nStopOnMismatch )
 246             {
 247                 // Yes, even a mismatch may have a fulfilled equal
 248                 // condition if regular expressions were involved and
 249                 // SC_LESS_EQUAL or SC_GREATER_EQUAL were queried.
 250                 if ( nTestEqualCondition && bTestEqualCondition )
 251                 {
 252                     nTestEqualCondition |= nTestEqualConditionMatched;
 253                     nStopOnMismatch |= nStopOnMismatchOccurred;
 254                     return;
 255                 }
 256                 bool bStop;
 257                 if (bFirstStringIgnore)
 258                 {
 259                     if (aCell.hasString())
 260                     {
 261                         !mbReverseSearch ? IncPos() : DecPos();
 262                         bStop = false;
 263                     }
 264                     else
 265                         bStop = true;
 266                 }
 267                 else
 268                     bStop = true;
 269                 if (bStop)
 270                 {
 271                     nStopOnMismatch |= nStopOnMismatchOccurred;
 272                     return;
 273                 }
 274             }
 275             else
 276                 !mbReverseSearch ? IncPos() : DecPos();
 277         }
 278         bFirstStringIgnore = false;
 279     }
 280 }
 281
 282 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
 283 void ScQueryCellIteratorBase< accessType, queryType >::InitPos()
 284 {
 285     if constexpr( accessType != ScQueryCellIteratorAccess::SortedCache )
 286         AccessBase::InitPos();
 287     else
 288     {
 289         // This should be all in AccessBase::InitPos(), but that one can't call
 290         // BinarySearch(), so do it this way instead.
 291         bool bNewSearchFunction = nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH;
 292         AccessBase::InitPosStart(bNewSearchFunction, nSortedBinarySearch);
 293         ScQueryOp& op = maParam.GetEntry(0).eOp;
 294         SCCOLROW beforeColRow = -1;
 295         SCCOLROW lastColRow = -1;
 296         if( op == SC_EQUAL )
 297         {
 298             if( BinarySearch( maParam.bByRow ? nCol : nRow) )
 299             {
 300                 // BinarySearch() searches for the last item that matches. Now we
 301                 // also need to find the first item where to start. Find the last
 302                 // non-matching position using SC_LESS and the start position
 303                 // is the one after it.
 304                 lastColRow = maParam.bByRow ? nRow : nCol;
 305                 ScQueryOp saveOp = op;
 306                 op = SC_LESS;
 307                 if( BinarySearch(maParam.bByRow ? nCol : nRow, true) )
 308                     beforeColRow = maParam.bByRow ? nRow : nCol;
 309                 // If BinarySearch() returns false, there was no match, which means
 310                 // there's no value smaller. In that case BinarySearch() has set
 311                 // the position to the first row in the range.
 312                 op = saveOp; // back to SC_EQUAL
 313             }
 314             else if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
 315                 && rDoc.IsEmptyData(maParam.nCol1, maParam.nRow1, maParam.nCol2, maParam.nRow2, nTab))
 316             {
 317                 // BinarySearch() returns false in case it's all empty data,
 318                 // handle that specially.
 319                 lastColRow = maParam.nRow2;
 320             }
 321             if (maParam.bByRow)
 322                 AccessBase::InitPosFinish(beforeColRow, lastColRow, false/*bFirstMatch*/);
 323             else
 324                 AccessBase::InitPosColFinish(beforeColRow, lastColRow, false/*bFirstMatch*/);
 325         }
 326         else
 327         {   // The range is from the start up to and including the last matching.
 328             if( BinarySearch( maParam.bByRow ? nCol : nRow) )
 329             {
 330                 lastColRow = maParam.bByRow ? nRow : nCol;
 331                 if (nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH)
 332                 {
 333                     ScQueryOp saveOp = op;
 334                     op = SC_LESS;
 335                     if( BinarySearch(maParam.bByRow ? nCol : nRow, true) )
 336                         beforeColRow = maParam.bByRow ? nRow : nCol;
 337                     op = saveOp;
 338                 }
 339             }
 340             if ((nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH) &&
 341                 (lastColRow == beforeColRow || beforeColRow == -1))
 342             {
 343                 beforeColRow = -1;
 344                 if (maParam.bByRow)
 345                     AccessBase::InitPosFinish(beforeColRow, lastColRow, true/*bFirstMatch*/);
 346                 else
 347                 {
 348                     AccessBase::InitPosColFinish(beforeColRow, lastColRow, true/*bFirstMatch*/);
 349                     AdvanceQueryParamEntryFieldForBinarySearch();
 350                 }
 351             }
 352             else
 353             {
 354                 if (maParam.bByRow)
 355                     AccessBase::InitPosFinish(beforeColRow, lastColRow, false/*bFirstMatch*/);
 356                 else
 357                 {
 358                     AccessBase::InitPosColFinish(beforeColRow, lastColRow, false/*bFirstMatch*/);
 359                     AdvanceQueryParamEntryFieldForBinarySearch();
 360                 }
 361             }
 362         }
 363     }
 364 }
 365
 366 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
 367 void ScQueryCellIteratorBase< accessType, queryType >::AdvanceQueryParamEntryField()
 368 {
 369     SCSIZE nEntries = maParam.GetEntryCount();
 370     for ( SCSIZE j = 0; j < nEntries; j++  )
 371     {
 372         ScQueryEntry& rEntry = maParam.GetEntry( j );
 373         if ( rEntry.bDoQuery )
 374         {
 375             if (!mbReverseSearch && rEntry.nField < rDoc.MaxCol())
 376                 rEntry.nField++;
 377             else if (mbReverseSearch && rEntry.nField > static_cast<SCCOLROW>(0))
 378                 rEntry.nField--;
 379             else
 380             {
 381                 assert(!"AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL || --rEntry.nField < 0");
 382             }
 383         }
 384         else
 385             break;  // for
 386     }
 387 }
 388
 389 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
 390 void ScQueryCellIteratorBase< accessType, queryType >::AdvanceQueryParamEntryFieldForBinarySearch()
 391 {
 392     SCSIZE nEntries = maParam.GetEntryCount();
 393     for ( SCSIZE j = 0; j < nEntries; j++  )
 394     {
 395         ScQueryEntry& rEntry = maParam.GetEntry( j );
 396         if ( rEntry.bDoQuery )
 397         {
 398             if (rEntry.nField < rDoc.MaxCol())
 399                 rEntry.nField = nCol;
 400             else
 401             {
 402                 assert(!"AdvanceQueryParamEntryFieldForBinarySearch: rEntry.nField >= MAXCOL");
 403             }
 404         }
 405         else
 406             break;  // for
 407     }
 408 }
 409
 410 namespace {
 411
 412 template<typename Iter>
 413 void incBlock(std::pair<Iter, size_t>& rPos)
 414 {
 415     // Move to the next block.
 416     ++rPos.first;
 417     rPos.second = 0;
 418 }
 419
 420 template<typename Iter>
 421 void decBlock(std::pair<Iter, size_t>& rPos)
 422 {
 423     // Move to the last element of the previous block.
 424     --rPos.first;
 425     rPos.second = rPos.first->size - 1;
 426 }
 427
 428 }
 429
 430 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
 431 bool ScQueryCellIteratorBase< accessType, queryType >::BinarySearch( SCCOLROW col_row, bool forEqual )
 432 {
 433     assert(maParam.GetEntry(0).bDoQuery && !maParam.GetEntry(1).bDoQuery
 434         && maParam.GetEntry(0).GetQueryItems().size() == 1 );
 435     assert(maParam.eSearchType == utl::SearchParam::SearchType::Normal);
 436     assert(maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString
 437         || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue);
 438     assert(maParam.GetEntry(0).eOp == SC_LESS || maParam.GetEntry(0).eOp == SC_LESS_EQUAL
 439         || maParam.GetEntry(0).eOp == SC_GREATER || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL
 440         || maParam.GetEntry(0).eOp == SC_EQUAL);
 441
 442     // TODO: This will be extremely slow with mdds::multi_type_vector.
 443
 444     assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
 445     nCol = maParam.bByRow ? col_row : maParam.nCol1;
 446     nRow = maParam.bByRow ? maParam.nRow1 : col_row;
 447
 448     if (maParam.bByRow)
 449     {
 450         if (nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
 451             return false;
 452     }
 453     else
 454     {
 455         if (maParam.nCol2 >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
 456             return false;
 457     }
 458
 459     const ScColumn* pCol = nullptr;
 460     if (maParam.bByRow)
 461     {
 462         pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 463         if (pCol->IsEmptyData())
 464             return false;
 465     }
 466     else
 467     {
 468         pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 469     }
 470
 471     CollatorWrapper& rCollator = ScGlobal::GetCollator(maParam.bCaseSens);
 472     const ScQueryEntry& rEntry = maParam.GetEntry(0);
 473     const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
 474     bool bAscending = rEntry.eOp == SC_LESS || rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_EQUAL;
 475     bool bByString = rItem.meType == ScQueryEntry::ByString;
 476     bool bForceStr = bByString && ( rEntry.eOp == SC_EQUAL || forEqual );
 477     bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString;
 478     bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
 479         !maParam.bHasHeader && bByString;
 480
 481     if (maParam.bHasHeader)
 482         maParam.bByRow ? ++nRow : ++nCol;
 483
 484     if (bFirstStringIgnore)
 485     {
 486         // move to next col if necessary
 487         if (!maParam.bByRow && maParam.nCol1 != nCol)
 488             pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 489
 490         sc::CellStoreType::const_position_type aPos = pCol->maCells.position(nRow);
 491         if (aPos.first->type == sc::element_type_string || aPos.first->type == sc::element_type_edittext)
 492         {
 493             ScRefCellValue aCell = sc::toRefCell(aPos.first, aPos.second);
 494             sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, nRow);
 495             OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, &mrContext, rDoc);
 496             sal_Int32 nTmp = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString());
 497             if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) ||
 498                     (rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) ||
 499                     (rEntry.eOp == SC_EQUAL && nTmp != 0) ||
 500                     (rEntry.eOp == SC_LESS && nTmp >= 0) ||
 501                     (rEntry.eOp == SC_GREATER && nTmp <= 0))
 502                 maParam.bByRow ? ++nRow : ++nCol;
 503         }
 504     }
 505
 506     sc::CellStoreType::const_position_type startPos;
 507     // Skip leading empty block, if any.
 508     if (maParam.bByRow)
 509     {
 510         startPos = pCol->maCells.position(nRow);
 511         if (startPos.first->type == sc::element_type_empty)
 512             incBlock(startPos);
 513     }
 514     else
 515     {
 516         bool bNonEmpty = false;
 517         while (nCol != maParam.nCol2 && !bNonEmpty)
 518         {
 519             if (maParam.nCol1 != nCol)
 520                 pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 521             startPos = pCol->maCells.position(nRow);
 522             if (startPos.first->type == sc::element_type_empty)
 523                 ++nCol;
 524             else
 525                 bNonEmpty = true;
 526         }
 527     }
 528
 529     if(bAllStringIgnore)
 530     {
 531         // Skip all leading string or empty blocks.
 532         if (maParam.bByRow)
 533         {
 534             while (startPos.first != pCol->maCells.end()
 535                 && (startPos.first->type == sc::element_type_string ||
 536                     startPos.first->type == sc::element_type_edittext ||
 537                     startPos.first->type == sc::element_type_empty))
 538             {
 539                 incBlock(startPos);
 540             }
 541         }
 542         else
 543         {
 544             bool bSkipped = false;
 545             while (nCol != maParam.nCol2 && !bSkipped)
 546             {
 547                 if (maParam.nCol1 != nCol)
 548                     pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
 549                 startPos = pCol->maCells.position(nRow);
 550                 if (startPos.first->type == sc::element_type_string ||
 551                     startPos.first->type == sc::element_type_edittext ||
 552                     startPos.first->type == sc::element_type_empty)
 553                     ++nCol;
 554                 else
 555                     bSkipped = true;
 556             }
 557         }
 558     }
 559
 560     if (maParam.bByRow)
 561     {
 562         if (startPos.first == pCol->maCells.end())
 563             return false;
 564         nRow = startPos.first->position + startPos.second;
 565         if (nRow > maParam.nRow2)
 566             return false;
 567     }
 568     else
 569     {
 570         if (nCol > maParam.nCol2)
 571             return false;
 572     }
 573
 574     const auto& aIndexer(maParam.bByRow ? MakeBinarySearchIndexer(&pCol->maCells, nRow, maParam.nRow2) :
 575         MakeBinarySearchIndexer(nullptr, nCol, maParam.nCol2));
 576
 577     if (!aIndexer.isValid())
 578         return false;
 579
 580     size_t nLo = aIndexer.getLowIndex();
 581     size_t nHi = aIndexer.getHighIndex();
 582     BinarySearchCellType aCellData;
 583
 584     // Bookkeeping values for breaking up the binary search in case the data
 585     // range isn't strictly sorted.
 586     size_t nLastInRange = nLo;
 587     double fLastInRangeValue = bAscending ?
 588         -(::std::numeric_limits<double>::max()) :
 589             ::std::numeric_limits<double>::max();
 590     OUString aLastInRangeString;
 591     if (!bAscending)
 592         aLastInRangeString = OUString(u'\xFFFF');
 593
 594     if (maParam.bByRow)
 595         aCellData = aIndexer.getCell(nLastInRange);
 596     else
 597         aCellData = aIndexer.getColCell(nLastInRange, nRow);
 598
 599     ScRefCellValue aCell = aCellData.first;
 600     if (bForceStr || aCell.hasString())
 601     {
 602         sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, maParam.bByRow ? aCellData.second : nRow);
 603         aLastInRangeString = ScCellFormat::GetInputString(aCell, nFormat, &mrContext, rDoc);
 604     }
 605     else
 606     {
 607         switch (aCell.getType())
 608         {
 609             case CELLTYPE_VALUE :
 610                 fLastInRangeValue = aCell.getDouble();
 611             break;
 612             case CELLTYPE_FORMULA :
 613                 fLastInRangeValue = aCell.getFormula()->GetValue();
 614             break;
 615             default:
 616             {
 617                 // added to avoid warnings
 618             }
 619         }
 620     }
 621
 622     sal_Int32 nRes = 0;
 623     std::optional<size_t> found;
 624     bool bDone = false;
 625     bool orderBroken = false;
 626     while (nLo <= nHi && !bDone)
 627     {
 628         size_t nMid = (nLo+nHi)/2;
 629         size_t i = nMid;
 630
 631         if (maParam.bByRow)
 632             aCellData = aIndexer.getCell(i);
 633         else
 634             aCellData = aIndexer.getColCell(i, nRow);
 635         aCell = aCellData.first;
 636         bool bStr = bForceStr || aCell.hasString();
 637         nRes = 0;
 638
 639         // compares are content<query:-1, content>query:1
 640         // Cell value comparison similar to ScTable::ValidQuery()
 641         if (!bStr && !bByString)
 642         {
 643             double nCellVal;
 644             switch (aCell.getType())
 645             {
 646                 case CELLTYPE_VALUE :
 647                 case CELLTYPE_FORMULA :
 648                     nCellVal = aCell.getValue();
 649                 break;
 650                 default:
 651                     nCellVal = 0.0;
 652             }
 653             if ((nCellVal < rItem.mfVal) && !::rtl::math::approxEqual(
 654                         nCellVal, rItem.mfVal))
 655             {
 656                 nRes = -1;
 657                 if (bAscending)
 658                 {
 659                     if (fLastInRangeValue <= nCellVal)
 660                     {
 661                         fLastInRangeValue = nCellVal;
 662                         nLastInRange = i;
 663                     }
 664                     else if (fLastInRangeValue >= nCellVal)
 665                     {
 666                         // not strictly sorted, continue with GetThis()
 667                         orderBroken = true;
 668                         bDone = true;
 669                     }
 670                 }
 671             }
 672             else if ((nCellVal > rItem.mfVal) && !::rtl::math::approxEqual(
 673                         nCellVal, rItem.mfVal))
 674             {
 675                 nRes = 1;
 676                 if (!bAscending)
 677                 {
 678                     if (fLastInRangeValue >= nCellVal)
 679                     {
 680                         fLastInRangeValue = nCellVal;
 681                         nLastInRange = i;
 682                     }
 683                     else if (fLastInRangeValue <= nCellVal)
 684                     {
 685                         // not strictly sorted, continue with GetThis()
 686                         orderBroken = true;
 687                         bDone = true;
 688                     }
 689                 }
 690             }
 691         }
 692         else if (bStr && bByString)
 693         {
 694             if (!maParam.bByRow)
 695                 pCol = &(rDoc.maTabs[nTab])->aCol[aCellData.second];
 696             sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, maParam.bByRow ? aCellData.second : nRow);
 697             OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, &mrContext, rDoc);
 698
 699             nRes = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString());
 700             if (nRes < 0 && bAscending)
 701             {
 702                 sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
 703                         aCellStr);
 704                 if (nTmp <= 0)
 705                 {
 706                     aLastInRangeString = aCellStr;
 707                     nLastInRange = i;
 708                 }
 709                 else if (nTmp > 0)
 710                 {
 711                     // not strictly sorted, continue with GetThis()
 712                     orderBroken = true;
 713                     bDone = true;
 714                 }
 715             }
 716             else if (nRes > 0 && !bAscending)
 717             {
 718                 sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
 719                         aCellStr);
 720                 if (nTmp >= 0)
 721                 {
 722                     aLastInRangeString = aCellStr;
 723                     nLastInRange = i;
 724                 }
 725                 else if (nTmp < 0)
 726                 {
 727                     // not strictly sorted, continue with GetThis()
 728                     orderBroken = true;
 729                     bDone = true;
 730                 }
 731             }
 732         }
 733         else if (!bStr && bByString)
 734         {
 735             nRes = -1; // numeric < string
 736             if (bAscending)
 737                 nLastInRange = i;
 738         }
 739         else // if (bStr && !bByString)
 740         {
 741             nRes = 1; // string > numeric
 742             if (!bAscending)
 743                 nLastInRange = i;
 744         }
 745         if (nRes < 0)
 746         {
 747             if (bAscending)
 748                 nLo = nMid + 1;
 749             else // assumed to be SC_GREATER_EQUAL
 750             {
 751                 if (nMid > 0)
 752                     nHi = nMid - 1;
 753                 else
 754                     bDone = true;
 755             }
 756         }
 757         else if (nRes > 0)
 758         {
 759             if (bAscending)
 760             {
 761                 if (nMid > 0)
 762                     nHi = nMid - 1;
 763                 else
 764                     bDone = true;
 765             }
 766             else // assumed to be SC_GREATER_EQUAL
 767                 nLo = nMid + 1;
 768         }
 769         else
 770         {
 771             if(rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_GREATER_EQUAL || rEntry.eOp == SC_EQUAL)
 772             {
 773                 found = i;
 774                 nLastInRange = i;
 775                 nLo = nMid + 1;
 776             }
 777             else if (bAscending)
 778             {
 779                 if (nMid > 0)
 780                     nHi = nMid - 1;
 781                 else
 782                     bDone = true;
 783             }
 784             else
 785             {
 786                 if (nMid > 0)
 787                     nHi = nMid - 1;
 788                 else
 789                     bDone = true;
 790             }
 791         }
 792     }
 793
 794     bool isInRange;
 795     if (orderBroken)
 796     {
 797         // Reset position to the first row in range and force caller
 798         // to search from start.
 799         nLo = aIndexer.getLowIndex();
 800         isInRange = false;
 801     }
 802     else if (found)
 803     {
 804         nLo = *found;
 805         isInRange = true;
 806     }
 807     else
 808     {
 809         // Not nothing was found and the search position is at the start,
 810         // then the possible match would need to be before the data range.
 811         // In that case return false to force the caller to search from the start
 812         // and detect this.
 813         isInRange = nLo != aIndexer.getLowIndex();
 814         // If nothing was found, that is either because there is no value
 815         // that would match exactly, or the data range is not properly sorted
 816         // and we failed to detect (doing so reliably would require a linear scan).
 817         // Set the position to the last one that was in matching range (i.e. before
 818         // where the exact match would be), and leave sorting it out to GetThis()
 819         // or whatever the caller uses.
 820         nLo = nLastInRange;
 821     }
 822
 823     if (maParam.bByRow)
 824     {
 825         aCellData = aIndexer.getCell(nLo);
 826         if (nLo <= nHi && aCellData.second <= maParam.nRow2)
 827         {
 828             nRow = aCellData.second;
 829             maCurPos = aIndexer.getPosition(nLo);
 830             return isInRange;
 831         }
 832         else
 833         {
 834             nRow = maParam.nRow2 + 1;
 835             // Set current position to the last possible row.
 836             maCurPos.first = pCol->maCells.end();
 837             --maCurPos.first;
 838             maCurPos.second = maCurPos.first->size - 1;
 839             return false;
 840         }
 841     }
 842     else
 843     {
 844         aCellData = aIndexer.getColCell(nLo, nRow);
 845         if (nLo <= nHi && aCellData.second <= maParam.nCol2)
 846         {
 847             nCol = aCellData.second;
 848             maCurPos = aIndexer.getColPosition(nLo, nRow);
 849             return isInRange;
 850         }
 851         else
 852         {
 853             nCol = maParam.nCol2 + 1;
 854             // Set current position to the last possible col.
 855             pCol = &(rDoc.maTabs[nTab])->aCol[maParam.nCol2];
 856             maCurPos.first = pCol->maCells.end();
 857             --maCurPos.first;
 858             maCurPos.second = maCurPos.first->size - 1;
 859             return false;
 860         }
 861     }
 862 }
 863
 864
 865 template< ScQueryCellIteratorAccess accessType >
 866 bool ScQueryCellIterator< accessType >::FindEqualOrSortedLastInRange( SCCOL& nFoundCol,
 867         SCROW& nFoundRow )
 868 {
 869     // Set and automatically reset mpParam->mbRangeLookup when returning.
 870     comphelper::FlagRestorationGuard aRangeLookupResetter( maParam.mbRangeLookup, true );
 871
 872     nFoundCol = rDoc.MaxCol()+1;
 873     nFoundRow = rDoc.MaxRow()+1;
 874
 875     if ((nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH) &&
 876         nSortedBinarySearch == nBinarySearchDisabled)
 877         SetStopOnMismatch( false ); // assume not sorted keys for XLookup/XMatch
 878     else
 879         SetStopOnMismatch( true ); // assume sorted keys
 880
 881     SetTestEqualCondition( true );
 882     bIgnoreMismatchOnLeadingStrings = true;
 883
 884     bool bLiteral = maParam.eSearchType == utl::SearchParam::SearchType::Normal &&
 885         maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString;
 886     bool bBinary = maParam.bByRow &&
 887         (bLiteral || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue) &&
 888         (maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL);
 889
 890     // assume not sorted properly if we are using XLookup/XMatch with forward or backward search
 891     if (bBinary && (nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH) &&
 892         nSortedBinarySearch == nBinarySearchDisabled)
 893         bBinary = false;
 894
 895     bool bFound = false;
 896     if (bBinary)
 897     {
 898         if (BinarySearch( maParam.nCol1 ))
 899         {
 900             // BinarySearch() already positions correctly and only needs real
 901             // query comparisons afterwards, skip the verification check below.
 902             maParam.mbRangeLookup = false;
 903             bFound = GetThis();
 904         }
 905         else // Not sorted properly, or before the range (in which case GetFirst() will be simple).
 906             bFound = GetFirst();
 907     }
 908     else
 909     {
 910         bFound = GetFirst();
 911     }
 912     if (bFound)
 913     {
 914         // First equal entry or last smaller than (greater than) entry.
 915         PositionType aPosSave;
 916         bool bNext = false;
 917         SCSIZE nEntries = maParam.GetEntryCount();
 918         std::vector<SCCOL> aFoundFieldPositions(nEntries);
 919         do
 920         {
 921             nFoundCol = GetCol();
 922             nFoundRow = GetRow();
 923             aPosSave = maCurPos;
 924             // If we might need to rewind below, save the position to rewind to
 925             // rather than calculate it as a diff between nCol and nFoundCol as
 926             // PerformQuery can return early if nCol is greater than
 927             // maParam.nCol2 or AllocatedColumns
 928             if (maParam.mbRangeLookup && bAdvanceQuery)
 929             {
 930                 for (SCSIZE j=0; j < nEntries; ++j)
 931                 {
 932                     ScQueryEntry& rEntry = maParam.GetEntry( j );
 933                     if (rEntry.bDoQuery)
 934                         aFoundFieldPositions[j] = maParam.GetEntry(j).nField;
 935                     else
 936                         break;  // for
 937                 }
 938             }
 939             if (IsEqualConditionFulfilled())
 940                 break;
 941             bNext = GetNext();
 942         }
 943         while (bNext);
 944
 945         // There may be no pNext but equal condition fulfilled if regular
 946         // expressions are involved. Keep the found entry and proceed.
 947         if (!bNext && !IsEqualConditionFulfilled())
 948         {
 949             // Step back to last in range and adjust position markers for
 950             // GetNumberFormat() or similar.
 951             bool bColDiff = nCol != nFoundCol;
 952             nCol = nFoundCol;
 953             nRow = nFoundRow;
 954             maCurPos = std::move(aPosSave);
 955             if (maParam.mbRangeLookup)
 956             {
 957                 // Verify that the found entry does not only fulfill the range
 958                 // lookup but also the real query, i.e. not numeric was found
 959                 // if query is ByString and vice versa.
 960                 maParam.mbRangeLookup = false;
 961                 // Step back the last field advance if GetNext() did one.
 962                 if (bAdvanceQuery && bColDiff)
 963                 {
 964                     for (SCSIZE j=0; j < nEntries; ++j)
 965                     {
 966                         ScQueryEntry& rEntry = maParam.GetEntry( j );
 967                         if (rEntry.bDoQuery)
 968                         {
 969                             rEntry.nField = aFoundFieldPositions[j];
 970                             assert(rEntry.nField >= 0);
 971                         }
 972                         else
 973                             break;  // for
 974                     }
 975                 }
 976                 // Check it.
 977                 if (!GetThis())
 978                 {
 979                     nFoundCol = rDoc.MaxCol()+1;
 980                     nFoundRow = rDoc.MaxRow()+1;
 981                 }
 982             }
 983         }
 984     }
 985     if (IsEqualConditionFulfilled() && (nSearchOpCode != SC_OPCODE_X_LOOKUP &&
 986         nSearchOpCode != SC_OPCODE_X_MATCH))
 987     {
 988         // Position on last equal entry, except for XLOOKUP,
 989         // which looking for the first equal entry
 990         SCSIZE nEntries = maParam.GetEntryCount();
 991         for ( SCSIZE j = 0; j < nEntries; j++  )
 992         {
 993             ScQueryEntry& rEntry = maParam.GetEntry( j );
 994             if ( rEntry.bDoQuery )
 995             {
 996                 switch ( rEntry.eOp )
 997                 {
 998                     case SC_LESS_EQUAL :
 999                     case SC_GREATER_EQUAL :
1000                         rEntry.eOp = SC_EQUAL;
1001                     break;
1002                     default:
1003                     {
1004                         // added to avoid warnings
1005                     }
1006                 }
1007             }
1008             else
1009                 break;  // for
1010         }
1011         PositionType aPosSave;
1012         bIgnoreMismatchOnLeadingStrings = false;
1013         SetTestEqualCondition( false );
1014         do
1015         {
1016             nFoundCol = GetCol();
1017             nFoundRow = GetRow();
1018             aPosSave = maCurPos;
1019         } while (GetNext());
1020
1021         // Step back conditions are the same as above
1022         nCol = nFoundCol;
1023         nRow = nFoundRow;
1024         maCurPos = std::move(aPosSave);
1025         return true;
1026     }
1027     if ( (maParam.eSearchType != utl::SearchParam::SearchType::Normal) &&
1028             StoppedOnMismatch() )
1029     {
1030         // Assume found entry to be the last value less than respectively
1031         // greater than the query. But keep on searching for an equal match.
1032         SCSIZE nEntries = maParam.GetEntryCount();
1033         for ( SCSIZE j = 0; j < nEntries; j++  )
1034         {
1035             ScQueryEntry& rEntry = maParam.GetEntry( j );
1036             if ( rEntry.bDoQuery )
1037             {
1038                 switch ( rEntry.eOp )
1039                 {
1040                     case SC_LESS_EQUAL :
1041                     case SC_GREATER_EQUAL :
1042                         rEntry.eOp = SC_EQUAL;
1043                     break;
1044                     default:
1045                     {
1046                         // added to avoid warnings
1047                     }
1048                 }
1049             }
1050             else
1051                 break;  // for
1052         }
1053         SetStopOnMismatch( false );
1054         SetTestEqualCondition( false );
1055         if (GetNext())
1056         {
1057             // Last of a consecutive area, avoid searching the entire parameter
1058             // range as it is a real performance bottleneck in case of regular
1059             // expressions.
1060             PositionType aPosSave;
1061             do
1062             {
1063                 nFoundCol = GetCol();
1064                 nFoundRow = GetRow();
1065                 aPosSave = maCurPos;
1066                 SetStopOnMismatch( true );
1067             } while (GetNext());
1068             nCol = nFoundCol;
1069             nRow = nFoundRow;
1070             maCurPos = std::move(aPosSave);
1071         }
1072     }
1073     return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
1074 }
1075
1076 // Direct linear cell access using mdds.
1077
1078 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
1079     ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument,
1080         ScInterpreterContext& rContext, const ScQueryParam& rParam, bool bReverseSearch )
1081     : maParam( rParam )
1082     , rDoc( rDocument )
1083     , mrContext( rContext )
1084     , mbReverseSearch( bReverseSearch )
1085 {
1086     // coverity[uninit_member] - this just contains data, subclass will initialize some of it
1087 }
1088
1089 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::InitPos()
1090 {
1091     if (!mbReverseSearch)
1092     {
1093         nRow = maParam.nRow1;
1094         if (maParam.bHasHeader && maParam.bByRow)
1095             ++nRow;
1096     }
1097     else
1098     {
1099         nRow = maParam.nRow2;
1100     }
1101     const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1102     maCurPos = rCol.maCells.position(nRow);
1103 }
1104
1105 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::IncPos()
1106 {
1107     if (maCurPos.second + 1 < maCurPos.first->size)
1108     {
1109         // Move within the same block.
1110         ++maCurPos.second;
1111         ++nRow;
1112     }
1113     else
1114         // Move to the next block.
1115         IncBlock();
1116 }
1117
1118 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::DecPos()
1119 {
1120     if (maCurPos.second > 0)
1121     {
1122         // Move within the same block.
1123         --maCurPos.second;
1124         --nRow;
1125     }
1126     else
1127         // Move to the prev block.
1128         DecBlock();
1129 }
1130
1131 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::IncBlock()
1132 {
1133     ++maCurPos.first;
1134     maCurPos.second = 0;
1135
1136     nRow = maCurPos.first->position;
1137 }
1138
1139 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::DecBlock()
1140 {
1141     // Set current position to the last possible row.
1142     const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1143     if (maCurPos.first != rCol.maCells.begin())
1144     {
1145         --maCurPos.first;
1146         maCurPos.second = maCurPos.first->size - 1;
1147
1148         nRow = maCurPos.first->position + maCurPos.second;
1149     }
1150     else
1151     {
1152         // No rows, set to end. This will make PerformQuery() go to next column.
1153         nRow = maParam.nRow1 - 1;
1154         maCurPos.first = rCol.maCells.end();
1155         maCurPos.second = 0;
1156     }
1157 }
1158
1159 /**
1160  * This class sequentially indexes non-empty cells in order, from the top of
1161  * the block where the start row position is, to the bottom of the block
1162  * where the end row position is.  It skips all empty blocks that may be
1163  * present in between.
1164  *
1165  * The index value is an offset from the first element of the first block
1166  * disregarding all empty cell blocks.
1167  */
1168 class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::NonEmptyCellIndexer
1169 {
1170     typedef std::map<size_t, sc::CellStoreType::const_iterator> BlockMapType;
1171
1172     BlockMapType maBlockMap;
1173
1174     const sc::CellStoreType* mpCells;
1175
1176     size_t mnLowIndex;
1177     size_t mnHighIndex;
1178
1179     bool mbValid;
1180
1181 public:
1182     /**
1183      * @param rCells cell storage container
1184      * @param nStartRow logical start row position
1185      * @param nEndRow logical end row position, inclusive.
1186      */
1187     NonEmptyCellIndexer(
1188         const sc::CellStoreType* pCells, SCROW nStartRow, SCROW nEndRow) :
1189         mpCells(pCells), mnLowIndex(0), mnHighIndex(0), mbValid(true)
1190     {
1191         // Find the low position.
1192
1193         sc::CellStoreType::const_position_type aLoPos = mpCells->position(nStartRow);
1194         assert(aLoPos.first->type != sc::element_type_empty);
1195         assert(aLoPos.first != mpCells->end());
1196
1197         SCROW nFirstRow = aLoPos.first->position;
1198         SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1;
1199
1200         if (nFirstRow > nEndRow)
1201         {
1202             // Both start and end row positions are within the leading skipped
1203             // blocks.
1204             mbValid = false;
1205             return;
1206         }
1207
1208         // Calculate the index of the low position.
1209         if (nFirstRow < nStartRow)
1210             mnLowIndex = nStartRow - nFirstRow;
1211         else
1212         {
1213             // Start row is within the skipped block(s). Set it to the first
1214             // element of the low block.
1215             mnLowIndex = 0;
1216         }
1217
1218         if (nEndRow < nLastRow)
1219         {
1220             assert(nEndRow >= nFirstRow);
1221             mnHighIndex = nEndRow - nFirstRow;
1222
1223             maBlockMap.emplace(aLoPos.first->size, aLoPos.first);
1224             return;
1225         }
1226
1227         // Find the high position.
1228
1229         sc::CellStoreType::const_position_type aHiPos = mpCells->position(aLoPos.first, nEndRow);
1230         if (aHiPos.first->type == sc::element_type_empty)
1231         {
1232             // Move to the last position of the previous block.
1233             decBlock(aHiPos);
1234
1235             // Check the row position of the end of the previous block, and make sure it's valid.
1236             SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size - 1;
1237             if (nBlockEndRow < nStartRow)
1238             {
1239                 mbValid = false;
1240                 return;
1241             }
1242         }
1243
1244         // Tag the start and end blocks, and all blocks in between in order
1245         // but skip all empty blocks.
1246
1247         size_t nPos = 0;
1248         sc::CellStoreType::const_iterator itBlk = aLoPos.first;
1249         while (itBlk != aHiPos.first)
1250         {
1251             if (itBlk->type == sc::element_type_empty)
1252             {
1253                 ++itBlk;
1254                 continue;
1255             }
1256
1257             nPos += itBlk->size;
1258             maBlockMap.emplace(nPos, itBlk);
1259             ++itBlk;
1260
1261             if (itBlk->type == sc::element_type_empty)
1262                 ++itBlk;
1263
1264             assert(itBlk != mpCells->end());
1265         }
1266
1267         assert(itBlk == aHiPos.first);
1268         nPos += itBlk->size;
1269         maBlockMap.emplace(nPos, itBlk);
1270
1271         // Calculate the high index.
1272         BlockMapType::const_reverse_iterator ri = maBlockMap.rbegin();
1273         mnHighIndex = ri->first;
1274         mnHighIndex -= ri->second->size;
1275         mnHighIndex += aHiPos.second;
1276     }
1277
1278     sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
1279     {
1280         assert(mbValid);
1281         assert(mnLowIndex <= nIndex);
1282         assert(nIndex <= mnHighIndex);
1283
1284         sc::CellStoreType::const_position_type aRet(mpCells->end(), 0);
1285
1286         BlockMapType::const_iterator it = maBlockMap.upper_bound(nIndex);
1287         if (it == maBlockMap.end())
1288             return aRet;
1289
1290         sc::CellStoreType::const_iterator itBlk = it->second;
1291         size_t nBlkIndex = it->first - itBlk->size; // index of the first element of the block.
1292         assert(nBlkIndex <= nIndex);
1293         assert(nIndex < it->first);
1294
1295         size_t nOffset = nIndex - nBlkIndex;
1296         aRet.first = std::move(itBlk);
1297         aRet.second = nOffset;
1298         return aRet;
1299     }
1300
1301     BinarySearchCellType getCell( size_t nIndex ) const
1302     {
1303         BinarySearchCellType aRet;
1304         aRet.second = -1;
1305
1306         sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
1307         if (aPos.first == mpCells->end())
1308             return aRet;
1309
1310         aRet.first = sc::toRefCell(aPos.first, aPos.second);
1311         aRet.second = aPos.first->position + aPos.second;
1312         return aRet;
1313     }
1314
1315     // TODO: NonEmptyCellIndexer for columns search
1316     static sc::CellStoreType::const_position_type getColPosition(size_t /*nIndex*/, SCROW /*nRow*/)
1317     {
1318         return sc::CellStoreType::const_position_type();
1319     }
1320
1321     // TODO: NonEmptyCellIndexer for columns search
1322     static BinarySearchCellType getColCell(size_t /*nIndex*/, SCROW /*nRow*/)
1323     {
1324         BinarySearchCellType aRet;
1325         return aRet;
1326     }
1327
1328     size_t getLowIndex() const { return mnLowIndex; }
1329
1330     size_t getHighIndex() const { return mnHighIndex; }
1331
1332     bool isValid() const { return mbValid; }
1333 };
1334
1335 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::NonEmptyCellIndexer
1336 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::MakeBinarySearchIndexer(
1337     const sc::CellStoreType* pCells, SCCOLROW nStartRow, SCCOLROW nEndRow)
1338 {
1339     return NonEmptyCellIndexer(pCells, nStartRow, nEndRow);
1340 }
1341
1342 // Sorted access using ScSortedRangeCache.
1343
1344 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >
1345     ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument,
1346         ScInterpreterContext& rContext, const ScQueryParam& rParam, bool bReverseSearch )
1347     : maParam( rParam )
1348     , rDoc( rDocument )
1349     , mrContext( rContext )
1350     , mbReverseSearch( bReverseSearch )
1351 {
1352     // coverity[uninit_member] - this just contains data, subclass will initialize some of it
1353 }
1354
1355 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::SetSortedRangeCache(
1356     const ScSortedRangeCache& cache)
1357 {
1358     sortedCache = &cache;
1359 }
1360
1361 // The idea in iterating using the sorted cache is that the iteration is instead done
1362 // over indexes of the sorted cache (which is a stable sort of the cell contents) in the range
1363 // that fits the query condition and then that is mapped to rows. This will result in iterating
1364 // over only matching rows in their sorted order (and for equal rows in their row order).
1365 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::InitPosStart(bool bNewSearchFunction, sal_uInt8 nSortedBinarySearch)
1366 {
1367     ScRange aSortedRangeRange( maParam.nCol1, maParam.nRow1, nTab, maParam.nCol2, maParam.nRow2, nTab );
1368     // We want all matching values first in the sort order,
1369     SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange, maParam, &mrContext, bNewSearchFunction, nSortedBinarySearch ));
1370     // InitPosFinish() needs to be called after this, ScQueryCellIteratorBase::InitPos()
1371     // will handle that
1372 }
1373
1374 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::InitPosFinish(
1375     SCROW beforeRow, SCROW lastRow, bool bFirstMatch )
1376 {
1377     pColumn = &rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1378     if(lastRow >= 0)
1379     {
1380         sortedCachePos = beforeRow >= 0 ? sortedCache->indexForRow(beforeRow) + 1 : 0;
1381         sortedCachePosLast = sortedCache->indexForRow(lastRow);
1382         if(sortedCachePos <= sortedCachePosLast)
1383         {
1384             if (!bFirstMatch)
1385                 nRow = sortedCache->rowForIndex(sortedCachePos);
1386             else
1387                 nRow = sortedCache->rowForIndex(sortedCachePosLast);
1388             maCurPos = pColumn->maCells.position(nRow);
1389             return;
1390         }
1391     }
1392     // No rows, set to end.
1393     sortedCachePos = sortedCachePosLast = 0;
1394     maCurPos.first = pColumn->maCells.end();
1395     maCurPos.second = 0;
1396 }
1397
1398 void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::InitPosColFinish(
1399     SCCOL beforeCol, SCCOL lastCol, bool bFirstMatch)
1400 {
1401     pColumn = &rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1402     if (lastCol >= 0)
1403     {
1404         sortedCachePos = beforeCol >= 0 ? sortedCache->indexForCol(beforeCol) + 1 : 0;
1405         sortedCachePosLast = sortedCache->indexForCol(lastCol);
1406         if (sortedCachePos <= sortedCachePosLast)
1407         {
1408             if (!bFirstMatch)
1409                 nCol = sortedCache->colForIndex(sortedCachePos);
1410             else
1411                 nCol = sortedCache->colForIndex(sortedCachePosLast);
1412             pColumn = &rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1413             maCurPos = pColumn->maCells.position(nRow);
1414             return;
1415         }
1416     }
1417     // No cols, set to end.
1418     sortedCachePos = sortedCachePosLast = 0;
1419     maCurPos.first = pColumn->maCells.end();
1420     maCurPos.second = 0;
1421 }
1422
1423 template<bool fast>
1424 bool ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::IncPosImpl()
1425 {
1426     if(sortedCachePos < sortedCachePosLast)
1427     {
1428         ++sortedCachePos;
1429         if (maParam.bByRow)
1430             nRow = sortedCache->rowForIndex(sortedCachePos);
1431         else
1432             nCol = sortedCache->colForIndex(sortedCachePos);
1433 #ifndef DBG_UTIL
1434         if constexpr (!fast)
1435 #endif
1436         {
1437             if (maParam.bByRow)
1438             {
1439                 // Avoid mdds position() call if row is in the same block.
1440                 if (maCurPos.first != pColumn->maCells.end() && o3tl::make_unsigned(nRow) >= maCurPos.first->position
1441                     && o3tl::make_unsigned(nRow) < maCurPos.first->position + maCurPos.first->size)
1442                     maCurPos.second = nRow - maCurPos.first->position;
1443                 else
1444                     maCurPos = pColumn->maCells.position(nRow);
1445             }
1446         }
1447         return true;
1448     }
1449     else
1450     {
1451         // This will make PerformQuery() go to next column.
1452         // Necessary even in fast mode, as GetNext() will call GetThis() in this case.
1453         if (!maParam.bByRow)
1454             ++nRow;
1455         maCurPos.first = pColumn->maCells.end();
1456         maCurPos.second = 0;
1457         return false;
1458     }
1459 }
1460
1461 template
1462 bool ScQueryCellIteratorAccessSpecific<ScQueryCellIteratorAccess::SortedCache>::IncPosImpl<false>();
1463 template
1464 bool ScQueryCellIteratorAccessSpecific<ScQueryCellIteratorAccess::SortedCache>::IncPosImpl<true>();
1465
1466 // Helper that allows binary search of unsorted cells using ScSortedRangeCache.
1467 // Rows in the given range are kept in a sorted vector and that vector is binary-searched.
1468 class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::SortedCacheIndexer
1469 {
1470     std::vector<SCCOLROW> mSortedColsRowsCopy;
1471     const std::vector<SCCOLROW>& mSortedColsRows;
1472     ScDocument& mrDoc;
1473     const sc::CellStoreType* mpCells;
1474     size_t mLowIndex;
1475     size_t mHighIndex;
1476     bool mValid;
1477     SCTAB mnTab;
1478
1479     const std::vector<SCCOLROW>& makeSortedColsRows( const ScSortedRangeCache* cache, SCCOLROW startColRow, SCCOLROW endColRow )
1480     {
1481         // Keep a reference to cols/rows from the cache if equal, otherwise make a copy.
1482         if (cache->isRowSearch())
1483         {
1484             if (startColRow == cache->getRange().aStart.Row() && endColRow == cache->getRange().aEnd.Row())
1485                 return cache->sortedRows();
1486             else
1487             {
1488                 mSortedColsRowsCopy.reserve(cache->sortedRows().size());
1489                 for (SCROW row : cache->sortedRows())
1490                     if (row >= startColRow && row <= endColRow)
1491                         mSortedColsRowsCopy.emplace_back(row);
1492                 return mSortedColsRowsCopy;
1493             }
1494         }
1495         else
1496         {
1497             if (startColRow == cache->getRange().aStart.Col() && endColRow == cache->getRange().aEnd.Col())
1498                 return cache->sortedCols();
1499             else
1500             {
1501                 mSortedColsRowsCopy.reserve(cache->sortedCols().size());
1502                 for (SCCOL col : cache->sortedCols())
1503                     if (col >= startColRow && col <= endColRow)
1504                         mSortedColsRowsCopy.emplace_back(col);
1505                 return mSortedColsRowsCopy;
1506             }
1507         }
1508     }
1509
1510 public:
1511     SortedCacheIndexer( ScDocument& rDoc, const sc::CellStoreType* cells,
1512         SCCOLROW startColRow, SCCOLROW endColRow, SCTAB nTab,
1513         const ScSortedRangeCache* cache )
1514         : mSortedColsRows( makeSortedColsRows( cache, startColRow, endColRow))
1515         , mrDoc( rDoc )
1516         , mpCells( cells )
1517         , mValid( false )
1518         , mnTab( nTab )
1519     {
1520         if(mSortedColsRows.empty())
1521         {
1522             // coverity[uninit_member] - these are initialized only if valid
1523             return;
1524         }
1525         mLowIndex = 0;
1526         mHighIndex = mSortedColsRows.size() - 1;
1527         mValid = true;
1528     }
1529
1530     sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
1531     {
1532         // TODO optimize?
1533         SCROW row = mSortedColsRows[ nIndex ];
1534         return mpCells->position(row);
1535     }
1536
1537     BinarySearchCellType getCell( size_t nIndex ) const
1538     {
1539         BinarySearchCellType aRet;
1540         aRet.second = -1;
1541
1542         sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
1543         if (aPos.first == mpCells->end())
1544             return aRet;
1545
1546         aRet.first = sc::toRefCell(aPos.first, aPos.second);
1547         aRet.second = aPos.first->position + aPos.second;
1548         return aRet;
1549     }
1550
1551     sc::CellStoreType::const_position_type getColPosition( size_t nColIndex, SCROW nRowPos ) const
1552     {
1553         // TODO optimize?
1554         SCCOL col = mSortedColsRows[nColIndex];
1555         if (col >= mrDoc.maTabs[mnTab]->GetAllocatedColumnsCount())
1556             return sc::CellStoreType::const_position_type();
1557
1558         const ScColumn& rCol = mrDoc.maTabs[mnTab]->aCol[col];
1559         return rCol.maCells.position(nRowPos);
1560     }
1561
1562     BinarySearchCellType getColCell( size_t nColIndex, SCROW nRowPos) const
1563     {
1564         BinarySearchCellType aRet;
1565         aRet.second = -1;
1566
1567         sc::CellStoreType::const_position_type aPos = getColPosition(nColIndex, nRowPos);
1568
1569         aRet.first = sc::toRefCell(aPos.first, aPos.second);
1570         aRet.second = mSortedColsRows[nColIndex];
1571
1572         return aRet;
1573     }
1574
1575     size_t getLowIndex() const { return mLowIndex; }
1576
1577     size_t getHighIndex() const { return mHighIndex; }
1578
1579     bool isValid() const { return mValid; }
1580 };
1581
1582 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::SortedCacheIndexer
1583 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::MakeBinarySearchIndexer(
1584     const sc::CellStoreType* pCells, SCCOLROW nStartRow, SCCOLROW nEndRow)
1585 {
1586     return SortedCacheIndexer(rDoc, pCells, nStartRow, nEndRow, nTab, sortedCache);
1587 }
1588
1589 static bool CanBeUsedForSorterCache(ScDocument& /*rDoc*/, const ScQueryParam& /*rParam*/,
1590     SCTAB /*nTab*/, const ScFormulaCell* /*cell*/, const ScComplexRefData* /*refData*/,
1591     ScInterpreterContext& /*context*/)
1592 {
1593 #if 1
1594     /* TODO: tdf#151958 broken by string query of binary search on sorted
1595      * cache, use the direct query instead for releases and fix SortedCache
1596      * implementation after. Not only COUNTIF() is broken, but also COUNTIFS(),
1597      * and maybe lcl_LookupQuery() for VLOOKUP() etc. as well. Just disable
1598      * this for now.
1599      * Can't just return false because below would be unreachable code. Can't
1600      * just #if/#else/#endif either because parameters would be unused. Crap
1601      * this and comment out parameter names. */
1602     return false;
1603 #else
1604     if(!rParam.GetEntry(0).bDoQuery || rParam.GetEntry(1).bDoQuery
1605         || rParam.GetEntry(0).GetQueryItems().size() != 1 )
1606         return false;
1607     if(rParam.eSearchType != utl::SearchParam::SearchType::Normal)
1608         return false;
1609     if(rParam.GetEntry(0).GetQueryItem().meType != ScQueryEntry::ByValue
1610         && rParam.GetEntry(0).GetQueryItem().meType != ScQueryEntry::ByString)
1611         return false;
1612     if(!rParam.bByRow)
1613         return false;
1614     if(rParam.bHasHeader)
1615         return false;
1616     if(rParam.mbRangeLookup)
1617         return false;
1618     const bool bNewSearchFunction = nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH;
1619     if(rParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString && !bNewSearchFunction
1620         && !ScQueryEvaluator::isMatchWholeCell(rDoc, rParam.GetEntry(0).eOp))
1621         return false; // substring matching cannot be sorted
1622     if(rParam.GetEntry(0).eOp != SC_LESS && rParam.GetEntry(0).eOp != SC_LESS_EQUAL
1623         && rParam.GetEntry(0).eOp != SC_GREATER && rParam.GetEntry(0).eOp != SC_GREATER_EQUAL
1624         && rParam.GetEntry(0).eOp != SC_EQUAL)
1625         return false;
1626     // For unittests allow inefficient caching, in order for the code to be checked.
1627     static const bool bRunningUnitTest = o3tl::IsRunningUnitTest();
1628     if(refData == nullptr || refData->Ref1.IsRowRel() || refData->Ref2.IsRowRel())
1629     {
1630         // If this is not a range, then a cache is not worth it. If rows are relative, then each
1631         // computation will use a different area, so the cache wouldn't be reused. Tab/cols are
1632         // not a problem, because formula group computations are done for the same tab/col.
1633         if(!bRunningUnitTest)
1634             return false;
1635     }
1636     if(rParam.nRow2 - rParam.nRow1 < 10)
1637     {
1638         if(!bRunningUnitTest)
1639             return false;
1640     }
1641     if( !cell )
1642         return false;
1643     if( !cell->GetCellGroup() || cell->GetCellGroup()->mnLength < 10 )
1644     {
1645         if(!bRunningUnitTest)
1646             return false;
1647     }
1648     // Check that all the relevant caches would be valid (may not be the case when mixing
1649     // numeric and string cells for ByValue lookups).
1650     for(SCCOL col : rDoc.GetAllocatedColumnsRange(nTab, rParam.nCol1, rParam.nCol2))
1651     {
1652         ScRange aSortedRangeRange( col, rParam.nRow1, nTab, col, rParam.nRow2, nTab);
1653         if( aSortedRangeRange.Contains( cell->aPos ))
1654             return false; // self-referencing, can't create cache
1655         ScSortedRangeCache& cache = rDoc.GetSortedRangeCache( aSortedRangeRange, rParam, &context );
1656         if(!cache.isValid())
1657             return false;
1658     }
1659     return true;
1660 #endif
1661 }
1662
1663 // Generic query implementation.
1664
1665 bool ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::Generic >::HandleItemFound()
1666 {
1667     getThisResult = true;
1668     return true; // Return from PerformQuery().
1669 }
1670
1671 template< ScQueryCellIteratorAccess accessType >
1672 bool ScQueryCellIterator< accessType >::GetThis()
1673 {
1674     getThisResult = false;
1675     PerformQuery();
1676     return getThisResult;
1677 }
1678
1679 template< ScQueryCellIteratorAccess accessType >
1680 bool ScQueryCellIterator< accessType >::GetFirst()
1681 {
1682     assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
1683     if (!mbReverseSearch)
1684         nCol = maParam.nCol1;
1685     else
1686         nCol = maParam.nCol2;
1687     InitPos();
1688     return GetThis();
1689 }
1690
1691 template< ScQueryCellIteratorAccess accessType >
1692 bool ScQueryCellIterator< accessType >::GetNext()
1693 {
1694     if (!mbReverseSearch)
1695         IncPos();
1696     else
1697         DecPos();
1698     if ( nStopOnMismatch )
1699         nStopOnMismatch = nStopOnMismatchEnabled;
1700     if ( nTestEqualCondition )
1701         nTestEqualCondition = nTestEqualConditionEnabled;
1702     return GetThis();
1703 }
1704
1705 template<>
1706 bool ScQueryCellIterator< ScQueryCellIteratorAccess::SortedCache >::GetNext()
1707 {
1708     assert( !nStopOnMismatch );
1709     assert( !nTestEqualCondition );
1710     // When searching using sorted cache, we should always find cells that match,
1711     // because InitPos()/IncPos() select only such rows, so skip GetThis() (and thus
1712     // the somewhat expensive PerformQuery) as long as we're not at the end
1713     // of a column. As an optimization IncPosFast() returns true if not at the end,
1714     // in which case in non-DBG_UTIL mode it doesn't even bother to set maCurPos.
1715     if( IncPosFast())
1716     {
1717 #ifdef DBG_UTIL
1718         assert(GetThis());
1719 #endif
1720         return true;
1721     }
1722     return GetThis();
1723 }
1724
1725 bool ScQueryCellIteratorSortedCache::CanBeUsed(ScDocument& rDoc, const ScQueryParam& rParam,
1726     SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
1727     ScInterpreterContext& context)
1728 {
1729     return CanBeUsedForSorterCache(rDoc, rParam, nTab, cell, refData, context);
1730 }
1731
1732 // Countifs implementation.
1733
1734 bool ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::CountIf >::HandleItemFound()
1735 {
1736     ++countIfCount;
1737     return false; // Continue searching.
1738 }
1739
1740 template< ScQueryCellIteratorAccess accessType >
1741 sal_uInt64 ScCountIfCellIterator< accessType >::GetCount()
1742 {
1743     // Keep Entry.nField in iterator on column change
1744     SetAdvanceQueryParamEntryField( true );
1745     assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds, FIX IT");
1746     maParam.nCol1 = rDoc.ClampToAllocatedColumns(nTab, maParam.nCol1);
1747     maParam.nCol2 = rDoc.ClampToAllocatedColumns(nTab, maParam.nCol2);
1748     nCol = maParam.nCol1;
1749     InitPos();
1750     countIfCount = 0;
1751     PerformQuery();
1752     return countIfCount;
1753 }
1754
1755
1756 bool ScCountIfCellIteratorSortedCache::CanBeUsed(ScDocument& rDoc, const ScQueryParam& rParam,
1757     SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
1758     ScInterpreterContext& context)
1759 {
1760     return CanBeUsedForSorterCache(rDoc, rParam, nTab, cell, refData, context);
1761 }
1762
1763 template<>
1764 sal_uInt64 ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >::GetCount()
1765 {
1766     // Keep Entry.nField in iterator on column change
1767     SetAdvanceQueryParamEntryField( true );
1768     assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds, FIX IT");
1769     sal_uInt64 count = 0;
1770     // Each column must be sorted separately.
1771     for(SCCOL col : rDoc.GetAllocatedColumnsRange(nTab, maParam.nCol1, maParam.nCol2))
1772     {
1773         nCol = col;
1774         nRow = maParam.nRow1;
1775         ScRange aSortedRangeRange( col, maParam.nRow1, nTab, col, maParam.nRow2, nTab);
1776         ScQueryOp& op = maParam.GetEntry(0).eOp;
1777         bool bNewSearchFunction = nSearchOpCode == SC_OPCODE_X_LOOKUP || nSearchOpCode == SC_OPCODE_X_MATCH;
1778         SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange, maParam, &mrContext, bNewSearchFunction, nSearchOpCode ));
1779         if( op == SC_EQUAL )
1780         {
1781             // BinarySearch() searches for the last item that matches. Therefore first
1782             // find the last non-matching position using SC_LESS and then find the last
1783             // matching position using SC_EQUAL.
1784             ScQueryOp saveOp = op;
1785             op = SC_LESS;
1786             if( BinarySearch( nCol, true ))
1787             {
1788                 op = saveOp; // back to SC_EQUAL
1789                 size_t lastNonMatching = sortedCache->indexForRow(nRow);
1790                 if( BinarySearch( nCol ))
1791                 {
1792                     size_t lastMatching = sortedCache->indexForRow(nRow);
1793                     assert(lastMatching >= lastNonMatching);
1794                     count += lastMatching - lastNonMatching;
1795                 }
1796                 else
1797                 {
1798                     // BinarySearch() should at least find the same result as the SC_LESS
1799                     // call, so this should not happen.
1800                     assert(false);
1801                 }
1802             }
1803             else
1804             {
1805                 // BinarySearch() returning false means that all values are larger,
1806                 // so try to find matching ones and count those up to and including
1807                 // the found one.
1808                 op = saveOp; // back to SC_EQUAL
1809                 if( BinarySearch( nCol ))
1810                 {
1811                     size_t lastMatching = sortedCache->indexForRow(nRow) + 1;
1812                     count += lastMatching;
1813                 }
1814                 else if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
1815                     && rDoc.IsEmptyData(col, maParam.nRow1, col, maParam.nRow2, nTab))
1816                 {
1817                     // BinarySearch() returns false in case it's all empty data,
1818                     // handle that specially.
1819                     count += maParam.nRow2 - maParam.nRow1 + 1;
1820                 }
1821             }
1822         }
1823         else
1824         {
1825             // BinarySearch() searches for the last item that matches. Therefore everything
1826             // up to and including the found row matches the condition.
1827             if( BinarySearch( nCol ))
1828                 count += sortedCache->indexForRow(nRow) + 1;
1829         }
1830     }
1831     if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
1832         && maParam.nCol2 >= rDoc.GetAllocatedColumnsCount( nTab ))
1833     {
1834         const sal_uInt64 nRows = maParam.nRow2 - maParam.nRow1 + 1;
1835         count += (maParam.nCol2 - rDoc.GetAllocatedColumnsCount(nTab)) * nRows;
1836     }
1837     return count;
1838 }
1839
1840 template class ScQueryCellIterator< ScQueryCellIteratorAccess::Direct >;
1841 template class ScQueryCellIterator< ScQueryCellIteratorAccess::SortedCache >;
1842 template class ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct >;
1843 template class ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >;
1844
1845 // gcc for some reason needs these too
1846 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct, ScQueryCellIteratorType::Generic >;
1847 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::SortedCache, ScQueryCellIteratorType::Generic >;
1848 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct, ScQueryCellIteratorType::CountIf >;
1849 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::SortedCache, ScQueryCellIteratorType::CountIf >;
1850
1851 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */