source: git/factory/int_poly.cc @ 84250a6

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