InternalPoly Class Reference

factory's class for polynomials More...

#include <int_poly.h>

Public Member Functions
	InternalPoly ()
	InternalPoly (const Variable &v, const int e, const CanonicalForm &c)
	InternalPoly (const InternalPoly &)
	~InternalPoly ()
InternalCF *	deepCopyObject () const
const char *	classname () const
int	level () const
Variable	variable () const
int	degree ()
	int InternalPoly::degree () More...
CanonicalForm	lc ()
CanonicalForm	Lc ()
CanonicalForm	LC ()
int	taildegree ()
CanonicalForm	tailcoeff ()
	CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree () More...
CanonicalForm	coeff (int i)
	CanonicalForm InternalPoly::coeff ( int i ) More...
void	print (OSTREAM &, char *)
bool	inBaseDomain () const
bool	inExtension () const
bool	inCoeffDomain () const
bool	inPolyDomain () const
bool	inQuotDomain () const
InternalCF *	genZero ()
InternalCF *	genOne ()
bool	isUnivariate () const
InternalCF *	neg ()
	InternalCF * InternalPoly::neg () More...
InternalCF *	invert ()
InternalCF *	tryInvert (const CanonicalForm &, bool &)
int	comparesame (InternalCF *)
	comparesame(), comparecoeff() - compare with an InternalPoly. More...
InternalCF *	addsame (InternalCF *)
InternalCF *	subsame (InternalCF *)
InternalCF *	mulsame (InternalCF *)
InternalCF *	tryMulsame (InternalCF *, const CanonicalForm &)
InternalCF *	dividesame (InternalCF *)
InternalCF *	modulosame (InternalCF *)
InternalCF *	divsame (InternalCF *)
InternalCF *	tryDivsame (InternalCF *, const CanonicalForm &, bool &)
InternalCF *	modsame (InternalCF *)
void	divremsame (InternalCF *, InternalCF *&, InternalCF *&)
bool	divremsamet (InternalCF *, InternalCF *&, InternalCF *&)
bool	tryDivremsamet (InternalCF *, InternalCF *&, InternalCF *&, const CanonicalForm &, bool &)
int	comparecoeff (InternalCF *)
	comparecoeff() always returns 1 since CO is defined to be larger than anything which is a coefficient w.r.t. More...
InternalCF *	addcoeff (InternalCF *)
InternalCF *	subcoeff (InternalCF *, bool)
InternalCF *	mulcoeff (InternalCF *)
InternalCF *	dividecoeff (InternalCF *, bool)
InternalCF *	tryDividecoeff (InternalCF *, bool, const CanonicalForm &, bool &)
InternalCF *	modulocoeff (InternalCF *, bool)
InternalCF *	divcoeff (InternalCF *, bool)
InternalCF *	tryDivcoeff (InternalCF *, bool, const CanonicalForm &, bool &)
InternalCF *	modcoeff (InternalCF *, bool)
void	divremcoeff (InternalCF *, InternalCF *&, InternalCF *&, bool)
bool	divremcoefft (InternalCF *, InternalCF *&, InternalCF *&, bool)
bool	tryDivremcoefft (InternalCF *, InternalCF *&, InternalCF *&, bool, const CanonicalForm &, bool &)
int	sign () const
	int InternalPoly::sign () const More...
void *	operator new (size_t)
void	operator delete (void *addr, size_t)
Public Member Functions inherited from InternalCF
	InternalCF ()
	InternalCF (const InternalCF &)
virtual	~InternalCF ()
int	deleteObject ()
InternalCF *	copyObject ()
virtual int	levelcoeff () const
virtual int	type () const
virtual bool	isZero () const
virtual bool	isOne () const
	bool InternalCF::isOne, isZero () const More...
virtual long	intval () const
virtual int	intmod (int) const
virtual InternalCF *	num ()
	InternalCF * InternalCF::num (), den () More...
virtual InternalCF *	den ()
virtual InternalCF *	bgcdsame (const InternalCF *const) const
	InternalCF * InternalCF::bgcdsame, bgcdcoeff ( const InternalCF * const ) More...
virtual InternalCF *	bgcdcoeff (const InternalCF *const)
virtual InternalCF *	bextgcdsame (InternalCF *, CanonicalForm &, CanonicalForm &)
	InternalCF * InternalCF::bextgcdsame ( InternalCF *, CanonicalForm & a, CanonicalForm & b ) More...
virtual InternalCF *	bextgcdcoeff (InternalCF *, CanonicalForm &, CanonicalForm &)
virtual InternalCF *	sqrt ()
	InternalCF * InternalCF::sqrt () More...
virtual int	ilog2 ()
	int InternalCF::ilog2 () More...
Public Member Functions inherited from omallocClass
void *	operator new (size_t size) throw (std::bad_alloc)
void	operator delete (void *block) throw ()
void *	operator new[] (size_t size) throw (std::bad_alloc)
void	operator delete[] (void *block) throw ()
void *	operator new (size_t size, const std::nothrow_t &) throw ()
void *	operator new[] (size_t size, const std::nothrow_t &) throw ()

Static Public Attributes
static const omBin	InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly))

Private Member Functions
	InternalPoly (termList, termList, const Variable &)

Static Private Member Functions
static termList	copyTermList (termList, termList &, bool negate=false)
static termList	deepCopyTermList (termList, termList &)
static void	freeTermList (termList)
static void	negateTermList (termList)
static termList	addTermList (termList, termList, termList &, bool negate)
static void	mulTermList (termList, const CanonicalForm &, const int)
static termList	divideTermList (termList, const CanonicalForm &, termList &)
static termList	divTermList (termList, const CanonicalForm &, termList &)
static termList	tryDivTermList (termList, const CanonicalForm &, termList &, const CanonicalForm &, bool &)
static termList	modTermList (termList, const CanonicalForm &, termList &)
static void	appendTermList (termList &, termList &, const CanonicalForm &, const int)
static termList	mulAddTermList (termList theList, termList aList, const CanonicalForm &c, const int exp, termList &lastTerm, bool negate)
static termList	reduceTermList (termList first, termList redterms, termList &last)

Private Attributes
termList	firstTerm
termList	lastTerm
Variable	var

Friends
class	CFIterator

Additional Inherited Members
Protected Member Functions inherited from InternalCF
int	getRefCount ()
void	incRefCount ()
int	decRefCount ()

Detailed Description

factory's class for polynomials

polynomials are represented as a linked list termList, factory uses a sparse distributive representation of polynomials, i.e. each poly is viewed as a univariate poly in its main variable CanonicalForm::mvar() over a (polynomial) ring

Definition at line 71 of file int_poly.h.

Constructor & Destructor Documentation

InternalPoly() [1/4]

InternalPoly::InternalPoly ( termList  first, termList  last, const Variable &  v  )

private

Definition at line 46 of file int_poly.cc.

{
    firstTerm = first;
    lastTerm = last;
    var = v;
}

InternalPoly() [2/4]

InternalPoly::InternalPoly

(

)

Definition at line 53 of file int_poly.cc.

{
    ASSERT( 0, "ups, why do you initialize an empty poly" );
}

InternalPoly() [3/4]

InternalPoly::InternalPoly	(	const Variable &	v,
		const int	e,
		const CanonicalForm &	c
	)

Definition at line 58 of file int_poly.cc.

{
    var = v;
    firstTerm = new term( 0, c, e );
    lastTerm = firstTerm;
}

InternalPoly() [4/4]

InternalPoly::InternalPoly

(

const InternalPoly &

)

Definition at line 65 of file int_poly.cc.

                                               :InternalCF()
{
    ASSERT( 0, "ups there is something wrong in your code" );
}

~InternalPoly()

InternalPoly::~InternalPoly

(

)

Definition at line 70 of file int_poly.cc.

{
    freeTermList( firstTerm );
}

Member Function Documentation

addcoeff()

InternalCF * InternalPoly::addcoeff ( InternalCF *  cc )

