polynomial.h 2.76 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
  // 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.
66
  inline 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
inline bool Polynomial::IsTopReducibleBy(const Polynomial &g) const {
92 93 94
  assert(!g.IsEmpty());
  if (IsEmpty()) return false;
  return LeadingMonomial().IsDivisibleBy(g.LeadingMonomial());
SPAENLEHAUER Pierre-Jean's avatar
SPAENLEHAUER Pierre-Jean committed
95 96
}

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

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

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