polynomial.h 5.51 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
#include <utility>
6
#include "./common.h"
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
7
#include "./monomial.h"
8
#include "./givaro_wrapper.h"
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
9

10 11
namespace tinygb {

12
class Polynomial {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
13
 public:
14
  typedef std::pair<Monomial, GivaroWrapper> Term;
15

16
  Polynomial() {
17
      terms_ = std::list<Term>();
SPAENLEHAUER Pierre-Jean's avatar
doc  
SPAENLEHAUER Pierre-Jean committed
18
    }
19 20
  explicit Polynomial(const std::list<Term>& terms_)
    : terms_(terms_) {}
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
21

22
  const std::list<Term>& terms() const {
23
    return terms_;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
24 25
  }

26 27 28 29
  // Put the list of terms in standard form. Depends on the monomial ordering.
  // The list is ordered from smallest to largest
  // TODO(pj): leading monomial should be first
  void Normalize();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
30

31 32
  void SetToZero() {
    terms_.clear();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
33
  }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
34

35 36
  void insert(Monomial m, GivaroWrapper e) {
    terms_.push_back(std::pair<Monomial, GivaroWrapper>(m, e));
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
37
  }
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
38

39 40 41
  // Assumes that the polynomial's list of terms is normalized
  const Monomial& LeadingMonomial() const {
    assert(!terms_.back().second.is_zero());
42
    return terms_.back().first;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
43 44
  }

45
  const GivaroWrapper& LeadingCoefficient() const {
46
    return terms_.back().second;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
47 48
  }

49
  void DivideByLeadingCoefficient();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
50

51 52 53
  unsigned Degree() const {
    // TODO(pj): Extend for non-degree orderings.
    return LeadingMonomial().Degree();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
54 55
  }

56 57 58 59 60 61 62 63 64 65 66
  // Reduces leading monomial by the polynomial given.
  // Returns true if leading monomial is divisible by the leading monomial of
  // the argument. When this function returns false, then nothing has been
  // modified.
  // Assumes that terms_ is normalized.
  bool TopReductionBy(const Polynomial &);

  // Returns true if the leading monomial is divisible by the leading monomial
  // of the argument.
  // Assumes that terms_ is normalized.
  bool IsTopReducibleBy(const Polynomial &) const;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
67

68 69 70 71 72
  Polynomial operator*(const Monomial&) const;
  void operator+=(const Polynomial&);
  void operator-=(const Polynomial&);
  void operator*=(const GivaroWrapper&);
  void operator/=(const GivaroWrapper&);
73
  void Print(std::ostream& out) const;
74
  inline bool operator<(const Polynomial& P) const;
75

76
  friend std::ostream& operator<<(std::ostream&, const Polynomial&);
77

78 79 80 81
 private:
  // Adds coefficients of consecutive terms if they share the same monomials.
  // Useful for adding polynomials. Do not use if terms_ is not sorted.
  void CombineMonomials();
82 83 84 85
  bool IsEmpty() const {
    return terms_.empty();
  }
  // Removes terms with coefficient 0
86
  void RemoveZeroTerms();
87 88

  std::list<Term> terms_;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
89
};
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
90

91
void Polynomial::RemoveZeroTerms() {
92
  for (auto it = terms_.begin(); it != terms_.end(); ++it) {
93
    while (it != terms_.end() && it->second == GivaroWrapper(0))
94 95 96 97
      it = terms_.erase(it);
  }
}

98 99
void Polynomial::CombineMonomials() {
  typename std::list<std::pair<Monomial, GivaroWrapper> >::iterator it2;
100 101 102 103
  for (auto it1 = terms_.begin(); it1 != terms_.end();) {
    it2 = it1;
    ++it1;
    if (it1 == terms_.end()) {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
104
      break;
105 106
    } else if (it1->first == it2->first) {
      it1->second += it2->second;
107
      terms_.erase(it2);
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
108 109 110 111
    }
  }
}

112 113 114
void Polynomial::DivideByLeadingCoefficient() {
  GivaroWrapper leading_coefficient = terms_.back().second;
  assert(leading_coefficient != GivaroWrapper(0));
115
  leading_coefficient.inv();
116
  if (leading_coefficient == GivaroWrapper(1)) return;
117
  for (auto& it : terms_)
118
    it.second *= leading_coefficient;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
119 120
}

121
void Polynomial::Normalize() {
122
  terms_.sort();
123 124
  CombineMonomials();
  RemoveZeroTerms();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
125 126
}

127
bool Polynomial::TopReductionBy(const Polynomial &g) {
128 129 130 131 132 133
  assert(!g.IsEmpty());
  if (IsEmpty()) return false;
  if (!LeadingMonomial().IsDivisibleBy(g.LeadingMonomial())) return false;
  Polynomial reductor = g*(LeadingMonomial()/g.LeadingMonomial());
  reductor.DivideByLeadingCoefficient();
  reductor *= LeadingCoefficient();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
134 135 136 137
  operator-=(reductor);
  return true;
}

138
bool Polynomial::IsTopReducibleBy(const Polynomial &g) const {
139 140 141
  assert(!g.IsEmpty());
  if (IsEmpty()) return false;
  return LeadingMonomial().IsDivisibleBy(g.LeadingMonomial());
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
142 143
}

144
Polynomial Polynomial::operator*(const Monomial &m) const {
145
  Polynomial R;
146
  R.terms_.insert(R.terms_.begin(), this->terms_.begin(), this->terms_.end());
147 148
  for (auto& it : R.terms_)
    it.first *= m;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
149 150 151
  return R;
}

152
void Polynomial::operator+=(const Polynomial &P) {
153 154 155 156
  std::list<Term> tmp_terms = P.terms_;
  terms_.merge(tmp_terms);
  CombineMonomials();
  RemoveZeroTerms();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
157 158
}

159
void Polynomial::operator*=(const GivaroWrapper &e) {
160 161
  for (auto& it : terms_)
    it.second *= e;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
162 163
}

164
void Polynomial::operator/=(const GivaroWrapper& e) {
165 166
  for (auto& it : terms_)
    it.second /= e;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
167 168
}

169
void Polynomial::operator-=(const Polynomial& P) {
170 171 172 173 174 175
  std::list<Term> tmp_terms = P.terms_;
  for (auto& it : tmp_terms)
    it.second.neg();
  terms_.merge(tmp_terms);
  CombineMonomials();
  RemoveZeroTerms();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
176 177
}

178
void Polynomial::Print(std::ostream& o) const {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
179
  for (const auto& it : terms_) {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
180
    o << it.second << " ";
181
    it.first.Print(o);
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
182 183 184 185 186
    o << std::endl;
  }
  o << ";";
}

187
std::ostream& operator<<(std::ostream& o, const Polynomial& P) {
188
  if (P.IsEmpty()) {
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
189 190 191
    o << "0";
    return o;
  }
192
  // TODO(pj) : improve printing of polynomial and monomial
193
  typename std::list<typename Polynomial::Term>::const_iterator it = P.terms_.begin();
194
  if (it == P.terms_.end())
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
195
    return o;
196
  if (it->second != GivaroWrapper(0))
197
    o << it->second << " " << it->first;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
198
  ++it;
199
  for (; it != P.terms_.end() ; ++it)
200
    if (it->second != GivaroWrapper(0))
201
      o << "+" << it->second << " " <<  it->first;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
202 203 204
  return o;
}

205
inline bool Polynomial::operator<(const Polynomial& P) const {
206
  return LeadingMonomial() < P.LeadingMonomial();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
207
}
208
}  // namespace tinygb
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
209

SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
210
#endif  // POLYNOMIAL_H_