All Classes Functions Friends
triangularset.h
1 #ifndef _TRIANGULARSET_H_
2 #define _TRIANGULARSET_H_
3 
4 #include "Polynomial/mpolynomial.h"
5 
6 template <class Ring>
8  protected:
9  int n;
11  std::string* names;
12  public:
13  /**
14  * Default constructpr
15  *
16  * @param
17  **/
18  TriangularSet<Ring> () : n(0) {}
19  /**
20  * Construct with number of polynomials and variable names
21  *
22  * @param s: The number of polynomials
23  * @param xs: The variable names
24  **/
25  TriangularSet<Ring> (int s, std::vector<std::string> xs) {
26  if (s < 1) { n = 0; }
27  else {
28  n = s;
30  if (xs.size() == s) {
31  names = new std::string[n];
32  for (int i = 0; i < n; ++i)
33  names[i] = xs[n-i-1];
34  }
35  else {
36  std::cout << "BPAS: error, TriangularSet<Ring> must be defined with " << s << " variables." << std::endl;
37  exit(1);
38  }
39  }
40  }
41  /**
42  * Copy constructor
43  *
44  * @param a: A triangular set
45  **/
47  if (n) {
49  names = new std::string[n];
50  std::copy(a.set, a.set+n, set);
51  std::copy(a.names, a.names+n, names);
52  }
53  }
54  /**
55  * Deconstructor
56  *
57  * @param
58  **/
60  if (n) {
61  delete [] set;
62  delete [] names;
63  }
64  }
65  /**
66  * Overload operator =
67  *
68  * @param a: A triangular set
69  **/
71  if (this != &a) {
72  if (n) {
73  delete [] set;
74  delete [] names;
75  }
76  n = a.n;
78  names = new std::string[n];
79  std::copy(a.set, a.set+n, set);
80  std::copy(a.names, a.names+n, names);
81  }
82  return *this;
83  }
84  /**
85  * Overload operator +
86  *
87  * @param smp: A sparse multivariate polynomial
88  **/
90  TriangularSet<Ring> r(*this);
91  return (r += smp);
92  }
93 
94  /**
95  * Overload operator +=
96  *
97  * @param smp: A sparse multivariate polynomial
98  **/
100  if (smp.isConstant()) {
101  std::cout << "BPAS: error, cannot adding a constant to TriangularSet<Ring>" << std::endl;
102  exit(1);
103  }
104  int v = smp.numberOfVariables();
105  if (v > n || !v) {
106  std::cout << "BPAS: error, cannot adding a polynomisl of " << v << " variables to a TriangularSet<Ring> of " << n << " variables." << std::endl;
107  exit(1);
108  }
109 
110  int* pos = new int[v];
111  std::vector<std::string> xs = smp.variables();
112  for (int i = 0; i < v; ++i) {
113  pos[i] = -1;
114  for (int j = n-1; j > -1; --j) {
115  if (xs[i] == names[j]) {
116  pos[i] = j;
117  break;
118  }
119  }
120  }
121  bool isIt = 0;
122  int k = pos[0];
123  if (k < 0) { isIt = 1; }
124  for (int i = 1; i < v; ++i) {
125  if (pos[i] >= 0 && pos[i] < k) { k = pos[i]; }
126  else { isIt = 1; break; }
127  }
128  if (isIt) {
129  std::cout << "BPAS: error, TriangularSet<Ring>[";
130  for (int i = n-1; i > -1; --i) {
131  std::cout << names[i];
132  if (i) { std::cout << ", "; }
133  }
134  std::cout << "] cannot add a polynomial in Ring[";
135  for (int i = 0; i < xs.size(); ++i) {
136  std::cout << xs[i];
137  if (i < xs.size()-1) { std::cout << ", "; }
138  }
139  std::cout << "]." << std::endl;
140  exit(1);
141  }
142  k = pos[0];
143  delete [] pos;
144 
145  if (!set[k].isZero()) {
146  std::cout << "BPAS: error, a polynomial with the leading variable " << xs[0] << " already exists in TriangularSet<Ring>[";
147  for (int i = n-1; i > -1; --i) {
148  std::cout << names[i];
149  if (i) { std::cout << ", "; }
150  }
151  std::cout << "]." << std::endl;
152  exit(1);
153  }
154 
155  set[k] += smp;
156 
157  return *this;
158  }
159  /**
160  * Get the number of variables
161  *
162  * @param
163  **/
164  inline int numberOfVariables() {
165  return n;
166  }
167  /**
168  * Get variable names
169  *
170  * @param
171  **/
172  inline std::vector<std::string> variables() {
173  std::vector<std::string> xs;
174  for (int i = n-1; i > -1; --i)
175  xs.push_back(names[i]);
176  return xs;
177  }
178  /**
179  * Select a polynomial given the leading variable
180  *
181  * @param x: The leading variable name
182  **/
184  int k = -1;
185  for (int i = 0; i < n; ++i) {
186  if (x == names[i]) {
187  k = i;
188  break;
189  }
190  }
191  if (k < 0)
193  else
194  return set[k];
195  }
196  /**
197  * The triangular set under a variable
198  *
199  * @param x: The variable name
200  **/
201  inline TriangularSet<Ring> under(std::string x) {
202  int k = -1;
203  for (int i = 0; i < n; ++i) {
204  if (x == names[i]) {
205  k = i;
206  break;
207  }
208  }
209  if (k <= 0)
210  return TriangularSet<Ring>();
211  else {
213  r.n = k - 1;
214  r.set = new SparseMultivariatePolynomial<Ring>[r.n];
215  r.names = new std::string[r.n];
216  std::copy(set, set+k-1, r.set);
217  std::copy(names, names+k-1, r.names);
218  return r;
219  }
220  }
221  /**
222  * The triangular set upper a variable
223  *
224  * @param x: The variable name
225  **/
226  inline TriangularSet<Ring> upper(std::string x) {
227  int k = -1;
228  for (int i = 0; i < n; ++i) {
229  if (x == names[i]) {
230  k = i;
231  break;
232  }
233  }
234  if (k < 0 || k == n-1)
235  return TriangularSet<Ring>();
236  else {
238  r.n = n - k - 1;
239  r.set = new SparseMultivariatePolynomial<Ring>[r.n];
240  r.names = new std::string[r.n];
241  std::copy(set+k+1, set+n, r.set);
242  std::copy(names+k+1, names+n, r.names);
243  return r;
244  }
245  }
246  /**
247  * Pseudo division
248  * Return the remainder
249  *
250  * @param p: An input polynomial
251  * @param quo: The quotients
252  * @param c: The constant multiplied to the input polynomial
253  **/
255  if (quo == NULL)
256  quo = new std::vector< SparseMultivariatePolynomial<Ring> >;
257  if (c == NULL)
259  c->one();
260 
262  for (int i = n-1; i > -1 && !r.isZero(); --i) {
263  if (!set[i].isZero()) {
264  SparseUnivariatePolynomial< SparseMultivariatePolynomial<Ring> > s = set[i].convertToSUP(names[i]);
269  *c *= d;
270  quo->push_back(SparseMultivariatePolynomial<Ring>(q));
271  }
272  }
273  return r;
274  }
275  /**
276  * Monic division
277  * Return the remainder
278  *
279  * @param p: An input polynomial
280  * @param quo: The quotients
281  **/
283  if (quo == NULL)
284  quo = new std::vector< SparseMultivariatePolynomial<Ring> >;
285 
287  for (int i = n-1; i > -1 && !r.isZero(); --i) {
288  if (!set[i].isZero()) {
289  SparseUnivariatePolynomial< SparseMultivariatePolynomial<Ring> > s = set[i].convertToSUP(names[i]);
293  quo->push_back(SparseMultivariatePolynomial<Ring>(q));
294  }
295  }
296  return r;
297 
298  }
299 
300  /**
301  * Overload stream operator <<
302  *
303  * @param out: Stream object
304  * @param a: A triangular set
305  **/
306  inline friend std::ostream& operator<< (std::ostream& out, TriangularSet<Ring>& a) {
307  bool isFirst = 0;
308  out << "[";
309  for (int i = 0; i < a.n; ++i) {
310  if (!a.set[i].isZero()) {
311  if (isFirst) { out << ", "; }
312  out << a.set[i];
313  isFirst = 1;
314  }
315  }
316  out << "]";
317  return out;
318  }
319 };
320 
321 #endif
322 /* This file is part of the BPAS library http://www.bpaslib.org
323 
324  BPAS is free software: you can redistribute it and/or modify
325  it under the terms of the GNU General Public License as published by
326  the Free Software Foundation, either version 3 of the License, or
327  (at your option) any later version.
328 
329  BPAS is distributed in the hope that it will be useful,
330  but WITHOUT ANY WARRANTY; without even the implied warranty of
331  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
332  GNU General Public License for more details.
333 
334  You should have received a copy of the GNU General Public License
335  along with BPAS. If not, see <http://www.gnu.org/licenses/>.
336 
337  Copyright: Changbo Chen <changbo.chen@hotmail.com>
338  Farnam Mansouri <mansouri.farnam@gmail.com>
339  Marc Moreno Maza <moreno@csd.uwo.ca>
340  Ning Xie <nxie6@csd.uwo.ca>
341  Yuzhen Xie <yuzhenxie@yahoo.ca>
342 
343 */
344 
345 
TriangularSet< Ring > & operator=(TriangularSet< Ring > a)
Definition: triangularset.h:70
Definition: triangularset.h:7
Definition: upolynomial.h:10
int isConstant()
Definition: mpolynomial.h:621
bool isZero()
Definition: mpolynomial.h:543
SparseUnivariatePolynomial< Ring > monicDivide(SparseUnivariatePolynomial< Ring > &b)
Definition: upolynomial.h:1200
SparseMultivariatePolynomial< Ring > select(std::string x)
Definition: triangularset.h:183
SparseUnivariatePolynomial< SparseMultivariatePolynomial< Ring > > convertToSUP(std::string x)
Definition: mpolynomial.h:1399
std::vector< std::string > variables()
Definition: mpolynomial.h:1313
SparseMultivariatePolynomial< Ring > monicDivide(SparseMultivariatePolynomial< Ring > &p, std::vector< SparseMultivariatePolynomial< Ring > > *quo=NULL)
Definition: triangularset.h:282
std::vector< std::string > variables()
Definition: triangularset.h:172
Definition: mpolynomial.h:12
TriangularSet< Ring > & operator+=(SparseMultivariatePolynomial< Ring > smp)
Definition: triangularset.h:99
SparseUnivariatePolynomial< Ring > lazyPseudoDivide(SparseUnivariatePolynomial< Ring > &b, Ring *c, Ring *d=NULL)
Definition: upolynomial.h:1260
void one()
Definition: mpolynomial.h:575
int numberOfVariables()
Definition: triangularset.h:164
TriangularSet< Ring > under(std::string x)
Definition: triangularset.h:201
TriangularSet< Ring > upper(std::string x)
Definition: triangularset.h:226
Definition: polynomial.h:94
int numberOfVariables()
Definition: mpolynomial.h:414
TriangularSet< Ring > operator+(SparseMultivariatePolynomial< Ring > smp)
Definition: triangularset.h:89
SparseMultivariatePolynomial< Ring > pseudoDivide(SparseMultivariatePolynomial< Ring > &p, std::vector< SparseMultivariatePolynomial< Ring > > *quo=NULL, SparseMultivariatePolynomial< Ring > *c=NULL)
Definition: triangularset.h:254