mterm Class Reference

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

#include <mterm.hh>

Collaboration diagram for mterm:

Public Member Functions
	mterm ()
	create a 0 mterm More...
	mterm (int k)
	create a simple integer mterm More...
	mterm (double k)
	create a simple float mterm More...
	mterm (Tree t)
	create a mterm from a multiplicative exp More...
	mterm (const mterm &m)
	create a copy of a mterm More...
void	cleanup ()
	remove usued factors More...
bool	isNotZero () const
	true if mterm doesn't represent number 0 More...
bool	isNegative () const
	true if mterm has a negative coefficient More...
const mterm &	operator= (const mterm &m)
	replace the content with a copy of m More...
const mterm &	operator*= (Tree m)
	multiply in place by a multiplicative exp More...
const mterm &	operator/= (Tree m)
	divide in place by a multiplicative exp More...
const mterm &	operator+= (const mterm &m)
	add in place an mterm of same signature More...
const mterm &	operator-= (const mterm &m)
	add in place an mterm of same signature More...
const mterm &	operator*= (const mterm &m)
	multiply in place by a mterm More...
const mterm &	operator/= (const mterm &m)
	divide in place by a mterm More...
mterm	operator* (const mterm &m) const
	mterms multiplication More...
mterm	operator/ (const mterm &m) const
	mterms division More...
ostream &	print (ostream &dst) const
	print a mterm k*x1**n1*x2**n2... More...
int	complexity () const
	return an evaluation of the complexity More...
Tree	normalizedTree (bool sign=false, bool neg=false) const
	return the normalized tree of the mterm More...
Tree	signatureTree () const
	return a signature (a normalized tree) More...
bool	hasDivisor (const mterm &n) const
	return true if this can be divided by n More...

Private Attributes
Tree	fCoef
	constant part of the term (usually 1 or -1) More...
map< Tree, int >	fFactors
	non constant terms and their power More...

Friends
mterm	gcd (const mterm &m1, const mterm &m2)
	return a mterm that is the greatest common divisor of two mterms More...

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.

: fCoef(sigInt(0)) {}

mterm::mterm

(

int

k

)

create a simple integer mterm

Definition at line 15 of file mterm.cpp.

: fCoef(sigInt(k)) {}

mterm::mterm

(

double

k

)

create a simple float mterm

Definition at line 16 of file mterm.cpp.

: 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.

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

mterm::mterm

(

const mterm &

m

)

create a copy of a mterm

Definition at line 17 of file mterm.cpp.

: 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/=().

{
    if (isZero(fCoef)) {
        fFactors.clear();
    } else {
        for (MP::iterator p = fFactors.begin(); p != fFactors.end(); ) {
            if (p->second == 0) {
                fFactors.erase(p++);
            } else {
                p++;
            }
        }
    }
}

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

{
    int c = isOne(fCoef) ? 0 : 1;
    for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); ++p) {
        c += (1+getSigOrder(p->first))*abs(p->second);
    }
    return c;
}

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

{
    for (MP::const_iterator p1 = n.fFactors.begin(); p1 != n.fFactors.end(); p1++) {
        // for each factor f**q of m
        Tree    f = p1->first;  
        int     v = p1->second;
        
        // check that f is also a factor of *this
        MP::const_iterator p2 = fFactors.find(f);
        if (p2 == fFactors.end()) return false;
        
        // analyze quantities
        int u = p2->second;
        if (! contains(u,v) ) return false;
    }
    return true;
}

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

{
    return !isGEZero(fCoef);
}

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

{
    return !isZero(fCoef);
}

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

{
    if (fFactors.empty() || isZero(fCoef)) {
        // it's a pure number
        if (signatureMode)  return tree(1);
        if (negativeMode)   return minusNum(fCoef);
        else                return fCoef;
    } else {
        // it's not a pure number, it has factors
        Tree A[4], B[4];
        
        // group by order
        for (int order = 0; order < 4; order++) {
            A[order] = 0; B[order] = 0;
            for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) {
                Tree    f = p->first;       // f = factor
                int     q = p->second;      // q = power of f
                if (f && q && getSigOrder(f)==order) {
                    
                    combineMulDiv (A[order], B[order], f, q);
                }
            }
        }
        if (A[0] != 0) cerr << "A[0] == " << *A[0] << endl; 
        if (B[0] != 0) cerr << "B[0] == " << *B[0] << endl; 
        // en principe ici l'order zero est vide car il correspond au coef numerique
        assert(A[0] == 0);
        assert(B[0] == 0);
        
        // we only use a coeficient if it differes from 1 and if we are not in signature mode
        if (! (signatureMode | isOne(fCoef))) {
            A[0] = (negativeMode) ? minusNum(fCoef) : fCoef;
        }
        
        if (signatureMode) {
            A[0] = 0;
        } else if (negativeMode) {
            if (isMinusOne(fCoef)) { A[0] = 0; } else { A[0] = minusNum(fCoef); }
        } else if (isOne(fCoef)) {
            A[0] = 0;
        } else {
            A[0] = fCoef;
        }
                    
        // combine each order separately : R[i] = A[i]/B[i]
        Tree RR = 0;
        for (int order = 0; order < 4; order++) {
            if (A[order] && B[order])   combineMulLeft(RR,sigDiv(A[order],B[order]));
            else if (A[order])          combineMulLeft(RR,A[order]);
            else if (B[order])          combineDivLeft(RR,B[order]);
        }
        if (RR == 0) RR = tree(1); // a verifier *******************
            
        assert(RR);
        //cerr << "Normalized Tree of " << *this << " is " << ppsig(RR) << endl;
        return RR;
    }
}

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.

