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 145 of file mterm.cpp.
References fCoef, fFactors, and isZero().
Referenced by operator*=(), operator+=(), operator-=(), and operator/=().
00146 { 00147 if (isZero(fCoef)) { 00148 fFactors.clear(); 00149 } else { 00150 for (MP::iterator p = fFactors.begin(); p != fFactors.end(); ) { 00151 if (p->second == 0) { 00152 fFactors.erase(p++); 00153 } else { 00154 p++; 00155 } 00156 } 00157 } 00158 }
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 64 of file mterm.cpp.
References abs(), fCoef, fFactors, getSigOrder(), and isOne().
Referenced by aterm::greatestDivisor(), and normalizeAddTerm().
00065 { 00066 int c = isOne(fCoef) ? 0 : 1; 00067 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); ++p) { 00068 c += (1+getSigOrder(p->first))*abs(p->second); 00069 } 00070 return c; 00071 }
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 305 of file mterm.cpp.
References contains(), and fFactors.
Referenced by aterm::factorize().
00306 { 00307 for (MP::const_iterator p1 = n.fFactors.begin(); p1 != n.fFactors.end(); p1++) { 00308 // for each factor f**q of m 00309 Tree f = p1->first; 00310 int v = p1->second; 00311 00312 // check that f is also a factor of *this 00313 MP::const_iterator p2 = fFactors.find(f); 00314 if (p2 == fFactors.end()) return false; 00315 00316 // analyze quantities 00317 int u = p2->second; 00318 if (! contains(u,v) ) return false; 00319 } 00320 return true; 00321 }
bool mterm::isNegative | ( | ) | const |
true if mterm has a negative coefficient
true if mterm doesn't represent number 0
Definition at line 39 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 391 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().
00392 { 00393 if (fFactors.empty() || isZero(fCoef)) { 00394 // it's a pure number 00395 if (signatureMode) return tree(1); 00396 if (negativeMode) return minusNum(fCoef); 00397 else return fCoef; 00398 } else { 00399 // it's not a pure number, it has factors 00400 Tree A[4], B[4]; 00401 00402 // group by order 00403 for (int order = 0; order < 4; order++) { 00404 A[order] = 0; B[order] = 0; 00405 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) { 00406 Tree f = p->first; // f = factor 00407 int q = p->second; // q = power of f 00408 if (f && q && getSigOrder(f)==order) { 00409 00410 combineMulDiv (A[order], B[order], f, q); 00411 } 00412 } 00413 } 00414 if (A[0] != 0) cerr << "A[0] == " << *A[0] << endl; 00415 if (B[0] != 0) cerr << "B[0] == " << *B[0] << endl; 00416 // en principe ici l'order zero est vide car il correspond au coef numerique 00417 assert(A[0] == 0); 00418 assert(B[0] == 0); 00419 00420 // we only use a coeficient if it differes from 1 and if we are not in signature mode 00421 if (! (signatureMode | isOne(fCoef))) { 00422 A[0] = (negativeMode) ? minusNum(fCoef) : fCoef; 00423 } 00424 00425 if (signatureMode) { 00426 A[0] = 0; 00427 } else if (negativeMode) { 00428 if (isMinusOne(fCoef)) { A[0] = 0; } else { A[0] = minusNum(fCoef); } 00429 } else if (isOne(fCoef)) { 00430 A[0] = 0; 00431 } else { 00432 A[0] = fCoef; 00433 } 00434 00435 // combine each order separately : R[i] = A[i]/B[i] 00436 Tree RR = 0; 00437 for (int order = 0; order < 4; order++) { 00438 if (A[order] && B[order]) combineMulLeft(RR,sigDiv(A[order],B[order])); 00439 else if (A[order]) combineMulLeft(RR,A[order]); 00440 else if (B[order]) combineDivLeft(RR,B[order]); 00441 } 00442 if (RR == 0) RR = tree(1); // a verifier ******************* 00443 00444 assert(RR); 00445 //cerr << "Normalized Tree of " << *this << " is " << ppsig(RR) << endl; 00446 return RR; 00447 } 00448 }
multiply in place by a mterm
Multiply a mterm by the content of another mterm.
Definition at line 205 of file mterm.cpp.
References cleanup(), fCoef, fFactors, and mulNums().
00206 { 00207 fCoef = mulNums(fCoef,m.fCoef); 00208 for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) { 00209 fFactors[p->first] += p->second; 00210 } 00211 cleanup(); 00212 return *this; 00213 }
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 78 of file mterm.cpp.
References fCoef, fFactors, isNum(), isSigBinOp(), kDiv, kMul, and mulNums().
00079 { 00080 int op; 00081 Tree x,y; 00082 00083 assert(t!=0); 00084 00085 if (isNum(t)) { 00086 fCoef = mulNums(fCoef,t); 00087 00088 } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) { 00089 *this *= x; 00090 *this *= y; 00091 00092 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) { 00093 *this *= x; 00094 *this /= y; 00095 00096 } else { 00097 Tree tnorm = t; //= simplify(t); 00098 fFactors[tnorm] += 1; 00099 } 00100 return *this; 00101 }
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 164 of file mterm.cpp.
References addNums(), cleanup(), fCoef, fFactors, isZero(), and signatureTree().
00165 { 00166 if (isZero(m.fCoef)) { 00167 // nothing to do 00168 } else if (isZero(fCoef)) { 00169 // copy of m 00170 fCoef = m.fCoef; 00171 fFactors = m.fFactors; 00172 } else { 00173 // only add mterms of same signature 00174 assert(signatureTree() == m.signatureTree()); 00175 fCoef = addNums(fCoef, m.fCoef); 00176 } 00177 cleanup(); 00178 return *this; 00179 }
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 185 of file mterm.cpp.
References cleanup(), fCoef, fFactors, isZero(), minusNum(), signatureTree(), and subNums().
00186 { 00187 if (isZero(m.fCoef)) { 00188 // nothing to do 00189 } else if (isZero(fCoef)) { 00190 // minus of m 00191 fCoef = minusNum(m.fCoef); 00192 fFactors = m.fFactors; 00193 } else { 00194 // only add mterms of same signature 00195 assert(signatureTree() == m.signatureTree()); 00196 fCoef = subNums(fCoef, m.fCoef); 00197 } 00198 cleanup(); 00199 return *this; 00200 }
divide in place by a mterm
Divide a mterm by the content of another mterm.
Definition at line 218 of file mterm.cpp.
References cleanup(), divExtendedNums(), fCoef, and fFactors.
00219 { 00220 //cerr << "division en place : " << *this << " / " << m << endl; 00221 fCoef = divExtendedNums(fCoef,m.fCoef); 00222 for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) { 00223 fFactors[p->first] -= p->second; 00224 } 00225 cleanup(); 00226 return *this; 00227 }
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 107 of file mterm.cpp.
References divExtendedNums(), fCoef, fFactors, isNum(), isSigBinOp(), kDiv, and kMul.
00108 { 00109 //cerr << "division en place : " << *this << " / " << ppsig(t) << endl; 00110 int op; 00111 Tree x,y; 00112 00113 assert(t!=0); 00114 00115 if (isNum(t)) { 00116 fCoef = divExtendedNums(fCoef,t); 00117 00118 } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) { 00119 *this /= x; 00120 *this /= y; 00121 00122 } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) { 00123 *this /= x; 00124 *this *= y; 00125 00126 } else { 00127 fFactors[t] -= 1; 00128 } 00129 return *this; 00130 }
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 47 of file mterm.cpp.
References fCoef, fFactors, and isOne().
Referenced by operator<<().
00048 { 00049 const char* sep = ""; 00050 if (!isOne(fCoef) || fFactors.empty()) { dst << ppsig(fCoef); sep = " * "; } 00051 //if (true) { dst << ppsig(fCoef); sep = " * "; } 00052 for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) { 00053 dst << sep << ppsig(p->first); 00054 if (p->second != 1) dst << "**" << p->second; 00055 sep = " * "; 00056 } 00057 return dst; 00058 }
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 380 of file mterm.cpp.
References normalizedTree().
Referenced by operator+=(), aterm::operator+=(), operator-=(), and aterm::operator-=().
00381 { 00382 return normalizedTree(true); 00383 }
return a mterm that is the greatest common divisor of two mterms
Definition at line 267 of file mterm.cpp.
00268 { 00269 //cerr << "GCD of " << m1 << " and " << m2 << endl; 00270 00271 Tree c = (m1.fCoef == m2.fCoef) ? m1.fCoef : tree(1); // common coefficient (real gcd not needed) 00272 mterm R(c); 00273 for (MP::const_iterator p1 = m1.fFactors.begin(); p1 != m1.fFactors.end(); p1++) { 00274 Tree t = p1->first; 00275 MP::const_iterator p2 = m2.fFactors.find(t); 00276 if (p2 != m2.fFactors.end()) { 00277 int v1 = p1->second; 00278 int v2 = p2->second; 00279 int c = common(v1,v2); 00280 if (c != 0) { 00281 R.fFactors[t] = c; 00282 } 00283 } 00284 } 00285 //cerr << "GCD of " << m1 << " and " << m2 << " is : " << R << endl; 00286 return R; 00287 }
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().