// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// FREE SOURCE CODE
// http://www.magic-software.com/License/free.pdf

#ifndef MGCPOLYNOMIAL_H
#define MGCPOLYNOMIAL_H



class MgcPolynomial
{
public:
    // construction and destruction
    MgcPolynomial (int iDegree = -1);
    MgcPolynomial (const MgcPolynomial& rkPoly);
    ~MgcPolynomial ();

    // assignment
    MgcPolynomial& operator= (const MgcPolynomial& rkPoly);

    // coefficient access
    void SetDegree (int iDegree);
    int GetDegree () const;
    float& operator[] (int i) const;

    // evaluation
    float operator() (float fT) const;

    // derivation
    MgcPolynomial GetDerivative () const;

    // inversion ( invpoly[i] = poly[degree-i] for 0 <= i <= degree )
    MgcPolynomial GetInversion () const;

    // arithmetic
    MgcPolynomial operator+ (const MgcPolynomial& rkPoly) const;
    MgcPolynomial operator- (const MgcPolynomial& rkPoly) const;
    MgcPolynomial operator* (const MgcPolynomial& rkPoly) const;
    MgcPolynomial operator* (float fScalar) const;
    MgcPolynomial operator- () const;
    friend MgcPolynomial operator* (float fScalar,
        const MgcPolynomial& rkPoly);

    // root finding
    static int DIGITS_ACCURACY;
    static float ZERO_TOLERANCE;
    bool Bisection (float fXMin, float fXMax, float& rfRoot) const;
    void GetRootsOnInterval (float fXMin, float fXMax,
        int& riCount, float* afRoot) const;
    void GetAllRoots (int& riCount, float* afRoot) const;

    float GetRootBound () const;  // real roots must be in [-bound,bound]
    bool AllRealPartsNegative () const;
    bool AllRealPartsPositive () const;

    // low-degree root finding (degree must be correct, must be monic poly)
    bool RootsDegree2 (int& riCount, float afRoot[2]) const;
    bool RootsDegree3 (int& riCount, float afRoot[3]) const;
    bool RootsDegree4 (int& riCount, float afRoot[4]) const;

    // solve A*r^3 + B*r = C where A > 0 and B > 0
    float SpecialCubeRoot (float fA, float fB, float fC);

protected:
    int m_iDegree;
    float* m_afCoeff;

    // root finding
    static const float ms_fInvLog2;
    static const float ms_fLog10;
    static const float ms_fThird;
    static const float ms_fSqrt3;
    static const float ms_fTwentySeventh;
    static bool AllRealPartsNegative (int iDegree, float* afCoeff);

    // TO DO.  Sturm sequences for counting roots on interval.
};

#endif
