tdf#89387 improve performance for some matrix operations

add method in scmatrix to get Gcd and lcm
modified function scinterpreter::ScGcd() and scinterpreter::ScLcm()
now should be ok

Change-Id: I1e41fa5707bc4b637a986f2fc0a2358ac0121af1
Reviewed-on: https://gerrit.libreoffice.org/34110
Reviewed-by: Eike Rathke <erack@redhat.com>
Tested-by: Eike Rathke <erack@redhat.com>

5 files changed, 165 insertions, 40 deletions

diff --git a/sc/inc/scmatrix.hxx b/sc/inc/scmatrix.hxx
index 7fdcb1d782d9..632205a6ebfb 100644
--- a/sc/inc/scmatrix.hxx
+++ b/sc/inc/scmatrix.hxx
@@ -387,6 +387,8 @@ public:
 
     virtual double GetMaxValue( bool bTextAsZero ) const = 0;
     virtual double GetMinValue( bool bTextAsZero ) const = 0;
+    virtual double GetGcd() const = 0;
+    virtual double GetLcm() const = 0;
 
     virtual ScMatrixRef CompareMatrix(
         sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions ) const = 0;
@@ -601,6 +603,8 @@ public:
 
     virtual double GetMaxValue( bool bTextAsZero ) const override;
     virtual double GetMinValue( bool bTextAsZero ) const override;
+    virtual double GetGcd() const override;
+    virtual double GetLcm() const override;
 
     virtual ScMatrixRef CompareMatrix(
         sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions ) const override;
@@ -818,6 +822,8 @@ public:
 
     virtual double GetMaxValue(bool bTextAsZero) const override;
     virtual double GetMinValue(bool bTextAsZero) const override;
+    virtual double GetGcd() const override;
+    virtual double GetLcm() const override;
 
     virtual ScMatrixRef CompareMatrix(sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions) const override;
 
diff --git a/sc/qa/unit/ucalc_formula.cxx b/sc/qa/unit/ucalc_formula.cxx
index cec64f16d15c..1fde2916d369 100644
--- a/sc/qa/unit/ucalc_formula.cxx
+++ b/sc/qa/unit/ucalc_formula.cxx
@@ -6976,6 +6976,20 @@ void Test::testFuncGCD()
     CPPUNIT_ASSERT_EQUAL_MESSAGE("GCD should return Err:502 for a array with strings",
             OUString("Err:502"), aVal);
 
+    //many inline array
+    m_pDoc->SetString(aPos, "=GCD({6;6;6};{3;6;9})");
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("Calculation of GCD for failed", 3.0, m_pDoc->GetValue(aPos));
+    m_pDoc->SetString(aPos, "=GCD({300;300;300};{150;0})");
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("Calculation of GCD for failed", 150.0, m_pDoc->GetValue(aPos));
+    m_pDoc->SetString(aPos,"=GCD({3;6;9};{3;-6;9})");
+    aVal = m_pDoc->GetString(aPos);
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("GCD should return Err:502 for a array with values less then 0",
+            OUString("Err:502"), aVal);
+    m_pDoc->SetString(aPos, "=GCD({3;6;9};{\"a\";6;9})");
+    aVal = m_pDoc->GetString(aPos);
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("GCD should return Err:502 for a array with strings",
+            OUString("Err:502"), aVal);
+
     // inline list of values
     m_pDoc->SetString(aPos, "=GCD(12;24;36;48;60)");
     CPPUNIT_ASSERT_EQUAL_MESSAGE("Calculation of GCD for failed", 12.0, m_pDoc->GetValue(aPos));
@@ -7059,6 +7073,20 @@ void Test::testFuncLCM()
     CPPUNIT_ASSERT_EQUAL_MESSAGE("LCM should return Err:502 for a array with strings",
             OUString("Err:502"), aVal);
 
+        //many inline array
+    m_pDoc->SetString(aPos, "=LCM({6;6;6};{3;6;9})");
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("Calculation of LCM for failed", 18.0, m_pDoc->GetValue(aPos));
+    m_pDoc->SetString(aPos, "=LCM({300;300;300};{150;0})");
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("Calculation of LCM for failed", 0.0, m_pDoc->GetValue(aPos));
+    m_pDoc->SetString(aPos,"=LCM({3;6;9};{3;-6;9})");
+    aVal = m_pDoc->GetString(aPos);
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("LCM should return Err:502 for a array with values less then 0",
+            OUString("Err:502"), aVal);
+    m_pDoc->SetString(aPos, "=LCM({3;6;9};{\"a\";6;9})");
+    aVal = m_pDoc->GetString(aPos);
+    CPPUNIT_ASSERT_EQUAL_MESSAGE("LCM should return Err:502 for a array with strings",
+            OUString("Err:502"), aVal);
+
     m_pDoc->SetString(aPos, "=LCM(12;24;36;48;60)");
     CPPUNIT_ASSERT_EQUAL_MESSAGE("Calculation of LCM for failed", 720.0, m_pDoc->GetValue(aPos));
     m_pDoc->SetString(aPos, "=LCM(0;12;24;36;48;60)");