virtual

Reimplemented from InternalCF.

Definition at line 1038 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( c.isZero() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            if ( lastTerm->exp == 0 )
            {
                lastTerm->coeff += c;
                if ( lastTerm->coeff.isZero() )
                {
                    termList cursor = firstTerm;
                    while ( cursor->next != lastTerm )
                        cursor = cursor->next;
                    delete lastTerm;
                    cursor->next = 0;
                    lastTerm = cursor;
                }
            }
            else
            {
                lastTerm->next = new term( 0, c, 0 );
                lastTerm = lastTerm->next;
            }
            return this;
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last, false );
            if ( last->exp == 0 )
            {
                last->coeff += c;
                if ( last->coeff.isZero() )
                {
                    termList cursor = first;
                    while ( cursor->next != last )
                        cursor = cursor->next;
                    delete last;
                    cursor->next = 0;
                    last = cursor;
                }
            }
            else
            {
                last->next = new term( 0, c, 0L );
                last = last->next;
            }
            return new InternalPoly( first, last, var );
        }
    }
}

addsame()

InternalCF * InternalPoly::addsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 286 of file int_poly.cc.

{
    InternalPoly * aPoly = (InternalPoly*)aCoeff;
    if ( getRefCount() <= 1 )
    {
        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
        if ( firstTerm && firstTerm->exp != 0 )
            return this;
        else  if ( firstTerm )
        {
            InternalCF * res = firstTerm->coeff.getval();
            delete this;
            return res;
        }
        else
        {
            delete this;
            return CFFactory::basic( 0 );
        }
    }
    else
    {
        decRefCount();
        termList last, first = copyTermList( firstTerm, last );
        first = addTermList( first, aPoly->firstTerm, last, false );
        if ( first && first->exp != 0 )
            return new InternalPoly( first, last, var );
        else  if ( first )
        {
            InternalCF * res = first->coeff.getval();
            delete first;
            return res;
        }
        else
            return CFFactory::basic( 0 );
 
    }
}

addTermList()

termList InternalPoly::addTermList ( termList  theList, termList  aList, termList &  lastTerm, bool  negate  )

staticprivate

Definition at line 1922 of file int_poly.cc.

{
    termList theCursor = theList;
    termList aCursor = aList;
    termList predCursor = 0;
 
    if (negate)
      while ( theCursor && aCursor )
      {
        if ( theCursor->exp == aCursor->exp )
        {
            theCursor->coeff -= aCursor->coeff;
            if ( theCursor->coeff.isZero() )
            {
                if ( predCursor )
                {
                    predCursor->next = theCursor->next;
                    delete theCursor;
                    theCursor = predCursor->next;
                }
                else
                {
                    theList = theList->next;
                    delete theCursor;
                    theCursor = theList;
                }
            }
            else
            {
                predCursor = theCursor;
                theCursor = theCursor->next;
            }
            aCursor = aCursor->next;
        }
        else if ( theCursor->exp < aCursor->exp )
        {
            if ( predCursor )
            {
                predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
                predCursor = predCursor->next;
            }
            else
            {
                theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
                predCursor = theList;
            }
            aCursor = aCursor->next;
        }
        else
        {
            predCursor = theCursor;
            theCursor = theCursor->next;
        }
      }
    else
    while ( theCursor && aCursor )
    {
        if ( theCursor->exp == aCursor->exp )
        {
            theCursor->coeff += aCursor->coeff;
            if ( theCursor->coeff.isZero() )
            {
                if ( predCursor )
                {
                    predCursor->next = theCursor->next;
                    delete theCursor;
                    theCursor = predCursor->next;
                }
                else
                {
                    theList = theList->next;
                    delete theCursor;
                    theCursor = theList;
                }
            }
            else
            {
                predCursor = theCursor;
                theCursor = theCursor->next;
            }
            aCursor = aCursor->next;
        }
        else if ( theCursor->exp < aCursor->exp )
        {
            if ( predCursor )
            {
                predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
                predCursor = predCursor->next;
            }
            else
            {
                theList = new term( theCursor, aCursor->coeff, aCursor->exp );
                predCursor = theList;
            }
            aCursor = aCursor->next;
        }
        else
        {
            predCursor = theCursor;
            theCursor = theCursor->next;
        }
    }
    if ( aCursor )
    {
        if ( predCursor )
            predCursor->next = copyTermList( aCursor, lastTerm, negate );
        else
            theList = copyTermList( aCursor, lastTerm, negate );
    }
    else if ( ! theCursor )
        lastTerm = predCursor;
 
    return theList;
}

appendTermList()

void InternalPoly::appendTermList ( termList &  first, termList &  last, const CanonicalForm &  coeff, const int  exp  )

staticprivate

Definition at line 2167 of file int_poly.cc.

{
    if ( last )
    {
        last->next = new term( 0, coeff, exp );
        last = last->next;
    }
    else
    {
        first = new term( 0, coeff, exp );
        last = first;
    }
}

classname()

const char* InternalPoly::classname ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 96 of file int_poly.h.

{ return "InternalPoly"; }

coeff()

CanonicalForm InternalPoly::coeff ( int  i )

virtual

CanonicalForm InternalPoly::coeff ( int i )

See also

CanonicalForm::operator []()

Reimplemented from InternalCF.

Definition at line 162 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    while ( theCursor )
    {
        if ( theCursor->exp == i )
            return theCursor->coeff;
        else if ( theCursor->exp < i )
            return CanonicalForm( 0 );
        else
            theCursor = theCursor->next;
    }
    return CanonicalForm( 0 );
}

comparecoeff()

int InternalPoly::comparecoeff ( InternalCF *  )

virtual

comparecoeff() always returns 1 since CO is defined to be larger than anything which is a coefficient w.r.t.

CO.

Reimplemented from InternalCF.

Definition at line 1032 of file int_poly.cc.

{
    return 1;
}

comparesame()

int InternalPoly::comparesame ( InternalCF *  acoeff )

virtual

comparesame(), comparecoeff() - compare with an InternalPoly.

comparesame() compares the coefficient vectors of f=CO and g=acoeff w.r.t to a lexicographic order in the following way: f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t. i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and ii) g[i] occurs in g (i.e. is not equal to zero) and f[i] does not occur in f or f[i] < g[i] if f[i] occurs where f[i] denotes the coefficient to the power x^i of f.

As usual, comparesame() returns 1 if CO is larger than c, 0 if CO equals c, and -1 if CO is less than c. However, this function is optimized to test on equality since this is its most important and frequent usage.

See the respective ‘CanonicalForm’-methods for an explanation why we define such a strange (but total) ordering on polynomials.

See also

CanonicalForm::operator <(), CanonicalForm::operator ==()

Reimplemented from InternalCF.

Definition at line 990 of file int_poly.cc.

{
    ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
    InternalPoly* apoly = (InternalPoly*)acoeff;
    // check on triviality
    if ( this == apoly )
        return 0;
    else
    {
        termList cursor1 = firstTerm;
        termList cursor2 = apoly->firstTerm;
        for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
            // we test on inequality of coefficients at this
            // point instead of testing on "less than" at the
            // last `else' in the enclosed `if' statement since a
            // test on inequaltiy in general is cheaper
            if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) )
            {
                if ( cursor1->exp > cursor2->exp )
                    return 1;
                else  if ( cursor1->exp < cursor2->exp )
                    return -1;
                else  if ( cursor1->coeff > cursor2->coeff )
                    return 1;
                else
                    return -1;
             }
        // check trailing terms
        if ( cursor1 == cursor2 )
            return 0;
        else if ( cursor1 != 0 )
            return 1;
        else
            return -1;
    }
}

copyTermList()

termList InternalPoly::copyTermList ( termList  aTermList, termList &  theLastTerm, bool  negate = false  )

staticprivate

Definition at line 1830 of file int_poly.cc.

