Implements a multiplicative term, a term of type k*x^n*y^m*. More...
#include <mterm.hh>
Public Member Functions | |
mterm () | |
create a 0 mterm | |
mterm (int k) | |
create a simple integer mterm | |
mterm (double k) | |
create a simple float mterm | |
mterm (Tree t) | |
create a mterm from a multiplicative exp | |
mterm (const mterm &m) | |
create a copy of a mterm | |
void | cleanup () |
remove usued factors | |
bool | isNotZero () const |
true if mterm doesn't represent number 0 | |
bool | isNegative () const |
true if mterm has a negative coefficient | |
const mterm & | operator= (const mterm &m) |
replace the content with a copy of m | |
const mterm & | operator*= (Tree m) |
multiply in place by a multiplicative exp | |
const mterm & | operator/= (Tree m) |
divide in place by a multiplicative exp | |
const mterm & | operator+= (const mterm &m) |
add in place an mterm of same signature | |
const mterm & | operator-= (const mterm &m) |
add in place an mterm of same signature | |
const mterm & | operator*= (const mterm &m) |
multiply in place by a mterm | |
const mterm & | operator/= (const mterm &m) |
divide in place by a mterm | |
mterm | operator* (const mterm &m) const |
mterms multiplication | |
mterm | operator/ (const mterm &m) const |
mterms division | |
ostream & | print (ostream &dst) const |
print a mterm k*x1**n1*x2**n2... | |
int | complexity () const |
return an evaluation of the complexity | |
Tree | normalizedTree (bool sign=false, bool neg=false) const |
return the normalized tree of the mterm | |
Tree | signatureTree () const |
return a signature (a normalized tree) | |
bool | hasDivisor (const mterm &n) const |
return true if this can be divided by n | |
Private Attributes | |
Tree | fCoef |
constant part of the term (usually 1 or -1) | |
map< Tree, int > | fFactors |
non constant terms and their power | |
Friends | |
mterm | gcd (const mterm &m1, const mterm &m2) |
return a mterm that is the greatest common divisor of two mterms |
Implements a multiplicative term, a term of type k*x^n*y^m*.
.. and its arithmetic
Definition at line 21 of file mterm.hh.
mterm::mterm | ( | ) |
mterm::mterm | ( | int | k | ) |
mterm::mterm | ( | double | k | ) |
mterm::mterm | ( | Tree | t | ) |
create a mterm from a multiplicative exp
create a mterm from a tree sexpression
mterm::mterm | ( | const mterm & | m | ) |
void mterm::cleanup | ( | ) |
remove usued factors
Clean a mterm by removing x**0 factors.
Definition at line 177 of file mterm.cpp.
References fCoef, fFactors, and isZero().
Referenced by operator*=(), operator+=(), operator-=(), and operator/=().
00178 { 00179 if (isZero(fCoef)) { 00180 fFactors.clear(); 00181 } else { 00182 for (MP::iterator p = fFactors.begin(); p != fFactors.end(); ) { 00183 if (p->second == 0) { 00184 fFactors.erase(p++); 00185 } else { 00186 p++; 00187 } 00188 } 00189 } 00190 }
int mterm::complexity | ( | ) | const |
return an evaluation of the complexity
Compute the "complexity" of a mterm, that is the number of factors it contains (weighted by the importance of these factors).
Definition at line 65 of file mterm.cpp.
References abs(), fCoef, fFactors, getSigOrder(), and isOne().
Referenced by aterm::greatestDivisor(), and normalizeAddTerm().
00066 { 00067 int c = isOne(fCoef) ? 0 : 1; 00068 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); ++p) { 00069 c += (1+getSigOrder(p->first))*abs(p->second); 00070 } 00071 return c; 00072 }
bool mterm::hasDivisor | ( | const mterm & | n | ) | const |
return true if this can be divided by n
Check if M accept N has a divisor.
We can say that N is a divisor of M if M = N*Q and the complexity is preserved : complexity(M) = complexity(N)+complexity(Q) x**u has divisor x**v if u >= v x**-u has divisor x**-v if -u <= -v
Definition at line 337 of file mterm.cpp.
References contains(), and fFactors.
Referenced by aterm::factorize().
00338 { 00339 for (MP::const_iterator p1 = n.fFactors.begin(); p1 != n.fFactors.end(); p1++) { 00340 // for each factor f**q of m 00341 Tree f = p1->first; 00342 int v = p1->second; 00343 00344 // check that f is also a factor of *this 00345 MP::const_iterator p2 = fFactors.find(f); 00346 if (p2 == fFactors.end()) return false; 00347 00348 // analyze quantities 00349 int u = p2->second; 00350 if (! contains(u,v) ) return false; 00351 } 00352 return true; 00353 }
bool mterm::isNegative | ( | ) | const |
true if mterm has a negative coefficient
true if mterm doesn't represent number 0
Definition at line 40 of file mterm.cpp.
References fCoef, and isGEZero().
Referenced by aterm::normalizedTree().
bool mterm::isNotZero | ( | ) | const |
Tree mterm::normalizedTree | ( | bool | sign = false , |
|
bool | neg = false | |||
) | const |
return the normalized tree of the mterm
returns a normalized (canonical) tree expression of structure : ((k*(v1/v2))*(c1/c2))*(s1/s2) In signature mode the fCoef factor is ommited In negativeMode the sign of the fCoef factor is inverted
Definition at line 424 of file mterm.cpp.
References combineDivLeft(), combineMulDiv(), combineMulLeft(), fCoef, fFactors, getSigOrder(), isMinusOne(), isOne(), isZero(), minusNum(), sigDiv(), and tree().
Referenced by aterm::factorize(), aterm::normalizedTree(), and signatureTree().
00425 { 00426 if (fFactors.empty() || isZero(fCoef)) { 00427 // it's a pure number 00428 if (signatureMode) return tree(1); 00429 if (negativeMode) return minusNum(fCoef); 00430 else return fCoef; 00431 } else { 00432 // it's not a pure number, it has factors 00433 Tree A[4], B[4]; 00434 00435 // group by order 00436 for (int order = 0; order < 4; order++) { 00437 A[order] = 0; B[order] = 0; 00438 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) { 00439 Tree f = p->first; // f = factor 00440 int q = p->second; // q = power of f 00441 if (f && q && getSigOrder(f)==order) { 00442 00443 combineMulDiv (A[order], B[order], f, q); 00444 } 00445 } 00446 } 00447 if (A[0] != 0) cerr << "A[0] == " << *A[0] << endl; 00448 if (B[0] != 0) cerr << "B[0] == " << *B[0] << endl; 00449 // en principe ici l'order zero est vide car il correspond au coef numerique 00450 assert(A[0] == 0); 00451 assert(B[0] == 0); 00452 00453 // we only use a coeficient if it differes from 1 and if we are not in signature mode 00454 if (! (signatureMode | isOne(fCoef))) { 00455 A[0] = (negativeMode) ? minusNum(fCoef) : fCoef; 00456 } 00457 00458 if (signatureMode) { 00459 A[0] = 0; 00460 } else if (negativeMode) { 00461 if (isMinusOne(fCoef)) { A[0] = 0; } else { A[0] = minusNum(fCoef); } 00462 } else if (isOne(fCoef)) { 00463 A[0] = 0; 00464 } else { 00465 A[0] = fCoef; 00466 } 00467 00468 // combine each order separately : R[i] = A[i]/B[i] 00469 Tree RR = 0; 00470 for (int order = 0; order < 4; order++) { 00471 if (A[order] && B[order]) combineMulLeft(RR,sigDiv(A[order],B[order])); 00472 else if (A[order]) combineMulLeft(RR,A[order]); 00473 else if (B[order]) combineDivLeft(RR,B[order]); 00474 } 00475 if (RR == 0) RR = tree(1); // a verifier ******************* 00476 00477 assert(RR); 00478 //cerr << "Normalized Tree of " << *this << " is " << ppsig(RR) << endl; 00479 return RR; 00480 } 00481 }
multiply in place by a mterm
Multiply a mterm by the content of another mterm.
Definition at line 237 of file mterm.cpp.
References cleanup(), fCoef, fFactors, and mulNums().
00238 { 00239 fCoef = mulNums(fCoef,m.fCoef); 00240 for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) { 00241 fFactors[p->first] += p->second; 00242 } 00243 cleanup(); 00244 return *this; 00245 }
multiply in place by a multiplicative exp
Multiple a mterm by an expression tree t.
Go down recursively looking for multiplications and divisions
Definition at line 103 of file mterm.cpp.
References fCoef, fFactors, isNum(), isSigBinOp(), isSigPow(), kDiv, kMul, and mulNums().
00104 { 00105 int op, n; 00106 Tree x,y; 00107 00108 assert(t!=0); 00109 00110 if (isNum(t)) { 00111 fCoef = mulNums(fCoef,t); 00112 00113 } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) { 00114 *this *= x; 00115 *this *= y; 00116 00117 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) { 00118 *this *= x; 00119 *this /= y; 00120 00121 } else { 00122 if (isSigPow(t,x,n)) { 00123 fFactors[x] += n; 00124 } else { 00125 fFactors[t] += 1; 00126 } 00127 } 00128 return *this; 00129 }
add in place an mterm of same signature
Add in place an mterm.
As we want the result to be a mterm therefore essentially mterms of same signature can be added
Definition at line 196 of file mterm.cpp.
References addNums(), cleanup(), fCoef, fFactors, isZero(), and signatureTree().
00197 { 00198 if (isZero(m.fCoef)) { 00199 // nothing to do 00200 } else if (isZero(fCoef)) { 00201 // copy of m 00202 fCoef = m.fCoef; 00203 fFactors = m.fFactors; 00204 } else { 00205 // only add mterms of same signature 00206 assert(signatureTree() == m.signatureTree()); 00207 fCoef = addNums(fCoef, m.fCoef); 00208 } 00209 cleanup(); 00210 return *this; 00211 }
add in place an mterm of same signature
Substract in place an mterm.
As we want the result to be a mterm therefore essentially mterms of same signature can be substracted
Definition at line 217 of file mterm.cpp.
References cleanup(), fCoef, fFactors, isZero(), minusNum(), signatureTree(), and subNums().
00218 { 00219 if (isZero(m.fCoef)) { 00220 // nothing to do 00221 } else if (isZero(fCoef)) { 00222 // minus of m 00223 fCoef = minusNum(m.fCoef); 00224 fFactors = m.fFactors; 00225 } else { 00226 // only add mterms of same signature 00227 assert(signatureTree() == m.signatureTree()); 00228 fCoef = subNums(fCoef, m.fCoef); 00229 } 00230 cleanup(); 00231 return *this; 00232 }
divide in place by a mterm
Divide a mterm by the content of another mterm.
Definition at line 250 of file mterm.cpp.
References cleanup(), divExtendedNums(), fCoef, and fFactors.
00251 { 00252 //cerr << "division en place : " << *this << " / " << m << endl; 00253 fCoef = divExtendedNums(fCoef,m.fCoef); 00254 for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) { 00255 fFactors[p->first] -= p->second; 00256 } 00257 cleanup(); 00258 return *this; 00259 }
divide in place by a multiplicative exp
Divide a mterm by an expression tree t.
Go down recursively looking for multiplications and divisions
Definition at line 135 of file mterm.cpp.
References divExtendedNums(), fCoef, fFactors, isNum(), isSigBinOp(), isSigPow(), kDiv, and kMul.
00136 { 00137 //cerr << "division en place : " << *this << " / " << ppsig(t) << endl; 00138 int op,n; 00139 Tree x,y; 00140 00141 assert(t!=0); 00142 00143 if (isNum(t)) { 00144 fCoef = divExtendedNums(fCoef,t); 00145 00146 } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) { 00147 *this /= x; 00148 *this /= y; 00149 00150 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) { 00151 *this /= x; 00152 *this *= y; 00153 00154 } else { 00155 if (isSigPow(t,x,n)) { 00156 fFactors[x] -= n; 00157 } else { 00158 fFactors[t] -= 1; 00159 } 00160 } 00161 return *this; 00162 }
ostream & mterm::print | ( | ostream & | dst | ) | const |
print a mterm k*x1**n1*x2**n2...
print a mterm in a human readable format
Definition at line 48 of file mterm.cpp.
References fCoef, fFactors, and isOne().
Referenced by operator<<().
00049 { 00050 const char* sep = ""; 00051 if (!isOne(fCoef) || fFactors.empty()) { dst << ppsig(fCoef); sep = " * "; } 00052 //if (true) { dst << ppsig(fCoef); sep = " * "; } 00053 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) { 00054 dst << sep << ppsig(p->first); 00055 if (p->second != 1) dst << "**" << p->second; 00056 sep = " * "; 00057 } 00058 return dst; 00059 }
Tree mterm::signatureTree | ( | ) | const |
return a signature (a normalized tree)
returns a normalized (canonical) tree expression of structure : ((v1/v2)*(c1/c2))*(s1/s2)
Definition at line 413 of file mterm.cpp.
References normalizedTree().
Referenced by operator+=(), aterm::operator+=(), operator-=(), and aterm::operator-=().
00414 { 00415 return normalizedTree(true); 00416 }
return a mterm that is the greatest common divisor of two mterms
Definition at line 299 of file mterm.cpp.
00300 { 00301 //cerr << "GCD of " << m1 << " and " << m2 << endl; 00302 00303 Tree c = (m1.fCoef == m2.fCoef) ? m1.fCoef : tree(1); // common coefficient (real gcd not needed) 00304 mterm R(c); 00305 for (MP::const_iterator p1 = m1.fFactors.begin(); p1 != m1.fFactors.end(); p1++) { 00306 Tree t = p1->first; 00307 MP::const_iterator p2 = m2.fFactors.find(t); 00308 if (p2 != m2.fFactors.end()) { 00309 int v1 = p1->second; 00310 int v2 = p2->second; 00311 int c = common(v1,v2); 00312 if (c != 0) { 00313 R.fFactors[t] = c; 00314 } 00315 } 00316 } 00317 //cerr << "GCD of " << m1 << " and " << m2 << " is : " << R << endl; 00318 return R; 00319 }
Tree mterm::fCoef [private] |
constant part of the term (usually 1 or -1)
Definition at line 24 of file mterm.hh.
Referenced by cleanup(), complexity(), gcd(), isNegative(), isNotZero(), normalizedTree(), operator*=(), operator+=(), operator-=(), operator/=(), operator=(), and print().
map<Tree,int> mterm::fFactors [private] |
non constant terms and their power
Definition at line 25 of file mterm.hh.
Referenced by cleanup(), complexity(), gcd(), hasDivisor(), normalizedTree(), operator*=(), operator+=(), operator-=(), operator/=(), operator=(), and print().