tdf#127293 Add Excel2021 function XLOOKUP to Calc

https://issues.oasis-open.org/browse/OFFICE-4154

What is working already: xlookup with normal forward,
backward search in columns/rows. Binary search in rows with
real binary search algorithm, in columns only works with linear search yet.
Linear forward backward wildcard/regex search in columns/rows.
Looking for the first smaller or greater value with linear and binary search
ALso all the combination of all these options. Except XLOOKUP
not supperted wildcard/regex search with binary search.

TODO in next patches:
- add the binary search option for searching in columns.
- Evaluate Formula calculation not working in general.

Co-authored-by: Balazs Varga <balazs.varga.extern@allotropia.de>

Change-Id: I15fd4479b63ec13b093d269760d1bbb5957553e8
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/131905
Tested-by: Jenkins
Tested-by: Gabor Kelemen <gabor.kelemen.extern@allotropia.de>
Reviewed-by: Balazs Varga <balazs.varga.extern@allotropia.de>

1 files changed, 48 insertions, 12 deletions

diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
index 1d0066de7fb8..e34a7be20e13 100644
--- a/sc/inc/queryiter.hxx
+++ b/sc/inc/queryiter.hxx
@@ -62,7 +62,7 @@ class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
 {
 protected:
     ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, ScInterpreterContext& rContext,
-        const ScQueryParam& rParam );
+        const ScQueryParam& rParam, bool bReverseSearch );
     // Initialize position for new column.
     void InitPos();
     // Increase position (next row).
@@ -71,12 +71,19 @@ protected:
     // should call IncPos().
     void IncBlock();
 
+    // Decrease position (prev row).
+    void DecPos();
+    // Prev mdds block. If access is not direct/linear, then
+    // should call DecPos().
+    void DecBlock();
+
     // These members needs to be available already in the base class.
     typedef sc::CellStoreType::const_position_type PositionType;
     PositionType maCurPos;
     ScQueryParam    maParam;
     ScDocument&     rDoc;
     ScInterpreterContext& mrContext;
+    bool            mbReverseSearch;
     SCTAB           nTab;
     SCCOL           nCol;
     SCROW           nRow;
@@ -98,19 +105,24 @@ public:
     bool IncPosImpl();
 protected:
     ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, ScInterpreterContext& rContext,
-        const ScQueryParam& rParam );
+        const ScQueryParam& rParam, bool bReverseSearch );
     void InitPosStart();
-    void InitPosFinish( SCROW beforeRow, SCROW lastRow );
+    void InitPosFinish( SCROW beforeRow, SCROW lastRow, bool bFirstMatch );
     void IncPos() { IncPosImpl<false>(); }
     bool IncPosFast() { return IncPosImpl<true>(); }
     void IncBlock() { IncPos(); } // Cannot skip entire block, not linear.
 
+    // Initialize for backward search. (no need for SortedCache)
+    static void DecPos() {};
+    static void DecBlock() {};
+
     // These members needs to be available already in the base class.
     typedef sc::CellStoreType::const_position_type PositionType;
     PositionType maCurPos;
     ScQueryParam    maParam;
     ScDocument&     rDoc;
     ScInterpreterContext& mrContext;
+    bool            mbReverseSearch;
     SCTAB           nTab;
     SCCOL           nCol;
     SCROW           nRow;
@@ -163,17 +175,24 @@ protected:
     sal_uInt8            nTestEqualCondition;
     bool            bAdvanceQuery;
     bool            bIgnoreMismatchOnLeadingStrings;
+    bool            bSortedBinarySearch;
+    bool            bXLookUp;
+    SCCOL           nBestFitCol;
+    SCROW           nBestFitRow;
 
     // Make base members directly visible here (templated bases need 'this->').
     using AccessBase::maCurPos;
     using AccessBase::maParam;
     using AccessBase::rDoc;
     using AccessBase::mrContext;
+    using AccessBase::mbReverseSearch;
     using AccessBase::nTab;
     using AccessBase::nCol;
     using AccessBase::nRow;
     using AccessBase::IncPos;
     using AccessBase::IncBlock;
+    using AccessBase::DecPos;
+    using AccessBase::DecBlock;
     using typename AccessBase::BinarySearchCellType;
     using AccessBase::MakeBinarySearchIndexer;
     using TypeBase::HandleItemFound;