{
    if ( UNLIKELY(aTermList == 0) )
        return 0;
    else  if ( negate )
    {
        termList sourceCursor = aTermList;
        termList dummy = new term;
        termList targetCursor = dummy;
 
        while ( LIKELY(sourceCursor) )
        {
            targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
            targetCursor = targetCursor->next;
            sourceCursor = sourceCursor->next;
        }
        targetCursor->next = 0;
        theLastTerm = targetCursor;
        targetCursor = dummy->next;
        delete dummy;
        return targetCursor;
    }
    else
    {
        termList sourceCursor = aTermList;
        termList dummy = new term;
        termList targetCursor = dummy;
 
        while ( LIKELY(sourceCursor) )
        {
            targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
            targetCursor = targetCursor->next;
            sourceCursor = sourceCursor->next;
        }
        targetCursor->next = 0;
        theLastTerm = targetCursor;
        targetCursor = dummy->next;
        delete dummy;
        return targetCursor;
    }
}

deepCopyObject()

InternalCF * InternalPoly::deepCopyObject ( ) const

virtual

Reimplemented from InternalCF.

Definition at line 76 of file int_poly.cc.

{
    termList first, last;
    first = deepCopyTermList( firstTerm, last );
    return new InternalPoly( first, last, var );
}

deepCopyTermList()

termList InternalPoly::deepCopyTermList ( termList  aTermList, termList &  theLastTerm  )

staticprivate

Definition at line 1873 of file int_poly.cc.

{
    if ( aTermList == 0 )
        return 0;
    else
    {
        termList sourceCursor = aTermList;
        termList dummy = new term;
        termList targetCursor = dummy;
 
        while ( sourceCursor )
        {
            targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
            targetCursor = targetCursor->next;
            sourceCursor = sourceCursor->next;
        }
        targetCursor->next = 0;
        theLastTerm = targetCursor;
        targetCursor = dummy->next;
        delete dummy;
        return targetCursor;
    }
}

degree()

int InternalPoly::degree ( )

virtual

int InternalPoly::degree ()

See also

CanonicalForm::sign ()

Reimplemented from InternalCF.

Definition at line 100 of file int_poly.cc.

{
    return firstTerm->exp;
}

divcoeff()

InternalCF * InternalPoly::divcoeff ( InternalCF *  cc, bool  invert  )

virtual

Reimplemented from InternalCF.

Definition at line 1399 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( inExtension() && getReduce( var ) && invert )
    {
        InternalCF * dummy;
        dummy = this->invert();
        dummy = dummy->mulcoeff( cc );
        if ( getRefCount() <= 1 )
        {
            delete this;
            return dummy;
        }
        else
        {
            decRefCount();
            return dummy;
        }
    }
    if ( invert )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0 );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0 );
        }
    }
    if ( c.isOne() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            firstTerm = divTermList( firstTerm, c, lastTerm );
            if ( firstTerm && firstTerm->exp != 0 )
                return this;
            else  if ( firstTerm )
            {
                InternalCF * res = firstTerm->coeff.getval();
                delete this;
                return res;
            }
            else
            {
                delete this;
                return CFFactory::basic( 0 );
            }
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            first = divTermList( first, c, last );
            if ( first && first->exp != 0 )
                return new InternalPoly( first, last, var );
            else  if ( first )
            {
                InternalCF * res = first->coeff.getval();
                delete first;
                return res;
            }
            else
            {
                delete first;
                return CFFactory::basic( 0 );
            }
        }
    }
}

dividecoeff()

InternalCF * InternalPoly::dividecoeff ( InternalCF *  cc, bool  invert  )

virtual

Reimplemented from InternalCF.

Definition at line 1217 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( inExtension() && getReduce( var ) && invert )
    {
        InternalCF * dummy;
        dummy = this->invert();
        if (is_imm(dummy))
        {
          if (is_imm(cc))
          {
            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
            dummy=d;
          }
          else
            dummy=cc->mulcoeff(dummy);
        }
        else dummy = dummy->mulcoeff( cc );
        if ( getRefCount() <= 1 )
        {
            delete this;
            return dummy;
        }
        else
        {
            decRefCount();
            return dummy;
        }
    }
    if ( invert )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0 );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0 );
        }
    }
    if ( c.isOne() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            firstTerm = divideTermList( firstTerm, c, lastTerm );
            if ( firstTerm && firstTerm->exp != 0 )
                return this;
            else  if ( firstTerm )
            {
                InternalCF * res = firstTerm->coeff.getval();
                delete this;
                return res;
            }
            else
            {
                delete this;
                return CFFactory::basic( 0 );
            }
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            first = divideTermList( first, c, last );
            if ( first && first->exp != 0 )
                return new InternalPoly( first, last, var );
            else  if ( first )
            {
                InternalCF * res = first->coeff.getval();
                delete first;
                return res;
            }
            else
            {
                delete first;
                return CFFactory::basic( 0 );
            }
        }
    }
}

dividesame()

InternalCF * InternalPoly::dividesame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 491 of file int_poly.cc.

{
    return divsame( aCoeff );
}

divideTermList()

termList InternalPoly::divideTermList ( termList  firstTerm, const CanonicalForm &  coeff, termList &  lastTerm  )

staticprivate

Definition at line 2049 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    lastTerm = 0;
    termList dummy;
 
    while ( LIKELY(theCursor) )
    {
        theCursor->coeff /= coeff;
        if ( theCursor->coeff.isZero() )
        {
            if ( theCursor == firstTerm )
                firstTerm = theCursor->next;
            else
                lastTerm->next = theCursor->next;
            dummy = theCursor;
            theCursor = theCursor->next;
            delete dummy;
        }
        else
        {
            lastTerm = theCursor;
            theCursor = theCursor->next;
        }
    }
    return firstTerm;
}

divremcoeff()

void InternalPoly::divremcoeff ( InternalCF *  cc, InternalCF *&  quot, InternalCF *&  rem, bool  invert  )

virtual

Reimplemented from InternalCF.

Definition at line 1652 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        quot = copyObject();
        quot = quot->dividecoeff( cc, invert );
        rem = CFFactory::basic( 0 );
    }
    else  if ( invert )
    {
        if ( is_imm( cc ) )
            rem = cc;
        else
            rem = cc->copyObject();
        quot = CFFactory::basic( 0 );
    }
    else
    {
        CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
        ASSERT( ! c.isZero(), "divide by zero!" );
        termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
        quotfirst = divideTermList( quotfirst, c, quotlast );
        if ( quotfirst )
            if ( quotfirst->exp == 0 )
            {
                quot = quotfirst->coeff.getval();
                delete quotfirst;
            }
            else
                quot = new InternalPoly( quotfirst, quotlast, var );
        else
            quot = CFFactory::basic( 0 );
        rem = CFFactory::basic( 0 );
    }
}

divremcoefft()

bool InternalPoly::divremcoefft ( InternalCF *  cc, InternalCF *&  quot, InternalCF *&  rem, bool  invert  )

virtual

Reimplemented from InternalCF.

Definition at line 1689 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        quot = copyObject();
        quot = quot->dividecoeff( cc, invert );
        rem = CFFactory::basic( 0 );
        return true;
    }
    else  if ( invert )
    {
        if ( is_imm( cc ) )
            rem = cc;
        else
            rem = cc->copyObject();
        quot = CFFactory::basic( 0 );
        return true;
    }
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    ASSERT( ! c.isZero(), "divide by zero!" );
    termList quotfirst, quotcursor;
    termList cursor;
    CanonicalForm cquot, crem;
    bool divideok = true;
 
    cursor = firstTerm;
    quotcursor = quotfirst = new term;
 
    while ( cursor && divideok )
    {
        divideok = divremt( cursor->coeff, c, cquot, crem );
        divideok = divideok && crem.isZero();
        if ( divideok )
        {
            if ( ! cquot.isZero() )
            {
                quotcursor->next = new term( 0, cquot, cursor->exp );
                quotcursor = quotcursor->next;
            }
            cursor = cursor->next;
        }
    }
    quotcursor->next = 0;
    if ( divideok )
    {
        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
        if ( quotfirst )
            if ( quotfirst->exp == 0 )
            {
                quot = quotfirst->coeff.getval();
                delete quotfirst;
            }
            else
                quot = new InternalPoly( quotfirst, quotcursor, var );
        else
            quot = CFFactory::basic( 0 );
        rem = CFFactory::basic( 0 );
    }
    else
    {
        freeTermList( quotfirst );
    }
    return divideok;
}

