mterm Class Reference

Implements a multiplicative term, a term of type k*x^n*y^m*. More...

#include <mterm.hh>

Collaboration diagram for mterm:
[legend]

List of all members.

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 mtermoperator= (const mterm &m)
 replace the content with a copy of m
const mtermoperator*= (Tree m)
 multiply in place by a multiplicative exp
const mtermoperator/= (Tree m)
 divide in place by a multiplicative exp
const mtermoperator+= (const mterm &m)
 add in place an mterm of same signature
const mtermoperator-= (const mterm &m)
 add in place an mterm of same signature
const mtermoperator*= (const mterm &m)
 multiply in place by a mterm
const mtermoperator/= (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

Detailed Description

Implements a multiplicative term, a term of type k*x^n*y^m*.

.. and its arithmetic

Definition at line 21 of file mterm.hh.


Constructor & Destructor Documentation

mterm::mterm (  ) 

create a 0 mterm

Definition at line 13 of file mterm.cpp.

00013 : fCoef(sigInt(0)) {}

mterm::mterm ( int  k  ) 

create a simple integer mterm

Definition at line 14 of file mterm.cpp.

00014 : fCoef(sigInt(k)) {}

mterm::mterm ( double  k  ) 

create a simple float mterm

Definition at line 15 of file mterm.cpp.

00015 : fCoef(sigReal(k)) {}  // cerr << "DOUBLE " << endl; }

mterm::mterm ( Tree  t  ) 

create a mterm from a multiplicative exp

create a mterm from a tree sexpression

Definition at line 21 of file mterm.cpp.

00021                     : fCoef(sigInt(1))
00022 {
00023     //cerr << "mterm::mterm (Tree t) : " << ppsig(t) << endl;
00024     *this *= t; 
00025     //cerr << "MTERM(" << ppsig(t) << ") -> " << *this << endl;
00026 }

mterm::mterm ( const mterm m  ) 

create a copy of a mterm

Definition at line 16 of file mterm.cpp.

00016 : fCoef(m.fCoef), fFactors(m.fFactors) {}


Member Function Documentation

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

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().

00040 {
00041     return !isGEZero(fCoef);
00042 }

Here is the call graph for this function:

Here is the caller graph for this function:

bool mterm::isNotZero (  )  const

true if mterm doesn't represent number 0

Definition at line 31 of file mterm.cpp.

References fCoef, and isZero().

Referenced by normalizeAddTerm().

00032 {
00033     return !isZero(fCoef);
00034 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

mterm mterm::operator* ( const mterm m  )  const

mterms multiplication

Multiply two mterms.

Definition at line 232 of file mterm.cpp.

00233 {
00234     mterm r(*this);
00235     r *= m;
00236     return r;
00237 }

const mterm & mterm::operator*= ( const mterm m  ) 

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 }

Here is the call graph for this function:

const mterm & mterm::operator*= ( Tree  t  ) 

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 }

Here is the call graph for this function:

const mterm & mterm::operator+= ( const mterm m  ) 

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 }

Here is the call graph for this function:

const mterm & mterm::operator-= ( const mterm m  ) 

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 }

Here is the call graph for this function:

mterm mterm::operator/ ( const mterm m  )  const

mterms division

Divide two mterms.

Definition at line 242 of file mterm.cpp.

00243 {
00244     mterm r(*this);
00245     r /= m;
00246     return r;
00247 }

const mterm & mterm::operator/= ( const mterm m  ) 

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 }

Here is the call graph for this function:

const mterm & mterm::operator/= ( Tree  t  ) 

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 }

Here is the call graph for this function:

const mterm & mterm::operator= ( const mterm m  ) 

replace the content with a copy of m

Definition at line 135 of file mterm.cpp.

References fCoef, and fFactors.

00136 {
00137     fCoef = m.fCoef;
00138     fFactors = m.fFactors;
00139     return *this;
00140 }

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

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 }

Here is the call graph for this function:

Here is the caller graph for this function:


Friends And Related Function Documentation

mterm gcd ( const mterm m1,
const mterm m2 
) [friend]

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 }


Member Data Documentation

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().


The documentation for this class was generated from the following files:
Generated on Wed Apr 28 23:46:06 2010 for FAUST compiler by  doxygen 1.6.3