diff --git a/sc/source/core/inc/interpre.hxx b/sc/source/core/inc/interpre.hxx
index 2a810abd301f..2004fd11d9ba 100644
--- a/sc/source/core/inc/interpre.hxx
+++ b/sc/source/core/inc/interpre.hxx
@@ -234,6 +234,7 @@ bool IsTableOpInRange( const ScRange& );
 sal_uLong GetCellNumberFormat( const ScAddress& rPos, ScRefCellValue& rCell );
 double ConvertStringToValue( const OUString& );
 public:
+static double ScGetGCD(double fx, double fy);
 /** For matrix back calls into the current interpreter.
     Uses rError instead of nGlobalError and rCurFmtType instead of nCurFmtType. */
 double ConvertStringToValue( const OUString&, FormulaError& rError, short& rCurFmtType );
@@ -779,7 +780,6 @@ void ScEffect();
 void ScNominal();
 void ScMod();
 void ScIntercept();
-static double ScGetGCD(double fx, double fy);
 void ScGCD();
 void ScLCM();
 
@@ -831,6 +831,7 @@ static SC_DLLPUBLIC double integralPhi(double x);
 static SC_DLLPUBLIC double gaussinv(double x);
 static SC_DLLPUBLIC double GetPercentile( ::std::vector<double> & rArray, double fPercentile );
 
+
 private:
 double GetBetaDist(double x, double alpha, double beta);  //cumulative distribution function
 double GetBetaDistPDF(double fX, double fA, double fB); //probability density function)
diff --git a/sc/source/core/tool/interpr5.cxx b/sc/source/core/tool/interpr5.cxx
index 43a80861d612..fe3b6e402a32 100644
--- a/sc/source/core/tool/interpr5.cxx
+++ b/sc/source/core/tool/interpr5.cxx
@@ -187,24 +187,8 @@ void ScInterpreter::ScGCD()
                             SetError(FormulaError::IllegalArgument);
                         else
                         {
-                            for ( SCSIZE j = 0; j < nC; j++ )
-                            {
-                                for (SCSIZE k = 0; k < nR; ++k)
-                                {
-                                    if (!pMat->IsValue(j,k))
-                                    {
-                                        PushIllegalArgument();
-                                        return;
-                                    }
-                                    fx = ::rtl::math::approxFloor( pMat->GetDouble(j,k));
-                                    if (fx < 0.0)
-                                    {
-                                        PushIllegalArgument();
-                                        return;
-                                    }
-                                    fy = ScGetGCD(fx, fy);
-                                }
-                            }
+                         double nVal = pMat->GetGcd();
+                         fy = ScGetGCD(nVal,fy);
                         }
                     }
                 }
@@ -283,27 +267,8 @@ void ScInterpreter:: ScLCM()
                             SetError(FormulaError::IllegalArgument);
                         else
                         {
-                            for ( SCSIZE j = 0; j < nC; j++ )
-                            {
-                                for (SCSIZE k = 0; k < nR; ++k)
-                                {
-                                    if (!pMat->IsValue(j,k))
-                                    {
-                                        PushIllegalArgument();
-                                        return;
-                                    }
-                                    fx = ::rtl::math::approxFloor( pMat->GetDouble(j,k));
-                                    if (fx < 0.0)
-                                    {
-                                        PushIllegalArgument();
-                                        return;
-                                    }
-                                    if (fx == 0.0 || fy == 0.0)
-                                        fy = 0.0;
-                                    else
-                                        fy = fx * fy / ScGetGCD(fx, fy);
-                                }
-                            }
+                         double nVal = pMat->GetLcm();
+                         fy = (nVal * fy ) / ScGetGCD(nVal, fy);
                         }
                     }
                 }
diff --git a/sc/source/core/tool/scmatrix.cxx b/sc/source/core/tool/scmatrix.cxx
index 10210621fcb2..bd98d4b4213a 100644
--- a/sc/source/core/tool/scmatrix.cxx
+++ b/sc/source/core/tool/scmatrix.cxx
@@ -305,6 +305,8 @@ public:
 
     double GetMaxValue( bool bTextAsZero ) const;
     double GetMinValue( bool bTextAsZero ) const;
+    double GetGcd() const;
+    double GetLcm() const;
 
     ScMatrixRef CompareMatrix( sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions ) const;
 
@@ -1410,6 +1412,42 @@ struct MinOp
     }
 };
 