divremsame()

void InternalPoly::divremsame ( InternalCF *  acoeff, InternalCF *&  quot, InternalCF *&  rem  )

virtual

Reimplemented from InternalCF.

Definition at line 765 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        InternalCF * dummy = acoeff->invert();
        quot = dummy->mulsame( this );
        rem = CFFactory::basic( 0 );
    }
    else
    {
        InternalPoly *aPoly = (InternalPoly*)acoeff;
        termList dummy, first, last, resultfirst = 0, resultlast = 0;
        CanonicalForm coeff, newcoeff;
        int exp, newexp;
 
        first = copyTermList( firstTerm, last );
 
        coeff = aPoly->firstTerm->coeff;
        exp = aPoly->firstTerm->exp;
        while (first && ( first->exp >= exp ) )
        {
            newcoeff = first->coeff / coeff;
            newexp = first->exp - exp;
            dummy = first;
            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
            delete dummy;
            appendTermList( resultfirst, resultlast, newcoeff, newexp );
        }
        if ( resultfirst )
            if ( resultfirst->exp == 0 )
            {
                quot = resultfirst->coeff.getval();
                delete resultfirst;
            }
            else
                quot = new InternalPoly( resultfirst, resultlast, var );
        else
            quot = CFFactory::basic( 0 );
        if ( first )
            if ( first->exp == 0 )
            {
                rem = first->coeff.getval();
                delete first;
            }
            else
                rem = new InternalPoly( first, last, var );
        else
            rem = CFFactory::basic( 0 );
    }
}

divremsamet()

bool InternalPoly::divremsamet ( InternalCF *  acoeff, InternalCF *&  quot, InternalCF *&  rem  )

virtual

Reimplemented from InternalCF.

Definition at line 817 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        divremsame( acoeff, quot, rem );
        return true;
    }
    InternalPoly *aPoly = (InternalPoly*)acoeff;
    termList dummy, first, last, resultfirst = 0, resultlast = 0;
    CanonicalForm coeff, newcoeff, dummycoeff;
    int exp, newexp;
    bool divideok = true;
 
//    if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
//        return false;
 
    first = copyTermList( firstTerm, last );
 
    coeff = aPoly->firstTerm->coeff;
    exp = aPoly->firstTerm->exp;
    while (first && ( first->exp >= exp ) && divideok )
    {
        divideok = divremt( first->coeff, coeff, newcoeff, dummycoeff );
        if ( divideok && dummycoeff.isZero() )
        {
            newexp = first->exp - exp;
            dummy = first;
            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
            delete dummy;
            appendTermList( resultfirst, resultlast, newcoeff, newexp );
        }
        else
            divideok = false;
    }
    if ( divideok )
    {
        if ( resultfirst )
            if ( resultfirst->exp == 0 )
            {
                quot = resultfirst->coeff.getval();
                delete resultfirst;
            }
            else
                quot = new InternalPoly( resultfirst, resultlast, var );
        else
            quot = CFFactory::basic( 0 );
        if ( first )
            if ( first->exp == 0 )
            {
                rem = first->coeff.getval();
                delete first;
            }
            else
                rem = new InternalPoly( first, last, var );
        else
            rem = CFFactory::basic( 0 );
    }
    else
    {
        freeTermList( resultfirst );
        freeTermList( first );
    }
    return divideok;
}

divsame()

InternalCF * InternalPoly::divsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 498 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        InternalCF * dummy = aCoeff->invert();
        if (is_imm(dummy)) dummy=this->mulsame(dummy);
        else dummy = dummy->mulsame( this );
        if ( getRefCount() <= 1 )
        {
             delete this;
             return dummy;
        }
        else
        {
            decRefCount();
            return dummy;
        }
    }
    InternalPoly *aPoly = (InternalPoly*)aCoeff;
    termList dummy, first, last, resultfirst = 0, resultlast = 0;
    CanonicalForm coeff, newcoeff;
    int exp, newexp;
    bool singleObject;
 
    if ( getRefCount() <= 1 )
    {
        first = firstTerm; last = lastTerm; singleObject = true;
    }
    else
    {
        first = copyTermList( firstTerm, last ); singleObject = false;
        decRefCount();
    }
    coeff = aPoly->firstTerm->coeff;
    exp = aPoly->firstTerm->exp;
    while (first && ( first->exp >= exp ) )
    {
        newcoeff = first->coeff / coeff;
        newexp = first->exp - exp;
        dummy = first;
        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
        delete dummy;
        appendTermList( resultfirst, resultlast, newcoeff, newexp );
    }
    freeTermList( first );
    if ( singleObject )
    {
        if ( resultfirst && resultfirst->exp != 0 )
        {
            firstTerm = resultfirst;
            lastTerm = resultlast;
            return this;
        }
        else  if ( resultfirst )
        {
            InternalCF * res = resultfirst->coeff.getval();
            delete resultfirst;
            firstTerm = 0;
            delete this;
            return res;
        }
        else
        {
            // this should not happen (evtl use assertion)
            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
            firstTerm = 0;
            delete this;
            return CFFactory::basic( 0 );
        }
    }
    else
    {
        if ( resultfirst && resultfirst->exp != 0 )
            return new InternalPoly( resultfirst, resultlast, var );
        else  if ( resultfirst )
        {
            InternalCF * res = resultfirst->coeff.getval();
            delete resultfirst;
            return res;
        }
        else
            return CFFactory::basic( 0 );
    }
}

divTermList()

termList InternalPoly::divTermList ( termList  firstTerm, const CanonicalForm &  coeff, termList &  lastTerm  )

staticprivate

Definition at line 2078 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    lastTerm = 0;
    termList dummy;
 
    while ( LIKELY(theCursor) )
    {
        theCursor->coeff.div( coeff );
        if ( theCursor->coeff.isZero() )
        {
            if ( theCursor == firstTerm )
                firstTerm = theCursor->next;
            else
                lastTerm->next = theCursor->next;
            dummy = theCursor;
            theCursor = theCursor->next;
            delete dummy;
        }
        else
        {
            lastTerm = theCursor;
            theCursor = theCursor->next;
        }
    }
    return firstTerm;
}

freeTermList()

void InternalPoly::freeTermList ( termList  aTermList )

staticprivate

Definition at line 1898 of file int_poly.cc.

{
    termList cursor = aTermList;
 
    while ( LIKELY(cursor) )
    {
        cursor = cursor->next;
        delete aTermList;
        aTermList = cursor;
    }
}

genOne()

InternalCF* InternalPoly::genOne ( )

inlinevirtual

Reimplemented from InternalCF.

Definition at line 118 of file int_poly.h.

    { return firstTerm->coeff.genOne().getval(); }

genZero()

InternalCF* InternalPoly::genZero ( )

inlinevirtual

Reimplemented from InternalCF.

Definition at line 115 of file int_poly.h.

    { return firstTerm->coeff.genZero().getval(); }

inBaseDomain()

bool InternalPoly::inBaseDomain ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 109 of file int_poly.h.

{ return false; }

inCoeffDomain()

bool InternalPoly::inCoeffDomain ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 111 of file int_poly.h.

{ return var.level() < 0; }

inExtension()

bool InternalPoly::inExtension ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 110 of file int_poly.h.

{ return var.level() < 0; }

inPolyDomain()

bool InternalPoly::inPolyDomain ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 112 of file int_poly.h.

