use ScSortedRangeCache also for generic queries

This enables use for e.g. VLOOKUP or COUNTIFS (as COUNTIFS does
not use the specialized code for COUNTIF).

Change-Id: Idad7503750d421f3f1c9ac34dfe95393fa3ead15
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/134124
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

4 files changed, 187 insertions, 59 deletions

diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
index 2b542233d7cd..c27aadf92c68 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -60,7 +60,8 @@ template<>
 class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
 {
 protected:
-    ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const ScQueryParam& rParam );
+    ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, ScInterpreterContext& rContext,
+        const ScQueryParam& rParam );
     // Initialize position for new column.
     void InitPos();
     // Increase position (next row).
@@ -74,6 +75,7 @@ protected:
     PositionType maCurPos;
     ScQueryParam    maParam;
     ScDocument&     rDoc;
+    ScInterpreterContext& mrContext;
     SCTAB           nTab;
     SCCOL           nCol;
     SCROW           nRow;
@@ -92,8 +94,10 @@ class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache
 public:
     void SetSortedRangeCache( const ScSortedRangeCache& cache );
 protected:
-    ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const ScQueryParam& rParam );
-    void InitPos();
+    ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, ScInterpreterContext& rContext,
+        const ScQueryParam& rParam );
+    void InitPosStart();
+    void InitPosFinish( SCROW beforeRow, SCROW lastRow );
     void IncPos();
     void IncBlock() { IncPos(); } // Cannot skip entire block, not linear.
 
@@ -102,19 +106,19 @@ protected:
     PositionType maCurPos;
     ScQueryParam    maParam;
     ScDocument&     rDoc;
+    ScInterpreterContext& mrContext;
     SCTAB           nTab;
     SCCOL           nCol;
     SCROW           nRow;
 
     const ScSortedRangeCache* sortedCache;
     size_t sortedCachePos;
+    size_t sortedCachePosLast;
 
     class SortedCacheIndexer;
     typedef std::pair<ScRefCellValue, SCROW> BinarySearchCellType;
     SortedCacheIndexer MakeBinarySearchIndexer(const sc::CellStoreType& rCells,
         SCROW nStartRow, SCROW nEndRow);
-private:
-    void UpdatePos();
 };
 
 // Data and functionality for specific types of query.
@@ -150,7 +154,6 @@ protected:
         nTestEqualConditionFulfilled = nTestEqualConditionEnabled | nTestEqualConditionMatched
     };
 
-    ScInterpreterContext& mrContext;
     sal_uInt8            nStopOnMismatch;
     sal_uInt8            nTestEqualCondition;
     bool            bAdvanceQuery;
@@ -160,16 +163,18 @@ protected:
     using AccessBase::maCurPos;
     using AccessBase::maParam;
     using AccessBase::rDoc;
+    using AccessBase::mrContext;
     using AccessBase::nTab;
     using AccessBase::nCol;
     using AccessBase::nRow;
-    using AccessBase::InitPos;
     using AccessBase::IncPos;
     using AccessBase::IncBlock;
     using typename AccessBase::BinarySearchCellType;
     using AccessBase::MakeBinarySearchIndexer;
     using TypeBase::HandleItemFound;
 
+    void InitPos();
+
     // The actual query function. It will call HandleItemFound() for any matching type
     // and return if HandleItemFound() returns true.
     void PerformQuery();
@@ -248,6 +253,7 @@ class ScQueryCellIterator
     // Make base members directly visible here (templated bases need 'this->').
     using Base::maParam;
     using Base::rDoc;
+    using Base::mrContext;
     using Base::nTab;
     using Base::nCol;
     using Base::nRow;
@@ -303,6 +309,18 @@ public:
 
 typedef ScQueryCellIterator< ScQueryCellIteratorAccess::Direct > ScQueryCellIteratorDirect;
 
