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 38 of file int_poly.cc.

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

InternalPoly() [2/4]

InternalPoly::InternalPoly

(

)

Definition at line 45 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 50 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 57 of file int_poly.cc.

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

~InternalPoly()

InternalPoly::~InternalPoly

(

)

Definition at line 62 of file int_poly.cc.

{
    freeTermList( firstTerm );
}

Member Function Documentation

addcoeff()

InternalCF * InternalPoly::addcoeff ( InternalCF *  cc )

virtual

Reimplemented from InternalCF.

Definition at line 1042 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 290 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( 0L );
        }
    }
    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( 0L );

    }
}

addTermList()

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

staticprivate

Definition at line 1926 of file int_poly.cc.

{
    termList theCursor = theList;
    termList aCursor = aList;
    termList predCursor = 0;

    while ( theCursor && aCursor )
    {
        if ( theCursor->exp == aCursor->exp )
        {
            if ( negate )
                theCursor->coeff -= aCursor->coeff;
            else
                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 ( negate )
                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;
                }
            else
                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 2137 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 166 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 1036 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 994 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 1834 of file int_poly.cc.

{
    if ( aTermList == 0 )
        return 0;
    else  if ( negate )
    {
        termList sourceCursor = aTermList;
        termList dummy = new term;
        termList targetCursor = dummy;

        while ( 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 ( 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 68 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 1877 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 104 of file int_poly.cc.

{
    return firstTerm->exp;
}

divcoeff()

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

virtual

Reimplemented from InternalCF.

Definition at line 1403 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( 0L );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0L );
        }
    }
    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( 0L );
            }
        }
        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( 0L );
            }
        }
    }
}

dividecoeff()

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

virtual

Reimplemented from InternalCF.

Definition at line 1221 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( 0L );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0L );
        }
    }
    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( 0L );
            }
        }
        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( 0L );
            }
        }
    }
}

dividesame()

InternalCF * InternalPoly::dividesame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 495 of file int_poly.cc.

{
    return divsame( aCoeff );
}

divideTermList()

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

staticprivate

Definition at line 2019 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    lastTerm = 0;
    termList dummy;

    while ( 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 1656 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        quot = copyObject();
        quot = quot->dividecoeff( cc, invert );
        rem = CFFactory::basic( 0L );
    }
    else  if ( invert )
    {
        if ( is_imm( cc ) )
            rem = cc;
        else
            rem = cc->copyObject();
        quot = CFFactory::basic( 0L );
    }
    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( 0L );
        rem = CFFactory::basic( 0L );
    }
}

divremcoefft()

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

virtual

Reimplemented from InternalCF.

Definition at line 1693 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        quot = copyObject();
        quot = quot->dividecoeff( cc, invert );
        rem = CFFactory::basic( 0L );
        return true;
    }
    else  if ( invert )
    {
        if ( is_imm( cc ) )
            rem = cc;
        else
            rem = cc->copyObject();
        quot = CFFactory::basic( 0L );
        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( 0L );
        rem = CFFactory::basic( 0L );
    }
    else
    {
        freeTermList( quotfirst );
    }
    return divideok;
}

divremsame()

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

virtual

Reimplemented from InternalCF.

Definition at line 769 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        InternalCF * dummy = acoeff->invert();
        quot = dummy->mulsame( this );
        rem = CFFactory::basic( 0L );
    }
    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( 0L );
        if ( first )
            if ( first->exp == 0 )
            {
                rem = first->coeff.getval();
                delete first;
            }
            else
                rem = new InternalPoly( first, last, var );
        else
            rem = CFFactory::basic( 0L );
    }
}

divremsamet()

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

virtual

Reimplemented from InternalCF.

Definition at line 821 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( 0L );
        if ( first )
            if ( first->exp == 0 )
            {
                rem = first->coeff.getval();
                delete first;
            }
            else
                rem = new InternalPoly( first, last, var );
        else
            rem = CFFactory::basic( 0L );
    }
    else
    {
        freeTermList( resultfirst );
        freeTermList( first );
    }
    return divideok;
}

divsame()

InternalCF * InternalPoly::divsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 502 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( 0L );
        }
    }
    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( 0L );
    }
}

divTermList()

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

staticprivate

Definition at line 2048 of file int_poly.cc.

{
    termList theCursor = firstTerm;
    lastTerm = 0;
    termList dummy;

    while ( 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 1902 of file int_poly.cc.

{
    termList cursor = aTermList;

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

genOne()

InternalCF * InternalPoly::genOne ( )

virtual

Reimplemented from InternalCF.

Definition at line 82 of file int_poly.cc.

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

genZero()

InternalCF * InternalPoly::genZero ( )

virtual

Reimplemented from InternalCF.

Definition at line 76 of file int_poly.cc.

{
    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 251 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( 0L );
}

isUnivariate()

bool InternalPoly::isUnivariate ( ) const

virtual

Reimplemented from InternalCF.

Definition at line 88 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 124 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 133 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 142 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 1592 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( 0L );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0L );
        }
    }
    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( 0L );
            }
        }
        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( 0L );
            }
        }
    }
}

