Basic Polynomial Algebra Subprograms (BPAS)  v. 1.791
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  /**
260  * Add a Ring element and its corresponding exponent as a Factor.
261  * @param r the ring element.
262  * @param e the exponent
263  */
264  inline void addFactor(Ring&& r, int e) {
265  if (r.isOne()) {
266  return;
267  }
268  for (int i = 0; i < facts.size(); ++i) {
269  if (r == facts[i].first) {
270  facts[i].second += e;
271  return;
272  }
273  }
274  facts.emplace_back(r, e);
275  }
276 
277  /**
278  * Combine another Factors' list of Factor elements with this Factors. This does
279  * not modify the invertible ring element.
280  * @param f the Factors object
281  */
282  inline void addFactors(const Factors<Ring> f) {
283  for (int i = 0; i < f.facts.size(); ++i) {
284  this->addFactor(f.facts[i]);
285  }
286  }
287 
288  /**
289  * Get the number of Factor elements in this Factors object.
290  * @return the number of Factor elements.
291  */
292  inline size_t size() const {
293  return facts.size();
294  }
295 
296  /**
297  * Copy assignment.
298  * @param f the Factors to copy from.
299  */
300  Factors<Ring>& operator=(const Factors<Ring>& f);
301 
302  /**
303  * Move assignment.
304  * @param f the Factors to move from.
305  */
306  Factors<Ring>& operator=(Factors<Ring>&& f);
307 
308  /**
309  * Equality testing for Factors. Does NOT check if, when factors are distributed,
310  * that the underlying elements are the same. Only if the factoirzation is the same.
311  * @param f the Factors to test equality with.
312  * @return true iff all factors are equal in both Factors.
313  */
314  bool operator==(const Factors<Ring>& f) const;
315 
316  /**
317  * Inequality testing for Factors. Does NOT check if, when factors are distributed,
318  * that the underlying elements are the same. Only if the factoirzation is the same.
319  * @param f the Factors to test equality with.
320  * @return false iff all factors are equal in both Factors.
321  */
322  inline bool operator!=(const Factors<Ring>& f) const {
323  return !(*this == f);
324  }
325 
326  /**
327  * Indexing operator.
328  * @param idx the index
329  * @return the Factor at index idx.
330  */
331  inline Factor<Ring>& operator[](size_t idx) {
332  return facts[idx];
333  }
334 
335  /**
336  * Output operator. Defines a to string conversion.
337  * @param out the output stream
338  * @param f the Factors to output
339  */
340  friend std::ostream& operator<<(std::ostream& out, const Factors<Ring>& f) {
341  out << "[" << f.u << ", [";
342 
343 
344  for (int i = 0; i < f.facts.size(); ++i) {
345  out << f.facts[i];
346  if (i + 1 < f.facts.size()) {
347  out << ", ";
348  }
349  }
350 
351  out << "]]";
352  return out;
353  }
354 
355  /**
356  * Convert the Factors object to an ExpressionTree.
357  * @return the ExpressionTree encoding the Factors.
358  */
360  std::vector<ExpressionTree> trees;
361  ExpressionTree t;
362  t.fromVector(facts);
363 
364  trees.push_back(u.convertToExpressionTree());
365  trees.push_back(t);
366 
367  return ExpressionTree(trees);
368  }
369 
370 };
371 
372 
373 //Include the implementation
374 #include "Factors_impl.hxx"
375 
376 #endif
size_t size() const
Get the number of Factor elements in this Factors object.
Definition: Factors.hpp:292
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:282
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:359
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 addFactor(Ring &&r, int e)
Add a Ring element and its corresponding exponent as a Factor.
Definition: Factors.hpp:264
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:322
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:331
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