LibreOffice Module sc (master) 1
queryiter.cxx
Go to the documentation of this file.
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
23#include <o3tl/safeint.hxx>
24#include <svl/numformat.hxx>
25#include <svl/zforlist.hxx>
26
27#include <global.hxx>
28#include <dociter.hxx>
29#include <document.hxx>
30#include <table.hxx>
31#include <column.hxx>
32#include <formulacell.hxx>
33#include <attarray.hxx>
34#include <patattr.hxx>
35#include <docoptio.hxx>
36#include <cellform.hxx>
37#include <segmenttree.hxx>
38#include <progress.hxx>
39#include <queryparam.hxx>
40#include <queryentry.hxx>
41#include <globstr.hrc>
42#include <scresid.hxx>
43#include <cellvalue.hxx>
44#include <scmatrix.hxx>
45#include <rowheightcontext.hxx>
46#include <queryevaluator.hxx>
47#include <rangecache.hxx>
48#include <refdata.hxx>
49
50#include <o3tl/safeint.hxx>
51#include <tools/fract.hxx>
52#include <editeng/editobj.hxx>
53#include <svl/sharedstring.hxx>
55#include <osl/diagnose.h>
56#include <sal/log.hxx>
57
58#include <algorithm>
59#include <limits>
60#include <vector>
61
62template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
64 ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam& rParam, bool bMod )
65 : AccessBase( rDocument, rContext, rParam )
66 , nStopOnMismatch( nStopOnMismatchDisabled )
67 , nTestEqualCondition( nTestEqualConditionDisabled )
68 , bAdvanceQuery( false )
69 , bIgnoreMismatchOnLeadingStrings( false )
70{
71 nTab = nTable;
72 nCol = maParam.nCol1;
73 nRow = maParam.nRow1;
74 SCSIZE i;
75 if (!bMod) // Or else it's already inserted
76 return;
77
78 SCSIZE nCount = maParam.GetEntryCount();
79 for (i = 0; (i < nCount) && (maParam.GetEntry(i).bDoQuery); ++i)
80 {
81 ScQueryEntry& rEntry = maParam.GetEntry(i);
82 ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
83 sal_uInt32 nIndex = 0;
84 bool bNumber = mrContext.GetFormatTable()->IsNumberFormat(
85 rItem.maString.getString(), nIndex, rItem.mfVal);
87 }
88}
89
90template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
92{
93 assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
94 const ScQueryEntry& rEntry = maParam.GetEntry(0);
95 const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
96
97 const bool bSingleQueryItem = rEntry.GetQueryItems().size() == 1;
98 SCCOLROW nFirstQueryField = rEntry.nField;
99 bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings &&
101 bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
102 !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString &&
103 ((maParam.bByRow && nRow == maParam.nRow1) ||
104 (!maParam.bByRow && nCol == maParam.nCol1));
105 bool bTestEqualCondition = false;
106 ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam, &mrContext,
107 (nTestEqualCondition ? &bTestEqualCondition : nullptr));
108 if( queryType == ScQueryCellIteratorType::CountIf )
109 {
110 // These are not used for COUNTIF, so should not be set, make the compiler
111 // explicitly aware of it so that the relevant parts are optimized away.
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;
120 // This one is always set.
121 assert( bAdvanceQuery );
122 bAdvanceQuery = true;
123 }
124
125 ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
126 while (true)
127 {
128 bool bNextColumn = maCurPos.first == pCol->maCells.end();
129 if (!bNextColumn)
130 {
131 if (nRow > maParam.nRow2)
132 bNextColumn = true;
133 }
134
135 if (bNextColumn)
136 {
137 do
138 {
139 ++nCol;
140 if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
141 return;
142 if ( bAdvanceQuery )
143 {
144 AdvanceQueryParamEntryField();
145 nFirstQueryField = rEntry.nField;
146 }
147 pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
148 }
149 while (!rItem.mbMatchEmpty && pCol->IsEmptyData());
150
151 InitPos();
152
153 bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
154 !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString &&
155 maParam.bByRow;
156 }
157
158 if (maCurPos.first->type == sc::element_type_empty)
159 {
160 if (rItem.mbMatchEmpty && bSingleQueryItem)
161 {
162 // This shortcut, instead of determining if any SC_OR query
163 // exists or this query is SC_AND'ed (which wouldn't make
164 // sense, but..) and evaluating them in ValidQuery(), is
165 // possible only because the interpreter is the only caller
166 // that sets mbMatchEmpty and there is only one item in those
167 // cases.
168 // XXX this would have to be reworked if other filters used it
169 // in different manners and evaluation would have to be done in
170 // ValidQuery().
171 if(HandleItemFound())
172 return;
173 IncPos();
174 continue;
175 }
176 else
177 {
178 IncBlock();
179 continue;
180 }
182
183 ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second);
184
185 if (bAllStringIgnore && aCell.hasString())
186 IncPos();
187 else
188 {
189 if ( queryEvaluator.ValidQuery( nRow,
190 (nCol == static_cast<SCCOL>(nFirstQueryField) ? &aCell : nullptr)))
191 {
192 if ( nTestEqualCondition && bTestEqualCondition )
193 nTestEqualCondition |= nTestEqualConditionMatched;
194 if ( aCell.isEmpty())
195 return;
196 if( HandleItemFound())
197 return;
198 IncPos();
199 continue;
200 }
201 else if ( nStopOnMismatch )
202 {
203 // Yes, even a mismatch may have a fulfilled equal
204 // condition if regular expressions were involved and
205 // SC_LESS_EQUAL or SC_GREATER_EQUAL were queried.
206 if ( nTestEqualCondition && bTestEqualCondition )
207 {
208 nTestEqualCondition |= nTestEqualConditionMatched;
209 nStopOnMismatch |= nStopOnMismatchOccurred;
210 return;
211 }
212 bool bStop;
213 if (bFirstStringIgnore)
214 {
215 if (aCell.hasString())
216 {
217 IncPos();
218 bStop = false;
219 }
220 else
221 bStop = true;
222 }
223 else
224 bStop = true;
225 if (bStop)
226 {
227 nStopOnMismatch |= nStopOnMismatchOccurred;
228 return;
229 }
230 }
231 else
232 IncPos();
233 }
234 bFirstStringIgnore = false;
235 }
236}
237
238template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
241 if constexpr( accessType != ScQueryCellIteratorAccess::SortedCache )
242 AccessBase::InitPos();
243 else
244 {
245 // This should be all in AccessBase::InitPos(), but that one can't call
246 // BinarySearch(), so do it this way instead.
247 AccessBase::InitPosStart();
248 ScQueryOp& op = maParam.GetEntry(0).eOp;
249 SCROW beforeRow = -1;
250 SCROW lastRow = -1;
251 if( op == SC_EQUAL )
252 {
253 if( BinarySearch( nCol ))
254 {
255 // BinarySearch() searches for the last item that matches. Now we
256 // also need to find the first item where to start. Find the last
257 // non-matching position using SC_LESS and the start position
258 // is the one after it.
259 lastRow = nRow;
260 ScQueryOp saveOp = op;
261 op = SC_LESS;
262 if( BinarySearch( nCol, true ))
263 beforeRow = nRow;
264 // If BinarySearch() returns false, there was no match, which means
265 // there's no value smaller. In that case BinarySearch() has set
266 // the position to the first row in the range.
267 op = saveOp; // back to SC_EQUAL
268 }
269 else if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
270 && rDoc.IsEmptyData(nCol, maParam.nRow1, nCol, maParam.nRow2, nTab))
271 {
272 // BinarySearch() returns false in case it's all empty data,
273 // handle that specially.
274 beforeRow = -1;
275 lastRow = maParam.nRow2;
276 }
277 }
278 else
279 { // The range is from the start up to and including the last matching.
280 if( BinarySearch( nCol ))
281 lastRow = nRow;
282 }
283 AccessBase::InitPosFinish( beforeRow, lastRow );
284 }
285}
286
287template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
290 SCSIZE nEntries = maParam.GetEntryCount();
291 for ( SCSIZE j = 0; j < nEntries; j++ )
292 {
293 ScQueryEntry& rEntry = maParam.GetEntry( j );
294 if ( rEntry.bDoQuery )
295 {
296 if ( rEntry.nField < rDoc.MaxCol() )
297 rEntry.nField++;
298 else
299 {
300 assert(!"AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL");
301 }
302 }
303 else
304 break; // for
305 }
306}
307
308namespace {
309
310template<typename Iter>
311void incBlock(std::pair<Iter, size_t>& rPos)
313 // Move to the next block.
314 ++rPos.first;
315 rPos.second = 0;
316}
317
318template<typename Iter>
319void decBlock(std::pair<Iter, size_t>& rPos)
320{
321 // Move to the last element of the previous block.
322 --rPos.first;
323 rPos.second = rPos.first->size - 1;
324}
325
326}
327
328template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
330{
331 assert(maParam.GetEntry(0).bDoQuery && !maParam.GetEntry(1).bDoQuery
332 && maParam.GetEntry(0).GetQueryItems().size() == 1 );
333 assert(maParam.eSearchType == utl::SearchParam::SearchType::Normal);
334 assert(maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString
335 || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue);
336 assert(maParam.bByRow);
337 assert(maParam.GetEntry(0).eOp == SC_LESS || maParam.GetEntry(0).eOp == SC_LESS_EQUAL
338 || maParam.GetEntry(0).eOp == SC_GREATER || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL
339 || maParam.GetEntry(0).eOp == SC_EQUAL);
340
341 // TODO: This will be extremely slow with mdds::multi_type_vector.
342
343 assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
344 nCol = col;
345 nRow = maParam.nRow1;
346
347 if (nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount())
348 return false;
349
350 ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol];
351 if (pCol->IsEmptyData())
352 return false;
353
354 CollatorWrapper& rCollator = ScGlobal::GetCollator(maParam.bCaseSens);
355 SvNumberFormatter& rFormatter = *(mrContext.GetFormatTable());
356 const ScQueryEntry& rEntry = maParam.GetEntry(0);
357 const ScQueryEntry::Item& rItem = rEntry.GetQueryItem();
358 bool bAscending = rEntry.eOp == SC_LESS || rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_EQUAL;
359 bool bByString = rItem.meType == ScQueryEntry::ByString;
360 bool bForceStr = bByString && ( rEntry.eOp == SC_EQUAL || forEqual );
361 bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString;
362 bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings &&
363 !maParam.bHasHeader && bByString;
364
365 if (maParam.bHasHeader)
366 ++nRow;
367
368 if (bFirstStringIgnore)
369 {
370 sc::CellStoreType::const_position_type aPos = pCol->maCells.position(nRow);
371 if (aPos.first->type == sc::element_type_string || aPos.first->type == sc::element_type_edittext)
372 {
373 ScRefCellValue aCell = sc::toRefCell(aPos.first, aPos.second);
374 sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, nRow);
375 OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc);
376 sal_Int32 nTmp = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString());
377 if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) ||
378 (rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) ||
379 (rEntry.eOp == SC_EQUAL && nTmp != 0) ||
380 (rEntry.eOp == SC_LESS && nTmp >= 0) ||
381 (rEntry.eOp == SC_GREATER && nTmp <= 0))
382 ++nRow;
383 }
384 }
385
386 // Skip leading empty block, if any.
387 sc::CellStoreType::const_position_type startPos = pCol->maCells.position(nRow);
388 if (startPos.first->type == sc::element_type_empty)
389 incBlock(startPos);
390 if(bAllStringIgnore)
391 {
392 // Skip all leading string or empty blocks.
393 while (startPos.first != pCol->maCells.end()
394 && (startPos.first->type == sc::element_type_string ||
395 startPos.first->type == sc::element_type_edittext ||
396 startPos.first->type == sc::element_type_empty))
397 {
398 incBlock(startPos);
399 }
400 }
401 if(startPos.first == pCol->maCells.end())
402 return false;
403 nRow = startPos.first->position + startPos.second;
404 if (nRow > maParam.nRow2)
405 return false;
406
407 auto aIndexer = MakeBinarySearchIndexer(pCol->maCells, nRow, maParam.nRow2);
408 if (!aIndexer.isValid())
409 return false;
410
411 size_t nLo = aIndexer.getLowIndex();
412 size_t nHi = aIndexer.getHighIndex();
413 BinarySearchCellType aCellData;
414
415 // Bookkeeping values for breaking up the binary search in case the data
416 // range isn't strictly sorted.
417 size_t nLastInRange = nLo;
418 double fLastInRangeValue = bAscending ?
419 -(::std::numeric_limits<double>::max()) :
420 ::std::numeric_limits<double>::max();
421 OUString aLastInRangeString;
422 if (!bAscending)
423 aLastInRangeString = OUString(u'\xFFFF');
424
425 aCellData = aIndexer.getCell(nLastInRange);
426 ScRefCellValue aCell = aCellData.first;
427 if (bForceStr || aCell.hasString())
428 {
429 sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, aCellData.second);
430 OUString aStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc);
431 aLastInRangeString = aStr;
432 }
433 else
434 {
435 switch (aCell.getType())
436 {
437 case CELLTYPE_VALUE :
438 fLastInRangeValue = aCell.getDouble();
439 break;
440 case CELLTYPE_FORMULA :
441 fLastInRangeValue = aCell.getFormula()->GetValue();
442 break;
443 default:
444 {
445 // added to avoid warnings
446 }
447 }
448 }
449
450 sal_Int32 nRes = 0;
451 std::optional<size_t> found;
452 bool bDone = false;
453 bool orderBroken = false;
454 while (nLo <= nHi && !bDone)
455 {
456 size_t nMid = (nLo+nHi)/2;
457 size_t i = nMid;
458
459 aCellData = aIndexer.getCell(i);
460 aCell = aCellData.first;
461 bool bStr = bForceStr || aCell.hasString();
462 nRes = 0;
463
464 // compares are content<query:-1, content>query:1
465 // Cell value comparison similar to ScTable::ValidQuery()
466 if (!bStr && !bByString)
467 {
468 double nCellVal;
469 switch (aCell.getType())
470 {
471 case CELLTYPE_VALUE :
472 case CELLTYPE_FORMULA :
473 nCellVal = aCell.getValue();
474 break;
475 default:
476 nCellVal = 0.0;
477 }
478 if ((nCellVal < rItem.mfVal) && !::rtl::math::approxEqual(
479 nCellVal, rItem.mfVal))
480 {
481 nRes = -1;
482 if (bAscending)
483 {
484 if (fLastInRangeValue <= nCellVal)
485 {
486 fLastInRangeValue = nCellVal;
487 nLastInRange = i;
488 }
489 else if (fLastInRangeValue >= nCellVal)
490 {
491 // not strictly sorted, continue with GetThis()
492 orderBroken = true;
493 bDone = true;
494 }
495 }
496 }
497 else if ((nCellVal > rItem.mfVal) && !::rtl::math::approxEqual(
498 nCellVal, rItem.mfVal))
499 {
500 nRes = 1;
501 if (!bAscending)
502 {
503 if (fLastInRangeValue >= nCellVal)
504 {
505 fLastInRangeValue = nCellVal;
506 nLastInRange = i;
507 }
508 else if (fLastInRangeValue <= nCellVal)
509 {
510 // not strictly sorted, continue with GetThis()
511 orderBroken = true;
512 bDone = true;
513 }
514 }
515 }
516 }
517 else if (bStr && bByString)
518 {
519 sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, aCellData.second);
520 OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc);
521
522 nRes = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString());
523 if (nRes < 0 && bAscending)
524 {
525 sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
526 aCellStr);
527 if (nTmp <= 0)
528 {
529 aLastInRangeString = aCellStr;
530 nLastInRange = i;
531 }
532 else if (nTmp > 0)
533 {
534 // not strictly sorted, continue with GetThis()
535 orderBroken = true;
536 bDone = true;
537 }
538 }
539 else if (nRes > 0 && !bAscending)
540 {
541 sal_Int32 nTmp = rCollator.compareString( aLastInRangeString,
542 aCellStr);
543 if (nTmp >= 0)
544 {
545 aLastInRangeString = aCellStr;
546 nLastInRange = i;
547 }
548 else if (nTmp < 0)
549 {
550 // not strictly sorted, continue with GetThis()
551 orderBroken = true;
552 bDone = true;
553 }
554 }
555 }
556 else if (!bStr && bByString)
557 {
558 nRes = -1; // numeric < string
559 if (bAscending)
560 nLastInRange = i;
561 }
562 else // if (bStr && !bByString)
563 {
564 nRes = 1; // string > numeric
565 if (!bAscending)
566 nLastInRange = i;
567 }
568 if (nRes < 0)
569 {
570 if (bAscending)
571 nLo = nMid + 1;
572 else // assumed to be SC_GREATER_EQUAL
573 {
574 if (nMid > 0)
575 nHi = nMid - 1;
576 else
577 bDone = true;
578 }
579 }
580 else if (nRes > 0)
581 {
582 if (bAscending)
583 {
584 if (nMid > 0)
585 nHi = nMid - 1;
586 else
587 bDone = true;
588 }
589 else // assumed to be SC_GREATER_EQUAL
590 nLo = nMid + 1;
591 }
592 else
593 {
594 if(rEntry.eOp == SC_LESS_EQUAL || rEntry.eOp == SC_GREATER_EQUAL || rEntry.eOp == SC_EQUAL)
595 {
596 found = i;
597 nLastInRange = i;
598 // But keep searching to find the last matching one.
599 nLo = nMid + 1;
600 }
601 else if (bAscending)
602 {
603 if (nMid > 0)
604 nHi = nMid - 1;
605 else
606 bDone = true;
607 }
608 else
609 {
610 if (nMid > 0)
611 nHi = nMid - 1;
612 else
613 bDone = true;
614 }
615 }
616 }
617
618 bool isInRange;
619 if (orderBroken)
620 {
621 // Reset position to the first row in range and force caller
622 // to search from start.
623 nLo = aIndexer.getLowIndex();
624 isInRange = false;
625 }
626 else if (found)
627 {
628 nLo = *found;
629 isInRange = true;
630 }
631 else
632 {
633 // Not nothing was found and the search position is at the start,
634 // then the possible match would need to be before the data range.
635 // In that case return false to force the caller to search from the start
636 // and detect this.
637 isInRange = nLo != aIndexer.getLowIndex();
638 // If nothing was found, that is either because there is no value
639 // that would match exactly, or the data range is not properly sorted
640 // and we failed to detect (doing so reliably would require a linear scan).
641 // Set the position to the last one that was in matching range (i.e. before
642 // where the exact match would be), and leave sorting it out to GetThis()
643 // or whatever the caller uses.
644 nLo = nLastInRange;
645 }
646
647 aCellData = aIndexer.getCell(nLo);
648 if (nLo <= nHi && aCellData.second <= maParam.nRow2)
649 {
650 nRow = aCellData.second;
651 maCurPos = aIndexer.getPosition(nLo);
652 return isInRange;
653 }
654 else
655 {
656 nRow = maParam.nRow2 + 1;
657 // Set current position to the last possible row.
658 maCurPos.first = pCol->maCells.end();
659 --maCurPos.first;
660 maCurPos.second = maCurPos.first->size - 1;
661 return false;
662 }
663}
664
665
666template< ScQueryCellIteratorAccess accessType >
668 SCROW& nFoundRow )
669{
670 // Set and automatically reset mpParam->mbRangeLookup when returning.
671 comphelper::FlagRestorationGuard aRangeLookupResetter( maParam.mbRangeLookup, true );
672
673 nFoundCol = rDoc.MaxCol()+1;
674 nFoundRow = rDoc.MaxRow()+1;
675 SetStopOnMismatch( true ); // assume sorted keys
676 SetTestEqualCondition( true );
677 bIgnoreMismatchOnLeadingStrings = true;
678 bool bLiteral = maParam.eSearchType == utl::SearchParam::SearchType::Normal &&
679 maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString;
680 bool bBinary = maParam.bByRow &&
681 (bLiteral || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue) &&
682 (maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL);
683 bool bFound = false;
684 if (bBinary)
685 {
686 if (BinarySearch( maParam.nCol1 ))
687 {
688 // BinarySearch() already positions correctly and only needs real
689 // query comparisons afterwards, skip the verification check below.
690 maParam.mbRangeLookup = false;
691 bFound = GetThis();
692 }
693 else // Not sorted properly, or before the range (in which case GetFirst() will be simple).
694 bFound = GetFirst();
695 }
696 else
697 {
698 bFound = GetFirst();
699 }
700 if (bFound)
701 {
702 // First equal entry or last smaller than (greater than) entry.
703 PositionType aPosSave;
704 bool bNext = false;
705 do
706 {
707 nFoundCol = GetCol();
708 nFoundRow = GetRow();
709 aPosSave = maCurPos;
710 if (IsEqualConditionFulfilled())
711 break;
712 bNext = GetNext();
713 }
714 while (bNext);
715
716 // There may be no pNext but equal condition fulfilled if regular
717 // expressions are involved. Keep the found entry and proceed.
718 if (!bNext && !IsEqualConditionFulfilled())
719 {
720 // Step back to last in range and adjust position markers for
721 // GetNumberFormat() or similar.
722 SCCOL nColDiff = nCol - nFoundCol;
723 nCol = nFoundCol;
724 nRow = nFoundRow;
725 maCurPos = aPosSave;
726 if (maParam.mbRangeLookup)
727 {
728 // Verify that the found entry does not only fulfill the range
729 // lookup but also the real query, i.e. not numeric was found
730 // if query is ByString and vice versa.
731 maParam.mbRangeLookup = false;
732 // Step back the last field advance if GetNext() did one.
733 if (bAdvanceQuery && nColDiff)
734 {
735 SCSIZE nEntries = maParam.GetEntryCount();
736 for (SCSIZE j=0; j < nEntries; ++j)
737 {
738 ScQueryEntry& rEntry = maParam.GetEntry( j );
739 if (rEntry.bDoQuery)
740 {
741 if (rEntry.nField - nColDiff >= 0)
742 rEntry.nField -= nColDiff;
743 else
744 {
745 assert(!"FindEqualOrSortedLastInRange: rEntry.nField -= nColDiff < 0");
746 }
747 }
748 else
749 break; // for
750 }
751 }
752 // Check it.
753 if (!GetThis())
754 {
755 nFoundCol = rDoc.MaxCol()+1;
756 nFoundRow = rDoc.MaxRow()+1;
757 }
758 }
759 }
760 }
761 if ( IsEqualConditionFulfilled() )
762 {
763 // Position on last equal entry.
764 SCSIZE nEntries = maParam.GetEntryCount();
765 for ( SCSIZE j = 0; j < nEntries; j++ )
766 {
767 ScQueryEntry& rEntry = maParam.GetEntry( j );
768 if ( rEntry.bDoQuery )
769 {
770 switch ( rEntry.eOp )
771 {
772 case SC_LESS_EQUAL :
773 case SC_GREATER_EQUAL :
774 rEntry.eOp = SC_EQUAL;
775 break;
776 default:
777 {
778 // added to avoid warnings
779 }
780 }
781 }
782 else
783 break; // for
784 }
785 PositionType aPosSave;
786 bIgnoreMismatchOnLeadingStrings = false;
787 SetTestEqualCondition( false );
788 do
789 {
790 nFoundCol = GetCol();
791 nFoundRow = GetRow();
792 aPosSave = maCurPos;
793 } while (GetNext());
794
795 // Step back conditions are the same as above
796 nCol = nFoundCol;
797 nRow = nFoundRow;
798 maCurPos = aPosSave;
799 return true;
800 }
801 if ( (maParam.eSearchType != utl::SearchParam::SearchType::Normal) &&
802 StoppedOnMismatch() )
803 {
804 // Assume found entry to be the last value less than respectively
805 // greater than the query. But keep on searching for an equal match.
806 SCSIZE nEntries = maParam.GetEntryCount();
807 for ( SCSIZE j = 0; j < nEntries; j++ )
808 {
809 ScQueryEntry& rEntry = maParam.GetEntry( j );
810 if ( rEntry.bDoQuery )
811 {
812 switch ( rEntry.eOp )
813 {
814 case SC_LESS_EQUAL :
815 case SC_GREATER_EQUAL :
816 rEntry.eOp = SC_EQUAL;
817 break;
818 default:
819 {
820 // added to avoid warnings
821 }
822 }
823 }
824 else
825 break; // for
826 }
827 SetStopOnMismatch( false );
828 SetTestEqualCondition( false );
829 if (GetNext())
830 {
831 // Last of a consecutive area, avoid searching the entire parameter
832 // range as it is a real performance bottleneck in case of regular
833 // expressions.
834 PositionType aPosSave;
835 do
836 {
837 nFoundCol = GetCol();
838 nFoundRow = GetRow();
839 aPosSave = maCurPos;
840 SetStopOnMismatch( true );
841 } while (GetNext());
842 nCol = nFoundCol;
843 nRow = nFoundRow;
844 maCurPos = aPosSave;
845 }
846 }
847 return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow());
848}
849
850// Direct linear cell access using mdds.
851
854 ScInterpreterContext& rContext, const ScQueryParam& rParam )
855 : maParam( rParam )
856 , rDoc( rDocument )
857 , mrContext( rContext )
858{
859 // coverity[uninit_member] - this just contains data, subclass will initialize some of it
860}
861
863{
864 nRow = maParam.nRow1;
865 if (maParam.bHasHeader && maParam.bByRow)
866 ++nRow;
867 const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
868 maCurPos = rCol.maCells.position(nRow);
869}
870
872{
873 if (maCurPos.second + 1 < maCurPos.first->size)
874 {
875 // Move within the same block.
876 ++maCurPos.second;
877 ++nRow;
878 }
879 else
880 // Move to the next block.
881 IncBlock();
882}
883
885{
886 ++maCurPos.first;
887 maCurPos.second = 0;
888
889 nRow = maCurPos.first->position;
890}
891
902{
903 typedef std::map<size_t, sc::CellStoreType::const_iterator> BlockMapType;
904
906
908
911
913
914public:
920 NonEmptyCellIndexer(
921 const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow) :
922 mrCells(rCells), mnLowIndex(0), mnHighIndex(0), mbValid(true)
923 {
924 // Find the low position.
925
926 sc::CellStoreType::const_position_type aLoPos = mrCells.position(nStartRow);
927 assert(aLoPos.first->type != sc::element_type_empty);
928 assert(aLoPos.first != rCells.end());
929
930 SCROW nFirstRow = aLoPos.first->position;
931 SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1;
932
933 if (nFirstRow > nEndRow)
934 {
935 // Both start and end row positions are within the leading skipped
936 // blocks.
937 mbValid = false;
938 return;
939 }
940
941 // Calculate the index of the low position.
942 if (nFirstRow < nStartRow)
943 mnLowIndex = nStartRow - nFirstRow;
944 else
945 {
946 // Start row is within the skipped block(s). Set it to the first
947 // element of the low block.
948 mnLowIndex = 0;
949 }
950
951 if (nEndRow < nLastRow)
952 {
953 assert(nEndRow >= nFirstRow);
954 mnHighIndex = nEndRow - nFirstRow;
955
956 maBlockMap.emplace(aLoPos.first->size, aLoPos.first);
957 return;
958 }
959
960 // Find the high position.
961
962 sc::CellStoreType::const_position_type aHiPos = mrCells.position(aLoPos.first, nEndRow);
963 if (aHiPos.first->type == sc::element_type_empty)
964 {
965 // Move to the last position of the previous block.
966 decBlock(aHiPos);
967
968 // Check the row position of the end of the previous block, and make sure it's valid.
969 SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size - 1;
970 if (nBlockEndRow < nStartRow)
971 {
972 mbValid = false;
973 return;
974 }
975 }
976
977 // Tag the start and end blocks, and all blocks in between in order
978 // but skip all empty blocks.
979
980 size_t nPos = 0;
981 sc::CellStoreType::const_iterator itBlk = aLoPos.first;
982 while (itBlk != aHiPos.first)
983 {
984 if (itBlk->type == sc::element_type_empty)
985 {
986 ++itBlk;
987 continue;
988 }
989
990 nPos += itBlk->size;
991 maBlockMap.emplace(nPos, itBlk);
992 ++itBlk;
993
994 if (itBlk->type == sc::element_type_empty)
995 ++itBlk;
996
997 assert(itBlk != mrCells.end());
998 }
999
1000 assert(itBlk == aHiPos.first);
1001 nPos += itBlk->size;
1002 maBlockMap.emplace(nPos, itBlk);
1003
1004 // Calculate the high index.
1005 BlockMapType::const_reverse_iterator ri = maBlockMap.rbegin();
1006 mnHighIndex = ri->first;
1007 mnHighIndex -= ri->second->size;
1008 mnHighIndex += aHiPos.second;
1009 }
1010
1011 sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
1012 {
1013 assert(mbValid);
1014 assert(mnLowIndex <= nIndex);
1015 assert(nIndex <= mnHighIndex);
1016
1017 sc::CellStoreType::const_position_type aRet(mrCells.end(), 0);
1018
1019 BlockMapType::const_iterator it = maBlockMap.upper_bound(nIndex);
1020 if (it == maBlockMap.end())
1021 return aRet;
1022
1023 sc::CellStoreType::const_iterator itBlk = it->second;
1024 size_t nBlkIndex = it->first - itBlk->size; // index of the first element of the block.
1025 assert(nBlkIndex <= nIndex);
1026 assert(nIndex < it->first);
1027
1028 size_t nOffset = nIndex - nBlkIndex;
1029 aRet.first = itBlk;
1030 aRet.second = nOffset;
1031 return aRet;
1032 }
1033
1034 BinarySearchCellType getCell( size_t nIndex ) const
1035 {
1036 BinarySearchCellType aRet;
1037 aRet.second = -1;
1038
1039 sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
1040 if (aPos.first == mrCells.end())
1041 return aRet;
1042
1043 aRet.first = sc::toRefCell(aPos.first, aPos.second);
1044 aRet.second = aPos.first->position + aPos.second;
1045 return aRet;
1046 }
1047
1048 size_t getLowIndex() const { return mnLowIndex; }
1049
1050 size_t getHighIndex() const { return mnHighIndex; }
1051
1052 bool isValid() const { return mbValid; }
1053};
1054
1057 const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow )
1058{
1059 return NonEmptyCellIndexer(rCells, nStartRow, nEndRow);
1060}
1061
1062// Sorted access using ScSortedRangeCache.
1063
1066 ScInterpreterContext& rContext, const ScQueryParam& rParam )
1067 : maParam( rParam )
1068 , rDoc( rDocument )
1069 , mrContext( rContext )
1070{
1071 // coverity[uninit_member] - this just contains data, subclass will initialize some of it
1072}
1073
1075 const ScSortedRangeCache& cache)
1076{
1077 sortedCache = &cache;
1078}
1079
1080// The idea in iterating using the sorted cache is that the iteration is instead done
1081// over indexes of the sorted cache (which is a stable sort of the cell contents) in the range
1082// that fits the query condition and then that is mapped to rows. This will result in iterating
1083// over only matching rows in their sorted order (and for equal rows in their row order).
1085{
1086 ScRange aSortedRangeRange( nCol, maParam.nRow1, nTab, nCol, maParam.nRow2, nTab );
1087 // We want all matching values first in the sort order,
1088 SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange, maParam, &mrContext ));
1089 // InitPosFinish() needs to be called after this, ScQueryCellIteratorBase::InitPos()
1090 // will handle that
1091}
1092
1094 SCROW beforeRow, SCROW lastRow )
1095{
1096 pColumn = &rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
1097 if(lastRow >= 0)
1098 {
1099 sortedCachePos = beforeRow >= 0 ? sortedCache->indexForRow(beforeRow) + 1 : 0;
1100 sortedCachePosLast = sortedCache->indexForRow(lastRow);
1101 if(sortedCachePos <= sortedCachePosLast)
1102 {
1103 nRow = sortedCache->rowForIndex(sortedCachePos);
1104 maCurPos = pColumn->maCells.position(nRow);
1105 return;
1106 }
1107 }
1108 // No rows, set to end.
1109 sortedCachePos = sortedCachePosLast = 0;
1110 maCurPos.first = pColumn->maCells.end();
1111 maCurPos.second = 0;
1112}
1113
1114template<bool fast>
1116{
1117 if(sortedCachePos < sortedCachePosLast)
1118 {
1119 ++sortedCachePos;
1120 nRow = sortedCache->rowForIndex(sortedCachePos);
1121#ifndef DBG_UTIL
1122 if constexpr (!fast)
1123#endif
1124 {
1125 // Avoid mdds position() call if row is in the same block.
1126 if(maCurPos.first != pColumn->maCells.end() && o3tl::make_unsigned(nRow) >= maCurPos.first->position
1127 && o3tl::make_unsigned(nRow) < maCurPos.first->position + maCurPos.first->size)
1128 maCurPos.second = nRow - maCurPos.first->position;
1129 else
1130 maCurPos = pColumn->maCells.position(nRow);
1131 }
1132 return true;
1133 }
1134 else
1135 {
1136 // This will make PerformQuery() go to next column.
1137 // Necessary even in fast mode, as GetNext() will call GetThis() in this case.
1138 maCurPos.first = pColumn->maCells.end();
1139 maCurPos.second = 0;
1140 return false;
1141 }
1142}
1143
1144// Helper that allows binary search of unsorted cells using ScSortedRangeCache.
1145// Rows in the given range are kept in a sorted vector and that vector is binary-searched.
1147{
1148 std::vector<SCROW> mSortedRowsCopy;
1149 const std::vector<SCROW>& mSortedRows;
1154
1155 const std::vector<SCROW>& makeSortedRows( const ScSortedRangeCache* cache, SCROW startRow, SCROW endRow )
1156 {
1157 // Keep a reference to rows from the cache if equal, otherwise make a copy.
1158 if(startRow == cache->getRange().aStart.Row() && endRow == cache->getRange().aEnd.Row())
1159 return cache->sortedRows();
1160 else
1161 {
1162 mSortedRowsCopy.reserve( cache->sortedRows().size());
1163 for( SCROW row : cache->sortedRows())
1164 if( row >= startRow && row <= endRow )
1165 mSortedRowsCopy.emplace_back( row );
1166 return mSortedRowsCopy;
1167 }
1168 }
1169
1170public:
1171 SortedCacheIndexer( const sc::CellStoreType& cells, SCROW startRow, SCROW endRow,
1172 const ScSortedRangeCache* cache )
1173 : mSortedRows( makeSortedRows( cache, startRow, endRow ))
1174 , mCells( cells )
1175 , mValid( false )
1176 {
1177 if(mSortedRows.empty())
1178 {
1179 // coverity[uninit_member] - these are initialized only if valid
1180 return;
1181 }
1182 mLowIndex = 0;
1183 mHighIndex = mSortedRows.size() - 1;
1184 mValid = true;
1185 }
1186
1187 sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const
1188 {
1189 // TODO optimize?
1190 SCROW row = mSortedRows[ nIndex ];
1191 return mCells.position(row);
1192 }
1193
1194 BinarySearchCellType getCell( size_t nIndex ) const
1195 {
1196 BinarySearchCellType aRet;
1197 aRet.second = -1;
1198
1199 sc::CellStoreType::const_position_type aPos = getPosition(nIndex);
1200 if (aPos.first == mCells.end())
1201 return aRet;
1202
1203 aRet.first = sc::toRefCell(aPos.first, aPos.second);
1204 aRet.second = aPos.first->position + aPos.second;
1205 return aRet;
1206 }
1207
1208 size_t getLowIndex() const { return mLowIndex; }
1209
1210 size_t getHighIndex() const { return mHighIndex; }
1211
1212 bool isValid() const { return mValid; }
1213};
1214
1217 const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow)
1218{
1219 return SortedCacheIndexer(rCells, nStartRow, nEndRow, sortedCache);
1220}
1221
1222static bool CanBeUsedForSorterCache(ScDocument& rDoc, const ScQueryParam& rParam,
1223 SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
1224 ScInterpreterContext& context)
1225{
1226 if(!rParam.GetEntry(0).bDoQuery || rParam.GetEntry(1).bDoQuery
1227 || rParam.GetEntry(0).GetQueryItems().size() != 1 )
1228 return false;
1230 return false;
1233 return false;
1234 if(!rParam.bByRow)
1235 return false;
1236 if(rParam.bHasHeader)
1237 return false;
1238 if(rParam.mbRangeLookup)
1239 return false;
1241 && !ScQueryEvaluator::isMatchWholeCell(rDoc, rParam.GetEntry(0).eOp))
1242 return false; // substring matching cannot be sorted
1243 if(rParam.GetEntry(0).eOp != SC_LESS && rParam.GetEntry(0).eOp != SC_LESS_EQUAL
1244 && rParam.GetEntry(0).eOp != SC_GREATER && rParam.GetEntry(0).eOp != SC_GREATER_EQUAL
1245 && rParam.GetEntry(0).eOp != SC_EQUAL)
1246 return false;
1247 // For unittests allow inefficient caching, in order for the code to be checked.
1248 static bool inUnitTest = getenv("LO_TESTNAME") != nullptr;
1249 if(refData == nullptr || refData->Ref1.IsRowRel() || refData->Ref2.IsRowRel())
1250 {
1251 // If this is not a range, then a cache is not worth it. If rows are relative, then each
1252 // computation will use a different area, so the cache wouldn't be reused. Tab/cols are
1253 // not a problem, because formula group computations are done for the same tab/col.
1254 if(!inUnitTest)
1255 return false;
1256 }
1257 if(rParam.nRow2 - rParam.nRow1 < 10)
1258 {
1259 if(!inUnitTest)
1260 return false;
1261 }
1262 if( !cell || !cell->GetCellGroup() || cell->GetCellGroup()->mnLength < 10 )
1263 {
1264 if(!inUnitTest)
1265 return false;
1266 }
1267 // Check that all the relevant caches would be valid (may not be the case when mixing
1268 // numeric and string cells for ByValue lookups).
1269 for(SCCOL col : rDoc.GetAllocatedColumnsRange(nTab, rParam.nCol1, rParam.nCol2))
1270 {
1271 ScRange aSortedRangeRange( col, rParam.nRow1, nTab, col, rParam.nRow2, nTab);
1272 ScSortedRangeCache& cache = rDoc.GetSortedRangeCache( aSortedRangeRange, rParam, &context );
1273 if(!cache.isValid())
1274 return false;
1275 }
1276 return true;
1277}
1278
1279// Generic query implementation.
1280
1282{
1283 getThisResult = true;
1284 return true; // Return from PerformQuery().
1285}
1286
1287template< ScQueryCellIteratorAccess accessType >
1289{
1290 getThisResult = false;
1291 PerformQuery();
1292 return getThisResult;
1293}
1294
1295template< ScQueryCellIteratorAccess accessType >
1297{
1298 assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT");
1299 nCol = maParam.nCol1;
1300 InitPos();
1301 return GetThis();
1302}
1303
1304template< ScQueryCellIteratorAccess accessType >
1306{
1307 IncPos();
1308 if ( nStopOnMismatch )
1309 nStopOnMismatch = nStopOnMismatchEnabled;
1310 if ( nTestEqualCondition )
1311 nTestEqualCondition = nTestEqualConditionEnabled;
1312 return GetThis();
1313}
1314
1315template<>
1317{
1318 assert( !nStopOnMismatch );
1319 assert( !nTestEqualCondition );
1320 // When searching using sorted cache, we should always find cells that match,
1321 // because InitPos()/IncPos() select only such rows, so skip GetThis() (and thus
1322 // the somewhat expensive PerformQuery) as long as we're not at the end
1323 // of a column. As an optimization IncPosFast() returns true if not at the end,
1324 // in which case in non-DBG_UTIL mode it doesn't even bother to set maCurPos.
1325 if( IncPosFast())
1326 {
1327#ifdef DBG_UTIL
1328 assert(GetThis());
1329#endif
1330 return true;
1331 }
1332 return GetThis();
1333}
1334
1336 SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
1337 ScInterpreterContext& context)
1338{
1339 return CanBeUsedForSorterCache(rDoc, rParam, nTab, cell, refData, context);
1340}
1341
1342// Countifs implementation.
1343
1345{
1346 ++countIfCount;
1347 return false; // Continue searching.
1348}
1349
1350template< ScQueryCellIteratorAccess accessType >
1352{
1353 // Keep Entry.nField in iterator on column change
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;
1359 InitPos();
1360 countIfCount = 0;
1361 PerformQuery();
1362 return countIfCount;
1363}
1364
1365
1367 SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
1368 ScInterpreterContext& context)
1369{
1370 return CanBeUsedForSorterCache(rDoc, rParam, nTab, cell, refData, context);
1371}
1372
1373template<>
1375{
1376 // Keep Entry.nField in iterator on column change
1378 assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds, FIX IT");
1379 sal_uInt64 count = 0;
1380 // Each column must be sorted separately.
1381 for(SCCOL col : rDoc.GetAllocatedColumnsRange(nTab, maParam.nCol1, maParam.nCol2))
1382 {
1383 nCol = col;
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 ));
1388 if( op == SC_EQUAL )
1389 {
1390 // BinarySearch() searches for the last item that matches. Therefore first
1391 // find the last non-matching position using SC_LESS and then find the last
1392 // matching position using SC_EQUAL.
1393 ScQueryOp saveOp = op;
1394 op = SC_LESS;
1395 if( BinarySearch( nCol, true ))
1396 {
1397 op = saveOp; // back to SC_EQUAL
1398 size_t lastNonMatching = sortedCache->indexForRow(nRow);
1399 if( BinarySearch( nCol ))
1400 {
1401 size_t lastMatching = sortedCache->indexForRow(nRow);
1402 assert(lastMatching >= lastNonMatching);
1403 count += lastMatching - lastNonMatching;
1404 }
1405 else
1406 {
1407 // BinarySearch() should at least find the same result as the SC_LESS
1408 // call, so this should not happen.
1409 assert(false);
1410 }
1411 }
1412 else
1413 {
1414 // BinarySearch() returning false means that all values are larger,
1415 // so try to find matching ones and count those up to and including
1416 // the found one.
1417 op = saveOp; // back to SC_EQUAL
1418 if( BinarySearch( nCol ))
1419 {
1420 size_t lastMatching = sortedCache->indexForRow(nRow) + 1;
1421 count += lastMatching;
1422 }
1423 else if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
1424 && rDoc.IsEmptyData(col, maParam.nRow1, col, maParam.nRow2, nTab))
1425 {
1426 // BinarySearch() returns false in case it's all empty data,
1427 // handle that specially.
1428 count += maParam.nRow2 - maParam.nRow1 + 1;
1429 }
1430 }
1431 }
1432 else
1433 {
1434 // BinarySearch() searches for the last item that matches. Therefore everything
1435 // up to and including the found row matches the condition.
1436 if( BinarySearch( nCol ))
1437 count += sortedCache->indexForRow(nRow) + 1;
1438 }
1439 }
1440 if( maParam.GetEntry(0).GetQueryItem().mbMatchEmpty
1441 && maParam.nCol2 >= rDoc.GetAllocatedColumnsCount( nTab ))
1442 {
1443 count += (maParam.nCol2 - rDoc.GetAllocatedColumnsCount( nTab ))
1444 * ( maParam.nRow2 - maParam.nRow1 + 1 );
1445 }
1446 return count;
1447}
1448
1453
1454// gcc for some reason needs these too
1459
1460/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
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 ...
Definition: address.hxx:44
const NodeContext & mrContext
sal_Int32 compareString(const OUString &s1, const OUString &s2) const
SCROW Row() const
Definition: address.hxx:274
static OUString GetInputString(const ScRefCellValue &rCell, sal_uInt32 nFormat, SvNumberFormatter &rFormatter, const ScDocument &rDoc, const svl::SharedString **pShared=nullptr, bool bFiltering=false, bool bForceSystemLocale=false)
Definition: cellform.cxx:129
bool IsEmptyData() const
Definition: column2.cxx:1251
sc::CellStoreType maCells
Definition: column.hxx:196
sal_uInt32 GetNumberFormat(const ScInterpreterContext &rContext, SCROW nRow) const
Definition: column.hxx:969
static bool CanBeUsed(ScDocument &rDoc, const ScQueryParam &aParam, SCTAB nTab, const ScFormulaCell *cell, const ScComplexRefData *refData, ScInterpreterContext &context)
Definition: queryiter.cxx:1366
sal_uInt64 GetCount()
Definition: queryiter.cxx:1351
SC_DLLPUBLIC ScColumnsRange GetAllocatedColumnsRange(SCTAB nTab, SCCOL nColBegin, SCCOL nColEnd) const
Definition: document.cxx:2569
ScSortedRangeCache & GetSortedRangeCache(const ScRange &rRange, const ScQueryParam &param, ScInterpreterContext *pContext)
Definition: documen2.cxx:1199
const ScFormulaCellGroupRef & GetCellGroup() const
double GetValue()
static SC_DLLPUBLIC CollatorWrapper & GetCollator()
case-insensitive collator
Definition: global.cxx:1055
bool BinarySearch(SCCOL col, bool forEqual=false)
Definition: queryiter.cxx:329
ScQueryCellIteratorBase(ScDocument &rDocument, ScInterpreterContext &rContext, SCTAB nTable, const ScQueryParam &aParam, bool bMod)
Definition: queryiter.cxx:63
void AdvanceQueryParamEntryField()
Definition: queryiter.cxx:288
static bool CanBeUsed(ScDocument &rDoc, const ScQueryParam &aParam, SCTAB nTab, const ScFormulaCell *cell, const ScComplexRefData *refData, ScInterpreterContext &context)
Definition: queryiter.cxx:1335
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...
Definition: queryiter.cxx:667
bool isMatchWholeCell(ScQueryOp eOp) const
bool ValidQuery(SCROW nRow, const ScRefCellValue *pCell=nullptr, sc::TableColumnBlockPositionSet *pBlockPos=nullptr)
ScAddress aEnd
Definition: address.hxx:498
ScAddress aStart
Definition: address.hxx:497
Sorted cache for one range used with interpreter functions such as VLOOKUP and MATCH.
Definition: rangecache.hxx:45
bool isValid() const
Returns if the cache is usable.
Definition: rangecache.hxx:52
const std::vector< SCROW > & sortedRows() const
Definition: rangecache.hxx:93
const ScRange & getRange() const
Definition: rangecache.hxx:57
OUString getString() const
int nCount
@ CELLTYPE_FORMULA
Definition: global.hxx:274
@ CELLTYPE_VALUE
Definition: global.hxx:272
ScQueryOp
Definition: global.hxx:818
@ SC_LESS_EQUAL
Definition: global.hxx:822
@ SC_LESS
Definition: global.hxx:820
@ SC_GREATER_EQUAL
Definition: global.hxx:823
@ SC_GREATER
Definition: global.hxx:821
@ SC_EQUAL
Definition: global.hxx:819
sal_Int32 nIndex
sal_uInt16 nPos
aStr
int i
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
Definition: mtvelements.hxx:49
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
Definition: mtvelements.hxx:48
const mdds::mtv::element_t element_type_empty
Definition: mtvelements.hxx:57
size_t mLowIndex
Definition: queryiter.cxx:1151
size_t mnLowIndex
Definition: queryiter.cxx:909
BlockMapType maBlockMap
Definition: queryiter.cxx:905
std::vector< SCROW > mSortedRowsCopy
Definition: queryiter.cxx:1148
const std::vector< SCROW > & mSortedRows
Definition: queryiter.cxx:1149
std::map< size_t, sc::CellStoreType::const_iterator > BlockMapType
Definition: queryiter.cxx:903
bool mValid
Definition: queryiter.cxx:1153
size_t mnHighIndex
Definition: queryiter.cxx:910
const sc::CellStoreType & mCells
Definition: queryiter.cxx:1150
const sc::CellStoreType & mrCells
Definition: queryiter.cxx:907
static bool CanBeUsedForSorterCache(ScDocument &rDoc, const ScQueryParam &rParam, SCTAB nTab, const ScFormulaCell *cell, const ScComplexRefData *refData, ScInterpreterContext &context)
Definition: queryiter.cxx:1222
size_t mHighIndex
Definition: queryiter.cxx:1152
bool mbValid
Definition: queryiter.cxx:912
Complex reference (a range) into the sheet.
Definition: refdata.hxx:123
ScSingleRefData Ref2
Definition: refdata.hxx:125
ScSingleRefData Ref1
Definition: refdata.hxx:124
svl::SharedString maString
Definition: queryentry.hxx:49
Each instance of this struct represents a single filtering criteria.
Definition: queryentry.hxx:34
SCCOLROW nField
Definition: queryentry.hxx:61
const Item & GetQueryItem() const
Definition: queryentry.hxx:85
ScQueryOp eOp
Definition: queryentry.hxx:62
QueryItemsType & GetQueryItems()
Definition: queryentry.hxx:75
SC_DLLPUBLIC const ScQueryEntry & GetEntry(SCSIZE n) const
Definition: queryparam.cxx:116
utl::SearchParam::SearchType eSearchType
Definition: queryparam.hxx:43
bool mbRangeLookup
for spreadsheet functions like MATCH, LOOKUP, HLOOKUP, VLOOKUP
Definition: queryparam.hxx:49
This is very similar to ScCellValue, except that it references the original value instead of copying ...
Definition: cellvalue.hxx:108
ScFormulaCell * getFormula() const
Definition: cellvalue.hxx:137
double getDouble() const
Definition: cellvalue.hxx:134
double getValue()
Definition: cellvalue.cxx:629
bool hasString() const
Definition: cellvalue.cxx:614
CellType getType() const
Definition: cellvalue.hxx:133
bool IsRowRel() const
Definition: refdata.hxx:67
sal_Int32 SCCOLROW
a type capable of holding either SCCOL or SCROW
Definition: types.hxx:23
sal_Int16 SCTAB
Definition: types.hxx:22
sal_Int16 SCCOL
Definition: types.hxx:21
ScQueryCellIteratorAccess
Definition: types.hxx:145
sal_Int32 SCROW
Definition: types.hxx:17