{ return var.level() > 0; }

inQuotDomain()

bool InternalPoly::inQuotDomain ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 113 of file int_poly.h.

{ return false; }

invert()

InternalCF * InternalPoly::invert ( )

virtual

Reimplemented from InternalCF.

Definition at line 247 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        setReduce( var, false );
        CanonicalForm a( this->copyObject() );
        CanonicalForm b = getMipo( var );
        CanonicalForm u, v;
        CanonicalForm g = extgcd( a, b, u, v );
        setReduce( var, true );
        return u.getval();
    }
    else
        return CFFactory::basic( 0 );
}

isUnivariate()

bool InternalPoly::isUnivariate ( ) const

virtual

Reimplemented from InternalCF.

Definition at line 84 of file int_poly.cc.

{
    termList cursor = firstTerm;
    while ( cursor )
    {
        if ( ! cursor->coeff.inCoeffDomain() )
            return false;
        cursor = cursor->next;
    }
    return true;
}

lc()

CanonicalForm InternalPoly::lc ( )

virtual

See also

CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::Lc (), InternalPoly::LC ()

Reimplemented from InternalCF.

Definition at line 120 of file int_poly.cc.

{
    return firstTerm->coeff.lc();
}

Lc()

CanonicalForm InternalPoly::Lc ( )

virtual

See also

CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::LC ()

Reimplemented from InternalCF.

Definition at line 129 of file int_poly.cc.

{
    return firstTerm->coeff.Lc();
}

LC()

CanonicalForm InternalPoly::LC ( )

virtual

See also

CanonicalForm::lc(), CanonicalForm::Lc(), CanonicalForm::LC(), InternalPoly::lc (), InternalPoly::Lc ()

Reimplemented from InternalCF.

Definition at line 138 of file int_poly.cc.

{
    return firstTerm->coeff;
}

level()

int InternalPoly::level ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 97 of file int_poly.h.

{ return var.level(); }

modcoeff()

InternalCF * InternalPoly::modcoeff ( InternalCF *  cc, bool  invert  )

virtual

Reimplemented from InternalCF.

Definition at line 1588 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( invert )
    {
        if ( deleteObject() ) delete this;
        return c.getval();
    }
    ASSERT( ! c.isZero(), "divide by zero!" );
    if ( c.isOne() )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0 );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0 );
        }
    }
    else
    {
        if ( getRefCount() <= 1 )
        {
            firstTerm = modTermList( firstTerm, c, lastTerm );
            if ( firstTerm && firstTerm->exp != 0 )
                return this;
            else  if ( firstTerm )
            {
                InternalCF * res = firstTerm->coeff.getval();
                delete this;
                return res;
            }
            else
            {
                delete this;
                return CFFactory::basic( 0 );
            }
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            first = modTermList( first, c, last );
            if ( first && first->exp != 0 )
                return new InternalPoly( first, last, var );
            else  if ( first )
            {
                InternalCF * res = first->coeff.getval();
                delete first;
                return res;
            }
            else
            {
                delete first;
                return CFFactory::basic( 0 );
            }
        }
    }
}

modsame()

InternalCF * InternalPoly::modsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 693 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        if ( deleteObject() ) delete this;
        return CFFactory::basic( 0 );
    }
    InternalPoly *aPoly = (InternalPoly*)aCoeff;
    termList dummy, first, last;
    CanonicalForm coeff, newcoeff;
    int exp, newexp;
    bool singleObject;
 
    if ( getRefCount() <= 1 )
    {
        first = firstTerm; last = lastTerm; singleObject = true;
    }
    else
    {
        first = copyTermList( firstTerm, last ); singleObject = false;
        decRefCount();
    }
    coeff = aPoly->firstTerm->coeff;
    exp = aPoly->firstTerm->exp;
    while (first && ( first->exp >= exp ) )
    {
        newcoeff = first->coeff / coeff;
        newexp = first->exp - exp;
        dummy = first;
        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
        delete dummy;
    }
    if ( singleObject )
    {
        if ( first && first->exp != 0 )
        {
            firstTerm = first;
            lastTerm = last;
            return this;
        }
        else  if ( first )
        {
            InternalCF * res = first->coeff.getval();
            delete first;
            firstTerm = 0;
            delete this;
            return res;
        }
        else
        {
            firstTerm = 0;
            delete this;
            return CFFactory::basic( 0 );
        }
    }
    else
    {
        if ( first && first->exp != 0 )
            return new InternalPoly( first, last, var );
        else  if ( first )
        {
            InternalCF * res = first->coeff.getval();
            delete first;
            return res;
        }
        else
            return CFFactory::basic( 0 );
    }
}

modTermList()

termList InternalPoly::modTermList ( termList  firstTerm, const CanonicalForm &  coeff, termList &  lastTerm  )

staticprivate

Definition at line 2138 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    lastTerm = 0;
    termList dummy;
 
    while ( theCursor )
    {
        theCursor->coeff.mod( coeff );
        if ( theCursor->coeff.isZero() )
        {
            if ( theCursor == firstTerm )
                firstTerm = theCursor->next;
            else
                lastTerm->next = theCursor->next;
            dummy = theCursor;
            theCursor = theCursor-> next;
            delete dummy;
        }
        else
        {
            lastTerm = theCursor;
            theCursor = theCursor->next;
        }
    }
    return firstTerm;
}

modulocoeff()

InternalCF * InternalPoly::modulocoeff ( InternalCF *  cc, bool  invert  )

virtual

Reimplemented from InternalCF.

Definition at line 1574 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( invert )
    {
        if ( deleteObject() ) delete this;
        return c.getval();
    }
    ASSERT( ! c.isZero(), "divide by zero!" );
    if ( deleteObject() ) delete this;
    return CFFactory::basic( 0 );
}

modulosame()

InternalCF * InternalPoly::modulosame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 687 of file int_poly.cc.

{
    return modsame( aCoeff );
}

mulAddTermList()

termList InternalPoly::mulAddTermList ( termList  theList, termList  aList, const CanonicalForm &  c, const int  exp, termList &  lastTerm, bool  negate  )

staticprivate

Definition at line 2182 of file int_poly.cc.

{
    termList theCursor = theList;
    termList aCursor = aList;
    termList predCursor = 0;
    CanonicalForm coeff;
 
    if ( negate )
        coeff = -c;
    else
        coeff = c;
 
    while ( theCursor && aCursor )
    {
        if ( theCursor->exp == aCursor->exp + exp )
        {
            theCursor->coeff += aCursor->coeff * coeff;
            if(UNLIKELY(( theCursor->coeff.isZero() )))
            {
                if ( predCursor )
                {
                    predCursor->next = theCursor->next;
                    delete theCursor;
                    theCursor = predCursor->next;
                }
                else
                {
                    theList = theList->next;
                    delete theCursor;
                    theCursor = theList;
                }
            }
            else
            {
                predCursor = theCursor;
                theCursor = theCursor->next;
            }
            aCursor = aCursor->next;
        }
        else if ( theCursor->exp < aCursor->exp + exp )
        {
            if ( predCursor )
            {
                predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
                predCursor = predCursor->next;
            }
            else
            {
                theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
                predCursor = theList;
            }
            aCursor = aCursor->next;
        }
        else
        {
            predCursor = theCursor;
            theCursor = theCursor->next;
        }
    }
    if ( aCursor )
    {
        if ( predCursor )
        {
            predCursor->next = copyTermList( aCursor, lastTerm );
            predCursor = predCursor->next;
        }
        else
        {
            theList = copyTermList( aCursor, lastTerm );
            predCursor = theList;
        }
        while ( predCursor )
        {
            predCursor->exp += exp;
            predCursor->coeff *= coeff;
            predCursor = predCursor->next;
        }
    }
    else if ( ! theCursor )
        lastTerm = predCursor;
    return theList;
}

mulcoeff()

InternalCF * InternalPoly::mulcoeff ( InternalCF *  cc )

