Adding upstream version 4:24.2.0.upstream/4%24.2.0

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 381 insertions, 0 deletions

diff --git a/sc/inc/queryiter.hxx b/sc/inc/queryiter.hxx
new file mode 100644
index 0000000000..1d0066de7f
--- /dev/null
+++ b/sc/inc/queryiter.hxx
@@ -0,0 +1,381 @@
+/* -*- 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"
+#include "types.hxx"
+
+struct ScComplexRefData;
+class ScSortedRangeCache;
+
+/*
+Query-related iterators. There is one template class ScQueryCellIteratorBase
+that implements most of the shared functionality, specific parts are done
+by specializing the templates and then subclassing as the actual class to use.
+A template is used for maximum performance, as that allows fast code specializing,
+inlining, etc.
+There are two template arguments:
+* ScQueryCellIteratorAccess specifies how cells are accessed:
+  + Direct - direct access to cells using mdds.
+  + SortedCache - for accessing unsorted cells in a sorted way using ScSortedRangeCache.
+* ScQueryCellIteratorType specifies the type of the query operation:
+  + Generic - the generic lookup, used e.g. by VLOOKUP.
+  + CountIf - faster implementation for COUNTIF(S).
+
+Specific data should be in specific templated base classes, otherwise adding data
+members would mean specializing the entire ScQueryCellIteratorBase. Some specific
+functionality may also be implemented in the base classes or depending on the template
+parameter.
+*/
+
+// Data and functionality for accessing cells in a specific way.
+// Needs specialization, see ScQueryCellIteratorAccess::Direct for what is needed.
+template< ScQueryCellIteratorAccess accessType >
+class ScQueryCellIteratorAccessSpecific
+{
+};
+
+// The implementation using linear direct mdds access.
+template<>
+class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::Direct >
+{
+protected:
+    ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, ScInterpreterContext& rContext,
+        const ScQueryParam& rParam );
+    // Initialize position for new column.
+    void InitPos();
+    // Increase position (next row).
+    void IncPos();
+    // Next mdds block. If access is not direct/linear, then
+    // should call IncPos().
+    void IncBlock();
+
+    // 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;
+    SCTAB           nTab;
+    SCCOL           nCol;
+    SCROW           nRow;
+
+    class NonEmptyCellIndexer;
+    typedef std::pair<ScRefCellValue, SCROW> BinarySearchCellType;
+    static NonEmptyCellIndexer MakeBinarySearchIndexer(const sc::CellStoreType& rCells,
+        SCROW nStartRow, SCROW nEndRow);
+};
+
+// The implementation using ScSortedRangeCache, which allows sorted iteration
+// of unsorted cells.
+template<>
+class ScQueryCellIteratorAccessSpecific< ScQueryCellIteratorAccess::SortedCache >
+{
+public:
+    void SetSortedRangeCache( const ScSortedRangeCache& cache );
+    template<bool fast>
+    bool IncPosImpl();
+protected:
+    ScQueryCellIteratorAccessSpecific( ScDocument& rDocument, ScInterpreterContext& rContext,
+        const ScQueryParam& rParam );
+    void InitPosStart();
+    void InitPosFinish( SCROW beforeRow, SCROW lastRow );
+    void IncPos() { IncPosImpl<false>(); }
+    bool IncPosFast() { return IncPosImpl<true>(); }
+    void IncBlock() { IncPos(); } // Cannot skip entire block, not linear.
+
+    // 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;
+    SCTAB           nTab;
+    SCCOL           nCol;
+    SCROW           nRow;
+    const ScColumn* pColumn; // matching nCol, set by InitPos()
+
+    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);
+};
+
+// Data and functionality for specific types of query.
+template< ScQueryCellIteratorType iteratorType >
+class ScQueryCellIteratorTypeSpecific
+{
+protected:
+    bool HandleItemFound(); // not implemented, needs specialization
+};
+
+// Shared code for query-based iterators. The main class.
+template< ScQueryCellIteratorAccess accessType, ScQueryCellIteratorType queryType >
+class ScQueryCellIteratorBase
+    : public ScQueryCellIteratorAccessSpecific< accessType >
+    , public ScQueryCellIteratorTypeSpecific< queryType >
+{
+    typedef ScQueryCellIteratorAccessSpecific< accessType > AccessBase;
+    typedef ScQueryCellIteratorTypeSpecific< queryType > TypeBase;
+protected:
+    enum StopOnMismatchBits
+    {
+        nStopOnMismatchDisabled = 0x00,
+        nStopOnMismatchEnabled  = 0x01,
+        nStopOnMismatchOccurred  = 0x02,
+        nStopOnMismatchExecuted = nStopOnMismatchEnabled | nStopOnMismatchOccurred
+    };
+
+    enum TestEqualConditionBits
+    {
+        nTestEqualConditionDisabled = 0x00,
+        nTestEqualConditionEnabled  = 0x01,
+        nTestEqualConditionMatched  = 0x02,
+        nTestEqualConditionFulfilled = nTestEqualConditionEnabled | nTestEqualConditionMatched
+    };
+
+    sal_uInt8            nStopOnMismatch;
+    sal_uInt8            nTestEqualCondition;
+    bool            bAdvanceQuery;
+    bool            bIgnoreMismatchOnLeadingStrings;
+
+    // Make base members directly visible here (templated bases need 'this->').
+    using AccessBase::maCurPos;
+    using AccessBase::maParam;
+    using AccessBase::rDoc;
+    using AccessBase::mrContext;
+    using AccessBase::nTab;
+    using AccessBase::nCol;
+    using AccessBase::nRow;
+    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();
+
+    /* 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,SC_LESS_EQUAL,
+       SC_EQUAL (sorted ascending) or SC_GREATER,SC_GREATER_EQUAL (sorted descending). It
+       delivers a starting point set to nRow, i.e. the last row that either matches the searched
+       for value, or the last row that matches the condition. Continue with e.g. GetThis() and
+       GetNext() afterwards. Returns false if the searched for value is not in the search range
+       or if the range is not properly sorted, with nRow in that case set to the first row or after
+       the last row. In that case use GetFirst().
+    */
+    bool BinarySearch( SCCOL col, bool forEqual = false );
+
+                    /** 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; }
+
+public:
+                    ScQueryCellIteratorBase(ScDocument& rDocument, ScInterpreterContext& rContext, SCTAB nTable,
+                                            const ScQueryParam& aParam, bool bMod);
+                                        // when !bMod, the QueryParam has to be filled
+                                        // (bIsString)
+
+                    // increments all Entry.nField, if column
+                    // changes, for ScInterpreter ScHLookup()
+    void            SetAdvanceQueryParamEntryField( bool bVal )
+                        { bAdvanceQuery = bVal; }
+    void            AdvanceQueryParamEntryField();
+};
+
+
+template<>
+class ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::Generic >
+{
+protected:
+    bool HandleItemFound();
+    bool getThisResult;
+};
+
+// The generic query iterator, used e.g. by VLOOKUP.
+template< ScQueryCellIteratorAccess accessType >
+class ScQueryCellIterator
+    : public ScQueryCellIteratorBase< accessType, ScQueryCellIteratorType::Generic >
+{
+    typedef ScQueryCellIteratorBase< accessType, ScQueryCellIteratorType::Generic > Base;
+    // 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;
+    using Base::InitPos;
+    using Base::IncPos;
+    using Base::bIgnoreMismatchOnLeadingStrings;
+    using Base::SetStopOnMismatch;
+    using Base::SetTestEqualCondition;
+    using Base::BinarySearch;
+    using typename Base::PositionType;
+    using Base::maCurPos;
+    using Base::IsEqualConditionFulfilled;
+    using Base::bAdvanceQuery;
+    using Base::StoppedOnMismatch;
+    using Base::nStopOnMismatch;
+    using Base::nStopOnMismatchEnabled;
+    using Base::nTestEqualCondition;
+    using Base::nTestEqualConditionEnabled;
+    using Base::PerformQuery;
+    using Base::getThisResult;
+
+    bool GetThis();
+
+public:
+    ScQueryCellIterator(ScDocument& rDocument, ScInterpreterContext& rContext, SCTAB nTable,
+                        const ScQueryParam& aParam, bool bMod)
+        : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+    bool GetFirst();
+    bool GetNext();
+    SCCOL GetCol() const { return nCol; }
+    SCROW GetRow() const { return nRow; }
+
+                    /** 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 );
+};
+
+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(ScDocument& rDoc, const ScQueryParam& aParam,
+        SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
+        ScInterpreterContext& context);
+};
+
+
+template<>
+class ScQueryCellIteratorTypeSpecific< ScQueryCellIteratorType::CountIf >
+{
+protected:
+    bool HandleItemFound();
+    sal_uInt64 countIfCount;
+};
+
+// Used by ScInterpreter::ScCountIf.
+template< ScQueryCellIteratorAccess accessType >
+class ScCountIfCellIterator
+    : public ScQueryCellIteratorBase< accessType, ScQueryCellIteratorType::CountIf >
+{
+protected:
+    typedef ScQueryCellIteratorBase< accessType, ScQueryCellIteratorType::CountIf > Base;
+    // Make base members directly visible here (templated bases need 'this->').
+    using Base::maParam;
+    using Base::rDoc;
+    using Base::nTab;
+    using Base::nCol;
+    using Base::nRow;
+    using Base::InitPos;
+    using Base::PerformQuery;
+    using Base::SetAdvanceQueryParamEntryField;
+    using Base::countIfCount;
+
+public:
+    ScCountIfCellIterator(ScDocument& rDocument, ScInterpreterContext& rContext, SCTAB nTable,
+                          const ScQueryParam& aParam, bool bMod)
+        : Base( rDocument, rContext, nTable, aParam, bMod ) {}
+    sal_uInt64 GetCount();
+};
+
+typedef ScCountIfCellIterator< ScQueryCellIteratorAccess::Direct > ScCountIfCellIteratorDirect;
+
+class ScCountIfCellIteratorSortedCache
+    : public ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache >
+{
+    typedef ScCountIfCellIterator< ScQueryCellIteratorAccess::SortedCache > Base;
+public:
+    ScCountIfCellIteratorSortedCache(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(ScDocument& rDoc, const ScQueryParam& aParam,
+        SCTAB nTab, const ScFormulaCell* cell, const ScComplexRefData* refData,
+        ScInterpreterContext& context);
+};
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */