Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
Factors.hpp
1
2
3 #ifndef _FACTORS_HPP_
4 #define _FACTORS_HPP_
5
6 #include <iostream>
7 #include <utility>
8 #include "../Ring/BPASRing.hpp"
9 #include "../ExpressionTree/ExpressionTree.hpp"
10 #include "../Utils/TemplateHelpers.hpp"
11
12 /**
13  * A Factor is a pair of a BPASRing element and an integer exponent.
14  * Template Ring should derive from BPASRing.
15  */
16 template <class Ring>
17 class Factor : public std::pair<Ring, int>, public ExpressionTreeConvert, private Derived_from<Ring, BPASRing<Ring>> {
18
19 public:
20  /**
21  * Construct an empty factor.
22  */
23  Factor() : std::pair<Ring,int>() {}
24
25  /**
26  * Construct a factor from a Ring element and an exponent.
27  * @param r the Ring element
28  * @param e the exponent
29  */
30  Factor(const Ring& r, int e) : std::pair<Ring,int>(r,e) {}
31
32  /**
33  * Move-construct a factor from a Ring element and an exponent.
34  * @param r the Ring element
35  * @param e the exponent
36  */
37  Factor(Ring&& r, int e) : std::pair<Ring,int>(r,e) {}
38
39  /**
40  * Construct a Factor from a std::pair of a Ring element and integer exponent.
41  * @param p the pair
42  */
43  Factor(const std::pair<Ring, int>& p) : std::pair<Ring, int>(p) {}
44
45  /**
46  * Equality comparison operator.
47  * @param f the Factor to compare
48  * @return true iff *this == f.
49  */
50  bool operator==(const Factor<Ring>& f) {
51  return (this->first == f.first && this->second == f.second);
52  }
53
54  /**
55  * Inequality comparison operator.
56  * @param f the Factor to compare
57  * @return true iff *this != f.
58  */
59  bool operator!=(const Factor<Ring>& f) {
60  return (this->first != f.first || this->second != f.second);
61  }
62
63  /**
64  * Output operator, defines a to string conversion.
65  * @param out the output stream
66  * @param f the Factor
67  */
68  friend std::ostream& operator<<(std::ostream& out, const Factor<Ring>& f) {
69  out << "[" << f.first << ", " << f.second << "]";
70  return out;
71
72  }
73
74  /**
75  * Convert the Factor to an ExpressionTree.
76  * @return the ExpressionTree
77  */
79  std::vector<ExpressionTree> trees;
80  trees.push_back(this->first.convertToExpressionTree());
81  trees.emplace_back(new ExprTreeNode(this->second));
82
83  return ExpressionTree(trees);
84  }
85 };
86
87 /**
88  * A simple data structure for encapsulating a collection of Factor elements.
89  * Factors are encoded as a list of Factor items. That is, a pair of a Ring
90  * element and an integer representing its exponent. This list of Factor elements
91  * is augmented by an invertible element of the ring (if one such exists) as a constant
92  * multiplicative factor.
93  */
94 template <class Ring>
95 class Factors : public ExpressionTreeConvert, private Derived_from<Ring, BPASRing<Ring>> {
96
97 private:
98  Ring u;
99  std::vector<Factor<Ring>> facts;
100
101 public:
102
103  /**
104  * Default constructor. Constructs an empty list of factors.
105  */
106  Factors();
107
108  /**
109  * Construct a Factors with a single factor.
110  * @param r the Ring element
111  */
112  Factors(const Ring& r);
113
114  /**
115  * Create a Factors from a list of Ring elements. Each factor is assumed
116  * to have an exponent of 1.
117  * @param v the vector of Ring elements.
118  */
119  Factors(const std::vector<Ring>& v);
120
121  /**
122  * Create a Factors from a list of Ring elements and a parallel array of integers
123  * as exponents for each ring element.
124  * @param v the vector of Ring elements
125  * @param e the parallel vector of integer exponents
126  */
127  Factors(const std::vector<Ring>& v, const std::vector<int>& e);
128
129  /**
130  * Create a Factors from a list of ring elements, a parallel array of integers
131  * as exponents for each ring element, and a ring element representing the
132  * invertible unit of the Ring.
133  * @param v the vector of Ring elements
134  * @param e the parallel vector of integer exponents
135  * @param u the multicative factor
136  */
137  Factors(const std::vector<Ring>& v, const std::vector<int>& e, const Ring& u);
138
139  /**
140  * Create a Factors from a vector of Factor elements.
141  * @param v the vector of Factor elements.
142  */
143  Factors(const std::vector<Factor<Ring>>& v);
144
145  /**
146  * Create a Factors from a vector of Factor elements and an invertible Ring element.
147  * @param v the vector of Factor elements.
148  * @param u the invertible Ring element.
149  */
150  Factors(const std::vector<Factor<Ring>>& v, const Ring& u);
151
152  /**
153  * Copy consturctor.
154  * @param f the Factors to copy.
155  */
156  Factors(const Factors& f);
157
158  /**
159  * Move consturctor.
160  * @param f the Factors to move.
161  */
162  Factors(Factors&& f);
163
164  /**
165  * Destructor.
166  */
167  ~Factors();
168
169  /**
170  * Set the invertible Ring element.
171  * @param r the new invertible Ring element.
172  */
173  inline void setRingElement(const Ring& r) {
174  u = r;
175  }
176
177  /**
178  * Get the invertible Ring element.
179  * @return the invertible Ring element of this Factors
180  */
181  inline Ring ringElement() const {
182  return u;
183  }
184
185  /**
186  * Multiply this Factors invertible Ring element by another Ring element.
187  * @param r the other Ring element.
188  */
189  inline void multiplyRingElement(const Ring& r) {
190  u *= r;
191  }
192
193  /**
194  * Get the list of Factor elements.
195  * @return the vector of Factor elements.
196  */
197  inline std::vector<Factor<Ring>> factors() const {
198  return facts;
199  }
200
201  /**
202  * Get the i'th Factor.
203  * @param i the index
204  * @return the Factor at index i
205  */
206  inline Factor<Ring> factor(int i) const {
207  if (i < facts.size())
208  return facts[i];
209  else {
210  std::cerr << "BPAS: error, i exceeds array bounds of list of factors" << std::endl;
211  exit(1);
212  }
213  }
214
215  /**
216  * Set the list of Factor elements.
217  * @param v the vector of Factor elements.
218  */
219  inline void setFactors(const std::vector<Factor<Ring>>& v) {
220  facts = v;
221  }
222
223  /**
224  * A Factor to the list of Factor elements.
225  * @param f the Factor to add.
226  */
227  inline void addFactor(const Factor<Ring>& f) {
228  if (f.first.isOne()) {
229  return;
230  }
231  for (int i = 0; i < facts.size(); ++i) {
232  if (f.first == facts[i].first) {
233  facts[i].second += f.second;
234  return;
235  }
236  }
237  facts.push_back(f);
238  }
239
240  /**
241  * Add a Ring element and its corresponding exponent as a Factor.
242  * @param r the ring element.
243  * @param e the exponent
244  */
245  inline void addFactor(const Ring& r, int e) {
246  if (r.isOne()) {
247  return;
248  }
249  for (int i = 0; i < facts.size(); ++i) {
250  if (r == facts[i].first) {
251  facts[i].second += e;
252  return;
253  }
254  }
255  facts.emplace_back(r, e);
256  }
257
258  /**
259  * Combine another Factors' list of Factor elements with this Factors. This does
260  * not modify the invertible ring element.
261  * @param f the Factors object
262  */
263  inline void addFactors(const Factors<Ring> f) {
264  for (int i = 0; i < f.facts.size(); ++i) {
266  }
267  }
268
269  /**
270  * Get the number of Factor elements in this Factors object.
271  * @return the number of Factor elements.
272  */
273  inline size_t size() const {
274  return facts.size();
275  }
276
277  /**
278  * Copy assignment.
279  * @param f the Factors to copy from.
280  */
281  Factors<Ring>& operator=(const Factors<Ring>& f);
282
283  /**
284  * Move assignment.
285  * @param f the Factors to move from.
286  */
287  Factors<Ring>& operator=(Factors<Ring>&& f);
288
289  /**
290  * Equality testing for Factors. Does NOT check if, when factors are distributed,
291  * that the underlying elements are the same. Only if the factoirzation is the same.
292  * @param f the Factors to test equality with.
293  * @return true iff all factors are equal in both Factors.
294  */
295  bool operator==(const Factors<Ring>& f) const;
296
297  /**
298  * Inequality testing for Factors. Does NOT check if, when factors are distributed,
299  * that the underlying elements are the same. Only if the factoirzation is the same.
300  * @param f the Factors to test equality with.
301  * @return false iff all factors are equal in both Factors.
302  */
303  inline bool operator!=(const Factors<Ring>& f) const {
304  return !(*this == f);
305  }
306
307  /**
308  * Indexing operator.
309  * @param idx the index
310  * @return the Factor at index idx.
311  */
312  inline Factor<Ring>& operator[](size_t idx) {
313  return facts[idx];
314  }
315
316  /**
317  * Output operator. Defines a to string conversion.
318  * @param out the output stream
319  * @param f the Factors to output
320  */
321  friend std::ostream& operator<<(std::ostream& out, const Factors<Ring>& f) {
322  out << "[" << f.u << ", [";
323
324
325  for (int i = 0; i < f.facts.size(); ++i) {
326  out << f.facts[i];
327  if (i + 1 < f.facts.size()) {
328  out << ", ";
329  }
330  }
331
332  out << "]]";
333  return out;
334  }
335
336  /**
337  * Convert the Factors object to an ExpressionTree.
338  * @return the ExpressionTree encoding the Factors.
339  */
341  std::vector<ExpressionTree> trees;
342  ExpressionTree t;
343  t.fromVector(facts);
344
345  trees.push_back(u.convertToExpressionTree());
346  trees.push_back(t);
347
348  return ExpressionTree(trees);
349  }
350
351 };
352
353
354 //Include the implementation
355 #include "Factors_impl.hxx"
356
357 #endif
size_t size() const
Get the number of Factor elements in this Factors object.
Definition: Factors.hpp:273
std::vector< Factor< Ring > > factors() const
Get the list of Factor elements.
Definition: Factors.hpp:197
Factor< Ring > factor(int i) const
Get the i&#39;th Factor.
Definition: Factors.hpp:206
void setFactors(const std::vector< Factor< Ring >> &v)
Set the list of Factor elements.
Definition: Factors.hpp:219
void addFactor(const Factor< Ring > &f)
A Factor to the list of Factor elements.
Definition: Factors.hpp:227
Factor(const std::pair< Ring, int > &p)
Construct a Factor from a std::pair of a Ring element and integer exponent.
Definition: Factors.hpp:43
STL namespace.
Factor()
Construct an empty factor.
Definition: Factors.hpp:23
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
void addFactors(const Factors< Ring > f)
Combine another Factors&#39; list of Factor elements with this Factors.
Definition: Factors.hpp:263
bool operator!=(const Factor< Ring > &f)
Inequality comparison operator.
Definition: Factors.hpp:59
A Factor is a pair of a BPASRing element and an integer exponent.
Definition: Factors.hpp:17
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
ExpressionTree convertToExpressionTree() const
Convert the Factors object to an ExpressionTree.
Definition: Factors.hpp:340
Factor(const Ring &r, int e)
Construct a factor from a Ring element and an exponent.
Definition: Factors.hpp:30
void setRingElement(const Ring &r)
Set the invertible Ring element.
Definition: Factors.hpp:173
void fromVector(const std::vector< ExpTreeConvert > &ringVec)
Fill this expression tree with the vector of BPASRing elements specified.
Definition: ExpressionTree.hpp:180
ExpressionTree convertToExpressionTree() const
Convert the Factor to an ExpressionTree.
Definition: Factors.hpp:78
void multiplyRingElement(const Ring &r)
Multiply this Factors invertible Ring element by another Ring element.
Definition: Factors.hpp:189
bool operator!=(const Factors< Ring > &f) const
Inequality testing for Factors.
Definition: Factors.hpp:303
Factor(Ring &&r, int e)
Move-construct a factor from a Ring element and an exponent.
Definition: Factors.hpp:37
ExprTreeNode is a single node in the bianry tree of an ExpressionTree.
Definition: ExprTreeNode.hpp:76
Factor< Ring > & operator[](size_t idx)
Indexing operator.
Definition: Factors.hpp:312
An interface defining conversion of a class to an ExpressionTree.
Definition: ExpressionTree.hpp:195
bool operator==(const Factor< Ring > &f)
Equality comparison operator.
Definition: Factors.hpp:50
Ring ringElement() const
Get the invertible Ring element.
Definition: Factors.hpp:181
void addFactor(const Ring &r, int e)
Add a Ring element and its corresponding exponent as a Factor.
Definition: Factors.hpp:245