virtual

Reimplemented from InternalCF.

Definition at line 1181 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( c.isZero() )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0 );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0 );
        }
    }
    else  if ( c.isOne() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            mulTermList( firstTerm, c, 0 );
            return this;
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            mulTermList( first, c, 0 );
            return new InternalPoly( first, last, var );
        }
    }
}

mulsame()

InternalCF * InternalPoly::mulsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 366 of file int_poly.cc.

{
    if (is_imm(aCoeff)) return mulcoeff(aCoeff);
    InternalPoly *aPoly = (InternalPoly*)aCoeff;
    termList resultFirst = 0, resultLast = 0;
    termList theCursor = firstTerm;
 
    while ( theCursor )
    {
        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
                          theCursor->coeff, theCursor->exp, resultLast, false );
        theCursor = theCursor->next;
    }
    if ( inExtension() && getReduce( var ) )
    {
        resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
        if ( resultFirst == 0 )
        {
            if ( getRefCount() <= 1 )
            {
                delete this;
                return CFFactory::basic(0);
            }
            else
            {
                decRefCount();
                return CFFactory::basic(0);
            }
        }
        else  if ( resultFirst->exp == 0 )
        {
            if ( getRefCount() <= 1 )
            {
                InternalCF * res = resultFirst->coeff.getval();
                delete resultFirst;
                delete this;
                return res;
            }
            else
            {
                decRefCount();
                InternalCF * res = resultFirst->coeff.getval();
                delete resultFirst;
                return res;
            }
        }
    }
    if ( getRefCount() <= 1 )
    {
        freeTermList( firstTerm );
        firstTerm = resultFirst;
        lastTerm = resultLast;
        return this;
    }
    else
    {
        decRefCount();
        return new InternalPoly( resultFirst, resultLast, var );
    }
}

mulTermList()

void InternalPoly::mulTermList ( termList  theCursor, const CanonicalForm &  coeff, const int  exp  )

staticprivate

Definition at line 2038 of file int_poly.cc.

{
    while ( LIKELY(theCursor) )
    {
        theCursor->coeff *= coeff;
        theCursor->exp += exp;
        theCursor = theCursor->next;
    }
}

neg()

InternalCF * InternalPoly::neg ( )

virtual

InternalCF * InternalPoly::neg ()

See also

CanonicalForm::operator -()

Reimplemented from InternalCF.

Definition at line 231 of file int_poly.cc.

{
    if ( getRefCount() <= 1 )
    {
        negateTermList( firstTerm );
        return this;
    }
    else
    {
        decRefCount();
        termList last, first = copyTermList( firstTerm, last, true );
        return new InternalPoly( first, last, var );
    }
}

negateTermList()

void InternalPoly::negateTermList ( termList  terms )

staticprivate

Definition at line 1911 of file int_poly.cc.

{
    termList cursor = terms;
    while ( LIKELY(cursor) )
    {
        cursor->coeff = -cursor->coeff;
        cursor = cursor->next;
    }
}

operator delete()

void InternalPoly::operator delete ( void *  addr, size_t    )

inline

Definition at line 166 of file int_poly.h.

    {
      omFreeBin(addr, InternalPoly_bin);
    }

operator new()

void* InternalPoly::operator new ( size_t  )

inline

Definition at line 160 of file int_poly.h.

    {
      void* addr;
      omTypeAllocBin(void*, addr, InternalPoly_bin);
      return addr;
    }

print()

void InternalPoly::print ( OSTREAM &  aStream, char *  aString  )

virtual

Reimplemented from InternalCF.

Definition at line 179 of file int_poly.cc.

{
    if ( ! firstTerm )
        aStream << 0 << aString;
    else
    {
        char * theString;
        termList theCursor = firstTerm;
        while ( theCursor )
        {
            ostrstream theStream;
            if ( theCursor->exp == 0 )
                theCursor->coeff.print( aStream, aString );
            else  if ( theCursor->coeff.isOne() )
            {
                aStream << var;
                if ( theCursor->exp != 1 )
                    aStream << '^' << theCursor->exp << aString;
                else
                    aStream << aString;
            }
            else  if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() )
            {
                aStream << '-' << var;
                if ( theCursor->exp != 1 )
                    aStream << '^' << theCursor->exp << aString;
                else
                    aStream << aString;
            }
            else
            {
                theStream << '*' << var;
                if ( theCursor->exp != 1 )
                    theStream << '^' << theCursor->exp << aString << ends;
                else
                    theStream << aString << ends; // results from error in GNU strstream
                theString = theStream.str();
                theCursor->coeff.print( aStream, theString );
                theStream.freeze(0);//delete [] theString;
            }
            theCursor = theCursor->next;
            if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
                aStream << '+';
        }
    }
}

reduceTermList()

termList InternalPoly::reduceTermList ( termList  first, termList  redterms, termList &  last  )

staticprivate

Definition at line 2266 of file int_poly.cc.

{
    CanonicalForm coeff = CanonicalForm (1)/redterms->coeff;
    CanonicalForm newcoeff;
    int newexp;
    int exp = redterms->exp;
    termList dummy;
    while ( first && ( first->exp >= exp ) )
    {
        newcoeff = first->coeff * coeff;
        newexp = first->exp - exp;
        dummy = first;
        first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
        delete dummy;
    }
    return first;
}

sign()

int InternalPoly::sign ( ) const

virtual

int InternalPoly::sign () const

See also

CanonicalForm::sign()

Reimplemented from InternalCF.

Definition at line 110 of file int_poly.cc.

{
    return firstTerm->coeff.sign();
}

subcoeff()

InternalCF * InternalPoly::subcoeff ( InternalCF *  cc, bool  negate  )

virtual

Reimplemented from InternalCF.

Definition at line 1095 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( c.isZero() )
        if ( getRefCount() > 1 )
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last, negate );
            return new InternalPoly( first, last, var );
        }
        else
        {
            if ( negate )
                negateTermList( firstTerm );
            return this;
        }
    else
    {
        if ( getRefCount() <= 1 )
        {
            if ( lastTerm->exp == 0 )
            {
                if ( negate )
                {
                    negateTermList( firstTerm );
                    lastTerm->coeff += c;
                }
                else
                    lastTerm->coeff -= c;
                if ( lastTerm->coeff.isZero() )
                {
                    termList cursor = firstTerm;
                    while ( cursor->next != lastTerm )
                        cursor = cursor->next;
                    delete lastTerm;
                    cursor->next = 0;
                    lastTerm = cursor;
                }
            }
            else
            {
                if ( negate )
                {
                    negateTermList( firstTerm );
                    lastTerm->next = new term( 0, c, 0 );
                }
                else
                    lastTerm->next = new term( 0, -c, 0 );
                lastTerm = lastTerm->next;
            }
            return this;
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last, negate );
            if ( last->exp == 0 )
            {
                if ( negate )
                    last->coeff += c;
                else
                    last->coeff -= c;
                if ( last->coeff.isZero() )
                {
                    termList cursor = first;
                    while ( cursor->next != last )
                        cursor = cursor->next;
                    delete last;
                    cursor->next = 0;
                    last = cursor;
                }
            }
            else
            {
                if ( negate )
                    last->next = new term( 0, c, 0 );
                else
                    last->next = new term( 0, -c, 0 );
                last = last->next;
            }
            return new InternalPoly( first, last, var );
        }
    }
}

subsame()

InternalCF * InternalPoly::subsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 326 of file int_poly.cc.

{
    InternalPoly * aPoly = (InternalPoly*)aCoeff;
    if ( getRefCount() <= 1 )
    {
        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
        if ( firstTerm && firstTerm->exp != 0 )
            return this;
        else  if ( firstTerm )
        {
            InternalCF * res = firstTerm->coeff.getval();
            delete this;
            return res;
        }
        else
        {
            delete this;
            return CFFactory::basic( 0 );
        }
    }
    else
    {
        decRefCount();
        termList last, first = copyTermList( firstTerm, last );
        first = addTermList( first, aPoly->firstTerm, last, true );
        if ( first && first->exp != 0 )
            return new InternalPoly( first, last, var );
        else  if ( first )
        {
            InternalCF * res = first->coeff.getval();
            delete first;
            return res;
        }
        else
            return CFFactory::basic( 0 );
 
    }
}