@@ -227,9 +246,14 @@ protected:
     bool            IsEqualConditionFulfilled() const
                         { return nTestEqualCondition == nTestEqualConditionFulfilled; }
 
+    void            HandleBestFitItemFound(SCCOL nBFitCol, SCROW nBFitRow)
+                        {
+                            nBestFitCol = nBFitCol;
+                            nBestFitRow = nBFitRow;
+                        }
 public:
                     ScQueryCellIteratorBase(ScDocument& rDocument, ScInterpreterContext& rContext, SCTAB nTable,
-                                            const ScQueryParam& aParam, bool bMod);
+                                            const ScQueryParam& aParam, bool bMod, bool bReverse);
                                         // when !bMod, the QueryParam has to be filled
                                         // (bIsString)
 
@@ -238,6 +262,12 @@ public:
     void            SetAdvanceQueryParamEntryField( bool bVal )
                         { bAdvanceQuery = bVal; }
     void            AdvanceQueryParamEntryField();
+
+    void            SetSortedBinarySearchMode( bool bVal )
+                        { bSortedBinarySearch = bVal; }
+
+    void            SetXlookupMode( bool bVal )
+                        { bXLookUp = bVal; }
 };
 
 
@@ -259,11 +289,13 @@ class ScQueryCellIterator
     using Base::maParam;
     using Base::rDoc;
     using Base::mrContext;
+    using Base::mbReverseSearch;
     using Base::nTab;
     using Base::nCol;
     using Base::nRow;
     using Base::InitPos;
     using Base::IncPos;
+    using Base::DecPos;
     using Base::bIgnoreMismatchOnLeadingStrings;
     using Base::SetStopOnMismatch;
     using Base::SetTestEqualCondition;
@@ -279,13 +311,17 @@ class ScQueryCellIterator
     using Base::nTestEqualConditionEnabled;
     using Base::PerformQuery;
     using Base::getThisResult;
+    using Base::nBestFitCol;
+    using Base::nBestFitRow;
+    using Base::bSortedBinarySearch;
+    using Base::bXLookUp;
 
     bool GetThis();
 
 public:
     ScQueryCellIterator(ScDocument& rDocument, ScInterpreterContext& rContext, SCTAB nTable,
-                        const ScQueryParam& aParam, bool bMod)
-        : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+                        const ScQueryParam& aParam, bool bMod, bool bReverse)
+        : Base( rDocument, rContext, nTable, aParam, bMod, bReverse ) {}
     bool GetFirst();
     bool GetNext();
     SCCOL GetCol() const { return nCol; }
@@ -320,8 +356,8 @@ class ScQueryCellIteratorSortedCache
     typedef ScQueryCellIterator< ScQueryCellIteratorAccess::SortedCache > Base;
 public:
     ScQueryCellIteratorSortedCache(ScDocument& rDocument, ScInterpreterContext& rContext,
-        SCTAB nTable, const ScQueryParam& aParam, bool bMod)
-    : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+        SCTAB nTable, const ScQueryParam& aParam, bool bMod, bool bReverse )
+    : Base( rDocument, rContext, nTable, aParam, bMod, bReverse ) {}
     // Returns true if this iterator can be used for the given query.
     static bool CanBeUsed(ScDocument& rDoc, const ScQueryParam& aParam,
         SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
@@ -357,8 +393,8 @@ protected:
 
 public:
     ScCountIfCellIterator(ScDocument& rDocument, ScInterpreterContext& rContext, SCTAB nTable,
-                          const ScQueryParam& aParam, bool bMod)
-        : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+                          const ScQueryParam& aParam, bool bMod, bool bReverse)
+        : Base( rDocument, rContext, nTable, aParam, bMod, bReverse ) {}
     sal_uInt64 GetCount();
 };
 
@@ -370,8 +406,8 @@ class ScCountIfCellIteratorSortedCache
     typedef ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache > Base;
 public:
     ScCountIfCellIteratorSortedCache(ScDocument& rDocument, ScInterpreterContext& rContext,
-        SCTAB nTable, const ScQueryParam& aParam, bool bMod)
-    : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+        SCTAB nTable, const ScQueryParam& aParam, bool bMod, bool bReverse)
+    : Base( rDocument, rContext, nTable, aParam, bMod, bReverse ) {}
     // Returns true if this iterator can be used for the given query.
     static bool CanBeUsed(ScDocument& rDoc, const ScQueryParam& aParam,
         SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,