+struct Lcm
+{
+    static double init() { return 1.0; }
+    static double calculate(double fx,double fy)
+    {
+        return (fx*fy)/ScInterpreter::ScGetGCD(fx,fy);
+    }
+
+    static double boolValue(
+            MatrixImplType::boolean_block_type::const_iterator it,
+            const MatrixImplType::boolean_block_type::const_iterator& itEnd)
+    {
+        // If the array has at least one false value, the minimum value is 0.
+        it = std::find(it, itEnd, false);
+        return it == itEnd ? 1.0 : 0.0;
+    }
+};
+
+struct Gcd
+{
+    static double init() { return 0.0; }
+    static double calculate(double fx,double fy)
+    {
+        return ScInterpreter::ScGetGCD(fx,fy);
+    }
+
+    static double boolValue(
+            MatrixImplType::boolean_block_type::const_iterator it,
+            const MatrixImplType::boolean_block_type::const_iterator& itEnd)
+    {
+        // If the array has at least one true value, the gcdResult is 1.
+        it = std::find(it, itEnd, true);
+        return it == itEnd ? 0.0 : 1.0;
+    }
+};
+
 template<typename Op>
 class CalcMaxMinValue : public std::unary_function<MatrixImplType::element_block_type, void>
 {
@@ -1469,6 +1507,56 @@ public:
     }
 };
 
+template<typename Op>
+class CalcGcdLcm : public std::unary_function<MatrixImplType::element_block_type,void>
+{
+    double mfval;
+
+public:
+    CalcGcdLcm() : mfval(Op::init()) {}
+
+    double getResult() const { return mfval; }
+
+    void operator() ( const MatrixImplType::element_block_node_type& node )
+    {
+        switch (node.type)
+        {
+            case mdds::mtm::element_numeric:
+                {
+                    typedef MatrixImplType::numeric_block_type block_type;
+                    block_type::const_iterator it = block_type::begin(*node.data);
+                    block_type::const_iterator itEnd = block_type::end(*node.data);
+
+                    for ( ; it != itEnd; ++it)
+                    {
+                        if (*it < 0.0)
+                            mfval = CreateDoubleError(FormulaError::IllegalArgument);
+                        else
+                            mfval = ::rtl::math::approxFloor( Op::calculate(*it,mfval));
+                    }
+                }
+            break;
+            case mdds::mtm::element_boolean:
+                {
+                    typedef MatrixImplType::boolean_block_type block_type;
+                    block_type::const_iterator it = block_type::begin(*node.data);
+                    block_type::const_iterator itEnd = block_type::end(*node.data);
+
+                    mfval = Op::boolValue(it, itEnd);
+                }
+            break;
+            case mdds::mtm::element_empty:
+            case mdds::mtm::element_string:
+                {
+                    mfval = CreateDoubleError(FormulaError::IllegalArgument);
+                }
+            break;
+            default:
+                ;
+        }
+    }
+};
+
 inline double evaluate( double fVal, ScQueryOp eOp )
 {
     if (!rtl::math::isFinite(fVal))
@@ -1890,6 +1978,20 @@ double ScMatrixImpl::GetMinValue( bool bTextAsZero ) const
     return aFunc.getValue();
 }
 
+double ScMatrixImpl::GetGcd() const
+{
+    CalcGcdLcm<Gcd> aFunc;
+    maMat.walk(aFunc);
+    return aFunc.getResult();
+}
+
+double ScMatrixImpl::GetLcm() const
+{
+    CalcGcdLcm<Lcm> aFunc;
+    maMat.walk(aFunc);
+    return aFunc.getResult();
+}
+
 ScMatrixRef ScMatrixImpl::CompareMatrix(
     sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions ) const
 {
@@ -3030,6 +3132,17 @@ double ScFullMatrix::GetMinValue( bool bTextAsZero ) const
     return pImpl->GetMinValue(bTextAsZero);
 }
 
+double ScFullMatrix::GetGcd() const
+{
+    return pImpl->GetGcd();
+}
+
+double ScFullMatrix::GetLcm() const
+{
+    return pImpl->GetLcm();
+}
+
+
 ScMatrixRef ScFullMatrix::CompareMatrix(
     sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions ) const
 {
@@ -3945,6 +4058,18 @@ double ScVectorRefMatrix::GetMinValue(bool bTextAsZero) const
     return mpFullMatrix->GetMinValue(bTextAsZero);
 }
 
+double ScVectorRefMatrix::GetGcd() const
+{
+    const_cast<ScVectorRefMatrix*>(this)->ensureFullMatrix();
+    return mpFullMatrix->GetGcd();
+}
+
+double ScVectorRefMatrix::GetLcm() const
+{
+    const_cast<ScVectorRefMatrix*>(this)->ensureFullMatrix();
+    return mpFullMatrix->GetLcm();
+}
+
 ScMatrixRef ScVectorRefMatrix::CompareMatrix(sc::Compare& rComp, size_t nMatPos, sc::CompareOptions* pOptions) const
 {
     const_cast<ScVectorRefMatrix*>(this)->ensureFullMatrix();