tailcoeff()

CanonicalForm InternalPoly::tailcoeff ( )

virtual

CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()

See also

CanonicalForm::tailcoeff(), taildegree()

Reimplemented from InternalCF.

Definition at line 147 of file int_poly.cc.

{
    return lastTerm->coeff;
}

taildegree()

int InternalPoly::taildegree ( )

virtual

Reimplemented from InternalCF.

Definition at line 153 of file int_poly.cc.

{
    return lastTerm->exp;
}

tryDivcoeff()

InternalCF * InternalPoly::tryDivcoeff ( InternalCF *  cc, bool  invert, const CanonicalForm &  M, bool &  fail  )

virtual

Reimplemented from InternalCF.

Definition at line 1475 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( inExtension() && !getReduce( var ) && invert )
    {
        InternalCF * dummy;
        dummy = this->tryInvert(M, fail);
        if (fail)
        {
          if (getRefCount() <= 1)
            delete this;
          else
            decRefCount();
          return dummy;
        }
        dummy = dummy->mulcoeff( cc );
        if ( getRefCount() <= 1 )
        {
            delete this;
            return dummy;
        }
        else
        {
            decRefCount();
            return dummy;
        }
    }
    if ( invert )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0 );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0 );
        }
    }
    if ( c.isOne() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
            if (fail)
            {
              delete this;
              return CFFactory::basic (0);
            }
            if ( firstTerm && firstTerm->exp != 0 )
                return this;
            else  if ( firstTerm )
            {
                InternalCF * res = firstTerm->coeff.getval();
                delete this;
                return res;
            }
            else
            {
                delete this;
                return CFFactory::basic( 0 );
            }
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            first = tryDivTermList( first, c, last, M, fail );
            if (fail)
            {
              delete this;
              return CFFactory::basic (0);
            }
            if (fail)
            {
              delete first;
              return CFFactory::basic (0);
            }
            if ( first && first->exp != 0 )
                return new InternalPoly( first, last, var );
            else  if ( first )
            {
                InternalCF * res = first->coeff.getval();
                delete first;
                return res;
            }
            else
            {
                delete first;
                return CFFactory::basic( 0 );
            }
        }
    }
}

tryDividecoeff()

InternalCF * InternalPoly::tryDividecoeff ( InternalCF *  cc, bool  invert, const CanonicalForm &  M, bool &  fail  )

virtual

Reimplemented from InternalCF.

Definition at line 1303 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( inExtension() && !getReduce( var ) && invert )
    {
        InternalCF * dummy;
        dummy = this->tryInvert(M, fail);
        if (fail)
        {
          if (getRefCount() <= 1)
            delete this;
          else
            decRefCount();
          return dummy; //is equal to CFFactory::basic ( 0 ) in this case
        }
        if (is_imm(dummy))
        {
          if (is_imm(cc))
          {
            InternalInteger *d=new InternalInteger(imm2int(dummy)*imm2int(cc));
            dummy=d;
          }
          else
            dummy=cc->mulcoeff(dummy);
        }
        else dummy = dummy->mulcoeff( cc );
        if ( getRefCount() <= 1 )
        {
            delete this;
            return dummy;
        }
        else
        {
            decRefCount();
            return dummy;
        }
    }
    if ( invert )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0 );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0 );
        }
    }
    if ( c.isOne() )
        return this;
    //one should never get here
    else
    {
        if ( getRefCount() <= 1 )
        {
            firstTerm = divideTermList( firstTerm, c, lastTerm );
            if ( firstTerm && firstTerm->exp != 0 )
                return this;
            else  if ( firstTerm )
            {
                InternalCF * res = firstTerm->coeff.getval();
                delete this;
                return res;
            }
            else
            {
                delete this;
                return CFFactory::basic( 0 );
            }
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            first = divideTermList( first, c, last );
            if ( first && first->exp != 0 )
                return new InternalPoly( first, last, var );
            else  if ( first )
            {
                InternalCF * res = first->coeff.getval();
                delete first;
                return res;
            }
            else
            {
                delete first;
                return CFFactory::basic( 0 );
            }
        }
    }
}

tryDivremcoefft()

bool InternalPoly::tryDivremcoefft ( InternalCF *  cc, InternalCF *&  quot, InternalCF *&  rem, bool  invert, const CanonicalForm &  M, bool &  fail  )

virtual

Reimplemented from InternalCF.

Definition at line 1755 of file int_poly.cc.

{
    if ( inExtension() && !getReduce( var ) )
    {
        quot = copyObject();
        quot = quot->tryDividecoeff( cc, invert, M, fail );
        if (fail)
          return false;
        rem = CFFactory::basic( 0 );
        return true;
    }
    else  if ( invert )
    {
        if ( is_imm( cc ) )
            rem = cc;
        else
            rem = cc->copyObject();
        quot = CFFactory::basic( 0 );
        return true;
    }
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    ASSERT( ! c.isZero(), "divide by zero!" );
    termList quotfirst, quotcursor;
    termList cursor;
    CanonicalForm cquot, crem;
    bool divideok = true;
 
    cursor = firstTerm;
    quotcursor = quotfirst = new term;
 
    while ( cursor && divideok )
    {
        divideok = tryDivremt( cursor->coeff, c, cquot, crem, M, fail );
        if (fail)
        {
          freeTermList (quotfirst);
          return false;
        }
        divideok = divideok && crem.isZero();
        if ( divideok )
        {
            if ( ! cquot.isZero() )
            {
                quotcursor->next = new term( 0, cquot, cursor->exp );
                quotcursor = quotcursor->next;
            }
            cursor = cursor->next;
        }
    }
    quotcursor->next = 0;
    if ( divideok )
    {
        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
        if ( quotfirst )
            if ( quotfirst->exp == 0 )
            {
                quot = quotfirst->coeff.getval();
                delete quotfirst;
            }
            else
                quot = new InternalPoly( quotfirst, quotcursor, var );
        else
            quot = CFFactory::basic( 0 );
        rem = CFFactory::basic( 0 );
    }
    else
    {
        freeTermList( quotfirst );
    }
    return divideok;
}

tryDivremsamet()

bool InternalPoly::tryDivremsamet ( InternalCF *  acoeff, InternalCF *&  quot, InternalCF *&  rem, const CanonicalForm &  M, bool &  fail  )

virtual

Reimplemented from InternalCF.

Definition at line 883 of file int_poly.cc.

{
    if (inExtension() && !getReduce (var))
    {
       InternalCF * dummy = acoeff->tryInvert(M, fail);
       if (fail)
         return false;
       quot = dummy->tryMulsame( this, M);
       rem = CFFactory::basic( 0 );
       if (fail)
         return false;
       return true;
    }
    InternalPoly *aPoly = (InternalPoly*)acoeff;
    termList dummy, first, last, resultfirst = 0, resultlast = 0;
    CanonicalForm coeff, newcoeff, dummycoeff;
    int exp, newexp;
    bool divideok = true;
 
    first = copyTermList( firstTerm, last );
 
    coeff = aPoly->firstTerm->coeff;
    exp = aPoly->firstTerm->exp;
    while (first && ( first->exp >= exp ) && divideok )
    {
        divideok = tryDivremt( first->coeff, coeff, newcoeff, dummycoeff, M, fail );
        if (fail)
        {
          freeTermList (first);
          return false;
        }
        if ( divideok && dummycoeff.isZero() )
        {
            newexp = first->exp - exp;
            dummy = first;
            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
            delete dummy;
            if (!newcoeff.isZero())
              appendTermList( resultfirst, resultlast, newcoeff, newexp );
        }
        else
            divideok = false;
    }
    if ( divideok )
    {
        if ( resultfirst )
            if ( resultfirst->exp == 0 )
            {
                quot = resultfirst->coeff.getval();
                delete resultfirst;
            }
            else
                quot = new InternalPoly( resultfirst, resultlast, var );
        else
            quot = CFFactory::basic( 0 );
        if ( first )
            if ( first->exp == 0 )
            {
                rem = first->coeff.getval();
                delete first;
            }
            else
            {
                if (first->coeff.isZero())
                {
                  rem= CFFactory::basic (0);
                  delete first;
                }
                else
                  rem = new InternalPoly( first, last, var );
            }
        else
            rem = CFFactory::basic( 0 );
    }
    else
    {
        freeTermList( resultfirst );
        freeTermList( first );
    }
    return divideok;
}

