polynomials.h

Go to the documentation of this file.

/*
  This is polynomials.h

  Copyright (C) 2004,2005 Fokko du Cloux
  part of the Atlas of Lie Groups and Representations

  For license information see the LICENSE file
*/

#ifndef POLYNOMIALS_H  /* guard against multiple inclusions */
#define POLYNOMIALS_H

#include "polynomials_fwd.h"

#include <limits>
#include <vector>
#include <iostream>

namespace atlas {

namespace polynomials {

/******** constant declarations *********************************************/


  const Degree MinusOne = ~ Degree(0); // -1 as unsigned, the degree of Zero



/******** function declarations *********************************************/


template<typename C>
  bool compare(const Polynomial<C>&, const Polynomial<C>&); // lex ordering

// basic operations which test for overflow/underflow, assuming |C| is unsigned
template<typename C>
  void safeAdd(C&, C); // version of |operator+=| testing for overflow

template<typename C>
  void safeDivide(C&, C); // version of |operator/=| testing for divisibility

template<typename C>
  void safeProd(C&, C); // version of |operator*=| testing for overflow

template<typename C>
void safeSubtract(C&, C);// version of |operator-=| testing for underflow


/******** type definitions **************************************************/


template<typename C> class Polynomial
{
  std::vector<C> d_data;

 public:

// constructors and destructors
  Polynomial() : d_data() {} // zero polynomial
  explicit Polynomial(C c);  // constant polynomial, |c==0| handled correctly
  Polynomial(Degree d, C c); // initialised to $cX^d$ (with |c!=0|)
  Polynomial(Degree d,const Polynomial& Q); // initialised to $X^d Q$

// copy, assignment (default will do) and swap

template <typename U>
  Polynomial(const Polynomial<U>& src) : d_data(src.begin(),src.end()) { }

  void swap(Polynomial& other) { d_data.swap(other.d_data); }

// accessors
  const C& operator[] (Degree i) const; // get coefficient $X^i$
  const C coef (Degree i) const { return i>=d_data.size() ? C(0) : d_data[i]; }

  bool operator== (const Polynomial& q) const { return d_data == q.d_data; }
  bool operator!= (const Polynomial& q) const { return d_data != q.d_data; }

  bool operator< (const Polynomial& q) const { return d_data < q.d_data; }

  typename std::vector<C>::const_iterator begin() const
  { return d_data.begin();}
  typename std::vector<C>::const_iterator end() const { return d_data.end();}

  Degree degree() const { return d_data.size()-1; }
  Degree size() const { return d_data.size(); }

  bool isZero() const { return size() == 0; } // because of reduction
  bool multi_term () const; // whether more than one term is nonzero (printing)

  // write polynomial as $(1+cX)Q+rX^d$, and return $r$
  C up_remainder(C c, Degree d) const; // assumes $d\geq degree()$

// manipulators
  C& operator[] (Degree j); // non-const version of above

  Polynomial& operator+= (const Polynomial& q);

  Polynomial& operator-= (const Polynomial& q);

  Polynomial& subtract_from (const Polynomial& p); // *this = p - *this

  Polynomial& operator*= (C);
  Polynomial& operator/= (C);
  Polynomial operator* (C c) const { return Polynomial (*this)*=c; }

  Polynomial operator* (const Polynomial& q) const;
  Polynomial& operator*= (const Polynomial& q)
    { operator*(q).swap(*this); return *this; }
  Polynomial operator+ (const Polynomial& q) const
    { // avoid requiring reallocation during addition
      return d_data.size()>=q.d_data.size()
    ? Polynomial(*this)+=q : Polynomial(q)+=*this;
    }
  Polynomial operator- (const Polynomial& q) const
    { // avoid requiring reallocation during addition
      return d_data.size()>=q.d_data.size()
    ? Polynomial(*this)-=q : (Polynomial(q)*=C(-1))+=*this;
    }
  Polynomial operator- () const { return Polynomial(*this)*= C(-1); }

  // as |up_remainder| above, but also change polynomial into quotient $Q$
  C factor_by(C c, Degree d); // assumes $d\geq degree()$

  std::ostream& print(std::ostream& strm, const char* x) const;

protected:
  void resize (Degree d) { d_data.resize(d,C(0)); }
  void adjustSize(); // shrink |d_data| to make leading coefficient nonzero

 }; // |template<typename C> class Polynomial|

/*
  The following class template assumes |C| is an _unsigned_ integer type,
  for which |std::numeric_limits<C>| is defined; it then provides safe
  versions of shifted additive operations
 */
template <typename C>
  class Safe_Poly : public Polynomial<C>
{
  typedef Polynomial<C> base;
 public:
  Safe_Poly() : base() {} // zero polynomial
  explicit Safe_Poly(Degree d, C c) : base(d,c) {}

  // unlike |operator+| etc., the following test for negative coefficients
  void safeAdd(const Safe_Poly& p, Degree d, C c); // *this += c*q^d*p
  void safeAdd(const Safe_Poly& p, Degree d = 0);  // *this += q^d*p
  void safeDivide(C c);  // *this = *this/c
  void safeQuotient(Degree d = 0);  // *this = (*this + mq^d)/(q+1)

  void safeSubtract(const Safe_Poly& p, Degree d, C c);
  void safeSubtract(const Safe_Poly& p, Degree d = 0 );

}; // |template <typename C> class Safe_Poly|

} // |namespace polynomials|

} // |namespace atlas|

#include "polynomials_def.h"

#endif