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 14 of file mterm.cpp.

00014 : fCoef(sigInt(0)) {}

mterm::mterm ( int  k  ) 

create a simple integer mterm

Definition at line 15 of file mterm.cpp.

00015 : fCoef(sigInt(k)) {}

mterm::mterm ( double  k  ) 

create a simple float mterm

Definition at line 16 of file mterm.cpp.

00016 : 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 22 of file mterm.cpp.

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

mterm::mterm ( const mterm m  ) 

create a copy of a mterm

Definition at line 17 of file mterm.cpp.

00017 : 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 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 }

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 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 }

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 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 }

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 40 of file mterm.cpp.

References fCoef, and isGEZero().

Referenced by aterm::normalizedTree().

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

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 32 of file mterm.cpp.

References fCoef, and isZero().

Referenced by normalizeAddTerm().

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

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 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 }

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 264 of file mterm.cpp.

00265 {
00266     mterm r(*this);
00267     r *= m;
00268     return r;
00269 }

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 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 }

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 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 }

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 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 }

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 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 }

Here is the call graph for this function:

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

mterms division

Divide two mterms.

Definition at line 274 of file mterm.cpp.

00275 {
00276     mterm r(*this);
00277     r /= m;
00278     return r;
00279 }

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 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 }

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 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 }

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 167 of file mterm.cpp.

References fCoef, and fFactors.

00168 {
00169     fCoef = m.fCoef;
00170     fFactors = m.fFactors;
00171     return *this;
00172 }

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 }

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 413 of file mterm.cpp.

References normalizedTree().

Referenced by operator+=(), aterm::operator+=(), operator-=(), and aterm::operator-=().

00414 {
00415     return normalizedTree(true);
00416 }

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 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 }


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 Thu Jul 15 16:15:59 2010 for FAUST compiler by  doxygen 1.6.3