+class ScQueryCellIteratorSortedCache
+    : public ScQueryCellIterator< ScQueryCellIteratorAccess::SortedCache >
+{
+    typedef ScQueryCellIterator< ScQueryCellIteratorAccess::SortedCache > Base;
+public:
+    ScQueryCellIteratorSortedCache(ScDocument& rDocument, ScInterpreterContext& rContext,
+        SCTAB nTable, const ScQueryParam& aParam, bool bMod)
+    : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+    // Returns true if this iterator can be used for the given query.
+    static bool CanBeUsed(const ScQueryParam& aParam);
+};
+
 
 template<>
 class ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::CountIf >
diff --git a/sc/source/core/data/queryiter.cxx b/sc/source/core/data/queryiter.cxx
index 184e86ada37a..438128ef5f47 100644
--- a/sc/source/core/data/queryiter.cxx
+++ b/sc/source/core/data/queryiter.cxx
@@ -60,8 +60,7 @@
 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
 ScQueryCellIteratorBase< accessType, queryType >::ScQueryCellIteratorBase(ScDocument& rDocument,
     ScInterpreterContext& rContext, SCTAB nTable, const ScQueryParam& rParam, bool bMod )
-    : AccessBase( rDocument, rParam )
-    , mrContext( rContext )
+    : AccessBase( rDocument, rContext, rParam )
     , nStopOnMismatch( nStopOnMismatchDisabled )
     , nTestEqualCondition( nTestEqualConditionDisabled )
     , bAdvanceQuery( false )
@@ -235,6 +234,47 @@ void ScQueryCellIteratorBase< accessType, queryType >::PerformQuery()
 }
 
 template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
+void ScQueryCellIteratorBase< accessType, queryType >::InitPos()
+{
+    if constexpr( accessType != ScQueryCellIteratorAccess::SortedCache )
+        AccessBase::InitPos();
+    else
+    {
+        // This should be all in AccessBase::InitPos(), but that one can't call
+        // BinarySearch(), so do it this way instead.
+        AccessBase::InitPosStart();
+        ScQueryOp& op = maParam.GetEntry(0).eOp;
+        SCROW beforeRow = -1;
+        SCROW lastRow = -1;
+        if( op == SC_EQUAL )
+        {
+            if( BinarySearch( nCol ))
+            {
+                // BinarySearch() searches for the last item that matches. Now we
+                // also need to find the first item where to start. Find the last
+                // non-matching position using SC_LESS and the start position
+                // is the one after it.
+                lastRow = nRow;
+                ScQueryOp saveOp = op;
+                op = SC_LESS;
+                if( BinarySearch( nCol ))
+                    beforeRow = nRow;
+                // If BinarySearch() returns false, there was no match, which means
+                // there's no value smaller. In that case BinarySearch() has set
+                // the position to the first row in the range.
+                op = saveOp; // back to SC_EQUAL
+            }
+        }
+        else
+        {   // The range is from the start up to and including the last matching.
+            if( BinarySearch( nCol ))
+                lastRow = nRow;
+        }
+        AccessBase::InitPosFinish( beforeRow, lastRow );
+    }
+}
+
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
 void ScQueryCellIteratorBase< accessType, queryType >::AdvanceQueryParamEntryField()
 {
     SCSIZE nEntries = maParam.GetEntryCount();
@@ -799,9 +839,11 @@ bool ScQueryCellIterator< accessType >::FindEqualOrSortedLastInRange( SCCOL& nFo
 // Direct linear cell access using mdds.
 
 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
-    ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const ScQueryParam& rParam )
+    ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument,
+        ScInterpreterContext& rContext, const ScQueryParam& rParam )
     : maParam( rParam )
     , rDoc( rDocument )
+    , mrContext( rContext )
 {
 }
 
@@ -1008,9 +1050,11 @@ ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >::MakeBina
 // Sorted access using ScSortedRangeCache.
 
 ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >
-    ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, const ScQueryParam& rParam )
+    ::ScQueryCellIteratorAccessSpecific( ScDocument& rDocument,
+        ScInterpreterContext& rContext, const ScQueryParam& rParam )
     : maParam( rParam )
     , rDoc( rDocument )
+    , mrContext( rContext )
 {
 }
 
