include/AD/numeric/polynom.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef polynomial_h
  26 #define polynomial_h
  27
  28 ////////////////////////////////////////////////////////////////////
  29 // Class Polynomial<X> represents a polynomial of type X.  Type X
  30 // must be a field(in the mathematical sense, not C).
  31 ////////////////////////////////////////////////////////////////////
  32
  33 #include <AD/generic/generic.h>
  34
  35 template <class X>
  36    class Polynomial {
  37
  38       ////////////////////////////////////////////////////////////////////
  39       //  We use a simple array representation storing the coeficients
  40       // of the polynomial.   More storage is needed may be preallocated
  41       // to allow for future expansion.
  42       ////////////////////////////////////////////////////////////////////
  43       int max_degree;  // maximum degree currently allowed
  44       int degree;      // degree of polynomial
  45       X * coef;        // array of coefficients
  46
  47       void norm();     // normalize result
  48
  49       friend int max(int i,int j) { return i > j ? i : j; }
  50       friend int min(int i,int j) { return i < j ? i : j; }
  51       Polynomial(int deg) : degree(deg), coef(new X [deg + 1]) {}
  52
  53    public:
  54
  55       ////////////////////////////////////////////////////////////////
  56       // constructor and destructor
  57       ////////////////////////////////////////////////////////////////
  58
  59       Polynomial() : degree(-1), coef(0) {}
  60       Polynomial(const X& x) : degree(0), coef(new X [1]) { coef[0] = x; }
  61       Polynomial(const Polynomial& p) : coef(0) { *this = p; }
  62      ~Polynomial() { delete [] coef; }
  63
  64       ////////////////////////////////////////////////////////////////
  65       // Assignment
  66       ////////////////////////////////////////////////////////////////
  67       void operator = (const Polynomial&);
  68
  69       ////////////////////////////////////////////////////////////////
  70       // operator () -- evaluate the polynomial at a point
  71       // operator [] -- returns the coefficient of a certain degree
  72       // degree()    -- returns the maximum degree
  73       ////////////////////////////////////////////////////////////////
  74       X operator () (const X&) const;
  75       X& operator [] (int i) const { return coef[i]; }
  76       int deg() const              { return degree; }
  77
  78       void negate();
  79       void operator += (const X&);
  80       void operator -= (const X&);
  81       void operator *= (const X&);
  82       void operator /= (const X&);
  83       void operator += (const Polynomial&);
  84       void operator -= (const Polynomial&);
  85       void operator *= (const Polynomial&);
  86       void operator /= (const Polynomial&);
  87
  88       Polynomial operator - () const;
  89       friend Polynomial operator + (const Polynomial&, const Polynomial&);
  90       friend Polynomial operator - (const Polynomial&, const Polynomial&);
  91       friend Polynomial operator * (const Polynomial&, const Polynomial&);
  92       friend Polynomial operator / (const Polynomial&, const Polynomial&);
  93       friend Polynomial operator % (const Polynomial&, const Polynomial&);
  94       friend Polynomial operator + (const Polynomial&, const X&);
  95       friend Polynomial operator - (const Polynomial&, const X&);
  96       friend Polynomial operator * (const Polynomial&, const X&);
  97       friend Polynomial operator / (const Polynomial&, const X&);
  98       friend Polynomial operator + (const X&, const Polynomial&);
  99       friend Polynomial operator - (const X&, const Polynomial&);
 100       friend Polynomial operator * (const X&, const Polynomial&);
 101
 102       friend Bool operator == (const Polynomial&, const Polynomial&);
 103       friend Bool operator != (const Polynomial&, const Polynomial&);
 104       friend Bool operator == (const Polynomial&, const X&);
 105       friend Bool operator != (const Polynomial&, const X&);
 106       friend Bool operator == (const X&, const Polynomial&);
 107       friend Bool operator != (const X&, const Polynomial&);
 108    };
 109
 110 //////////////////////////////////////////////////////////////////////////
 111 // Implementation of the template methods
 112 //////////////////////////////////////////////////////////////////////////
 113
 114 template <class X>
 115    void Polynomial<X>::norm()
 116    { while (degree > 0 && coef[degree] == 0) --degree; }
 117
 118 template <class X>
 119    void Polynomial<X>::negate()
 120    { for (int i = degree; i >= 0; i--) coef[i] = -coef[i]; }
 121 template <class X>
 122    void Polynomial<X>::operator += (const X& x)
 123    { for (int i = degree; i >= 0; i--) coef[i] += x; norm(); }
 124 template <class X>
 125    void Polynomial<X>::operator -= (const X& x)
 126    { for (int i = degree; i >= 0; i--) coef[i] -= x; norm(); }
 127 template <class X>
 128    void Polynomial<X>::operator *= (const X& x)
 129    { for (int i = degree; i >= 0; i--) coef[i] *= x; norm(); }
 130 template <class X>
 131    void Polynomial<X>::operator /= (const X& x)
 132    { for (int i = degree; i >= 0; i--) coef[i] /= x; norm(); }
 133
 134 template <class X>
 135    void Polynomial<X>::operator += (const Polynomial<X>& p)
 136    { }
 137
 138 template <class X>
 139    void Polynomial<X>::operator -= (const Polynomial<X>& p)
 140    { for (int i = degree; i >= 0; i--) coef[i] -= p[i]; norm(); }
 141
 142 template <class X>
 143    void Polynomial<X>::operator *= (const Polynomial<X>& p)
 144    {  Polynomial<X> r(this->deg() + p.deg());
 145       { for (int i = r.deg(); i >= 0; i--) r[i] = 0; }
 146       { for (int i = degree; i >= 0; i--)
 147             for (int j = p.deg(); j >= 0; j--)
 148                coef[i+j] += (*this)[i] * p[j];
 149       }
 150       *this = r;
 151       norm();
 152    }
 153
 154 template <class X>
 155    Polynomial<X> Polynomial<X>::operator - () const
 156    {  Polynomial<X> r(degree);
 157       for (int i = degree; i >= 0; i--) r[i] = -coef[i];
 158       return r;
 159    }
 160 template <class X>
 161    Polynomial<X> operator + (const Polynomial<X>& p, const Polynomial<X>& q)
 162    {  Polynomial<X> r(max(p.deg(),q.deg()));
 163    }
 164 template <class X>
 165    Polynomial<X> operator - (const Polynomial<X>& p, const Polynomial<X>& q)
 166    {}
 167 template <class X>
 168    Polynomial<X> operator * (const Polynomial<X>& p, const Polynomial<X>& q)
 169    {}
 170 template <class X>
 171    Polynomial<X> operator + (const Polynomial<X>& p, const X& x)
 172    {}
 173 template <class X>
 174    Polynomial<X> operator - (const Polynomial<X>& p, const X& x)
 175    {}
 176 template <class X>
 177    Polynomial<X> operator * (const Polynomial<X>& p, const X& x)
 178    {}
 179 template <class X>
 180    Polynomial<X> operator / (const Polynomial<X>& p, const X& x)
 181    {}
 182 template <class X>
 183    Polynomial<X> operator + (const X& x, const Polynomial<X>& p)
 184    {}
 185 template <class X>
 186    Polynomial<X> operator - (const X& x, const Polynomial<X>& p)
 187    {}
 188
 189 #endif