sc/Library_sc.mk | 1 sc/inc/dociter.hxx | 143 ---- sc/inc/queryiter.hxx | 171 +++++ sc/source/core/data/dociter.cxx | 1036 ------------------------------------ sc/source/core/data/queryiter.cxx | 1090 ++++++++++++++++++++++++++++++++++++++ sc/source/core/tool/interpr1.cxx | 1 solenv/clang-format/excludelist | 2 7 files changed, 1265 insertions(+), 1179 deletions(-)
New commits: commit 4af9403cf718207620376b63242f6d0dd047406a Author: Luboš Luňák <[email protected]> AuthorDate: Fri Apr 22 12:08:57 2022 +0200 Commit: Luboš Luňák <[email protected]> CommitDate: Fri Apr 22 18:16:05 2022 +0200 move query-related iterators to a new separate file dociter.cxx/hxx are already quite big as it is, and the query iterators are more about queries than about iterating the document. Change-Id: I49e3a5636e4f366efb8b4968f54567d2716ade35 Reviewed-on: https://gerrit.libreoffice.org/c/core/+/133323 Tested-by: Luboš Luňák <[email protected]> Reviewed-by: Luboš Luňák <[email protected]> diff --git a/sc/Library_sc.mk b/sc/Library_sc.mk index 0ba02c9449ac..c6f65d4ec495 100644 --- a/sc/Library_sc.mk +++ b/sc/Library_sc.mk @@ -179,6 +179,7 @@ $(eval $(call gb_Library_add_exception_objects,sc,\ sc/source/core/data/poolhelp \ sc/source/core/data/postit \ sc/source/core/data/queryevaluator \ + sc/source/core/data/queryiter \ sc/source/core/data/refupdatecontext \ sc/source/core/data/rowheightcontext \ sc/source/core/data/segmenttree \ diff --git a/sc/inc/dociter.hxx b/sc/inc/dociter.hxx index 99ceb1e99972..90fbd614b8bd 100644 --- a/sc/inc/dociter.hxx +++ b/sc/inc/dociter.hxx @@ -248,149 +248,6 @@ public: bool next(); }; -class ScQueryCellIterator // walk through all non-empty cells in an area -{ - enum StopOnMismatchBits - { - nStopOnMismatchDisabled = 0x00, - nStopOnMismatchEnabled = 0x01, - nStopOnMismatchOccurred = 0x02, - nStopOnMismatchExecuted = nStopOnMismatchEnabled | nStopOnMismatchOccurred - }; - - enum TestEqualConditionBits - { - nTestEqualConditionDisabled = 0x00, - nTestEqualConditionEnabled = 0x01, - nTestEqualConditionMatched = 0x02, - nTestEqualConditionFulfilled = nTestEqualConditionEnabled | nTestEqualConditionMatched - }; - - typedef sc::CellStoreType::const_position_type PositionType; - PositionType maCurPos; - - ScQueryParam maParam; - ScDocument& rDoc; - const ScInterpreterContext& mrContext; - SCTAB nTab; - SCCOL nCol; - SCROW nRow; - sal_uInt8 nStopOnMismatch; - sal_uInt8 nTestEqualCondition; - bool bAdvanceQuery; - bool bIgnoreMismatchOnLeadingStrings; - - /** Initialize position for new column. */ - void InitPos(); - void IncPos(); - void IncBlock(); - bool GetThis(); - - /* Only works if no regular expression is involved, only - searches for rows in one column, and only the first - query entry is considered with simple conditions - SC_LESS_EQUAL (sorted ascending) or SC_GREATER_EQUAL - (sorted descending). Check these things before - invocation! Delivers a starting point, continue with - GetThis() and GetNext() afterwards. Introduced for - FindEqualOrSortedLastInRange() - */ - bool BinarySearch(); - -public: - ScQueryCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, - const ScQueryParam& aParam, bool bMod); - // when !bMod, the QueryParam has to be filled - // (bIsString) - bool GetFirst(); - bool GetNext(); - SCCOL GetCol() const { return nCol; } - SCROW GetRow() const { return nRow; } - - // increments all Entry.nField, if column - // changes, for ScInterpreter ScHLookup() - void SetAdvanceQueryParamEntryField( bool bVal ) - { bAdvanceQuery = bVal; } - void AdvanceQueryParamEntryField(); - - /** If set, iterator stops on first non-matching cell - content. May be used in SC_LESS_EQUAL queries where a - cell range is assumed to be sorted; stops on first - value being greater than the queried value and - GetFirst()/GetNext() return NULL. StoppedOnMismatch() - returns true then. - However, the iterator's conditions are not set to end - all queries, GetCol() and GetRow() return values for - the non-matching cell, further GetNext() calls may be - executed. */ - void SetStopOnMismatch( bool bVal ) - { - nStopOnMismatch = sal::static_int_cast<sal_uInt8>(bVal ? nStopOnMismatchEnabled : - nStopOnMismatchDisabled); - } - bool StoppedOnMismatch() const - { return nStopOnMismatch == nStopOnMismatchExecuted; } - - /** If set, an additional test for SC_EQUAL condition is - executed in ScTable::ValidQuery() if SC_LESS_EQUAL or - SC_GREATER_EQUAL conditions are to be tested. May be - used where a cell range is assumed to be sorted to stop - if an equal match is found. */ - void SetTestEqualCondition( bool bVal ) - { - nTestEqualCondition = sal::static_int_cast<sal_uInt8>(bVal ? - nTestEqualConditionEnabled : - nTestEqualConditionDisabled); - } - bool IsEqualConditionFulfilled() const - { return nTestEqualCondition == nTestEqualConditionFulfilled; } - - /** In a range assumed to be sorted find either the last of - a sequence of equal entries or the last being less than - (or greater than) the queried value. Used by the - interpreter for [HV]?LOOKUP() and MATCH(). Column and - row position of the found entry are returned, otherwise - invalid. - - The search does not stop when encountering a string and does not - assume that no values follow anymore. - If querying for a string a mismatch on the first - entry, e.g. column header, is ignored. - - @ATTENTION! StopOnMismatch, TestEqualCondition and - the internal IgnoreMismatchOnLeadingStrings and query - params are in an undefined state upon return! The - iterator is not usable anymore except for obtaining the - number format! - */ - bool FindEqualOrSortedLastInRange( SCCOL& nFoundCol, SCROW& nFoundRow ); -}; - -// Used by ScInterpreter::ScCountIf. -// Walk through all non-empty cells in an area. -class ScCountIfCellIterator -{ - typedef sc::CellStoreType::const_position_type PositionType; - PositionType maCurPos; - ScQueryParam maParam; - ScDocument& rDoc; - const ScInterpreterContext& mrContext; - SCTAB nTab; - SCCOL nCol; - SCROW nRow; - - /** Initialize position for new column. */ - void InitPos(); - void IncPos(); - void IncBlock(); - void AdvanceQueryParamEntryField(); - -public: - ScCountIfCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, - const ScQueryParam& aParam); - int GetCount(); -}; - class ScDocAttrIterator // all attribute areas { private: diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx new file mode 100644 index 000000000000..70b8daaf4153 --- /dev/null +++ b/sc/inc/queryiter.hxx @@ -0,0 +1,171 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +#pragma once + +#include "address.hxx" +#include "global.hxx" +#include "scdllapi.h" +#include "queryparam.hxx" +#include "mtvelements.hxx" + +class ScQueryCellIterator // walk through all non-empty cells in an area +{ + enum StopOnMismatchBits + { + nStopOnMismatchDisabled = 0x00, + nStopOnMismatchEnabled = 0x01, + nStopOnMismatchOccurred = 0x02, + nStopOnMismatchExecuted = nStopOnMismatchEnabled | nStopOnMismatchOccurred + }; + + enum TestEqualConditionBits + { + nTestEqualConditionDisabled = 0x00, + nTestEqualConditionEnabled = 0x01, + nTestEqualConditionMatched = 0x02, + nTestEqualConditionFulfilled = nTestEqualConditionEnabled | nTestEqualConditionMatched + }; + + typedef sc::CellStoreType::const_position_type PositionType; + PositionType maCurPos; + + ScQueryParam maParam; + ScDocument& rDoc; + const ScInterpreterContext& mrContext; + SCTAB nTab; + SCCOL nCol; + SCROW nRow; + sal_uInt8 nStopOnMismatch; + sal_uInt8 nTestEqualCondition; + bool bAdvanceQuery; + bool bIgnoreMismatchOnLeadingStrings; + + /** Initialize position for new column. */ + void InitPos(); + void IncPos(); + void IncBlock(); + bool GetThis(); + + /* Only works if no regular expression is involved, only + searches for rows in one column, and only the first + query entry is considered with simple conditions + SC_LESS_EQUAL (sorted ascending) or SC_GREATER_EQUAL + (sorted descending). Check these things before + invocation! Delivers a starting point, continue with + GetThis() and GetNext() afterwards. Introduced for + FindEqualOrSortedLastInRange() + */ + bool BinarySearch(); + +public: + ScQueryCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, + const ScQueryParam& aParam, bool bMod); + // when !bMod, the QueryParam has to be filled + // (bIsString) + bool GetFirst(); + bool GetNext(); + SCCOL GetCol() const { return nCol; } + SCROW GetRow() const { return nRow; } + + // increments all Entry.nField, if column + // changes, for ScInterpreter ScHLookup() + void SetAdvanceQueryParamEntryField( bool bVal ) + { bAdvanceQuery = bVal; } + void AdvanceQueryParamEntryField(); + + /** If set, iterator stops on first non-matching cell + content. May be used in SC_LESS_EQUAL queries where a + cell range is assumed to be sorted; stops on first + value being greater than the queried value and + GetFirst()/GetNext() return NULL. StoppedOnMismatch() + returns true then. + However, the iterator's conditions are not set to end + all queries, GetCol() and GetRow() return values for + the non-matching cell, further GetNext() calls may be + executed. */ + void SetStopOnMismatch( bool bVal ) + { + nStopOnMismatch = sal::static_int_cast<sal_uInt8>(bVal ? nStopOnMismatchEnabled : + nStopOnMismatchDisabled); + } + bool StoppedOnMismatch() const + { return nStopOnMismatch == nStopOnMismatchExecuted; } + + /** If set, an additional test for SC_EQUAL condition is + executed in ScTable::ValidQuery() if SC_LESS_EQUAL or + SC_GREATER_EQUAL conditions are to be tested. May be + used where a cell range is assumed to be sorted to stop + if an equal match is found. */ + void SetTestEqualCondition( bool bVal ) + { + nTestEqualCondition = sal::static_int_cast<sal_uInt8>(bVal ? + nTestEqualConditionEnabled : + nTestEqualConditionDisabled); + } + bool IsEqualConditionFulfilled() const + { return nTestEqualCondition == nTestEqualConditionFulfilled; } + + /** In a range assumed to be sorted find either the last of + a sequence of equal entries or the last being less than + (or greater than) the queried value. Used by the + interpreter for [HV]?LOOKUP() and MATCH(). Column and + row position of the found entry are returned, otherwise + invalid. + + The search does not stop when encountering a string and does not + assume that no values follow anymore. + If querying for a string a mismatch on the first + entry, e.g. column header, is ignored. + + @ATTENTION! StopOnMismatch, TestEqualCondition and + the internal IgnoreMismatchOnLeadingStrings and query + params are in an undefined state upon return! The + iterator is not usable anymore except for obtaining the + number format! + */ + bool FindEqualOrSortedLastInRange( SCCOL& nFoundCol, SCROW& nFoundRow ); +}; + +// Used by ScInterpreter::ScCountIf. +// Walk through all non-empty cells in an area. +class ScCountIfCellIterator +{ + typedef sc::CellStoreType::const_position_type PositionType; + PositionType maCurPos; + ScQueryParam maParam; + ScDocument& rDoc; + const ScInterpreterContext& mrContext; + SCTAB nTab; + SCCOL nCol; + SCROW nRow; + + /** Initialize position for new column. */ + void InitPos(); + void IncPos(); + void IncBlock(); + void AdvanceQueryParamEntryField(); + +public: + ScCountIfCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, + const ScQueryParam& aParam); + int GetCount(); +}; + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sc/source/core/data/dociter.cxx b/sc/source/core/data/dociter.cxx index 052439698adb..d0849d17eb29 100644 --- a/sc/source/core/data/dociter.cxx +++ b/sc/source/core/data/dociter.cxx @@ -61,26 +61,6 @@ using ::std::set; // #define debugiter(...) fprintf(stderr, __VA_ARGS__) #define debugiter(...) -namespace { - -template<typename Iter> -void incBlock(std::pair<Iter, size_t>& rPos) -{ - // Move to the next block. - ++rPos.first; - rPos.second = 0; -} - -template<typename Iter> -void decBlock(std::pair<Iter, size_t>& rPos) -{ - // Move to the last element of the previous block. - --rPos.first; - rPos.second = rPos.first->size - 1; -} - -} - static void ScAttrArray_IterGetNumberFormat( sal_uInt32& nFormat, const ScAttrArray*& rpArr, SCROW& nAttrEndRow, const ScAttrArray* pNewArr, SCROW nRow, const ScDocument& rDoc, const ScInterpreterContext* pContext = nullptr ) @@ -1050,1022 +1030,6 @@ bool ScCellIterator::next() return getCurrent(); } -ScQueryCellIterator::ScQueryCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, - const ScQueryParam& rParam, bool bMod ) : - maParam(rParam), - rDoc( rDocument ), - mrContext( rContext ), - nTab( nTable), - nStopOnMismatch( nStopOnMismatchDisabled ), - nTestEqualCondition( nTestEqualConditionDisabled ), - bAdvanceQuery( false ), - bIgnoreMismatchOnLeadingStrings( false ) -{ - nCol = maParam.nCol1; - nRow = maParam.nRow1; - SCSIZE i; - if (!bMod) // Or else it's already inserted - return; - - SCSIZE nCount = maParam.GetEntryCount(); - for (i = 0; (i < nCount) && (maParam.GetEntry(i).bDoQuery); ++i) - { - ScQueryEntry& rEntry = maParam.GetEntry(i); - ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); - sal_uInt32 nIndex = 0; - bool bNumber = mrContext.GetFormatTable()->IsNumberFormat( - rItem.maString.getString(), nIndex, rItem.mfVal); - rItem.meType = bNumber ? ScQueryEntry::ByValue : ScQueryEntry::ByString; - } -} - -void ScQueryCellIterator::InitPos() -{ - nRow = maParam.nRow1; - if (maParam.bHasHeader && maParam.bByRow) - ++nRow; - const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol); - maCurPos = rCol.maCells.position(nRow); -} - -void ScQueryCellIterator::IncPos() -{ - if (maCurPos.second + 1 < maCurPos.first->size) - { - // Move within the same block. - ++maCurPos.second; - ++nRow; - } - else - // Move to the next block. - IncBlock(); -} - -void ScQueryCellIterator::IncBlock() -{ - ++maCurPos.first; - maCurPos.second = 0; - - nRow = maCurPos.first->position; -} - -bool ScQueryCellIterator::GetThis() -{ - assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT"); - const ScQueryEntry& rEntry = maParam.GetEntry(0); - const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); - - SCCOLROW nFirstQueryField = rEntry.nField; - bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && - rItem.meType != ScQueryEntry::ByString; - bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && - !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString && - ((maParam.bByRow && nRow == maParam.nRow1) || - (!maParam.bByRow && nCol == maParam.nCol1)); - bool bTestEqualCondition = false; - ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam, &mrContext, - (nTestEqualCondition ? &bTestEqualCondition : nullptr)); - - ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; - while (true) - { - bool bNextColumn = maCurPos.first == pCol->maCells.end(); - if (!bNextColumn) - { - if (nRow > maParam.nRow2) - bNextColumn = true; - } - - if (bNextColumn) - { - do - { - ++nCol; - if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount()) - return false; - if ( bAdvanceQuery ) - { - AdvanceQueryParamEntryField(); - nFirstQueryField = rEntry.nField; - } - pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; - } - while (!rItem.mbMatchEmpty && pCol->IsEmptyData()); - - InitPos(); - - bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && - !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString && - maParam.bByRow; - } - - if (maCurPos.first->type == sc::element_type_empty) - { - if (rItem.mbMatchEmpty && rEntry.GetQueryItems().size() == 1) - { - // This shortcut, instead of determining if any SC_OR query - // exists or this query is SC_AND'ed (which wouldn't make - // sense, but..) and evaluating them in ValidQuery(), is - // possible only because the interpreter is the only caller - // that sets mbMatchEmpty and there is only one item in those - // cases. - // XXX this would have to be reworked if other filters used it - // in different manners and evaluation would have to be done in - // ValidQuery(). - return true; - } - else - { - IncBlock(); - continue; - } - } - - ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second); - - if (bAllStringIgnore && aCell.hasString()) - IncPos(); - else - { - if ( queryEvaluator.ValidQuery( nRow, - (nCol == static_cast<SCCOL>(nFirstQueryField) ? &aCell : nullptr))) - { - if ( nTestEqualCondition && bTestEqualCondition ) - nTestEqualCondition |= nTestEqualConditionMatched; - return !aCell.isEmpty(); // Found it! - } - else if ( nStopOnMismatch ) - { - // Yes, even a mismatch may have a fulfilled equal - // condition if regular expressions were involved and - // SC_LESS_EQUAL or SC_GREATER_EQUAL were queried. - if ( nTestEqualCondition && bTestEqualCondition ) - { - nTestEqualCondition |= nTestEqualConditionMatched; - nStopOnMismatch |= nStopOnMismatchOccurred; - return false; - } - bool bStop; - if (bFirstStringIgnore) - { - if (aCell.hasString()) - { - IncPos(); - bStop = false; - } - else - bStop = true; - } - else - bStop = true; - if (bStop) - { - nStopOnMismatch |= nStopOnMismatchOccurred; - return false; - } - } - else - IncPos(); - } - bFirstStringIgnore = false; - } -} - -bool ScQueryCellIterator::GetFirst() -{ - assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT"); - nCol = maParam.nCol1; - InitPos(); - return GetThis(); -} - -bool ScQueryCellIterator::GetNext() -{ - IncPos(); - if ( nStopOnMismatch ) - nStopOnMismatch = nStopOnMismatchEnabled; - if ( nTestEqualCondition ) - nTestEqualCondition = nTestEqualConditionEnabled; - return GetThis(); -} - -void ScQueryCellIterator::AdvanceQueryParamEntryField() -{ - SCSIZE nEntries = maParam.GetEntryCount(); - for ( SCSIZE j = 0; j < nEntries; j++ ) - { - ScQueryEntry& rEntry = maParam.GetEntry( j ); - if ( rEntry.bDoQuery ) - { - if ( rEntry.nField < rDoc.MaxCol() ) - rEntry.nField++; - else - { - assert(!"AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL"); - } - } - else - break; // for - } -} - -bool ScQueryCellIterator::FindEqualOrSortedLastInRange( SCCOL& nFoundCol, - SCROW& nFoundRow ) -{ - // Set and automatically reset mpParam->mbRangeLookup when returning. We - // could use comphelper::FlagRestorationGuard, but really, that one is - // overengineered for this simple purpose here. - struct BoolResetter - { - bool& mr; - bool mb; - BoolResetter( bool& r, bool b ) : mr(r), mb(r) { r = b; } - ~BoolResetter() { mr = mb; } - } aRangeLookupResetter( maParam.mbRangeLookup, true); - - nFoundCol = rDoc.MaxCol()+1; - nFoundRow = rDoc.MaxRow()+1; - SetStopOnMismatch( true ); // assume sorted keys - SetTestEqualCondition( true ); - bIgnoreMismatchOnLeadingStrings = true; - bool bLiteral = maParam.eSearchType == utl::SearchParam::SearchType::Normal && - maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString; - bool bBinary = maParam.bByRow && - (bLiteral || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue) && - (maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL); - bool bFound = false; - if (bBinary) - { - if (BinarySearch()) - { - // BinarySearch() already positions correctly and only needs real - // query comparisons afterwards, skip the verification check below. - maParam.mbRangeLookup = false; - bFound = GetThis(); - } - } - else - { - bFound = GetFirst(); - } - if (bFound) - { - // First equal entry or last smaller than (greater than) entry. - PositionType aPosSave; - bool bNext = false; - do - { - nFoundCol = GetCol(); - nFoundRow = GetRow(); - aPosSave = maCurPos; - if (IsEqualConditionFulfilled()) - break; - bNext = GetNext(); - } - while (bNext); - - // There may be no pNext but equal condition fulfilled if regular - // expressions are involved. Keep the found entry and proceed. - if (!bNext && !IsEqualConditionFulfilled()) - { - // Step back to last in range and adjust position markers for - // GetNumberFormat() or similar. - SCCOL nColDiff = nCol - nFoundCol; - nCol = nFoundCol; - nRow = nFoundRow; - maCurPos = aPosSave; - if (maParam.mbRangeLookup) - { - // Verify that the found entry does not only fulfill the range - // lookup but also the real query, i.e. not numeric was found - // if query is ByString and vice versa. - maParam.mbRangeLookup = false; - // Step back the last field advance if GetNext() did one. - if (bAdvanceQuery && nColDiff) - { - SCSIZE nEntries = maParam.GetEntryCount(); - for (SCSIZE j=0; j < nEntries; ++j) - { - ScQueryEntry& rEntry = maParam.GetEntry( j ); - if (rEntry.bDoQuery) - { - if (rEntry.nField - nColDiff >= 0) - rEntry.nField -= nColDiff; - else - { - assert(!"FindEqualOrSortedLastInRange: rEntry.nField -= nColDiff < 0"); - } - } - else - break; // for - } - } - // Check it. - if (!GetThis()) - { - nFoundCol = rDoc.MaxCol()+1; - nFoundRow = rDoc.MaxRow()+1; - } - } - } - } - if ( IsEqualConditionFulfilled() ) - { - // Position on last equal entry. - SCSIZE nEntries = maParam.GetEntryCount(); - for ( SCSIZE j = 0; j < nEntries; j++ ) - { - ScQueryEntry& rEntry = maParam.GetEntry( j ); - if ( rEntry.bDoQuery ) - { - switch ( rEntry.eOp ) - { - case SC_LESS_EQUAL : - case SC_GREATER_EQUAL : - rEntry.eOp = SC_EQUAL; - break; - default: - { - // added to avoid warnings - } - } - } - else - break; // for - } - PositionType aPosSave; - bIgnoreMismatchOnLeadingStrings = false; - SetTestEqualCondition( false ); - do - { - nFoundCol = GetCol(); - nFoundRow = GetRow(); - aPosSave = maCurPos; - } while (GetNext()); - - // Step back conditions are the same as above - nCol = nFoundCol; - nRow = nFoundRow; - maCurPos = aPosSave; - return true; - } - if ( (maParam.eSearchType != utl::SearchParam::SearchType::Normal) && - StoppedOnMismatch() ) - { - // Assume found entry to be the last value less than respectively - // greater than the query. But keep on searching for an equal match. - SCSIZE nEntries = maParam.GetEntryCount(); - for ( SCSIZE j = 0; j < nEntries; j++ ) - { - ScQueryEntry& rEntry = maParam.GetEntry( j ); - if ( rEntry.bDoQuery ) - { - switch ( rEntry.eOp ) - { - case SC_LESS_EQUAL : - case SC_GREATER_EQUAL : - rEntry.eOp = SC_EQUAL; - break; - default: - { - // added to avoid warnings - } - } - } - else - break; // for - } - SetStopOnMismatch( false ); - SetTestEqualCondition( false ); - if (GetNext()) - { - // Last of a consecutive area, avoid searching the entire parameter - // range as it is a real performance bottleneck in case of regular - // expressions. - PositionType aPosSave; - do - { - nFoundCol = GetCol(); - nFoundRow = GetRow(); - aPosSave = maCurPos; - SetStopOnMismatch( true ); - } while (GetNext()); - nCol = nFoundCol; - nRow = nFoundRow; - maCurPos = aPosSave; - } - } - return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow()); -} - -ScCountIfCellIterator::ScCountIfCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, - const ScQueryParam& rParam ) : - maParam(rParam), - rDoc( rDocument ), - mrContext( rContext ), - nTab( nTable) -{ - maParam.nCol1 = rDoc.maTabs[nTable]->ClampToAllocatedColumns(maParam.nCol1); - maParam.nCol2 = rDoc.maTabs[nTable]->ClampToAllocatedColumns(maParam.nCol2); - nCol = maParam.nCol1; - nRow = maParam.nRow1; -} - -void ScCountIfCellIterator::InitPos() -{ - nRow = maParam.nRow1; - if (maParam.bHasHeader && maParam.bByRow) - ++nRow; - ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; - maCurPos = pCol->maCells.position(nRow); -} - -void ScCountIfCellIterator::IncPos() -{ - if (maCurPos.second + 1 < maCurPos.first->size) - { - // Move within the same block. - ++maCurPos.second; - ++nRow; - } - else - // Move to the next block. - IncBlock(); -} - -void ScCountIfCellIterator::IncBlock() -{ - ++maCurPos.first; - maCurPos.second = 0; - - nRow = maCurPos.first->position; -} - -int ScCountIfCellIterator::GetCount() -{ - assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds, FIX IT"); - nCol = maParam.nCol1; - InitPos(); - - const ScQueryEntry& rEntry = maParam.GetEntry(0); - const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); - const bool bSingleQueryItem = rEntry.GetQueryItems().size() == 1; - int count = 0; - ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam, &mrContext); - - ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; - while (true) - { - bool bNextColumn = maCurPos.first == pCol->maCells.end(); - if (!bNextColumn) - { - if (nRow > maParam.nRow2) - bNextColumn = true; - } - - if (bNextColumn) - { - do - { - ++nCol; - if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount()) - return count; - AdvanceQueryParamEntryField(); - pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; - } - while (!rItem.mbMatchEmpty && pCol->IsEmptyData()); - - InitPos(); - } - - if (maCurPos.first->type == sc::element_type_empty) - { - if (rItem.mbMatchEmpty && bSingleQueryItem) - { - // This shortcut, instead of determining if any SC_OR query - // exists or this query is SC_AND'ed (which wouldn't make - // sense, but..) and evaluating them in ValidQuery(), is - // possible only because the interpreter is the only caller - // that sets mbMatchEmpty and there is only one item in those - // cases. - // XXX this would have to be reworked if other filters used it - // in different manners and evaluation would have to be done in - // ValidQuery(). - count++; - IncPos(); - continue; - } - else - { - IncBlock(); - continue; - } - } - - ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second); - - if ( queryEvaluator.ValidQuery( nRow, - (nCol == static_cast<SCCOL>(rEntry.nField) ? &aCell : nullptr))) - { - if (aCell.isEmpty()) - return count; - count++; - IncPos(); - continue; - } - else - IncPos(); - } - return count; -} - -void ScCountIfCellIterator::AdvanceQueryParamEntryField() -{ - SCSIZE nEntries = maParam.GetEntryCount(); - for ( SCSIZE j = 0; j < nEntries; j++ ) - { - ScQueryEntry& rEntry = maParam.GetEntry( j ); - if ( rEntry.bDoQuery ) - { - if ( rEntry.nField < rDoc.MaxCol() ) - rEntry.nField++; - else - { - OSL_FAIL( "AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL" ); - } - } - else - break; // for - } -} - -namespace { - -/** - * This class sequentially indexes non-empty cells in order, from the top of - * the block where the start row position is, to the bottom of the block - * where the end row position is. It skips all empty blocks that may be - * present in between. - * - * The index value is an offset from the first element of the first block - * disregarding all empty cell blocks. - */ -class NonEmptyCellIndexer -{ - typedef std::map<size_t, sc::CellStoreType::const_iterator> BlockMapType; - - BlockMapType maBlockMap; - - const sc::CellStoreType& mrCells; - - size_t mnLowIndex; - size_t mnHighIndex; - - bool mbValid; - -public: - - typedef std::pair<ScRefCellValue, SCROW> CellType; - - /** - * @param rCells cell storage container - * @param nStartRow logical start row position - * @param nEndRow logical end row position, inclusive. - * @param bSkipTopStrBlock when true, skip all leading string cells. - */ - NonEmptyCellIndexer( - const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow, bool bSkipTopStrBlock ) : - mrCells(rCells), mnLowIndex(0), mnHighIndex(0), mbValid(true) - { - if (nEndRow < nStartRow) - { - mbValid = false; - return; - } - - // Find the low position. - - sc::CellStoreType::const_position_type aLoPos = mrCells.position(nStartRow); - if (aLoPos.first->type == sc::element_type_empty) - incBlock(aLoPos); - - if (aLoPos.first == rCells.end()) - { - mbValid = false; - return; - } - - if (bSkipTopStrBlock) - { - // Skip all leading string or empty blocks. - while (aLoPos.first->type == sc::element_type_string || - aLoPos.first->type == sc::element_type_edittext || - aLoPos.first->type == sc::element_type_empty) - { - incBlock(aLoPos); - if (aLoPos.first == rCells.end()) - { - mbValid = false; - return; - } - } - } - - SCROW nFirstRow = aLoPos.first->position; - SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1; - - if (nFirstRow > nEndRow) - { - // Both start and end row positions are within the leading skipped - // blocks. - mbValid = false; - return; - } - - // Calculate the index of the low position. - if (nFirstRow < nStartRow) - mnLowIndex = nStartRow - nFirstRow; - else - { - // Start row is within the skipped block(s). Set it to the first - // element of the low block. - mnLowIndex = 0; - } - - if (nEndRow < nLastRow) - { - assert(nEndRow >= nFirstRow); - mnHighIndex = nEndRow - nFirstRow; - - maBlockMap.emplace(aLoPos.first->size, aLoPos.first); - return; - } - - // Find the high position. - - sc::CellStoreType::const_position_type aHiPos = mrCells.position(aLoPos.first, nEndRow); - if (aHiPos.first->type == sc::element_type_empty) - { - // Move to the last position of the previous block. - decBlock(aHiPos); - - // Check the row position of the end of the previous block, and make sure it's valid. - SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size - 1; - if (nBlockEndRow < nStartRow) - { - mbValid = false; - return; - } - } - - // Tag the start and end blocks, and all blocks in between in order - // but skip all empty blocks. - - size_t nPos = 0; - sc::CellStoreType::const_iterator itBlk = aLoPos.first; - while (itBlk != aHiPos.first) - { - if (itBlk->type == sc::element_type_empty) - { - ++itBlk; - continue; - } - - nPos += itBlk->size; - maBlockMap.emplace(nPos, itBlk); - ++itBlk; - - if (itBlk->type == sc::element_type_empty) - ++itBlk; - - assert(itBlk != mrCells.end()); - } - - assert(itBlk == aHiPos.first); - nPos += itBlk->size; - maBlockMap.emplace(nPos, itBlk); - - // Calculate the high index. - BlockMapType::const_reverse_iterator ri = maBlockMap.rbegin(); - mnHighIndex = ri->first; - mnHighIndex -= ri->second->size; - mnHighIndex += aHiPos.second; - } - - sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const - { - assert(mbValid); - assert(mnLowIndex <= nIndex); - assert(nIndex <= mnHighIndex); - - sc::CellStoreType::const_position_type aRet(mrCells.end(), 0); - - BlockMapType::const_iterator it = maBlockMap.upper_bound(nIndex); - if (it == maBlockMap.end()) - return aRet; - - sc::CellStoreType::const_iterator itBlk = it->second; - size_t nBlkIndex = it->first - itBlk->size; // index of the first element of the block. - assert(nBlkIndex <= nIndex); - assert(nIndex < it->first); - - size_t nOffset = nIndex - nBlkIndex; - aRet.first = itBlk; - aRet.second = nOffset; - return aRet; - } - - CellType getCell( size_t nIndex ) const - { - std::pair<ScRefCellValue, SCROW> aRet; - aRet.second = -1; - - sc::CellStoreType::const_position_type aPos = getPosition(nIndex); - if (aPos.first == mrCells.end()) - return aRet; - - aRet.first = sc::toRefCell(aPos.first, aPos.second); - aRet.second = aPos.first->position + aPos.second; - return aRet; - } - - size_t getLowIndex() const { return mnLowIndex; } - - size_t getHighIndex() const { return mnHighIndex; } - - bool isValid() const { return mbValid; } -}; - -} - -bool ScQueryCellIterator::BinarySearch() -{ - // TODO: This will be extremely slow with mdds::multi_type_vector. - - assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT"); - nCol = maParam.nCol1; - - if (nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount()) - return false; - - ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; - if (pCol->IsEmptyData()) - return false; - - CollatorWrapper& rCollator = ScGlobal::GetCollator(maParam.bCaseSens); - SvNumberFormatter& rFormatter = *(mrContext.GetFormatTable()); - const ScQueryEntry& rEntry = maParam.GetEntry(0); - const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); - bool bLessEqual = rEntry.eOp == SC_LESS_EQUAL; - bool bByString = rItem.meType == ScQueryEntry::ByString; - bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString; - bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && - !maParam.bHasHeader && bByString; - - nRow = maParam.nRow1; - if (maParam.bHasHeader) - ++nRow; - - ScRefCellValue aCell; - if (bFirstStringIgnore) - { - sc::CellStoreType::const_position_type aPos = pCol->maCells.position(nRow); - if (aPos.first->type == sc::element_type_string || aPos.first->type == sc::element_type_edittext) - { - aCell = sc::toRefCell(aPos.first, aPos.second); - sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, nRow); - OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); - sal_Int32 nTmp = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString()); - if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) || - (rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) || - (rEntry.eOp == SC_EQUAL && nTmp != 0)) - ++nRow; - } - } - - NonEmptyCellIndexer aIndexer(pCol->maCells, nRow, maParam.nRow2, bAllStringIgnore); - if (!aIndexer.isValid()) - return false; - - size_t nLo = aIndexer.getLowIndex(); - size_t nHi = aIndexer.getHighIndex(); - NonEmptyCellIndexer::CellType aCellData; - - // Bookkeeping values for breaking up the binary search in case the data - // range isn't strictly sorted. - size_t nLastInRange = nLo; - size_t nFirstLastInRange = nLastInRange; - double fLastInRangeValue = bLessEqual ? - -(::std::numeric_limits<double>::max()) : - ::std::numeric_limits<double>::max(); - OUString aLastInRangeString; - if (!bLessEqual) - aLastInRangeString = OUString(u'\xFFFF'); - - aCellData = aIndexer.getCell(nLastInRange); - aCell = aCellData.first; - if (aCell.hasString()) - { - sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, aCellData.second); - OUString aStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); - aLastInRangeString = aStr; - } - else - { - switch (aCell.meType) - { - case CELLTYPE_VALUE : - fLastInRangeValue = aCell.mfValue; - break; - case CELLTYPE_FORMULA : - fLastInRangeValue = aCell.mpFormula->GetValue(); - break; - default: - { - // added to avoid warnings - } - } - } - - sal_Int32 nRes = 0; - bool bFound = false; - bool bDone = false; - while (nLo <= nHi && !bDone) - { - size_t nMid = (nLo+nHi)/2; - size_t i = nMid; - - aCellData = aIndexer.getCell(i); - aCell = aCellData.first; - bool bStr = aCell.hasString(); - nRes = 0; - - // compares are content<query:-1, content>query:1 - // Cell value comparison similar to ScTable::ValidQuery() - if (!bStr && !bByString) - { - double nCellVal; - switch (aCell.meType) - { - case CELLTYPE_VALUE : - case CELLTYPE_FORMULA : - nCellVal = aCell.getValue(); - break; - default: - nCellVal = 0.0; - } - if ((nCellVal < rItem.mfVal) && !::rtl::math::approxEqual( - nCellVal, rItem.mfVal)) - { - nRes = -1; - if (bLessEqual) - { - if (fLastInRangeValue < nCellVal) - { - fLastInRangeValue = nCellVal; - nLastInRange = i; - } - else if (fLastInRangeValue > nCellVal) - { - // not strictly sorted, continue with GetThis() - nLastInRange = nFirstLastInRange; - bDone = true; - } - } - } - else if ((nCellVal > rItem.mfVal) && !::rtl::math::approxEqual( - nCellVal, rItem.mfVal)) - { - nRes = 1; - if (!bLessEqual) - { - if (fLastInRangeValue > nCellVal) - { - fLastInRangeValue = nCellVal; - nLastInRange = i; - } - else if (fLastInRangeValue < nCellVal) - { - // not strictly sorted, continue with GetThis() - nLastInRange = nFirstLastInRange; - bDone = true; - } - } - } - } - else if (bStr && bByString) - { - sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, aCellData.second); - OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); - - nRes = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString()); - if (nRes < 0 && bLessEqual) - { - sal_Int32 nTmp = rCollator.compareString( aLastInRangeString, - aCellStr); - if (nTmp < 0) - { - aLastInRangeString = aCellStr; - nLastInRange = i; - } - else if (nTmp > 0) - { - // not strictly sorted, continue with GetThis() - nLastInRange = nFirstLastInRange; - bDone = true; - } - } - else if (nRes > 0 && !bLessEqual) - { - sal_Int32 nTmp = rCollator.compareString( aLastInRangeString, - aCellStr); - if (nTmp > 0) - { - aLastInRangeString = aCellStr; - nLastInRange = i; - } - else if (nTmp < 0) - { - // not strictly sorted, continue with GetThis() - nLastInRange = nFirstLastInRange; - bDone = true; - } - } - } - else if (!bStr && bByString) - { - nRes = -1; // numeric < string - if (bLessEqual) - nLastInRange = i; - } - else // if (bStr && !bByString) - { - nRes = 1; // string > numeric - if (!bLessEqual) - nLastInRange = i; - } - if (nRes < 0) - { - if (bLessEqual) - nLo = nMid + 1; - else // assumed to be SC_GREATER_EQUAL - { - if (nMid > 0) - nHi = nMid - 1; - else - bDone = true; - } - } - else if (nRes > 0) - { - if (bLessEqual) - { - if (nMid > 0) - nHi = nMid - 1; - else - bDone = true; - } - else // assumed to be SC_GREATER_EQUAL - nLo = nMid + 1; - } - else - { - nLo = i; - bDone = bFound = true; - } - } - - if (!bFound) - { - // If all hits didn't result in a moving limit there's something - // strange, e.g. data range not properly sorted, or only identical - // values encountered, which doesn't mean there aren't any others in - // between... leave it to GetThis(). The condition for this would be - // if (nLastInRange == nFirstLastInRange) nLo = nFirstLastInRange; - // Else, in case no exact match was found, we step back for a - // subsequent GetThis() to find the last in range. Effectively this is - // --nLo with nLastInRange == nLo-1. Both conditions combined yield: - nLo = nLastInRange; - } - - aCellData = aIndexer.getCell(nLo); - if (nLo <= nHi && aCellData.second <= maParam.nRow2) - { - nRow = aCellData.second; - maCurPos = aIndexer.getPosition(nLo); - return true; - } - else - { - nRow = maParam.nRow2 + 1; - // Set current position to the last possible row. - maCurPos.first = pCol->maCells.end(); - --maCurPos.first; - maCurPos.second = maCurPos.first->size - 1; - return false; - } -} - ScHorizontalCellIterator::ScHorizontalCellIterator(ScDocument& rDocument, SCTAB nTable, SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 ) : rDoc( rDocument ), diff --git a/sc/source/core/data/queryiter.cxx b/sc/source/core/data/queryiter.cxx new file mode 100644 index 000000000000..27217b0a1eb2 --- /dev/null +++ b/sc/source/core/data/queryiter.cxx @@ -0,0 +1,1090 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +#include <queryiter.hxx> + +#include <svl/numformat.hxx> +#include <svl/zforlist.hxx> + +#include <global.hxx> +#include <dociter.hxx> +#include <document.hxx> +#include <table.hxx> +#include <column.hxx> +#include <formulacell.hxx> +#include <attarray.hxx> +#include <patattr.hxx> +#include <docoptio.hxx> +#include <cellform.hxx> +#include <segmenttree.hxx> +#include <progress.hxx> +#include <queryparam.hxx> +#include <queryentry.hxx> +#include <globstr.hrc> +#include <scresid.hxx> +#include <cellvalue.hxx> +#include <scmatrix.hxx> +#include <rowheightcontext.hxx> +#include <queryevaluator.hxx> + +#include <o3tl/safeint.hxx> +#include <tools/fract.hxx> +#include <editeng/editobj.hxx> +#include <svl/sharedstring.hxx> +#include <unotools/collatorwrapper.hxx> +#include <osl/diagnose.h> +#include <sal/log.hxx> + +#include <algorithm> +#include <limits> +#include <vector> + +ScQueryCellIterator::ScQueryCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, + const ScQueryParam& rParam, bool bMod ) : + maParam(rParam), + rDoc( rDocument ), + mrContext( rContext ), + nTab( nTable), + nStopOnMismatch( nStopOnMismatchDisabled ), + nTestEqualCondition( nTestEqualConditionDisabled ), + bAdvanceQuery( false ), + bIgnoreMismatchOnLeadingStrings( false ) +{ + nCol = maParam.nCol1; + nRow = maParam.nRow1; + SCSIZE i; + if (!bMod) // Or else it's already inserted + return; + + SCSIZE nCount = maParam.GetEntryCount(); + for (i = 0; (i < nCount) && (maParam.GetEntry(i).bDoQuery); ++i) + { + ScQueryEntry& rEntry = maParam.GetEntry(i); + ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); + sal_uInt32 nIndex = 0; + bool bNumber = mrContext.GetFormatTable()->IsNumberFormat( + rItem.maString.getString(), nIndex, rItem.mfVal); + rItem.meType = bNumber ? ScQueryEntry::ByValue : ScQueryEntry::ByString; + } +} + +void ScQueryCellIterator::InitPos() +{ + nRow = maParam.nRow1; + if (maParam.bHasHeader && maParam.bByRow) + ++nRow; + const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol); + maCurPos = rCol.maCells.position(nRow); +} + +void ScQueryCellIterator::IncPos() +{ + if (maCurPos.second + 1 < maCurPos.first->size) + { + // Move within the same block. + ++maCurPos.second; + ++nRow; + } + else + // Move to the next block. + IncBlock(); +} + +void ScQueryCellIterator::IncBlock() +{ + ++maCurPos.first; + maCurPos.second = 0; + + nRow = maCurPos.first->position; +} + +bool ScQueryCellIterator::GetThis() +{ + assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT"); + const ScQueryEntry& rEntry = maParam.GetEntry(0); + const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); + + SCCOLROW nFirstQueryField = rEntry.nField; + bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && + rItem.meType != ScQueryEntry::ByString; + bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && + !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString && + ((maParam.bByRow && nRow == maParam.nRow1) || + (!maParam.bByRow && nCol == maParam.nCol1)); + bool bTestEqualCondition = false; + ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam, &mrContext, + (nTestEqualCondition ? &bTestEqualCondition : nullptr)); + + ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; + while (true) + { + bool bNextColumn = maCurPos.first == pCol->maCells.end(); + if (!bNextColumn) + { + if (nRow > maParam.nRow2) + bNextColumn = true; + } + + if (bNextColumn) + { + do + { + ++nCol; + if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount()) + return false; + if ( bAdvanceQuery ) + { + AdvanceQueryParamEntryField(); + nFirstQueryField = rEntry.nField; + } + pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; + } + while (!rItem.mbMatchEmpty && pCol->IsEmptyData()); + + InitPos(); + + bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && + !maParam.bHasHeader && rItem.meType == ScQueryEntry::ByString && + maParam.bByRow; + } + + if (maCurPos.first->type == sc::element_type_empty) + { + if (rItem.mbMatchEmpty && rEntry.GetQueryItems().size() == 1) + { + // This shortcut, instead of determining if any SC_OR query + // exists or this query is SC_AND'ed (which wouldn't make + // sense, but..) and evaluating them in ValidQuery(), is + // possible only because the interpreter is the only caller + // that sets mbMatchEmpty and there is only one item in those + // cases. + // XXX this would have to be reworked if other filters used it + // in different manners and evaluation would have to be done in + // ValidQuery(). + return true; + } + else + { + IncBlock(); + continue; + } + } + + ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second); + + if (bAllStringIgnore && aCell.hasString()) + IncPos(); + else + { + if ( queryEvaluator.ValidQuery( nRow, + (nCol == static_cast<SCCOL>(nFirstQueryField) ? &aCell : nullptr))) + { + if ( nTestEqualCondition && bTestEqualCondition ) + nTestEqualCondition |= nTestEqualConditionMatched; + return !aCell.isEmpty(); // Found it! + } + else if ( nStopOnMismatch ) + { + // Yes, even a mismatch may have a fulfilled equal + // condition if regular expressions were involved and + // SC_LESS_EQUAL or SC_GREATER_EQUAL were queried. + if ( nTestEqualCondition && bTestEqualCondition ) + { + nTestEqualCondition |= nTestEqualConditionMatched; + nStopOnMismatch |= nStopOnMismatchOccurred; + return false; + } + bool bStop; + if (bFirstStringIgnore) + { + if (aCell.hasString()) + { + IncPos(); + bStop = false; + } + else + bStop = true; + } + else + bStop = true; + if (bStop) + { + nStopOnMismatch |= nStopOnMismatchOccurred; + return false; + } + } + else + IncPos(); + } + bFirstStringIgnore = false; + } +} + +bool ScQueryCellIterator::GetFirst() +{ + assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT"); + nCol = maParam.nCol1; + InitPos(); + return GetThis(); +} + +bool ScQueryCellIterator::GetNext() +{ + IncPos(); + if ( nStopOnMismatch ) + nStopOnMismatch = nStopOnMismatchEnabled; + if ( nTestEqualCondition ) + nTestEqualCondition = nTestEqualConditionEnabled; + return GetThis(); +} + +void ScQueryCellIterator::AdvanceQueryParamEntryField() +{ + SCSIZE nEntries = maParam.GetEntryCount(); + for ( SCSIZE j = 0; j < nEntries; j++ ) + { + ScQueryEntry& rEntry = maParam.GetEntry( j ); + if ( rEntry.bDoQuery ) + { + if ( rEntry.nField < rDoc.MaxCol() ) + rEntry.nField++; + else + { + assert(!"AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL"); + } + } + else + break; // for + } +} + +bool ScQueryCellIterator::FindEqualOrSortedLastInRange( SCCOL& nFoundCol, + SCROW& nFoundRow ) +{ + // Set and automatically reset mpParam->mbRangeLookup when returning. We + // could use comphelper::FlagRestorationGuard, but really, that one is + // overengineered for this simple purpose here. + struct BoolResetter + { + bool& mr; + bool mb; + BoolResetter( bool& r, bool b ) : mr(r), mb(r) { r = b; } + ~BoolResetter() { mr = mb; } + } aRangeLookupResetter( maParam.mbRangeLookup, true); + + nFoundCol = rDoc.MaxCol()+1; + nFoundRow = rDoc.MaxRow()+1; + SetStopOnMismatch( true ); // assume sorted keys + SetTestEqualCondition( true ); + bIgnoreMismatchOnLeadingStrings = true; + bool bLiteral = maParam.eSearchType == utl::SearchParam::SearchType::Normal && + maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByString; + bool bBinary = maParam.bByRow && + (bLiteral || maParam.GetEntry(0).GetQueryItem().meType == ScQueryEntry::ByValue) && + (maParam.GetEntry(0).eOp == SC_LESS_EQUAL || maParam.GetEntry(0).eOp == SC_GREATER_EQUAL); + bool bFound = false; + if (bBinary) + { + if (BinarySearch()) + { + // BinarySearch() already positions correctly and only needs real + // query comparisons afterwards, skip the verification check below. + maParam.mbRangeLookup = false; + bFound = GetThis(); + } + } + else + { + bFound = GetFirst(); + } + if (bFound) + { + // First equal entry or last smaller than (greater than) entry. + PositionType aPosSave; + bool bNext = false; + do + { + nFoundCol = GetCol(); + nFoundRow = GetRow(); + aPosSave = maCurPos; + if (IsEqualConditionFulfilled()) + break; + bNext = GetNext(); + } + while (bNext); + + // There may be no pNext but equal condition fulfilled if regular + // expressions are involved. Keep the found entry and proceed. + if (!bNext && !IsEqualConditionFulfilled()) + { + // Step back to last in range and adjust position markers for + // GetNumberFormat() or similar. + SCCOL nColDiff = nCol - nFoundCol; + nCol = nFoundCol; + nRow = nFoundRow; + maCurPos = aPosSave; + if (maParam.mbRangeLookup) + { + // Verify that the found entry does not only fulfill the range + // lookup but also the real query, i.e. not numeric was found + // if query is ByString and vice versa. + maParam.mbRangeLookup = false; + // Step back the last field advance if GetNext() did one. + if (bAdvanceQuery && nColDiff) + { + SCSIZE nEntries = maParam.GetEntryCount(); + for (SCSIZE j=0; j < nEntries; ++j) + { + ScQueryEntry& rEntry = maParam.GetEntry( j ); + if (rEntry.bDoQuery) + { + if (rEntry.nField - nColDiff >= 0) + rEntry.nField -= nColDiff; + else + { + assert(!"FindEqualOrSortedLastInRange: rEntry.nField -= nColDiff < 0"); + } + } + else + break; // for + } + } + // Check it. + if (!GetThis()) + { + nFoundCol = rDoc.MaxCol()+1; + nFoundRow = rDoc.MaxRow()+1; + } + } + } + } + if ( IsEqualConditionFulfilled() ) + { + // Position on last equal entry. + SCSIZE nEntries = maParam.GetEntryCount(); + for ( SCSIZE j = 0; j < nEntries; j++ ) + { + ScQueryEntry& rEntry = maParam.GetEntry( j ); + if ( rEntry.bDoQuery ) + { + switch ( rEntry.eOp ) + { + case SC_LESS_EQUAL : + case SC_GREATER_EQUAL : + rEntry.eOp = SC_EQUAL; + break; + default: + { + // added to avoid warnings + } + } + } + else + break; // for + } + PositionType aPosSave; + bIgnoreMismatchOnLeadingStrings = false; + SetTestEqualCondition( false ); + do + { + nFoundCol = GetCol(); + nFoundRow = GetRow(); + aPosSave = maCurPos; + } while (GetNext()); + + // Step back conditions are the same as above + nCol = nFoundCol; + nRow = nFoundRow; + maCurPos = aPosSave; + return true; + } + if ( (maParam.eSearchType != utl::SearchParam::SearchType::Normal) && + StoppedOnMismatch() ) + { + // Assume found entry to be the last value less than respectively + // greater than the query. But keep on searching for an equal match. + SCSIZE nEntries = maParam.GetEntryCount(); + for ( SCSIZE j = 0; j < nEntries; j++ ) + { + ScQueryEntry& rEntry = maParam.GetEntry( j ); + if ( rEntry.bDoQuery ) + { + switch ( rEntry.eOp ) + { + case SC_LESS_EQUAL : + case SC_GREATER_EQUAL : + rEntry.eOp = SC_EQUAL; + break; + default: + { + // added to avoid warnings + } + } + } + else + break; // for + } + SetStopOnMismatch( false ); + SetTestEqualCondition( false ); + if (GetNext()) + { + // Last of a consecutive area, avoid searching the entire parameter + // range as it is a real performance bottleneck in case of regular + // expressions. + PositionType aPosSave; + do + { + nFoundCol = GetCol(); + nFoundRow = GetRow(); + aPosSave = maCurPos; + SetStopOnMismatch( true ); + } while (GetNext()); + nCol = nFoundCol; + nRow = nFoundRow; + maCurPos = aPosSave; + } + } + return (nFoundCol <= rDoc.MaxCol()) && (nFoundRow <= rDoc.MaxRow()); +} + +ScCountIfCellIterator::ScCountIfCellIterator(ScDocument& rDocument, const ScInterpreterContext& rContext, SCTAB nTable, + const ScQueryParam& rParam ) : + maParam(rParam), + rDoc( rDocument ), + mrContext( rContext ), + nTab( nTable) +{ + maParam.nCol1 = rDoc.maTabs[nTable]->ClampToAllocatedColumns(maParam.nCol1); + maParam.nCol2 = rDoc.maTabs[nTable]->ClampToAllocatedColumns(maParam.nCol2); + nCol = maParam.nCol1; + nRow = maParam.nRow1; +} + +void ScCountIfCellIterator::InitPos() +{ + nRow = maParam.nRow1; + if (maParam.bHasHeader && maParam.bByRow) + ++nRow; + ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; + maCurPos = pCol->maCells.position(nRow); +} + +void ScCountIfCellIterator::IncPos() +{ + if (maCurPos.second + 1 < maCurPos.first->size) + { + // Move within the same block. + ++maCurPos.second; + ++nRow; + } + else + // Move to the next block. + IncBlock(); +} + +void ScCountIfCellIterator::IncBlock() +{ + ++maCurPos.first; + maCurPos.second = 0; + + nRow = maCurPos.first->position; +} + +int ScCountIfCellIterator::GetCount() +{ + assert(nTab < rDoc.GetTableCount() && "try to access index out of bounds, FIX IT"); + nCol = maParam.nCol1; + InitPos(); + + const ScQueryEntry& rEntry = maParam.GetEntry(0); + const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); + const bool bSingleQueryItem = rEntry.GetQueryItems().size() == 1; + int count = 0; + ScQueryEvaluator queryEvaluator(rDoc, *rDoc.maTabs[nTab], maParam, &mrContext); + + ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; + while (true) + { + bool bNextColumn = maCurPos.first == pCol->maCells.end(); + if (!bNextColumn) + { + if (nRow > maParam.nRow2) + bNextColumn = true; + } + + if (bNextColumn) + { + do + { + ++nCol; + if (nCol > maParam.nCol2 || nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount()) + return count; + AdvanceQueryParamEntryField(); + pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; + } + while (!rItem.mbMatchEmpty && pCol->IsEmptyData()); + + InitPos(); + } + + if (maCurPos.first->type == sc::element_type_empty) + { + if (rItem.mbMatchEmpty && bSingleQueryItem) + { + // This shortcut, instead of determining if any SC_OR query + // exists or this query is SC_AND'ed (which wouldn't make + // sense, but..) and evaluating them in ValidQuery(), is + // possible only because the interpreter is the only caller + // that sets mbMatchEmpty and there is only one item in those + // cases. + // XXX this would have to be reworked if other filters used it + // in different manners and evaluation would have to be done in + // ValidQuery(). + count++; + IncPos(); + continue; + } + else + { + IncBlock(); + continue; + } + } + + ScRefCellValue aCell = sc::toRefCell(maCurPos.first, maCurPos.second); + + if ( queryEvaluator.ValidQuery( nRow, + (nCol == static_cast<SCCOL>(rEntry.nField) ? &aCell : nullptr))) + { + if (aCell.isEmpty()) + return count; + count++; + IncPos(); + continue; + } + else + IncPos(); + } + return count; +} + +void ScCountIfCellIterator::AdvanceQueryParamEntryField() +{ + SCSIZE nEntries = maParam.GetEntryCount(); + for ( SCSIZE j = 0; j < nEntries; j++ ) + { + ScQueryEntry& rEntry = maParam.GetEntry( j ); + if ( rEntry.bDoQuery ) + { + if ( rEntry.nField < rDoc.MaxCol() ) + rEntry.nField++; + else + { + OSL_FAIL( "AdvanceQueryParamEntryField: ++rEntry.nField > MAXCOL" ); + } + } + else + break; // for + } +} + +namespace { + +template<typename Iter> +void incBlock(std::pair<Iter, size_t>& rPos) +{ + // Move to the next block. + ++rPos.first; + rPos.second = 0; +} + +template<typename Iter> +void decBlock(std::pair<Iter, size_t>& rPos) +{ + // Move to the last element of the previous block. + --rPos.first; + rPos.second = rPos.first->size - 1; +} + +/** + * This class sequentially indexes non-empty cells in order, from the top of + * the block where the start row position is, to the bottom of the block + * where the end row position is. It skips all empty blocks that may be + * present in between. + * + * The index value is an offset from the first element of the first block + * disregarding all empty cell blocks. + */ +class NonEmptyCellIndexer +{ + typedef std::map<size_t, sc::CellStoreType::const_iterator> BlockMapType; + + BlockMapType maBlockMap; + + const sc::CellStoreType& mrCells; + + size_t mnLowIndex; + size_t mnHighIndex; + + bool mbValid; + +public: + + typedef std::pair<ScRefCellValue, SCROW> CellType; + + /** + * @param rCells cell storage container + * @param nStartRow logical start row position + * @param nEndRow logical end row position, inclusive. + * @param bSkipTopStrBlock when true, skip all leading string cells. + */ + NonEmptyCellIndexer( + const sc::CellStoreType& rCells, SCROW nStartRow, SCROW nEndRow, bool bSkipTopStrBlock ) : + mrCells(rCells), mnLowIndex(0), mnHighIndex(0), mbValid(true) + { + if (nEndRow < nStartRow) + { + mbValid = false; + return; + } + + // Find the low position. + + sc::CellStoreType::const_position_type aLoPos = mrCells.position(nStartRow); + if (aLoPos.first->type == sc::element_type_empty) + incBlock(aLoPos); + + if (aLoPos.first == rCells.end()) + { + mbValid = false; + return; + } + + if (bSkipTopStrBlock) + { + // Skip all leading string or empty blocks. + while (aLoPos.first->type == sc::element_type_string || + aLoPos.first->type == sc::element_type_edittext || + aLoPos.first->type == sc::element_type_empty) + { + incBlock(aLoPos); + if (aLoPos.first == rCells.end()) + { + mbValid = false; + return; + } + } + } + + SCROW nFirstRow = aLoPos.first->position; + SCROW nLastRow = aLoPos.first->position + aLoPos.first->size - 1; + + if (nFirstRow > nEndRow) + { + // Both start and end row positions are within the leading skipped + // blocks. + mbValid = false; + return; + } + + // Calculate the index of the low position. + if (nFirstRow < nStartRow) + mnLowIndex = nStartRow - nFirstRow; + else + { + // Start row is within the skipped block(s). Set it to the first + // element of the low block. + mnLowIndex = 0; + } + + if (nEndRow < nLastRow) + { + assert(nEndRow >= nFirstRow); + mnHighIndex = nEndRow - nFirstRow; + + maBlockMap.emplace(aLoPos.first->size, aLoPos.first); + return; + } + + // Find the high position. + + sc::CellStoreType::const_position_type aHiPos = mrCells.position(aLoPos.first, nEndRow); + if (aHiPos.first->type == sc::element_type_empty) + { + // Move to the last position of the previous block. + decBlock(aHiPos); + + // Check the row position of the end of the previous block, and make sure it's valid. + SCROW nBlockEndRow = aHiPos.first->position + aHiPos.first->size - 1; + if (nBlockEndRow < nStartRow) + { + mbValid = false; + return; + } + } + + // Tag the start and end blocks, and all blocks in between in order + // but skip all empty blocks. + + size_t nPos = 0; + sc::CellStoreType::const_iterator itBlk = aLoPos.first; + while (itBlk != aHiPos.first) + { + if (itBlk->type == sc::element_type_empty) + { + ++itBlk; + continue; + } + + nPos += itBlk->size; + maBlockMap.emplace(nPos, itBlk); + ++itBlk; + + if (itBlk->type == sc::element_type_empty) + ++itBlk; + + assert(itBlk != mrCells.end()); + } + + assert(itBlk == aHiPos.first); + nPos += itBlk->size; + maBlockMap.emplace(nPos, itBlk); + + // Calculate the high index. + BlockMapType::const_reverse_iterator ri = maBlockMap.rbegin(); + mnHighIndex = ri->first; + mnHighIndex -= ri->second->size; + mnHighIndex += aHiPos.second; + } + + sc::CellStoreType::const_position_type getPosition( size_t nIndex ) const + { + assert(mbValid); + assert(mnLowIndex <= nIndex); + assert(nIndex <= mnHighIndex); + + sc::CellStoreType::const_position_type aRet(mrCells.end(), 0); + + BlockMapType::const_iterator it = maBlockMap.upper_bound(nIndex); + if (it == maBlockMap.end()) + return aRet; + + sc::CellStoreType::const_iterator itBlk = it->second; + size_t nBlkIndex = it->first - itBlk->size; // index of the first element of the block. + assert(nBlkIndex <= nIndex); + assert(nIndex < it->first); + + size_t nOffset = nIndex - nBlkIndex; + aRet.first = itBlk; + aRet.second = nOffset; + return aRet; + } + + CellType getCell( size_t nIndex ) const + { + std::pair<ScRefCellValue, SCROW> aRet; + aRet.second = -1; + + sc::CellStoreType::const_position_type aPos = getPosition(nIndex); + if (aPos.first == mrCells.end()) + return aRet; + + aRet.first = sc::toRefCell(aPos.first, aPos.second); + aRet.second = aPos.first->position + aPos.second; + return aRet; + } + + size_t getLowIndex() const { return mnLowIndex; } + + size_t getHighIndex() const { return mnHighIndex; } + + bool isValid() const { return mbValid; } +}; + +} + +bool ScQueryCellIterator::BinarySearch() +{ + // TODO: This will be extremely slow with mdds::multi_type_vector. + + assert(nTab < rDoc.GetTableCount() && "index out of bounds, FIX IT"); + nCol = maParam.nCol1; + + if (nCol >= rDoc.maTabs[nTab]->GetAllocatedColumnsCount()) + return false; + + ScColumn* pCol = &(rDoc.maTabs[nTab])->aCol[nCol]; + if (pCol->IsEmptyData()) + return false; + + CollatorWrapper& rCollator = ScGlobal::GetCollator(maParam.bCaseSens); + SvNumberFormatter& rFormatter = *(mrContext.GetFormatTable()); + const ScQueryEntry& rEntry = maParam.GetEntry(0); + const ScQueryEntry::Item& rItem = rEntry.GetQueryItem(); + bool bLessEqual = rEntry.eOp == SC_LESS_EQUAL; + bool bByString = rItem.meType == ScQueryEntry::ByString; + bool bAllStringIgnore = bIgnoreMismatchOnLeadingStrings && !bByString; + bool bFirstStringIgnore = bIgnoreMismatchOnLeadingStrings && + !maParam.bHasHeader && bByString; + + nRow = maParam.nRow1; + if (maParam.bHasHeader) + ++nRow; + + ScRefCellValue aCell; + if (bFirstStringIgnore) + { + sc::CellStoreType::const_position_type aPos = pCol->maCells.position(nRow); + if (aPos.first->type == sc::element_type_string || aPos.first->type == sc::element_type_edittext) + { + aCell = sc::toRefCell(aPos.first, aPos.second); + sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, nRow); + OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); + sal_Int32 nTmp = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString()); + if ((rEntry.eOp == SC_LESS_EQUAL && nTmp > 0) || + (rEntry.eOp == SC_GREATER_EQUAL && nTmp < 0) || + (rEntry.eOp == SC_EQUAL && nTmp != 0)) + ++nRow; + } + } + + NonEmptyCellIndexer aIndexer(pCol->maCells, nRow, maParam.nRow2, bAllStringIgnore); + if (!aIndexer.isValid()) + return false; + + size_t nLo = aIndexer.getLowIndex(); + size_t nHi = aIndexer.getHighIndex(); + NonEmptyCellIndexer::CellType aCellData; + + // Bookkeeping values for breaking up the binary search in case the data + // range isn't strictly sorted. + size_t nLastInRange = nLo; + size_t nFirstLastInRange = nLastInRange; + double fLastInRangeValue = bLessEqual ? + -(::std::numeric_limits<double>::max()) : + ::std::numeric_limits<double>::max(); + OUString aLastInRangeString; + if (!bLessEqual) + aLastInRangeString = OUString(u'\xFFFF'); + + aCellData = aIndexer.getCell(nLastInRange); + aCell = aCellData.first; + if (aCell.hasString()) + { + sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, aCellData.second); + OUString aStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); + aLastInRangeString = aStr; + } + else + { + switch (aCell.meType) + { + case CELLTYPE_VALUE : + fLastInRangeValue = aCell.mfValue; + break; + case CELLTYPE_FORMULA : + fLastInRangeValue = aCell.mpFormula->GetValue(); + break; + default: + { + // added to avoid warnings + } + } + } + + sal_Int32 nRes = 0; + bool bFound = false; + bool bDone = false; + while (nLo <= nHi && !bDone) + { + size_t nMid = (nLo+nHi)/2; + size_t i = nMid; + + aCellData = aIndexer.getCell(i); + aCell = aCellData.first; + bool bStr = aCell.hasString(); + nRes = 0; + + // compares are content<query:-1, content>query:1 + // Cell value comparison similar to ScTable::ValidQuery() + if (!bStr && !bByString) + { + double nCellVal; + switch (aCell.meType) + { + case CELLTYPE_VALUE : + case CELLTYPE_FORMULA : + nCellVal = aCell.getValue(); + break; + default: + nCellVal = 0.0; + } + if ((nCellVal < rItem.mfVal) && !::rtl::math::approxEqual( + nCellVal, rItem.mfVal)) + { + nRes = -1; + if (bLessEqual) + { + if (fLastInRangeValue < nCellVal) + { + fLastInRangeValue = nCellVal; + nLastInRange = i; + } + else if (fLastInRangeValue > nCellVal) + { + // not strictly sorted, continue with GetThis() + nLastInRange = nFirstLastInRange; + bDone = true; + } + } + } + else if ((nCellVal > rItem.mfVal) && !::rtl::math::approxEqual( + nCellVal, rItem.mfVal)) + { + nRes = 1; + if (!bLessEqual) + { + if (fLastInRangeValue > nCellVal) + { + fLastInRangeValue = nCellVal; + nLastInRange = i; + } + else if (fLastInRangeValue < nCellVal) + { + // not strictly sorted, continue with GetThis() + nLastInRange = nFirstLastInRange; + bDone = true; + } + } + } + } + else if (bStr && bByString) + { + sal_uInt32 nFormat = pCol->GetNumberFormat(mrContext, aCellData.second); + OUString aCellStr = ScCellFormat::GetInputString(aCell, nFormat, rFormatter, rDoc); + + nRes = rCollator.compareString(aCellStr, rEntry.GetQueryItem().maString.getString()); + if (nRes < 0 && bLessEqual) + { + sal_Int32 nTmp = rCollator.compareString( aLastInRangeString, + aCellStr); + if (nTmp < 0) + { + aLastInRangeString = aCellStr; + nLastInRange = i; + } + else if (nTmp > 0) + { + // not strictly sorted, continue with GetThis() + nLastInRange = nFirstLastInRange; + bDone = true; + } + } + else if (nRes > 0 && !bLessEqual) + { + sal_Int32 nTmp = rCollator.compareString( aLastInRangeString, + aCellStr); + if (nTmp > 0) + { + aLastInRangeString = aCellStr; + nLastInRange = i; + } + else if (nTmp < 0) + { + // not strictly sorted, continue with GetThis() + nLastInRange = nFirstLastInRange; + bDone = true; + } + } + } + else if (!bStr && bByString) + { + nRes = -1; // numeric < string + if (bLessEqual) + nLastInRange = i; + } + else // if (bStr && !bByString) + { + nRes = 1; // string > numeric + if (!bLessEqual) + nLastInRange = i; + } + if (nRes < 0) + { + if (bLessEqual) + nLo = nMid + 1; + else // assumed to be SC_GREATER_EQUAL + { + if (nMid > 0) + nHi = nMid - 1; + else + bDone = true; + } + } + else if (nRes > 0) + { + if (bLessEqual) + { + if (nMid > 0) + nHi = nMid - 1; + else + bDone = true; + } + else // assumed to be SC_GREATER_EQUAL + nLo = nMid + 1; + } + else + { + nLo = i; + bDone = bFound = true; + } + } + + if (!bFound) + { + // If all hits didn't result in a moving limit there's something + // strange, e.g. data range not properly sorted, or only identical + // values encountered, which doesn't mean there aren't any others in + // between... leave it to GetThis(). The condition for this would be + // if (nLastInRange == nFirstLastInRange) nLo = nFirstLastInRange; + // Else, in case no exact match was found, we step back for a + // subsequent GetThis() to find the last in range. Effectively this is + // --nLo with nLastInRange == nLo-1. Both conditions combined yield: + nLo = nLastInRange; + } + + aCellData = aIndexer.getCell(nLo); + if (nLo <= nHi && aCellData.second <= maParam.nRow2) + { + nRow = aCellData.second; + maCurPos = aIndexer.getPosition(nLo); + return true; + } + else + { + nRow = maParam.nRow2 + 1; + // Set current position to the last possible row. + maCurPos.first = pCol->maCells.end(); + --maCurPos.first; + maCurPos.second = maCurPos.first->size - 1; + return false; + } +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx index f80deb14e221..aacfa42ec8ea 100644 --- a/sc/source/core/tool/interpr1.cxx +++ b/sc/source/core/tool/interpr1.cxx @@ -61,6 +61,7 @@ #include <doubleref.hxx> #include <queryparam.hxx> #include <queryentry.hxx> +#include <queryiter.hxx> #include <tokenarray.hxx> #include <compare.hxx> diff --git a/solenv/clang-format/excludelist b/solenv/clang-format/excludelist index 08ed93138cab..14e57ef6f081 100644 --- a/solenv/clang-format/excludelist +++ b/solenv/clang-format/excludelist @@ -8001,6 +8001,7 @@ sc/inc/printopt.hxx sc/inc/prnsave.hxx sc/inc/progress.hxx sc/inc/queryentry.hxx +sc/inc/queryiter.hxx sc/inc/queryparam.hxx sc/inc/rangelst.hxx sc/inc/rangenam.hxx @@ -8190,6 +8191,7 @@ sc/source/core/data/patattr.cxx sc/source/core/data/pivot2.cxx sc/source/core/data/poolhelp.cxx sc/source/core/data/postit.cxx +sc/source/core/data/queryiter.cxx sc/source/core/data/refupdatecontext.cxx sc/source/core/data/rowheightcontext.cxx sc/source/core/data/segmenttree.cxx