@@ -1020,31 +1064,54 @@ void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >
     sortedCache = &cache;
 }
 
-void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::InitPos()
+// The idea in iterating using the sorted cache is that the iteration is instead done
+// over indexes of the sorted cache (which is a stable sort of the cell contents) in the range
+// that fits the query condition and then that is mapped to rows. This will result in iterating
+// over only matching rows in their sorted order (and for equal rows in their row order).
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::InitPosStart()
 {
-    assert(sortedCache->getRange().aStart.Row() == maParam.nRow1);
-    assert(!(maParam.bHasHeader && maParam.bByRow));
-    sortedCachePos = 0;
-    UpdatePos();
+    ScRange aSortedRangeRange( nCol, maParam.nRow1, nTab, nCol, maParam.nRow2, nTab );
+    ScQueryOp& op = maParam.GetEntry(0).eOp;
+    // We want all matching values first in the sort order,
+    bool descending = op == SC_GREATER || op == SC_GREATER_EQUAL;
+    SetSortedRangeCache( rDoc.GetSortedRangeCache( aSortedRangeRange, descending, &mrContext ));
+    // InitPosFinish() needs to be called after this, ScQueryCellIteratorBase::InitPos()
+    // will handle that
 }
 
-void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::IncPos()
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::InitPosFinish(
+    SCROW beforeRow, SCROW lastRow )
 {
-    ++sortedCachePos;
-    UpdatePos();
+    const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
+    if(lastRow >= 0)
+    {
+        sortedCachePos = beforeRow >= 0 ? sortedCache->indexForRow(beforeRow) + 1 : 0;
+        sortedCachePosLast = sortedCache->indexForRow(lastRow);
+        if(sortedCachePos <= sortedCachePosLast)
+        {
+            nRow = sortedCache->rowForIndex(sortedCachePos);
+            maCurPos = rCol.maCells.position(nRow);
+            return;
+        }
+    }
+    // No rows, set to end.
+    sortedCachePos = sortedCachePosLast = 0;
+    maCurPos.first = rCol.maCells.end();
+    maCurPos.second = 0;
 }
 
-void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::UpdatePos()
+void ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::IncPos()
 {
-    // TODO optimize?
-    const ScColumn& rCol = rDoc.maTabs[nTab]->CreateColumnIfNotExists(nCol);
-    if(sortedCachePos < sortedCache->size())
+    const ScColumn& rCol = rDoc.maTabs[nTab]->aCol[nCol];
+    if(sortedCachePos < sortedCachePosLast)
     {
+        ++sortedCachePos;
         nRow = sortedCache->rowForIndex(sortedCachePos);
         maCurPos = rCol.maCells.position(nRow);
     }
     else
     {
+        // This will make PerformQuery() go to next column.
         maCurPos.first = rCol.maCells.end();
         maCurPos.second = 0;
     }
@@ -1125,6 +1192,25 @@ ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >::Mak
     return SortedCacheIndexer(rCells, nStartRow, nEndRow, sortedCache);
 }
 
+static bool CanBeUsedForSorterCache(const ScQueryParam& rParam)
+{
+    if(!rParam.GetEntry(0).bDoQuery || rParam.GetEntry(1).bDoQuery
+        || rParam.GetEntry(0).GetQueryItems().size() != 1 )
+        return false;
+    if(rParam.eSearchType != utl::SearchParam::SearchType::Normal)
+        return false;
+    if(rParam.GetEntry(0).GetQueryItem().meType != ScQueryEntry::ByValue)
+        return false;
+    if(!rParam.bByRow)
+        return false;
+    if(rParam.bHasHeader)
+        return false;
+    if(rParam.GetEntry(0).eOp != SC_LESS && rParam.GetEntry(0).eOp != SC_LESS_EQUAL
+        && rParam.GetEntry(0).eOp != SC_GREATER && rParam.GetEntry(0).eOp != SC_GREATER_EQUAL
+        && rParam.GetEntry(0).eOp != SC_EQUAL)
+        return false;
+    return true;
+}
 
 // Generic query implementation.
 
