source: git/factory/int_poly.cc @ c284ce

fieker-DuValspielwiese
Last change on this file since c284ce was 43a44b, checked in by Jens Schmidt <schmidt@…>, 26 years ago
* int_poly.cc, int_pp.cc, int_rat.cc (neg): doc fixes git-svn-id: file:///usr/local/Singular/svn/trunk@2239 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 33.9 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: int_poly.cc,v 1.12 1998-06-26 16:15:28 schmidt Exp $ */
3
4#include <config.h>
5
6#ifndef NOSTREAMIO
7#include <string.h>
8#if defined(WINNT) && ! defined(__GNUC__)
9#include <strstrea.h>
10#else
11#include <strstream.h>
12#endif
13#endif /* NOSTREAMIO */
14
15#include "assert.h"
16
17#include "cf_defs.h"
18#include "cf_factory.h"
19#include "int_cf.h"
20#include "int_poly.h"
21#include "canonicalform.h"
22#include "variable.h"
23#include "imm.h"
24
25
26InternalPoly::InternalPoly( termList first, termList last, const Variable & v )
27{
28    firstTerm = first;
29    lastTerm = last;
30    var = v;
31}
32
33InternalPoly::InternalPoly()
34{
35    ASSERT( 0, "ups, why do you initialize an empty poly" );
36}
37
38InternalPoly::InternalPoly( const Variable & v, const int e, const CanonicalForm& c )
39{
40    var = v;
41    firstTerm = new term( 0, c, e );
42    lastTerm = firstTerm;
43}
44
45InternalPoly::InternalPoly( const InternalPoly& )
46{
47    ASSERT( 0, "ups there is something wrong in your code" );
48};
49
50InternalPoly::~InternalPoly()
51{
52    freeTermList( firstTerm );
53}
54
55InternalCF*
56InternalPoly::deepCopyObject() const
57{
58    termList first, last;
59    first = deepCopyTermList( firstTerm, last );
60    return new InternalPoly( first, last, var );
61}
62
63InternalCF*
64InternalPoly::genZero()
65{
66    return firstTerm->coeff.genZero().getval();
67}
68
69InternalCF*
70InternalPoly::genOne()
71{
72    return firstTerm->coeff.genOne().getval();
73}
74
75bool
76InternalPoly::isUnivariate() const
77{
78    termList cursor = firstTerm;
79    while ( cursor ) {
80        if ( ! cursor->coeff.inCoeffDomain() )
81            return false;
82        cursor = cursor->next;
83    }
84    return true;
85}
86
87//{{{ int InternalPoly::degree ()
88// docu: see CanonicalForm::sign ()
89int
90InternalPoly::degree ()
91{
92    return firstTerm->exp;
93}
94//}}}
95
96//{{{ int InternalPoly::sign () const
97// docu: see CanonicalForm::sign()
98int
99InternalPoly::sign () const
100{
101    return firstTerm->coeff.sign();
102}
103//}}}
104
105//{{{ CanonicalForm InternalPoly::lc (), Lc (), LC ()
106// docu: see CanonicalForm::lc(), Lc(), LC()
107CanonicalForm
108InternalPoly::lc ()
109{
110    return firstTerm->coeff.lc();
111}
112
113CanonicalForm
114InternalPoly::Lc ()
115{
116    return firstTerm->coeff.Lc();
117}
118
119CanonicalForm
120InternalPoly::LC ()
121{
122    return firstTerm->coeff;
123}
124//}}}
125
126//{{{ CanonicalForm InternalPoly::tailcoeff (), int InternalPoly::taildegree ()
127// docu: see CanonicalForm::tailcoeff(), taildegree()
128CanonicalForm
129InternalPoly::tailcoeff ()
130{
131    return lastTerm->coeff;
132}
133
134int
135InternalPoly::taildegree ()
136{
137    return lastTerm->exp;
138}
139//}}}
140
141//{{{ CanonicalForm InternalPoly::coeff ( int i )
142// docu: see CanonicalForm::operator []()
143CanonicalForm
144InternalPoly::coeff ( int i )
145{
146    termList theCursor = firstTerm;
147    while ( theCursor ) {
148        if ( theCursor->exp == i )
149            return theCursor->coeff;
150        else if ( theCursor->exp < i )
151            return CanonicalForm( 0 );
152        else
153            theCursor = theCursor->next;
154    }
155    return CanonicalForm( 0 );
156}
157//}}}
158
159#ifndef NOSTREAMIO
160void
161InternalPoly::print(ostream &aStream, char * aString )
162{
163    if ( ! firstTerm )
164        aStream << 0 << aString;
165    else {
166        char * theString;
167        termList theCursor = firstTerm;
168        while ( theCursor ) {
169            ostrstream theStream;
170            if ( theCursor->exp == 0 )
171                theCursor->coeff.print( aStream, aString );
172            else  if ( theCursor->coeff.isOne() ) {
173                aStream << var;
174                if ( theCursor->exp != 1 )
175                    aStream << '^' << theCursor->exp << aString;
176                else
177                    aStream << aString;
178            }
179            else  if ( theCursor->coeff.sign() < 0 && (-theCursor->coeff).isOne() ) {
180                aStream << '-' << var;
181                if ( theCursor->exp != 1 )
182                    aStream << '^' << theCursor->exp << aString;
183                else
184                    aStream << aString;
185            }
186            else {
187                theStream << '*' << var;
188                if ( theCursor->exp != 1 )
189                    theStream << '^' << theCursor->exp << aString << ends;
190                else
191                    theStream << aString << ends; // results from error in GNU strstream
192                theString = theStream.str();
193                theCursor->coeff.print( aStream, theString );
194                delete [] theString;
195            }
196            theCursor = theCursor->next;
197            if ( theCursor && ( theCursor->coeff.sign() >= 0 ) )
198                aStream << '+';
199        }
200    }
201}
202#endif /* NOSTREAMIO */
203
204//{{{ InternalCF * InternalPoly::neg ()
205// docu: see CanonicalForm::operator -()
206InternalCF *
207InternalPoly::neg ()
208{
209    if ( getRefCount() == 1 ) {
210        negateTermList( firstTerm );
211        return this;
212    } else {
213        decRefCount();
214        termList last, first = copyTermList( firstTerm, last, true );
215        return new InternalPoly( first, last, var );
216    }
217}
218//}}}
219
220InternalCF*
221InternalPoly::invert()
222{
223    if ( inExtension() && getReduce( var ) ) {
224        setReduce( var, false );
225        CanonicalForm a( this->copyObject() );
226        CanonicalForm b = getMipo( var );
227        CanonicalForm u, v;
228        CanonicalForm g = extgcd( a, b, u, v );
229        setReduce( var, true );
230        return u.getval();
231    }
232    else
233        return CFFactory::basic( 0 );
234}
235
236InternalCF*
237InternalPoly::addsame( InternalCF* aCoeff )
238{
239    InternalPoly * aPoly = (InternalPoly*)aCoeff;
240    if ( getRefCount() == 1 ) {
241        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, false );
242        if ( firstTerm && firstTerm->exp != 0 )
243            return this;
244        else  if ( firstTerm ) {
245            InternalCF * res = firstTerm->coeff.getval();
246            delete this;
247            return res;
248        }
249        else {
250            delete this;
251            return CFFactory::basic( 0 );
252        }
253    }
254    else {
255        decRefCount();
256        termList last, first = copyTermList( firstTerm, last );
257        first = addTermList( first, aPoly->firstTerm, last, false );
258        if ( first && first->exp != 0 )
259            return new InternalPoly( first, last, var );
260        else  if ( first ) {
261            InternalCF * res = first->coeff.getval();
262            delete first;
263            return res;
264        }
265        else
266            return CFFactory::basic( 0 );
267
268    }
269}
270
271InternalCF*
272InternalPoly::subsame( InternalCF* aCoeff )
273{
274    InternalPoly * aPoly = (InternalPoly*)aCoeff;
275    if ( getRefCount() == 1 ) {
276        firstTerm = addTermList( firstTerm, aPoly->firstTerm, lastTerm, true );
277        if ( firstTerm && firstTerm->exp != 0 )
278            return this;
279        else  if ( firstTerm ) {
280            InternalCF * res = firstTerm->coeff.getval();
281            delete this;
282            return res;
283        }
284        else {
285            delete this;
286            return CFFactory::basic( 0 );
287        }
288    }
289    else {
290        decRefCount();
291        termList last, first = copyTermList( firstTerm, last );
292        first = addTermList( first, aPoly->firstTerm, last, true );
293        if ( first && first->exp != 0 )
294            return new InternalPoly( first, last, var );
295        else  if ( first ) {
296            InternalCF * res = first->coeff.getval();
297            delete first;
298            return res;
299        }
300        else
301            return CFFactory::basic( 0 );
302
303    }
304}
305
306InternalCF*
307InternalPoly::mulsame( InternalCF* aCoeff )
308{
309    InternalPoly *aPoly = (InternalPoly*)aCoeff;
310    termList resultFirst = 0, resultLast = 0;
311    termList theCursor = firstTerm;
312
313    while ( theCursor ) {
314        resultFirst = mulAddTermList( resultFirst, aPoly->firstTerm, theCursor->coeff, theCursor->exp, resultLast, false );
315        theCursor = theCursor->next;
316    }
317    if ( inExtension() && getReduce( var ) ) {
318        resultFirst = reduceTermList( resultFirst, (getInternalMipo( var ))->firstTerm, resultLast );
319        if ( resultFirst == 0 )
320            if ( getRefCount() == 1 ) {
321                delete this;
322                return CFFactory::basic(0);
323            }
324            else {
325                decRefCount();
326                return CFFactory::basic(0);
327            }
328        else  if ( resultFirst->exp == 0 )
329            if ( getRefCount() == 1 ) {
330                InternalCF * res = resultFirst->coeff.getval();
331                delete resultFirst;
332                delete this;
333                return res;
334            }
335            else {
336                decRefCount();
337                InternalCF * res = resultFirst->coeff.getval();
338                delete resultFirst;
339                return res;
340            }
341    }
342    if ( getRefCount() == 1 ) {
343        freeTermList( firstTerm );
344        firstTerm = resultFirst;
345        lastTerm = resultLast;
346        return this;
347    }
348    else {
349        decRefCount();
350        return new InternalPoly( resultFirst, resultLast, var );
351    }
352}
353
354InternalCF*
355InternalPoly::dividesame( InternalCF* aCoeff )
356{
357    return divsame( aCoeff );
358}
359
360
361InternalCF*
362InternalPoly::divsame( InternalCF* aCoeff )
363{
364    if ( inExtension() && getReduce( var ) ) {
365        InternalCF * dummy = aCoeff->invert();
366        dummy = dummy->mulsame( this );
367        if ( getRefCount() == 1 ) {
368             delete this;
369             return dummy;
370        }
371        else {
372            decRefCount();
373            return dummy;
374        }
375    }
376    InternalPoly *aPoly = (InternalPoly*)aCoeff;
377    termList dummy, first, last, resultfirst = 0, resultlast = 0;
378    CanonicalForm coeff, newcoeff;
379    int exp, newexp;
380    bool singleObject;
381
382    if ( getRefCount() == 1 ) {
383        first = firstTerm; last = lastTerm; singleObject = true;
384    }
385    else {
386        first = copyTermList( firstTerm, last ); singleObject = false;
387        decRefCount();
388    }
389    coeff = aPoly->firstTerm->coeff;
390    exp = aPoly->firstTerm->exp;
391    while (first && ( first->exp >= exp ) ) {
392        newcoeff = first->coeff / coeff;
393        newexp = first->exp - exp;
394        dummy = first;
395        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
396        delete dummy;
397        appendTermList( resultfirst, resultlast, newcoeff, newexp );
398    }
399    freeTermList( first );
400    if ( singleObject ) {
401        if ( resultfirst && resultfirst->exp != 0 ) {
402            firstTerm = resultfirst;
403            lastTerm = resultlast;
404            return this;
405        }
406        else  if ( resultfirst ) {
407            InternalCF * res = resultfirst->coeff.getval();
408            delete resultfirst;
409            firstTerm = 0;
410            delete this;
411            return res;
412        }
413        else {
414            // this should not happen (evtl use assertion)
415            ASSERT( 0, "FATAL ERROR, PLEASE INFORM THE AUTHOR" );
416            firstTerm = 0;
417            delete this;
418            return CFFactory::basic( 0 );
419        }
420    }
421    else {
422        if ( resultfirst && resultfirst->exp != 0 )
423            return new InternalPoly( resultfirst, resultlast, var );
424        else  if ( resultfirst ) {
425            InternalCF * res = resultfirst->coeff.getval();
426            delete resultfirst;
427            return res;
428        }
429        else
430            return CFFactory::basic( 0 );
431    }
432}
433
434InternalCF*
435InternalPoly::modulosame( InternalCF* aCoeff )
436{
437    return modsame( aCoeff );
438}
439
440InternalCF*
441InternalPoly::modsame( InternalCF* aCoeff )
442{
443    if ( inExtension() && getReduce( var ) ) {
444        if ( deleteObject() ) delete this;
445        return CFFactory::basic( 0 );
446    }
447    InternalPoly *aPoly = (InternalPoly*)aCoeff;
448    termList dummy, first, last;
449    CanonicalForm coeff, newcoeff;
450    int exp, newexp;
451    bool singleObject;
452
453    if ( getRefCount() == 1 ) {
454        first = firstTerm; last = lastTerm; singleObject = true;
455    }
456    else {
457        first = copyTermList( firstTerm, last ); singleObject = false;
458        decRefCount();
459    }
460    coeff = aPoly->firstTerm->coeff;
461    exp = aPoly->firstTerm->exp;
462    while (first && ( first->exp >= exp ) ) {
463        newcoeff = first->coeff / coeff;
464        newexp = first->exp - exp;
465        dummy = first;
466        first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
467        delete dummy;
468    }
469    if ( singleObject ) {
470        if ( first && first->exp != 0 ) {
471            firstTerm = first;
472            lastTerm = last;
473            return this;
474        }
475        else  if ( first ) {
476            InternalCF * res = first->coeff.getval();
477            delete first;
478            firstTerm = 0;
479            delete this;
480            return res;
481        }
482        else {
483            firstTerm = 0;
484            delete this;
485            return CFFactory::basic( 0 );
486        }
487    }
488    else {
489        if ( first && first->exp != 0 )
490            return new InternalPoly( first, last, var );
491        else  if ( first ) {
492            InternalCF * res = first->coeff.getval();
493            delete first;
494            return res;
495        }
496        else
497            return CFFactory::basic( 0 );
498    }
499}
500
501
502void
503InternalPoly::divremsame( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
504{
505    if ( inExtension() && getReduce( var ) ) {
506        InternalCF * dummy = acoeff->invert();
507        quot = dummy->mulsame( this );
508        rem = CFFactory::basic( 0 );
509    }
510    else {
511        InternalPoly *aPoly = (InternalPoly*)acoeff;
512        termList dummy, first, last, resultfirst = 0, resultlast = 0;
513        CanonicalForm coeff, newcoeff;
514        int exp, newexp;
515
516        first = copyTermList( firstTerm, last );
517
518        coeff = aPoly->firstTerm->coeff;
519        exp = aPoly->firstTerm->exp;
520        while (first && ( first->exp >= exp ) ) {
521            newcoeff = first->coeff / coeff;
522            newexp = first->exp - exp;
523            dummy = first;
524            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
525            delete dummy;
526            appendTermList( resultfirst, resultlast, newcoeff, newexp );
527        }
528        if ( resultfirst )
529            if ( resultfirst->exp == 0 ) {
530                quot = resultfirst->coeff.getval();
531                delete resultfirst;
532            }
533            else
534                quot = new InternalPoly( resultfirst, resultlast, var );
535        else
536            quot = CFFactory::basic( 0 );
537        if ( first )
538            if ( first->exp == 0 ) {
539                rem = first->coeff.getval();
540                delete first;
541            }
542            else
543                rem = new InternalPoly( first, last, var );
544        else
545            rem = CFFactory::basic( 0 );
546    }
547}
548
549
550bool
551InternalPoly::divremsamet( InternalCF* acoeff, InternalCF*& quot, InternalCF*& rem )
552{
553    if ( inExtension() && getReduce( var ) ) {
554        divremsame( acoeff, quot, rem );
555        return true;
556    }
557    InternalPoly *aPoly = (InternalPoly*)acoeff;
558    termList dummy, first, last, resultfirst = 0, resultlast = 0;
559    CanonicalForm coeff, newcoeff, dummycoeff;
560    int exp, newexp;
561    bool divideok = true;
562
563//    if ( ! ::divremt( lastTerm->coeff, aPoly->lastTerm->coeff, newcoeff, dummycoeff ) )
564//      return false;
565
566    first = copyTermList( firstTerm, last );
567
568    coeff = aPoly->firstTerm->coeff;
569    exp = aPoly->firstTerm->exp;
570    while (first && ( first->exp >= exp ) && divideok ) {
571        divideok = ::divremt( first->coeff, coeff, newcoeff, dummycoeff );
572        if ( divideok && dummycoeff.isZero() ) {
573            newexp = first->exp - exp;
574            dummy = first;
575            first = mulAddTermList( first->next, aPoly->firstTerm->next, newcoeff, newexp, last, true );
576            delete dummy;
577            appendTermList( resultfirst, resultlast, newcoeff, newexp );
578        }
579        else
580            divideok = false;
581    }
582    if ( divideok ) {
583        if ( resultfirst )
584            if ( resultfirst->exp == 0 ) {
585                quot = resultfirst->coeff.getval();
586                delete resultfirst;
587            }
588            else
589                quot = new InternalPoly( resultfirst, resultlast, var );
590        else
591            quot = CFFactory::basic( 0 );
592        if ( first )
593            if ( first->exp == 0 ) {
594                rem = first->coeff.getval();
595                delete first;
596            }
597            else
598                rem = new InternalPoly( first, last, var );
599        else
600            rem = CFFactory::basic( 0 );
601    }
602    else {
603        freeTermList( resultfirst );
604        freeTermList( first );
605    }
606    return divideok;
607}
608
609//{{{ int InternalPoly::comparesame, comparecoeff ( InternalCF * acoeff )
610//{{{ docu
611//
612// comparesame(), comparecoeff() - compare with an
613//   InternalPoly.
614//
615// comparecoeff() always returns 1 since CO is defined to be
616// larger than anything which is a coefficient w.r.t. CO.
617//
618// comparesame() compares the coefficient vectors of f=CO and
619// g=acoeff w.r.t to a lexicographic order in the following way:
620// f < g iff there exists an 0 <= i <= max(deg(f),deg(g)) s.t.
621// i) f[j] = g[j] for all i < j <= max(deg(f),deg(g)) and
622// ii) g[i] occurs in g (i.e. is not equal to zero) and
623//     f[i] does not occur in f or f[i] < g[i] if f[i] occurs
624// where f[i] denotes the coefficient to the power x^i of f.
625//
626// As usual, comparesame() returns 1 if CO is larger than c, 0 if
627// CO equals c, and -1 if CO is less than c.  However, this
628// function is optimized to test on equality since this is its
629// most important and frequent usage.
630//
631// See the respective `CanonicalForm'-methods for an explanation
632// why we define such a strange (but total) ordering on
633// polynomials.
634//
635// See also: CanonicalForm::operator <(), CanonicalForm::operator ==()
636//
637//}}}
638int
639InternalPoly::comparesame ( InternalCF * acoeff )
640{
641    ASSERT( ! ::is_imm( acoeff ) && acoeff->level() > LEVELBASE, "incompatible base coefficients" );
642    InternalPoly* apoly = (InternalPoly*)acoeff;
643    // check on triviality
644    if ( this == apoly )
645        return 0;
646    else {
647        termList cursor1 = firstTerm;
648        termList cursor2 = apoly->firstTerm;
649        for ( ; cursor1 && cursor2; cursor1 = cursor1->next, cursor2 = cursor2->next )
650            // we test on inequality of coefficients at this
651            // point instead of testing on "less than" at the
652            // last `else' in the enclosed `if' statement since a
653            // test on inequaltiy in general is cheaper
654            if ( (cursor1->exp != cursor2->exp) || (cursor1->coeff != cursor2->coeff) )
655                if ( cursor1->exp > cursor2->exp )
656                    return 1;
657                else  if ( cursor1->exp < cursor2->exp )
658                    return -1;
659                else  if ( cursor1->coeff > cursor2->coeff )
660                    return 1;
661                else
662                    return -1;
663        // check trailing terms
664        if ( cursor1 == cursor2 )
665            return 0;
666        else if ( cursor1 != 0 )
667            return 1;
668        else
669            return -1;
670    }
671}
672
673int
674InternalPoly::comparecoeff ( InternalCF * )
675{
676    return 1;
677}
678//}}}
679
680InternalCF*
681InternalPoly::addcoeff( InternalCF* cc )
682{
683    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
684    if ( c.isZero() )
685        return this;
686    else {
687        if ( getRefCount() == 1 ) {
688            if ( lastTerm->exp == 0 ) {
689                lastTerm->coeff += c;
690                if ( lastTerm->coeff.isZero() ) {
691                    termList cursor = firstTerm;
692                    while ( cursor->next != lastTerm )
693                        cursor = cursor->next;
694                    delete lastTerm;
695                    cursor->next = 0;
696                    lastTerm = cursor;
697                }
698            }
699            else {
700                lastTerm->next = new term( 0, c, 0 );
701                lastTerm = lastTerm->next;
702            }
703            return this;
704        }
705        else {
706            decRefCount();
707            termList last, first = copyTermList( firstTerm, last, false );
708            if ( last->exp == 0 ) {
709                last->coeff += c;
710                if ( last->coeff.isZero() ) {
711                    termList cursor = first;
712                    while ( cursor->next != last )
713                        cursor = cursor->next;
714                    delete last;
715                    cursor->next = 0;
716                    last = cursor;
717                }
718            }
719            else {
720                last->next = new term( 0, c, 0 );
721                last = last->next;
722            }
723            return new InternalPoly( first, last, var );
724        }
725    }
726}
727
728InternalCF*
729InternalPoly::subcoeff( InternalCF* cc, bool negate )
730{
731    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
732    if ( c.isZero() )
733        if ( getRefCount() > 1 ) {
734            decRefCount();
735            termList last, first = copyTermList( firstTerm, last, negate );
736            return new InternalPoly( first, last, var );
737        }
738        else {
739            if ( negate )
740                negateTermList( firstTerm );
741            return this;
742        }
743    else {
744        if ( getRefCount() == 1 ) {
745            if ( lastTerm->exp == 0 ) {
746                if ( negate ) {
747                    negateTermList( firstTerm );
748                    lastTerm->coeff += c;
749                }
750                else
751                    lastTerm->coeff -= c;
752                if ( lastTerm->coeff.isZero() ) {
753                    termList cursor = firstTerm;
754                    while ( cursor->next != lastTerm )
755                        cursor = cursor->next;
756                    delete lastTerm;
757                    cursor->next = 0;
758                    lastTerm = cursor;
759                }
760            }
761            else {
762                if ( negate ) {
763                    negateTermList( firstTerm );
764                    lastTerm->next = new term( 0, c, 0 );
765                }
766                else
767                    lastTerm->next = new term( 0, -c, 0 );
768                lastTerm = lastTerm->next;
769            }
770            return this;
771        }
772        else {
773            decRefCount();
774            termList last, first = copyTermList( firstTerm, last, negate );
775            if ( last->exp == 0 ) {
776                if ( negate )
777                    last->coeff += c;
778                else
779                    last->coeff -= c;
780                if ( last->coeff.isZero() ) {
781                    termList cursor = first;
782                    while ( cursor->next != last )
783                        cursor = cursor->next;
784                    delete last;
785                    cursor->next = 0;
786                    last = cursor;
787                }
788            }
789            else {
790                if ( negate )
791                    last->next = new term( 0, c, 0 );
792                else
793                    last->next = new term( 0, -c, 0 );
794                last = last->next;
795            }
796            return new InternalPoly( first, last, var );
797        }
798    }
799}
800
801InternalCF*
802InternalPoly::mulcoeff( InternalCF* cc )
803{
804    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
805    if ( c.isZero() ) {
806        if ( getRefCount() == 1 ) {
807            delete this;
808            return CFFactory::basic( 0 );
809        }
810        else {
811            decRefCount();
812            return CFFactory::basic( 0 );
813        }
814    }
815    else  if ( c.isOne() )
816        return this;
817    else {
818        if ( getRefCount() == 1 ) {
819            mulTermList( firstTerm, c, 0 );
820            return this;
821        }
822        else {
823            decRefCount();
824            termList last, first = copyTermList( firstTerm, last );
825            mulTermList( first, c, 0 );
826            return new InternalPoly( first, last, var );
827        }
828    }
829}
830
831InternalCF*
832InternalPoly::dividecoeff( InternalCF* cc, bool invert )
833{
834    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
835    if ( inExtension() && getReduce( var ) && invert ) {
836        InternalCF * dummy;
837        dummy = this->invert();
838        dummy = dummy->mulcoeff( cc );
839        if ( getRefCount() == 1 ) {
840            delete this;
841            return dummy;
842        }
843        else {
844            decRefCount();
845            return dummy;
846        }
847    }
848    if ( invert )
849        if ( getRefCount() == 1 ) {
850            delete this;
851            return CFFactory::basic( 0 );
852        }
853        else {
854            decRefCount();
855            return CFFactory::basic( 0 );
856        }
857    if ( c.isOne() )
858        return this;
859    else {
860        if ( getRefCount() == 1 ) {
861            firstTerm = divideTermList( firstTerm, c, lastTerm );
862            if ( firstTerm && firstTerm->exp != 0 )
863                return this;
864            else  if ( firstTerm ) {
865                InternalCF * res = firstTerm->coeff.getval();
866                delete this;
867                return res;
868            }
869            else {
870                delete this;
871                return CFFactory::basic( 0 );
872            }
873        }
874        else {
875            decRefCount();
876            termList last, first = copyTermList( firstTerm, last );
877            first = divideTermList( first, c, last );
878            if ( first && first->exp != 0 )
879                return new InternalPoly( first, last, var );
880            else  if ( first ) {
881                InternalCF * res = first->coeff.getval();
882                delete first;
883                return res;
884            }
885            else {
886                delete first;
887                return CFFactory::basic( 0 );
888            }
889        }
890    }
891}
892
893InternalCF*
894InternalPoly::divcoeff( InternalCF* cc, bool invert )
895{
896    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
897    if ( inExtension() && getReduce( var ) && invert ) {
898        InternalCF * dummy;
899        dummy = this->invert();
900        dummy = dummy->mulcoeff( cc );
901        if ( getRefCount() == 1 ) {
902            delete this;
903            return dummy;
904        }
905        else {
906            decRefCount();
907            return dummy;
908        }
909    }
910    if ( invert )
911        if ( getRefCount() == 1 ) {
912            delete this;
913            return CFFactory::basic( 0 );
914        }
915        else {
916            decRefCount();
917            return CFFactory::basic( 0 );
918        }
919    if ( c.isOne() )
920        return this;
921    else {
922        if ( getRefCount() == 1 ) {
923            firstTerm = divTermList( firstTerm, c, lastTerm );
924            if ( firstTerm && firstTerm->exp != 0 )
925                return this;
926            else  if ( firstTerm ) {
927                InternalCF * res = firstTerm->coeff.getval();
928                delete this;
929                return res;
930            }
931            else {
932                delete this;
933                return CFFactory::basic( 0 );
934            }
935        }
936        else {
937            decRefCount();
938            termList last, first = copyTermList( firstTerm, last );
939            first = divTermList( first, c, last );
940            if ( first && first->exp != 0 )
941                return new InternalPoly( first, last, var );
942            else  if ( first ) {
943                InternalCF * res = first->coeff.getval();
944                delete first;
945                return res;
946            }
947            else {
948                delete first;
949                return CFFactory::basic( 0 );
950            }
951        }
952    }
953}
954
955InternalCF*
956InternalPoly::modulocoeff( InternalCF* cc, bool invert )
957{
958    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
959    if ( invert ) {
960        if ( deleteObject() ) delete this;
961        return c.getval();
962    }
963    ASSERT( ! c.isZero(), "divide by zero!" );
964    if ( deleteObject() ) delete this;
965    return CFFactory::basic( 0 );
966}
967
968InternalCF*
969InternalPoly::modcoeff( InternalCF* cc, bool invert )
970{
971    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
972    if ( invert ) {
973        if ( deleteObject() ) delete this;
974        return c.getval();
975    }
976    ASSERT( ! c.isZero(), "divide by zero!" );
977    if ( c.isOne() ) {
978        if ( getRefCount() == 1 ) {
979            delete this;
980            return CFFactory::basic( 0 );
981        }
982        else {
983            decRefCount();
984            return CFFactory::basic( 0 );
985        }
986    }
987    else {
988        if ( getRefCount() == 1 ) {
989            firstTerm = modTermList( firstTerm, c, lastTerm );
990            if ( firstTerm && firstTerm->exp != 0 )
991                return this;
992            else  if ( firstTerm ) {
993                InternalCF * res = firstTerm->coeff.getval();
994                delete this;
995                return res;
996            }
997            else {
998                delete this;
999                return CFFactory::basic( 0 );
1000            }
1001        }
1002        else {
1003            decRefCount();
1004            termList last, first = copyTermList( firstTerm, last );
1005            first = modTermList( first, c, last );
1006            if ( first && first->exp != 0 )
1007                return new InternalPoly( first, last, var );
1008            else  if ( first ) {
1009                InternalCF * res = first->coeff.getval();
1010                delete first;
1011                return res;
1012            }
1013            else {
1014                delete first;
1015                return CFFactory::basic( 0 );
1016            }
1017        }
1018    }
1019}
1020
1021void
1022InternalPoly::divremcoeff( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
1023{
1024    if ( inExtension() && getReduce( var ) ) {
1025        quot = copyObject();
1026        quot = quot->dividecoeff( cc, invert );
1027        rem = CFFactory::basic( 0 );
1028    }
1029    else  if ( invert ) {
1030        if ( is_imm( cc ) )
1031            rem = cc;
1032        else
1033            rem = cc->copyObject();
1034        quot = CFFactory::basic( 0 );
1035    }
1036    else {
1037        CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1038        ASSERT( ! c.isZero(), "divide by zero!" );
1039        termList quotlast, quotfirst = copyTermList( firstTerm, quotlast );
1040        quotfirst = divideTermList( quotfirst, c, quotlast );
1041        if ( quotfirst )
1042            if ( quotfirst->exp == 0 ) {
1043                quot = quotfirst->coeff.getval();
1044                delete quotfirst;
1045            }
1046            else
1047                quot = new InternalPoly( quotfirst, quotlast, var );
1048        else
1049            quot = CFFactory::basic( 0 );
1050        rem = CFFactory::basic( 0 );
1051    }
1052}
1053
1054bool
1055InternalPoly::divremcoefft( InternalCF* cc, InternalCF*& quot, InternalCF*& rem, bool invert )
1056{
1057    if ( inExtension() && getReduce( var ) ) {
1058        quot = copyObject();
1059        quot = quot->dividecoeff( cc, invert );
1060        rem = CFFactory::basic( 0 );
1061        return true;
1062    }
1063    else  if ( invert ) {
1064        if ( is_imm( cc ) )
1065            rem = cc;
1066        else
1067            rem = cc->copyObject();
1068        quot = CFFactory::basic( 0 );
1069        return true;
1070    }
1071    CanonicalForm c( is_imm(cc) ? cc : cc->copyObject() );
1072    ASSERT( ! c.isZero(), "divide by zero!" );
1073    termList quotfirst, quotcursor;
1074    termList cursor;
1075    CanonicalForm cquot, crem;
1076    bool divideok = true;
1077
1078    cursor = firstTerm;
1079    quotcursor = quotfirst = new term;
1080
1081    while ( cursor && divideok ) {
1082        divideok = ::divremt( cursor->coeff, c, cquot, crem );
1083        divideok = divideok && crem.isZero();
1084        if ( divideok ) {
1085            if ( ! cquot.isZero() ) {
1086                quotcursor->next = new term( 0, cquot, cursor->exp );
1087                quotcursor = quotcursor->next;
1088            }
1089            cursor = cursor->next;
1090        }
1091    }
1092    quotcursor->next = 0;
1093    if ( divideok ) {
1094        cursor = quotfirst; quotfirst = quotfirst->next; delete cursor;
1095        if ( quotfirst )
1096            if ( quotfirst->exp == 0 ) {
1097                quot = quotfirst->coeff.getval();
1098                delete quotfirst;
1099            }
1100            else
1101                quot = new InternalPoly( quotfirst, quotcursor, var );
1102        else
1103            quot = CFFactory::basic( 0 );
1104        rem = CFFactory::basic( 0 );
1105    }
1106    else {
1107        freeTermList( quotfirst );
1108    }
1109    return divideok;
1110}
1111
1112// static functions
1113
1114termList
1115InternalPoly::copyTermList ( termList aTermList, termList& theLastTerm, bool negate )
1116{
1117    if ( aTermList == 0 )
1118        return 0;
1119    else  if ( negate ) {
1120        termList sourceCursor = aTermList;
1121        termList dummy = new term;
1122        termList targetCursor = dummy;
1123
1124        while ( sourceCursor ) {
1125            targetCursor->next = new term( 0, -sourceCursor->coeff, sourceCursor->exp );
1126            targetCursor = targetCursor->next;
1127            sourceCursor = sourceCursor->next;
1128        }
1129        targetCursor->next = 0;
1130        theLastTerm = targetCursor;
1131        targetCursor = dummy->next;
1132        delete dummy;
1133        return targetCursor;
1134    }
1135    else {
1136        termList sourceCursor = aTermList;
1137        termList dummy = new term;
1138        termList targetCursor = dummy;
1139
1140        while ( sourceCursor ) {
1141            targetCursor->next = new term( 0, sourceCursor->coeff, sourceCursor->exp );
1142            targetCursor = targetCursor->next;
1143            sourceCursor = sourceCursor->next;
1144        }
1145        targetCursor->next = 0;
1146        theLastTerm = targetCursor;
1147        targetCursor = dummy->next;
1148        delete dummy;
1149        return targetCursor;
1150    }
1151}
1152
1153termList
1154InternalPoly::deepCopyTermList ( termList aTermList, termList& theLastTerm )
1155{
1156    if ( aTermList == 0 )
1157        return 0;
1158    else {
1159        termList sourceCursor = aTermList;
1160        termList dummy = new term;
1161        termList targetCursor = dummy;
1162
1163        while ( sourceCursor ) {
1164            targetCursor->next = new term( 0, sourceCursor->coeff.deepCopy(), sourceCursor->exp );
1165            targetCursor = targetCursor->next;
1166            sourceCursor = sourceCursor->next;
1167        }
1168        targetCursor->next = 0;
1169        theLastTerm = targetCursor;
1170        targetCursor = dummy->next;
1171        delete dummy;
1172        return targetCursor;
1173    }
1174}
1175
1176void
1177InternalPoly::freeTermList ( termList aTermList )
1178{
1179    termList cursor = aTermList;
1180
1181    while ( cursor ) {
1182        cursor = cursor->next;
1183        delete aTermList;
1184        aTermList = cursor;
1185    }
1186}
1187
1188void
1189InternalPoly::negateTermList ( termList terms )
1190{
1191    termList cursor = terms;
1192    while ( cursor ) {
1193        cursor->coeff = -cursor->coeff;
1194        cursor = cursor->next;
1195    }
1196}
1197
1198termList
1199InternalPoly::addTermList ( termList theList, termList aList, termList& lastTerm, bool negate )
1200{
1201    termList theCursor = theList;
1202    termList aCursor = aList;
1203    termList predCursor = 0;
1204
1205    while ( theCursor && aCursor ) {
1206        if ( theCursor->exp == aCursor->exp ) {
1207            if ( negate )
1208                theCursor->coeff -= aCursor->coeff;
1209            else
1210                theCursor->coeff += aCursor->coeff;
1211            if ( theCursor->coeff.isZero() ) {
1212                if ( predCursor ) {
1213                    predCursor->next = theCursor->next;
1214                    delete theCursor;
1215                    theCursor = predCursor->next;
1216                }
1217                else {
1218                    theList = theList->next;
1219                    delete theCursor;
1220                    theCursor = theList;
1221                }
1222            }
1223            else {
1224                predCursor = theCursor;
1225                theCursor = theCursor->next;
1226            }
1227            aCursor = aCursor->next;
1228        }
1229        else if ( theCursor->exp < aCursor->exp ) {
1230            if ( negate )
1231                if ( predCursor ) {
1232                    predCursor->next = new term( theCursor, -aCursor->coeff, aCursor->exp );
1233                    predCursor = predCursor->next;
1234                }
1235                else {
1236                    theList = new term( theCursor, -aCursor->coeff, aCursor->exp );
1237                    predCursor = theList;
1238                }
1239            else
1240                if ( predCursor ) {
1241                    predCursor->next = new term( theCursor, aCursor->coeff, aCursor->exp );
1242                    predCursor = predCursor->next;
1243                }
1244                else {
1245                    theList = new term( theCursor, aCursor->coeff, aCursor->exp );
1246                    predCursor = theList;
1247                }
1248            aCursor = aCursor->next;
1249        }
1250        else {
1251            predCursor = theCursor;
1252            theCursor = theCursor->next;
1253        }
1254    }
1255    if ( aCursor ) {
1256        if ( predCursor )
1257            predCursor->next = copyTermList( aCursor, lastTerm, negate );
1258        else
1259            theList = copyTermList( aCursor, lastTerm, negate );
1260    }
1261    else if ( ! theCursor )
1262        lastTerm = predCursor;
1263
1264    return theList;
1265}
1266
1267void
1268InternalPoly::mulTermList ( termList theCursor, const CanonicalForm& coeff, const int exp )
1269{
1270    while ( theCursor ) {
1271        theCursor->coeff *= coeff;
1272        theCursor->exp += exp;
1273        theCursor = theCursor->next;
1274    }
1275}
1276
1277termList
1278InternalPoly::divideTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1279{
1280    termList theCursor = firstTerm;
1281    lastTerm = 0;
1282    termList dummy;
1283
1284    while ( theCursor ) {
1285        theCursor->coeff /= coeff;
1286        if ( theCursor->coeff.isZero() ) {
1287            if ( theCursor == firstTerm )
1288                firstTerm = theCursor->next;
1289            else
1290                lastTerm->next = theCursor->next;
1291            dummy = theCursor;
1292            theCursor = theCursor->next;
1293            delete dummy;
1294        }
1295        else {
1296            lastTerm = theCursor;
1297            theCursor = theCursor->next;
1298        }
1299    }
1300    return firstTerm;
1301}
1302
1303termList
1304InternalPoly::divTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1305{
1306    termList theCursor = firstTerm;
1307    lastTerm = 0;
1308    termList dummy;
1309
1310    while ( theCursor ) {
1311        theCursor->coeff.div( coeff );
1312        if ( theCursor->coeff.isZero() ) {
1313            if ( theCursor == firstTerm )
1314                firstTerm = theCursor->next;
1315            else
1316                lastTerm->next = theCursor->next;
1317            dummy = theCursor;
1318            theCursor = theCursor->next;
1319            delete dummy;
1320        }
1321        else {
1322            lastTerm = theCursor;
1323            theCursor = theCursor->next;
1324        }
1325    }
1326    return firstTerm;
1327}
1328
1329termList
1330InternalPoly::modTermList ( termList firstTerm, const CanonicalForm& coeff, termList& lastTerm )
1331{
1332    termList theCursor = firstTerm;
1333    lastTerm = 0;
1334    termList dummy;
1335
1336    while ( theCursor ) {
1337        theCursor->coeff.mod( coeff );
1338        if ( theCursor->coeff.isZero() ) {
1339            if ( theCursor == firstTerm )
1340                firstTerm = theCursor->next;
1341            else
1342                lastTerm->next = theCursor->next;
1343            dummy = theCursor;
1344            theCursor = theCursor-> next;
1345            delete dummy;
1346        }
1347        else {
1348            lastTerm = theCursor;
1349            theCursor = theCursor->next;
1350        }
1351    }
1352    return firstTerm;
1353}
1354
1355void
1356InternalPoly::appendTermList ( termList& first, termList& last, const CanonicalForm& coeff, const int exp )
1357{
1358    if ( last ) {
1359        last->next = new term( 0, coeff, exp );
1360        last = last->next;
1361    }
1362    else {
1363        first = new term( 0, coeff, exp );
1364        last = first;
1365    }
1366}
1367
1368termList
1369InternalPoly::mulAddTermList ( termList theList, termList aList, const CanonicalForm & c, const int exp, termList & lastTerm, bool negate )
1370{
1371    termList theCursor = theList;
1372    termList aCursor = aList;
1373    termList predCursor = 0;
1374    CanonicalForm coeff;
1375
1376    if ( negate )
1377        coeff = -c;
1378    else
1379        coeff = c;
1380
1381    while ( theCursor && aCursor ) {
1382        if ( theCursor->exp == aCursor->exp + exp ) {
1383            theCursor->coeff += aCursor->coeff * coeff;
1384            if ( theCursor->coeff.isZero() ) {
1385                if ( predCursor ) {
1386                    predCursor->next = theCursor->next;
1387                    delete theCursor;
1388                    theCursor = predCursor->next;
1389                }
1390                else {
1391                    theList = theList->next;
1392                    delete theCursor;
1393                    theCursor = theList;
1394                }
1395            }
1396            else {
1397                predCursor = theCursor;
1398                theCursor = theCursor->next;
1399            }
1400            aCursor = aCursor->next;
1401        }
1402        else if ( theCursor->exp < aCursor->exp + exp ) {
1403            if ( predCursor ) {
1404                predCursor->next = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1405                predCursor = predCursor->next;
1406            }
1407            else {
1408                theList = new term( theCursor, aCursor->coeff * coeff, aCursor->exp + exp );
1409                predCursor = theList;
1410            }
1411            aCursor = aCursor->next;
1412        }
1413        else {
1414            predCursor = theCursor;
1415            theCursor = theCursor->next;
1416        }
1417    }
1418    if ( aCursor ) {
1419        if ( predCursor ) {
1420            predCursor->next = copyTermList( aCursor, lastTerm );
1421            predCursor = predCursor->next;
1422        }
1423        else {
1424            theList = copyTermList( aCursor, lastTerm );
1425            predCursor = theList;
1426        }
1427        while ( predCursor ) {
1428            predCursor->exp += exp;
1429            predCursor->coeff *= coeff;
1430            predCursor = predCursor->next;
1431        }
1432    }
1433    else if ( ! theCursor )
1434        lastTerm = predCursor;
1435    return theList;
1436}
1437
1438termList
1439InternalPoly::reduceTermList ( termList first, termList redterms, termList & last )
1440{
1441    CanonicalForm coeff = redterms->coeff;
1442    CanonicalForm newcoeff;
1443    int newexp;
1444    int exp = redterms->exp;
1445    termList dummy;
1446    while ( first && ( first->exp >= exp ) ) {
1447        newcoeff = first->coeff / coeff;
1448        newexp = first->exp - exp;
1449        dummy = first;
1450        first = mulAddTermList( first->next, redterms->next, newcoeff, newexp, last, true );
1451        delete dummy;
1452    }
1453    return first;
1454}
Note: See TracBrowser for help on using the repository browser.