polynomial.h 1.78 KB
Newer Older
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
1 2
#ifndef POLYNOMIAL_H_
#define POLYNOMIAL_H_
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
3 4

#include <list>
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
5 6 7
#include <utility>
#include "./param.h"
#include "./monomial.h"
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
8

9 10
namespace tinygb {

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
11 12 13 14
template<class T>
class polynomial;

template<class T>
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
15
std::ostream& operator<<(std::ostream &o, const polynomial<T> &p);
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
16 17

template<class T>
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
18
class polynomial {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
19
  void combine_LM();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
20
  std::list<std::pair<monomial, T> > vp;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
21

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
22 23 24
 public:
  polynomial() {
      vp = std::list<std::pair<monomial, T> >();
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
25
    }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
26

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
27 28 29 30
  explicit polynomial(const std::list<std::pair<monomial, T> >& _vp)
    : vp(_vp) {}

  const std::list<std::pair<monomial, T> >& get_vp() const {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
31 32 33
    return vp;
  }

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
34 35 36
  void normalize();

  void clear() {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
37 38
    vp.clear();
  }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
39 40 41

  void insert(monomial m, T e) {
    vp.push_back(std::pair<monomial, T>(m, e));
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
42
  }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
43 44

  const monomial& LM() const {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
45 46 47 48
    assert(!vp.back().second.is_zero());
    return vp.back().first;
  }

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
49
  const T& LC() const {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
50 51 52 53
    return vp.back().second;
  }

  void set_monic();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
54 55

  unsigned size() const {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
56 57
    return vp.size();
  }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
58 59

  bool is_zero() const {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
60 61 62
    return vp.empty();
  }

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
63 64
  unsigned degree() const {
    // TODO(pj): extends for non-degree orderings
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
65 66 67 68 69 70 71
    return LM().degree();
  }

#ifdef BILIN
  unsigned degree_bilin() const;
#endif

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
72 73
  bool topred(const polynomial &g);
  bool istopred(const polynomial &g) const;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
74 75 76 77 78 79 80 81 82
  T coeff(const monomial& m) const;

  /****************************************/

  polynomial<T> operator*(const monomial&) const;
  void operator+=(const polynomial<T>&);
  void operator-=(const polynomial<T>&);
  void operator*=(const T&);
  void operator/=(const T&);
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
83 84

  void print(std::ostream& out) const;
85 86
  inline bool operator<(const polynomial<T>& P) const;

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
87 88
  friend std::ostream& operator<< <T>(std::ostream&, const polynomial<T>&);
};
89
}  // namespace tinygb
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
90 91

#include "polynomial.tpp"
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
92
#endif  // POLYNOMIAL_H_