@@ -1162,6 +1248,11 @@ bool ScQueryCellIterator< accessType >::GetNext()
     return GetThis();
 }
 
+bool ScQueryCellIteratorSortedCache::CanBeUsed(const ScQueryParam& rParam)
+{
+    return CanBeUsedForSorterCache(rParam);
+}
+
 // Countifs implementation.
 
 bool ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::CountIf >::HandleItemFound()
@@ -1188,22 +1279,7 @@ sal_uInt64 ScCountIfCellIterator< accessType >::GetCount()
 
 bool ScCountIfCellIteratorSortedCache::CanBeUsed(const ScQueryParam& rParam)
 {
-    if(!rParam.GetEntry(0).bDoQuery || rParam.GetEntry(1).bDoQuery
-        || rParam.GetEntry(0).GetQueryItems().size() != 1 )
-        return false;
-    if(rParam.eSearchType != utl::SearchParam::SearchType::Normal)
-        return false;
-    if(rParam.GetEntry(0).GetQueryItem().meType != ScQueryEntry::ByValue)
-        return false;
-    if(!rParam.bByRow)
-        return false;
-    if(rParam.bHasHeader)
-        return false;
-    if(rParam.GetEntry(0).eOp != SC_LESS && rParam.GetEntry(0).eOp != SC_LESS_EQUAL
-        && rParam.GetEntry(0).eOp != SC_GREATER && rParam.GetEntry(0).eOp != SC_GREATER_EQUAL
-        && rParam.GetEntry(0).eOp != SC_EQUAL)
-        return false;
-    return true;
+    return CanBeUsedForSorterCache(rParam);
 }
 
 template<>
@@ -1272,11 +1348,13 @@ sal_uInt64 ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >::GetC
 }
 
 template class ScQueryCellIterator< ScQueryCellIteratorAccess::Direct >;
+template class ScQueryCellIterator< ScQueryCellIteratorAccess::SortedCache >;
 template class ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct >;
 template class ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >;
 
 // gcc for some reason needs these too
 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct, ScQueryCellIteratorType::Generic >;
+template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::SortedCache, ScQueryCellIteratorType::Generic >;
 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::Direct, ScQueryCellIteratorType::CountIf >;
 template class ScQueryCellIteratorBase< ScQueryCellIteratorAccess::SortedCache, ScQueryCellIteratorType::CountIf >;
 
diff --git a/sc/source/core/tool/interpr1.cxx b/sc/source/core/tool/interpr1.cxx
index ec67766a26d1..92b4de1b3443 100644
--- a/sc/source/core/tool/interpr1.cxx
+++ b/sc/source/core/tool/interpr1.cxx
@@ -6150,17 +6150,35 @@ void ScInterpreter::IterateParametersIfs( double(*ResultFunc)( const sc::ParamIf
             }
             else
             {
-                ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1, rParam, false);
-                // Increment Entry.nField in iterator when switching to next column.
-                aCellIter.SetAdvanceQueryParamEntryField( true );
-                if ( aCellIter.GetFirst() )
+                if( ScQueryCellIteratorSortedCache::CanBeUsed( rParam ))
                 {
-                    do
+                    ScQueryCellIteratorSortedCache aCellIter(mrDoc, mrContext, nTab1, rParam, false);
+                    // Increment Entry.nField in iterator when switching to next column.
+                    aCellIter.SetAdvanceQueryParamEntryField( true );
+                    if ( aCellIter.GetFirst() )
                     {
-                        size_t nC = aCellIter.GetCol() + nColDiff;
-                        size_t nR = aCellIter.GetRow() + nRowDiff;
-                        ++vConditions[nC * nDimensionRows + nR];
-                    } while ( aCellIter.GetNext() );
+                        do
+                        {
+                            size_t nC = aCellIter.GetCol() + nColDiff;
+                            size_t nR = aCellIter.GetRow() + nRowDiff;
+                            ++vConditions[nC * nDimensionRows + nR];
+                        } while ( aCellIter.GetNext() );
+                    }
+                }
+                else
+                {
+                    ScQueryCellIteratorDirect aCellIter(mrDoc, mrContext, nTab1, rParam, false);
+                    // Increment Entry.nField in iterator when switching to next column.
+                    aCellIter.SetAdvanceQueryParamEntryField( true );
+                    if ( aCellIter.GetFirst() )
+                    {
+                        do
+                        {
+                            size_t nC = aCellIter.GetCol() + nColDiff;
+                            size_t nR = aCellIter.GetRow() + nRowDiff;
+                            ++vConditions[nC * nDimensionRows + nR];
+                        } while ( aCellIter.GetNext() );
+                    }
                 }
             }
             if (nRefArrayPos != std::numeric_limits<size_t>::max())