{
    mterm r(*this);
    r *= m;
    return r;
}

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

{
    int     op, n;
    Tree    x,y;

    assert(t!=0);

    if (isNum(t)) {
        fCoef = mulNums(fCoef,t);

    } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) {
        *this *= x;
        *this *= y;

    } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) {
        *this *= x;
        *this /= y;

    } else {
        if (isSigPow(t,x,n)) {
            fFactors[x] += n;
        } else {
            fFactors[t] += 1;
        }
    }
    return *this;
}

Here is the call graph for this function:

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

{
    fCoef = mulNums(fCoef,m.fCoef);
    for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) {
        fFactors[p->first] += p->second;
    }
    cleanup();
    return *this;
}

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

{
    if (isZero(m.fCoef)) {
        // nothing to do
    } else if (isZero(fCoef))   {
        // copy of m
        fCoef = m.fCoef;
        fFactors = m.fFactors;
    } else {
        // only add mterms of same signature
        assert(signatureTree() == m.signatureTree());
        fCoef = addNums(fCoef, m.fCoef);
    }
    cleanup();
    return *this;
}

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

{
    if (isZero(m.fCoef)) {
        // nothing to do
    } else if (isZero(fCoef))   {
        // minus of m
        fCoef = minusNum(m.fCoef);
        fFactors = m.fFactors;
    } else {
        // only add mterms of same signature
        assert(signatureTree() == m.signatureTree());
        fCoef = subNums(fCoef, m.fCoef);
    }
    cleanup();
    return *this;
}

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.

{
    mterm r(*this);
    r /= m;
    return r;
}

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.

{
    //cerr << "division en place : " << *this << " / " << ppsig(t) << endl;
    int     op,n;
    Tree    x,y;

    assert(t!=0);

    if (isNum(t)) {
        fCoef = divExtendedNums(fCoef,t);

    } else if (isSigBinOp(t, &op, x, y) && (op == kMul)) {
        *this /= x;
        *this /= y;

    } else if (isSigBinOp(t, &op, x, y) && (op == kDiv)) {
        *this /= x;
        *this *= y;

    } else {
        if (isSigPow(t,x,n)) {
            fFactors[x] -= n;
        } else {
            fFactors[t] -= 1;
        }
    }
    return *this;
}

Here is the call graph for this function:

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.

{
    //cerr << "division en place : " << *this << " / " << m << endl;
    fCoef = divExtendedNums(fCoef,m.fCoef);
    for (MP::const_iterator p = m.fFactors.begin(); p != m.fFactors.end(); p++) {
        fFactors[p->first] -= p->second;
    }
    cleanup();
    return *this;
}

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.

{
    fCoef = m.fCoef;
    fFactors = m.fFactors;
    return *this;
}

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

{
    const char* sep = "";
    if (!isOne(fCoef) || fFactors.empty()) { dst << ppsig(fCoef); sep = " * "; }
    //if (true) { dst << ppsig(fCoef); sep = " * "; }
    for (MP::const_iterator p = fFactors.begin(); p != fFactors.end(); p++) {
        dst << sep << ppsig(p->first);
        if (p->second != 1) dst << "**" << p->second;
        sep = " * ";
    }
    return dst;
}

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

References normalizedTree().

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

{
    return normalizedTree(true);
}

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.

{
    //cerr << "GCD of " << m1 << " and " << m2 << endl;

    Tree c = (m1.fCoef == m2.fCoef) ? m1.fCoef : tree(1);       // common coefficient (real gcd not needed)
    mterm R(c);
    for (MP::const_iterator p1 = m1.fFactors.begin(); p1 != m1.fFactors.end(); p1++) {
        Tree t = p1->first;
        MP::const_iterator p2 = m2.fFactors.find(t);
        if (p2 != m2.fFactors.end()) {
            int v1 = p1->second;
            int v2 = p2->second;
            int c = common(v1,v2);
            if (c != 0) {
                R.fFactors[t] = c;
            }
        }
    }
    //cerr << "GCD of " << m1 << " and " << m2 << " is : " << R << endl;
    return R;
}

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:

• mterm.hh
• mterm.cpp