tryDivsame()

InternalCF * InternalPoly::tryDivsame ( InternalCF *  aCoeff, const CanonicalForm &  M, bool &  fail  )

virtual

Reimplemented from InternalCF.

Definition at line 584 of file int_poly.cc.

{
    if ( inExtension() && !getReduce( var ) )
    {
        InternalCF * dummy = aCoeff->tryInvert(M, fail);
        if (fail)
          return CFFactory::basic( 0 );
        if (is_imm(dummy)) dummy=this->tryMulsame(dummy, M);
        else dummy = dummy->tryMulsame( this, M);
        if (fail)
        {
          if (getRefCount() <= 1)
            delete this;
          else
            decRefCount();
          return dummy;
        }
        if ( getRefCount() <= 1 )
        {
             delete this;
             return dummy;
        }
        else
        {
            decRefCount();
            return dummy;
        }
    }
    InternalPoly *aPoly = (InternalPoly*)aCoeff;
    termList dummy, first, last, resultfirst = 0, resultlast = 0;
    CanonicalForm coeff, newcoeff;
    int exp, newexp;
    bool singleObject;
 
    if ( getRefCount() <= 1 )
    {
        first = firstTerm; last = lastTerm; singleObject = true;
    }
    else
    {
        first = copyTermList( firstTerm, last ); singleObject = false;
        decRefCount();
    }
    coeff = aPoly->firstTerm->coeff;
    exp = aPoly->firstTerm->exp;
    while (first && ( first->exp >= exp ) )
    {
        newcoeff= first->coeff.tryDiv (coeff, M, fail);
        if (fail)
        {
          freeTermList (first);
          return CFFactory::basic (0);
        }
        newcoeff= reduce (newcoeff, M);
        newexp = first->exp - exp;
        dummy = first;
        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
        delete dummy;
        if (!newcoeff.isZero())
          appendTermList( resultfirst, resultlast, newcoeff, newexp );
    }
    freeTermList( first );
    if ( singleObject )
    {
        if ( resultfirst && resultfirst->exp != 0 )
        {
            firstTerm = resultfirst;
            lastTerm = resultlast;
            return this;
        }
        else  if ( resultfirst )
        {
            InternalCF * res = resultfirst->coeff.getval();
            delete resultfirst;
            firstTerm = 0;
            delete this;
            return res;
        }
        else
        {
            // this should not happen (evtl use assertion)
            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
            firstTerm = 0;
            delete this;
            return CFFactory::basic( 0 );
        }
    }
    else
    {
        if ( resultfirst && resultfirst->exp != 0 )
            return new InternalPoly( resultfirst, resultlast, var );
        else  if ( resultfirst )
        {
            InternalCF * res = resultfirst->coeff.getval();
            delete resultfirst;
            return res;
        }
        else
            return CFFactory::basic( 0 );
    }
}

tryDivTermList()

termList InternalPoly::tryDivTermList ( termList  firstTerm, const CanonicalForm &  coeff, termList &  lastTerm, const CanonicalForm &  M, bool &  fail  )

staticprivate

Definition at line 2107 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    lastTerm = 0;
    termList dummy;
 
    while ( theCursor )
    {
        theCursor->coeff.tryDiv( coeff, M, fail );
        if (fail)
          return 0;
        if ( theCursor->coeff.isZero() )
        {
            if ( theCursor == firstTerm )
                firstTerm = theCursor->next;
            else
                lastTerm->next = theCursor->next;
            dummy = theCursor;
            theCursor = theCursor->next;
            delete dummy;
        }
        else
        {
            lastTerm = theCursor;
            theCursor = theCursor->next;
        }
    }
    return firstTerm;
}

tryInvert()

InternalCF * InternalPoly::tryInvert ( const CanonicalForm &  M, bool &  fail  )

virtual

Reimplemented from InternalCF.

Definition at line 264 of file int_poly.cc.

{
  if ( inExtension() && !getReduce ( var ) )
  {
    CanonicalForm b, inverse;
    CanonicalForm F ( this ->copyObject() );
    Variable a = M.mvar();
    Variable x = Variable(1);
    F= mod (F, M); //reduce mod M
    CanonicalForm g= extgcd (replacevar( F, a, x ), replacevar( M, a, x ), inverse, b );
    if(!g.isOne())
      fail = true;
    else
      inverse = replacevar( inverse, x, a ); // change back to alg var
    CanonicalForm test= mod (inverse*F, M);
    return inverse.getval();
  }
  else
    return CFFactory::basic( 0 );
}

tryMulsame()

InternalCF * InternalPoly::tryMulsame ( InternalCF *  aCoeff, const CanonicalForm &  M  )

virtual

Reimplemented from InternalCF.

Definition at line 428 of file int_poly.cc.

{
    if (is_imm(aCoeff))
       return mulcoeff(aCoeff);
    InternalPoly *aPoly = (InternalPoly*)aCoeff;
    termList resultFirst = 0, resultLast = 0;
    termList theCursor = firstTerm;
 
    while ( theCursor )
    {
        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm,
                          theCursor->coeff, theCursor->exp, resultLast, false );
        theCursor = theCursor->next;
    }
    if ( inExtension() && !getReduce( var ) )
    {
        resultFirst= reduceTermList (resultFirst, ((InternalPoly*) M.getval())->firstTerm, resultLast);
        if ( resultFirst == 0 )
        {
            if ( getRefCount() <= 1 )
            {
                delete this;
                return CFFactory::basic(0);
            }
            else
            {
                decRefCount();
                return CFFactory::basic(0);
            }
        }
        else  if ( resultFirst->exp == 0 )
        {
            if ( getRefCount() <= 1 )
            {
                InternalCF * res = resultFirst->coeff.getval();
                delete resultFirst;
                delete this;
                return res;
            }
            else
            {
                decRefCount();
                InternalCF * res = resultFirst->coeff.getval();
                delete resultFirst;
                return res;
            }
        }
    }
    if ( getRefCount() <= 1 )
    {
        freeTermList( firstTerm );
        firstTerm = resultFirst;
        lastTerm = resultLast;
        return this;
    }
    else
    {
        decRefCount();
        return new InternalPoly( resultFirst, resultLast, var );
    }
}

variable()

Variable InternalPoly::variable ( ) const

inlinevirtual

Reimplemented from InternalCF.

Definition at line 98 of file int_poly.h.

{ return var; }

Friends And Related Function Documentation

CFIterator

friend class CFIterator

friend

Definition at line 171 of file int_poly.h.

Field Documentation

firstTerm

termList InternalPoly::firstTerm

private

Definition at line 73 of file int_poly.h.

InternalPoly_bin

const omBin InternalPoly::InternalPoly_bin = omGetSpecBin(sizeof(InternalPoly))

static

Definition at line 159 of file int_poly.h.

lastTerm

termList InternalPoly::lastTerm

private

Definition at line 73 of file int_poly.h.

var

Variable InternalPoly::var

private

Definition at line 74 of file int_poly.h.

---

The documentation for this class was generated from the following files:

• factory/int_poly.h
• factory/int_poly.cc