modsame()

InternalCF * InternalPoly::modsame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 697 of file int_poly.cc.

{
    if ( inExtension() && getReduce( var ) )
    {
        if ( deleteObject() ) delete this;
        return CFFactory::basic( 0L );
    }
    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( 0L );
        }
    }
    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( 0L );
    }
}

modTermList()

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

staticprivate

Definition at line 2108 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 1578 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( 0L );
}

modulosame()

InternalCF * InternalPoly::modulosame ( InternalCF *  aCoeff )

virtual

Reimplemented from InternalCF.

Definition at line 691 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 2152 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 ( 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 1185 of file int_poly.cc.

{
    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
    if ( c.isZero() )
    {
        if ( getRefCount() <= 1 )
        {
            delete this;
            return CFFactory::basic( 0L );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0L );
        }
    }
    else  if ( c.isOne() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            mulTermList( firstTerm, c, 0L );
            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 370 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(0L);
            }
            else
            {
                decRefCount();
                return CFFactory::basic(0L);
            }
        }
        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 2008 of file int_poly.cc.

{
    while ( 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 235 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 1915 of file int_poly.cc.

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

operator delete()

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

inline

Definition at line 162 of file int_poly.h.

    {
      omFreeBin(addr, InternalPoly_bin);
    }

operator new()

void* InternalPoly::operator new ( size_t  )

inline

Definition at line 156 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 183 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 2236 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 114 of file int_poly.cc.

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

subcoeff()

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

virtual

Reimplemented from InternalCF.

Definition at line 1099 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 330 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( 0L );
        }
    }
    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( 0L );

    }
}

tailcoeff()

CanonicalForm InternalPoly::tailcoeff ( )

virtual

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

See also

CanonicalForm::tailcoeff(), taildegree()

Reimplemented from InternalCF.

Definition at line 151 of file int_poly.cc.

{
    return lastTerm->coeff;
}

taildegree()

int InternalPoly::taildegree ( )

virtual

Reimplemented from InternalCF.

Definition at line 157 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 1479 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( 0L );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0L );
        }
    }
    if ( c.isOne() )
        return this;
    else
    {
        if ( getRefCount() <= 1 )
        {
            firstTerm = tryDivTermList( firstTerm, c, lastTerm, M, fail );
            if (fail)
            {
              delete this;
              return CFFactory::basic (0L);
            }
            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( 0L );
            }
        }
        else
        {
            decRefCount();
            termList last, first = copyTermList( firstTerm, last );
            first = tryDivTermList( first, c, last, M, fail );
            if (fail)
            {
              delete this;
              return CFFactory::basic (0L);
            }
            if (fail)
            {
              delete first;
              return CFFactory::basic (0L);
            }
            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( 0L );
            }
        }
    }
}

tryDividecoeff()

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

virtual

Reimplemented from InternalCF.

Definition at line 1307 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 ( 0L ) 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( 0L );
        }
        else
        {
            decRefCount();
            return CFFactory::basic( 0L );
        }
    }
    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( 0L );
            }
        }
        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( 0L );
            }
        }
    }
}

tryDivremcoefft()

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

virtual

Reimplemented from InternalCF.

Definition at line 1759 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( 0L );
        return true;
    }
    else  if ( invert )
    {
        if ( is_imm( cc ) )
            rem = cc;
        else
            rem = cc->copyObject();
        quot = CFFactory::basic( 0L );
        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( 0L );
        rem = CFFactory::basic( 0L );
    }
    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 887 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( 0L );
       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( 0L );
        if ( first )
            if ( first->exp == 0 )
            {
                rem = first->coeff.getval();
                delete first;
            }
            else
            {
                if (first->coeff.isZero())
                {
                  rem= CFFactory::basic (0L);
                  delete first;
                }
                else
                  rem = new InternalPoly( first, last, var );
            }
        else
            rem = CFFactory::basic( 0L );
    }
    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 588 of file int_poly.cc.

{
    if ( inExtension() && !getReduce( var ) )
    {
        InternalCF * dummy = aCoeff->tryInvert(M, fail);
        if (fail)
          return CFFactory::basic( 0L );
        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 (0L);
        }
        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( 0L );
        }
    }
    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( 0L );
    }
}

tryDivTermList()

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

staticprivate

Definition at line 2077 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 268 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( 0L );
}

tryMulsame()

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

virtual

Reimplemented from InternalCF.

Definition at line 432 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(0L);
            }
            else
            {
                decRefCount();
                return CFFactory::basic(0L);
            }
        }
        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 167 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 155 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