source: git/factory/int_poly.cc @ 2dd068

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