polynomial.h 2.87 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 "./abstract_polynomial.h"
9
#include "finite_field_arithmetic/givaro_wrapper.h"
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
10

11 12
namespace tinygb {

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

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

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

27 28 29 30
  // 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
31

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

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

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

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

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

52 53 54
  unsigned Degree() const {
    // TODO(pj): Extend for non-degree orderings.
    return LeadingMonomial().Degree();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
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.
67
  inline bool IsTopReducibleBy(const Polynomial &) const;
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
68

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

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

79 80 81 82
 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();
83 84 85 86
  bool IsEmpty() const {
    return terms_.empty();
  }
  // Removes terms with coefficient 0
87
  void RemoveZeroTerms();
88 89

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

92
inline bool Polynomial::IsTopReducibleBy(const Polynomial &g) const {
93 94 95
  assert(!g.IsEmpty());
  if (IsEmpty()) return false;
  return LeadingMonomial().IsDivisibleBy(g.LeadingMonomial());
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
96 97
}

98 99
inline 
bool Polynomial::operator<(const Polynomial& P) const {
100
  return LeadingMonomial() < P.LeadingMonomial();
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
101
}
102

103
}  // namespace tinygb
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
104

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