@@ -9951,28 +9969,43 @@ utl::SearchParam::SearchType ScInterpreter::DetectSearchType( std::u16string_vie
 static bool lcl_LookupQuery( ScAddress & o_rResultPos, ScDocument& rDoc, ScInterpreterContext& rContext,
         const ScQueryParam & rParam, const ScQueryEntry & rEntry )
 {
-    bool bFound = false;
-    ScQueryCellIteratorDirect aCellIter( rDoc, rContext, rParam.nTab, rParam, false);
     if (rEntry.eOp != SC_EQUAL)
     {
         // range lookup <= or >=
         SCCOL nCol;
         SCROW nRow;
-        bFound = aCellIter.FindEqualOrSortedLastInRange( nCol, nRow);
-        if (bFound)
+        ScQueryCellIteratorDirect aCellIter( rDoc, rContext, rParam.nTab, rParam, false);
+        if( aCellIter.FindEqualOrSortedLastInRange( nCol, nRow ))
         {
             o_rResultPos.SetCol( nCol);
             o_rResultPos.SetRow( nRow);
+            return true;
         }
     }
-    else if (aCellIter.GetFirst())
+    else // EQUAL
     {
-        // EQUAL
-        bFound = true;
-        o_rResultPos.SetCol( aCellIter.GetCol());
-        o_rResultPos.SetRow( aCellIter.GetRow());
+        if( ScQueryCellIteratorSortedCache::CanBeUsed( rParam ))
+        {
+            ScQueryCellIteratorSortedCache aCellIter( rDoc, rContext, rParam.nTab, rParam, false);
+            if (aCellIter.GetFirst())
+            {
+                o_rResultPos.SetCol( aCellIter.GetCol());
+                o_rResultPos.SetRow( aCellIter.GetRow());
+                return true;
+            }
+        }
+        else
+        {
+            ScQueryCellIteratorDirect aCellIter( rDoc, rContext, rParam.nTab, rParam, false);
+            if (aCellIter.GetFirst())
+            {
+                o_rResultPos.SetCol( aCellIter.GetCol());
+                o_rResultPos.SetRow( aCellIter.GetRow());
+                return true;
+            }
+        }
     }
-    return bFound;
+    return false;
 }
 
 // tdf#121052:
diff --git a/sc/source/core/tool/rangecache.cxx b/sc/source/core/tool/rangecache.cxx
index facd906a2f3e..0bfeb971969c 100644
--- a/sc/source/core/tool/rangecache.cxx
+++ b/sc/source/core/tool/rangecache.cxx
@@ -35,7 +35,6 @@ ScSortedRangeCache::ScSortedRangeCache(ScDocument* pDoc, const ScRange& rRange,
     assert(maRange.aStart.Tab() == maRange.aEnd.Tab());
     SCTAB nTab = maRange.aStart.Tab();
     SCTAB nCol = maRange.aStart.Col();
-    mSortedRows.reserve(maRange.aEnd.Row() - maRange.aStart.Row() + 1);
     for (SCROW nRow = maRange.aStart.Row(); nRow <= maRange.aEnd.Row(); ++nRow)
     {
         ScRefCellValue cell(pDoc->GetRefCellValue(ScAddress(nCol, nRow, nTab)));